简单实用的单片机CRC快速算法

1引言

CRC （循环冗余码）检验技术广泛应用于测控及通信领域。在很多情况下，CRC计算是靠专用的硬件来实现的，但是对于小型低成本的单片机系统来说，若要在没有这些硬件的支持下实现CRC检验，首先要解决的就是如何通过软件高效快速地完成CRC计算的问题，也就是CRC算法的问题。

这里将提供两种算法，它们稍有不同，一种适用于程序空间大一些的51系列等单片机，另一种适用于程序空间的使用条件十分苛刻的PIC单片机。这些算法按字节进行计算，仅使用查表和简单的异或运算等操作，所以，计算过程相当简捷，而计算速度却很快。

下面先简述一下CRC原理，然后再以CRC-CCITT标准生成多项式为例对算法进行说明，并给出一个51系列单片机子程序和一个PIC单片机子程序。

2CRC原理

CRC检验原理实际上就是在一个p位二进制数据序列之后附加一个r位二进制检验码(序列),从而构成一个总长为n＝p＋r位的二进制序列，例如，p位二进制数据序列D＝[dp-1dp-2......d1d0]，r位二进制检验码R＝[rr-1rr-2....r1r0]，所得到的这个n位二进制序列就是M＝[dp-1dp-2......d1d0rr-1rr-2....r1r0]；附加在数据序列之后的这个检验码与数据序列的内容之间存在着某种特定的关系。如果因干扰等原因使数据序列中的某一位或某些位发生错误，这种特定关系就会被破坏,因此,通过检查这一关系,就可以实现对数据正确性的检验。

校验码R是通过对数据序列D进行二进制除法取余式运算得到的，它被一个称为生成多项式的（r＋1）位二进制序列G＝[grgr-1....g1g0]来除，用多项式形式表示为

（1）

其中，xrD(x)表示将数据序列D左移r位（即在D的末尾再增加r个0位），Q(x)代表这一除法所得的商，R(x)就是所需的余式。这一运算关系还可以用式（2）来表达

（2）

其中，Re[]表示对括号内的式子进行取余式运算。

检验码的编码计算如上所述，而检验过程则是对M序列直接进行除法取余式运算，即

（3）

或表示为

（4）

所得到的余式R(x)若为零则表示数据正确，否则认为发生错误。

3快速算法的基本思路

这里仅以CRC-CCITT标准生成多项式为例进行说明。CRC-CCITT是一个17位生成多项式G＝[10001000000100001]，用多项式形式表示为G(x)＝x16＋x12＋x5＋1，由它产生的检验码R的二进制位数是16位（2字节）。

单片机的操作是以字节形式进行的，所以，算法应以字节为单位进行运算。这里将把用字节构成的二进制序列称为“字节序列”，显然，单片机的数据序列、检验码以及它俩组成的序列M都是字节序列，或者说是“多字节序列”。

实际上，这种算法所要解决的问题就是如何对多字节序列进行除法取余式运算的问题。

3.1多字节序列运算规律

首先设一个由i个字节m1、m2、......、mi-1、mi构成的8×i位二进制序列，并用字节形式表示它为Mi＝[m1m2......mi-1mi]，然后再截取Mi的前（i-1）个字节构成一个Mi-1序列，Mi-1＝[m1m2......mi-1]，这两个序列之间的关系可以用多项式表示为Mi(x)＝x8Mi-1(x)＋mi(x)，其中，mi(x)是字节mi的二进制多项式表示形式，而x8Mi-1(x)表示将Mi-1序列左移一个字节。

对于序列Mi-1来说，

(5)

其中，二字节序列余式Ri-1＝［hi-1li-1］。

而对于Mi序列来说，可得

(6)

这一结果的前一项为一整数，所以它与余式无关，这样，余式只可能出现在后一项中。因此，对x8Ri-1(x)＋mi(x)取余式运算就等价于对Mi(x)的取余式运算,用式（4）的形式表示为

(7)

x8Ri-1(x)+mi(x)代表一个由Ri-1和mi共同组成的三字节序列[hi-1li-1mi]，而且对这个三字节序列的取余式运算就等于对Mi序列的取余式运算，其结果就是Mi序列的余式Ri＝[hili]。同理可得，对于一个Mi+１序列（它比Mi序列多一个字节mi+1）来说，对三字节序列[hilimi+1]的运算就等价于对Mi+1序列的运算，其结果就是Mi+1序列的余式Ri+1＝[hi+1li+1]。

显然，这反映出一种如图1所示的递推运算的规律。可见，每一次递推运算都是对一个三字节序列的计算，所以，如何简单快捷地对三字节序列进行计算是这种算法的又一个关键。

3.2三字节序列计算

