crc算法:全面分析CRC算法

CRC全称为CyclicRedundancyCheck中文名称为循环冗余校验它是类重要线性分组码编码和解码思路方法简单检错和纠错能力强在通信领域广泛地用于实现差错控制实际上除数据通信外CRC在其它很多领域也是大有用武的地例如我们读软盘上文件以及解压个ZIP文件时偶尔会碰到“BadCRC”由此它在数据存储方面应用可略见斑
差错控制理论是在代数理论基础上建立起来这里我们着眼于介绍CRC算法和实现对原理只能捎带介绍说明下若需要进步了解线性码、分组码、循环码、纠错编码等方面原理可以阅读有关资料
利用CRC进行检错过程可简单描述为:在发送端根据要传送k位 2进制码序列以定规则产生个校验用r位监督码(CRC码)附在原始信息后边构成个新 2进制码序列数共k+r位然后发送出去在接收端根据信息码和CRC码的间所遵循规则进行检验以确定传送中是否出错这个规则在差错控制理论中称为“生成多项式”

　
1代数学般性算法
在代数编码理论中将个码组表示为个多项式码组中各码元当作多项式系数例如1100101表示为
1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1即x6+x5+x2+1
设编码前原始信息多项式为P(x)P(x)最高幂次加1等于k；生成多项式为G(x)G(x)最高幂次等于r；CRC多项式为R(x)；编码后带CRC信息多项式为T(x)
发送方编码思路方法:将P(x)乘以xr(即对应 2进制码序列左移r位)再除以G(x)所得余式即为R(x)用公式表示为
T(x)=xrP(x)+R(x)
接收方解码思路方法:将T(x)除以G(x)如果余数为0则介绍说明传输中无发生否则介绍说明传输有误
举例来说设信息码为1100生成多项式为1011即P(x)=x3+x2G(x)=x3+x+1计算CRC过程为
xrP(x)x3(x3+x2)x6+x5x
--------=----------=--------=(x3+x2+x)+--------
G(x)x3+x+1x3+x+1x3+x+1

即R(x)=x注意到G(x)最高幂次r=3得出CRC为010
如果用竖式除法计算过程为
1110
-------
1011/1100000(1100左移3位)
1011
----
1110
1011
----- [Page]
1010
1011
-----
0010
0000
----
010

因此T(x)=(x6+x5)+(x)=x6+x5+x,即1100000+010=1100010
如果传输无误
T(x)x6+x5+x
------=---------=x3+x2+x,
G(x)x3+x+1

无余式回头看下上面竖式除法如果被除数是1100010显然在商第 3个1时就能除尽
上述推算过程有助于我们理解CRC概念但直接编程来实现上面算法不仅繁琐效率也不高实际上在工程中不会直接这样去计算和验证CRC
下表中列出了些见于标准CRC资料:
名称生成多项式简记式*应用举例
CRC-4x4+x+1ITUG.704
CRC-12x12+x11+x3+x+1
CRC-16x16+x12+x2+11005IBMSDLC
CRC-ITU**x16+x12+x5+11021ISOHDLC,ITUX.25,V.34/V.41/V.42,PPP-FCS
CRC-32x32+x26+x23+...+x2+x+104C11DB7ZIP,RAR,IEEE802LAN/FDDI,IEEE1394,PPP-FCS
CRC-32cx32+x28+x27+...+x8+x6+11EDC6F41SCTP

*生成多项式最高幂次项系数是固定1故在简记式中将最高1统去掉了如04C11DB7实际上是104C11DB7


**前称CRC-CCITTITU前身是CCITT


2硬件电路实现思路方法
多项式除法可用除法电路来实现除法电路主体由组移位寄存器和模2加法器(异或单元)组成以CRC-ITU为例它由16级移位寄存器和3个加法器组成见下图(编码/解码共用)编码、解码前将各寄存器化为\"1\"信息位随着时钟移入当信息位全部输入后从寄存器组输出CRC结果

\" width=471 align=center>

