CRC错误检测原理.docVIP

13.1 CRC错误检测原理 在纠错编码代数中，把以二进制数字表示的一个数据系列看成一个多项式。例如，二进制数字序用多项式可以表示成： =表示代码的位置，或某个二进制数位的位置，前面的系数ai表示码的值。若ai是一位二进制代码，则取值是0或1。 在模2多项式代数运算中定义的运算规则有： 2多项式的加法和减法： 2运算来说，代码多项式的加法和减法运算所得的结果相同。所以在做代码多项式的减法时，可用做加法来代替做减法。 如果一个k位的二进制信息代码多项式为，再增加(n－k)位的校验码，那么增加(n－k)位之后，信息代码多项式在新的数据块，如图13-01所示。 13-01 信息代码结构 如果用一个校验码生成多项式去除代码多项式，得到的商假定为，余式为，则可写成 因为模2多项式的加法和减法运算结果相同，所以又可把上式写成： 是能够被校验码生成多项式除尽的，即它的余项为0。 CD盘中的q通道和软磁盘存储器中使用的CRC校验码生成多项式是 =100010000000100001(B)=11021(H) 假定要写到盘上的信息代码为 =4D6F746F (H) 由于增加了2个字节共16位的校验码，所以信息代码变成: 4D6F746F0000(H)。 CRC检验码计算如下： B994(H)就是CRC校验码。把信息代码写到盘上时，将原来的信息代码和CRC码一起写到盘上。在这个例子中，写到盘上的信息代码和CRC码是4D6F746F B994, 4D6F746F B994 CRC码 11021(H)除尽的。 CRC码生成多项式去除这块数据，相除后得到的两种可能结果是：①余数为0，表示读出没有出现错误；②余数不为0，表示读出有错。 CD-ROM中也采用了相同的CRC检错。CD-ROM扇区方式01中，有一个4字节共32位的EDC字域，它就是用来存放CRC码。不过，CD-ROM采用的CRC校验码生成多项式与软磁盘采用的生成多项式不同，它是一个32阶的多项式, CRC码时用的数据块是从扇区的开头到用户数据区结束为止的数据字节，即字节0～2063共2064个字节。在EDC中存放的CRC码的次序如下： EDC： x24x31 x16－x23 x8－x15 x0－x7 字节号： 2064 2065 2066 2067 用C语言实现CRC校验计算?xml:nmespce prefix = o ns =urn:schems-microsoft-com:office:office /Clcultes CRC quickly using the tble-lookup method作　　者：董云 YUN DONG工作单位：黄埔海关技术处工程师通讯地址：广州市经济技术开发区志诚大道海关大楼电话号码：020邮政编码：510730电子邮件： dy168@163.net摘 要：简述CRC算法原理，给出一种新颖快速的查表计算方法，并给出用C语言编写的算法源程序。关键词：CRC、多项式、查表法　　在编写数据传输程序时，数据容错是一个非常重要的问题。循环冗余位校验（Cyclicl Redundncy Check英文简称CRC）是目前运用非常广泛的一种数据容错方法，在数据传输，数据压缩等领域运用极其广泛。CRC的实现分为硬件和软件两种方法，其中软件实现的关键在于计算速度。如果单纯模拟硬件实现方法，则计算速度较慢。笔者在编制一个数据通讯软件中，运用了一种新颖的查表法计算CRC，速度很快，效果极佳。　　首先介绍其原理，如果每次参与CRC计算的信息为一个字节，该信息字节加到16位的累加器中去时，只有累加器的高8位或低8位与信息字节相互作用（异或），相互作用（异或）的结果记为组合值，那么累加器中的新值等于组合值加上（按模2异或）累加器中未改变的那一半即为新的CRC值。　　组合值只有256种可能，因此可利用硬件模拟算法先算好它们的CRC值预先填入一张表中，该表的每一单元对应相对值的CRC。这样就可以通过查表法来计算CRC值，以便大大提高CRC运算的速度。下面给出用Ｃ语言编制的计算程序。　　首先将CRC生成多项式及CRC值表定义为一个头文件CRC.H：　　#define CRC_CCITT 0x1021 //CCITT多项式#define REV_CCITT 0x8408 //反转CCITT多项式#define CRC16 0x8005 //CRC16多项式#define REV_CRC16 0x001 //反转CRC16多项式unsigned short crc_tble[256];　//CRC值表