任意长度信息序列的CRC快速算法

发布时间:2010-3-19 21:22    发布者:蹦蹦
关键词: CRC , 长度 , 算法 , 序列
CRC(循环冗余校验码)编码是数字信号传输中用得较普遍的一种差错控制编码。它不但可以用于纠正独立的随机错误,也可以用于纠正突发错误。CRC校验通常是靠专用硬件电路来实现的,但很多系统为了降低成本,常常利用单片机或微处理器编程来完成这一功能。因此,在器件处理能力有限的情况下,如何提高CRC 校验软件计算的速度,是开发者最为关心的问题。

1  整字节序列的CRC校验快速算法

文献[1]提出了一种针对整字节的CRC快速算法。它的基本思想是预先生成一个余式表,通过查表,利用递推原理进行快速计算。现以 CCITT(国际电话电报咨询委员会)建议的,用于基本型数据传输规程的生成多项式为例,简要介绍此先验算法的基本原理。
设M为由i个字节组成的8×i位二进制序列,用字节形式表示为

1.gif

截取Mi的前个字节构成一个序列,即

2.gif

这两个序列之间的关系可以表示为

3.gif

其中是字节的二进制多项式表示形式,是将序列左移一个字节。

对于序列来说,有

(1).gif

其中,是商多项式,为一整数项;为最高次幂小于15的余数项。而对于Mi序列,

(2).gif

其中为整数项,因此对多项式取余即等效于对多项式取余,记做

(3).gif

这样就形成了递推关系。对于序列,已知就可知,已知就可知,最后就变成了求三字节序列的余式项的问题。

不失一般性,设三字节序列 ,那么

(4).gif

我们可以预先做好一个16×16的[a00]形式的余式表,通过查余式表可以很快知道,而是小于等于16位的二字节序列,除以的余式即为本身。(4)式中的加法运算为模2加(异或运算)。运用此算法就可很快求出整字节的CRC校验码。

2  任意长度序列的CRC校验快速算法

上述算法,只适用于信息长度为整字节的情形;但在实际应用中,往往会遇到计算非整字节的CRC校验码。一种解决方法是,在信息数据前补零,即将信息数据右移,使之成为整字节来计算,这对于信息数据序列不长的情况还是奏效的;但遇到长数据序列,若对每一个字节均进行移位操作,则计算量明显增加,这一缺点对于实时性要求高的系统来说尤其明显。下面以生成多项式为例,提出一种改进算法,可实现任意长度序列快速CRC校验运算。

设D为任意长度的二进制序列,记长度为k位,则k总可以表示成的形式。其中s≥0,且0≤p<8。这样,就可以将序列D按降幂形式写成 D(x)=xp[d1d2……ds-1ds]+m(x),dj(1≤j≤s)是位长为8的字节,m为序列D除掉整字节后余下的位,为非整字节。记序列 M(x)=[d1d2……ds-1ds],那么

(5).gif

M(x)为整字节序列,其余式RM(x)可用前面介绍的整字节CRC算法求出。因为生成多项式G(x)=x16+x12+x5+1的最高次幂为 16,所以序列D(x)的余式RD(x)为

(6).gif

其中 (6.2).gif ,即形成两个余式的模2加(异或运算),m(x)的长度小于1字节,所以RM(x)是[a00]形式的余式,通过查余式表可以很快得到。

现在来讨论xpRM(x)的计算。RM(x)可以按照上述整字节的快速算法算出结果。因为RM(x)的位长为16,xpRM(x)相当于 RM(x)向左移p位,位长为(16+p)。

因为 0≤p<8
所以 16≤(16+p)<24

xpRM(x)可以看成一个3字节序列,定义

(6.5).gif

其中是2字节序列,长16位,小于生成多项式17位。它们除以生成多项式的余式即为本身,所以

(7).gif

是为样式的余式,可以由余式表直接获得,所以(1)式又可写为

(8).gif

这就是改进后的非整字节CRC校验快速算法。它不需要进行大量的数据移位对齐,比起整字节的算法,只增加了两次查表和两次异或运算,可见其运算量并没有显著增加。

值得提出的是,在文献[1]提出的整字节CRC校验快速算法中,推导递推公式(3)时,作者并没有考虑到序列用于计算CRC校验码时要先移16 位(生成多项式为时)。若读者按照此法,直接用序列来做运算,显然是不对的,必将导致错误结果。

3  适用于单片机或微处理器的算法流程

为了编程方便,我们将需处理的信息序列做以下变形。重写(4)式,在整字节部分的M(x)后补2字节的“0”,得到新数列

(9).gif

其中,用取代M(x)做编程计算,算法流程如图1所示。

图1.gif
图1  算法流程图

结语

任意长度非整字节的CRC快速算法适用的范围很广,只需预先在内存中生成一个余式表,通过查余式表就可以快速计算。由于算法的每一步递推都是以字节为单位的,这样就比传统的以位为单位的算法要快上十几倍。数据序列的长度越长,其体现的优越性就越高。而且算法不要求用于计算的序列为整字节,任意位长均适用,在实际应用中效果显著。

参考文献

   1. 韩炬 简单适用的单片机快速算法 2000(2)
   2. 王新梅 纠错码--原理与方法 2001
   3. 常晓明.潘卫华.王建东 CRC 校验及其软件实现 1995(6)

作 者:国防科技大学 刘小汇 王飞雪  
来 源:单片机与嵌入式系统应用 2003(10)
本文地址:https://www.eechina.com/thread-9632-1-1.html     【打印本页】

本站部分文章为转载或网友发布,目的在于传递和分享信息,并不代表本网赞同其观点和对其真实性负责;文章版权归原作者及原出处所有,如涉及作品内容、版权和其它问题,我们将根据著作权人的要求,第一时间更正或删除。
您需要登录后才可以发表评论 登录 | 立即注册

厂商推荐

相关视频

关于我们  -  服务条款  -  使用指南  -  站点地图  -  友情链接  -  联系我们
电子工程网 © 版权所有   京ICP备16069177号 | 京公网安备11010502021702
快速回复 返回顶部 返回列表