CRC校验

一、什么是CRC校验
     循环校验码（Jyclic Redundancy Check,简称CRC码): 是数据通信领域中最常用的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选定。

二、CRC校验计算
      CRC码是由两部分组成，前部分是信息码，就是需要校验的信息，后部分是校验码，如果CRC码共长n个bit，信息码长k个bit，它的编码规则是：
      1、首先将原信息码(kbit)左移r位(k+r=n),对应多项式为m(x)。
      2、运用一个生成R次多项式g(x)（也可看成二进制数）用模2除上面的式子，得到的余数就是校验码，r=R。
      非常简单，要说明的：模2除就是在除的过程中用模2加，模2加实际上就是我们熟悉的异或运算，就是加法不考虑进位，公式是：    
      0+0=1+1=0,1+0=0+1=1，即‘异’则真，‘非异’则假。
      由此得到定理：a+b+b=a 也就是‘模2减’和‘模2加’直值表完全相同。 
      有了加减法就可以用来定义模2除法，于是就可以用生成多项式g(x)生成CRC校验码。
      例如：代码1010111对应的多项式为x⁶+x⁴+x²+x+1，而多项式为x⁵+x³+x²+x+1对应的代码101111。
      现在计算 信息码1011001（多项式为x⁶+x⁴+x³+1），生成多项式g(x)=x⁴+x³+1（信息码为11001）的CRC，计算过程如下
      step1:   1011001左移4位得到10110010000
      steo2:   采用多项式除法:  得余数为: 1010     (即校验字段为：1010）
      CRC码即为1011001,1010 (逗号前为信息码，后为校验码)

三、编程实现
     

uint cal_crc(uchar *ptr, uchar len) { 
    uint crc; 
    uchar i; 
    crc=0; 
    while (len--!=0) { 
        for (i=0x80; i!=0; i/=2) { 
            if ((crc&0x8000)!=0){
                crc*=2; crc^=0x1021;
            } else crc*=2; 
            if ((*ptr&i)!=0)
                crc^=0x1021; 
        } 
    ptr++; 
    } 
    return(crc); 
} 

      

 四，实际应用
      发送方：发出的传输字段为:  1 0 1 1 0 0 1 1 0 10
                      信息字段       校验字段
     接收方：使用相同的生成码进行校验:接收到的字段/生成码（二进制除法）
    如果能够除尽，则正确

注：参考了网上很多资料

（pdf下载）《—— 重点推荐

标准CRC生成多项式如下表：

   名称        生成多项式              简记式*   标准引用
   CRC-4       x4+x+1                  3         ITU G.704
   CRC-8       x8+x5+x4+1              0x31                   
   CRC-8       x8+x2+x1+1              0x07                   
   CRC-8       x8+x6+x4+x3+x2+x1       0x5E
   CRC-12      x12+x11+x3+x+1          80F
   CRC-16      x16+x15+x2+1            8005      IBM SDLC
   CRC16-CCITT x16+x12+x5+1            1021      ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCS
   CRC-32      x32+x26+x23+...+x2+x+1 04C11DB7 ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCS
   CRC-32c     x32+x28+x27+...+x8+x6+1 1EDC6F41 SCTP

基本算法（人工笔算）：
   以CRC16-CCITT为例进行说明，CRC校验码为 16位，生成多项式17位。假如数据流为4字节：BYTE[3]、BYTE[2]、BYTE[1]、BYTE[0]；
数据流左移16位，相当于扩 大256×256倍，再除以生成多项式0x11021，做不借位的除法运算（相当于按位异或），所得的余数就是CRC校验码。
发送时的数据流为6字 节：BYTE[3]、BYTE[2]、BYTE[1]、BYTE[0]、CRC[1]、CRC[0]；

举例:

信息字段代码为: m(x)=x⁶+x⁴+x³+1    代码为:1011001

生成多项式:    g(x)=x⁴+x³+1       代码为:11001

m(x)x⁴⁼x¹⁰+x⁸+x⁷+x⁴ 对应的代码记为：10110010000     即 左移4位

m(x)x^{4 在与} g(x)进行 模2的除法运算,相当于按位异或,计算过程如下:

1 0 1 1 0 0 1 0 0 0 0
1 1 0 0 1
-----------------------------
0 1 1 1 1 0 1 0 0 0 0
   1 1 0 0 1
-----------------------------
   0 0 1 1 1 1 0 0 0 0
         1 1 0 0 1
-----------------------------
         0 0 1 1 1 0 0 0
               1 1 0 0 1
-----------------------------
               0 0 1 0 1 0             --------------> 余数     即 校验码

即发送10110011010

接收端接收到：10110011010，用10110011010/11001,因为是把余数加上一起除的，所以一定能除尽。如果除不尽，说明传输中出错。