循环冗余校验算法分析实现.doc

循环冗余校验算法分析实现.doc循环冗余校验算法分析实现第2卷第华北科技学院学报3期2005年循环冗余校验算法分析和实现①杜杏菁(华北科技学院计算机系,北京东燕郊101601)摘耍:在网络屮传输报文时,噪声干扰或传输中断等因素往往使接收端收到的报文出现错码。为了及时可靠地把报文传输给对方并有效地检测错误,需耍采用差错控制。循环冗余校验CRC(CyclicRedun2dancyCheck)是由分组线性码分支而来,其主耍应用是二元码组。循环冗余校验CRC编码简单且误判概率很低,在通信系统中得到了广泛的应用。文中详细介绍了循环冗余校验CRC的差错控制原理及其实现方法。关键词:循环冗余校验;异或运算;模2运算中图分类号:TP30116 文献标识码:A 文章编号:1672-7169(2005)03-0105-031概述盾。若要求快速在数字通信系统中可靠与快速往往是一对矛,则必然使得每个数据码元所占的时间缩短、波形变窄、能量减少,从而在受到干扰后产生错误的可能性增加,传送信息的可靠性下降。若是要求可靠,则使得传送消息的速率变慢。因此,如何合理地解决可靠性与速度这一对矛盾是正确设计一个通信系统的关键问题之一。为保证传输过程的正确性,需要対通信过程进行差错控制。实现检错功能的差错控制方法很多有奇偶校验、校验和检测、重复码校验、恒比码校验、行列冗余码校验等,这些方法都是增加数据的冗余量,将校验码和数据…起发送到接收端。接收端使用校验码对数据进行校验。但这些方法都有各自的缺点,误判的概率比较高。循环冗余校验CRC是由分组线性码分支而来,其主要应用是二元码组,编码简单且误判概率很低,在通信系统屮得到了广泛的应用。下面重点介绍了CRC校验的原理及其算法实现。2循环冗余校验码(CRC)原理CRC码检错是将被处理报文的比特序列当作一个二进制多项式A(x)的系数,如一个8位二进制数10110101可以表示为:1x2+0x6+1x5+1x4+0x3+1x2+0x+1,该系数除以发送方和①收稿日期:2005204220接收方预先约定好的生成多项式g(X)后,将求得的余数P(X)作为CRC校验码附加到原始的报文上,并一•起发给接收方。接收方用同样的g(x)去除收到的报文B(x),如果余数等于零,则传输无误;否则传输过程中出错,由发送端重发重新开始CRC校验,直到无误为止。上述校验过程中有儿点需注意:①在进行CRC计算时,采用二进制(模2)运算法,即加法不进位,减法不借位,其本质就是两个操作数进行逻辑异或运算:②在进行CRC计算前先将发送报文所表示的多项式A(x)乘以Xn,其中n为生成多项式g(x)的最高幕值。对二进制乘法来讲A(x)-Xn就是将A(x)左移n位,用来存放余数P(x),所以实际发送的报文就变为A(x)•Xn+p(X);③生成多项式g(X)的首位和最后一位的系数必须为lo3CRC校验码的算法分析CRC校验码的编码方法是用待发送的二进制数据t(x)除以生成多项式g(X),将最后的余数作为CRC校验码。其实现步骤如下1)设待发送的数据块是m位的二进制多项式t(x),生成多项式为r阶的g(x)o在数据块的末尾添加r个0,数据块的长度增加到m+r位,对应的二进制多项式为xrt(x)o②作者简介:杜杏菁,女,河北人,硕士研究生,华北科技学院计算机系教师。.1994-,3期 华北科技学院学报2005年9月成了可以被g(X)除尽的m+r位二进制多项式xrtz(x),所以解码时可以用接收到的数据去除g图1除数次数被除数/g(x)/结果余数01001000111000000100110000100111000000100111000000110011100000010011000001000000100000021000000100110001100检错的。同吋可以看做是由t(X)和CRC校验码的组合,所以解码时将接收到的二进制数据去掉尾部的r位数据,得到的就是原始数据。如果余数不为零,则在传输过程中肯定存在错误。许多CRC的硬件解码电路就是按这种方式进行(x),如果余数位零,则表示传输过程没有错误;(x)去除,求得余数为阶数为rT的二进制多项式y(x)o此二进制多项式y(x)就是t(x)经过生成多项式g(x)编码的CRC校验码。用以模2的方式减去y(x),得到二进制多项式xrt'(x)oxrtz(x)就是包含了CRC校验码的待发送字符串。从CRC的编码规则可以看出,CRC编码实际上是将代发送的m位二进制多项式t(x)转换为了更清楚的了解CRC校验码的编码过程下面用一个CRC24编码的例子来说明CRC的编码过程。设