天天看點

CRC校驗

1、循環校驗碼(CRC碼):是資料通信領域中最常用的一種差錯校驗碼,其特征是資訊字段和校驗字段的長度可以任意標明。

2、生成CRC碼的基本原理:任意一個由二進制位串組成的代碼都可以和一個系數僅為‘0’和‘1’取值的多項式一一對應。例如:代碼1010111對應的多項式為x6+x4+x2+x+1,而多項式為x5+x3+x2+x+1對應的代碼101111。

3、CRC碼集選擇的原則:若設碼字長度為N,資訊字段為K位,校驗字段為R位(N=K+R),則對于CRC碼集中的任一碼字,存在且僅存在一個R次多項式g(x),使得

V(x)=A(x)g(x)=xRm(x)+r(x);

其中:    m(x)為K次資訊多項式, r(x)為R-1次校驗多項式,

         g(x)稱為生成多項式:

g(x)=g0+g1x+ g2x2+...+g(R-1)x(R-1)+gRxR

發送方通過指定的g(x)産生CRC碼字,接收方則通過該g(x)來驗證收到的CRC碼字。

4、CRC校驗碼軟體生成方法:

    借助于多項式除法,其餘數為校驗字段。

例如:資訊字段代碼為: 1011001;對應m(x)=x6+x4+x3+1 

      假設生成多項式為:g(x)=x4+x3+1;則對應g(x)的代碼為: 11001

      x4m(x)=x10+x8+x7+x4 對應的代碼記為:10110010000;

采用多項式除法:  得餘數為: 1010     (即校驗字段為:1010)

發送方:發出的傳輸字段為:  1 0 1 1 0 0 1 1 0 10

                          資訊字段       校驗字段

接收方:使用相同的生成碼進行校驗:接收到的字段/生成碼(二進制除法)如果能夠除盡,則正确。

通俗一點講,就是首先由要發送的資訊碼1 0 1 1 0 0 1 和生成多項式碼11001得到最終要發送的資訊的長度即資訊碼長度+生成多項式碼長度-1。在計算最終資訊碼的時候首先将資訊碼後面補多項式碼長度-1個0,即1 0 1 1 0 0 1 0000,然後将得到的中間碼和多項式碼進行模2除法,并将最後的餘數1010,添加到資訊碼的後面即1 0 1 1 0 0 1 1 0 10,最終生成CRC校驗碼。