?

　　CRC即循環(huán)冗余校驗(yàn)碼(Cyclic Redundancy Check)：是數(shù)據(jù)通信領(lǐng)域中最常用的一種差錯(cuò)校驗(yàn)碼，其特征是信息字段和校驗(yàn)字段的長(zhǎng)度可以任意選定。

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

　　CRC幾個(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)式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ò)誤位置。

　　應(yīng)滿足以下條件：

　　a、生成多項(xiàng)式的最高位和最低位必須為1。

　　b、當(dāng)被傳送信息(CRC碼)任何一位發(fā)生錯(cuò)誤時(shí)，被生成多項(xiàng)式做除后應(yīng)該使余數(shù)不為0。

　　c、不同位發(fā)生錯(cuò)誤時(shí)，應(yīng)該使余數(shù)不同。

　　d、對(duì)余數(shù)繼續(xù)做除，應(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 x3+x+1

　　1011

　　7 4 3 x3+x2+1

　　1101

　　7 3 4 x4+x3+x2+1

　　11101

　　7 3 4 x4+x2+x+1

　　10111

　　15 11 3 x4+x+1

　　10011

　　15 7 5 x8+x7+x6+x4+1

　　111010001

　　31 26 3 x5+x2+1

　　100101

　　31 21 5 x10+x9+x8+x6+x5+x3+1

　　11101101001

　　63 57 3 x6+x+1

　　1000011

　　63 51 5 x12+x10+x5+x4+x2+1

　　1010000110101

　　1041 1024 x16+x15+x2+1

　　11000000000000101

　　3 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)*2的R次方

　　3、用生成多項(xiàng)式(二進(jìn)制數(shù))對(duì)信息碼做除，得到R位的余數(shù)。

　　4、將余數(shù)拼到信息碼左移后空出的位置，得到完整的CRC碼。