1、16位CR或驗原理與算法分析2007-12-14 09:37只是針對以下的生成這里，不討論CRC勺糾錯原理以及為什么要選下面提及的生成多項式, 多項式，如何獲得 CRO驗碼，作一個比較詳細的說明。CRC16-CCITT x16+x12+x5+1V.34/V.41/V.42, PPP-FCS1021 ISO HDLC, ITU X.25,名稱生成多項式簡記式*CRC-4x4+x+13ITU G.704CRC-8x8+x5+x4+10x31CRC-8x8+x2+x1+10x07CRC-8x8+x6+x4+x3+x2+x10x5ECRC-12x12+x11+x3+x+180FCRC-16x16+x1

2、5+x2+18005 IBM SDLC標準CRCfc成多項式如下表：標準引用CRC-32 x32+x26+x23+.+x2+x+1 04C11DB7 ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCSCRC-32c x32+x28+x27+.+x8+x6+1 1EDC6F41 SCTP生成多項式的最高位固定的1，故在簡記式中忽略最高位1 了，如0x1021實際是0x11021。I、基本算法（人工筆算）：以CRC16-CCITT為例進行說明，CR或驗碼為16位，生成多項式17位。假如數(shù)據(jù)流為4字節(jié)：BYTE3、BYTE2、BYTE1、BYTE0;數(shù)據(jù)流

3、左移16位，相當于擴大256X 256倍，再除以生成多項式 0x11021 ,做不借位的除法 運算（相當于按位異或），所得的余數(shù)就是CRC驗碼。發(fā)送時的數(shù)據(jù)流為 6 字節(jié)：BYTE3、BYTE2、BYTE1、BYTE0、CRC1、CRC0;II、計算機算法1 （比特型算法）：1）將擴大后的數(shù)據(jù)流 （6字節(jié)）高16位（BYTE3、BYTE2）放入一個長度為16的寄存器；2）如果寄存器的首位為1,將寄存器左移1位（寄存器的最低位從下一個字節(jié)獲得），再與生成多項式的簡記式異或；否則僅將寄存器左移1位（寄存器的最低位從下一個字節(jié)獲得）；3）重復第2步，直到數(shù)據(jù)流（6字節(jié)）全部移入寄存器；4）寄存器中的

4、值則為 CRC交驗碼CRC1、CRC0。III、計算機算法2 （字節(jié)型算法）：256An表示256的n次方把按字節(jié)排列的數(shù)據(jù)流表示成數(shù)學多項式，設(shè)數(shù)據(jù)流為BYTEnBYTEn 1BYTEn 2、BYTE1BYTE0,表示成數(shù)學表達式為BYTEn X 256An+BYTEn -1 X 256A（n -1）+.+BYTE1*256+BYTE0,在這里+表示為異或運算。設(shè)生成多項式為 G17 （17bit ） , CRC碼為CRC16則，CRC16=（BYTEn X256An+BYTEn -1 X 256A（n -1）+.+BY TE1 X 256+BYTE0） X 256人2/617,即數(shù)據(jù)流左移

5、16位，再除以生成多項式G17。先變換BYTEn-1、BYTEn-1擴大后的形式,CRC16 =BYTEnX 256AnX 256A2/G17+BYTEn -1 X 256A(n - 1) X 256A2/G17+.+BYTE1 X 256X256A2/G17+BYTE0X 256A2/G17 (Zn+Yn/G17) X 256An+BYTEn -1 X 256A(n - 1) X 256A2/G17+.+BYTE1 ><256><256人2/G17+BYTE0X 256A2/G17 =Zn X256An+丫n X 256/G17+BYTEn -1 X 256A2/G1

6、7 X 256A(n - 1)+.+BYTE1 X 256X2 56A2/G17+BYTE0X 256A2/G17Zn X256An+(YH8n X 256+YHLn) X 256/G17+BYTEn -1 X 256人2/617 X 256A(n -1)+. +BYTE1 256 256A2/G17+BYTE0 256A2/G17Zn 256An+YHLn 256/G17+（YH8n+BYTEn - 1）256A2/G17 256A（n -1）+.+BYTE1256 256A2/G17+BYTE0 256A2/G17這樣就推導出，BYTEn-1字節(jié)的CRC驗碼為YHLn X256/G17+（

