2018年最新整理循環(huán)冗余校驗碼CRC的基本原理

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碼的生成多項式。校驗碼的具體生成過程為：假設發(fā)送信息用信息多項式f(X)表示，將f(x)左移R位(則可表示成f(x)*XR),這樣f(x)的右邊就會空出R位，這就是校驗碼的位置。通過f(x)*XR除以生成多項式G(x)得到的余數(shù)就是校驗碼。幾個基本概念1、多項式與二進制數(shù)碼多項式和二進制數(shù)有直接對

2、應關系：x的最高哥次對應二進制數(shù)的最高位，以下各位對應多項式的各屆次，有此屆次項對應1,無此屆次項對應0?？梢钥闯觯簒的最高哥次為R,轉換成對應的二進制數(shù)有R+1位。多項式包括生成多項式G(x)和信息多項式f(x)。如生成多項式為G(x)=X4+X3+X+1,可轉換為二進制數(shù)碼11011。而發(fā)送信息位1111,可轉換為數(shù)據(jù)多項式為f(x)=X3+X2+X+1是接受方和發(fā)送方的一個約定，也就是一個二進制數(shù)，在整個傳輸過程中，這個數(shù)始終保持不變。在發(fā)送方，利用生成多項式對信息多項式做模2除生成校驗碼。在接受方利用生成多項式對收到的編碼多項式做模2除檢測和確定錯誤位置。應滿足以下條件：a、生成多項式

3、的最高位和最低位必須為1。b、當被傳送信息(CRC碼)任何一位發(fā)生錯誤時，被生成多項式做模2除后應該使余數(shù)不為0。c、不同位發(fā)生錯誤時，應該使余數(shù)不同。d、對余數(shù)繼續(xù)做模2除，應使余數(shù)循環(huán)。將這些要求反映為數(shù)學關系是比較復雜的。但可以從有關資料查到常用的對應于不同碼制的生成多項式如圖9所示：NK碼距dG(x)多項式G(x)743x3+x+11011743x3+x2+11101734x4+x3+x2+111101734x4+x2+x+11011115113x4+x+1100111575x8+x7+x6+x4+111101000131263x5+x2+110010131215x10+x9+x8+x

4、6+x5+x3+11110110100163573x6+x+1100001163515x12+x10+x5+x4+x2+1101000011010110411024x16+x15+x2+111000000000000101圖9常用的生成多項式3、模2除（按位除）模2除做法與算術除法類似,但每一位除（減）的結果不影響其它位，即不向上一位借位。所以實際上就是異或。然后再移位做下一位的模2減。步驟如下:a、用除數(shù)對被除數(shù)最高幾位做模2減，沒有借位。b、除數(shù)右移一位，若余數(shù)最高位為1,商為1,并對余數(shù)做模2減。若余數(shù)最高位為0,商為0,除數(shù)繼續(xù)右移一位。c、一直做到余數(shù)的位數(shù)小于除數(shù)時，該余數(shù)就是最終

5、余數(shù)?！纠?111000除以1101:1011商1111000-被除數(shù)1101除數(shù)1000110110101101111余數(shù)4、CRC碼的生成步驟(1)將x的最高哥次為R的生成多項式G(x)轉換成對應的R+1位二進制數(shù)。(2)將信息碼左移R位得到多項式f(x)*XR。(3)用生成多項式(二進制數(shù))對f(x)*XR做模2除，得到余數(shù)(即校驗碼)。(4)將余數(shù)多項式加到f(x)*XR中，得到完整的CRC碼?！纠考僭O使用的生成多項式是G(x)=x3+x+1。4位的原始報文為1010,求編碼后的報文。解：(1)將生成多項式G(x)=x3+x+1轉換成對應的二進制除數(shù)1011。(2)此題生成多項式有

6、4位(R+1),要把原始報文F(x)左移3(R)位變成1010000(3)用生成多項式對應的二進制數(shù)對左移4位后的原始報文進行模2除：1001商10100001011除數(shù)1000101111余數(shù)（校驗位）（4）編碼后的報文（CRC碼）：1010000+111010011CRC碼為1010011（和糾錯）。在接收端收到了CRC碼后用生成多項式為G（x）去做模2除，若得到余數(shù)為0,則碼字無誤。若得到余數(shù)不為0,則接收的數(shù)據(jù)有錯。5、通信與網(wǎng)絡中常用的CRC在數(shù)據(jù)通信與網(wǎng)絡中，通常k相當大，由一千甚至數(shù)千數(shù)據(jù)位構成一幀，而后采用CRC碼產生r位的校驗位。它只能檢測出錯誤，而不能糾正錯誤。一般取r=1

7、6,標準的16位生成多項式有CRC-16=x16+x15+x2+1和CRC-CCITT=x16+x15+x2+1?！纠?1某循環(huán)冗余碼（CRC）的生成多項式G（x）=x3+x2+1,用此生成多項式產生的冗余位，加在信息位后形成CRC碼。若發(fā)送信息位1111和1100則它的CRC碼分別為_A_和_Bo由于某種原因，使接收端收到了按某種規(guī)律可判斷為出錯的CRC碼，例如碼字_C_、D、和_E。11998年試題11）供選擇的答案A:1111100111110111111101111111B:1100100110010111001101100111CE:0000000000110000101110011

8、0101000110100111110100011011000解：A: G(x)=1101,f(x)=1111,f(x)*x32(x)=1111000+1101=1011余111得到的CRC碼為1111111B: G(x)=1101,f(x)=1100,f(x)*x32(x)=1100000+1101=1001余101得到的CRC碼為1100101CE:分別用G(x)=1101對作模2除：0010111+1101余0000011010+1101余0001000110+1101余0001001111+1101余1001010001+1101余0001011000+1101余100所以C、D和E的

9、答案是、【例2】計算機中常用的一種檢錯碼是CRC,即_A_碼。在進行編碼過程中要使用_B_運算。假設使用的生成多項式是G(X)=X4+X3+X+1,原始報文為11001010101,則編碼后的報文為_C_。CRC碼_D_的說法是正確的。供選擇的答案：A:水平垂直奇偶校驗循環(huán)求和循環(huán)冗余正比率B:模2除法定點二進制除法二十進制除法C:1100101010111110010101011100循環(huán)移位法110010101010011110010101010101D:可糾正一位差錯可檢測所有偶數(shù)位錯可檢測所有小于校驗位長度的突發(fā)錯可檢測所有小于、等于校驗位長度的突發(fā)錯解：從前面有關CRC的論述中可得出:A:循環(huán)冗余B