循環(huán)冗余檢驗(yàn)CRC 算法原理

1、CRC的校驗(yàn)原理隨著數(shù)據(jù)采集系統(tǒng)的功能日益強(qiáng)大，以及微型計(jì)算機(jī)的普及，在現(xiàn)代工業(yè)中，利用微機(jī)進(jìn)行數(shù)據(jù)通訊的工業(yè)控制應(yīng)用得也越來(lái)越廣泛。特別是在大規(guī)模高精度數(shù)據(jù)采集系統(tǒng)中，對(duì)數(shù)據(jù)進(jìn)行分析和計(jì)算將占用很大一部分單片機(jī)的資源，可以將采集到的數(shù)據(jù)通過(guò)串行通訊方式傳送給PC機(jī)，由PC機(jī)來(lái)完成數(shù)據(jù)的處理工作。但是由于傳輸距離、現(xiàn)場(chǎng)狀況等諸多可能出現(xiàn)的因素的影響，計(jì)算機(jī)與受控設(shè)備之間的通訊數(shù)據(jù)常會(huì)發(fā)生無(wú)法預(yù)測(cè)的錯(cuò)誤。為了防止錯(cuò)誤所帶來(lái)的影響，在數(shù)據(jù)的接收端必須進(jìn)行差錯(cuò)校驗(yàn)。雖然差錯(cuò)校驗(yàn)也可以完全由硬件來(lái)承擔(dān)，但由于單片機(jī)和PC都具有很強(qiáng)的軟件編程能力，這就為實(shí)施軟件的差錯(cuò)校驗(yàn)提供了前提條件，而軟件的差錯(cuò)校驗(yàn)

2、有經(jīng)濟(jì)實(shí)用并且不增加硬件開(kāi)銷(xiāo)的優(yōu)點(diǎn)。1 、CRC法的原理傳統(tǒng)的差錯(cuò)檢驗(yàn)法有：奇偶校驗(yàn)法，校驗(yàn)和法，行列冗余校驗(yàn)法等。這些方法都是在數(shù)據(jù)后面加一定數(shù)量的冗余位同時(shí)發(fā)送出去，例如在單片機(jī)的通訊方式2和3中，TB8就可以作為奇偶校驗(yàn)位同數(shù)據(jù)一起發(fā)送出去，在數(shù)據(jù)的接收端通過(guò)對(duì)數(shù)據(jù)信息進(jìn)行比較、判別或簡(jiǎn)單的求和運(yùn)算，然后將所得和接收到的冗余位進(jìn)行比較，若相等就認(rèn)為數(shù)據(jù)接收正確，否則就認(rèn)為數(shù)據(jù)傳送過(guò)程中出現(xiàn)錯(cuò)誤。但是冗余位只能反映數(shù)據(jù)行或列的奇偶情況，這類(lèi)檢驗(yàn)方法對(duì)數(shù)據(jù)行或列的偶數(shù)個(gè)錯(cuò)誤不敏感，漏判的概率很高。因此，此種方法的可靠性就差。循環(huán)冗余碼校驗(yàn)英文名稱為Cyclical Redundan

3、cy Check，簡(jiǎn)稱CRC。它是利用除法及余數(shù)的原理來(lái)作錯(cuò)誤偵測(cè)(Error Detecting)的。實(shí)際應(yīng)用時(shí)，發(fā)送裝置計(jì)算出CRC值并隨數(shù)據(jù)一同發(fā)送給接收裝置，接收裝置對(duì)收到的數(shù)據(jù)重新計(jì)算CRC并與收到的CRC相比較，若兩個(gè)CR C值不同，則說(shuō)明數(shù)據(jù)通訊出現(xiàn)錯(cuò)誤。由于這種方法取得校驗(yàn)碼的方式具有很強(qiáng)的信息覆蓋能力，所以它是一種效率極高的錯(cuò)誤校驗(yàn)法。錯(cuò)誤的概率幾乎為零。在很多的儀器設(shè)備中都采用這種冗余校驗(yàn)的通訊規(guī)約。根據(jù)應(yīng)用環(huán)境與習(xí)慣的不同，CRC又可分為以下幾種標(biāo)準(zhǔn)： CRC-12碼; CRC-16碼; CRC-CCITT碼; CRC-32碼。CRC-12碼通常用來(lái)傳送6-bit字符串。

