CCITT CRC-16計(jì)算原理與實(shí)現(xiàn)

1、CCITT CRC-16計(jì)算原理與實(shí)現(xiàn)CRC的全稱為Cyclic Redundancy Check，中文名稱為循環(huán)冗余校驗(yàn)。它是一類重要的線性分組碼，編碼和解碼方法簡(jiǎn)單，檢錯(cuò)和糾錯(cuò)能力強(qiáng)，在通信領(lǐng)域廣泛地用于實(shí)現(xiàn)差錯(cuò)控制。實(shí)際上，除數(shù)據(jù)通信外，CRC在其它很多領(lǐng)域也是大有用武之地的。例如我們讀軟盤上的文件，以及解壓一個(gè)ZIP文件時(shí)，偶爾會(huì)碰到“Bad CRC”錯(cuò)誤，由此它在數(shù)據(jù)存儲(chǔ)方面的應(yīng)用可略見(jiàn)一斑。 差錯(cuò)控制理論是在代數(shù)理論基礎(chǔ)上建立起來(lái)的。這里我們著眼于介紹CRC的算法與實(shí)現(xiàn)，對(duì)原理只能捎帶說(shuō)明一下。若需要進(jìn)一步了解線性碼、分組碼、循環(huán)碼、糾錯(cuò)編碼等方面的原理，可以閱讀有關(guān)資料。 利用C

2、RC進(jìn)行檢錯(cuò)的過(guò)程可簡(jiǎn)單描述為：在發(fā)送端根據(jù)要傳送的k位二進(jìn)制碼序列，以一定的規(guī)則產(chǎn)生一個(gè)校驗(yàn)用的r位監(jiān)督碼(CRC碼)，附在原始信息后邊，構(gòu)成一個(gè)新的二進(jìn)制碼序列數(shù)共k+r位，然后發(fā)送出去。在接收端，根據(jù)信息碼和CRC碼之間所遵循的規(guī)則進(jìn)行檢驗(yàn)，以確定傳送中是否出錯(cuò)。這個(gè)規(guī)則，在差錯(cuò)控制理論中稱為“生成多項(xiàng)式”。 1 代數(shù)學(xué)的一般性算法 在代數(shù)編碼理論中，將一個(gè)碼組表示為一個(gè)多項(xiàng)式，碼組中各碼元當(dāng)作多項(xiàng)式的系數(shù)。例如 1100101 表示為 1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1，即 x6+x5+x2+1。 設(shè)

3、編碼前的原始信息多項(xiàng)式為P(x)，P(x)的最高冪次加1等于k；生成多項(xiàng)式為G(x)，G(x)的最高冪次等于r；CRC多項(xiàng)式為R(x)；編碼后的帶CRC的信息多項(xiàng)式為T(x)。 發(fā)送方編碼方法：將P(x)乘以xr(即對(duì)應(yīng)的二進(jìn)制碼序列左移r位)，再除以G(x)，所得余式即為R(x)。用公式表示為 T(x)=xrP(x)+R(x) 接收方解碼方法：將T(x)除以G(x)，如果余數(shù)為0，則說(shuō)明傳輸中無(wú)錯(cuò)誤發(fā)生，否則說(shuō)明傳輸有誤。 舉例來(lái)說(shuō)，設(shè)信息碼為1100，生成多項(xiàng)式為1011，即P(x)=x3+x2，G(x)=x3+x+1，計(jì)算CRC的過(guò)程為     &

4、#160; xrP(x)     x3(x3+x2)     x6+x5                    x     - = - = - = (x3+x2+x) + -       G(x)   

5、;    x3+x+1      x3+x+1                 x3+x+1即 R(x)=x。注意到G(x)最高冪次r=3，得出CRC為010。 如果用豎式除法，計(jì)算過(guò)程為               

6、1110            -         1011 /1100000     (1100左移3位)            1011          

7、  -             1110             1011             -          

8、0;   1010              1011              -               0010     

9、;          0000               -                010因此，T(x)=(x6+x5)+(x)=x6+x5+x, 即 1100000+010=1100010 如果傳輸無(wú)誤， &

