CRC算法及工作原理

1、crc算法及工作原理crc校验有用程序库 在数据存储和数据通讯领域，为了保证数据的正确，就不得不采纳检错的手段。在诸多检错手段中，crc是最闻名的一种。crc的全称是循环冗余校验，其特点是:检错能力极强，开销小，易于用及检测实现。从其检错能力来看，它所不能发觉的错误的几率仅为0.0047%以下。从性能上和开销上考虑，均远远优于奇偶校验及算术和校验等方式。因而，在数据存储和数据通讯领域，crc无处不在：闻名的通讯协议x.25的fcs(帧检错序列)采纳的是crc- ccitt，winrar、nero、arj、lha等压缩工具软件采纳的是crc32，磁盘驱动器的读写采纳了crc16，通用的图像存储格

2、式gif、tiff等也都用crc作为检错手段。crc的本质是模-2除法的余数，采纳的除数不同，crc的类型也就不一样。通常，crc的除数用生成多项式来表示。最常用的crc码的生成多项式如表1所示。10a08800.gif;表1.最常用的crc码及生成多项式因为crc在通讯和数据处理软件中常常采纳，笔者在实际工作中对其算法举行了讨论和比较，总结并编写了一个具有最高效率的crc通用程序库。该程序采纳查表法计算crc，在速度上优于普通的挺直仿照硬件的算法，可以应用于通讯和数据压缩程序。算法通常的crc算法在计算一个数据段的crc值时，其crc值是由求解每个数值的crc值的和对crc寄存器的值反复更新

3、而得到的。这样，求解 crc的速度较慢。通过对crc算法的讨论，我们发觉:一个8位数据加到16位累加器中去，惟独累加器的高8位或低8位与数据相作用，其结果仅有256种可能的组合值。因而，我们可以用查表法来代替反复的运算，这也同样适用于crc32的计算。本文所提供的程序库中，函数crchware是普通的16位 crc的算法;mk-crctbl用以在内存中建立一个crc数值表;crcupdate用以查表并更新crc累加器的值;crcrevhware和 crcrevupdate是反序算法的两个函数;buildcrctable、calculateblockcrc32和updatecharactercr

4、c32用于crc32的计算。/* crc.ccrc程序库 */define crcccitt 0x1021define ccitt-rev 0x8408define crc16 0x8005define crc16-rev 0xa001define crc32-polynomial 0xedb88320l/* 以上为crc除数的定义 */define nil 0define crcupdate(d,a,t)*(a)=(*(a)8)(t)(*(a)8)(d);define crcupdate16(d,a,t)*(a)=(*(a)8(t)(*(a)(d)&0x00ff)/* 以上两个宏可以

5、代替函数crcupdate和crcrevupdate */include include include /* 函数crchware是传统的crc算法，其返回值即crc值 */ unsigned short crchware(data,genpoly,accum)unsigned short data;/* 输入的数据 */unsigned short genpoly;/* crc除数 */unsigned short accum;/* crc累加器值 */static int i;data=8;for(i=8;i0;i-)if(dataaccum)&0x8000)accum=(acc

6、um1)genpoly;elseaccum=1;data=1;return (accum);/* 函数mk-crctbl利用函数crchware建立内存中的crc数值表 */unsigned short *mk-crctbl(poly,crcfn);unsigned short poly;/* crc除数-crc生成多项式 */runsigned short (*crcfn)();/* 指向crc函数(例如crchware)的指针 */* unsigned short */malloc(); */unsigned short *crctp;int i;if(crctp=(unsigned sh

7、ort*)malloc(256*sizeof(unsigned)=0)return 0;for(i=0;i256;i+)crctp=(*crcfn)(i,poly,0);return crctp;/* 函数mk-crctbl的用法范例 */if(crctblp=mk-crctbl(crcccitt,crchware)=nil)puts("insuff memory for crc lookup table.n");return 1; */* 函数crcupdate用以用查表法计算crc值并更新crc累加器值 */void crcupdate(data,accum,crcta

8、b)unsigned short data;/* 输入的数据 */unsigned short *accum;/* 指向crc累加器的指针 */unsigned short *crctab;/* 指向内存中crc表的指针 */static short comb-val;comb-val=(*accum8)data;*accum=(*accum8)crctabcomb-val;/* 函数crcrevhware是传统的crc算法的反序算法，其返回值即crc值 */unsigned short crcrevhware(data,genpoly,accum)unsigned short data;un

9、signed short genpoly;unsigned short accum;static int i;data=1;for(i=8;i0;i-)data=1;if(dataaccum)&0x0001)accum=(accum1)genpoly;elseaccum=1;return accum;/* 函数crcrevupdate用以用反序查表法计算crc值并更新crc累加器值 */void crcrevupdate(data,accum,crcrevtab)unsigned short data;unsigned short *accum;crc检验办法的工作原理循环冗余码crc在发送端编码和接收端校验时，都可以利用事先商定的生成多项式g(x)来得到，k位要发送的信息位可对应一个(k-1)次多项式k(x)，r位冗余位对应于一个(r-1)次多项式r(x)，由k位信息位后面加上r位冗余位组成的n=k+r的码字则对应于一个(n-1)次多项式 t(x)x×k(x)+r(x)。也即在发送端产生一个循环冗余码，附加在信息位后面一起发送到接收端。接收端的检验过程就是将接收到的码字多项式除以 g(x)，若余式为零则认为传输无差错;若余式不为零则传输有差错。crc - crazy roller