4、CRC-16及CRC-CCITT碼則是用來(lái)傳送8-b it字符，其中CRC-16為美國(guó)采用，而CRC-CCITT為歐洲國(guó)家所采用。CRC-32碼大都被采用在一種稱為Point-to-Point的同步傳輸中。2、 CRC校驗(yàn)碼的生成過(guò)程2.1原理分析過(guò)程  假設(shè)數(shù)據(jù)傳輸過(guò)程中需要發(fā)送15位的二進(jìn)制信息g=101001110100001，這串二進(jìn)制碼可表示為代數(shù)多項(xiàng)式g(x) = x14 + x12 + x9 + x8 + x7 + x5 + 1，其中g(shù)中第k位的值，對(duì)應(yīng)g(x)中xk的系數(shù)。將g(x)乘以xm，既將g后加m個(gè)0，然后除以m階多項(xiàng)式h(x)，得到的(m-1)階余項(xiàng)r(x)

5、對(duì)應(yīng)的二進(jìn)制碼r就是CRC編碼。h(x)可以自由選擇或者使用國(guó)際通行標(biāo)準(zhǔn)，一般按照h(x)的階數(shù)m，將CRC算法稱為CRC-m，比如CRC-32、CRC-64等。國(guó)際通行標(biāo)準(zhǔn)可參看/wiki/Cyclic_redundancy_check g(x)和h(x)的除運(yùn)算，可以通過(guò)g和h做xor（異或）運(yùn)算。比如將11001與10101做xor運(yùn)算：       明白了xor運(yùn)算法則后，舉一個(gè)例子使用CRC-8算法求101001110100001的效驗(yàn)碼。CRC-8標(biāo)準(zhǔn)的h(x) = x8 + x

6、7 + x6 + x4 + x2 + 1，既h是9位的二進(jìn)制串111010101。        經(jīng)過(guò)迭代運(yùn)算后，最終得到的r是10001100，這就是CRC效驗(yàn)碼。通過(guò)示例，可以發(fā)現(xiàn)一些規(guī)律，依據(jù)這些規(guī)律調(diào)整算法：      1. 每次迭代，根據(jù)gk的首位決定b，b是與gk進(jìn)行運(yùn)算的二進(jìn)制碼。若gk的首位是1，則b=h；若gk的首位是0，則b=0，或者跳過(guò)此次迭代，上面的例子中就是碰到0后直接跳到后面的非零位。     &#

7、160;              2. 每次迭代，gk的首位將會(huì)被移出，所以只需考慮第2位后計(jì)算即可。這樣就可以舍棄h的首位，將b取h的后m位。比如CRC-8的h是111010101，b只需是11010101。            3. 每次迭代，受到影響的是gk的前m位，所以構(gòu)建一個(gè)m位的寄存器S，此寄存器儲(chǔ)存gk的前m位。每次迭代計(jì)算前先將

8、S的首位拋棄，將寄存器左移一位，同時(shí)將gk的后一位加入寄存器。若使用此種方法，計(jì)算步驟如下：       藍(lán)色表示寄存器S的首位，是需要移出的，b根據(jù)S的首位選擇0或者h(yuǎn)。黃色是需要移入寄存器的位。S'是經(jīng)過(guò)位移后的S。 2.2查表法     同樣是上面的那個(gè)例子，將數(shù)據(jù)按每4位組成1個(gè)block，這樣g就被分成6個(gè)block。          下面的表展示了4次迭代

9、計(jì)算步驟，灰色背景的位是保存在寄存器中的。       經(jīng)4次迭代，B1被移出寄存器。被移出的部分，不是我們關(guān)心的，我們關(guān)心的是這4次迭代對(duì)B2和B3產(chǎn)生了什么影響。注意表中紅色的部分，先作如下定義：   B23 = 00111010   b1 = 00000000   b2 = 01010100   b3 = 10101010   b4 = 11010101 

