循环冗余校验的原理及软件实现

1、天津轻工业学院学报JOURNAL OF TIANJ IN INSTITUTE OF LIGHT INDUSTRY1999年第4期N o 41999循环冗余校验的原理及软件实现葛方晖(天津职业技术师范学院自动化系，天津300222)摘要：论述了循环冗余校验的数学模型以及编码原理，并给岀了软件的实现方法。关键词：数据通信；信道;循环冗余校验；生成多项式1中图法分类号：TN 911172文献标识码:A文章编号:1001 2456X (1999 ) 0420046 203石左?"弩E $ %陕也r> 自 F*""-t"站 吃由n Vi 4 i> U如

2、_其!_田r 工沖 PII i m',1 订' Vill1月fl v .丄£甘左谆PR INCIPL EOF CYCL IC RED UNDANCY CHECK广于啦苫胡VX利:iii AV*AND SOFTWARE REAL IZAT IONGE Fang-hu i(T ianjin V ocati onal and T echnical T eachers' Co liege, T ianjin 300222Ch ina)Abstract : T h is paper p resents the m athem aticalmodeland coding

3、p rinci p le ofcyclicredundancycheck , and show the softw are m plem entati on.Key words : D ata Comm unicati on ; Channel ; CyclicRedundancy Check ; Generato rPo lynomial在数据通信的过程中，由于信道传输特性不理想和加性噪声的影响，所收到的数字信号不可避免地会受到干扰，严重时发生误码，影响系统的工作。在接收端为了检查所收到的数 据是否正确，可采用多种检错方法。比如奇偶校验法，校验和法以及行列冗余码校验等，但都有一定缺乏。本文介

4、绍一种强有力的检错方法，即循环冗余校验，并将其成功地应用于无线 测控系统中，收到了令人满意的效果。1循环冗余校验的数学模型循环冗余校验简称循环码或CRC码(Cyclic Redundancy Check)，是一种高效能的检错和纠错码，在数据通信中应用甚广。循环码编码通过模 2运算来建立信息位和校验位之间的 约束关系。首先将所传数据看成高次多项式，把此多项式除以预先给定的生成多项式，其余 数作为校验位附加在所传数据的尾部一并传送，即在一个长度为n的码组中有k个信息和r个校验位。译码时用同样的生成多项式去除，若余数为零，则可判断收到的数据是正确的。S收稿日期：19992082103 作者简介：葛方

5、晖（19702，男（汉族），江苏人，讲师，硕士. 1994-2蚀9 ChiiKi Acadwnic Joumal blectrcuiit Publishing Hcu池，All right s rcscFvcd,cnk第4期葛方晖：循环冗余校验的原理及软件实现47假设待编码的k位信息是：M =(m k- i, m k- 2,m 2, m i, m o)它所对应的信息多项式是k- 1k- 2M (x) = m k- 1x + m k- 2x+2+ m 2x + m1x+ m0用xn- k乘M(x)得：n- kn- 1n- 2x M(x ) = m k- ix + m k- 2x+n- k+ 2+

6、 m 2x+n- k+ in- km ix + m ox用给定的(n, k)循环码生成多项式g (x)除xn k? M (x)得：x" k? M (x) = q(x)? g (x) + R (x)(1)式中q(x)和R(x)分别是除法的商式和余式。因为生成多项式g(x)是(n- k)次，所以R (x ) 一定是等于或小于(n- k- 1)次,即：R (x) =rn-k-ix"-" 1 +rn-k- 2- k- 2+ +r2x2+rix+ro由 式得 xn- k?M (x)+ R(x)= q(x)? g (x),上式表明 xn- k? M (x)+ R (x)是 g

7、(x) 的倍式，其次数等于或小于(n- 1)。所以xn- k? M (x)+ R (x)是g (x )生成的循环码的一个 码多项式,把xn- k? M (x) + R (x)展开得：xn-k?M (x) +n- 1n- 2R (x) = m k- 1 ? x + m k- 2 ? x +n- k+ 2n - k+ 1+ m 2x+ m 1 x此码多项式对应的码字是 所以码字是由不加改变的n- kn - k- 1n - k- 22+ m °x + n- k- 1x + n- k- 2x + +r?x+ 2x+ r°:(mk- 1, mk- 2,m 2, m 1 ,m o, r

8、n- k- 1, rn- k- 2r2, r 1, ro)k位信息码元，其后再附加(n- k)位校验码元组成的。在接收端，对收到的码字进行译码,即除以g (x)xn-k?M (x) + R (x) g (x)= q(x)? g (x) + R (x)+ R (x) g (x)=q (x) ? g (x ) g (x ) = q (x )若传输正确，则余数为零，当余数为非零时，判断数据传送有误，以达到数据通信的检错目的。例如：对于(7,3)循环码，待编码的信息为M = 101,生成多项式g (x)= x4+ x'+ x2+ 1, 则 M (x)= x2+ 1x7- 3? M (x)= x

9、4(x2+ 1)= x6+ x4,其码字为1010000,运用长除法，所以码字为 1010011,传送时将信息位与校验位一同发出，在接收方译码时，也采用相同的长除法。若余数为零，则接收正确。2生成多项式g(x)的种类用于进行CRC除法的生成多项式有多种，推荐使用的有3种：(1)CRC212：用于6位字符的同步系统中，校验码组长12位,生成多项式是g(x)= x12+ x11+ x3+ x2+ x+ 1它能检测出长度在12位以内的突发差错。(2)CRC216：用于8位字符的同步系统，校验码组长16位,生成多项式是g (x) = x16+ x15+ x 2+ 1它能检测出全部16位以下和16位长的

10、突发差错，以及99%的长度大于16位的突发差错。(3) CRC2DCITT：也是对8位字符进行计算，产生的校验码组长16位,生成多项式是16g (x)= x +12其检错能力同CRC216。© 994-20ChinaJoumal Electronic PublishiiigAH rights reserved,48?天津轻工业学院学报1999年10月3 CRC校验的软件实现在实现循环码的编码时，大体有两种方法，即硬件法 和软件法。硬件法采用除法电路来完成，该除法电路是一 个根据生成多项式而形成的带反馈连接的移位寄存器，在很多通信设备中已广泛采用。但在有些系统中，为了简化硬件设备，往往

11、采用软件的方法来实现。循环码编码在软件实现过程中，多项式的除法运算是通过右移移位和异或运算来完成的。在本系统中采用 的生成多项式是CRC216,即g(x)= x16+ x15+ x?+ 1。由 于在进行异或运算的过程中，其最高位的运算结果是已 知的，即当信息位多项式右移，移出位为“1”时与生成多 项式进行异或运算，其运算结果必定为 0,因此当信息多 项式移出位为“1 ”时，移出位可不参加运算，生成多项式 的最高位也不参加运算，也不需存储，于是两个字节就可 以表达一个17比特的生成多项式，所以参与异或运算的 生成多项式只用两个字节表示 。对一帧数据进行 CRC编码的软件流程见图1。流程图中，3字

12、节右移一位操作，是将Ro的最低位 移出，R1的最低位移入 Ro的最高位，R2的最低位移入 R1的最高位，R2的最高位补0,之所以这样做，是为了保 证R1R0与# A 001H异或时，R1的最高位总是信息位 ， 当右移8次后，R2中的数值为0,而R1R0中为余数，完成 一个字节的运算。此时再取数据区中的下一个数据，送入R 2中,继续上述操作，直到数据长度减为 0时为止，R 1R 0 中即为CRC校验位，也就是这一帧数据的余数位。解码过程与编码过程相似，操作时两个字节的 CRC 位不清0,直接参与运算，当信息字节长度减为 0时, R1R0的值为0,则表示接收正确，否则有误。需要说明的是，由于右移操作是把信息字节中的最 低位当作最高位进行运算，则生成多项式也需按逆序运将一林据未尾 境加两牛字节務这圖牛字节淸0 做为将素的CRC指针常向数据区首址 井将所揩数据"阳数据指卡1 .将所三字节右移一悅 蒋出悅为用的晟低位将生馬与# A001H异或移位次数喊1檢度宇节诫1加曲中的数值即対 CRC校验位图1 CRC编码流程图算,即 x15+ x2+ 1 的 16进制形式为(1000 0000 0000 0101)B= 8005 H,其逆序为(1010 00000000 0001)b= A 001 H。正序和逆序的性质是一样的，使用哪种方式由与之通信的上位机