|
|
CRC---循環冗余校驗碼
CRC的基本原理
基本原理：在K位信息碼后再拼接R位的校驗碼，整個編碼長度為N位，因此，這種編碼又叫（N，K）碼。對于一個給定的（N，K）碼，可以證明存在一個最高次冪為N-K=R的多項式G(x)。根據G(x)可以生成K位信息的校驗碼，而G(x)叫做這個CRC碼的生成多項式。
校驗碼的具體生成過程為：假設發送信息用信息多項式C(X)表示，將C(x)左移R位，則可表示成C(x)*2R，這樣C(x)的右邊就會空出R位，這就是校驗碼的位置。通過C(x)*2R除以生成多項式G(x)得到的余數就是校驗碼。
CRC的標準
在國際標準中，根據生成多項式G(x)的不同，CRC又可分為以下幾種標準：
�、貱RC-12碼: G(x)=X12+X11+X3+X2+X+1
②CRC-16碼: G(x)=X16+X15+X2+1
③CRC-CCITT碼: G(x)=X16+X12+X5+1
④CRC-32碼: G(x)=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+X+1
CRC-12碼通常用來傳送6-bit字符串。CRC-16及CRC-CCITT碼則用是來傳送8-bit字符，其中CRC-16為美國采用，而CRC-CCITT為歐洲國家所采用。CRC-32碼大都被采用在一種稱為Point-to-Point的同步傳輸中。下面以最常用的CRC-16為例來說明其生成過程。
CRC-16碼由兩個字節構成，在開始時CRC寄存器的每一位都預置為1，然后把CRC寄存器與8-bit的數據進行異或，之后對CRC寄存器從高到低進行移位，在最高位（MSB）的位置補零，而最低位（LSB，移位后已經被移出CRC寄存器）如果為1，則把寄存器與預定義的多項式碼進行異或，否則如果LSB為零，則無需進行異或。重復上述的由高至低的移位8次，第一個8-bit數據處理完畢，用此時CRC寄存器的值與下一個8-bit數據異或并進行如前一個數據似的8次移位。所有的字符處理完成后CRC寄存器內的值即為最終的CRC值。
碼字長度為64bit的CRC編碼。常用的生成多項式有：
ISO 3309規定的 x^64 + x^4 + x^3 + x + 1；
ECMA規定的 x^64 + x^62 + x^57 + x^55 + x^54 + x^53 + x^52 + x^47 + x^46 + x^45 + x^40 + x^39 + x^38 + x^37 + x^35 + x^33 +x^32 + x^31 + x^29 + x^27 + x^24 + x^23 + x^22 + x^21 +x^19 + x^17 + x^13 + x^12 + x^10 + x^9 + x^7 + x^4 + x + 1
CRC的計算過程
1．設置CRC寄存器，并給其賦值FFFF(hex)。
2．將數據的第一個8-bit字符與16位CRC寄存器的低8位進行異或，并把結果存入CRC寄存器。
3．CRC寄存器向右移一位，MSB補零，移出并檢查LSB。
4．如果LSB為0，重復第三步；若LSB為1，CRC寄存器與多項式碼相異或。
5．重復第3與第4步直到8次移位全部完成。此時一個8-bit數據處理完畢。
6．重復第2至第5步直到所有數據全部處理完成。
7．最終CRC寄存器的內容即為CRC值。
CRC碼的生成步驟
1、將x的最高冪次為R的生成多項式G(x)轉換成對應的R+1位二進制數。
2、將信息碼左移R位，相當與對應的信息多項式C(x)*2R。
3、用生成多項式（二進制數）對信息碼做模2除，得到R位的余數。
4、將余數拼到信息碼左移后空出的位置，得到完整的CRC碼。
CRC64
- #include <STDIO.H>
- #include <MATH.H>
-
- // POLY
- //注意：因最高位一定為“1”，故略去
- #define cnCRC_64_H 0x42F0E1EB
- #define cnCRC_64_L 0xA9EA3693
- //CRC-64-ECMA-182 x64 + x62 + x57 + x55 + x54 + x53 + x52 + x47 + x46 + x45 +
- //x40 + x39 + x38 + x37 + x35 + x33 + x32 + x31 + x29 + x27 + x24 + x23 + x22
- //+ x21 + x19 + x17 + x13 + x12 + x10 + x9 + x7 + x4 + x + 1
- //(as described in ECMA-182 p.63) or 0xC96C5795D7870F42 (0x92D8AF2BAF0E1E85)
-
- unsigned long TableCRCHigh[256]; // CRC ±í for 64
- unsigned long TableCRCLow[256]; // CRC ±í for 64
-
- void BuildTable64(); //建立CRC表
- unsigned long* CRC_64( unsigned char * aData, unsigned long aSize ); //生成CRC
- //unsigned char test[11] = {0x01,0x02,0x03,0xf8,0x05,0x60,0x9e,0xce,0x1e,0xcb,0xf3};
-
- unsigned char test[5] = {'A','B','C','D','E'};
-
- void main()
- {
- unsigned int i;
-
- unsigned long* crc64; //CRC的結果
-
- BuildTable64(); //creat table
-
- for (i=0;i<256;i++)
- {
- printf("%x,%x\n", TableCRCHigh[i],TableCRCLow[i]);
- }
-
- crc64 = CRC_64(test,11); //creat CRC value
-
- printf("The CRC is:%x,%x\n", *crc64,*(crc64+1));
- }
-
- // 構造64位CRC表
- void BuildTable64()
- {
- unsigned long i, j;
- unsigned long nData[2];
- unsigned long nAccum[2];
-
- nData[0] = 0;
- nData[1] = 0;
-
- for ( i = 0; i < 256; i++ )
- {
- nAccum[0] = 0;
- nAccum[1] = 0;
- nData[1] = i;
-
- nData[0] = nData[1]<<24;
- nData[1] = 0;
-
- for ( j = 0; j < 8; j++ )
- {
- if ( (nData[0]^nAccum[0]) & 0x80000000 )
- {
- nAccum[0] = ((nAccum[0]<<1) | ((nAccum[1]&0x80000000)>>31)) ^ cnCRC_64_H;
- nAccum[1] = (nAccum[1]<<1) ^ cnCRC_64_L;
- }
- else
- {
- nAccum[0] = (nAccum[0] << 1 ) | ((nAccum[1]&0x80000000)>>31);
- nAccum[1] = nAccum[1] << 1;
- }
- nData[0] = (nData[0] << 1 ) | ((nData[1]&0x80000000)>>31);
- nData[1] = nData[1] << 1;
- }
-
- TableCRCHigh[i] = nAccum[0];
- TableCRCLow[i] = nAccum[1];
- }
- }
-
- // 計算64位CRC值
- unsigned long* CRC_64( unsigned char* aData, unsigned long aSize )
- {
- unsigned long i;
- unsigned long nAccum[2];
- unsigned long temp;
- unsigned long index;
-
- nAccum[0] = 0;
- nAccum[1] = 0;
-
- for ( i = 0; i < aSize; i++ )
- {
- temp = nAccum[0];
- index = (temp >> 24) ^ *aData++;
-
- nAccum[0] = ((nAccum[0] << 8 ) | ((nAccum[1]&0xff000000)>>24)) ^ TableCRCHigh[index];
- nAccum[1] = (nAccum[1] << 8) ^ TableCRCLow[index];
- }
-
- return nAccum;
- }
|
|
