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

《循環(huán)冗余校驗碼(crc)的基本原理》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

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

2、余數(shù)就是校驗碼。幾個基本概念1、多項式與二進(jìn)制數(shù)碼多項式和二進(jìn)制數(shù)有直接對應(yīng)關(guān)系：x的最高冪次對應(yīng)二進(jìn)制數(shù)的最高位，以下各位對應(yīng)多項式的各冪次，有此冪次項對應(yīng)1，無此冪次項對應(yīng)0?？梢钥闯觯簒的最高冪次為R，轉(zhuǎn)換成對應(yīng)的二進(jìn)制數(shù)有R+1位。多項式包括生成多項式G(x)和信息多項式f(x)。如生成多項式為G(x)=X4+X3+X+1，可轉(zhuǎn)換為二進(jìn)制數(shù)碼11011。而發(fā)送信息位1111，可轉(zhuǎn)換為數(shù)據(jù)多項式為f(x)=X3+X2+X+1。2、生成多項式是接受方和發(fā)送方的一個約定，也就是一個二進(jìn)制數(shù)，在整個傳輸過程中，這個數(shù)始終

3、保持不變。在發(fā)送方,利用生成多項式對信息多項式做模2除生成校驗碼。在接受方利用生成多項式對收到的編碼多項式做模2除檢測和確定錯誤位置。應(yīng)滿足以下條件：a、生成多項式的最高位和最低位必須為1。b、當(dāng)被傳送信息（CRC碼）任何一位發(fā)生錯誤時，被生成多項式做模2除后應(yīng)該使余數(shù)不為0。c、不同位發(fā)生錯誤時，應(yīng)該使余數(shù)不同。d、對余數(shù)繼續(xù)做模2除，應(yīng)使余數(shù)循環(huán)。將這些要求反映為數(shù)學(xué)關(guān)系是比較復(fù)雜的。但可以從有關(guān)資料查到常用的對應(yīng)于不同碼制的生成多項式如圖9所示：N??????????K??????????碼距d??????????

4、G(x)多項式??????????G(x)7??????????4??????????3??????????x3+x+1??????????10117????????4????????3??????????x3+x2+1???11017???????3?????????4?????????x4+x3+x2+1????????111017??????????3??????????4??????????x4+x2+x+1?????????1011115??????????11?????????3??????????x4+x+

5、1??????????1001115??????????7?????????5??????????x8+x7+x6+x4+1??????????11101000131??????????26?????????3??????????x5+x2+1??????????10010131??????????21?????????5??????????x10+x9+x8+x6+x5+x3+1???1110110100163??????????57????????3??????????x6+x+1??????????10000116

6、3??????????51???????5??????????x12+x10+x5+x4+x2+1?????????10100001101011041??????1024??????????　???x16+x15+x2+1??????????11000000000000101圖9常用的生成多項式3、模2除（按位除）模2除做法與算術(shù)除法類似，但每一位除（減）的結(jié)果不影響其它位，即不向上一位借位。所以實際上就是異或。然后再移位做下一位的模2減。步驟如下：a、用除數(shù)對被除數(shù)最高幾位做模2減，沒有借位。b、除數(shù)右移一位，若余數(shù)最

7、高位為1，商為1，并對余數(shù)做模2減。若余數(shù)最高位為0，商為0，除數(shù)繼續(xù)右移一位。c、一直做到余數(shù)的位數(shù)小于除數(shù)時，該余數(shù)就是最終余數(shù)?！纠?111000除以1101：1011———商————1111000-----被除數(shù)1101————除數(shù)————10001101————10101101————111————余數(shù)4、CRC碼的生成步驟（1）將x的最高冪次為R的生成多項式G(x)轉(zhuǎn)換成對應(yīng)的R+1位二進(jìn)制數(shù)。（2）將信息碼左移R位得到多項式f(x)*XR。（3）用生成多項式（二進(jìn)制數(shù)）對f(x)*XR做模2除，得到余數(shù)（

8、即校驗碼）。（4）將余數(shù)多項式加到f(x)*XR中，得到完整的CRC碼?！纠考僭O(shè)使用的生成多項式是G(x)=x3+x+1。4位的原始報文為1010，求編碼后的報文。解：（1）將生成多項式G(x)=x3+x+1轉(zhuǎn)換成對應(yīng)的二進(jìn)制除數(shù)1011。（2）此題生成多項式有4位（R+1），要把原始報文F(x)左移3（R）位變成