CRC校驗(yàn)原理-包括C++源碼

《CRC校驗(yàn)原理-包括C++源碼》由會(huì)員分享，可在線閱讀，更多相關(guān)《CRC校驗(yàn)原理-包括C++源碼（10頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 CRC校驗(yàn)原理 包括（C++源碼) 現(xiàn)在此說明下什么是CRC：循環(huán)冗余碼校驗(yàn)?英文名稱為Cyclical Redundancy Check，簡(jiǎn)稱CRC，它是利用除法及余數(shù)的原理來作錯(cuò)誤偵測(cè)（Error Detecting）的。實(shí)際應(yīng)用時(shí)，發(fā)送裝置計(jì)算出CRC值并隨數(shù)據(jù)一同發(fā)送給接收裝置，接收裝置對(duì)收到的數(shù)據(jù)重新計(jì)算CRC并與收到的CRC相比較，若兩個(gè)CRC值不同，則說明數(shù)據(jù)通訊出現(xiàn)錯(cuò)誤 那么其實(shí)CRC有比較多種，比如CRC16、CRC32 ，為什么叫16、32呢。在這里并非與位有和關(guān)系。而是由所確定的多項(xiàng)式最高次冪確定的。如下所示。理論上講冪次越高校驗(yàn)效果越好。 ??CRC(12

2、位) =X12+X11+X3+X2+X+1 　　CRC(16位) = X16+X15+X2+1 　　CRC(CCITT) = X16+X12 +X5+1 　　CRC(32位) = X32+X26+X23+X16+X12+X11+X10+ X8+X7+X5+X4+X2+X+1 循環(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)碼的具體生成過程為：假設(shè)

3、發(fā)送信息用信息多項(xiàng)式C(X)表示，將C(x)左移R位，則可表示成C(x)*2R，這樣C(x)的右邊就會(huì)空出R位，這就是校驗(yàn)碼的位置。通過C(x)*2R除以生成多項(xiàng)式G(x)得到的余數(shù)就是校驗(yàn)碼。 幾個(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，無此冪次項(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)換為

4、數(shù)據(jù)多項(xiàng)式為C(x)=x3+x2+x+1。 2、生成多項(xiàng)式 是接受方和發(fā)送方的一個(gè)約定，也就是一個(gè)二進(jìn)制數(shù)，在整個(gè)傳輸過程中，這個(gè)數(shù)始終保持不變。 授課：XXX 在發(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)式做模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)資料查到

5、常用的對(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??????

6、???? 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?????????? 1

7、1101101001 63?????????? 57?????????? 3?????????? x6+x+1?????????? 1000011 63?????????? 51?????????? 5?????????? x12+x10+x5+x4+x2+1?????????? 1010000110101 1041?????????? 1024?????????? 　?????????? x16+x15+x2+1?????????? 11000000000000101 圖9 常用的生成多項(xiàng)式 3、模2除（按位除） 模2除做法與算術(shù)除法類似，但每一位除（減）的結(jié)果不影響其它位，即不

8、向上一位借位。所以實(shí)際上就是異或。然后再移位移位做下一位的模2減。步驟如下： a、用除數(shù)對(duì)被除數(shù)最高幾位做模2減，沒有借位。 b、除數(shù)右移一位，若余數(shù)最高位為1，商為1，并對(duì)余數(shù)做模2減。若余數(shù)最高位為0，商為0，除數(shù)繼續(xù)右移一位。 c、一直做到余數(shù)的位數(shù)小于除數(shù)時(shí)，該余數(shù)就是最終余數(shù)。 【例】1111000除以1101： 1011———商 ———— 授課：XXX 1111000-----被除數(shù) 1101———— 除數(shù) ———— 010000 1101 ———— 01010 1101 ———— 111————余數(shù) CRC碼的生成步驟 1、將x的最高冪次

9、為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碼。 【例】假設(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ì)左移4位后的原始報(bào)文進(jìn)行模2除： 1001--

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

11、只與碼制及生成多項(xiàng)式有關(guān)，而與待測(cè)碼字（信息位）無關(guān)。圖10給出了G(x)＝1011，C(x)＝1010的出錯(cuò)模式，改變C(x)（碼字），只會(huì)改變表中碼字內(nèi)容，不改變余數(shù)與出錯(cuò)位的對(duì)應(yīng)關(guān)系。 　?????????? 收到的CRC碼字?????????? 余數(shù)?????????? 出錯(cuò)位 碼位?????????? A7?????????? A6?????????? A5?????????? A4?????????? A3?????????? A2?????????? A1 ???????????????? 正確?????????? 1?????????? 0?????????? 1???

12、??????? 0?????????? 0?????????? 1?????????? 1 ?????????? 000?????????? 無 錯(cuò) 誤?????????? 1?????????? 0?????????? 1?????????? 0?????????? 0?????????? 1?????????? 0 1?????????? 0?????????? 1?????????? 0?????????? 0?????????? 0?????????? 1 1?????????? 0?????????? 1?????????? 0?????????? 1?????????? 1

13、?????????? 1 1?????????? 0?????????? 1?????????? 1?????????? 0?????????? 1?????????? 1 1?????????? 0?????????? 0?????????? 0?????????? 0?????????? 1?????????? 1 1?????????? 1?????????? 1?????????? 0?????????? 0?????????? 1?????????? 1 0?????????? 0?????????? 1?????????? 0?????????? 0?????????? 1

14、?????????? 1 ?????????? 001010100011110111101?????????? 1234567 圖10 （7，4）CRC碼的出錯(cuò)模式（G(x)＝1011） 如果循環(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)碼”名稱的由來。這是一個(gè)有價(jià)值的特點(diǎn)。如果我們?cè)谇蟪鲇鄶?shù)不為0后，一邊對(duì)余數(shù)補(bǔ)0繼續(xù)做模2除，同時(shí)讓被檢測(cè)的校驗(yàn)碼字循環(huán)左移。圖10說明，當(dāng)出現(xiàn)余數(shù)

