CRC校验码算法的研究与实现

王根义

（陕西职业技术学院 陕西 西安 710100）

在通信系统的数据传输过程中，由于信道中各种复杂因素的影响，往往使传输的信号受到干扰，造成误码的出现。接收方为了检查所接收的数据是否有误码，可采用多种检测方法。差错控制编码是目前数据传输过程中普遍采用的一种提高数据通信可靠性的方法，而CRC是一种在实际通信中应用很广泛的差错控制编码，具有很强的检错能力。但由于国内对CRC技术应用的不够深入和不够广泛，许多检错改错工程死板地套用有限的模式，浪费了资源，本论文就是为了提高和推广国内的CRC技术，让相关人员能根据实际需要，灵活地采用CRC方法进行检错而撰写的。

1 有关符号的约定

模2除法就是在除的过程中用模2减法来减。模2加或模2减就是异或，结果都相同。本论文用“⊕”表示模2加，用“^” 表示异或，用“mod”表示求模。

2 分析研究按模2mod的相关性能

1）设信息码段为 h1h2h3h4h5h6H，生成多项式 g（x）的代码为11021H，分析研究计算CRC码的校验码段的过程。

设 （h1h2h3h4h5h6，0000H）按模 2mod（11021H）= （m3m2m 1m0H）。

如果先求出（h1h2，0000 H）按模 2mod （11021H）= （r3r2 r1r0H）

那么 [（h3h4h5h6，0000H）⊕（r3r2r1r0，0000 H）]按模 2 mod（11021H）= （m3m2m1m0H）。

如果先求出 [（h3h4，0000H）⊕（r3r2， 0000 H）]按模2mod（11021H）=（d3d2d1d0H）

那么[（h5h6，0000H）⊕（d3d2，0000 H）]按模 2mod （11021H）⊕（d1d0，00H） = （m3m2m1m0H）。

2）分析研究（h1H⊕h2H，0000H）按模 2mod（11021H）

设（h1H）=（a3a2a1a0B），（h2H）=（b3b2b1b0B），则

（h1H⊕h2H，0000H）按模 2mod （11021H）[1]

=（a3×219）B 按模 2mod （11021H）⊕

（a2×218）B 按模 2mod （11021H）⊕

（a1×217）B 按模 2mod （11021H）⊕

（a0×216）B 按模 2mod （11021H）⊕

（b3×219）B 按模 2mod （11021H）⊕

（b2×218）B 按模 2mod （11021H）⊕

（b1×217）B+（b0×216）B

可见， 如果 a3和 b3、a2和 b2、a1和 b1或 a0和 b0这 4对二进制数中，哪一对中的两个二进制数相等，则这一对二进制数对余数的作用就抵消了。

3 求CRC码的软件设计

在本论文的内容2中得到的结论非常重要，由此可以研制出用C语言编程求CRC校验码段的各种方法，在下面列举3种方法。

1）方法 1[2－4]

typedef unsigned char uchar；

typedef unsigned int uint；

code uchar crcbuff[]={0xe3，0xd2，0x0d，0x06，0x00，0x00，0x00，0x00}；

uint crc； //CRC码

uint crc16l（uchar*ptr，uchar len）；

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为数据长度（数据元素的个数，8个字节数）*/

{

uchar i；

while（len－－）

{

for（i=0x80； i； i＞＞=1）

{

if（（crc&0x8000） ^（*ptr&i）） {crc＜＜=1； crc^=0x1021；}

//生成多项式CRC－CCITT=X16+X12+X5+1对应的代码为11021

else crc＜＜=1；

}

ptr++；

}

return（crc）；

}

执行结果 crc=0x5f1d；

如想验证是否正确，可在程序中改 。

code uchar crcbuff_fan_result[]={0xe3，0xd2，0x0d，0x06，0x00，0x00，0x00，0x00，0x1d，0x5f}；

ptr=crcbuff_fan_result；

crc=crc16l（ptr，10）；

执行结果 crc=0；符合 CRC校验的原理。

此程序的难点在于把移位前crc的Bit15与数据对应的Bit（即*ptr&i）做XOR运算，根据此结果来决定是否执行crc^=0x1021；两次异或运算与原值相同。

2）方法 2:查表法[5－7]

下面给出半字节查表的处理程序。

typedef unsigned char uchar；

typedef unsigned int uint；

code uint crc_ba[16]={

0x0000， 0x1021， 0x2042， 0x3063， 0x4084， 0x50a5，0x60c6， 0x70e7， 0x8108， 0x9129， 0xa14a， 0xb16b， 0xc18c，0xd1ad， 0xe1ce， 0xf1ef，

}；

uint bancrc（uchar*ptr，uchar len）

{

uchar da； uint temp；

while（len－－!=0）

{temp=crc；

temp＞＞=12；

da=（uchar）temp； //

crc ＜＜=4；

crc^=crc_ba[da^（*ptr/16）]；

da= （（uchar）（crc/256）/16）；

crc ＜＜=4；

crc^=crc_ba[da^（*ptr&0fh）]；

ptr++；

}

return（crc）；

}

3）方法 3[3，8－9]

typedef unsigned char uchar；

typedef unsigned int uint；

uint reg；

uint crcdsp（uint reg， uchar data）

//reg为上次求得的CRC值，data为将要处理的8 bit数据流

{

uint msb；//保存reg将移出的最高1 bit信息。

uint data1；//保存 data的信息，但 data1为 16 bit。

uint gx=0x8005，i=0；/*i为左移次数，gx为生成多项式*/

data1= （uint）data；

data1 ＜＜=8；

reg=reg^data；

do

{

msb=reg&0x8000；

reg=reg＜＜ 1；

if（msb==0x8000）

{

reg=reg^gx；

}

i++；

}

while（i＜ 8）；

return （reg）；

}

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

上面提出的3种方法经过上机实验均证明正确可行，各有其特点。

4 结束语

本文创新点：找出了系数为1 bit二进制数的多项式按2模mod运算的新规律，根据按2模mod运算的这些性质，提出了计算任意长度CRC校验码的多种算法，并给出了具体实现这些算法的源程序。文中提出的CRC校验码的多种算法，可根据计算机的特点，灵活地应用在不同的工程当中。实践证明，该算法正确可靠，可以降低差错效验的成本，提高差错效验的效率。

[1]苗长云.现代通信原理及应用[M].北京:电子工业出版社，2005.

[2]陶亚雄.现代通信原理[M].北京:电子工业出版社，2003.

[3]王新梅，肖国镇.纠错码－原理与方法[M].西安：西安电子科技大学出版社，2001.

[4]Cunningham D G，PH.D，Lane W G，et al.千兆以太网[M].北京：清华大学出版社，2000.

[5]黄军.用Dephi编写串口通信程序[M].北京：人民邮电出版社，2001.

[6]朱荣华.一种CRC并行计算原理及实现方法[J].电子学报，1999，27（4）:143-145.ZHU Rong-hua.The principle and realization of a parallel computing method [J].Chinese Journal of Electronics，1999，27（4）:143-145.

[7]黄月江.信息安全保密：现代与未来战争的信息卫士[M].北京：国防工业出版社，2008.

[8]杨义先.现代密码新理论[M].北京：科学出版社，2002.

[9]谭方勇.网络安全技术实用教程 [M].重庆：重庆出版社，2000.