10、#160;      T(x)     x6+x5+x      - = - = x3+x2+x,       G(x)     x3+x+1無(wú)余式。回頭看一下上面的豎式除法，如果被除數(shù)是1100010，顯然在商第三個(gè)1時(shí)，就能除盡。 上述推算過(guò)程，有助于我們理解CRC的概念。但直接編程來(lái)實(shí)現(xiàn)上面的算法，不僅繁瑣，效率也不高。實(shí)際上在工程中不會(huì)直接這樣去計(jì)算

11、和驗(yàn)證CRC。 下表中列出了一些見(jiàn)于標(biāo)準(zhǔn)的CRC資料： 名稱   生成多項(xiàng)式   簡(jiǎn)記式*   應(yīng)用舉例 CRC-4   x4+x+1      ITU G.704 CRC-12   x12+x11+x3+x+1       CRC-16   x16+x12+x2+1   1005   IBM SDLC CRC-ITU*   x16+x12+x5+1   1021   ISO HDLC, ITU X.25, V.34

12、/V.41/V.42, PPP-FCS CRC-32   x32+x26+x23+.+x2+x+1   04C11DB7   ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCS CRC-32c   x32+x28+x27+.+x8+x6+1   1EDC6F41   SCTP     *  生成多項(xiàng)式的最高冪次項(xiàng)系數(shù)是固定的1，故在簡(jiǎn)記式中，將最高的1統(tǒng)一去掉了，如04C11DB7實(shí)際上是104C11DB7。    * 前

13、稱CRC-CCITT。ITU的前身是CCITT。 4.CRC算法的實(shí)現(xiàn) - 要用程序?qū)崿F(xiàn)CRC算法，考慮對(duì)第2節(jié)的長(zhǎng)除法做一下變換，依然是M = 11100110，G = 1011， 其系數(shù)r為3。                                   &

14、#160;      11001100                           -              1011 )11100110000 &

15、#160;                         1011.                          

16、;       -.                                     1010.       &

17、#160;                        1011.                  -.         &#

18、160;                        1110.                           

19、        1011.                                      -.     &#

20、160;                                   1010.               &

21、#160;                      1011.                             

22、;          -                                         &#

23、160;  100  <-校驗(yàn)碼                                  程序可以如下實(shí)現(xiàn)：     1)將Mxr的前r位放入一個(gè)長(zhǎng)度為r的寄存器；     2)如果寄

24、存器的首位為1，將寄存器左移1位(將Mxr剩下部分的MSB移入寄存器的LSB)，       再與G的后r位異或，否則僅將寄存器左移1位(將Mxr剩下部分的MSB移入寄存器的LSB)；     3)重復(fù)第2步，直到M全部Mxr移入寄存器；     4)寄存器中的值則為校驗(yàn)碼。     基于以上算法，我們可以看一下上面例子的程序計(jì)算過(guò)程：（r3）       首先，111 00110000前三位進(jìn)入

25、寄存器，即111        這時(shí)寄存器首位為1，執(zhí)行第2步,移位成110 0110000,這時(shí)寄存器中為前三位110，將其與011（生成多項(xiàng)式后三位）異或，得101 0110000.         然后繼續(xù)第2步，101首位為1，移位010 110000,然后010與011異或，得  001 110000 前面兩個(gè)0，連續(xù)以為2次且不用計(jì)算異或，得111 0000，接著移位110 000，異或得101 000    &#

26、160;   第一位為1，移位得010 00，前三位異或得001 00        最后因?yàn)榍懊鎯蓚€(gè)0，直接移位兩次后得寄存器中的內(nèi)容100,這時(shí)Mxr位的所有內(nèi)容都移入寄存器，運(yùn)算結(jié)束，記得檢驗(yàn)碼為100。（關(guān)鍵先判斷首位是否為1，然后移位，然后計(jì)算）          111 00110000移位>1 110 0110000         &#

27、160;                                       011           

28、60;                                     101 0110000  ->101第一位為1，移位且計(jì)算        

29、                                         1 010 110000        

30、0;                                           011        

31、;                                            001 110000->001第一位第二位均為0，移位2次  &

32、#160;                                                 00 111

33、 0000->111第一位為1，移位且計(jì)算                                               

34、;          1 110 000                                        

35、                    011                               &

