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

　　一、CRC簡(jiǎn)介

　　循環(huán)冗余校驗(yàn)（Cyclic Redundancy Check， CRC）是一種根據(jù)網(wǎng)絡(luò)數(shù)據(jù)包或電腦文件等數(shù)據(jù)產(chǎn)生簡(jiǎn)短固定位數(shù)校驗(yàn)碼的一種散列函數(shù)，主要用來(lái)檢測(cè)或校驗(yàn)數(shù)據(jù)傳輸或者保存后可能出現(xiàn)的錯(cuò)誤。它是利用除法及余數(shù)的原理來(lái)作錯(cuò)誤偵測(cè)的。

　　在數(shù)據(jù)傳輸過(guò)程中，無(wú)論傳輸系統(tǒng)的設(shè)計(jì)再怎么完美，差錯(cuò)總會(huì)存在，這種差錯(cuò)可能會(huì)導(dǎo)致在鏈路上傳輸?shù)囊粋€(gè)或者多個(gè)幀被破壞（出現(xiàn)比特差錯(cuò)，0變?yōu)?，或者1變?yōu)?），從而接受方接收到錯(cuò)誤的數(shù)據(jù)。為盡量提高接受方收到數(shù)據(jù)的正確率，在接收方接收數(shù)據(jù)之前需要對(duì)數(shù)據(jù)進(jìn)行差錯(cuò)檢測(cè)，當(dāng)且僅當(dāng)檢測(cè)的結(jié)果為正確時(shí)接收方才真正收下數(shù)據(jù)。檢測(cè)的方式有多種，常見(jiàn)的有奇偶校驗(yàn)、因特網(wǎng)校驗(yàn)和循環(huán)冗余校驗(yàn)等。

　　二、CRC硬件計(jì)算過(guò)程

　　1．設(shè)置CRC寄存器，并給其賦值FFFF（hex）。

　　2．將數(shù)據(jù)的第一個(gè)8-bit字符與16位CRC寄存器的低8位進(jìn)行異或，并把結(jié)果存入CRC寄存器。

　　3．CRC寄存器向右移一位，MSB補(bǔ)零，移出并檢查L(zhǎng)SB。

　　4．如果LSB為0，重復(fù)第三步；若LSB為1，CRC寄存器與多項(xiàng)式碼相異或。

　　注意：該步檢查L(zhǎng)SB應(yīng)該是右移前的LSB，即第3步前的LSB。

　　5．重復(fù)第3與第4步直到8次移位全部完成。此時(shí)一個(gè)8-bit數(shù)據(jù)處理完畢。

　　6．重復(fù)第2至第5步直到所有數(shù)據(jù)全部處理完成。7．最終CRC寄存器的內(nèi)容即為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)碼。

　　原理思維導(dǎo)圖總結(jié)：

　　四、通信與網(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+x15+x2+1 和 CRC-CCITT＝x16+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ò)以及99．997%的突發(fā)長(zhǎng)度為17的突發(fā)錯(cuò)和99．998%的突發(fā)長(zhǎng)度大于17的突發(fā)錯(cuò)。所以CRC碼的檢錯(cuò)能力還是很強(qiáng)的。這里，突發(fā)錯(cuò)誤是指幾乎是連續(xù)發(fā)生的一串錯(cuò)，突發(fā)長(zhǎng)度就是指從出錯(cuò)的第一位到出錯(cuò)的最后一位的長(zhǎng)度（但是，中間并不一定每一位都錯(cuò)）。

　　【例1】某循環(huán)冗余碼（CRC）的生成多項(xiàng)式 G（x）＝x3+x2+1，用此生成多項(xiàng)式產(chǎn)生的冗余位，加在信息位后形成 CRC 碼。若發(fā)送信息位 1111 和 1100 則它的 CRC 碼分別為＿A＿和＿B＿。由于某種原因，使接收端收到了按某種規(guī)律可判斷為出錯(cuò)的 CRC 碼，例如碼字＿C＿、＿D＿、和＿E＿。（1998年試題11）