10、60; b' = b1 xor b2 xor b3 xor b44次迭代對(duì)B2和B3來(lái)說(shuō),實(shí)際上就是讓它們與b1,b2,b3,b4做了xor計(jì)算，既：    B23 xor b1 xor b2 xor b3 xor b4可以證明xor運(yùn)算滿足交換律和結(jié)合律，于是：B23 xor b1 xor b2 xor b3 xor b4 = B23 xor (b1 xor b2 xor b3 xor b4) = B23 xor b' = 00111010 00101011 = 00010001b1是由B1的第1位決定的，b2是由B1迭代1次后的第2位

11、決定（既是由B1的第1和第2位決定），同理,b3和b4都是由B1決定。通過(guò)B1就可以計(jì)算出b'。另外，B1由4位組成，其一共24有種可能值。于是我們就可以想到一種更快捷的算法，事先將b'所有可能的值，16個(gè)值可以看成一個(gè)表；這樣就可以不必進(jìn)行那4次迭代，而是用B1查表得到b'值，將B1移出，B3移入，與b'計(jì)算，然后是下一次迭代。      可看到每次迭代，寄存器中的數(shù)據(jù)以4位為單位移入和移出，關(guān)鍵是通過(guò)寄存器前4位查表獲得，這樣的算法可以大大提高運(yùn)算速度。上面的方法是半字節(jié)查表法，另外還有單字節(jié)和雙字

12、節(jié)查表法，原理都是一樣的事先計(jì)算出28或216個(gè)b'的可能值，迭代中使用寄存器前8位或16位查表獲得b'。2.3反向算法   之前討論的算法可以稱為正向CRC算法，意思是將g左邊的位看作是高位，右邊的位看作低位。G的右邊加m個(gè)0，然后迭代計(jì)算是從高位開(kāi)始，逐步將低位加入到寄存器中。在實(shí)際的數(shù)據(jù)傳送過(guò)程中，是一邊接收數(shù)據(jù)，一邊計(jì)算CRC碼，正向算法將新接收的數(shù)據(jù)看作低位。 逆向算法顧名思義就是將左邊的數(shù)據(jù)看作低位，右邊的數(shù)據(jù)看作高位。這樣的話需要在g的左邊加m個(gè)0，h也要逆向，例如正向CRC-16算法h=0x4c11db8，逆向CRC-16

13、算法h=0xedb88320。b的選擇0還是h，由寄存器中右邊第1位決定，而不是左邊第1位。寄存器仍舊是向左位移，就是說(shuō)迭代變成從低位到高位。3、CRC算法實(shí)現(xiàn)：冗余循環(huán)碼包括2個(gè)字節(jié)，即16位二進(jìn)制數(shù)。先預(yù)置16位寄存器全部為1，再逐步把每8位的數(shù)據(jù)信息進(jìn)行處理。在進(jìn)行CRC計(jì)算時(shí)只用8位數(shù)據(jù)位，起始位和停止位，如有奇偶校驗(yàn)位的話也包括奇偶校驗(yàn)位，都不參與CRC計(jì)算。 計(jì)算CRC的步驟為：（1）      設(shè)置CRC寄存器，并給其賦值為“余數(shù)初始值”。（2）     

14、60;將數(shù)據(jù)的第一個(gè)8-bit字符與CRC寄存器進(jìn)行異或，并把結(jié)果存入CRC寄存器。（3）      CRC寄存器向左移一位，LSB補(bǔ)零，移出并檢查MSB。（4）      如果MSB為0，重復(fù)第三步；若MSB為1，CRC寄存器與0x1021相異或。（5）      重復(fù)第3與第4步直到8次移位全部完成。此時(shí)一個(gè)8-bit數(shù)據(jù)處理完畢。（6）      重復(fù)

15、第2至第5步直到所有數(shù)據(jù)全部處理完成。（7）      最終CRC寄存器的內(nèi)容與“結(jié)果異或值”進(jìn)行或非操作后即為CRC值。當(dāng)所有的信息處理完后，最后寄存器中的內(nèi)容即為CRC碼。這個(gè)CRC碼將由發(fā)送設(shè)備跟在數(shù)據(jù)的最后一起發(fā)送。常見(jiàn)的三種CRC 標(biāo)準(zhǔn)用到個(gè)各個(gè)參數(shù)如下表。 CCITTCRC16CRC32校驗(yàn)和位寬W161632生成多項(xiàng)式x16+x12+x5+1x16+x15+x2+1x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1除數(shù)（多項(xiàng)式）0x10210x80050x04

