《任意长度信息序列的CRC快速算法》由会员分享，可在线阅读，更多相关《任意长度信息序列的CRC快速算法（4页珍藏版）》请在金锄头文库上搜索。
1、任意长度信息序列的CRC 快速算法发布时间 :2003 年 5 月 11 日 点击次数 :1503 来源: 单片机与嵌入式系统应用作者 :国防科技大学刘小汇 王飞雪CRC （循环冗余校验码）编码是数字信号传输中用得较普遍的一种差错控制编码。它不但可以用于纠正独立的随机错误, 也可以用于纠正突发错误。CRC校验通常是靠专用硬件电路来实现的, 但很多系统为了降低成本 , 常常利用单片机或微处理器编程来完成这一功能。因此, 在器件处理能力有限的情况下, 如何提高CRC校验软件计算的速度, 是开发者最为关心的问题。1 整字节序列的CRC 校验快速算法文献 1 提出了一种针对整字节的CRC 快速算法。
2、它的基本思想是预先生成一个余式表, 通过查表 , 利用递推原理进行快速计算。现以CCITT（国际电话电报咨询委员会）建议的, 用于基本型数据传输规程的生成多项式为例 , 简要介绍此先验算法的基本原理。设 M为由 i 个字节组成的8i位二进制序列, 用字节形式表示为截取 Mi 的前个字节构成一个序列, 即这两个序列之间的关系可以表示为其中是字节的二进制多项式表示形式, 是将序列左移一个字节。对于序列来说 , 有其中 ,是商多项式 , 为一整数项 ; 为最高次幂小于15 的余数项。而对于Mi 序列 , 其中为整数项 , 因此对多项式取余即等效于对多项式取余, 记做这样就形成了递推关系。对于序列 ,
3、 已知就可知 , 已知就可知 , 最后就变成了求三字节序列的余式项的问题。不失一般性 , 设三字节序列 , 那么我们可以预先做好一个1616 的a00 形式的余式表, 通过查余式表可以很快知道, 而是小于等于16位的二字节序列, 除以的余式即为本身。(4) 式中的加法运算为模2 加（异或运算）。运用此算法就可很快求出整字节的CRC 校验码。2 任意长度序列的CRC校验快速算法上述算法 , 只适用于信息长度为整字节的情形; 但在实际应用中, 往往会遇到计算非整字节的CRC 校验码。一种解决方法是, 在信息数据前补零,即将信息数据右移, 使之成为整字节来计算, 这对于信息数据序列不长的情况还是奏效
4、的; 但遇到长数据序列, 若对每一个字节均进行移位操作, 则计算量明显增加, 这一缺点对于实时性要求高的系统来说尤其明显。下面以生成多项式为例, 提出一种改进算法, 可实现任意长度序列快速 CRC 校验运算。设 D为任意长度的二进制序列, 记长度为k 位, 则 k 总可以表示成的形式。其中 s0, 且 0p 8。 这样 ,就可以将序列D按降幂形式写成D(x)=xpd1d2,ds- 1ds+m(x),dj(1j s) 是位长为8 的字节 ,m 为序列D除掉整字节后余下的位, 为非整字节。记序列M(x)=d1d2,ds-1ds,那么M(x) 为整字节序列, 其余式 RM(x)可用前面介绍的整字节C
5、RC 算法求出。因为生成多项式G(x)=x16+x12+x5+1 的最高次幂为16, 所以序列D(x) 的余式 RD(x)为其中, 即形成两个余式的模2 加 （异或运算） ,m(x)的长度小于1 字节 , 所以 RM(x)是a00 形式的余式 ,通过查余式表可以很快得到。现在来讨论xpRM(x)的计算。 RM(x)可以按照上述整字节的快速算法算出结果。因为RM(x)的位长为16,xpRM(x) 相当于 RM(x)向左移 p位 , 位长为 (16+p) 。因为 0p 8 所以 16(16+p) 24 xpRM(x)可以看成一个3 字节序列 , 定义其中是 2 字节序列 , 长 16 位, 小于生
6、成多项式17 位。它们除以生成多项式的余式即为本身, 所以是为样式的余式, 可以由余式表直接获得, 所以 (1) 式又可写为这就是改进后的非整字节CRC 校验快速算法。它不需要进行大量的数据移位对齐, 比起整字节的算法,只增加了两次查表和两次异或运算, 可见其运算量并没有显著增加。值得提出的是 , 在文献 1 提出的整字节CRC校验快速算法中, 推导递推公式 (3) 时, 作者并没有考虑到序列用于计算CRC 校验码时要先移16 位（生成多项式为时）。若读者按照此法, 直接用序列来做运算, 显然是不对的 , 必将导致错误结果。3 适用于单片机或微处理器的算法流程为了编程方便 , 我们将需处理的信
7、息序列做以下变形。重写(4) 式, 在整字节部分的M(x) 后补 2 字节的“0”, 得到新数列其中 ,用取代 M(x) 做编程计算 , 算法流程如图1 所示。图 1 算法流程图结语任意长度非整字节的CRC快速算法适用的范围很广, 只需预先在内存中生成一个余式表, 通过查余式表就可以快速计算。 由于算法的每一步递推都是以字节为单位的, 这样就比传统的以位为单位的算法要快上十几倍。数据序列的长度越长, 其体现的优越性就越高。而且算法不要求用于计算的序列为整字节, 任意位长均适用 , 在实际应用中效果显著。参考文献1 韩炬 . 简单适用的单片机快速算法J .力源电子工程,2000 （2）2 王新梅 . 纠错码原理与方法M. 西安：西安电子科技大学出版社,2001 3 常晓明 , 潘卫华 , 王建东 . CRC 校验及其软件实现J. 电子技术应用 ,1995 （6）