3比特型算法
上面CRC-ITU除法电路完全可以用软件Software来模拟定义个寄存器组化为全\"1\"依照电路图每输入个信息位相当于个时钟脉冲到来从高到低依次移位移位前信息位和bit0相加产生临时位其中bit15移入临时位bit10、bit3还要加上临时位当全部信息位输入完成后从寄存器组取出它们值这就是CRC码 [Page]
typedefunsignedcharbit;
typedefunsignedchar;
typedefunsignedu16;

typedefunion{
u16val;
struct{
u16bit0:1;
u16bit1:1;
u16bit2:1;
u16bit3:1;
u16bit4:1;
u16bit5:1;
u16bit6:1;
u16bit7:1;
u16bit8:1;
u16bit9:1;
u16bit10:1;
u16bit11:1;
u16bit12:1;
u16bit13:1;
u16bit14:1;
u16bit15:1;
}bits;
}CRCREGS;

//寄存器组
CRCREGSregs;

//化CRC寄存器组:移位寄存器置为全\"1\"
voidcrcInitRegisters
{
regs.val=0xffff;
}

//CRC输入个bit
voidcrcInputBit(bitin)
{
bita;

a=regs.bits.bit0^in;

regs.bits.bit0=regs.bits.bit1;
regs.bits.bit1=regs.bits.bit2;
regs.bits.bit2=regs.bits.bit3;
regs.bits.bit3=regs.bits.bit4^a;
regs.bits.bit4=regs.bits.bit5;
regs.bits.bit5=regs.bits.bit6;
regs.bits.bit6=regs.bits.bit7;
regs.bits.bit7=regs.bits.bit8; [Page]
regs.bits.bit8=regs.bits.bit9;
regs.bits.bit9=regs.bits.bit10;
regs.bits.bit10=regs.bits.bit11^a;
regs.bits.bit11=regs.bits.bit12;
regs.bits.bit12=regs.bits.bit13;
regs.bits.bit13=regs.bits.bit14;
regs.bits.bit14=regs.bits.bit15;
regs.bits.bit15=a;
}

//输出CRC码(寄存器组值)
u16crcGetRegisters
{
regs.val;
}

crcInputBit中步步移位/异或操作可以进行简化:

voidcrcInputBit(bitin)
{
bita;
a=regs.bits.bit0^in;
regs.val>>=1;
(a)regs.val^=0x8408;
}

细心话可以发现0x8408和0x1021(CRC-ITU简记式)的间关系由于我们是从低到高输出比特流将0x1021左右反转就得到0x8408将生成多项式写成G(x)=1+x5+x12+x16是不是更好看点？
下面是个典型PPP帧最后两个字节称为FCS(FrameCheckSequence)是前面11个字节CRC
FF03C021040300070D0306D03A


我们来计算这个PPP帧CRC并验证它
ppp[13]={0xFF,0x03,0xC0,0x21,0x04,0x03,0x00,0x07,0x0D,0x03,0x06,0x00,0x00};
i,j;
u16result;

///////////以下计算FCS

//化
crcInitRegisters;

//逐位输入每个字节低位在先不包括两个FCS字节
for(i=0;i<11;i)
{
for(j=0;j<8;j)
{
crcInputBit((ppp[i]>>j)&1);
}
}

//得到CRC:将寄存器组值求反 [Page]
result=~crcGetRegisters;

//填写FCS先低后高
ppp[11]=result&0xff;
ppp[12]=(result>>8)&0xff;

///////////以下验证FCS

//化
crcInitRegisters;

//逐位输入每个字节低位在先包括两个FCS字节
for(i=0;i<13;i)
{
for(j=0;j<8;j)
{
crcInputBit((ppp[i]>>j)&1);
}
}

//得到验证结果
result=crcGetRegisters;

可以看到计算出CRC等于0x3AD0和原来FCS相同验证结果等于0化为全\"1\"以及将寄存器组值求反得到CRC都是CRC-ITU要求事实上不管化为全\"1\"还是全\"0\"计算CRC取反还是不取反得到验证结果都是0