16、C11DB7余數(shù)初始值0xFFFF0x00000xFFFFFFFF結(jié)果異或值0x00000x00000xFFFFFFFF 所謂的“余數(shù)初始值”就是在計(jì)算CRC值的開(kāi)始，給CRC寄存器一個(gè)初始值。“結(jié)果異或值”是在其余計(jì)算完成后將CRC寄存器的值在與這個(gè)值進(jìn)行一下異或操作作為最后的校驗(yàn)值。3.1 CRC軟件實(shí)現(xiàn) 示例性的C代碼如下所示，因?yàn)樾屎艿?，?xiàng)目中如對(duì)計(jì)算時(shí)間有要求應(yīng)該避免采用這樣的代碼。不過(guò)這個(gè)代碼已經(jīng)比網(wǎng)上常見(jiàn)的計(jì)算代碼要好了，因?yàn)檫@個(gè)代碼有一個(gè)crc的參數(shù)，可以將上次計(jì)算的crc結(jié)果傳入函數(shù)中作為這次計(jì)算的初始值，這對(duì)大數(shù)據(jù)塊的CRC計(jì)算是很有用的，不需要一次將所有數(shù)據(jù)讀入內(nèi)存，而

17、是讀一部分算一次，全讀完后就計(jì)算完了。這對(duì)內(nèi)存受限系統(tǒng)還是很有用的。1. #define POLY        0x1021  2. /* 3.  * Calculating CRC-16 in 'C' 4.  * para addr, start of data 5.  * para num,

18、60;length of data 6.  * para crc, incoming CRC 7. */  8. uint16_t crc16(unsigned char *addr, int num, uint16_t crc)  9.   10.     int i;  11.   &

19、#160; for (; num > 0; num-)              /* Step through bytes in memory */  12.       13.       

20、  crc = crc  (*addr+ << 8);     /* Fetch byte from memory, XOR into CRC top byte*/  14.         for (i = 0; i 

21、;< 8; i+)             /* Prepare to rotate 8 bits */  15.           16.           

22、  if (crc & 0x8000)            /* b15 is set. */  17.                 crc = (crc <&

23、lt; 1)  POLY;    /* rotate and XOR with polynomic */  18.             else               &

24、#160;          /* b15 is clear. */  19.                 crc <<= 1;         

25、0;        /* just rotate */  20.                                  

26、0;   /* Loop for 8 bits */  21.         crc &= 0xFFFF;                  /* Ensure CRC remai

27、ns 16-bit value */  22.                                    /* Loop until num=0 *

28、/  23.     return(crc);                    /* Return updated CRC */  24.   上面的算法對(duì)數(shù)據(jù)流逐位進(jìn)行計(jì)算，效率很低。實(shí)際上仔細(xì)分析CRC計(jì)算的數(shù)學(xué)性質(zhì)后我們可以多位多位計(jì)算，最常用的是

29、一種按字節(jié)查表的快速算法。該算法基于這樣一個(gè)事實(shí)：計(jì)算本字節(jié)后的CRC碼，等于上一字節(jié)余式CRC碼的低8位左移8位，加上上一字節(jié)CRC右移 8位和本字節(jié)之和后所求得的CRC碼。如果我們把8位二進(jìn)制序列數(shù)的CRC(共256個(gè))全部計(jì)算出來(lái)，放在一個(gè)表里，編碼時(shí)只要從表中查找對(duì)應(yīng)的值進(jìn)行處理即可。按照這個(gè)方法，可以有如下的代碼：1. /* 2. crc.h 3. */  4.   5. #ifndef CRC_H_INCLUDED  6. #define CRC_H_INCLUDED &#

30、160;7.   8. /* 9. * The CRC parameters. Currently configured for CCITT. 10. * Simply modify these to switch to another CRC Standard. 11. */  12. /* 13. #define POLYNOMIAL 

31、;         0x8005 14. #define INITIAL_REMAINDER   0x0000 15. #define FINAL_XOR_VALUE     0x0000 16. */  17. #define POLYNOMIAL        &#

