CRC校验原理

2、生成CRC码的基本原理：任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。例如：代码1010111对应的多项式为x6+x4+x2+x+1，而多项式为x5+x3+x2+x+1对应的代码101111。

3、CRC码集选择的原则：若设码字长度为N，信息字段为K位，校验字段为R位(N=K+R)，则对于CRC码集中的任一码字，存在且仅存在一个R次多项式g(x)，使得

                                                        V(x)=A(x)g(x)=xRm(x)+r(x);

其中:    m(x)为K次信息多项式， r(x)为R-1次校验多项式，

            g(x)称为生成多项式：

                                         g(x)=g0+g1x+ g2x2+...+g(R-1)x(R-1)+gRxR

发送方通过指定的g(x)产生CRC码字，接收方则通过该g(x)来验证收到的CRC码字。

4、CRC校验码软件生成方法：

      借助于多项式除法，其余数为校验字段。

      例如：信息字段代码为: 1011001；对应m(x)=x6+x4+x3+1

      假设生成多项式为：g(x)=x4+x3+1；则对应g(x)的代码为: 11001

      x4m(x)=x10+x8+x7+x4 对应的代码记为：10110010000；

      采用多项式除法: 得余数为: 1010     (即校验字段为：1010）

发送方：发出的传输字段为: 1 0 1 1 0 0 1    1 0 10

                                               信息字段       校验字段

看一下下面的生成码、解码的过程：发送的数据为“12”这是字符对应的16进制为3132H

接收方：使用相同的生成码进行校验:接收到的字段/生成码（二进制除法)如果能够除尽，则正确)。

下面的这个程序就是获取一块数据(以字节为单位)的CRC校验码，将所有的数据视作连接在一起的0、1，当然实际存储也是这样，我们计算是从第一个字节的第7位到最后一个字节的第0位。如何理解这一长串的0、1对生成码的除法是用程序实现的关键。这里的加减为异或，这一串0、1是左移16位的数据，所以，一直算到序列的最后一位也是可以被除的。除法思想借鉴如下：

当按位计算CRC时，例如计算二进制序列为1001 1010 1010 1111时，将二进制序列数左移16位，即为1001 1010 1010 1111 (0000 0000 0000 0000)，实际上该二进制序列可拆分为1000 0000 0000 0000 (0000 0000 0000 0000) + 000 0000 0000 0000 (0000 0000 0000 0000) + 00 0000 0000 0000 (0000 0000 0000 0000) + 1 0000 0000 0000 (0000 0000 0000 0000) + …… 现在开始分析运算： <1>对第一个二进制分序列求余数，竖式除法即为0x10000 ^ 0x11021运算，后面的0位保留； <2>接着对第二个二进制分序列求余数，将第一步运算的余数*2后再和第二个二进制分序列一起对0x11021求余，这一步理解应该没什么问题。如果该分序列为0，无需计算。在按个10进制的数说明一下例如54321除以10，我们可以50000%10*10+4000%10*10+300%10*10........注意我们只是为了说明上面的思想，这里的加为异或。

uint cal_crc(uchar *ptr, uchar len) { //len为数据的字节长度

    unsigned long temp = 0; 

     unsigned int crc; 

    unsigned char i; 

     unsigned char *ptr = test; //存放数据块

    while( len-- ) 

       { 

         for(i = 0x80; i != 0; i = i >> 1)

           { 

              temp = temp * 2;//上一次的余数乘以2

              if((temp & 0x10000) != 0)//做高位为1即可除

               { 

                  temp = temp ^ 0x11021; 

               } 

             if((*ptr & i) != 0) //如果字节数据的一位为1，和上一次的余数一起除以生成码

              { 

                  temp = temp ^ (0x10000 ^ 0x11021); 

              } 

          }//for

       ptr++; 

       }//while 

crc = temp; 

return(crc); 

}

/////////////////////////////////程序改进

uint cal_crc(uchar *ptr, uchar len) { //len为数据的字节长度

{ 

     unsigned int crc = 0; 

    unsigned char i; 

    unsigned char *ptr = test; 

    while( len-- ) 

      { 

         for(i = 0x80; i != 0; i = i >> 1)

           { 

                if((crc & 0x8000) != 0) 

                {

                    crc = crc << 1;

                    crc = crc ^ 0x1021; 

                } 

             else 

               { 

                   crc = crc << 1;

               } 

              if((*ptr & i) != 0) 

              { 

                   crc = crc ^ 0x1021; 

              } 

     }

ptr++; 

} 

return(crc);  

}

在把这个程序说详细点：开始我们从取得第一个字节假如为0x11，第一个if判断现在的校验码(这时的CRC码为上一次运算的余数)的第15（我们按0-15计算）为是否为1，如果为1说明左移1位后可以对0x11021求余运算，第二个if判断第7位是不是为1不是的话继续下一位，判断到1后除以0x1021。