1 引言
CRC(循环冗余码)检验技术广泛应用于测控及通信领域。在很多情况下，CRC计算是靠专用的硬件来实现的，但是对于小型低成本的单片机系统来说，若要在没有这些硬件的支持下实现CRC检验，首先要解决的就是如何通过软件高效快速地完成CRC计算的问题，也就是CRC算法的问题。
这里将提供两种算法，它们稍有不同，一种适用于程序空间大一些的51系列等单片机，另一种适用于程序空间的使用条件十分苛刻的PIC单片机。这些算法按字节进行计算，仅使用查表和简单的异或运算等操作，所以，计算过程相当简捷，而计算速度却很快。
下面先简述一下CRC原理，然后再以CRC-CCITT标准生成多项式为例对算法进行说明，并给出一个51系列单片机子程序和一个PIC单片机子程序。
2 CRC原理
CRC检验原理实际上就是在一个p位二进制数据序列之后附加一个r位二进制检验码(序列),从而构成一个总长为n=p+r位的二进制序列，例如，p 位二进制数据序列D=[dp-1dp-2 ......d1d0]，r位二进制检验码R=[rr-1 rr-2....r1 r0]，所得到的这个n位二进制序列就是M=[dp-1dp-2 ......d1d0 rr-1 rr-2....r1 r0]; 附加在数据序列之后的这个检验码与数据序列的内容之间存在着某种特定的关系。如果因干扰等原因使数据序列中的某一位或某些位发生错误，这种特定关系就会被破坏,因此,通过检查这一关系, 就可以实现对数据正确性的检验。
校验码R是通过对数据序列D进行二进制除法取余式运算得到的，它被一个称为生成多项式的(r+1)位二进制序列G=[gr gr-1 .... g1 g0]来除，用多项式形式表示为
(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=[1 0001 0000 0010 0001]，用多项式形式表示为G(x)=x16+x12+x5+1，由它产生的检验码R的二进制位数是16位(2字节)。 单片机的操作是以字节形式进行的，所以，算法应以字节为单位进行运算。这里将把用字节构成的二进制序列称为“字节序列”，显然，单片机的数据序列、检验码以及它俩组成的序列M都是字节序列，或者说是“多字节序列”。 实际上，这种算法所要解决的问题就是如何对多字节序列进行除法取余式运算的问题。3.1 多字节序列运算规律 首先设一个由i个字节 m1、m2、......、mi-1、mi 构成的8×i位二进制序列，并用字节形式表示它为Mi =[ m1 m2 ...... mi-1 mi ]，然后再截取Mi的前(i-1)个字节构成一个Mi-1序列，Mi-1=[ m1 m2 ...... mi-1 ]，这两个序列之间的关系可以用多项式表示为Mi(x)=x 8Mi-1(x)+mi(x)，其中，mi(x)是字节mi的二进制多项式表示形式，而x8Mi-1(x)表示将Mi-1序列左移一个字节。 对于序列Mi-1来说，
(5)
其中，二字节序列余式Ri-1=[hi-1 li-1]。 而对于Mi序列来说，可得
(6) 这一结果的前一项为一整数，所以它与余式无关，这样，余式只可能出现在后一项中。因此，对x8Ri-1(x)+mi(x)取余式运算就等价于对Mi(x)的取余式运算,用式(4)的形式表示为
(7) x8Ri-1(x)+mi(x)代表一个由Ri-1和mi共同组成的三字节序列[ hi-1 li-1 mi]，而且对这个三字节序列的取余式运算就等于对Mi序列的取余式运算，其结果就是Mi序列的余式Ri=[ hi li ]。同理可得，对于一个Mi+1序列(它比Mi序列多一个字节mi+1)来说，对三字节序列[ hi li mi+1]的运算就等价于对Mi+1序列的运算，其结果就是Mi+1序列的余式Ri+1=[ hi+1 li+1 ]。 显然，这反映出一种如图1所示的递推运算的规律。可见，每一次递推运算都是对一个三字节序列的计算，所以，如何简单快捷地对三字节序列进行计算是这种算法的又一个关键。
3.2 三字节序列计算 提到简单快捷，人们自然会想到采用查表的办法，例如事先把三字节序列的所有余式计算出来，置于一个称为“余式表”的表格中，供随时读取。不过，这样的表格太大，需要224个单元，也就是要占用225个字节的存储空间，这对单片机来说是绝对无法接受的，因此，需要想办法减少所占用的存储空间。
图1
递推计算步骤 设一个三字节序列Tabc =[ a b c ] 、一个 Ta00=[ a 0 0 ]和一个二字节序列 Tbc=[ b c ]。可以用多项式形式表示它们之间的关系为 Tabc(x)=Ta00(x)+Tbc(x)，因此，对Ta00来说，
[pagebreak]
(8) 而对Tabc来说，
?其中，Qa00是整数，与余式无关;而Ra00和Tbc都是二字节序列，因而，它们的和(模2加法，即异或运算)仍然是二字节序列(二进制16位，小于生成多项式的17位)，因此，它就是 Tabc的余式Rabc，即
(9) 这说明，可以把三字节序列Tabc=[ a b c ]的运算分解成两个步骤来进行，如图2所示。 1. 通过查余式表(表1)，读取Ta00=[a 0 0 ]的余式Ra00=[ ha00 la00 ]; 2. 将Ra00与[ b c ]进行异或运算，从而得到[ a b c ]的余式Rabc=[ habc labc ]，即habc=ha00 & b，labc=la00 & c。 由于[a 0 0 ]中只有一个字节不为零，因此，[a 0 0 ]余式表仅需要256个单元，即占用512个字节。
4 适用于51系列等单片机的算法 前面所述的办法可以直接用于51系列等单片机，因为512字节的余式表对它们的程序存储容量来说是完全不成问题的。 计算直接通过上述的递推过程来进行，每一次递推都是对一个三字节序列进行的计算：第一次是[ m1 m2 m3 ]，结果是[ h3 l3 ];第二次是[ h3 l3 m4 ]，结果是[ h4 l4 ];......，第i次是[ hi+1 li+1 mi+2 ]，结果是[ hi+2 li+2 ];......;最后是[ hk+1 lk+1 mk+2 ]，最终结果是[ h l ]。如果有k个数据字节，则递推k次。下面给出一个三字节序列计算子程序，供每一次递推运算时调用。注意，在第一次被调用之前，先将m1、 m2和m3分别存入R0、R1和R2中(子程序返回时，计算结果将存放在R0和R1中)。从第二次调用时开始，每次在调用之前只需先将参与本次运算的字节存入R2即可(第二次是m4，第三次是m5，...，第i次是mi+2，...)。当最后一次调用返回后，R0和R1分别存放的就是最终结果h和l 。
[pagebreak]CRC MOV DPH, #table ; 指向余式表下半区
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 ] 余式表
a 0 1 2 3 4 5 6 7 8 9 A B C D E F
0× 0000 1021 2042 3063 4084 50A5 60C6 70E7 8108 9129 A14A B16B C18C D1AD E1CE F1EF
1× 1231 0210 3273 2252 52B5 4294 72F7 62D6 9339 8318 B37B A35A D3BD C39C F3FF E3DE
2× 2462 3443 0420 1401 64E6 74C7 44A4 5485 A56A B54B 8528 9509 E5EE F5CF C5AC D58D
3× 3653 2672 1611 0630 76D7 66F6 5695 46B4 B75B A77A 9719 8738 F7DF E7FE D79D C7BC
4× 48C4 58E5 6886 78A7 0840 1861 2802 3823 C9CC D9ED E98E F9AF 8948 9969 A90A B92B
5× 5AF5 4AD4 7AB7 6A96 1A71 0A50 3A33 2A12 DBFD CBDC FBBF EB9E 9B79 8B58 BB3B AB1A
6× 6CA6 7C87 4CE4 5CC5 2C22 3C03 0C60 1C41 EDAE FD8F CDEC DDCD AD2A BD0B 8D68 9D49
7× 7E97 6EB6 5ED5 4EF4 3E13 2E32 1E51 0E70 FF9F EFBE DFDD CFFC BF1B AF3A 9F59 8F78
8× 9188 81A9 B1CA A1EB D10C C12D F14E E16F 1080 00A1 30C2 20E3 5004 4025 7046 6067
9× 83B9 9398 A3FB B3DA C33D D31C E37F F35E 02B1 1290 22F3 32D2 4235 5214 6277 7256
A× B5EA A5CB 95A8 8589 F56E E54F D52C C50D 34E2 24C3 14A0 0481 7466 6447 5424 4405
B× A7DB B7FA 8799 97B8 E75F F77E C71D D73C 26D3 36F2 0691 16B0 6657 7676 4615 5634
C× D94C C96D F90E E92F 99C8 89E9 B98A A9AB 5844 4865 7806 6827 18C0 08E1 3882 28A3
D× CB7D DB5C EB3F FB1E 8BF9 9BD8 ABBB BB9A 4A75 5A54 6A37 7A16 0AF1 1AD0 2AB3 3A92
E× FD2E ED0F DD6C CD4D BDAA AD8B 9DE8 8DC9 7C26 6C07 5C64 4C45 3CA2 2C83 1CE0 0CC1
F× EF1F FF3E CF5D DF7C AF9B BFBA 8FD9 9FF8 6E17 7E36 4E55 5E74 2E93 3EB2 0ED1 1EF0
5 适用于PIC单片机的算法 表1所示的余式表虽然只占用512个字节的程序存储空间，但对于PIC单片机来说还是太大了，需要再进行压缩。思路是这样的： 将Ta00=[a 0 0 ]分解成Te00=[e 0 0 ]和Tf00=[f 0 0 ]，并使字节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=[ ha00 la00 ]、Re00=[ he00 le00 ]和Rf00=[ hf00 lf00 ]，则ha00=he00? hf00 ，la00=le00? lf00。这样，三字节序列[a 0 0 ] 的计算可由图3所示的方法来进行，其中，[e 0 0 ]和[f 0 0 ]余式表见表2和表3。
表2 [ e 0 0 ] 余式表
00 10 20 30 40 50 60 70 80 90 A0 B0 C0 D0 E0 F0
0000 1231 2462 3653 48C4 5AF5 6CA6 7E97 9188 83B9 B5EA 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 3063 4084 50A5 60C6 70E7 8108 9129 A14A B16B C18C D1AD E1CE F1EF
显然，对于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 0 0 ]的计算办法
START MOVLW DATAe
MOVWF ADDR ;将[e 0 0]余式表首地址DATAe存入ADDR
SWAPF BYTEa，0
ANDLW 0FH ;求e和e指定的[e 0 0] 余式高字节的相对地址
ADDWF ADDR，1 ;取其绝对地址，存入ADDR
START MOVLW DATAe
MOVF ADDR，0 ;把这一绝对地址再存入W
CALL TABLE ;查表，返回时he00放在W中
MOVWF RESULTh ;把he00存入RESULTh
MOVLW 16
ADDWF ADDR，0 ;求e指定的[e 0 0]余式低字节的绝对地址
CALL TABLE ;查表，返回时le00放在W中
MOVWF RESULTl ;把le00存入RESULTl
MOVLW DATAf
MOVWF ADDR ;将[f 0 0]余式表首地址DATAf存入ADDR
MOVF BYTEa，0
ANDLW 0FH ;求f和f指定的[f 0 0]余式高字节的相对地址
ADDWF ADDR，1 ;取其绝对地址，存入ADDR
MOVF ADDR，0 ;把这一绝对地址再存入W
CALL TABLE ;查表，返回时hf00放在W中
XORWF RESULTh，0 ;he00与hf00异或，得ha00，存入W
XORWF BYTEb，0 ;ha00与b异或，得habc，存入W
MOVF BYTEa ;habc存入BYTEa
MOVLW 16
ADDWF ADDR，0 ;求f指定的[f 0 0]余式低字节的绝对地址
CALL TABLE ;查表,返回时lf00放在W中
XORWF RESULTl，0 ;le00与lf00异或，得la00，存入W
XORWF BYTEc，0 ;la00与c异或，得labc，存入W
MOVF BYTEb ;labc存入BYTEb
RETLW 0
