标题: CRC---循环冗余校验码 [打印本页]
作者: 51黑er    时间: 2015-11-2 14:41
标题: CRC---循环冗余校验码
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又可分为以下几种标准：

    　　①CRC-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   


  3. #include <STDIO.H>   
  4. #include <MATH.H>   
  5.   
  6. // POLY   
  7. //注意：因最高位一定为“1”，故略去

  9. #define cnCRC_64_H  0x42F0E1EB   
  10. #define cnCRC_64_L  0xA9EA3693   
  11. //CRC-64-ECMA-182 x64 + x62 + x57 + x55 + x54 + x53 + x52 + x47 + x46 + x45 +   
  12. //x40 + x39 + x38 + x37 + x35 + x33 + x32 + x31 + x29 + x27 + x24 + x23 + x22   
  13. //+ x21 + x19 + x17 + x13 + x12 + x10 + x9 + x7 + x4 + x + 1   
  14. //(as described in ECMA-182 p.63)  or 0xC96C5795D7870F42 (0x92D8AF2BAF0E1E85)   
  15.   
  16. unsigned long TableCRCHigh[256];     // CRC ±í for 64   
  17. unsigned long TableCRCLow[256];     // CRC ±í for 64   
  18.   
  19. void BuildTable64();    //建立CRC表  
  20. unsigned long* CRC_64( unsigned char * aData, unsigned long aSize );        //生成CRC  
  21. //unsigned char test[11] = {0x01,0x02,0x03,0xf8,0x05,0x60,0x9e,0xce,0x1e,0xcb,0xf3};  

  23. unsigned char test[5] = {'A','B','C','D','E'};  

  25. void main()  
  26. {  
  27.     unsigned int i;  
  28.   
  29.     unsigned long* crc64;       //CRC的结果   
  30.    
  31.     BuildTable64();     //creat table   
  32.   
  33.     for (i=0;i<256;i++)  
  34.     {  
  35.         printf("%x,%x\n", TableCRCHigh[i],TableCRCLow[i]);  
  36.     }  
  37.   
  38.     crc64 = CRC_64(test,11);        //creat CRC  value   
  39.   
  40.         printf("The CRC is:%x,%x\n", *crc64,*(crc64+1));  
  41. }  
  42.   
  43. // 构造64位CRC表   
  44. void BuildTable64()   
  45. {   
  46.     unsigned long i, j;   
  47.     unsigned long nData[2];   
  48.     unsigned long nAccum[2];   
  49.   
  50.     nData[0] = 0;  
  51.     nData[1] = 0;  
  52.   
  53.     for ( i = 0; i < 256; i++ )   
  54.     {   
  55.         nAccum[0] = 0;  
  56.         nAccum[1] = 0;  
  57.         nData[1] = i;  
  58.   
  59.         nData[0] = nData[1]<<24;  
  60.         nData[1]  = 0;  
  61.   
  62.         for ( j = 0; j < 8; j++ )   
  63.         {   
  64.             if ( (nData[0]^nAccum[0]) & 0x80000000 )   
  65.             {  
  66.                 nAccum[0] = ((nAccum[0]<<1) | ((nAccum[1]&0x80000000)>>31)) ^ cnCRC_64_H;  
  67.                 nAccum[1] = (nAccum[1]<<1) ^ cnCRC_64_L;  
  68.             }  
  69.             else   
  70.             {  
  71.                 nAccum[0] = (nAccum[0] << 1 ) | ((nAccum[1]&0x80000000)>>31);  
  72.                 nAccum[1] = nAccum[1] << 1;  
  73.             }  
  74.             nData[0] = (nData[0] << 1 ) | ((nData[1]&0x80000000)>>31);  
  75.             nData[1] = nData[1] << 1;      
  76.         }   
  77.   
  78.         TableCRCHigh[i] = nAccum[0];   
  79.         TableCRCLow[i]  = nAccum[1];   
  80.     }   
  81. }   
  82.   
  83. // 计算64位CRC值   
  84. unsigned long* CRC_64( unsigned char* aData, unsigned long aSize )   
  85. {   
  86.     unsigned long i;   
  87.     unsigned long nAccum[2];   
  88.     unsigned long temp;  
  89.     unsigned long index;  
  90.   
  91.     nAccum[0] = 0;  
  92.     nAccum[1] = 0;  
  93.   
  94.     for ( i = 0; i < aSize; i++ )   
  95.     {  
  96.         temp = nAccum[0];  
  97.         index = (temp >> 24) ^ *aData++;  
  98.   
  99.         nAccum[0] = ((nAccum[0] << 8 ) | ((nAccum[1]&0xff000000)>>24)) ^ TableCRCHigh[index];  
  100.         nAccum[1] = (nAccum[1] << 8) ^ TableCRCLow[index];  
  101.     }  
  102.   
  103.     return nAccum;   
  104. }
复制代码








欢迎光临 (http://www.51hei.com/bbs/) Powered by Discuz! X3.1