7、YH8n+BYTEn -1） X256A2/G17,即上一字節(jié) CR或驗碼 Yn的高 8位（YH8n）與本字節(jié) BYTEn-1異或，該結(jié)果單獨計算 CRO驗碼（即單字節(jié)的 16位CRO驗碼，對單字節(jié)可建立表格，預先生 成對應的16位CR儂驗碼），所得的CR俄驗碼與上一字節(jié) CR俄驗碼Yn的低8位（YL8n）乘以256 （即左移8位）異或。然后依次逐個字節(jié)求出CRC直到BYTE0。字節(jié)型算法的一般描述為：本字節(jié)的CRM,等于上一字節(jié) CRM的低8位左移8位，與上一字節(jié)CRC移8位同本字節(jié)異或后所得的CR刎異或。字節(jié)型算法如下：1）CRC 寄存器組初始化為全"0"（0x0000

8、）。（注意：CRCW存器組初始化全為1時，最后CRCZ取反。）2）CRC 寄存器組向左移 8位，并保存到CRCW存器組。3）原CRCW存器組高8位（右移8位）與數(shù)據(jù)字節(jié)進行異或運算，得出一個指向值表的索引。4）索引所指的表值與 CRCW存器組做異或運算。5）數(shù)據(jù)指針加1,如果數(shù)據(jù)沒有全部處理完，則重復步驟2）。6） 得出CRCunsigned short GetCrc_16(unsigned char * pData, int nLength)/函數(shù)功能：計算數(shù)據(jù)流* pData的16位CRC驗碼，數(shù)據(jù)流長度為nLengthunsigned short cRc_16 = 0x0000; /初始

9、化while(nLength>0)cRc_16 = (cRc_16 << 8) a cRctable_16(cRc_16>>8) a *pData) & 0xff;/cRctable_16 表由函數(shù) mK_cRctable 生成nLength-;pData+;)return cRc_16;) void mK_cRctable（unsigned short gEnpoly）/函數(shù)功能：生成 0 255對應的16CRCK驗碼，其實就是計算機算法1 （比特型算法）/gEnpoly 為生成多項式/注意，低位先傳送時，生成多項式應反轉(zhuǎn)（低位與高位互換）。如CRC16

10、-CCITT為0x1021,反轉(zhuǎn)后為0x8408unsigned short cRc_16=0;unsigned short i,j,k;for(i=0,k=0;i<256;i+,k+)cRc_16 = i<<8;for(j=8;j>0;j-)反轉(zhuǎn)時 cRc_16&0x0001反轉(zhuǎn)時 cRc_16=(cRc_16>>=1)AgEnpoly反轉(zhuǎn)時 cRc_16>>=1if(cRc_16&0x8000)/cRc_16=(cRc_16<<=1)AgEnpoly; /elsecRc_16<<=1;/)cRctabl

11、e_16k = cRc_16;)CRC(Cyclic Redundancy Check/ 循環(huán)冗余校驗)它是利用除法及余數(shù)的原理來作錯誤偵測(Error Detecting )的。實際應用時，發(fā)送裝置計算出CRC直并隨數(shù)據(jù)一同發(fā)送給接收裝置，接收裝置對收到的數(shù)據(jù)重新計算CRS與收到的CRCf比較，若兩個 CRC直不同，則說明數(shù)據(jù)通訊出現(xiàn)錯誤。根據(jù)應用環(huán)境與習慣的不同，CRCX可分為以下幾種標準：CRC12碼；CRC16碼；CRCCCITT 碼；CRC32碼。CRC-12碼通常用來傳送 6-bit字符串。CRC-16及CRC-CCITTM則用是來傳送 8-bit字符，其中CRC-16為美國采用，

