单片机CRC简易算法-

1、简单实用的单片机CRC快速算法摘 要 提供两个实用的、能够在单片机上通过软件来实现的CRC 快速算法,其中一个适用于51系列等单片机,另一个适用于PIC 单片机,这两种算法十分简单快捷。 关键词 CRC 算法 单片机 1 引言CRC (循环冗余码检验技术广泛应用于测控及通信领域。在很多情况下,CRC 计算是靠专用的硬件来实现的,但是对于小型低成本的单片机系统来说,若要在没有这些硬件的支持下实现CRC 检验,首先要解决的就是如何通过软件高效快速地完成CRC 计算的问题,也就是CRC 算法的问题。这里将提供两种算法,它们稍有不同,一种适用于程序空间大一些的51系列等单片机,另一种适用于程序空间的使

2、用条件十分苛刻的PIC 单片机。这些算法按字节进行计算,仅使用查表和简单的异或运算等操作,所以,计算过程相当简捷,而计算速度却很快。下面先简述一下CRC 原理,然后再以CRC-CCITT 标准生成多项式为例对算法进行说明,并给出一个51系列单片机子程序和一个PIC 单片机子程序。 2 CRC 原理CRC 检验原理实际上就是在一个p 位二进制数据序列之后附加一个r 位二进制检验码(序列,从而构成一个总长为n =p +r 位的二进制序列,例如,p 位二进制数据序列D =d p -1d p -2 .d 1d 0,r 位二进制检验码R =r r -1 r r -2.r 1 r 0,所得到的这个n 位二

3、进制序列就是M =d p -1d p -2 .d 1d 0 r r -1 r r -2.r 1r 0; 附加在数据序列之后的这个检验码与数据序列的内容之间存在着某种特定的关系。如果因干扰等原因使数据序列中的某一位或某些位发生错误,这种特定关系就会被破坏,因此,通过检查这一关系, 就可以实现对数据正确性的检验。校验码R 是通过对数据序列D 进行二进制除法取余式运算得到的,它被一个称为生成多项式的(r +1位二进制序列G =g r g r -1 . g 1 g 0来除,用多项式形式表示为 其中,x r D (x 表示将数据序列D 左移r 位(即在D 的末尾再增加r 个0位,Q (x 代表这一除法所

4、得的商,R (x 就是所需的余式。这一运算关系还可以用式(2来表达 其中,Re 表示对括号内的式子进行取余式运算。检验码的编码计算如上所述,而检验过程则是对M 序列直接进行除法取余式运算,即 或表示为 所得到的余式R (x 若为零则表示数据正确,否则认为发生错误。(1(2(3(43 快速算法的基本思路这里仅以CRC-CCITT 标准生成多项式为例进行说明。CRC-CCITT 是一个17位生成多项式G =1 0001 0000 0010 0001,用多项式形式表示为G (x =x 16+x 12+x 5+1,由它产生的检验码R 的二进制位数是16位(2字节。单片机的操作是以字节形式进行的,所以,

5、算法应以字节为单位进行运算。这里将把用字节构成的二进制序列称为“字节序列”,显然,单片机的数据序列、检验码以及它俩组成的序列M 都是字节序列,或者说是“多字节序列”。实际上,这种算法所要解决的问题就是如何对多字节序列进行除法取余式运算的问题。 3.1 多字节序列运算规律首先设一个由i 个字节 m 1、m 2、.、m i -1、m i 构成的8i 位二进制序列,并用字节形式表示它为M i = m 1 m 2 . m i -1 m i ,然后再截取M i 的前(i -1个字节构成一个M i -1序列,M i -1= m 1 m 2 . m i -1 ,这两个序列之间的关系可以用多项式表示为M i

6、(x =x 8M i -1(x +m i (x ,其中,m i (x 是字节m i 的二进制多项式表示形式,而x 8M i -1(x 表示将M i -1序列左移一个字节。 对于序列M i -1来说, 其中,二字节序列余式R i -1=h i -1 l i -1。 而对于M i 序列来说,可得 这一结果的前一项为一整数,所以它与余式无关,这样,余式只可能出现在后一项中。因此,对x 8R i-1(x+m i (x取余式运算就等价于对M i (x的取余式运算,用式(4的形式表示为 x 8R i-1(x+m i (x代表一个由R i-1和m i 共同组成的三字节序列 h i-1 l i-1 m i ,

7、而且对这个三字节序列的取余式运算就等于对M i 序列的取余式运算,其结果就是M i 序列的余式R i = h i l i 。同理可得,对于一个M i +1序列(它比M i 序列多一个字节m i +1来说,对三字节序列 h i l i m i +1的运算就等价于对M i +1序列的运算,其结果就是M i +1序列的余式R i +1= h i +1 l i +1 。显然,这反映出一种如图1所示的递推运算的规律。可见,每一次递推运算都是对一个三字节序列的计算,所以,如何简单快捷地对三字节序列进行计算是这种算法的又一个关键。 3.2 三字节序列计算提到简单快捷,人们自然会想到采用查表的办法,例如事先把

8、三字节序列的所有余式计算出来,置于一个称为“余式表”的表格中,供随时读取。不过,这样的表格太大,需要224个单元,也就是要占用225个字节的存储空间,这对单片机来说是绝对无法接受的,因此,需要想办法减少所占用的存储空间。(5(6(7 图1 递推计算步骤设一个三字节序列T abc = a b c 、一个 T a 00= a 0 0 和一个二字节序列 T bc = b c 。可以用多项式形式表示它们之间的关系为 T abc (x =T a 00(x +T bc (x ,因此,对T a 00来说, 而对T abc 来说, 其中,Q a 00是整数,与余式无关;而R a 00和T bc 都是二字节序列

9、,因而,它们的和(模2加法,即异或运算仍然是二字节序列(二进制16位,小于生成多项式的17位,因此,它就是 T abc 的余式R abc ,即 这说明,可以把三字节序列T abc = a b c 的运算分解成两个步骤来进行,如图2所示。 1. 通过查余式表(表1,读取T a 00=a 0 0 的余式R a 00= h a 00 l a 00 ;(8(92. 将R a 00与 b c 进行异或运算,从而得到 a b c 的余式R abc = h abc l abc ,即h abc =h a 00 b ,l abc =l a 00 c 。由于a 0 0 中只有一个字节不为零,因此,a 0 0 余式

10、表仅需要256个单元,即占用512个字节。 图2 三字节序列 a b c 的计算办法4 适用于51系列等单片机的算法前面所述的办法可以直接用于51系列等单片机,因为512字节的余式表对它们的程序存储容量来说是完全不成问题的。计算直接通过上述的递推过程来进行,每一次递推都是对一个三字节序列进行的计算:第一次是 m 1 m 2m 3 ,结果是 h 3 l 3 ;第二次是 h 3 l 3 m 4 ,结果是 h 4 l 4 ;.,第i 次是 h i +1 l i +1 m i +2 ,结果是 h i +2 l i +2 ;.;最后是 h k+1 l k+1 m k+2 ,最终结果是 h l 。如果有k

11、 个数据字节,则递推k 次。下面给出一个三字节序列计算子程序,供每一次递推运算时调用。注意,在第一次被调用之前,先将m 1、 m 2和m 3分别存入R0、R1和R2中(子程序返回时,计算结果将存放在R0和R1中。从第二次调用时开始,每次在调用之前只需先将参与本次运算的字节存入R2即可(第二次是m 4,第三次是m 5,.,第i 次是m i +2,.。当最后一次调用返回后,R0和R1分别存放的就是最终结果h 和l 。 这一子程序只有12条指令,因此十分简捷,而且只占用16个机器周期,也就是说,相当于计算每一个字CRCMOV DPH, #table; 指向余式表下半区MOV DPL, R0; 指向对

12、应单元CLR A ;MOVC A, A+DPTR; 读余式的高字节XRL A, R1; 计算余式的高字节MOV R0, A; 存入R0INC DPH; 指向余式表上半区CLR A ;MOVC A, A+DPTR; 读余式的低字节XRL A, R2; 计算余式的低字节MOV R1, A; 存入R1RET这子程序只有12条指令,因此十分简捷,而且只占用16个机器周期,也就是说,相当于计算每个字节只需16个机器周期即可完成,这将比传统的软件算法快十几倍。表1 a 0 0 余式表5 适用于PIC单片机的算法表1所示的余式表虽然只占用512个字节的程序存储空间,但对于PIC单片机来说还是太大了,需要再进

13、行压缩。思路是这样的:将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=a0F0H ,f=a0FH ,因此可得,T a00=T e00 T f00,同时,还可以证明它们余式的关系为R a00=R e00 R

14、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 e00l f00。这样,三字节序列a 0 0 的计算可由图3所示的方法来进行,其中,e 0 0 和f0 0 余式表见表2和表3。表2 e 0 0 余式表表3 f 0 0 余式表saint_data_sheet 第 6 頁，共 7 頁 显然，对于PIC单片机来说，三字节序列 a b c 的计算需要综合图2和图3 所示的两种 办法来进行，下面就给出一个这样的PIC子程序，它的使用与上面所述的51系列单片机

15、子程序基本相同，即，在第一次被调用之前，先将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 的计算办法 MOVLW DATAe MOVWF ADDR BYTE

16、a，0 SWAPF ANDLW 0FH ADDR，1 ADDWF ADDR，0 MOVF CALL TABLE MOVWF MOVLW ADDWF CALL MOVWF MOVLW MOVWF MOVF ANDLW ADDWF MOVF CALL XORWF XORWF RESULTh 16 ADDR，0 TABLE RESULTl DATAf ADDR BYTEa，0 0FH ADDR，1 ADDR，0 TABLE RESULTh，0 BYTEb，0 START ；将e 0 0余式表首地址DATAe存入ADDR ；求e和e指定的e 0 0 余式高字节的相对地址 ；取其绝对地址，存入ADDR

17、；把这一绝对地址再存入W ；查表，返回时he00放在W中 ；把he00存入RESULTh ；求e指定的e 0 0余式低字节的绝对地址 ；查表，返回时le00放在W中 ；把le00存入RESULTl ；将f 0 0余式表首地址DATAf存入ADDR ；求f和f指定的f 0 0余式高字节的相对地址 ；取其绝对地址，存入ADDR ；把这一绝对地址再存入W ；查表，返回时hf00放在W中 ；he00与hf00异或，得ha00，存入W ；ha00与b异或，得habc，存入W file:/C:Documents and Settingssaint.000桌面ww_eebyte_com.htm 2003-3-13 saint_data_sheet 第 7 頁，共 7 頁 a00 abc MOVF MOVLW ADDWF CALL XORWF XORWF MOVF RETLW B