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

2008-11-17 08:48 3160 15 15 分类: MCU/ 嵌入式

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


煤炭科学研究总院太原分院(030006) 韩 炬










摘 要 提供两个实用的、能够在单片机上通过软件来实现的CRC快速算法,其中一个适用于51系列等单片机,另一个适用于PIC单片机,这两种算法十分简单快捷。


关键词 CRC    算法   单片机


1 引言


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


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


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


2 CRC原理


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


    校验码R是通过对数据序列D进行二进制除法取余式运算得到的,它被一个称为生成多项式的(r1)位二进制序列G[gr gr-1 .... g1 g0]来除,用多项式形式表示为




Image124.gif1

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




Image125.gif2

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


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




Image126.gif3

    或表示为




Image127.gif4

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


3 快速算法的基本思路


    这里仅以CRC-CCITT标准生成多项式为例进行说明。CRC-CCITT是一个17位生成多项式G[1 0001 0000 0010 0001],用多项式形式表示为G(x)x16x12x51,由它产生的检验码R的二进制位数是16位(2字节)。


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


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


3.1 多字节序列运算规律


    首先设一个由i个字节 m1m2......mi-1mi 构成的i位二进制序列,并用字节形式表示它为Mi [ m1m2 ...... mi-1mi ],然后再截取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来说,




Image128.gif(5)

    其中,二字节序列余式Ri-1=[hi-1li-1]。


     而对于Mi序列来说,可得




Image129.gif(6)

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




Image130.gif(7)

    x8Ri-1(x)+mi(x)代表一个由Ri-1mi共同组成的三字节序列[ 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+1li+1 ]


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


3.2 三字节序列计算


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


hj.1.gif (6698 字节)


 图1 递推计算步骤


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




Image132.gif8

    而对Tabc来说,




Image133.gif

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




Image134.gif9

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


    1. 通过查余式表(表1),读取Ta00[a 0 0 ]的余式Ra00[ ha00la00 ]


    2. Ra00[ b c ]进行异或运算,从而得到[ a b c ]的余式Rabc[ habc labc ],即habcha00 ? blabcla00 ? c


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


hj.2.gif (4470 字节)



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


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


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


    计算直接通过上述的递推过程来进行,每一次递推都是对一个三字节序列进行的计算:第一次是[ m1 m2 m3 ],结果是[ h3 l3 ];第二次是[ h3 l3m4 ],结果是[ h4 l4 ]......,第i次是[ hi+1 li+1mi+2 ],结果是[ hi+2 li+2 ]......;最后是[ hk+1 lk+1mk+2 ],最终结果是[ hl]。如果有k个数据字节,则递推k次。下面给出一个三字节序列计算子程序,供每一次递推运算时调用。注意,在第一次被调用之前,先将m1m2m3分别存入R0R1R2中(子程序返回时,计算结果将存放在R0R1中)。从第二次调用时开始,每次在调用之前只需先将参与本次运算的字节存入R2即可(第二次是m4,第三次是m5...,第i次是mi+2...)。当最后一次调用返回后,R0R1分别存放的就是最终结果hl




CRCMOV DPH, #table; 指向余式表下半区
MOVDPL, R0; 指向对应单元
CLRA ;
MOVCA, @A+DPTR ; 读余式的高字节
XRLA, R1; 计算余式的高字节
MOV R0, A; 存入R0
INCDPH; 指向余式表上半区
CLRA;
MOVCA, @A+DPTR; 读余式的低字节
XRLA, R2; 计算余式的低字节
MOVR1, 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



0000


1021


2042


3063


4084


50A5


60C6


70E7


8108


9129


A14A


B16B


C18C


D1AD


E1CE


F1EF



1231


0210


3273


2252


52B5


4294


72F7


62D6


9339


8318


B37B


A35A


D3BD


C39C


F3FF


E3DE



2462


3443


0420


1401


64E6


74C7


44A4


5485


A56A


B54B


8528


9509


E5EE


F5CF


C5AC


D58D



3653


2672


1611


0630


76D7


66F6


5695


46B4


B75B


A77A


9719


8738


F7DF


E7FE


D79D


C7BC



48C4


58E5


6886


78A7


0840


1861


2802


3823


C9CC


D9ED


E98E


F9AF


8948


9969


A90A


B92B



5AF5


4AD4


7AB7


6A96


1A71


0A50


3A33


2A12


DBFD


CBDC


FBBF


EB9E


9B79


8B58


BB3B


AB1A



6CA6


7C87