　　供選擇的答案：

　　A：① lllll00 ② 1111101 ③ 1111110 ④ 1111111

　　B：① 1100100 ② 1100101 ③ 1100110 ④ 1100111

　　C～E：① 0000000 ② 0001100 ③ 0010111 ⑤ 1000110 ⑥ 1001111 ⑦ 1010001 ⑧ 1011000

　　解：

　　A：G（x）＝1101，C（x）＝1111 C（x）*23÷G（x）＝1111000÷1101＝1011余111

　　得到的CRC碼為1111111

　　B：G（x）＝1101，C（x）＝1100 C（x）*23÷G（x）＝1100000÷1101＝1001余101

　　得到的CRC碼為1100101

　　C～E：

　　分別用G（x）＝1101對(duì)①～⑧ 作模2除： ① 0000000÷1101 余000 ② 1111101÷1101 余001

　?、?0010111÷1101 余000 ④ 0011010÷1101 余000 ⑤ 1000110÷1101 余000

　　⑥ 1001111÷1101 余100 ⑦ 1010001÷1101 余000 ⑧ 1011000÷1101 余100

　　所以＿C＿、＿D＿和＿E＿的答案是②、⑥、⑧

　　【例2】計(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ō)法是正確的。

　　在無(wú)線電通信中常采用它規(guī)定碼字長(zhǎng)為7位．并且其中總有且僅有3個(gè)“1”。這種碼的編碼效率為_(kāi)E_。

　　供選擇的答案：

　　A：① 水平垂直奇偶校驗(yàn) ② 循環(huán)求和 ③ 循環(huán)冗余 ④正比率

　　B：① 模2除法 ②定點(diǎn)二進(jìn)制除法 ③二－十進(jìn)制除法 ④循環(huán)移位法

　　C：① 1100101010111 ② 110010101010011 ③ 110010101011100 ④ 110010101010101

　　D：① 可糾正一位差錯(cuò) ②可檢測(cè)所有偶數(shù)位錯(cuò)

　　③ 可檢測(cè)所有小于校驗(yàn)位長(zhǎng)度的突發(fā)錯(cuò) ④可檢測(cè)所有小于、等于校驗(yàn)位長(zhǎng)度的突發(fā)錯(cuò)

　　E：① 3/7 ② 4/7 ③ log23/log27 ④ （log235）/7

　　解：從前面有關(guān)CRC的論述中可得出： A：③ 循環(huán)冗余 B：① 模2除法

　　C：G（x）＝11011，C（x）＝11001010101，C（x）*24÷G（x）＝110010101010000÷11011 余0011

　　得到的CRC碼為② 110010101010011

　　D：從前面有關(guān)通信與網(wǎng)絡(luò)中常用的CRC的論述中可得出：④ 可檢測(cè)所有小于、等于校驗(yàn)位長(zhǎng)度的突發(fā)錯(cuò)

　　E：定比碼又叫定重碼，是奇偶校驗(yàn)的推廣。在定比碼中，奇數(shù)或偶數(shù)的性質(zhì)保持不變，然而附加一種限制，每個(gè)字中1的總數(shù)是固定的。隨用途之不同，定比碼要求的附加校驗(yàn)位可能多于一個(gè)，但較之單一的奇偶校驗(yàn)將增加更多的檢錯(cuò)能力。

　　所謂7中取3定比碼，就是整個(gè)碼字長(zhǎng)度為7位，其中1的位數(shù)固定為3。所有128個(gè)7位代碼（0000000～1111111）中只有1的位數(shù)固定為3的才是其合法碼字?？梢杂们蠼M合的公式求出其合法碼字?jǐn)?shù)為：C73＝7！/（3！*（7-3）?。?*6*5/（1*2*3）＝35

　　編碼效率＝合法碼字所需位數(shù)/碼字總位數(shù)＝（log235）/7

　　而對(duì)于CRC的實(shí)現(xiàn)有兩種方式，分別為多項(xiàng)式和查表法。