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

薅第聿2卷第腿3期华北科技学院学报袅2005年肄9月蝿羆羄循环冗余校验算法分析和实现①蒄蕿杜杏菁肈②莆,刘春梅袃芀聿(华北科技学院计算机系蒅,北京东燕郊莂101601)羀袆摘要袇:在网络中传输报文时螂,噪声干扰或传输中断等因素往往使接收端收到的报文出现错码。为了螁及时可靠地把报文传输给对方并有效地检测错误羈,需要采用差错控制。循环冗余校验羅CRC(CyclicRedun2蒅dancyCheck)是由分组线性码分支而来蒁,其主要应用是二元码组。循环冗余校验罿CRC编码简单且误判概肄率很低袄,在通信系统中得到了广泛的应用。文中详细介绍了循环冗余校验芁CRC的差错控制原理及其实现螇方法。蒆关键词芄:循环冗余校验羂;异或运算袈;模薄2运算螃中图分类号螂:TP30116 文献标识码衿:A 文章编号羇:1672-7169(2005)03-0105-03膃蒃1 概述蚇肅薂盾。若要求快速罿在数字通信系统中可靠与快速往往是一对矛螈,则必然使得每个数据码元所占膄的时间缩短、波形变窄、能量减少羁,从而在受到干虿扰后产生错误的可能性增加袀,传送信息的可靠性薆下降。若是要求可靠蚅,则使得传送消息的速率变蒀慢。因此蚇,如何合理地解决可靠性与速度这一对蚄矛盾是正确设计一个通信系统的关键问题之一。膄为保证传输过程的正确性膀,需要对通信过程进行蚈差错控制。实现检错功能的差错控制方法很多有肇奇偶校验、校验和检测、重复码校验、恒比码校验、薃行列冗余码校验等羀,这些方法都是增加数据的冗螀余量膅,将校验码和数据一起发送到接收端。接收羃端使用校验码对数据进行校验。但这些方法都有蚁各自的缺点薇,误判的概率比较高。循环冗余校验蒇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)的首位和最后一位的莂系数必须为羀1。袆袇肆3 CRC校验码的算法分析羅膂艿CRC校验码的编码方法是用待发送的二进虿制数据螅t(x)除以生成多项式芃g(x),将最后的余莈数作为腿CRC校验码。其实现步骤如下蒅:肁蚀1)设待发送的数据块是薈m位的二进制多项芆式膂t(x),生成多项式为袈r阶的羇g(x)。在数据块羆的末尾添加膃r个膁0,数据块的长度增加到蒇m+r螇位羁,对应的二进制多项式为艿xrt(x)。袆②作者简介膃:杜杏菁肂,女蒈,河北人芅,硕士研究生羃,华北科技学院计算机系教师。-. 第袁2卷第袈3期华北科技学院学报莈2005年蒄9月羂芁成了可以被袇g(x)除尽的膄m+r位二进制多项式羄xrt′(x),所以解码时可以用接收到的数据去除荿g图芇1羅螁螂除数次数被除数/g(x)/结果余数蚆0蚅1001000111000000袂10011袀0000100111000000肆100111000000莆1