CRC---循环冗余校验码

只看该作者 · 2015-12-16 20:07

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

只看该作者 · 2015-12-16 20:08

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

只看该作者 · 2015-12-16 20:08

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值。

只看该作者 · 2015-12-16 20:09

CRC码的生成步骤

　　1、将x的最高幂次为R的生成多项式G(x)转换成对应的R+1位二进制数。

　　2、将信息码左移R位，相当与对应的信息多项式C(x)*2R。

　　3、用生成多项式（二进制数）对信息码做模2除，得到R位的余数。

　　4、将余数拼到信息码左移后空出的位置，得到完整的CRC码。

只看该作者 · 2015-12-16 20:09

复制

#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));  

}

只看该作者 · 2015-12-16 20:10

复制

// 构造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];   

    }   

}

只看该作者 · 2015-12-16 20:10

复制

// 计算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;   

}