?

　　CRC即循環冗余校驗碼(Cyclic Redundancy Check)：是數據通信領域中最常用的一種差錯校驗碼，其特征是信息字段和校驗字段的長度可以任意選定。

　　循環冗余校驗碼(CRC)的基本原理

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

　　CRC幾個基本概念

　　1、多項式與二進制數碼

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

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

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

　　而發送信息位 1111，可轉換為數據多項式為C(x)=x3+x2+x+1。

　　2、生成多項式

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

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

　　應滿足以下條件：

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

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

　　c、不同位發生錯誤時，應該使余數不同。

　　d、對余數繼續做除，應使余數循環。

　　將這些要求反映為數學關系是比較復雜的。但可以從有關資料查到常用的對應于不同碼制的生成多項式如圖9所示：

　　N K 碼距d G(x)多項式 G(x)

　　7 4 3 x3+x+1

　　1011

　　7 4 3 x3+x2+1

　　1101

　　7 3 4 x4+x3+x2+1

　　11101

　　7 3 4 x4+x2+x+1

　　10111

　　15 11 3 x4+x+1

　　10011

　　15 7 5 x8+x7+x6+x4+1

　　111010001

　　31 26 3 x5+x2+1

　　100101

　　31 21 5 x10+x9+x8+x6+x5+x3+1

　　11101101001

　　63 57 3 x6+x+1

　　1000011

　　63 51 5 x12+x10+x5+x4+x2+1

　　1010000110101

　　1041 1024 x16+x15+x2+1

　　11000000000000101

　　3 CRC碼的生成步驟

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

　　2、將信息碼左移R位，相當與對應的信息多項式C(x)*2的R次方

　　3、用生成多項式(二進制數)對信息碼做除，得到R位的余數。

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