crc校驗基本原理

?

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

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

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

　　CRC幾個基本概念

　　1、多項式與二進制數(shù)碼

　　多項式和二進制數(shù)有直接對應關系：x的最高冪次對應二進制數(shù)的最高位，以下各位對應多項式的各冪次，有此冪次項對應1，無此冪次項對應0?？梢钥闯觯簒的最高冪次為R，轉(zhuǎn)換成對應的二進制數(shù)有R+1位。

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

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

　　而發(fā)送信息位 1111，可轉(zhuǎn)換為數(shù)據(jù)多項式為C(x)=x3+x2+x+1。

　　2、生成多項式

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

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

　　應滿足以下條件：

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

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

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

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

　　將這些要求反映為數(shù)學關系是比較復雜的。但可以從有關資料查到常用的對應于不同碼制的生成多項式如圖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)轉(zhuǎn)換成對應的R+1位二進制數(shù)。

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

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

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