提到简单快捷，人们自然会想到采用查表的办法，例如事先把三字节序列的所有余式计算出来，置于一个称为“余式表”的表格中，供随时读取。不过，这样的表格太大，需要224个单元，也就是要占用225个字节的存储空间，这对单片机来说是绝对无法接受的，因此，需要想办法减少所占用的存储空间。

图1递推计算步骤

设一个三字节序列Tabc＝[a b c]、一个Ta00＝[a00]和一个二字节序列Tbc＝[b c]。可以用多项式形式表示它们之间的关系为Tabc(x)＝Ta00(x)＋Tbc(x)，因此，对Ta00来说，

（8）

而对Tabc来说，

其中，Qa00是整数，与余式无关；而Ra00和Tbc都是二字节序列，因而，它们的和（模2加法，即异或运算）仍然是二字节序列（二进制16位，小于生成多项式的17位），因此，它就是Tabc的余式Rabc，即

（9）

这说明，可以把三字节序列Tabc＝[a b c]的运算分解成两个步骤来进行，如图2所示。

1.通过查余式表（表1），读取Ta00＝[a00]的余式Ra00＝[ha00la00]；

2.将Ra00与[b c]进行异或运算，从而得到[a b c]的余式Rabc＝[habclabc]，即habc＝ha00Åb，labc＝la00Åc。

由于[a00]中只有一个字节不为零，因此，[a00]余式表仅需要256个单元，即占用512个字节。

图２三字节序列[a b c]的计算办法

4适用于51系列等单片机的算法

前面所述的办法可以直接用于51系列等单片机，因为512字节的余式表对它们的程序存储容量来说是完全不成问题的。

计算直接通过上述的递推过程来进行，每一次递推都是对一个三字节序列进行的计算：第一次是[m1m2m3]，结果是[h3l3]；第二次是[h3l3m4]，结果是[h4l4]；......，第i次是[hi+1li+1mi+2]，结果是[hi+2li+2]；......；最后是[hk+1lk+1mk+2]，最终结果是[hl]。如果有k个数据字节，则递推k次。下面给出一个三字节序列计算子程序，供每一次递推运算时调用。注意，在第一次被调用之前，先将m1、m2和m3分别存入R0、R1和R2中（子程序返回时，计算结果将存放在R0和R1中）。从第二次调用时开始，每次在调用之前只需先将参与本次运算的字节存入R2即可（第二次是m4，第三次是m5，...，第i次是mi+2，...）。当最后一次调用返回后，R0和R1分别存放的就是最终结果h和l。

这一子程序只有12条指令，因此十分简捷，而且只占用16个机器周期，也就是说，相当于计算每一个字节只需16个机器周期即可完成，这将比传统的软件算法快十几倍。

表1所示的余式表虽然只占用512个字节的程序存储空间，但对于PIC单片来说还是太大了，需要再进行压缩。思路是这样的：

将Ta00＝[a00]分解成Te00＝[e00]和Tf00＝[f00]，并使字节e的上半字节内容与a的上半字节相同但下半字节为零，同时使字节f的下半字节内容与a的下半字节相同但上半字节为零，然后用Te00和Tf00生成余式表来代替Ta00余式表。由于Te00和Tf00中只有半个字节不为零，所以，每个余式表只需16个单元（32个字节），两个余式表总共只占用64个字节，这样就可满足PIC单片机的要求了。

由上述思路可知，e＝a∧0F0H，f＝a∧0FH，因此可得，Ta00＝Te00ÅTf00，同时，还可以证明它们余式的关系为Ra00＝Re00ÅRf00，也就是说，如果设Ra00＝[ha00la00]、Re00＝[he00le00]和Rf00＝[hf00lf00]，则ha00＝he00Åhf00，la00＝le00Ålf00。这样，三字节序列[a00]的计算可由图3所示的方法来进行，其中，[e00]和[f00]余式表见表2和表3。

显然，对于PIC单片机来说，三字节序列[a b c]的计算需要综合图2和图3所示的两种办法来进行，下面就给出一个这样的PIC子程序，它的使用与上面所述的51系列单片机子程序基本相同，即，在第一次被调用之前，先将m1、m2和m3分别存入通用寄存器BYTEa、BYTEb和BYTEc中；从第二次调用时开始，每次在调用之前只需先将参与本次运算的字节存入BYTEc即可（第二次是m4，第三次是m5，...，第i次是mi+2，...）。每次子程序返回时，计算结果将存放在BYTEa和BYTEb中，最后一次调用返回后，BYTEa和BYTEb分别存放的就是最终结果h和l。子程序中，除BYTEa、BYTEb和BYTEc外，ADDR、RESULTh和RESULTl也是通用寄存器。

图3三字节序列[a 00]的计算办法

参考文献

1常晓明，潘卫华，王建东.CRC校验及其软件实现.电子技术应用,1995(6)

5适用于PIC单片机的算法