CCITTCRC16计算原理与实现.docx
《CCITTCRC16计算原理与实现.docx》由会员分享，可在线阅读，更多相关《CCITTCRC16计算原理与实现.docx（20页珍藏版）》请在冰点文库上搜索。
CCITTCRC16计算原理与实现
CCITTCRC-16计算原理与实现
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+x5 x --------=----------=--------=（x3+x2+x）+-------- G（x） x3+x+1 x3+x+1 x3+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。
4.CRC算法的实现
---------------
要用程序实现CRC算法，考虑对第2节的长除法做一下变换，依然是M=11100110，G=1011，
其系数r为3。
11001100
------------------------
1011）11100110000
1011.......
----.......
1010......
1011......
----......
1110...
1011...
------...
1010..
1011..
-------
100 <---校验码
程序可以如下实现：
1）将Mx^r的前r位放入一个长度为r的寄存器；
2）如果寄存器的首位为1，将寄存器左移1位（将Mx^r剩下部分的MSB移入寄存器的LSB），
再与G的后r位异或，否则仅将寄存器左移1位（将Mx^r剩下部分的MSB移入寄存器的LSB）；
3）重复第2步，直到M全部Mx^r移入寄存器；
4）寄存器中的值则为校验码。
基于以上算法，我们可以看一下上面例子的程序计算过程：
（r＝3）
首先，11100110000前三位进入寄存器，即111
这时寄存器首位为1，执行第2步,移位成1100110000,这时寄存器中为前三位110，将其与011（生成多项式后三位）异或，得1010110000.
然后继续第2步，101首位为1，移位010110000,然后010与011异或，得 001110000
前面两个0，连续以为2次且不用计算异或，得1110000，接着移位110000，异或得101000
第一位为1，移位得01000，前三位异或得00100
最后因为前面两个0，直接移位两次后得寄存器中的内容100,这时Mx^r位的所有内容都移入寄存器，运算结束，记得检验码为100。
（关键先判断首位是否为1，然后移位，然后计算）
11100110000移位－>11100110000
011
1010110000 -->101第一位为1，移位且计算
1010110000
011
001110000-->001第一位第二位均为0，移位2次
001110000-->111第一位为1，移位且计算
1110000
011
101000-->101第一位为1，移位且计算
101000
011
00100-->移位2次得100
用CRC16-CCITT的生成多项式0x1021，其C代码（本文所有代码假定系统为32位，且都在VC6上编译通过）如下：
unsignedshortdo_crc（unsignedchar*message,unsignedintlen）
{
inti,j;
unsignedshortcrc_reg;
crc_reg=（message[0]<<
+message[1];
for（i=0;i {
if（i for（j=0;j<=7;j++）
{
if（（short）crc_reg<0）
crc_reg=（（crc_reg<<1）+（message[i+2]>>（7-i）））^0x1021;
else
crc_reg=（crc_reg<<1）+（message[i+2]>>（7-i））;
}
else
for（j=0;j<=7;j++）
{
if（（short）crc_reg<0）
crc_reg=（crc_reg<<1）^0x1021;
else
crc_reg<<=1;
}
}
returncrc_reg;
}
显然，每次内循环的行为取决于寄存器首位。
由于异或运算满足交换率和结合律，以及与0异或无影响，消息可以不移入寄存器，而在每次内循环的时候，寄存器首位再与对应的消息位异或。
改进的代码如下：
unsignedshortdo_crc（unsignedchar*message,unsignedintlen）
{
inti,j;
unsignedshortcrc_reg=0;
unsignedshortcurrent;
for（i=0;i {
current=message[i]<<8;
for（j=0;j<8;j++）
{
if（（short）（crc_reg^current）<0）
crc_reg=（crc_reg<<1）^0x1021;
else
crc_reg<<=1;
current<<=1;
}
}
returncrc_reg;
}
以上的讨论中，消息的每个字节都是先传输MSB，CRC16-CCITT标准却是按照先传输LSB，消息右移进寄存器来计算的。
只需将代码改成判断寄存器的LSB，将0x1021按位颠倒后（0x8408）与寄存器异或即可，如下所示：
Java代码
1.unsigned short do_crc（unsigned char *message, unsigned int len）
2.{
3. int i, j;
4. unsigned short crc_reg = 0;
5. unsigned short current;
6.
7. for （i = 0; i < len; i++）
8. {
9. current = message[i];
10. for （j = 0; j < 8; j++）
11. {
12. if （（crc_reg ^ current） & 0x0001）
13. crc_reg = （crc_reg >> 1） ^ 0x8408;
14. else
15. crc_reg >>= 1;
16. current >>= 1;
17. }
18. }
19. return crc_reg;
20.}
unsignedshortdo_crc（unsignedchar*message,unsignedintlen）
{
inti,j;
unsignedshortcrc_reg=0;
unsignedshortcurrent;
for（i=0;i{
current=message[i];
for（j=0;j<8;j++）
{
if（（crc_reg^current）&0x0001）
crc_reg=（crc_reg>>1）^0x8408;
else
crc_reg>>=1;
current>>=1;
}
}
returncrc_reg;
}
该算法使用了两层循环，对消息逐位进行处理，这样效率是很低的。
为了提高时间效率，通常的思想是以空间换时间。
考虑到内循环只与当前的消息字节和crc_reg的低字节有关，对该算法做以下等效转换：
Java代码
1.unsigned short do_crc（unsigned char *message, unsigned int len）
2.{
3. int i, j;
4. unsigned short crc_reg = 0;
5. unsigned char index;
6. unsigned short to_xor;
7.
8. for （i = 0; i < len; i++）
9. {
10. index = （crc_reg ^ message[i]） & 0xff;
11. to_xor = index;
12. for （j = 0; j < 8; j++）
13. {
14. if （to_xor & 0x0001）
15. to_xor = （to_xor >> 1） ^ 0x8408;
16. else
17. to_xor >>= 1;
18. }
19. crc_reg = （crc_reg >> 8） ^ to_xor;
20. }
21. return crc_reg;
22.}
unsignedshortdo_crc（unsignedchar*message,unsignedintlen）
{
inti,j;
unsignedshortcrc_reg=0;
unsignedcharindex;
unsignedshortto_xor;
for（i=0;i{
index=（crc_reg^message[i]）&0xff;
to_xor=index;
for（j=0;j<8;j++）
{
if（to_xor&0x0001）
to_xor=（to_xor>>1）^0x8408;
else
to_xor>>=1;
}
crc_reg=（crc_reg>>8）^to_xor;
}
returncrc_reg;
}
现在内循环只与index相关了，可以事先以数组形式生成一个表crc16_ccitt_table，使得to_xor=crc16_ccitt_table[index]，于是可以简化为：
Java代码
1.unsigned short do_crc（unsigned char *message, unsigned int len）
2.{
3. unsigned short crc_reg = 0;
4.
5. while （len--）
6. crc_reg = （crc_reg >> 8） ^ crc16_ccitt_table[（crc_reg ^ *message++） & 0xff];
7.
8. return crc_reg;
9.}
unsignedshortdo_crc（unsignedchar*message,unsignedintlen）
{
unsignedshortcrc_reg=0;
while（len--）
crc_reg=（crc_reg>>8）^crc16_ccitt_table[（crc_reg^*message++）&0xff];
returncrc_reg;
}
crc16_ccitt_table通过以下代码生成：
Java代码
1.int main（）
2.{
3. unsigned char index = 0;
4. unsigned short to_xor;
5. int i;
6.
7. printf（"unsigned short crc16_ccitt_table[256] =\n{"）;
8. while
（1）
9. {
10. if （!
（index % 8））
11. printf（"\n"）;
12.
13. to_xor = index;
14. for （i = 0; i < 8; i++）
15. {
16. if （to_xor & 0x0001）
17. to_xor = （to_xor >> 1） ^ 0x8408;
18. else
19. to_xor >>= 1;
20. }
21. printf（"0x%04x", to_xor）;
22.
23. if （index == 255）
24. {
25. printf（"\n"）;
26.
升级会员 