中药馆门头装修效果图:CRC原理的理解与C语言

名称 生成多项式 简记式^* 应用举例 CRC-4 x⁴+x+1    3 ITU G.704 CRC-12 x¹²+x¹¹+x³+x+1       CRC-16 x¹⁶+x¹⁵+x²+1 8005 IBM SDLC CRC-ITU^** x¹⁶+x¹²+x⁵+1 1021 ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCS CRC-32 x³²+x²⁶+x²³+...+x²+x+1 04C11DB7 ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCS CRC-32c x³²+x²⁸+x²⁷+...+x⁸+x⁶+1 1EDC6F41 SCTP

*  生成多项式的最高幂次项系数是固定的1，故在简记式中，将最高的1统一去掉了，如04C11DB7实际上是104C11DB7。** 前称CRC-CCITT。ITU的前身是CCITT。

先举个简单的例子，以CRC-4标准为例，说明CRC编码过程。

设待发送的数据t(x)为12位的二进制数据100100011100；CRC-4的生成多项式为g(x)=x^4+x+1，阶数r为4，即10011(生成多项式中x用1表示)。首先在t(x)的末尾添加4个0构成x^4*t(x)，即是左移4位(CRC-16就是左移16位)，此后，待发送的数据块变为1001000111000000。然后用g(x)（其值为10011）去除x^4*t(x)（左移4位后的待发送数据）【实际是XOR异或运算，不是除法】，不管商是多少，只需要求得余数y(x)，即为待发送数据对应的CRC值。

下表为给出的除法过程：

最后的4位的余数就是待发送数据对应的CRC-4编码。从上面表中可以看出，CRC 编码实际上是一个循环移位的模 2 运算。对 CRC-4，我们假设有一个 5 bits 的寄存器，通过反复的移位和进行 CRC的除法，那么最终该寄存器中的值去掉最高一位就是我们所要求的余数。所以可以将上述步骤用下面的流程描述：

//reg 是一个 5 bits 的寄存器 
把 reg 中的值置 0.  
把原始的数据后添加 r个 0.  
While (数据未处理完)  
Begin  
If (reg 首位是 1)  
reg = reg XOR 0011.        
把 reg 中的值左移一位，读入一个新的数据并置于 register的 0 bit 的位置。 
End 
reg 的后四位就是我们所要求的余数。

常见的CRC校验法有3种，直接计算法，查表法，半查表法。下面是几种CRC16的C语言代码，自己理解分析一下

首先是WINAVR中的crc16.h中的库函数(路径在C:\WinAVR-20090313\avr\include\util\crc16.h)

    //Optimized CRC-XMODEM calculation.

    //Polynomial: x^16 + x^12 + x^5 + 1 (0x1021)

    //Initial value: 0x0

    //This is the CRC used by the Xmodem-CRC protocol.

    //code
    uint16_t
    crc_xmodem_update (uint16_t crc, uint8_t data)
    {
        int i;

        crc = crc ^ ((uint16_t)data << 8);
        for (i=0; i<8; i++)
        {
            if (crc & 0x8000)
                crc = (crc << 1) ^ 0x1021;
            else
                crc <<= 1;
        }

        return crc;
    }

但我觉得WINAVR中的Xmodem-CRC标准与很多文章说的CRC-CCITT好像是一致的，
但WINAVR中又提供另一个CRC-CCITT标准，应该是反相CRC-CCITT运算，即右移，原代码如下：

       //Optimized CRC-CCITT calculation.

       //Polynomial: x^16 + x^12 + x^5 + 1 (0x8408)

        //Initial value: 0xffff

        //This is the CRC used by PPP and IrDA.

        //See RFC1171 (PPP protocol) and IrDA IrLAP 1.1

 //       \note Although the CCITT polynomial is the same as that used by the Xmodem
 //       protocol, they are quite different. The difference is in how the bits are
 //       shifted through the alorgithm. Xmodem shifts the MSB of the CRC and the
 //       input first, while CCITT shifts the LSB of the CRC and the input first.

//以上一段话说明了CCITT与Xmodem 的CRC校验的不同点。

//       The following is the equivalent functionality written in C.

        \code
        uint16_t
        crc_ccitt_update (uint16_t crc, uint8_t data)
        {
            data ^= lo8 (crc);
            data ^= data << 4;

            return ((((uint16_t)data << 8) | hi8 (crc)) ^ (uint8_t)(data >> 4) 
                    ^ ((uint16_t)data << 3));
        }

不知道上面哪个才是我们说的CRC-CCITT，不过我个人认为其实是哪种CRC校验没所谓，关键是发送端与接收端用同一种CRC校验就可以了。

下面是网上比较多见的CRC-CCITT校验源码。

typedef        unsigned char         uchar; 
typedef        unsigned int          uint; 
 
code uchar crcbuff [] = { 0x00,0x00,0x00,0x00,0x06,0x0d,0xd2,0xe3}; //待发送数据
uint crc;                       // CRC 码 
void main(void) 
{ 
  uchar *ptr; 
  crc = 0;                    // CRC  初值 
  ptr = crcbuff;                   //  指向待发送数据 
  crc = crc16l(ptr,8);                 
  while(1); 
}

uint crc16l(uchar *ptr,uchar len)            // ptr 为数据指针，len 为数据长度 
{ 
  uchar i; 
  while(len--) 
  { 
           for(i=0x80; i!=0; i>>=1) 
           { 
               if((crc&0x8000)!=0) 
              {
                 crc<<=1; 
                 crc^=0x1021;
               }                                      //1-1       
               else 
              {
                 crc<<=1;                             //1-2 
              }


               if((*ptr&i)!=0) 
              {
                 crc^=0x1021;                        //1-3       
              }        
           } 
           ptr++; 
  } 
  return(crc); 
}

执行结果 crc = 0xdbc0; 
程序 1-1,1-2,1-3 可以理解成移位前 crc  的 Bit15 与数据对应的 Bit(*ptr&i)做 XOR运算，根
据此结果来决定是否执行 crc^=0x1021。只要明白两次异或运算与原值相同，就不难理解这
个程序。 
 
很多资料上都写了查表法来计算，当时是怎么也没想通。其实蛮简单的。假设通过移位处理
了 8 个 bit 的数据，相当于把之前的 CRC 码的高字节(8bit)全部移出，与一个 byte 的数据做
XOR 运算，根据运算结果来选择一个值(称为余式)，与原来的 CRC 码再做一次 XOR 运算，
就可以得到新的 CRC 码。

具体应用的编程思路：

另外，其实应用CRC校验，关键的是编写发送端的计算CRC码，及在待发送数据后添加CRC码的函数。至于用哪种CRC标准，是CRC-CCITT，还是CRC-8等要看具体的应用，另外高效的代码也是要考虑的，毕竟用在单片机系统中，是用计算法、查表法、半查表法，需要兼顾代码运行时间或程序空间两方面。
在接收端，则要编写与发送端CRC标准一致的检验函数，根据收到的数据有效部分，用同样的CRC标准运算出CRC
码，与发送端所发送的数据最后夹带的CRC码比较，如果相同，则认为传输过程中误码机会较小，认为通讯有效。