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

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)式C(X)表示，將C(x)左移R位，則可表示成C(x)*2R，這樣C(x)的右邊就會(huì)空出R位，這就是校驗(yàn)碼的位置。通過(guò)C(x)*2R除以生成多項(xiàng)式G(x)得到的余數(shù)就是校驗(yàn)碼。 幾個(gè)基本概念 1、多項(xiàng)式與二進(jìn)制數(shù)碼 多項(xiàng)式和二進(jìn)制數(shù)有

2、直接對(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)式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ā)送方的一個(gè)約定，也就是一個(gè)二進(jìn)制數(shù)，在整個(gè)傳輸過(guò)程中，這個(gè)數(shù)始終保持不變。 在發(fā)送方,利用生成多項(xiàng)式對(duì)信息多項(xiàng)式做模2除生成校驗(yàn)碼。在接受方利用生成多項(xiàng)式對(duì)收到的編碼多項(xiàng)式做模2除檢測(cè)和確定錯(cuò)

3、誤位置。 應(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&

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ù)除法類(lèi)似，但每一位除（減）的結(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ù)。 【例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)換成對(duì)應(yīng)的R+1位二進(jìn)制數(shù)。 2、將信息碼左移R位，相當(dāng)與對(duì)應(yīng)的信息多項(xiàng)式C(x)*2R 3、用生成多項(xiàng)式（二進(jìn)制數(shù)）對(duì)信息碼做模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)換成對(duì)應(yīng)的二進(jìn)制除數(shù)1011。 2、此題生成多項(xiàng)式有4位（R+1），要把原始報(bào)文C(x)左移3（R）位變成1010000 3、用生成多項(xiàng)式對(duì)應(yīng)的二進(jìn)制數(shù)對(duì)左

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的和糾錯(cuò) 在接收端收到了CRC碼后用生成多項(xiàng)式為G(x)去做模2除，若得到余數(shù)為0,則碼字無(wú)誤。若如果有一位出錯(cuò)，則余數(shù)不為0，而且不同位出錯(cuò)，其余數(shù)也不同?？梢宰C明，余數(shù)與出錯(cuò)位的對(duì)應(yīng)關(guān)系只與碼制及生成多項(xiàng)式有關(guān)，而與待測(cè)碼字（信息位）無(wú)關(guān)。圖10給出了G(x)1011

9、，C(x)1010的出錯(cuò)模式，改變C(x)（碼字），只會(huì)改變表中碼字內(nèi)容，不改變余數(shù)與出錯(cuò)位的對(duì)應(yīng)關(guān)系。 如果循環(huán)碼有一位出錯(cuò)，用G(x)作模2除將得到一個(gè)不為0的余數(shù)。如果對(duì)余數(shù)補(bǔ)0繼續(xù)除下去，我們將發(fā)現(xiàn)一個(gè)有趣的結(jié)果；各次余數(shù)將按圖10順序循環(huán)。例如第一位出錯(cuò)，余數(shù)將為001，補(bǔ)0后再除，第二次余數(shù)為010，以后依次為100，0ll，反復(fù)循環(huán)，這就是“循環(huán)碼”名稱的由來(lái)。這是一個(gè)有價(jià)值的特點(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)位。它只能檢測(cè)出錯(cuò)誤，而不能糾正錯(cuò)誤。一般取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碼可檢測(cè)出所有的雙錯(cuò)、奇數(shù)位錯(cuò)和突發(fā)長(zhǎng)度小于等于r的突發(fā)錯(cuò)以及（1-2-(r-1)）的突發(fā)長(zhǎng)度為r+1的突發(fā)錯(cuò)和（1-2-r）的突發(fā)長(zhǎng)度大于r+1的突發(fā)錯(cuò)。例如，對(duì)上述r=16的情況，就能檢測(cè)出所有突發(fā)長(zhǎng)度小于等于16的突發(fā)錯(cuò)以及99997%的突發(fā)長(zhǎng)度為17的突發(fā)錯(cuò)和99998%的突發(fā)長(zhǎng)度大于17的突發(fā)錯(cuò)。所以CRC碼的檢錯(cuò)能力還是很強(qiáng)的。這里，突發(fā)錯(cuò)誤是指幾乎是連續(xù)發(fā)生的一串錯(cuò)，突發(fā)長(zhǎng)度就是指從出錯(cuò)的第一位到出錯(cuò)的最后一位的長(zhǎng)度(但是，中間并不一定每一位都錯(cuò))。 【例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】計(jì)算機(jī)中常用的一種檢錯(cuò)碼是CRC，即 _A_ 碼。在進(jìn)行編碼過(guò)程中要使用 _B_ 運(yùn)算。假設(shè)使用的生成多項(xiàng)式是 G(X)=X4+X3+X+1， 原始報(bào)文為11001010101，則編碼后的報(bào)文為 _C_ 。CRC碼 _D_ 的說(shuō)法是正確的。 供選擇的答案： A： 水平垂直奇偶校驗(yàn)            

14、0;           循環(huán)求和                           循環(huán)冗余            

15、               正比率 B： 模2除法                        定點(diǎn)二進(jìn)制除法         

16、0;            二十進(jìn)制除法                    循環(huán)移位法 C： 1100101010111              110010101

17、010011         110010101011100         110010101010101 D： 可糾正一位差錯(cuò)                          

18、;                         可檢測(cè)所有偶數(shù)位錯(cuò) 可檢測(cè)所有小于校驗(yàn)位長(zhǎng)度的突發(fā)錯(cuò)                     可檢測(cè)所有小于、等于校驗(yàn)位長(zhǎng)度的突發(fā)錯(cuò) E： 3/7          4/7          log23