15、(101)時(shí)，出錯(cuò)位也移到A7位置?？赏ㄟ^異或門將它糾正后在下一次移位時(shí)送回A1。這樣我們就不必像海明校驗(yàn)?zāi)菢佑米g碼電路對(duì)每一位提供糾正條件。當(dāng)位數(shù)增多時(shí)，循環(huán)碼校驗(yàn)?zāi)苡行У亟档陀布鷥r(jià)，這是它得以廣泛應(yīng)用的主要原因。 通信與網(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ò)誤。一般取 授課：XXX 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ò)、

16、奇數(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ā)送信息位 11

17、11 和 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

18、???????? ???????? ⑤ 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???? ② 1

19、111101÷1101 余001 ③ 0010111÷1101 余000???? ④ 0011010÷1101 余000???? ⑤ 1000110÷1101 余000 ⑥ 1001111÷1101 余100???? ⑦ 1010001÷1101 余000???? ⑧ 1011000÷1101 余100 授課：XXX 所以＿C＿、＿D＿和＿E＿的答案是②、⑥、⑧ 【例2】計(jì)算機(jī)中常用的一種檢錯(cuò)碼是CRC，即 _A_ 碼。在進(jìn)行編碼過程中要使用 _B_ 運(yùn)算。假設(shè)使用的生成多項(xiàng)式是 G(X)=X4+X3+X+1， 原始報(bào)文為11001010101，則編碼后的報(bào)文為 _C_ 。CRC

20、碼 _D_ 的說法是正確的。 在無線電通信中常采用它規(guī)定碼字長(zhǎng)為7位．并且其中總有且僅有3個(gè)“1”。這種碼的編碼效率為_E_。 供選擇的答案： A：① 水平垂直奇偶校驗(yàn)??????????????????????? ② 循環(huán)求和?????????????????????????? ③ 循環(huán)冗余?????????????????????????? ④正比率 B：① 模2除法??????????????????????? ②定點(diǎn)二進(jìn)制除法????????????????????? ③二－十進(jìn)制除法??????????????????? ④循環(huán)移位法 C：① 1100101010111??

21、??????????? ② 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的論述中可

22、得出：???? 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定比碼，就

