CRC的校驗原理以及例子

一、基本原理

    CRC檢驗原理實際上就是在一個p位二進制資料序列之後附加一個r位二進制檢驗碼(序列)，進而構成一個總長為n＝p＋r位的二進制序列；附加在資料序列之後的這個檢驗碼與資料序列的内容之間存在着某種特定的關系。如果因幹擾等原因使資料序列中的某一位或某些位發生錯誤，這種特定關系就會被破壞。是以，通過檢查這一關系，就可以實作對資料正确性的檢驗。

二、幾個基本概念

1、幀檢驗序列FCS（Frame Check Sequence）：為了進行差錯檢驗而添加的備援碼。

2、多項式模2運作：實際上是按位異或(Exclusive OR)運算，即相同為0，相異為1，也就是不考慮進位、借位的二進制加減運算。如：10011011 + 11001010 = 01010001。

3、生成多項式（generator polynomial）：當進行CRC檢驗時，發送方與接收方需要事先約定一個除數，即生成多項式，一般記作G（x）。生成多項式的最高位與最低位必須是1。常用的CRC碼的生成多項式有：

CRC8=X8+X5+X4+1

CRC-CCITT=X16+X12+X5+1

CRC16=X16+X15+X5+1

CRC12=X12+X11+X3+X2+1

CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1

每一個生成多項式都可以與一個代碼相對應，如CRC8對應代碼：100110001。

三，生成步驟

1、将X的最高次幂為R的生成多項式G(X)轉換成對應的R+1位二進制數。

2、将資訊碼左移R位，相當于對應的資訊多項式C(X)*2R。

3、用生成多項式（二進制數）對資訊碼做除，得到R位的餘數。

4、将餘數拼到資訊碼左移後空出的位置，得到完整的CRC碼。

【例】假設使用的生成多項式是G(X)=X3+X+1。4位的原始封包為1010。

四、CRC檢驗碼的計算

設資訊字段為K位，校驗字段為R位，則碼字長度為N(N=K+R)。設雙方事先約定了一個R次多項式g(x)，則CRC碼：

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

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

這裡r(x)對應的代碼即為備援碼，加在原資訊字段後即形成CRC碼。

r(x)的計算方法為：在K位資訊字段的後面添加R個0，再除以g(x)對應的代碼序列，得到的餘數即為r(x)對應的代碼(應為R－1位；若不足，而在高位補0)。

計算示例：

設需要發送的資訊為M = 1010001101，CRC8=X5+X4+X2+1産生多項式對應的代碼為P = 110101，R＝5。在M後加5個0為計算序列：101000110100000，然後對P做模2除法運算，得餘數r(x)對應的代碼：01110。故實際需要發送的資料是101000110101110。其中CRC校驗碼就為：01110。

五、錯誤檢測

    當接收方收到資料後，用收到的資料對P（事先約定的）進行模2除法，若餘數為0，則認為資料傳輸無差錯；若餘數不為0，則認為資料傳輸出現了錯誤，由于不知道錯誤發生在什麼地方，因而不能進行自動糾正，一般的做法是丢棄接收的資料。

注釋 幾點說明：

    1、CRC是一種常用的檢錯碼，并不能用于自動糾錯。

    2、隻要經過嚴格的挑選，并使用位數足夠多的除數P，那麼出現檢測不到的差錯的機率就很小很小。

    3、僅用循環備援檢驗 CRC 差錯檢測技術隻能做到無差錯接受（隻是非常近似的認為是無差錯的），并不能保證可靠傳輸。