CRC-16原理及通用的16位CRC校驗(yàn)算法代碼

1、CRC-1616CRC校驗(yàn)算法代碼 位循環(huán)冗余碼校驗(yàn)英名稱為CyclicalRedundancy Check，簡稱CRC。它是利除法及余數(shù)的原理來作錯(cuò)誤偵測（ErrorDetecting）的。實(shí)際應(yīng)時(shí)，發(fā)送裝置計(jì)算出CRC值并隨數(shù)據(jù)同發(fā)送給接收裝置，接收裝置對收到的數(shù)據(jù)重新計(jì)算CRC并與收到的CRC相較，若兩個(gè)CRC值不同，則說明數(shù)據(jù)通訊出現(xiàn)錯(cuò)誤。根據(jù)應(yīng)環(huán)境與習(xí)慣的不同，CRC常的些標(biāo)準(zhǔn)如下：CRC-4/ITUCRC-5/EPC CRC-5/ITU CRC-5/USBCRC-6/ITUCRC-7/MMCCRC-8 CRC-8/ITU CRC-8/ROHC CRC-8/MAXIMCRC-16/I

2、BM CRC-16/MAXIM CRC-16/USB CRC-16/MODBUS CRC-16/CCITT CRC-16/CCITT-FALSECRC-16/X25 CRC-16/XMODEM CRC-16/DNPCRC-32 CRC-32/MPEG-2等CRC-16及CRC-CCITT碼則是來傳送8-bit字符，其中CRC-16為美國采，CRC-CCITT為歐洲國家所采。CRC-32碼都被采在種稱為Point-to-Point的同步傳輸中。CRC-16碼由兩個(gè)字節(jié)構(gòu)成，在開始時(shí)CRC寄存器的每位都預(yù)置為1，然后把CRC寄存器與8-bit的數(shù)據(jù)進(jìn)異或，之后對CRC寄存器從到低進(jìn)移位，在最位（M

3、SB）的位置補(bǔ)零，最低位（LSB，移位后已經(jīng)被移出CRC寄存器）如果為1，則把寄存器與預(yù)定義的多項(xiàng)式碼進(jìn)異或，否則如果 LSB為零，則需進(jìn)異或。重復(fù)上述的由低的移位8次，第個(gè)8-bit數(shù)據(jù)處理完畢，此時(shí)CRC寄存器的值與下個(gè)8-bit數(shù)據(jù)異或并進(jìn)如前個(gè)數(shù)據(jù)似的8次移位。所有的字符處理完成后CRC寄存器內(nèi)的值即為最終的CRC值。任意個(gè)由進(jìn)制位串組成的代碼都可以和個(gè)系數(shù)僅為0和1取值的多項(xiàng)式對應(yīng)。例如：代碼1010111對應(yīng)的多項(xiàng)式為x6+x4+x2+x+1，多項(xiàng)式為x5+x3+x2+x+1對應(yīng)的代碼101111。常的CRC16-CCITT多項(xiàng)式為x16+x12+x5+1，0 x1021進(jìn)制為10

4、001000000100001。成多項(xiàng)式的最位固定的1，故在簡記式中忽略最位1了，如0 x1021實(shí)際是0 x11021。多項(xiàng)式需要滿：最位和最低位都是1當(dāng)被傳送信息任何位發(fā)錯(cuò)誤時(shí)，P(X)不被T(X)整除不同位發(fā)錯(cuò)誤時(shí)，余數(shù)應(yīng)該不同對余數(shù)繼續(xù)做模除法時(shí)，應(yīng)該使余數(shù)循環(huán)標(biāo)準(zhǔn)CRC成多項(xiàng)式見末附表。以CRC16-CCITT為例進(jìn)說明，CRC校驗(yàn)碼為16位，成多項(xiàng)式17位。假如數(shù)據(jù)流為4字節(jié)：BYTE3、BYTE2、BYTE1、BYTE0；數(shù)據(jù)流左移16位，相當(dāng)于擴(kuò)256256倍，再除以成多項(xiàng)式0 x11021，做不借位的除法運(yùn)算（相當(dāng)于按位異或），所得的余數(shù)就是CRC校驗(yàn)碼。發(fā)送時(shí)的數(shù)據(jù)流為6字

5、節(jié)：BYTE3、BYTE2、BYTE1、BYTE0、CRC1、CRC0； 1)將擴(kuò)后的數(shù)據(jù)流（6字節(jié)）16位（BYTE3、BYTE2）放個(gè)長度為16的寄存器；2)如果寄存器的位為1，將寄存器左移1位(寄存器的最低位從下個(gè)字節(jié)獲得)，再與成多項(xiàng)式的簡記式異或；否則僅將寄存器左移1位(寄存器的最低位從下個(gè)字節(jié)獲得)；3)重復(fù)第2步，直到數(shù)據(jù)流（6字節(jié)）全部移寄存器；4)寄存器中的值則為CRC校驗(yàn)碼CRC1、CRC0。 的把按字節(jié)排列的數(shù)據(jù)流表成數(shù)學(xué)多項(xiàng)式，設(shè)數(shù)據(jù)流為BYTEnBYTEn1BYTEn2、BYTE1BYTE0，表成數(shù)學(xué)表達(dá)式為BYTEn256n+BYTEn-1256(n-1)+.+BY