23、是整個(gè)碼字長(zhǎng)度為7位，其中1的位數(shù)固定為3。所有128個(gè)7位代碼（0000000～1111111）中只有1的位數(shù)固定為3的才是其合法碼字。可以用求組合的公式求出其合法碼字?jǐn)?shù)為：C73＝7!/(3!*(7-3)!)＝7*6*5/(1*2*3)＝35 編碼效率＝合法碼字所需位數(shù)/碼字總位數(shù)＝(log235)/7 授課：XXX 而對(duì)于CRC的實(shí)現(xiàn)有兩種方式，分別為多項(xiàng)式和查表法 下面先講講多余多項(xiàng)式的實(shí)現(xiàn)，附代碼如下 [cpp]?view plain?copy 1. /*??? 2. ?*??函數(shù)名：GetCrc32??? 3. ?*??函數(shù)原型：unsigned?int?Get

24、Crc32(char*?InStr,unsigned?int?len)??? 4. ?*??????參數(shù)：InStr??---指向需要計(jì)算CRC32值的字符串??? 5. ?*??????????len??---為InStr的長(zhǎng)度??? 6. ?*??????返回值為計(jì)算出來的CRC32結(jié)果。??? 7. ?*??? 8. ?*??函數(shù)名：GetCrc16??? 9. ?*??函數(shù)原型：unsigned?short?GetCrc16(char*?InStr,unsigned?int?len)??? 10. ?*??????參數(shù)：InStr??---指向需要計(jì)算CRC32值的字符串

25、??? 11. ?*??????????len??---為InStr的長(zhǎng)度??? 12. ?*??????返回值為計(jì)算出來的CRC32結(jié)果。??? 13. ?*??? 14. ?*????2009/03/26???Edit?By?iawen??? 15. ?*??? 16. ?*/???? 17. ???? 18. unsigned?int?GetCrc32(char*?InStr,unsigned?int?len){???????? 19. ??//生成Crc32的查詢表????? 20. ??unsigned?int?Crc32Table[256];?????? 21

26、. ??int?i,j;???????? 22. ??unsigned?int?Crc;???????? 23. ??for?(i?=?0;?i?>?1)?^?0xEDB88320;???????? 28. ??????else??????? 29. ????????Crc?>>=?1;??????

27、 30. ????}???????? 31. ????Crc32Table[i]?=?Crc;???????? 32. ??}???????? 33. ???? 34. ??//開始計(jì)算CRC32校驗(yàn)值????? 35. ??Crc=0xffffffff;???????? 36. ??for(int?i=0;?i>?8)?^?Crc32Table[(Crc?&?0xFF)?^?InStr[i]];???????? 38. ??}????? 39. ??????? 40. ??Crc?^=?

28、0xFFFFFFFF;????? 授課：XXX 41. ??return?Crc;???????? 42. }???????? 43. ???? 44. unsigned?short?GetCrc16(char*?InStr,unsigned?int?len){???????? 45. ??//生成Crc16的查詢表????? 46. ??unsigned?short?Crc16Table[256];?????? 47. ??unsigned?int?i,j;????? 48. ??unsigned?short?Crc;???????? 49. ??for?(i?=?0

29、;?i?>?1)?^?0xA001;???????? 56. ??????else??????? 57. ????????Crc?>>=?1;?????? 58. ????}???????? 59. ????Crc16Table[i]?=?Crc;????

30、???? 60. ??}????? 61. ??????? 62. ??//開始計(jì)算CRC16校驗(yàn)值????? 63. ??Crc=0x0000;?????????? 64. ??for(i=0;?i>?8)?^?Crc16Table[(Crc?&?0xFF)?^?InStr[i]];??????? 66. ???? 67. ??}????? 68. ??//Crc?^=?0x0000;??????? 69. ??return?Crc;???????? 70. }?????? 71. #

31、include??????? 72. using?namespace?std;????? 73. ???? 74. int?main()?? 75. {????? 76. ??char?str[]="iawen";????? 77. ??unsigned?int?crc;?? 78. ??//crc?32校驗(yàn)?? 79. ??crc=GetCrc32(str,5);????? 80. ??????? 81. ??printf("%08X\n",crc);????? 82. ??//crc?16校驗(yàn)?? 83. ??crc=GetCrc16(str,5);//0x5359????? 84. ??//printf("%04X\n",crc);????? 授課：XXX 85. ??system("pause");?? 86. ??return?0;????? 87. }??? 88. 89. 90. 91. （注：可編輯下載，若有不當(dāng)之處，請(qǐng)指正，謝謝!） 92. 93. 94. 95. 96. 97. 授課：XXX