循环冗余校验算法分析实现.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