36、#160;                            101 000->101第一位為1，移位且計(jì)算                  

37、60;                                         1 010 00         

38、;                                                  

39、;    011                                               

40、                001 00->移位2次得100 用CRC16-CCITT的生成多項(xiàng)式0x1021，其C代碼(本文所有代碼假定系統(tǒng)為32位，且都在VC6上編譯通過(guò))如下： unsigned short do_crc(unsigned char *message, unsigned int len)     int i, j;     unsigned short c

41、rc_reg;             crc_reg = (message0 << + message1;     for (i = 0; i < len; i+)             if (i < len - 2)           

42、  for (j = 0; j <= 7; j+)                             if (short)crc_reg < 0)              

43、0;      crc_reg = (crc_reg << 1) + (messagei + 2 >> (7 - i) 0x1021;                 else                 

44、60;   crc_reg = (crc_reg << 1) + (messagei + 2 >> (7 - i);                           else             f

45、or (j = 0; j <= 7; j+)                             if (short)crc_reg < 0)                

46、     crc_reg = (crc_reg << 1) 0x1021;                 else                     crc_reg <<= 1; 

47、;                                         return crc_reg;   顯然，每次內(nèi)循環(huán)的行為取決于寄存器首位。由于異或運(yùn)算滿足交換率和結(jié)合律，以及與0異或無(wú)影響，消息可以不移入寄存

48、器，而在每次內(nèi)循環(huán)的時(shí)候，寄存器首位再與對(duì)應(yīng)的消息位異或。改進(jìn)的代碼如下： unsigned short do_crc(unsigned char *message, unsigned int len)     int i, j;     unsigned short crc_reg = 0;     unsigned short current;             for (i = 0; i <

49、; len; i+)             current = messagei << 8;         for (j = 0; j < 8; j+)                     if (short)(crc_re

50、g current) < 0)                 crc_reg = (crc_reg << 1) 0x1021;             else              &

51、#160;  crc_reg <<= 1;             current <<= 1;                            return crc_reg; 以上的討論中，消息的每個(gè)字節(jié)都是

52、先傳輸MSB，CRC16-CCITT標(biāo)準(zhǔn)卻是按照先傳輸LSB，消息右移進(jìn)寄存器來(lái)計(jì)算的。只需將代碼改成判斷寄存器的LSB，將0x1021按位顛倒后(0x8408)與寄存器異或即可，如下所示： Java代碼 1. unsigned short do_crc(unsigned char *message, unsigned int len)    2.   3.     int i, j;   4.

53、    unsigned short crc_reg = 0;   5.     unsigned short current;   6.            7.     for (i = 0; i < len

54、; i+)    8.        9.         current = messagei;   10.         for (j = 0; j < 8; j+)    11.

55、60;           12.             if (crc_reg  current) & 0x0001)   13.               

56、;  crc_reg = (crc_reg >> 1)  0x8408;   14.             else    15.                 crc_re

57、g >>= 1;    16.             current >>= 1;               17.            1

58、8.        19.     return crc_reg;   20.       unsigned short do_crc(unsigned char *message, unsigned int len) int i, j; unsigned short crc_reg = 0; unsigned short current; for (i = 0; i < len; i+) curre

59、nt = messagei; for (j = 0; j < 8; j+) if (crc_reg current) & 0x0001) crc_reg = (crc_reg >> 1) 0x8408; else crc_reg >>= 1; current >>= 1; return crc_reg; 該算法使用了兩層循環(huán)，對(duì)消息逐位進(jìn)行處理，這樣效率是很低的。為了提高時(shí)間效率，通常的思想是以空間換時(shí)間?？紤]到內(nèi)循環(huán)只與當(dāng)前的消息字節(jié)和crc_reg的低字節(jié)有關(guān)，對(duì)該算法做以下等效轉(zhuǎn)換： Java代碼 1. unsigned sho

60、rt do_crc(unsigned char *message, unsigned int len)    2.   3.     int i, j;   4.     unsigned short crc_reg = 0;   5.     unsigned

61、0;char  index;   6.     unsigned short to_xor;   7.           8.     for (i = 0; i < len; i+)    9.    

62、0;   10.         index = (crc_reg  messagei) & 0xff;    11.         to_xor = index;          12.  

