CRC的全称为循环冗余校验.docx
《CRC的全称为循环冗余校验.docx》由会员分享，可在线阅读，更多相关《CRC的全称为循环冗余校验.docx（18页珍藏版）》请在冰点文库上搜索。
CRC的全称为循环冗余校验
CRC的全称为CyclicRedundancyCheck，中文名称为循环冗余校验。
它是一类重要的线性分组码，编码和解码方法简单，检错和纠错能力强，在通信领域广泛地用于实现差错控制。
实际上，除数据通信外，CRC在其它很多领域也是大有用武之地的。
例如我们读软盘上的文件，以及解压一个ZIP文件时，偶尔会碰到“BadCRC”错误，由此它在数据存储方面的应用可略见一斑。
差错控制理论是在代数理论基础上建立起来的。
这里我们着眼于介绍CRC的算法与实现，对原理只能捎带说明一下。
若需要进一步了解线性码、分组码、循环码、纠错编码等方面的原理，可以阅读有关资料。
利用CRC进行检错的过程可简单描述为：
在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的r位监督码（CRC码），附在原始信息后边，构成一个新的二进制码序列数共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（即对应的二进制码序列左移r位），再除以G（x），所得余式即为R（x）。
用公式表示为
T（x）=xrP（x）+R（x）
接收方解码方法：
将T（x）除以G（x），如果余数为0，则说明传输中无错误发生，否则说明传输有误。
举例来说，设信息码为1100，生成多项式为1011，即P（x）=x3+x2，G（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
-----
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，显然在商第三个1时，就能除尽。
上述推算过程，有助于我们理解CRC的概念。
但直接编程来实现上面的算法，不仅繁琐，效率也不高。
实际上在工程中不会直接这样去计算和验证CRC。
下表中列出了一些见于标准的CRC资料：
名称
生成多项式
简记式*
应用举例
CRC-4
x4+x+1
ITUG.704
CRC-12
x12+x11+x3+x+1
CRC-16
x16+x12+x2+1
1005
IBMSDLC
CRC-ITU**
x16+x12+x5+1
1021
ISOHDLC,ITUX.25,V.34/V.41/V.42,PPP-FCS
CRC-32
x32+x26+x23+...+x2+x+1
04C11DB7
ZIP,RAR,IEEE802LAN/FDDI,IEEE1394,PPP-FCS
CRC-32c
x32+x28+x27+...+x8+x6+1
1EDC6F41
SCTP
*生成多项式的最高幂次项系数是固定的1，故在简记式中，将最高的1统一去掉了，如04C11DB7实际上是104C11DB7。
**前称CRC-CCITT。
ITU的前身是CCITT。
2硬件电路的实现方法
多项式除法，可用除法电路来实现。
除法电路的主体由一组移位寄存器和模2加法器（异或单元）组成。
以CRC-ITU为例，它由16级移位寄存器和3个加法器组成，见下图（编码/解码共用）。
编码、解码前将各寄存器初始化为"1"，信息位随着时钟移入。
当信息位全部输入后，从寄存器组输出CRC结果。
3比特型算法
上面的CRC-ITU除法电路，完全可以用软件来模拟。
定义一个寄存器组，初始化为全"1"。
依照电路图，每输入一个信息位，相当于一个时钟脉冲到来，从高到低依次移位。
移位前信息位与bit0相加产生临时位，其中bit15移入临时位，bit10、bit3还要加上临时位。
当全部信息位输入完成后，从寄存器组取出它们的值，这就是CRC码。
typedefunsignedcharbit;
typedefunsignedcharbyte;
typedefunsignedshortu16;
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;
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（）
{
returnregs.val;
}
crcInputBit中一步一步的移位/异或操作，可以进行简化：
voidcrcInputBit（bitin）
{
bita;
a=regs.bits.bit0^in;
regs.val>>=1;
if（a）regs.val^=0x8408;
}
细心的话，可以发现0x8408和0x1021（CRC-ITU的简记式）之间的关系。
由于我们是从低到高输出比特流的，将0x1021左右反转就得到0x8408。
将生成多项式写成G（x）=1+x5+x12+x16，是不是更好看一点？
下面是一个典型的PPP帧。
最后两个字节称为FCS（FrameCheckSequence），是前面11个字节的CRC。
FF03C021040300070D0306D03A
我们来计算这个PPP帧的CRC，并验证它。
byteppp[13]={0xFF,0x03,0xC0,0x21,0x04,0x03,0x00,0x07,0x0D,0x03,0x06,0x00,0x00};
inti,j;
u16result;
///////////以下计算FCS
//初始化
crcInitRegisters（）;
//逐位输入，每个字节低位在先，不包括两个FCS字节
for（i=0;i<11;i++）
{
for（j=0;j<8;j++）
{
crcInputBit（（ppp[i]>>j）&1）;
}
}
//得到CRC：
将寄存器组的值求反
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位二进制序列数的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），若相等则通过，否则失败。
下面是通用的CRC-ITU查找表以及计算和验证CRC的C语言程序：
//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,
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（constbyte*pData,intnLength）
{
u16fcs=0xffff;//初始化
while（nLength>0）
{
fcs=（fcs>>8）^crctab16[（fcs^*pData）&0xff];
nLength--;
pData++;
}
return~fcs;//取反
}
//检查给定长度数据的16位CRC是否正确。
boolIsCrc16Good（constbyte*pData,intnLength）
{
u16fcs=0xffff;//初始化
while（nLength>0）
{
fcs=（fcs>>8）^crctab16[（fcs^*pData）&0xff];
nLength--;
pData++;
}
return（fcs==0xf0b8）;//0xf0b8是CRC-ITU的"MagicValue"
}
使用字节型算法，前面出现的PPP帧FCS计算和验证过程，可用下面的程序片断实现：
byteppp[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
if（IsCrc16Good（ppp,13））
{
......
}
该例中数据长度为11，说明CRC计算并不要求数据2字节或4字节对齐。
至于查找表的生成算法，以及CRC-32等其它CRC的算法，可参考RFC1661,RFC3309等文档。
需要注意的是，虽然CRC算法的本质是一样的，但不同的协议、标准所规定的初始化、移位次序、验证方法等可能有所差别。
结语
CRC是现代通信领域的重要技术之一。
掌握CRC的算法与实现方法，在通信系统的设计、通信协议的分析以及软件保护等诸多方面，能发挥很大的作用。
如在作者曾经设计的一个多串口数据传输系统中，每串口速率为460kbps，不加校验时误码率大于10-6，加上简单的奇偶校验后性能改善不很明显，利用CRC进行检错重传，误码率降低至10-15以下，满足了实际应用的要求。
CRC循环冗余校验
计算过程
1．设置CRC寄存器，并给其赋值FFFF（hex）。
2．将数据的第一个8-bit字符与16位CRC寄存器的低8位进行异或，并把结果存入CRC寄存器。
3．CRC寄存器向右移一位，MSB补零，移出并检查LSB。
4．如果LSB为0，重复第三步；若LSB为1，CRC寄存器与多项式码相异或。
5．重复第3与第4步直到8次移位全部完成。
此时一个8-bit数据处理完毕。
6．重复第2至第5步直到所有数据全部处理完成。
7．最终CRC寄存器的内容即为CRC值。
常用的CRC循环冗余校验标准多项式如下：
CRC（12位）=X12+X11+X3+X2+X+1
CRC（16位）=X16+X15+X2+1
CRC（CCITT）=X16+X12+X5+1
CRC（32位）=X32+X26+X23+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1
以CRC（16位）多项式为例，其对应校验二进制位列为11000000000000101。
注意：
这儿列出的标准校验多项式都含有（X+1）的多项式因子；各多项式的系数均为二进制数，所涉及的四则运算仍遵循对二取模的运算规则。
（注：
对二取模的四则运算指参与运算的两个二进制数各位之间凡涉及加减运算时均进行XOR异或运算，即：
1XOR1=0，0XOR0=0，1XOR0=1，0XOR1=1，即相同为0，不同为1）
算法
通常的CRC算法在计算一个数据段的CRC值时，其CRC值是由求解每个数值的CRC值的和对CRC寄存器的值反复更新而得到的。
这样，求解CRC的速度较慢。
通过对CRC算法的研究，我们发现:
一个8位数据加到16位累加器中去，只有累加器的高8位或低8位与数据相作用，其结果仅有256种可能的组合值。
因而，我们可以用查表法来代替反复的运算，这也同样适用于CRC32的计算。
本文所提供的程序库中，函数crchware是一般的16位CRC的算法；mk-crctbl用以在内存中建立一个CRC数值表；crcupdate用以查表并更新CRC累加器的值；crcrevhware和crcrevupdate是反序算法的两个函数；BuildCRCTable、CalculateBlockCRC32和UpdateCharac
terCRC32用于CRC32的计算。
/*CRC.C——CRC程序库*/
#defineCRCCCITT0x1021
#defineCCITT-REV0x8408
#defineCRC160x8005
#defineCRC16-REV0xA001
#defineCRC32-POLYNOMIAL0xEDB88320L
/*以上为CRC除数的定义*/
#defineNIL0
#definecrcupdate（d,a,t）*（a）=（*（a）<<8）^（t
升级会员 