Cyclic Redundancy Check

CRC校验码

校验原理

1、循环校验码(CRC码):是数据通信领域中最常用的一种差错校验码,其特征是信息字段和校验字段的长度可以任意选定。

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

3CRC码集选择的原则:若设码字长度为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码字。

4CRC校验码软件生成方法:

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

例如:信息字段代码为: 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

                          信息字段       校验字段

接收方:使用相同的生成码进行校验:接收到的字段/生成码(二进制除法)

                  如果能够除尽,则正确,

 

 

 

CRC校验原理看起来比较复杂,好难懂,因为大多数书上基本上是以二进制的多项式形式来说明的。其实很简单的问题,其根本思想就是先在要发送的帧后面附加一个数(这个就是用来校验的校验码,但要注意,这里的数也是二进制序列的,下同),生成一个新帧发送给接收端。当然,这个附加的数不是随意的,它要使所生成的新帧能与发送端和接收端共同选定的某个特定数整除(注意,这里不是直接采用二进制除法,而是采用一种称之为2除法)。到达接收端后,再把接收到的新帧除以(同样采用2除法)这个选定的除数。因为在发送端发送数据帧之前就已通过附加一个数,做了去余处理(也就已经能整除了),所以结果应该是没有余数。如果有余数,则表明该帧在传输过程中出现了差错。

 

 

CRC 根据”(即多项表达式)的不同而相应的源代码也有稍许不同。以下是各种常用的权。

l  CRC8=X8+X5+X4+1

l  CRC-CCITT=X16+X12+X5+1

l  CRC16=X16+X15+X5+1

l  CRC12=X12+X11+X3+X2+1

l  CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1    

 

以下的源程序全部以 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;              // 
指向第一个 Byte 数据

  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 计算的就是移位和异或。所以一次处理移动几位都没有关系,只要做相应的处理就好了。
下面给出半字节查表的处理程序。其实和全字节是一回事。

 

