CRC校驗

一、什么是CRC校驗

CRC校驗（即循環(huán)冗余校驗）是數據通訊中最常采用檢錯糾錯的一種校驗方式，它廣泛應用于數據鏈路層的數據傳輸中，以保證數據傳輸可靠性的一種差錯檢測措施。其特征是信息字段和校驗字段的長度可以任意選定。循環(huán)冗余檢查（CRC）是一種數據傳輸檢錯功能，對數據進行多項式計算，并將得到的結果附在幀的后面，接收設備也執(zhí)行類似的算法，以保證數據傳輸的正確性和完整性。CRC 算法的基本思想是將傳輸的數據當做一個位數很長的數。將這個數除以另一個數。得到的余數作為校驗數據附加到原數據后面。

循環(huán)冗余校驗碼（CRC）的基本原理是：在K位信息碼后再拼接R位的校驗碼，整個編碼長度為N位，因此，這種編碼也叫（N，K）碼。對于一個給定的（N，K）碼，可以證明存在一個最高次冪為N-K=R的多項式G(x)。根據G(x)可以生成K位信息的校驗碼，而G(x)叫做這個CRC碼的生成多項式。 校驗碼的具體生成過程為：假設要發(fā)送的信息用多項式C(X)表示，將C(x)左移R位（可表示成C(x)*2R），這樣C(x)的右邊就會空出R位，這就是校驗碼的位置。用 C(x)*2R 除以生成多項式G(x)得到的余數就是校驗碼。

任意一個由二進制位串組成的代碼都可以和一個系數僅為‘0’和‘1’取值的多項式一一對應。例如：代碼1010111對應的多項式為x6+x4+x2+x+1，而多項式為x5+x3+x2+x+1對應的代碼101111。

二、基本概念

1.對應關系

多項式和二進制數有直接對應關系：X的最高冪次對應二進制數的最高位，以下各位對應多項式的各冪次，有此冪次項對應1，無此冪次項對應0。可以看出：X的最高冪次為R，轉換成對應的二進制數有R+1位。

多項式包括生成多項式G(X)和信息多項式C(X)。

如生成多項式為G(X)=X4+X3+X+1， 可轉換為二進制數碼11011。

而發(fā)送信息位 101111，可轉換為數據多項式為C(X)=X5+X3+X2+X+1。

2.生成多項式

是接受方和發(fā)送方的一個約定，也就是一個二進制數，在整個傳輸過程中，這個數始終保持不變。

在發(fā)送方，利用生成多項式對信息多項式做模2除生成校驗碼。在接收方利用生成多項式對收到的編碼多項式做模2除檢測和確定錯誤位置。

應滿足以下條件：

A、生成多項式的最高位和最低位必須為1。

B、當被傳送信息（CRC碼）任何一位發(fā)生錯誤時，被生成多項式做除后應該使余數不為0。

C、不同位發(fā)生錯誤時，應該使余數不同。

D、對余數繼續(xù)做除，應使余數循環(huán)。

3.校驗碼位數

CRC校驗碼位數 = 生成多項式位數 - 1。注意有些生成多項式的簡記式中將生成多項式的最高位1省略了。

4.生成步驟

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

2、將信息碼左移R位，相當于對應的信息多項式C(X)*2R。

3、用生成多項式（二進制數）對信息碼做除，得到R位的余數(注意：這里的二進制做除法得到的余數其實是模2除法得到的余數，并不等于其對應十進制數做除法得到的余數。)。

4、將余數拼到信息碼左移后空出的位置，得到完整的CRC碼。

三、舉例

【例】假設使用的生成多項式是G(X)=X3+X+1。4位的原始報文為1010，求編碼后的報文。

解：

1、將生成多項式G(X)=X3+X+1轉換成對應的二進制除數1011。

2、此題生成多項式有4位（R+1）(注意：4位的生成多項式計算所得的校驗碼為3位，R為校驗碼位數)，要把原始報文C(X)左移3（R）位變成1010 000

3、用生成多項式對應的二進制數對左移3位后的原始報文進行模2除（高位對齊），相當于按位異或：

1010000

1011

------------------

0001000

0001011

------------------

0000011

得到的余位011，所以最終編碼為：1010 011

四、原則

若設碼字長度為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次校驗多項式（即CRC校驗和），

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

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

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

五、生成方法

借助于模2除法則，其余數為校驗字段。

例如：信息字段代碼為: 1011001；對應m(x)=x6+x4+x3+1

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

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

采用模2除法則: 得余數為: 1010(即校驗字段為：1010）

發(fā)送方：發(fā)出的傳輸字段為: 1 0 1 1 0 0 1 1010

信息字段 校驗字段

接收方：使用相同的生成碼進行校驗:接收到的字段/生成碼（二進制除法）

如果能夠除盡，則正確，

給出余數（1010）的計算步驟：

除法沒有數學上的含義，而是采用計算機的模二除法，即除數和被除數做異或運算。進行異或運算時除數和被除數最高位對齊，按位異或。

10110010000

^11001

--------------------------

01111010000

1111010000

^11001

-------------------------

0011110000

11110000

^11001

--------------------------

00111000

111000

^11001

-------------------

001010

則四位CRC校驗碼就為：1010。

利用CRC進行檢錯的過程可簡單描述為：在發(fā)送端根據要傳送的k位二進制碼序列，以一定的規(guī)則產生一個校驗用的r位監(jiān)督碼(CRC碼)，附在原始信息后邊，構成一個新的二進制碼序列數共k+r位，然后發(fā)送出去。在接收端，根據信息碼和CRC碼之間所遵循的規(guī)則進行檢驗，以確定傳送中是否出錯。這個規(guī)則，在差錯控制理論中稱為“生成多項式”。