32、160; 0x1021  18. #define INITIAL_REMAINDER   0xFFFF  19. #define FINAL_XOR_VALUE     0x0000  20.   21. /* 22. #define POLYNOMIAL          0x1021&

33、#160;23. #define POLYNOMIAL          0xA001 24. #define INITIAL_REMAINDER   0xFFFF 25. #define FINAL_XOR_VALUE     0x0000 26. */  27.   28. /* 29. * T

34、he width of the CRC calculation and result. 30. * Modify the typedef for an 8 or 32-bit CRC standard. 31. */  32. typedef unsigned short width_t;  33. #define WIDTH&

35、#160;(8 * sizeof(width_t)  34. #define TOPBIT (1 << (WIDTH - 1)  35.   36. /* 37.  * Initialize the CRC lookup table. 38.  * This table is used by cr

36、cCompute() to make CRC computation faster. 39.  */  40. void crcInit(void);  41.   42. /* 43.  * Compute the CRC checksum of a binary message block. 44.  * para

37、 message, 用來(lái)計(jì)算的數(shù)據(jù) 45.  * para nBytes, 數(shù)據(jù)的長(zhǎng)度 46.  * note This function expects that crcInit() has been called 47.  *       first to initialize the 

38、;CRC lookup table. 48.  */  49. width_t crcCompute(unsigned char * message, unsigned int nBytes);  50.   51. #endif / CRC_H_INCLUDED   1. /* 2.  *crc.c 3.  */  

39、4.   5. #include "crc.h"  6. /* 7. * An array containing the pre-computed intermediate result for each 8. * possible byte of input. This is used to speed up

40、0;the computation. 9. */  10. static width_t crcTable256;  11.   12. /* 13.  * Initialize the CRC lookup table. 14.  * This table is used by crcCompute() to make

41、0;CRC computation faster. 15.  */  16. void crcInit(void)  17.   18.     width_t remainder;  19.     width_t dividend;  20.     int bit;  21

42、.     /* Perform binary long division, a bit at a time. */  22.     for(dividend = 0; dividend < 256; dividend+)  23.       24.

43、         /* Initialize the remainder.  */  25.         remainder = dividend << (WIDTH - 8);  26.        

44、 /* Shift and XOR with the polynomial.   */  27.         for(bit = 0; bit < 8; bit+)  28.           29.

45、60;           /* Try to divide the current data bit.  */  30.             if(remainder & TOPBIT)  31. 

46、0;             32.                 remainder = (remainder << 1)  POLYNOMIAL;  33.     

47、60;         34.             else  35.               36.           

48、;      remainder = remainder << 1;  37.               38.           39.        

49、 /* Save the result in the table. */  40.         crcTabledividend = remainder;  41.       42.  /* crcInit() */  43.   44. /*

50、 45.  * Compute the CRC checksum of a binary message block. 46.  * para message, 用來(lái)計(jì)算的數(shù)據(jù) 47.  * para nBytes, 數(shù)據(jù)的長(zhǎng)度 48.  * note This function expects that c

51、rcInit() has been called 49.  *       first to initialize the CRC lookup table. 50.  */  51. width_t crcCompute(unsigned char * message, unsigned int nByte

52、s)  52.   53.     unsigned int offset;  54.     unsigned char byte;  55.     width_t remainder = INITIAL_REMAINDER;  56.     /* Di

53、vide the message by the polynomial, a byte at a time. */  57.     for( offset = 0; offset < nBytes; offset+)  58.       59.   &

54、#160;     byte = (remainder >> (WIDTH - 8)  messageoffset;  60.         remainder = crcTablebyte  (remainder << 8);  61.   

55、    62.     /* The final remainder is the CRC result. */  63.     return (remainder  FINAL_XOR_VALUE);  64.  /* crcCompute() */  1. uint crctable= /CRC計(jì)算用表2. 0x0000,0xC0C1,0xC181,0x0140,0xC301,0x03C0,0x0280,0xC241,3. 0xC601,0x06