循环冗余校验码

  CRCCyclic Redundancy Check)循环冗余校验码是常用的校验码,在早期的通信中运用广泛,因为早期的通信技术不够可靠(不可靠性的来源是通信技术决定的,比如电磁波通信时受雷电等因素的影响),不可靠的通信就会带来确认信息的困惑,书上提到红军和蓝军通信联合进攻山下的敌军的例子,第一天红军发了条信息要蓝军第二天一起进攻,蓝军收到之后,发一条确认信息,但是蓝军担心的是确认信息如果也不可靠而没有成功到达红军那里,那自己不是很危险?于是红军再发一条对确认的确认信息,但同样的问题还是不能解决,红军仍然不敢贸然行动。

  对通信的可靠性检查就需要校验,校验是从数据本身进行检查,它依靠某种数学上约定的形式进行检查,校验的结果是可靠或不可靠,如果可靠就对数据进行处理,如果不可靠,就丢弃重发或者进行修复。

  CRC码是由两部分组成,前部分是信息码,就是需要校验的信息,后部分是校验码,如果CRC码共长nbit,信息码长kbit,就称为(n,k)码。 它的编码规则是:

  1、首先将原信息码(kbit)左移r(k+r=n)

  2、运用一个生成多项式g(x)(也可看成二进制数)用模2除上面的式子,得到的余数就是校验码。

  非常简单,要说明的:模2除就是在除的过程中用模2加,模2加实际上就是我们熟悉的异或运算,就是加法不考虑进位,公式是:

  0+0=1+1=0,1+0=0+1=1

  即则真,非异则假。

  由此得到定理:a+b+b=a 也就是22直值表完全相同。

  有了加减法就可以用来定义模2除法,于是就可以用生成多项式g(x)生成CRC校验码。

  例如: g(x)=x4+x3+x2+1,(7,3),信息码110产生的CRC码就是:

  对于g(x)=x4+x3+x2+1的解释:(都是从右往左数)x4就是第五位是1,因为没有x1所以第2位就是0

  11101 | 110,0000(设a=11101 b=1100000

  取b的前511000a异或得到101

  101加上b没有取到的00得到10100

  然后跟a异或得到01001

  也就是余数1001

  余数是1001,所以CRC码是110,1001

  标准的CRC码是,CRC-CCITTCRC-16,它们的生成多项式是:

  CRC-CCITT=x^16+x^12+x^5+1

  CRC-16=x^16+x^15+x^2+1

 

 

2 CRC校验的C语言实现
下面我们以CRC-16为例来说明任意长度数据流的CRC校验码生成过程。我们采用将数据流分成若干个8bit字符,并由低字节到高字节传送的并行方法来求CRC校验码。具体计算过程为:用一个16bit的寄存器来存放CRC校验值,且设定其初值为0x0000;将数据流的第一个8bit16bitCRC寄存器的高字节相异或,并将结果存入CRC寄存器高字节;CRC寄存器左移一位,最低1bit补零,同时检查移出的最高1bit,若移出的最高1bit0,则继续按上述过程左移,若最高1bit1,则将CRC寄存器中的值与生成多项式码相异或,结果存入CRC寄存器值;继续左移并重复上述处理方法,直到将8bit数据处理完为止,则此时CRC寄存器中的值就是第一个8bit数据对应的CRC校验码;然后将此时CRC寄存器的值作为初值,用同样的处理方法重复上述步骤来处理下一个8bit数据流,直到将所有的8bit字符都处理完后,此刻CRC寄存器中的值即为整个数据流对应的CRC校验码。

下面示出了其计算过程的流程图:

在用C语言编写CRC校验码的实现程序时我们应该注意,生成多项式 对应的十六进制数为0x18005,由于CRC寄存器左移过程中,移出的最高位为1时与 相异或,所以与16bitCRC寄存器对应的生成多项式的十六进制数可用0x8005表示。下面给出并行处理8bit数据流的C源程序:
unsigned short crc_dsp(unsigned short reg, unsigned char data_crc)
//reg
crc寄存器, data_crc为将要处理的8bit数据流

{
unsigned short msb; //crc
寄存器将移出的最高
1bit
unsigned short data;
unsigned short gx = 0x8005, i = 0; //i
为左移次数, gx为生成多项式

data = (unsigned short)data_crc;
data = data << 8;
reg = reg ^ data;
do
{
msb = reg & 0x8000;
reg = reg << 1;
if(msb == 0x8000)
{
reg = reg ^ gx;
}
i++;
}
while(i < 8);
return (reg);
}

以上为处理每一个8bit数据流的子程序,在计算整个数据流的CRC校验码时,我们只需将CRC_reg的初值置为0x0000,求第一个8bitCRC值,之后,即可将上次求得的CRC值和本次将要处理的8bit数据作为函数实参传递给上述子程序的形参进行处理即可,最终返回的reg值便是我们所想得到的整个数据流的CRC校验值。


 

 

其实CRC可以用查表的方法。
/*
CRC
校验算法实现 C语言代码实现

文件
CRC16.h
*/
#ifndef _CRC16_h
#define _CRC16_h
static unsigned char auchCRCHi[] = {
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0,
0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41,
0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0,
0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40,
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1,
0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41,
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1,
0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41,
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0,
0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40,
0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1,
0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40,
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0,
0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40,
0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0,
0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40,
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0,
0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41,
0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0,
0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41,
0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0,
0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40,
0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1,
0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41,
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0,
0x80, 0x41, 0x00, 0xC1, 0x81, 0x40
};
/* CRC
低位字节值表
*/
static char auchCRCLo[] = {
0x00, 0xC0, 0xC1, 0x01, 0xC3, 0x03, 0x02, 0xC2, 0xC6, 0x06,
0x07, 0xC7, 0x05, 0xC5, 0xC4, 0x04, 0xCC, 0x0C, 0x0D, 0xCD,
0x0F, 0xCF, 0xCE, 0x0E, 0x0A, 0xCA, 0xCB, 0x0B, 0xC9, 0x09,
0x08, 0xC8, 0xD8, 0x18, 0x19, 0xD9, 0x1B, 0xDB, 0xDA, 0x1A,
0x1E, 0xDE, 0xDF, 0x1F, 0xDD, 0x1D, 0x1C, 0xDC, 0x14, 0xD4,
0xD5, 0x15, 0xD7, 0x17, 0x16, 0xD6, 0xD2, 0x12, 0x13, 0xD3,
0x11, 0xD1, 0xD0, 0x10, 0xF0, 0x30, 0x31, 0xF1, 0x33, 0xF3,
0xF2, 0x32, 0x36, 0xF6, 0xF7, 0x37, 0xF5, 0x35, 0x34, 0xF4,
0x3C, 0xFC, 0xFD, 0x3D, 0xFF, 0x3F, 0x3E, 0xFE, 0xFA, 0x3A,
0x3B, 0xFB, 0x39, 0xF9, 0xF8, 0x38, 0x28, 0xE8, 0xE9, 0x29,
0xEB, 0x2B, 0x2A, 0xEA, 0xEE, 0x2E, 0x2F, 0xEF, 0x2D, 0xED,
0xEC, 0x2C, 0xE4, 0x24, 0x25, 0xE5, 0x27, 0xE7, 0xE6, 0x26,
0x22, 0xE2, 0xE3, 0x23, 0xE1, 0x21, 0x20, 0xE0, 0xA0, 0x60,
0x61, 0xA1, 0x63, 0xA3, 0xA2, 0x62, 0x66, 0xA6, 0xA7, 0x67,
0xA5, 0x65, 0x64, 0xA4, 0x6C, 0xAC, 0xAD, 0x6D, 0xAF, 0x6F,
0x6E, 0xAE, 0xAA, 0x6A, 0x6B, 0xAB, 0x69, 0xA9, 0xA8, 0x68,
0x78, 0xB8, 0xB9, 0x79, 0xBB, 0x7B, 0x7A, 0xBA, 0xBE, 0x7E,
0x7F, 0xBF, 0x7D, 0xBD, 0xBC, 0x7C, 0xB4, 0x74, 0x75, 0xB5,
0x77, 0xB7, 0xB6, 0x76, 0x72, 0xB2, 0xB3, 0x73, 0xB1, 0x71,
0x70, 0xB0, 0x50, 0x90, 0x91, 0x51, 0x93, 0x53, 0x52, 0x92,
0x96, 0x56, 0x57, 0x97, 0x55, 0x95, 0x94, 0x54, 0x9C, 0x5C,
0x5D, 0x9D, 0x5F, 0x9F, 0x9E, 0x5E, 0x5A, 0x9A, 0x9B, 0x5B,
0x99, 0x59, 0x58, 0x98, 0x88, 0x48, 0x49, 0x89, 0x4B, 0x8B,
0x8A, 0x4A, 0x4E, 0x8E, 0x8F, 0x4F, 0x8D, 0x4D, 0x4C, 0x8C,
0x44, 0x84, 0x85, 0x45, 0x87, 0x47, 0x46, 0x86, 0x82, 0x42,
0x43, 0x83, 0x41, 0x81, 0x80, 0x40
};
/*
要进行CRC校验的消息 */ /* 消息中字节数
*/
unsigned short CRC16(unsigned char *puchMsg,unsigned short usDataLen )
{
unsigned char uchCRCHi = 0xFF ; /*
CRC字节初始化
*/
unsigned char uchCRCLo = 0xFF ; /*
CRC 字节初始化
*/
unsigned uIndex ; /* CRC
循环中的索引
*/
while (usDataLen–) /*
传输消息缓冲区
*/
{
uIndex = uchCRCHi ^ *puchMsg++ ; /*
计算
CRC */
uchCRCHi = uchCRCLo ^ auchCRCHi[uIndex];
uchCRCLo = auchCRCLo[uIndex] ;
}
return (uchCRCHi < < 8 | uchCRCLo) ;
}
#endif //_CRC16_h

/*
CRC16.cpp

生成 CRC码实现

*/
#include <stdio.h>
#include “CRC16.h”
void main()
{
unsigned char ppp[13] = {0x12,0x34};
    unsigned short result; 
    //
计算
CRC
    result = CRC16(ppp, 2);
printf(“%x\n”,result);
}