12、而CRC-CCITT 為歐洲國家所采用。CRC-32碼大都被采用在一種稱為 Point-to-Point 的同步傳輸中。下面為CRC十算過程：1 .設(shè)置CRCW存器，并給其賦值 FFFF(hex)。2 .將數(shù)據(jù)的 第一個8-bit字符與16位CRCW存器的低8位進行異或，并把結(jié)果存入 CRCW存器。3 . CRCW存器向右移一位，MS外卜零，移出并檢查 LSR4 .如果LSB為0,重復第三步；若 LSB為1, CRCW存器與多項式碼相異或。5 .重復第3與第4步直到8次移位全部完成。此時一個 8-bit數(shù)據(jù)處理完畢。6 .重復第2至第5步直到所有數(shù)據(jù)全部處理完成。7 .最終CRCW存器的內(nèi)容即

13、為 CRC直。常用的CRC1環(huán)冗余校驗標準多項式如下：CRC(16位)=X16+X15+X2+1CRC(CCITT) = X16+X12 +X5+1CRC(32 位)=X32+X26+X23+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1 以CRC(16位)多項式為例，其對應校驗二進制位列為1 1000 0000 0000 0101 。CRCg本原理是：在K位信息碼后再拼接 R位的校驗碼，整個編碼長度為N位，因此，這種編碼又叫(N,K)碼。對于一個給定的(N,K)碼，可以證明存在一個最高次哥為N-K=R的多項式G(x),根據(jù)G(x)可以生成K位信息的校驗碼，而 G(x)叫

14、做這個CR加的生成多項 式。 校驗碼的具體生成過程為：假設(shè)發(fā)送信息用信息多項式C(X)表示，將C(x)左移R位，則可表示成C(x)*2R ,這樣C(x)的右邊就會空出 R位，這就是校驗碼的位置。通過C(x)*2R除以生成多項式G(x)得到的余數(shù)就是校驗碼。幾個基本概念1、多項式與二進制數(shù)碼多項式和二進制數(shù)有直接對應關(guān)系：x的最高哥次對應二進制數(shù)的最高位，以下各位對應多項式的各哥次，有此哥次項對應1,無此哥次項對應 0?？梢钥闯觯簒的最高哥次為R, 轉(zhuǎn)換成對應的二進制數(shù)有 R+1位。多項式包括生成多項式G(x)和信息多項式C(x)。如生成多項式為 G(x)=x4+x3+x+1 ,可轉(zhuǎn)換為二進制數(shù)

15、碼 11011。而發(fā)送信息位1111 ,可轉(zhuǎn)換為數(shù)據(jù)多項式為C(x)=x3+x2+x+1。2、生成多項式是接受方和發(fā)送方的一個約定，也就是一個二進制數(shù)，在整個傳輸過程中，這個數(shù)始終保持不變。在發(fā)送方，利用生成多項式對信息多項式做模2除生成校驗碼。在接受方利用生成多項式對收到的編碼多項式做模2除檢測和確定錯誤位置。應滿足以下條件:a、生成多項式的最高位和最低位必須為1。b、當被傳送信息(CRM)任何一位發(fā)生錯誤時，被生成多項式做模2除后應該使余數(shù)不為0。c、不同位發(fā)生錯誤時，應該使余數(shù)不同。但可以從有關(guān)資料查到常用的對應于不同碼d、對余數(shù)繼續(xù)做模 2除，應使余數(shù)循環(huán)。 將這些要求反映為數(shù)學關(guān)系是

16、比較復雜的。N7777K碼距dx3+x+1x3+x2+1x4+x3+x2+1x4+x2+x+1G(x)多項式10111101111011011144333344151115375x4+x+1x8+x7+x6+x4+110011111010001制的生成多項式如圖 9所示:G(x)31263x5+x2+110010131215x10+x9+x8+x6+x5+x3+1 1110110100163573x6+x+1100001163515x12+x10+x5+x4+x2+1101000011010110411024x16+x15+x2+1110000000000001013、模2除(按位除)模2除做

