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

第 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位二进制数 10110101可以表示为 :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。 3CRC校验码的算法分析 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 1 1 00111000000 1 0011 0 00001000000 1000000 2 1 000000 1 0011 0 001100 1100检错的。同时可以看做是由 t( x)和 CRC校验码的组合 ,所以解码时将接收到的二进制数据去掉尾部的 r位数据 ,得到的就是原始数据。如果余数不为零,则在传输过程中肯定存在错误。许多CRC的硬件解码电路就是按这种方式进行(x) ,如果余数位零 ,则表示传输过程没有错误 ;4CRC码的电路实现 4. 1硬件电路的特点2)用生成多项式 g( x)去除 ,求得余数为阶数为 r -1的二进制多项式 y( x)。此二进制多项式 y( x)就是 t( x)经过生成多项式 g( x)编码的 CRC校验码。 3)用以模 2的方式减去 y(x) ,得到二进制多项式 x rt( x)。 x rt( x)就是包含了 CRC校验码的待发送字符串。从 CRC的编码规则可以看出 , CRC编码实际上是将代发送的 m位二进制多项式 t( x)转换为了更清楚的了解 CRC校验码的编码过程 ,下面用一个 CRC24编码的例子来说明 CRC的编码过程。设待发送的数据 t( x)为 12位的二进制数据 100100011100 ;CRC24的生成多项式为 g( x) = x 4+ x +1 ,阶数 r为 4,即 10011。首先在 t( x)的末尾添加 4个 0构成 x 4 t(x) ,数据块就成了 1001000111000000。然后用 g( x)去除 x 4 t(x) ,不用管商是多少 ,只需要求得余数 y( x)。图 1给出了除法过程。在网络中为了产生 CRC码 ,硬件电路除了具有复位和时钟信号以外 ,还需要以下两个控制信号的参与 :填充位解除信号 destuff ,它的有效逻辑值是 1; CRC检验的使能信号 enable ,有效逻辑也为 1。该硬件电路的特点是采用选择器和反相器代替传统设计中用的异或门 ,既实现了比较功能 ,又降低了生产成本。 4. 2硬件电路图图 2中需要说明的几点如下 :使能信号和填充位解除信号省略 ; crcnxt代表的逻辑值为输入报文序列和 CRC寄存器的最高位异或的结果 ;标号 014所指示的为 15位 CRC寄存器 ,上升沿触发 ;标号 16所指示的为选择器和反相器的组合逻辑 ,实现异或功能。图 2产生 CRC校验码的硬件电路 4. 3电路工作过程高位异或 ,结果分别左移一位 ;其它未进行异或操从以上分析可知 :当 enable = 0时 ,CRC清 作的寄存器位值也分别左移一位 ,直到报文的每0;当 enable = 1、destuff = 1时 ,进行正常 CRC一位都移入 CRC寄存器为止 ,此时寄存器中的值计算 ;当 enable = 1而 destuff = 0时 ,正在解除取为计算得到的 CRC码。填充 ,数据暂停传送。如果报文的比特序列长度为 16 ,则需要左移 在各个控制信号均有效时 ,输入报文的每一16次才能对报文的每一位均进行处理。如果以 位都是和 CRC寄存器的最高位相异或后移入最Ck表示 CRC寄存器的第 k位位值、 Ck表示移位低位 ,同时寄存器的第 13、9、7、6、3、2位均和其最后的第 k位位值 (k=0,1,2,3.15) ,则移位 106. 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. 第 3期杜杏菁等 :循环冗余校验算法分析和实现规律见表 1。表 1移位规律表 C14= C13crcnxt C13= 12 C12= C11 C11= C10 C10= C9crcnxt C6= C5 C9= C8 C5= C4 C8= C7crcnxt C4= C3crcnxt C7= C6crcnxt C3= C2crcnxt C2= C1 C1= C0 C0= crcnxtdatain 5CRC校验码的软件实现 CRC校验用软件实现起来非常方便。这里给出用 Verilog HDL实现 CRC码 module crc (clk ,rst ,enable ,destuff ,datain ,crc) ; input clk; input rst ; input enable; end endmodule 6仿真结果假设发送的是一个标准格式的远程帧 ,需求output14:0crc; input destuff; input datain; 的数据字节为 8,标识符序列为 10101011000 ,则对上述程序仿真后的波形如图 4所示。 Crc序列reg 14 :0 crc ; 从第 20位开始输出。wire crcnxt =dataincrc14; always (posedge rst or posedge clk) begin if (rst)crc =0; else if (enable & & destuff) begin if (crcnxt) crc = crc15h4599 ; else crc =crc13:0,1b0 ; end 图 4CRC仿真波形图 CRC校验码的检错能力很强 ,并且由于 CRC地一种很好的手段。码检错的软件和硬件实现都很简单 ,因而被广泛参考文献 : 地应用于各类数据校验中。 CRC码检错是提高1席振元 ,刘士杰 .计算机网络实用技术 M.北数据传输质量、高效检错的有力手段。 京 :煤炭工业出版社 , 2004 . 2于峰 .计算机网路与数据通信 M.北京 :中国CRC校验由于实现简单 ,检错能力强 ,被广水利水电出版社 2003. 泛使用在各种数据校验应用中。占用系统资源3王新梅 ,肖国镇 .纠错码 -原理与方法 M.西少 ,用软硬件均能实现 ,是进行数据传输差错检测安 :西安电子科技大学出版社 ,2001. Research of CRC Arithmetic in Software and Hardware DU Xing2jing , LIU Chun2mei (Computer Department of North China Institute of Science &Technology , Beijing101601) Abstract : Noise and disturb ofen made the message mistaking when transferring it in network. . In order to transfer the message in time and reliably and check the inaccurate message ,the control of the mistake is must need. The control principle of CRC (Cyclic Redundancy Check) was introduce particularly in the paper ,the hardware circuit an