计算校验和的算法。

摘要提供两个实用的、能够在单片机上通过软件来实现的CRC快速算法，其中一个适用于51系列等单片机，另一个适用于PIC单片机，这两种算法十分简单快捷。关键词　CRC    算法   单片机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+１序列（它比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来说，（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个字节。图２三字节序列[ a b c ]的计算办法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 。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 ] 余式表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 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  参考文献1 常晓明，潘卫华，王建东. CRC校验及其软件实现. 电子技术应用, 1995(6)

调试易

计算校验和的算法。

解决方案 »