crc编码算法研究与实现

《crc编码算法研究与实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据西北大学学报(自然科学版)2006年12月，第36卷第6期，Dec．，2006，V01．36，No．6JoumalofNonhwestUniversity(NaturalScienceEdition)CRC编码算法研究与实现李宥谋1，房鼎益2(1．西安邮电学院专用集成电路设计中心，陕西西安710061；2．西北大学信息科学与技术学院，陕西西安710061)摘要：目的研究cRc编码中模2除法运算的规则，解决cRC编解码过程中的延时问题。方法对CRC编码中模2除法进行变换，得出一种无延时、简单、实用的编码算法。结果采用Verilog语言设计一个经过验

2、证的16位无延时的cRC一16软核。结论该软核可直接应用到具有CRC．16校验电路的收发器中。关键词：CRC码；CRC．16；Ve订109HDL语言中图分类号：TN911．22文献标识码：A文章编号：1000-274X(2006)06一0895旬4在串行数据传输中广泛采用循环冗余校验码CRC(cyclicredundancycheck)来测试一个数据包是否有错误发生，虽然循环冗余校验码的理论较为复杂⋯，但实现检错的基本原理十分简单。在m位信息码后再拼接r位的校验码，整个编码长度为n位，因此这种编码又叫(n，南)码。对于一个给定的(n，庇)码，可以证明存在

3、一个最高次幂为挖一露=r的多项式g(戈)。根据g(z)可以生成后位信息的校验码，而g(石)叫做这个CRc码的生成多项式。校验码的具体生成过程为：假设发送信息用数据多项式m(戈)表示，将m(z)左移n一五位，则可表示成，n(z)×2”‘。这样m(尤)的右边就会空出n一露位，即校验码的位置。通过m(戈)×2”‘除以生成多项式g(戈)得到的商Q(戈)和余数r(戈)，其中余数r(戈)就是校验码。即／、一^，、丛孕善}=Q(戈)+兴。(1)gL石／gk咒／在发送端发送数据时余数加到信息码之后一同发出，将一组信息码和余数组成的数据块称为一个码元，设为r(戈)，则有丁

4、(石)=m(咒)×2“一8+r(戈)。(2)在接收端任一组多项式r(z)都应被生成多项式g(戈)整除，如果传输中未发生错误，则接收码元与发送码元相同，故接收的码元必定能被g(戈)整除；若码元在传输中发生错误，则接收的码元可能除不尽而有余数，因此我们就以余数是否为零来判断接收码元中有无错误。可能有错误的码元正好也被g(咒)整除，这是CRC校验无力消除的，但通过选择多项式g(戈)和增加冗余位数，使余数r(戈)多项式的位数增多，来降低发生这种错误的概率。lCRC码的计算方法cRC编码采用的除法运算是模2除法悼J，它与算术除法类似，但每一位除(减)的结果不影响其

5、他位，即不向上一位借位，故实际上就是异或。这可以由移位寄存器和异或门组成，例如一个生成多项式g(z)=茗6+菇5+z4+z3+i=lI100i，数据流，nf石1=戈13+石11+戈10+z7+戈4+戈3+戈+1=101100l0011011，(m(z)×26)除以g(x)得至4Q(戈)：戈13+戈j2+z1I+戈8+戈7+戈6+戈4+戈3+戈2+戈+l=11100111011111，余数r(咒)=戈5+戈4+戈2+戈+1=110111。按照一般的模2除法过程设汁cflc逻辑电路(见图1)。其生成多项式为g(戈)=戈6+x5+z4+z3+1。逻辑电路由6个

6、移位寄存器和4个异或门组成，完成模2除法运算。第6级寄存器的输出就是模2除法的商，一个时钟周期右移一次，如果除法商“l”时(即第6级寄存器的输出为“1”时)，移位寄存器输出与生成多项式g(石)进行模2运算，然后右移一收稿日期：2005—10—11基金项目：国家863基金资助项目(2003AAlzll90)；陕西省科研发展基金资助项目(2004K05一G4)作者简介：李宥谋(1959一)，男，陕西西安人，西安邮电学院副教授，从事网络通信、集成电路研究。万方数据西北大学学报(自然科学版)第36卷位。否则直接右移一位。对于一个14位数据流和6位14位数据流的C

7、RC校验码。CRc码组成的码元，需要20个时钟周期才能计算出输CLK清零图l有延时的CRC逻辑电路Fig．1CRClogicalcircuitwithdelay有延时的cRc逻辑电路工作过程：①先将移位寄存器清零；②将数据流m(戈)的高6位移进六级的寄存器中，由于寄存器初始值为零，因此数据流m(戈)的高6位移进寄存器中不发生改变；③数据流m(石)继续移进寄存器时，第6级移位寄存器移出值若为“0”时，不进行模2运算只右移一位；若为“1”时进行模2运算后右移一位；④数据流m(石)全部移进寄存器后，还要继续移进6个连续“0”之后，该组数据的cRc计算才结束。这

8、种电路的设计思想完全采用了一般的模2除法的运算过程。其最大缺点是在数据流m(菇)