简单实用的单片机CRC快速算法
摘 要提供两个实用的、能够在单片机上通过软件来实现的CRC快速算法，其中一个适用于51系列等单片机，另一个适用于PIC单片机，这两种算法十分简单快捷。
关键词CRC 算法 单片机
1 引言
CRC（循环冗余码）检验技术广泛应用于测控及通信领域。在很多情况下，CRC计算是靠专用的硬件来实现的，但是对于小型低成本的单片机系统来说，若要在没有这些硬件的支持下实现CRC检验，首先要解决的就是如何通过软件高效快速地完成CRC计算的问题，也就是CRC算法的问题。
这里将提供两种算法，它们稍有不同，一种适用于程序空间大一些的51系列等单片机，另一种适用于程序空间的使用条件十分苛刻的PIC单片机。这些算法按字节进行计算，仅使用查表和简单的异或运算等操作，所以，计算过程相当简捷，而计算速度却很快。
下面先简述一下CRC原理，然后再以CRC-CCITT标准生成多项式为例对算法进行说明，并给出一个51系列单片机子程序和一个PIC单片机子程序。
2CRC原理
CRC检验原理实际上就是在一个p位二进制数据序列之后附加一个r位二进制检验码(序列),从而构成一个总长为n＝p＋r位的二进制序列，例如，p位二进制数据序列D＝[d p-1d p-2 ......d1d0]，r位二进制检验码R＝[r r-1r r-2....r1r0]，所得到的这个n位二进制序列就是M＝[d p-1d p-2 ......d1d0r r-1r r-2....r1r0]； 附加在数据序列之后的这个检验码与数据序列的内容之间存在着某种特定的关系。如果因干扰等原因使数据序列中的某一位或某些位发生错误，这种特定关系就会被破坏,因此,通过检查这一关系, 就可以实现对数据正确性的检验。
校验码R是通过对数据序列D进行二进制除法取余式运算得到的，它被一个称为生成多项式的（r＋1）位二进制序列G＝[g r g r-1 .... g1 g0]来除，用多项式形式表示为
（1）
其中，x r D(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＝[1 0001 0000 0010 0001]，用多项式形式表示为G(x)＝x16＋x12＋x5＋1，由它产生的检验码R的二进制位数是16位（2字节）。
单片机的操作是以字节形式进行的，所以，算法应以字节为单位进行运算。这里将把用字节构成的二进制序列称为“字节序列”，显然，单片机的数据序列、检验码以及它俩组成的序列M都是字节序列，或者说是“多字节序列”。
实际上，这种算法所要解决的问题就是如何对多字节序列进行除法取余式运算的问题。
3.1 多字节序列运算规律
首先设一个由i个字节 m1、m2、......、m i-1、m i构成的8×i位二进制序列，并用字节形式表示它为M i＝[ m1
m2 ...... m i-1m i ]，然后再截取M i的前（i-1）个字节构成一个M i-1序列，M i-1＝[ m1 m2 ...... m i-1 ]，这两个序列之间的关系可以用多项式表示为M i(x)＝x 8M i-1(x)＋m i(x)，其中，m i(x)是字节m i的二进制多项式表示形式，而x8M i-1(x)表示将M i-1序列左移一个字节。
对于序列M i-1来说，
(5)
其中，二字节序列余式R i-1＝［h i-1l i-1］。
而对于M i序列来说，可得
(6)
这一结果的前一项为一整数，所以它与余式无关，这样，余式只可能出现在后一项中。因此，对x8R i-1(x)＋m i(x)取余式运算就等价于对M i(x)的取余式运算,用式（4）的形式表示为
(7)
x8R i-1(x)+m i(x)代表一个由R i-1和m i共同组成的三字节序列[ h i-1 l i-1 m i]，而且对这个三字节序列的取余式运算就等于对M i序列的取余式运算，其结果就是M i序列的余式R i＝[ h i l i ]。同理可得，对于一个M i+１序列（它比M i序列多一个字节m i+1）来说，对三字节序列[ h i l i m i+1]的运算就等价于对M i+1序列的运算，其结果就是M i+1序列的余式R i+1＝[ h i+1l i+1 ]。
显然，这反映出一种如图1所示的递推运算的规律。可见，每一次递推运算都是对一个三字节序列的计算，所以，如何简单快捷地对三字节序列进行计算是这种算法的又一个关键。
3.2 三字节序列计算
提到简单快捷，人们自然会想到采用查表的办法，例如事先把三字节序列的所有余式计算出来，置于一个称为“余式表”的表格中，供随时读取。不过，这样的表格太大，需要224个单元，也就是要占用225个字节的存储空间，这对单片机来说是绝对无法接受的，因此，需要想办法减少所占用的存储空间。
图1 递推计算步骤
设一个三字节序列T abc＝[ a b c ] 、一个 T a00＝[ a 0 0 ]和一个二字节序列 T bc＝[ b c ]。可以用多项式形式表示它们之间的关系为 T abc(x)＝T a00(x)＋T bc(x)，因此，对T a00来说，
（8）
而对T abc来说，
其中，Q a00是整数，与余式无关；而R a00和T bc都是二字节序列，因而，它们的和（模2加法，即异或运算）仍然是二字节序列（二进制16位，小于生成多项式的17位），因此，它就是 T abc的余式R abc，即
（9）
这说明，可以把三字节序列T abc＝[ a b c ]的运算分解成两个步骤来进行，如图2所示。
1. 通过查余式表（表1），读取T a00＝[a 0 0 ]的余式R a00＝[ h a00l a00 ]；
2. 将R a00与[ b c ]进行异或运算，从而得到[ a b c ]的余式R abc＝[ h abc l abc ]，即h abc＝h a00 ? b，l abc＝l a00 ? c。
由于[a 0 0 ]中只有一个字节不为零，因此，[a 0 0 ]余式表仅需要256个单元，即占用512个字节。
图２ 三字节序列[ a b c ]的计算办法
4适用于51系列等单片机的算法
前面所述的办法可以直接用于51系列等单片机，因为512字节的余式表对它们的程序存储容量来说是完全不成问题的。
计算直接通过上述的递推过程来进行，每一次递推都是对一个三字节序列进行的计算：第一次是[ m1m2 m3 ]，结果是[ h3 l3 ]；第二次是[ h3 l3m4 ]，结果是[ h4 l4 ]；......，第i次是[ h i+1 l i+1m i+2 ]，结果是[ h i+2 l i+2 ]；......；最后是[ h k+1 l k+1m k+2 ]，最终结果是[ h l]。如果有k个数据字节，则递推k次。下面给出一个三字节序列计算子程序，
供每一次递推运算时调用。注意，在第一次被调用之前，先将m1、m2和m3分别存入R0、R1和R2中（子程序返回时，计算结果将存放在R0和R1中）。从第二次调用时开始，每次在调用之前只需先将参与本次运算的字节存入R2即可（第二次是m4，第三次是m5，...，第i次是m i+2，...）。当最后一次调用返回后，R0和R1分别存放的就是最终结果h和l。CRC MOV DPH, #table; 指向余式表下半区
MOV DPL, R0; 指向对应单元
CLR A ;
MOVC A, @A+DPTR ; 读余式的高字节
XRL A, R1; 计算余式的高字节
MOV R0, A; 存入R0
INC DPH; 指向余式表上半区
CLR A;
MOVC A, @A+DPTR; 读余式的低字节
XRL A, R2; 计算余式的低字节
MOV R1, A; 存入R1
RET
这一子程序只有12条指令，因此十分简捷，而且只占用16个机器周期，也就是说，相当于计算每一个字节只需16个机器周期即可完成，这将比传统的软件算法快十几倍。
表1 [ a 0 0 ] 余式表
a0123456789A B C D E F 0×0000102120423063408450A560C670E781089129A14A B16B C18C D1AD E1CE F1EF 1×123102103273225252B5429472F762D693398318B37B A35A D3BD C39C F3FF E3DE 2×246234430420140164E674C744A45485A56A B54B85289509E5EE F5CF C5AC D58D 3×365326721611063076D766F6569546B4B75B A77A97198738F7DF E7FE D79D C7BC 4×48C458E5688678A70840186128023823C9CC D9ED E98E F9AF89489969A90A B92B 5×5AF54AD47AB76A961A710A503A332A12DBFD CBDC FBBF EB9E9B798B58BB3B AB1A 6×6CA67C874CE45CC52C223C030C601C41EDAE FD8F CDEC DDCD AD2A BD0B8D689D49 7×7E976EB65ED54EF43E132E321E510E70FF9F EFBE DFDD CFFC BF1B AF3A9F598F78 8×918881A9B1CA A1EB D10C C12D F14E E16F108000A130C220E35004402570466067 9×83B99398A3FB B3DA C33D D31C E37F F35E02B1129022F332D24235521462777256 A×B5EA A5CB95A88589F56E E54F D52C C50D34E224C314A004817466644754244405 B×A7DB B7FA879997B8E75F F77E C71D D73C26D336F2069116B06657767646155634 C×D94C C96D F90E E92F99C889E9B98A A9AB584448657806682718C008E1388228A3 D×CB7D DB5C EB3F FB1E8BF99BD8ABBB BB9A4A755A546A377A160AF11AD02AB33A92 E×FD2E ED0F DD6C CD4D BDAA AD8B9DE88DC97C266C075C644C453CA22C831CE00CC1 F×EF1F FF3E CF5D DF7C AF9B BFBA8FD99FF86E177E364E555E742E933EB20ED11EF0
5 适用于PIC单片机的算法
表1所示的余式表虽然只占用512个字节的程序存储空间，但对于PIC单片机来说还是太大了，需要再进行压缩。思路是这样的：
将T a00＝[a 0 0 ]分解成T e00＝[e 0 0 ]和T f00＝[f 0 0 ]，并使字节e的上半字节内容与a的上半字节相同但下半字节为零，同时使字节f的下半字节内容与a的下半字节相同但上半字节为零，然后用T e00和T f00生成余式表来代替T a00余式表。由于T e00和T f00中只有半个字节不为零，所以，每个余式表只需16个单元（32个字节），两个余式表总共只占用64个字节，这样就可满足PIC单片机的要求了。
由上述思路可知，e＝a∧0F0H ，f＝a∧0FH ，因此可得，T a00＝T e00? T f00，同时，还可以证明它们余式的关系为R a00＝R e00? R f00，也就是说，如果设R a00＝[ h a00l a00 ]、R e00＝[ h e00l e00 ]和R f00＝[ h f00l f00 ]，则h a00＝h e00? h f00，l a00＝l e00? l f00。这样，三字节序列[a 0 0 ] 的计算可由图3所示的方法来进行，其中，[e 0 0 ]和[f 0 0 ]余式表见表2和表3。
表2 [ e 0 0 ] 余式表
00102030405060708090A0B0C0D0E0F0 000012312462365348C45AF56CA67E97918883B9B5EA A7DB D94C CB7D FD2E EF1F
表3 [ f 0 0 ] 余式表
00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F
0000 1021 2042 30634084 50A5 60C670E781089129A14A B16B C18C D1AD E1CE F1EF
显然，对于PIC单片机来说，三字节序列[ a b c ]的计算需要综合图2和图3 所示的两种办法来进行，下面就给出一个这样的PIC子程序，它的使用与上面所述的51系列单片机子程序基本相同，即，在第一次被调用之前，先将m1、m2和m3分别存入通用寄存器BYTEa、BYTEb和BYTEc中；从第二次调用时开始，每次在调用之前只需先将参与本次运算的字节存入BYTEc即可（第二次是m4，第三次是m5，...，第i次是m i+2，...）。每次子程序返回时，计算结果将存放在BYTEa和BYTEb中，最后一次调用返回后，BYTEa和BYTEb分别存放的就是最终结果h和l。子程序中，除BYTEa、BYTEb和BYTEc外，ADDR、RESULTh和RESULTl也是通用寄存器。
图3 三字节序列[ a 0 0 ]的计算办法
START MOVLW DATAe
MOVWF ADDR；将[e 0 0]余式表首地址DATAe存入ADDR
SWAPF BYTEa，0
ANDLW0FH；求e和e指定的[e 0 0] 余式高字节的相对地址
ADDWF ADDR，1 ；取其绝对地址，存入ADDR
MOVF ADDR，0 ；把这一绝对地址再存入W
CALL TABLE；查表，返回时h f00放在W中
XORWF RESULTh，0 ；h e00与h f00异或，得h a00，存入W XORWF BYTEb，0；h a00与b异或，得h abc，存入W
MOVF BYTEa；h abc存入BYTEa
MOVLW16
ADDWF ADDR，0 ；求f指定的[f 0 0]余式低字节的绝对地址CALL TABLE ；查表,返回时l f00放在W中
XORWF RESULTl，0 ；l e00与l f00异或，得l a00，存入W XORWF BYTEc，0；l a00与c异或，得l abc，存入W
MOVF BYTEb；l abc存入BYTEb
RETLW0