17、法與算術(shù)除法類似，但每一位除(減)的結(jié)果不影響其它位，即不向上一位借位。所以實際上就是異或。然后再移位移位做下一位的模2減。步驟如下：a、用除數(shù)對被除數(shù)最高幾位做模2減，沒有借位。b、除數(shù)右移一位，若余數(shù)最高位為1,商為1,并對余數(shù)做模2減。若余數(shù)最高位為0, 商為0,除數(shù)繼續(xù)右移一位。c、一直做到余數(shù)的位數(shù)小于除數(shù)時，該余數(shù)就是最終余數(shù)。CR或驗程序編寫：編寫CRCK驗程序有兩種辦法： 一種為計算法，一種為查表法。下面對兩種方法分別討 論。計算法計算法就是依據(jù) CRO驗碼的產(chǎn)生原理來設(shè)計程序。 其優(yōu)點是模塊代碼少，修改靈活，可移 植性好。其缺點為計算量大。為了便于理解，這里假定了三位數(shù)據(jù)，而

18、多項式碼為 A001(hex)。 在窗體上放置一命令按鈕 Commandl并添加如下代碼：Private Sub Command1_Click()Dim CRC() As ByteDim d() As Byte '待傳輸數(shù)據(jù)ReDim d(2) As Byted(0) = 123d(1) = 112d(2) = 135CRC = CRC16(d)' 調(diào)用CRC1附算函數(shù) 'CRC(0) 為高位 'CRC(1) 為低位End SubCRC勺低位可能在前，而高位在后。Function CRC16(data() As Byte) As String Dim CRC16

19、Lo As Byte, CRC16Hi As Byte Dim CL As Byte, CH As Byte'Dim SaveHi As Byte, SaveLo As Byte Dim i As Integer Dim Flag As Integer CRC16Lo = &HFF CRC16Hi = &HFFCL = &H1 多項式碼低位&H01CH = &HA0 多項式碼高位 &HA0For i = 0 To UBound(data)CRC16Lo = CRC16Lo Xor data(i)'For Flag = 0 To 7

20、SaveHi = CRC16Hi SaveLo = CRC16Lo CRC16Hi = CRC16Hi 2'CRC16Lo = CRC16Lo 2'If (SaveHi And &H1) = &H1) Then ' CRC16Lo = CRC16Lo Or &H80 End If'If (SaveLo And &H1) = &H1) Then 'CRC16Hi = CRC16Hi Xor CH CRC16Lo = CRC16Lo Xor CL End If Next Flag Next i Dim ReturnDa

21、ta(1) As ByteReturnData(0) = CRC16Hi'CRCReturnData(1) = CRC16Lo'CRC'CRC寄存器多項式碼&HA001每一個數(shù)據(jù)與CRCW存器進行異或高位右移一位低位右移一位如果高位字節(jié)最后一位為1則低位字節(jié)右移后前面補 1否則自動補0如果LSB為1,則與多項式碼進行異或高位低位注意：在數(shù)據(jù)傳輸時CRC16 = ReturnDataEnd Function查表法查表法的優(yōu)缺點與計算法的正好相反。為了便于比較，這里所有的假定與計算法的完全相同，都而在窗體上放置一個Command的按鈕，其代碼部分與上面的也完全一致。

22、下面只介紹CRC®數(shù)的編寫源代碼。Private Function CRC16(data() As Byte) As StringDim CRC16Hi As Byte Dim CRC16Lo As Byte CRC16Hi = &HFF CRC16Lo = &HFF Dim i As Integer Dim iIndex As Long For i = 0 To UBound(data) iIndex = CRC16Lo Xor data(i) CRC16Lo = CRC16Hi Xor GetCRCLo(iIndex) '低位處理CRC16Hi = Get

