文档介绍：第20讲 CRC算法详解
青岛科技大学
王泽华
**********
基本思想
发送端根据要传送的m位二进制码序列,以一定的规则产生校验用的r位CRC码,并附在信息后边,构成一个新的二进制码序列,共(m+r)位,发送出去。
接收端,将接收到的二进制序列数(m+r位)除以多项式,如果余数为0,则说明传输中无错误发生。用软件计算CRC码时,接收方可以将接收到的信息码求CRC码,与接收到的CRC码比较是否相同来判断传输数据是否有误。
一 CRC基本概念
二进制数与多项式
任意一个二进制数都对应一个多项式
例:1 0 1 1, 0 0 0 1 对应的多项式为
1·x7+0·x6+1·x5+1·x4+0·x3+0·x2+0·x1+1·x0
即 x7+x5+x4+1
生成多项式
任一种CRC校验都对应着一个生成多项式;生成多项式最高幂次和最低幂次的系数始终为1。
名称
生成多项式
16进制数
应用举例
CRC4
x4+x+1
ITU
CRC8/MAXIM
x8+x5+x4+1
0x31
MAXIM芯片
CRC16
x16+x15+x2+1
0x8005
MODBUS
CRC16-ITU*
x16+x12+x5+1
0x1021
ISO HDLC
CRC32
x32+x26+···+x2+x+1
0x04C11DB7
ZIP,RAR,
IEEE1394
CRC32C
x32+x28+···+x8+x6+1
0x1EDC6F41
SCTP
*CRC16-ITU以前称作CRC16-CITT
二 CRC算法基本原理
CRC的本质是模-2除法的余数。求CRC码所采用模2加减运算法则,即是不带进位和借位的按位加减,这种加减运算实际上是逻辑上的异或运算,加法和减法等价;乘法和除法运算与普通代数式的乘除法运算是一样。
假定要发送的二进制数对应的多项式为K(x),生成多项式为G(x),最高幂次为r。设xr·K(x)/G(x)得到的余数多项式为R(x)。则R(x)对应的二进制数即为CRC校验码,位数为r位。
用数学表达式表示为
xr·K(x)=G(x) ·Q(x)+R(x)
其中Q(x)为得到的整数商多项式。
举例:采用CRC4校验,传送的信息码为0101, 1001 ,生成多项式为x4+x+1。
解:信息码0101, 1001对应多项式为x6+x4+x3+1,乘以x4得
x10+x8+x7+x4,对应二进制**********
生成多项式x4+x+1对应被除数10011。
10011 1 0 1 1 0 0 1 0 0 0 0
1 0 0 1 1
1 0 1 0 1 0 0 0 0
1 0 0 1 1
1 1 0 0 0 0 0
1 0 0 1 1
1 0 1 1 0 0
1 0 0 1 1
1 0 1 0
1 0 1 0 1 1
异或运算
异或运算
余数
余数
余数
CRC码
异或运算
异或运算
为0不做处理
为0不做处理
简单改进
m位信息码添加r位0构成要处理的码块
每次处理4位,可设置一个4位寄存器,初始值为0。
信息码左移一位进入REG0,同时
检测寄存器中的移出位为1,将寄存器与0011异或运算,为0返回步骤3
若没处理完m+r位,返回步骤3;否则寄存器内容为CRC码
REG3
REG2
REG1
REG0
1 0 1 1 0 0 1 0 0 0 0
左移
左移
生成多项式最高位始终为1,可省掉该位
左移待检测的标志位
crcReg实际只用4位
16位crcReg=0x0000;
实际编程时的考虑
crcReg寄存器为16位,Bit0-7位存储加载的信息码字节
crcReg寄存器的Bit7-11用于crc码,Bit12用于检测左移出的值为1或0。
加载要处理的8位信息码
Bit
0
Bit
7
Bit
8
Bit
11
Bit
9
Bit
10
Bit
12
/**********************************************************/
#include<>
typedef unsigned char uint8;
typedef unsigned short int uint16;
uint8 simpCrc4(uint8 *p,int n)
{
uint16 crcReg=0x0000; //初始值
int i,j;
for(i=0;i<n;i++) //信息码共n个字节
{
crcReg ^= p[i];
for(j=0;j<8;j++) //处理一个字节
{