63、60;      for (j = 0; j < 8; j+)    13.             14.             if (to_xor & 0x0

64、001)   15.                 to_xor = (to_xor >> 1)  0x8408;   16.             else    17.

65、                to_xor >>= 1;              18.            19.     

66、60;   crc_reg = (crc_reg >> 8)  to_xor;   20.        21.     return crc_reg;   22.    unsigned short do_crc(unsigned char *message, unsigned int len) int i, j;

67、 unsigned short crc_reg = 0; unsigned char index; unsigned short to_xor; for (i = 0; i < len; i+) index = (crc_reg messagei) & 0xff; to_xor = index; for (j = 0; j < 8; j+) if (to_xor & 0x0001) to_xor = (to_xor >> 1) 0x8408; else to_xor >>= 1; crc_reg = (crc_reg >> 8)

68、to_xor; return crc_reg; 現(xiàn)在內(nèi)循環(huán)只與index相關(guān)了，可以事先以數(shù)組形式生成一個(gè)表crc16_ccitt_table，使得to_xor = crc16_ccitt_tableindex，于是可以簡(jiǎn)化為： Java代碼 1. unsigned short do_crc(unsigned char *message, unsigned int len)    2.   3.     unsigned sh

69、ort crc_reg = 0;    4.              5.     while (len-)    6.         crc_reg = (crc_reg >> 8) 

70、0;crc16_ccitt_table(crc_reg  *message+) & 0xff;   7.            8.     return crc_reg;   9.      unsigned short do_crc(unsigned char *message, unsigned int

71、len) unsigned short crc_reg = 0; while (len-) crc_reg = (crc_reg >> 8) crc16_ccitt_table(crc_reg *message+) & 0xff; return crc_reg; crc16_ccitt_table通過(guò)以下代碼生成： Java代碼 1. int main()   2.   3.     unsigned char index = 0;  

72、 4.     unsigned short to_xor;   5.     int i;   6.   7.     printf("unsigned short crc16_ccitt_table256 =n");   8.     while (1)&

73、#160;   9.        10.         if (!(index % 8)   11.             printf("n");   12.      &

74、#160;     13.         to_xor = index;          14.         for (i = 0; i < 8; i+)    15.

75、60;           16.             if (to_xor & 0x0001)   17.                 to_xor&#

76、160;= (to_xor >> 1)  0x8408;   18.             else    19.                 to_xor >>= 1;

77、              20.                        21.         printf("0x%04x", 

78、to_xor);   22.            23.         if (index = 255)   24.            25.         &

79、#160;   printf("n");   26.             break;   27.            28.         else  29.  

80、0;         30.             printf(", ");   31.             index+;   32.      &#

81、160;     33.        34.     printf("");   35.     return 0;   36.   37.   38. 生成的表如下：   39.   40. unsigned short crc16_ccitt_

82、table256 =   41.   42. 0x0000, 0x1189, 0x2312, 0x329b, 0x4624, 0x57ad, 0x6536, 0x74bf,   43. 0x8c48, 0x9dc1, 0xaf5a, 0xbed3, 0xca6c, 0xdbe5, 0xe97e, 0xf8f7,   44. 0x1081, 0x0108,&#

83、160;0x3393, 0x221a, 0x56a5, 0x472c, 0x75b7, 0x643e,   45. 0x9cc9, 0x8d40, 0xbfdb, 0xae52, 0xdaed, 0xcb64, 0xf9ff, 0xe876,   46. 0x2102, 0x308b, 0x0210, 0x1399, 0x6726, 0x76af, 0x4434, 0

84、x55bd,   47. 0xad4a, 0xbcc3, 0x8e58, 0x9fd1, 0xeb6e, 0xfae7, 0xc87c, 0xd9f5,   48. 0x3183, 0x200a, 0x1291, 0x0318, 0x77a7, 0x662e, 0x54b5, 0x453c,   49. 0xbdcb, 0xac42, 0x9ed9, 0x8f50,&

85、#160;0xfbef, 0xea66, 0xd8fd, 0xc974,   50. 0x4204, 0x538d, 0x6116, 0x709f, 0x0420, 0x15a9, 0x2732, 0x36bb,   51. 0xce4c, 0xdfc5, 0xed5e, 0xfcd7, 0x8868, 0x99e1, 0xab7a, 0xbaf3,   52. 0x

