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

Forpersonaluseonlyinstudyandresearch;mercialuse蒆第膅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位蚁二进制数膇可以表示为膄:1x2+0x6+1x5芁肂+1x4+0x3+1x2+0x+1,该系数除以发送方和衿①膆收稿日期芁:20芈接收方预先约定好的生成多项式莇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)。蚆②作者简介肄:杜杏菁肂,女肁,河北人虿,硕士研究生膄,华北科技学院计算机系教师。-(x)除尽的蒄m+r位二进制多项式莂xrt′(x),所以解码时可以用接收到的数据去除蒀g图聿1蒄螂袈除数次数被除数/g(x)/结果余数螇0薄10000000膃10011薀00000000薆0000蚄1