lit_mouse 

 网上能查到,下面是一些,不过没有图
 简单实用的单片机CRC快速算法 

煤炭科学研究总院太原分院（030006） 韩 炬 

摘 要 提供两个实用的、能够在单片机上通过软件来实现的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)

（收稿日期：2000-05-15）
  


发表时间:2003年1月19日21:34:00