4字节型算法
比特型算法逐位进行运算效率比较低不适用于高速通信场合数字通信系统(各种通信标准)般是对帧数据进行CRC校验而字节是帧基本单位最常用是种按字节查表快速算法该算法基于这样个事实:计算本字节后CRC码等于上字节余式CRC码低8位左移8位加上上字节CRC右移8位和本字节的和后所求得CRC码如果我们把8位 2进制序列数CRC(共256个)全部计算出来放在个表里编码时只要从表中查找对应值进行处理即可

CRC-ITU计算算法如下:
a.寄存器组化为全\"1\"(0xFFFF)
b.寄存器组向右移动个字节
c.刚移出那个字节和数据字节进行异或运算得出个指向值表索引
d.索引所指表值和寄存器组做异或运算
f.数据指针加1如果数据没有全部处理完则重复步骤b
g.寄存器组取反得到CRC附加在数据的后

CRC-ITU验证算法如下:
a.寄存器组化为全\"1\"(0xFFFF)
b.寄存器组向右移动个字节
c.刚移出那个字节和数据字节进行异或运算得出个指向值表索引
d.索引所指表值和寄存器组做异或运算
e.数据指针加1如果数据没有全部处理完则重复步骤b(数据包括CRC两个字节)
f.寄存器组值是否等于“MagicValue”(0xF0B8)若相等则通过否则失败 [Page]

下面是通用CRC-ITU查找表以及计算和验证CRCC语言:
//CRC-ITU查找表
constu16crctab16=
{
0x0000,0x1189,0x2312,0x329b,0x4624,0x57ad,0x6536,0x74bf,
0x8c48,0x9dc1,0xaf5a,0xbed3,0xca6c,0xdbe5,0xe97e,0xf8f7,
0x1081,0x0108,0x3393,0x221a,0x56a5,0x472c,0x75b7,0x643e,
0x9cc9,0x8d40,0xbfdb,0xae52,0xdaed,0xcb64,0xf9ff,0xe876,
0x2102,0x308b,0x0210,0x1399,0x6726,0x76af,0x4434,0x55bd,
0xad4a,0xbcc3,0x8e58,0x9fd1,0xeb6e,0xfae7,0xc87c,0xd9f5,
0x3183,0x200a,0x1291,0x0318,0x77a7,0x662e,0x54b5,0x453c,
0xbdcb,0xac42,0x9ed9,0x8f50,0xfbef,0xea66,0xd8fd,0xc974,


0x4204,0x538d,0x6116,0x709f,0x0420,0x15a9,0x2732,0x36bb,
0xce4c,0xdfc5,0xed5e,0xfcd7,0x8868,0x99e1,0xab7a,0xbaf3,
0x5285,0x430c,0x7197,0x601e,0x14a1,0x0528,0x37b3,0x263a,
0xdecd,0xcf44,0xfddf,0xec56,0x98e9,0x8960,0xbbfb,0xaa72,
0x6306,0x728f,0x4014,0x519d,0x2522,0x34ab,0x0630,0x17b9,
0xef4e,0xfec7,0xcc5c,0xddd5,0xa96a,0xb8e3,0x8a78,0x9bf1,
0x7387,0x620e,0x5095,0x411c,0x35a3,0x242a,0x16b1,0x0738,
0xffcf,0xee46,0xdcdd,0xcd54,0xb9eb,0xa862,0x9af9,0x8b70,
0x8408,0x9581,0xa71a,0xb693,0xc22c,0xd3a5,0xe13e,0xf0b7,
0x0840,0x19c9,0x2b52,0x3adb,0x4e64,0x5fed,0x6d76,0x7cff,
0x9489,0x8500,0xb79b,0xa612,0xd2ad,0xc324,0xf1bf,0xe036,
0x18c1,0x0948,0x3bd3,0x2a5a,0x5ee5,0x4f6c,0x7df7,0x6c7e, [Page]
0xa50a,0xb483,0x8618,0x9791,0xe32e,0xf2a7,0xc03c,0xd1b5,
0x2942,0x38cb,0x0a50,0x1bd9,0x6f66,0x7eef,0x4c74,0x5dfd,
0xb58b,0xa402,0x9699,0x8710,0xf3af,0xe226,0xd0bd,0xc134,
0x39c3,0x284a,0x1ad1,0x0b58,0x7fe7,0x6e6e,0x5cf5,0x4d7c,
0xc60c,0xd785,0xe51e,0xf497,0x8028,0x91a1,0xa33a,0xb2b3,
0x4a44,0x5bcd,0x6956,0x78df,0x0c60,0x1de9,0x2f72,0x3efb,
0xd68d,0xc704,0xf59f,0xe416,0x90a9,0x8120,0xb3bb,0xa232,
0x5ac5,0x4b4c,0x79d7,0x685e,0x1ce1,0x0d68,0x3ff3,0x2e7a,
0xe70e,0xf687,0xc41c,0xd595,0xa12a,0xb0a3,0x8238,0x93b1,
0x6b46,0x7acf,0x4854,0x59dd,0x2d62,0x3ceb,0x0e70,0x1ff9,
0xf78f,0xe606,0xd49d,0xc514,0xb1ab,0xa022,0x92b9,0x8330,
0x7bc7,0x6a4e,0x58d5,0x495c,0x3de3,0x2c6a,0x1ef1,0x0f78,
};

