CRC-16原理及通用的16位CRC校驗算法代碼

1、CRC-1616CRC校驗算法代碼 位循環(huán)冗余碼校驗英名稱為CyclicalRedundancy Check，簡稱CRC。它是利除法及余數(shù)的原理來作錯誤偵測（ErrorDetecting）的。實際應(yīng)時，發(fā)送裝置計算出CRC值并隨數(shù)據(jù)同發(fā)送給接收裝置，接收裝置對收到的數(shù)據(jù)重新計算CRC并與收到的CRC相較，若兩個CRC值不同，則說明數(shù)據(jù)通訊出現(xiàn)錯誤。根據(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碼由兩個字節(jié)構(gòu)成，在開始時CRC寄存器的每位都預(yù)置為1，然后把CRC寄存器與8-bit的數(shù)據(jù)進異或，之后對CRC寄存器從到低進移位，在最位（M

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

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

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

6、TE1*256+BYTE0，在這+表為異或運算。設(shè)成多項式為G17（17bit），CRC碼為CRC16。則，CRC16(BYTEn256n+BYTEn-1256(n-1)+.+BYTE1256+BYTE0)2562/G17，即數(shù)據(jù)流左移16位，再除以成多項式G17。先變換BYTEn-1、BYTEn-1擴后的形式，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校驗碼為YHLn256/G17+(YH8n+BYTEn-1)25

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

9、寄存器組向左移8位,并保存到CRC寄存器組。3)原CRC寄存器組8位（右移8位）與數(shù)據(jù)字節(jié)進異或運算，得出個指向值表的索引。4)索引所指的表值與CRC寄存器組做異或運算。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)算法很多，般不同多項式對應(yīng)不同表，不同的算法有不同的函數(shù)，這樣不太便，下給出個通函數(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ù)實現(xiàn)則填充參數(shù)如下：calculate_crc(0,0 x1021,0,true,true,puchMsg,usDataLen)其它使情況參數(shù)參考下表如計算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算法名稱多項式公式寬度多項式初始值CRC-4/ITUCRC-5/EPCx4 + x + 145030900090000truetruex5 + x3 + 1falsefalse5150000truetruetruefalsefalsefalsetruetruetruetruetruetruetruefalsetruefalsetruetruetruefalsefalsefalsetruetruetruetruetruetruetruefalsetruefalse5051F1F6030000709000080700008070055807FF00831000016161616161616168005800580058005102110211021102100000000FFFFFFFF0000FFFFFFFF00000000FFFFFFFF000000000000FFFF0000 x16 + x13 + x12 + x11 + x10 + x8 + x6 +x5 + x2 + 116323D650000FFFFtr