4CE4


5CC5


2C22


3C03


0C60


1C41


EDAE


FD8F


CDEC


DDCD


AD2A


BD0B


8D68


9D49



7E97


6EB6


5ED5


4EF4


3E13


2E32


1E51


0E70


FF9F


EFBE


DFDD


CFFC


BF1B


AF3A


9F59


8F78



9188


81A9


B1CA


A1EB


D10C


C12D


F14E


E16F


1080


00A1


30C2


20E3


5004


4025


7046


6067



83B9


9398


A3FB


B3DA


C33D


D31C


E37F


F35E


02B1


1290


22F3


32D2


4235


5214


6277


7256



B5EA


A5CB


95A8


8589


F56E


E54F


D52C


C50D


34E2


24C3


14A0


0481


7466


6447


5424


4405



A7DB


B7FA


8799


97B8


E75F


F77E


C71D


D73C


26D3


36F2


0691


16B0


6657


7676


4615


5634



D94C


C96D


F90E


E92F


99C8


89E9


B98A


A9AB


5844


4865


7806


6827


18C0


08E1


3882


28A3



CB7D


DB5C


EB3F


FB1E


8BF9


9BD8


ABBB


BB9A


4A75


5A54


6A37


7A16


0AF1


1AD0


2AB3


3A92



FD2E


ED0F


DD6C


CD4D


BDAA


AD8B


9DE8


8DC9


7C26


6C07


5C64


4C45


3CA2


2C83


1CE0


0CC1



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的下半字节相同但上半字节为零,然后用Te00Tf00生成余式表来代替Ta00余式表。由于Te00Tf00中只有半个字节不为零,所以,每个余式表只需16个单元(32个字节),两个余式表总共只占用64个字节,这样就可满足PIC单片机的要求了。


    由上述思路可知,ea0F0H fa0FH ,因此可得,Ta00Te00? Tf00,同时,还可以证明它们余式的关系为Ra00Re00? Rf00,也就是说,如果设Ra00[ ha00la00 ]Re00[ he00le00 ]Rf00[ hf00lf00 ],则ha00he00? hf00 la00le00? 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系列单片机子程序基本相同,即,在第一次被调用之前,先将m1m2m3分别存入通用寄存器BYTEaBYTEbBYTEc中;从第二次调用时开始,每次在调用之前只需先将参与本次运算的字节存入BYTEc即可(第二次是m4,第三次是m5...,第i次是mi+2...)。每次子程序返回时,计算结果将存放在BYTEaBYTEb中,最后一次调用返回后,BYTEaBYTEb分别存放的就是最终结果hl。子程序中,除BYTEaBYTEbBYTEc外,ADDRRESULThRESULTl也是通用寄存器。


 hj.3.gif (5224 字节)


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




STARTMOVLWDATAe



MOVWFADDR;将[e 0 0]余式表首地址DATAe存入ADDR
SWAPFBYTEa0
ANDLW0FH;求ee指定的[e 0 0] 余式高字节的相对地址
ADDWFADDR1 ;取其绝对地址,存入ADDR



MOVFADDR0;把这一绝对地址再存入W



CALLTABLE;查表,返回时he00放在W
MOVWFRESULTh;把he00存入RESULTh
MOVLW16
ADDWFADDR0;求e指定的[e 0 0]余式低字节的绝对地址
CALLTABLE;查表,返回时le00放在W
MOVWFRESULTl;把le00存入RESULTl
MOVLWDATAf
MOVWFADDR;将[f 0 0]余式表首地址DATAf存入ADDR
MOVFBYTEa0
ANDLW0FH;求ff指定的[f 0 0]余式高字节的相对地址
ADDWFADDR1;取其绝对地址,存入ADDR
MOVFADDR0 ;把这一绝对地址再存入W
CALLTABLE;查表,返回时hf00放在W
XORWFRESULTh0 he00hf00异或,得ha00,存入W
XORWFBYTEb0ha00b异或,得habc,存入W
MOVFBYTEahabc存入BYTEa
MOVLW16
ADDWFADDR0 ;求f指定的[f 0 0]余式低字节的绝对地址
CALL TABLE ;查表,返回时lf00放在W
XORWFRESULTl0 le00lf00异或,得la00,存入W
XORWFBYTEc0la00c异或,得labc,存入W
MOVFBYTEblabc存入BYTEb
RETLW0

参 考 文 献


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

文章评论0条评论)

登录后参与讨论
我要评论
0
15
关闭 站长推荐上一条 /2 下一条