[年最新整理]循環(huán)冗余校驗(yàn)碼(CRC)的基本原理(精品文檔)

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)*X R ），這樣 f(x) 的右邊就會(huì)空出R 位，這就是校驗(yàn)碼的位置。通過(guò)f(x)*XR 除以生成多項(xiàng)式G(x) 得到的余數(shù)

2、就是校驗(yàn)碼。幾個(gè)基本概念1、多項(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。可以看出： x 的最高冪次為 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)=X 4+X 3+X+1 ，可轉(zhuǎn)換為二進(jìn)制數(shù)碼11011 。而發(fā)送信息位1111 ，可轉(zhuǎn)換為數(shù)據(jù)多項(xiàng)式為f(x)=X 3+X 2+X+1 。2、生成多項(xiàng)式是接受方和發(fā)送方的一個(gè)約定，也就是一個(gè)二進(jìn)制數(shù)，在整個(gè)傳輸過(guò)程中，這個(gè)數(shù)始終保持不變。在發(fā)送方 ,利用生成多項(xiàng)式對(duì)信息

3、多項(xiàng)式做模 2 除生成校驗(yàn)碼。在接受方利用生成多項(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 所示：NK碼距 dG(x) 多項(xiàng)式G(x)743x3+x+11011743x3 +x2+11101734x4 +x3+x2+111101734x4+x2 +x+1101

4、1115113x4+x+1100111575x8+x 7+x 6+x4 +111101000131263x5 +x2+110010131215x10 +x9 +x8+x 6+x 5+x3 +163573x6+x+1100001163515x12 +x10 +x 5+x4 +x2 +110411024x16 +x15 +x 2+1圖 9 常用的生成多項(xiàng)式3、模 2 除（按位除）模 2 除做法與算術(shù)除法類似，但每一位除（減）的結(jié)果不影響其它位，即不向上一位借位。所以實(shí)際上就是異或。然后再移位做下一位的模 2 減。步驟如下：a、用除數(shù)對(duì)被除數(shù)最高幾位做模2 減，沒有借位。b、除數(shù)右移一位，若余數(shù)最高

5、位為1，商為 1，并對(duì)余數(shù)做模2 減。若余數(shù)最高位為0，商為 0，除數(shù)繼續(xù)右移一位。c、一直做到余數(shù)的位數(shù)小于除數(shù)時(shí)，該余數(shù)就是最終余數(shù)?！纠?1111000 除以 1101 ：1011 商1111000- 被除數(shù)1101除數(shù)1000110110101101111 余數(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)*X R 。（3）用生成多項(xiàng)式（二進(jìn)制數(shù)）對(duì)f(x)*X R 做模 2 除，得到余數(shù)（即校驗(yàn)碼）。（4）將余數(shù)多項(xiàng)式加到f(x)*X R 中，得到完整的CRC 碼?！纠考?/p>

6、設(shè)使用的生成多項(xiàng)式是G(x)=x 3 +x+1 。4 位的原始報(bào)文為 1010 ，求編碼后的報(bào)文。解：（1）將生成多項(xiàng)式G(x)=x 3 +x+1 轉(zhuǎn)換成對(duì)應(yīng)的二進(jìn)制除數(shù)1011 。（2）此題生成多項(xiàng)式有4 位（ R+1 ），要把原始報(bào)文F(x) 左移3（R）位變成 1010000（3）用生成多項(xiàng)式對(duì)應(yīng)的二進(jìn)制數(shù)對(duì)左移4 位后的原始報(bào)文進(jìn)行模 2除：1001- 商-10100001011- 除數(shù)-10001011-11- 余數(shù)（校驗(yàn)位）（4）編碼后的報(bào)文（ CRC 碼）：1010000+ 11-1010011CRC 碼為 1010011 （和糾錯(cuò)）。在接收端收到了 CRC 碼后用生成多項(xiàng)式為

7、G(x) 去做模 2 除，若得到余數(shù)為 0，則碼字無(wú)誤。若得到余數(shù)不為 0，則接收的數(shù)據(jù)有錯(cuò)。5、通信與網(wǎng)絡(luò)中常用的CRC在數(shù)據(jù)通信與網(wǎng)絡(luò)中，通常k 相當(dāng)大，由一千甚至數(shù)千數(shù)據(jù)位構(gòu)成一幀，而后采用CRC 碼產(chǎn)生 r 位的校驗(yàn)位。它只能檢測(cè)出錯(cuò)誤，而不能糾正錯(cuò)誤。一般取r=16 ，標(biāo)準(zhǔn)的 16 位生成多項(xiàng)式有CRC-16 x16 +x 15 +x 2+1 和 CRC-CCITT x16 +x 15 +x2+1。【例 1】某循環(huán)冗余碼（ CRC ）的生成多項(xiàng)式G(x) x3+x 2+1，用此生成多項(xiàng)式產(chǎn)生的冗余位，加在信息位后形成CRC碼。若發(fā)送信息位 1111 和 1100 則它的 CRC 碼分

8、別為 A和 B。由于某種原因，使接收端收到了按某種規(guī)律可判斷為出錯(cuò)的CRC碼，例如碼字 C、 D、和 E。（ 1998年試題 11）供選擇的答案A：1111100111110111111101111111B：1100100110010111001101100111CE：00000000001100001011100110101000110100111110100011011000解：A：G(x) 1101 ，f(x)1111 ，f(x)*x 3 G(x) 11110001101 1011 余 111得到的 CRC 碼為 1111111B：G(x) 1101 ，f(x)1100 ，f(x)*x

9、3 G(x) 11000001101 1001 余 101得到的 CRC 碼為 1100101CE：分別用 G(x) 1101 對(duì)作模 2 除: 0000000 1101 余 000 1111101 1101 余 001 00101111101 余 000 00110101101余 000 1000110 1101 余 000 1001111 1101 余 100 10100011101 余 000 10110001101余 100所以 C、 D和 E的答案是、【例 2】計(jì)算機(jī)中常用的一種檢錯(cuò)碼是CRC ，即_A_碼。在進(jìn)行編碼過(guò)程中要使用_B_運(yùn)算。假設(shè)使用的生成多項(xiàng)式是G(X)=X4+X 3+X+1 ，原始報(bào)文為 ，則編碼后的報(bào)文為_C_ 。CRC 碼 _D_ 的說(shuō)法是正確的。供選擇的答案：A： 水平垂直奇偶校驗(yàn) 循環(huán)求和 循環(huán)冗余正比率B： 模 2 除法定點(diǎn)二進(jìn)制除法二十進(jìn)制除法循環(huán)移位法C： D： 可糾正一位差錯(cuò)可檢測(cè)所有偶數(shù)位錯(cuò) 可檢測(cè)所有小于校驗(yàn)位長(zhǎng)度的突發(fā)錯(cuò) 可檢測(cè)所有