资源描述：
《循环冗余校验算法分析实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、循环冗余校验算法分析实现 第2卷 第3期 华北科技学院学报 2005年9月循环冗余校验算法分析和实现 ①杜杏菁②,刘春梅(华北科技学院计算机系,北京东燕郊 101601)摘 要:在网络中传输报文时,噪声干扰或传输中断等因素往往使接收端收到的报文出现错码。为了及时可靠地把报文传输给对方并有效地检测错误,需要采用差错控制。循环冗余校验CRC(CyclicRedun2dancyCheck)是由分组线性码分支而来,其主要应用是二元码组。循环冗余校验CRC编码简单且误判概率很低,在通信系统中得到了广泛的应用。文中详细介绍了循环冗余校验CRC的差错控制原理及其实现方法。关
2、键词:循环冗余校验;异或运算;模2运算中图分类号:TP30116 文献标识码:A 文章编号:1672-7169(2005)03-0105-031 概述盾。若要求快速在数字通信系统中可靠与快速往往是一对矛,则必然使得每个数据码元所占的时间缩短、波形变窄、能量减少,从而在受到干扰后产生错误的可能性增加,传送信息的可靠性下降。若是要求可靠,则使得传送消息的速率变慢。因此,如何合理地解决可靠性与速度这一对矛盾是正确设计一个通信系统的关键问题之一。为保证传输过程的正确性,需要对通信过程进行差错控制。实现检错功能的差错控制方法很多有奇偶校验、校验和检测、重复码校验、恒比码校验、行列冗余码校验
3、等,这些方法都是增加数据的冗余量,将校验码和数据一起发送到接收端。接收端使用校验码对数据进行校验。但这些方法都有各自的缺点,误判的概率比较高。循环冗余校验CRC是由分组线性码分支而来,其主要应用是二元码组,编码简单且误判概率很低,在通信系统中得到了广泛的应用。下面重点介绍了CRC校验的原理及其算法实现。2 循环冗余校验码(CRC)原理CRC码检错是将被处理报文的比特序列当作一个二进制多项式A(x)的系数,如一个8位二进制数10110101可以表示为:1x2+0x6+1x5+1x4+0x3+1x2+0x+1,该系数除以发送方和①收稿日期:2005204220接收方预先约定好的生成多项式
4、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
5、(x);③生成多项式g(x)的首位和最后一位的系数必须为1。3 CRC校验码的算法分析CRC校验码的编码方法是用待发送的二进制数据t(x)除以生成多项式g(x),将最后的余数作为CRC校验码。其实现步骤如下:1)设待发送的数据块是m位的二进制多项式t(x),生成多项式为r阶的g(x)。在数据块的末尾添加r个0,数据块的长度增加到m+r位,对应的二进制多项式为xrt(x)。②作者简介:杜杏菁,女,河北人,硕士研究生,华北科技学院计算机系教师。.1994-2009ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved
6、.http://www.cnki.net 第2卷 第3期 华北科技学院学报 2005年9月成了可以被g(x)除尽的m+r位二进制多项式xrt′(x),所以解码时可以用接收到的数据去除g图1除数次数被除数/g(x)/结果余 数010010001110000001001100001001110000001001110000001100111000000100110000010000001000000210000001001100011001100检错的。同时可以看做是由t(x)和CRC校验码的组合,所以解码时将接收到的二进制数据去掉尾部的r位数据,得到的就是原始
7、数据。如果余数不为零,则在传输过程中肯定存在错误。许多CRC的硬件解码电路就是按这种方式进行(x),如果余数位零,则表示传输过程没有错误;4 CRC码的电路实现4.1 硬件电路的特点2)用生成多项式g(x)去除,求得余数为阶数为r-1的二进制多项式y(x)。此二进制多项式y(x)就是t(x)经过生成多项式g(x)编码的CRC校验码。3)用以模2的方式减去y(x),得到二进制多项式xrt′(x)。xrt′(x)就是包含了CRC校验码的待发送字符串。从CRC的