//计算给定长度数据16位CRC
u16GetCrc16(const*pData,nLength)
{
u16fcs=0xffff;//化

while(nLength>0)
{
fcs=(fcs>>8)^crctab16[(fcs^*pData)&0xff];
nLength--;
pData;
}

~fcs;//取反
}

//检查给定长度数据16位CRC是否正确
boolIsCrc16Good(const*pData,nLength)
{
u16fcs=0xffff;//化

while(nLength>0) [Page]
{
fcs=(fcs>>8)^crctab16[(fcs^*pData)&0xff];
nLength--;
pData;
}

(fcs0xf0b8);//0xf0b8是CRC-ITU\"MagicValue\"
}

使用字节型算法前面出现PPP帧FCS计算和验证过程可用下面片断实现:
ppp[13]={0xFF,0x03,0xC0,0x21,0x04,0x03,0x00,0x07,0x0D,0x03,0x06,0x00,0x00};
u16result;

//计算CRC
result=GetCrc16(ppp,11);



//填写FCS先低后高
ppp[11]=result&0xff;
ppp[12]=(result>>8)&0xff;

//验证FCS
(IsCrc16Good(ppp,13))
{
......
}

该例中数据长度为11介绍说明CRC计算并不要求数据2字节或4字节对齐
至于查找表生成算法以及CRC-32等其它CRC算法可参考RFC1661,RFC3309等文档需要注意是虽然CRC算法本质是样但区别协议、标准所规定化、移位次序、验证思路方法等可能有所差别


CRC是现代通信领域重要技术的掌握CRC算法和实现思路方法在通信系统设计、通信协议分析以及软件Software保护等诸多方面能发挥很大作用如在作者曾经设计个多串口数据传输系统中每串口速率为460kbps不加校验时误码率大于10-6加上简单奇偶校验后性能改善不很明显利用CRC进行检错重传误码率降低至10-15以下满足了实际应用要求

延伸阅读

• 2009-2-12-- 校验和算法:身份证校验算法与ASP程序
• 2009-2-12-- crc32算法:crc32算法介绍附C#版
• 2009-2-12-- crc算法及c语言实现:CRC算法的实现
• 2009-2-12-- crc32算法:CRC32算法实现原理
• 2009-2-12-- crc算法及c语言实现:CRC算法的实现
• 2008-9-25-- crc算法及c语言实现:C语言实现CRC算法的方法代码
• 2009-2-12-- crc校验算法:网际校验和(Internet Checksum)算法（C++）