6、TE1*256+BYTE0，在這+表為異或運(yùn)算。設(shè)成多項(xiàng)式為G17（17bit），CRC碼為CRC16。則，CRC16(BYTEn256n+BYTEn-1256(n-1)+.+BYTE1256+BYTE0)2562/G17，即數(shù)據(jù)流左移16位，再除以成多項(xiàng)式G17。先變換BYTEn-1、BYTEn-1擴(kuò)后的形式，CRC16BYTEn256n2562/G17+BYTEn-1256(n-1)2562/G17+.+BYTE12562562/G17+BYTE02562/G17(Zn+Yn/G17)256n+BYTEn-1256(n-1)2562/G17+.+BYTE12562562/G17+BYTE0

7、2562/G17Zn256n+Yn256/G17+BYTEn-12562/G17256(n-1)+.+BYTE12562562/G17+BYTE02562/G17Zn256n+(YH8n256+YHLn)256/G17+BYTEn-12562/G17256(n-1)+.+BYTE12562562/G17+BYTE02562/G17Zn256n+YHLn256/G17+(YH8n+BYTEn-1)2562/G17256(n-1)+.+BYTE12562562/G17+BYTE02562/G17這樣就推導(dǎo)出，BYTEn-1字節(jié)的CRC校驗(yàn)碼為YHLn256/G17+(YH8n+BYTEn-1)25

8、62/G17，即上字節(jié)CRC校驗(yàn)碼Yn的8位（YH8n）與本字節(jié)BYTEn-1異或，該結(jié)果單獨(dú)計(jì)算CRC校驗(yàn)碼（即單字節(jié)的16位CRC校驗(yàn)碼，對單字節(jié)可建表格，預(yù)先成對應(yīng)的16位CRC校驗(yàn)碼），所得的CRC校驗(yàn)碼與上字節(jié)CRC校驗(yàn)碼Yn的低8位（YL8n）乘以256（即左移8位）異或。然后依次逐個(gè)字節(jié)求出CRC，直到BYTE0。字節(jié)型算法的般描述為：本字節(jié)的CRC碼，等于上字節(jié)CRC碼的低8位左移8位，與上字節(jié)CRC右移8位同本字節(jié)異或后所得的CRC碼異或。字節(jié)型算法過程如下：1)CRC寄存器組初始化為全0(0 x0000)。（注意：CRC寄存器組初始化全為1時(shí)，最后CRC應(yīng)取反。）2)CRC

9、寄存器組向左移8位,并保存到CRC寄存器組。3)原CRC寄存器組8位（右移8位）與數(shù)據(jù)字節(jié)進(jìn)異或運(yùn)算，得出個(gè)指向值表的索引。4)索引所指的表值與CRC寄存器組做異或運(yùn)算。5)數(shù)據(jù)指針加1，如果數(shù)據(jù)沒有全部處理完，則重復(fù)步驟2)。6)得出CRC。查表算法代碼例：/*CRC16 Coding & Decoding G(X) = X16+X12+X5+1*/quint16 CRC_Calculate:CRC16_cal(quint8 *ptr, quint32 len, quint16 crc_init)crc = crc_init;temp=(crc8)&0 xff;oldcrc16=crc16_

10、tab*ptrtemp;crc=(crc8)oldcrc16;ptr+;return(crc); 位CRC16標(biāo)準(zhǔn)算法很多，般不同多項(xiàng)式對應(yīng)不同表，不同的算法有不同的函數(shù)，這樣不太便，下給出個(gè)通函數(shù)quint16 CRC_Normal:calculate_crc16(quint16 wCRCin,quint16 wCPoly,quint16 wResultXOR,bool input_invert,bool ouput_invert,const char *puchMsg, int usDatawChar|=0 x01=1;wCRCin = (wCRCin 1) wCPoly;elseif(o

11、uput_invert)quint16 temp_short = wCRCin;wCRCin=0;for(int i=0;i16;+i)if(temp_short&0 x01)wCRCin|=0 x01=1;return (wCRCinwResultXOR);CRC-16/CCITT由本函數(shù)實(shí)現(xiàn)則填充參數(shù)如下：calculate_crc(0,0 x1021,0,true,true,puchMsg,usDataLen)其它使情況參數(shù)參考下表如計(jì)算CRC-16/MODBUS：calculate_crc(0 xffff,0 x8005,0,true,true,puchMsg,usDataLen)ca

12、lculate_crc(0,0 x1021,0,false,false,puchMsg,usDataLen)結(jié)果異或值輸反轉(zhuǎn)輸出反轉(zhuǎn)CRC算法名稱多項(xiàng)式公式寬度多項(xiàng)式初始值CRC-4/ITUCRC-5/EPCx4 + x + 145030900090000truetruex5 + x3 + 1falsefalse5150000truetruetruefalsefalsefalsetruetruetruetruetruetruetruefalsetruefalsetruetruetruefalsefalsefalsetruetruetruetruetruetruetruefalsetruefalse5051F1F6030000709000080700008070055807FF00831000016161616161616168005800580058005102110211021102100000000FFFFFFFF0000FFFFFFFF00000000FFFFFFFF000000000000FFFF0000 x16 + x13 + x12 + x11 + x10 + x8 + x6 +x5 + x2 + 116323D650000FFFFtr