86、5285, 0x430c, 0x7197, 0x601e, 0x14a1, 0x0528, 0x37b3, 0x263a,   53. 0xdecd, 0xcf44, 0xfddf, 0xec56, 0x98e9, 0x8960, 0xbbfb, 0xaa72,   54. 0x6306, 0x728f, 0x4014, 0x519d, 0x2522, 0x34ab,

87、 0x0630, 0x17b9,   55. 0xef4e, 0xfec7, 0xcc5c, 0xddd5, 0xa96a, 0xb8e3, 0x8a78, 0x9bf1,   56. 0x7387, 0x620e, 0x5095, 0x411c, 0x35a3, 0x242a, 0x16b1, 0x0738,   57. 0xffcf, 0xee46, 0

88、xdcdd, 0xcd54, 0xb9eb, 0xa862, 0x9af9, 0x8b70,   58. 0x8408, 0x9581, 0xa71a, 0xb693, 0xc22c, 0xd3a5, 0xe13e, 0xf0b7,   59. 0x0840, 0x19c9, 0x2b52, 0x3adb, 0x4e64, 0x5fed, 0x6d76, 0x7cff

89、,   60. 0x9489, 0x8500, 0xb79b, 0xa612, 0xd2ad, 0xc324, 0xf1bf, 0xe036,   61. 0x18c1, 0x0948, 0x3bd3, 0x2a5a, 0x5ee5, 0x4f6c, 0x7df7, 0x6c7e,   62. 0xa50a, 0xb483, 0x8618, 0x9791, 

90、0xe32e, 0xf2a7, 0xc03c, 0xd1b5,   63. 0x2942, 0x38cb, 0x0a50, 0x1bd9, 0x6f66, 0x7eef, 0x4c74, 0x5dfd,   64. 0xb58b, 0xa402, 0x9699, 0x8710, 0xf3af, 0xe226, 0xd0bd, 0xc134,   65. 0x39c3,

91、 0x284a, 0x1ad1, 0x0b58, 0x7fe7, 0x6e6e, 0x5cf5, 0x4d7c,   66. 0xc60c, 0xd785, 0xe51e, 0xf497, 0x8028, 0x91a1, 0xa33a, 0xb2b3,   67. 0x4a44, 0x5bcd, 0x6956, 0x78df, 0x0c60, 0x1de9, 

92、;0x2f72, 0x3efb,   68. 0xd68d, 0xc704, 0xf59f, 0xe416, 0x90a9, 0x8120, 0xb3bb, 0xa232,   69. 0x5ac5, 0x4b4c, 0x79d7, 0x685e, 0x1ce1, 0x0d68, 0x3ff3, 0x2e7a,   70. 0xe70e, 0xf687, 0xc41c

93、, 0xd595, 0xa12a, 0xb0a3, 0x8238, 0x93b1,   71. 0x6b46, 0x7acf, 0x4854, 0x59dd, 0x2d62, 0x3ceb, 0x0e70, 0x1ff9,   72. 0xf78f, 0xe606, 0xd49d, 0xc514, 0xb1ab, 0xa022, 0x92b9, 0x8330,

