循环冗余校验算法分析实现【荐】.docVIP

　第 2卷　第 3期　　　　　　　　华北科技学院学报　　　　　　 2005年 9月 循环冗余校验算法分析和实现　① 杜杏菁 ② ,刘春梅 (华北科技学院计算机系 ,北京东燕郊　 101601) 摘　要 :在网络中传输报文时 ,噪声干扰或传输中断等因素往往使接收端收到的报文出现错码。为了 及时可靠地把报文传输给对方并有效地检测错误 ,需要采用差错控制。循环冗余校验 CRC (Cyclic Redun2 dancy Check)是由分组线性码分支而来 ,其主要应用是二元码组。循环冗余校验 CRC编码简单且误判概 率很低 ,在通信系统中得到了广泛的应用。文中详细介绍了循环冗余校验 CRC的差错控制原理及其实现 方法。 关键词 :循环冗余校验 ;异或运算 ;模 2运算 中图分类号 : TP30116　　文献标识码 :A　　文章编号 :1672 -7169 (2005) 03 -0105 -03 1　概述 盾。若要求快速 在数字通信系统中可靠与快速往往是一对矛 ,则必然使得每个数据码元所占 的时间缩短、波形变窄、能量减少 ,从而在受到干 扰后产生错误的可能性增加 ,传送信息的可靠性 下降。若是要求可靠 ,则使得传送消息的速率变 慢。因此 ,如何合理地解决可靠性与速度这一对 矛盾是正确设计一个通信系统的关键问题之一。 为保证传输过程的正确性 ,需要对通信过程进行 差错控制。实现检错功能的差错控制方法很多有 奇偶校验、校验和检测、重复码校验、恒比码校验、 行列冗余码校验等 ,这些方法都是增加数据的冗 余量 ,将校验码和数据一起发送到接收端。接收 端使用校验码对数据进行校验。但这些方法都有 各自的缺点 ,误判的概率比较高。循环冗余校验 CRC是由分组线性码分支而来 ,其主要应用是二 元码组 ,编码简单且误判概率很低 ,在通信系统中 得到了广泛的应用。下面重点介绍了 CRC校验 的原理及其算法实现。 2　循环冗余校验码 ( CRC)原理 CRC码检错是将被处理报文的比特序列当 作一个二进制多项式 A (x)的系数 ,如一个 8位 二进制数 以表示为 :1 x 2+0 x 6+1 x 5 +1 x 4+0 x 3+1 x 2+0 x +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)。 ②作者简介 :杜杏菁 ,女 ,河北人 ,硕士研究生 ,华北科技学院计算机系教师。 . 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved.  　第 2卷　第 3期　　　　　　　　华北科技学院学报　　　　　　 2005年 9月 成了可以被 g( x)除尽的 m + r位二进制多项式 x rt′(x) ,所以解码时可以用接收到的数据去除 g 图 1 除数次数被除数/ g ( x) /结果余　　数 0 1 001000111000000 1 0011 0 000100111000000 100111000000