循環(huán)冗余校驗(yàn)碼

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

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

3、誤位置。 應(yīng)滿足以下條件： a、生成多項(xiàng)式的最高位和最低位必須為1。 b、當(dāng)被傳送信息（CRC碼）任何一位發(fā)生錯誤時，被生成多項(xiàng)式做模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)于不同碼制的生成多項(xiàng)式如圖9所示： N           K           碼距d&

4、#160;          G(x)多項(xiàng)式           G(x)7           4            3       

5、    x3+x+1            10117           3            4            x4+x3+x2+1  

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

7、1101 111余數(shù) CRC碼的生成步驟 1、將x的最高冪次為R的生成多項(xiàng)式G(x)轉(zhuǎn)換成對應(yīng)的R+1位二進(jìn)制數(shù)。 2、將信息碼左移R位，相當(dāng)與對應(yīng)的信息多項(xiàng)式C(x)*2R 3、用生成多項(xiàng)式（二進(jìn)制數(shù)）對信息碼做模2除，得到R位的余數(shù)。 4、將余數(shù)拼到信息碼左移后空出的位置，得到完整的CRC碼。 【例2】假設(shè)使用的生成多項(xiàng)式是G(x)=x3+x+1。4位的原始報(bào)文為1010，求編碼后的報(bào)文。 解： 1、將生成多項(xiàng)式G(x)=x3+x+1轉(zhuǎn)換成對應(yīng)的二進(jìn)制除數(shù)1011。 2、此題生成多項(xiàng)式有4位（R+1），要把原始報(bào)文C(x)左移3（R）位變成1010000 3、用生成多項(xiàng)式對應(yīng)的二進(jìn)制數(shù)對左

8、移4位后的原始報(bào)文進(jìn)行模2除： 1001-商 - 1010000 1011-除數(shù) - 1000 1011 - 011-余數(shù)（校驗(yàn)位） 5、編碼后的報(bào)文（CRC碼）： 1010000 +          011 - 1010011 CRC的和糾錯 在接收端收到了CRC碼后用生成多項(xiàng)式為G(x)去做模2除，若得到余數(shù)為0,則碼字無誤。若如果有一位出錯，則余數(shù)不為0，而且不同位出錯，其余數(shù)也不同?？梢宰C明，余數(shù)與出錯位的對應(yīng)關(guān)系只與碼制及生成多項(xiàng)式有關(guān)，而與待測碼字（信息位）無關(guān)。圖10給出了G(x)1011

9、，C(x)1010的出錯模式，改變C(x)（碼字），只會改變表中碼字內(nèi)容，不改變余數(shù)與出錯位的對應(yīng)關(guān)系。 如果循環(huán)碼有一位出錯，用G(x)作模2除將得到一個不為0的余數(shù)。如果對余數(shù)補(bǔ)0繼續(xù)除下去，我們將發(fā)現(xiàn)一個有趣的結(jié)果；各次余數(shù)將按圖10順序循環(huán)。例如第一位出錯，余數(shù)將為001，補(bǔ)0后再除，第二次余數(shù)為010，以后依次為100，0ll，反復(fù)循環(huán)，這就是“循環(huán)碼”名稱的由來。這是一個有價值的特點(diǎn)。通信與網(wǎng)絡(luò)中常用的CRC 在數(shù)據(jù)通信與網(wǎng)絡(luò)中，通常k相當(dāng)大，由一千甚至數(shù)千數(shù)據(jù)位構(gòu)成一幀，而后采用CRC碼產(chǎn)生r位的校驗(yàn)位。它只能檢測出錯誤，而不能糾正錯誤。一般取r=16，標(biāo)準(zhǔn)的16位生成多項(xiàng)式有C

10、RC-16x16+x15+x2+1 和 CRC-CCITTx16+x15+x2+1。 一般情況下，r位生成多項(xiàng)式產(chǎn)生的CRC碼可檢測出所有的雙錯、奇數(shù)位錯和突發(fā)長度小于等于r的突發(fā)錯以及（1-2-(r-1)）的突發(fā)長度為r+1的突發(fā)錯和（1-2-r）的突發(fā)長度大于r+1的突發(fā)錯。例如，對上述r=16的情況，就能檢測出所有突發(fā)長度小于等于16的突發(fā)錯以及99997%的突發(fā)長度為17的突發(fā)錯和99998%的突發(fā)長度大于17的突發(fā)錯。所以CRC碼的檢錯能力還是很強(qiáng)的。這里，突發(fā)錯誤是指幾乎是連續(xù)發(fā)生的一串錯，突發(fā)長度就是指從出錯的第一位到出錯的最后一位的長度(但是，中間并不一定每一位都錯)。 【例3

11、】某循環(huán)冗余碼（CRC）的生成多項(xiàng)式 G(x)x3+x2+1，用此生成多項(xiàng)式產(chǎn)生的冗余位，加在信息位后形成 CRC 碼。若發(fā)送信息位 1111 和 1100 則它的 CRC 碼分別為A和B。供選擇的答案 A： lllll00           1111101           1111110        

12、0;  1111111B： 1100100          1100101           1100110           1100111解：A：G(x)1101，C(x)1111 C(x)*23÷G(x)1111000÷11011011余111得到的CRC碼為1111

13、111B：G(x)1101，C(x)1100 C(x)*23÷G(x)1100000÷11011001余101得到的CRC碼為1100101【例4供選擇的答案： A： 水平垂直奇偶校驗(yàn)                        循環(huán)求和         &

14、#160;                 循環(huán)冗余                           正比率 B： 模2除法    &#

15、160;                   定點(diǎn)二進(jìn)制除法                      二十進(jìn)制除法        

16、;            循環(huán)移位法 C： 可糾正一位差錯                                                   可檢測所有偶數(shù)位錯 可檢測所有小于校驗(yàn)位長度的突發(fā)錯                     可檢測所有小于、等于校驗(yàn)位長度的突發(fā)錯 E： 3/7