任意长度信息序列的CRC快速算法 - 软件编程/OS - 电子工程

2dmin

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

<strong>1整字节序列的CRC校验快速算法</strong>

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


<ignore_js_op>





2010-3-19 21:15:16 上传
<strong>下载附件</strong> (2.01 KB)




</ignore_js_op>


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


<ignore_js_op>





2010-3-19 21:15:16 上传
<strong>下载附件</strong> (1.95 KB)




</ignore_js_op>


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


<ignore_js_op>





2010-3-19 21:15:16 上传
<strong>下载附件</strong> (2.29 KB)




</ignore_js_op>


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

对于序列来说,有


<ignore_js_op>





2010-3-19 21:15:15 上传
<strong>下载附件</strong> (3.37 KB)




</ignore_js_op>


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


<ignore_js_op>





2010-3-19 21:15:15 上传
<strong>下载附件</strong> (4.82 KB)




</ignore_js_op>


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


<ignore_js_op>





2010-3-19 21:15:15 上传
<strong>下载附件</strong> (4.25 KB)




</ignore_js_op>


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

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


<ignore_js_op>





2010-3-19 21:15:15 上传
<strong>下载附件</strong> (4.82 KB)




</ignore_js_op>


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

<strong>2任意长度序列的CRC校验快速算法</strong>

上述算法,只适用于信息长度为整字节的情形;但在实际应用中,往往会遇到计算非整字节的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],那么


<ignore_js_op>





2010-3-19 21:15:15 上传
<strong>下载附件</strong> (2.31 KB)




</ignore_js_op>


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


<ignore_js_op>





2010-3-19 21:15:15 上传
<strong>下载附件</strong> (6.24 KB)




</ignore_js_op>


其中
<ignore_js_op>





2010-3-19 21:15:16 上传
<strong>下载附件</strong> (3.34 KB)




</ignore_js_op>
,即形成两个余式的模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字节序列,定义


<ignore_js_op>





2010-3-19 21:15:14 上传
<strong>下载附件</strong> (3.34 KB)




</ignore_js_op>


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


<ignore_js_op>





2010-3-19 21:19:55 上传
<strong>下载附件</strong> (3.93 KB)




</ignore_js_op>


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


<ignore_js_op>





2010-3-19 21:19:55 上传
<strong>下载附件</strong> (4.72 KB)




</ignore_js_op>


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

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

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

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


<ignore_js_op>





2010-3-19 21:21:01 上传
<strong>下载附件</strong> (3.83 KB)




</ignore_js_op>


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


<ignore_js_op>





2010-3-19 21:21:42 上传
<strong>下载附件</strong> (12.8 KB)




</ignore_js_op>

图1算法流程图

<strong>结语</strong>

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

<strong>参考文献</strong>

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

作 者：国防科技大学 刘小汇 王飞雪
来 源：单片机与嵌入式系统应用 2003（10）