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

《循環(huán)冗余校驗(yàn)碼(crc)的基本原理》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

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

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

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

4、???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+1??????????1001115??????????7?????????5??????????x8+x7+x6+x4+1??????

5、????11101000131??????????26?????????3??????????x5+x2+1??????????10010131??????????21?????????5??????????x10+x9+x8+x6+x5+x3+1???1110110100163??????????57????????3??????????x6+x+1??????????100001163??????????51???????5??????????x12+x10+x5+x4+x2+1?????????10100001101011041??????1024

6、??????????　???x16+x15+x2+1??????????11000000000000101圖9常用的生成多項(xiàng)式3、模2除（按位除）模2除做法與算術(shù)除法類似，但每一位除（減）的結(jié)果不影響其它位，即不向上一位借位。所以實(shí)際上就是異或。然后再移位做下一位的模2減。步驟如下：a、用除數(shù)對(duì)被除數(shù)最高幾位做模2減，沒(méi)有借位。b、除數(shù)右移一位，若余數(shù)最高位為1，商為1，并對(duì)余數(shù)做模2減。若余數(shù)最高位為0，商為0，除數(shù)繼續(xù)右移一位。c、一直做到余數(shù)的位數(shù)小于除數(shù)時(shí)，該余數(shù)就是最終余數(shù)。【例】1111000除以1101：1011———商————111100

7、0-----被除數(shù)1101————除數(shù)————10001101————10101101————111————余數(shù)4、CRC碼的生成步驟（1）將x的最高冪次為R的生成多項(xiàng)式G(x)轉(zhuǎn)換成對(duì)應(yīng)的R+1位二進(jìn)制數(shù)。（2）將信息碼左移R位得到多項(xiàng)式f(x)*XR。（3）用生成多項(xiàng)式（二進(jìn)制數(shù)）對(duì)f(x)*XR做模2除，得到余數(shù)（即校驗(yàn)碼）。（4）將余數(shù)多項(xiàng)式加到f(x)*XR中，得到完整的CRC碼?！纠考僭O(shè)使用的生成多項(xiàng)式是G(x)=x3+x+1。4位的原始報(bào)文為1010，求編碼后的報(bào)文。解：（1）將生成多項(xiàng)式G(x)=x3+x+1轉(zhuǎn)換成對(duì)應(yīng)的二進(jìn)制除數(shù)101

8、1。（2）此題生成多項(xiàng)式有4位（R+1），要把原始報(bào)文F(x)左移3（R）位變成