94、60; 73. 0x7bc7, 0x6a4e, 0x58d5, 0x495c, 0x3de3, 0x2c6a, 0x1ef1, 0x0f78  74. ;  int main() unsigned char index = 0; unsigned short to_xor; int i; printf("unsigned short crc16_ccitt_table256 =n"); while (1) if (!(index % 8) printf(&

95、quot;n"); to_xor = index; for (i = 0; i < 8; i+) if (to_xor & 0x0001) to_xor = (to_xor >> 1) 0x8408; else to_xor >>= 1; printf("0x%04x", to_xor); if (index = 255) printf("n"); break; else printf(", "); index+; printf(""); return 0;生成的表如

96、下：unsigned short crc16_ccitt_table256 =0x0000, 0x1189, 0x2312, 0x329b, 0x4624, 0x57ad, 0x6536, 0x74bf,0x8c48, 0x9dc1, 0xaf5a, 0xbed3, 0xca6c, 0xdbe5, 0xe97e, 0xf8f7,0x1081, 0x0108, 0x3393, 0x221a, 0x56a5, 0x472c, 0x75b7, 0x643e,0x9cc9, 0x8d40, 0xbfdb, 0xae52, 0xdaed, 0xcb64, 0xf9ff, 0xe876,0x2102, 0

97、x308b, 0x0210, 0x1399, 0x6726, 0x76af, 0x4434, 0x55bd,0xad4a, 0xbcc3, 0x8e58, 0x9fd1, 0xeb6e, 0xfae7, 0xc87c, 0xd9f5,0x3183, 0x200a, 0x1291, 0x0318, 0x77a7, 0x662e, 0x54b5, 0x453c,0xbdcb, 0xac42, 0x9ed9, 0x8f50, 0xfbef, 0xea66, 0xd8fd, 0xc974,0x4204, 0x538d, 0x6116, 0x709f, 0x0420, 0x15a9, 0x2732, 0

98、x36bb,0xce4c, 0xdfc5, 0xed5e, 0xfcd7, 0x8868, 0x99e1, 0xab7a, 0xbaf3,0x5285, 0x430c, 0x7197, 0x601e, 0x14a1, 0x0528, 0x37b3, 0x263a,0xdecd, 0xcf44, 0xfddf, 0xec56, 0x98e9, 0x8960, 0xbbfb, 0xaa72,0x6306, 0x728f, 0x4014, 0x519d, 0x2522, 0x34ab, 0x0630, 0x17b9,0xef4e, 0xfec7, 0xcc5c, 0xddd5, 0xa96a, 0x

99、b8e3, 0x8a78, 0x9bf1,0x7387, 0x620e, 0x5095, 0x411c, 0x35a3, 0x242a, 0x16b1, 0x0738,0xffcf, 0xee46, 0xdcdd, 0xcd54, 0xb9eb, 0xa862, 0x9af9, 0x8b70,0x8408, 0x9581, 0xa71a, 0xb693, 0xc22c, 0xd3a5, 0xe13e, 0xf0b7,0x0840, 0x19c9, 0x2b52, 0x3adb, 0x4e64, 0x5fed, 0x6d76, 0x7cff,0x9489, 0x8500, 0xb79b, 0xa

100、612, 0xd2ad, 0xc324, 0xf1bf, 0xe036,0x18c1, 0x0948, 0x3bd3, 0x2a5a, 0x5ee5, 0x4f6c, 0x7df7, 0x6c7e,0xa50a, 0xb483, 0x8618, 0x9791, 0xe32e, 0xf2a7, 0xc03c, 0xd1b5,0x2942, 0x38cb, 0x0a50, 0x1bd9, 0x6f66, 0x7eef, 0x4c74, 0x5dfd,0xb58b, 0xa402, 0x9699, 0x8710, 0xf3af, 0xe226, 0xd0bd, 0xc134,0x39c3, 0x28

101、4a, 0x1ad1, 0x0b58, 0x7fe7, 0x6e6e, 0x5cf5, 0x4d7c,0xc60c, 0xd785, 0xe51e, 0xf497, 0x8028, 0x91a1, 0xa33a, 0xb2b3,0x4a44, 0x5bcd, 0x6956, 0x78df, 0x0c60, 0x1de9, 0x2f72, 0x3efb,0xd68d, 0xc704, 0xf59f, 0xe416, 0x90a9, 0x8120, 0xb3bb, 0xa232,0x5ac5, 0x4b4c, 0x79d7, 0x685e, 0x1ce1, 0x0d68, 0x3ff3, 0x2e7a,0xe70e, 0xf687, 0xc41c, 0xd595, 0xa12a, 0xb0a3, 0x8238, 0x93b1,0x6b46, 0x7acf, 0x4854, 0x59dd, 0x2d62, 0x3ceb, 0x0e70, 0x1ff9,0xf78f, 0xe606, 0xd49d, 0xc514, 0xb1ab, 0xa022, 0x92b9, 0x8330,0x7bc7, 0x6a4e, 0x58d5, 0x495c, 0x3de3, 0x2c6a, 0x1ef1, 0x0f78;這樣對(duì)于消息unsi