23、CRCHi(iIndex)'高位處理Next iDim ReturnData(1) As ByteReturnData(0) = CRC16Hi'CRC高位ReturnData(1) = CRC16Lo'CRC低位CRC16 = ReturnDataEnd Function'CRC低位字節(jié)值表Function GetCRCLo(Ind As Long) As ByteGetCRCLo= Choose(Ind + 1, &H0, &HC1, &H81, &H40, &H1, &HC0, &H80, &

24、H41, &H1, &HC0, &H80, &H41, &H0, &HC1, &H81, &H40, &H1, &HC0, &H80, &H41, &H0, &HC1, &H81, &H40, &H0, &HC1, &H81, &H40, &H1, &HC0, &H80, &H41, &H1, &HC0, &H80, &H41, &H0, &HC1, &am

25、p;H81, &H40, &H0, &HC1, &H81, &H40, &H1, &HC0, &H80, &H41, &H0, &HC1, &H81, &H40, &H1, &HC0, &H80, &H41, &H1, &HC0, &H80, &H41, &H0, &HC1, &H81, &H40, &H1, &HC0, &H80, &H41, &H0, &

26、amp;HC1, &H81, &H40, &H0, &HC1, &H81, &H40, &H1, &HC0, &H80, &H41, &H0, &HC1, &H81, &H40, &H1, &HC0, &H80, &H41, &H1, &HC0, &H80, &H41, &H0, &HC1, &H81, &H40, &H0, &HC1, &H81, &H40

27、, &H1, &HC0, &H80, &H41, &H1, &HC0, &H80, &H41, &H0, &HC1, &H81, &H40, &H1, &HC0, &H80, &H41, &H0, &HC1, &H81, &H40, &H0, &HC1, &H81, &H40, &H1, &HC0, &H80, &H41, &H1, &HC0, _ &

28、;H80, &H41, &H0, &HC1, &H81, &H40, &H0, &HC1, &H81, &H40, &H1, &HC0, &H80, &H41, &H0, &HC1, &H81, &H40, &H1, &HC0, &H80, &H41, &H1, &HC0, &H80, &H41, &H0, &HC1, &H81, &H40, &H0, &a

29、mp;HC1, &H81, &H40, &H1, &HC0, &H80, &H41, &H1, &HC0, &H80, &H41, &H0, &HC1, &H81, &H40, &H1, &HC0, &H80, &H41, &H0, &HC1, &H81, &H40, &H0, &HC1, &H81, &H40, &H1, &HC0, &H80, &H41,

30、 &H0, &HC1, &H81, &H40, &H1, &HC0, &H80, &H41, &H1, &HC0, &H80, &H41, &H0, &HC1, &H81, &H40, &H1, &HC0, &H80, &H41, &H0, &HC1, &H81, &H40, &H0, &HC1, &H81, &H40, &H1, &HC0, &H8

31、0, &H41, &H1, &HC0, &H80, &H41, &H0, &HC1, &H81, &H40, &H0, &HC1, &H81, &H40, &H1, &HC0, &H80, &H41, &H0, &HC1, &H81, &H40, &H1, &HC0, &H80, &H41, &H1, &HC0, &H80, &H41, &H0, &

32、HC1, &H81, &H40)End Function'CRC高位字節(jié)值表Function GetCRCHi(Ind As Long) As ByteGetCRCHi = Choose(Ind + 1, &H0, &HC0, &HC1, &H1, &HC3, &H3, &H2, &HC2, &HC6, &H6, &H7, &HC7, &H5, &HC5, &HC4, &H4, &HCC, &HC, &HD, &

33、HCD, &HF, &HCF, &HCE, &HE, &HA, &HCA, &HCB, &HB, &HC9, &H9, &H8, &HC8, &HD8, &H18, &H19, &HD9, &H1B, &HDB, &HDA, &H1A, &H1E, &HDE,&HDF, &H1F, &HDD,&H1D, &H1C, &HDC, &H14, &HD4, &am

34、p;HD5, &H15, &HD7, &H17, &H16, &HD6, &HD2,&H12,&H13, &HD3,&H11, &HD1,&HD0, &H10,&HF0, &H30, &H31,&HF1, &H33, &HF3, &HF2,&H32,&H36, &HF6,&HF7, &H37,&HF5, &H35,&H34, &HF4, &H3C,&

35、HFC, &HFD, &H3D, &HFF,&H3F,&H3E, &HFE,&HFA, &H3A,&H3B, &HFB,&H39, &HF9, &HF8,&H38, &H28, &HE8, &HE9,&H29,&HEB, &H2B,&H2A, &HEA,&HEE, &H2E,&H2F, &HEF, &H2D,&HED, &HEC, &H2C, &HE4,&H24,&H25, &HE5,&H27, &HE7,&HE6, &H26,&H22, &HE2, &HE3,&H23, &HE1, &H21, &H20, &HE0, &HA0, &H60, _&H61,