简单有效的单片机CRC快速算法.docx

简单实用的单片机CRC快速算法1引言CRC(循环冗余码)检验技术广泛应用于测控及通信领域在很多情况下，CRCH•算是匏专用的硬件来实现的，但是对于小型低成本的小片机系统来说，若要在没有这些硬件的支持下实现CRC检验，首先要解决的就是如何通过软件高效快速地完成CRC计算的问题，也就是CRC算法的问题这里将提供两种算法，它们稍有不同，一种适用于程序空间大一些的51系列等玳片机，另一种适用于程序空间的使用条件十分苛刻的PIC单片机这些算法按字节进行计算，仅使用查表和简单.的异或运算等操作，所以，计算过程相当简捷.而计算速度却很快下面先简述一下CRC原理，然后再以CRC-CCITT标准生成多项式为例对算法进行说明，并给出一个51系列单片机子程序和一个PIC的片机子程序2CRC原理CRC检验原理实际上就是在一个p位二进制数据序列之后附加一个r位二进制检验码字列)，从而构成一个总长为n=p+r位的二进制序列，例如，p位二进制数据序列D=［dp-ldp-2did］,r位二进制检验码R=［rr-1rr-2.・…rlrO］，所得到的这个n位二进制序列就是M=［dp-ldp-2dldOrr«lrr-2....rlrO］：附加在数据序列之后的这个检验码与数据序列的内容之间存在着某种特定的关系。

如果因干扰等原因使数据序列中的某一位或某些位发生错误，这种特定关系就会被破坏，因此,通过检查这一关系，就可以实现对数据正确性的检验校验码R是通过对数据序列D进行二进制除法取余式运算得到的，它被一个称为生成多项式的(r+1)位二进制序列G=［grgr-1....glgO］来除，用多项式形式表示为至”的中3(1)如)*代力其中，xrD(x)表示将数据序列D左移r位(即在D的末尾再增加r个0位)，Q(x)代表这一除法所得的商，R(x)就是所需的余式这一运算关系还可以用式(2)来表达畋卜时■器］(2)其中，Re［］表示对括号内的式子进行取余式运算检验码的编码计算如上所述，而检验过程则是对M序列直接进行除法取余式运算，即——=(3)G国"G㈤或表示为( 4)典即=Re[所得到的余式R(x)若为零则表示数据正确，否则认为发生错误3快速算法的基本思路这里仅以CRCCCR7标准生成多项式为例进行说明CRCCCITT是一个17位生成多项式G=[10001000000100001],用多项式形式表示为G(x)=x16+x12+x5+1,由它产生的检验码R的二进制位数是16位(2字节)单片机的操作是以字节形式进行的，所以，算法应以字节为旗位进行运算。

这里将把用字节构成的二进制序列称为“字节序列”，显然，的片机的数据序列、检验码以及它俩组成的序列M都是字节序列，或者说是“影字节序列工实际上，这种算法所要解决的问题就是如何对多字节序列进行除法取余式运算的问题多字节序列运算规律首先设一个由i个字节ml、m2mi・1、mi构成的8xi位二进制序列，并用字节形式表示它为Mi=(m1m2……mi-1mi].然后再截取Mi的前(i-1)个字节构成一个Mi-1序列，Mi-1=[m1m2……mi・1],这两个序列之间的关系可以用多项式表示为Mi(x)=x8Mi・1(x)+mi(x),其中，mi(x)是字节mi的二进制多项式表示形式，而x8Mi.1(x)表示将Mi・1序列左移一个字节对于序列Mi・1来说，如"=必_倒十0幽⑸G(x)21G(x)皿其中，二字节序列余式Ri-1=[hMIM]o而对于Mi序列来说，可得M印_Atfs-lN+叫⑶_Fo㈤.卜/国-向十叫你住)两丽殳"函''这一结果的前一项为一整数，所以它与余式无关，这样，余式只可能出现在后一项中因此，对x8Ri・1(x)+mi(x)取余式运算就等价于对Mi(x)的取余式运算，用式(4)的形式表示为x8Ri・1(x)+mi(x)代表一个由Ri-1和mi共同组成的三字节序列[hi・1li"mi],而且对这个三字节序列的取余式运算就等于对Mi序列的取余式运算，其结果就是Mi序列的余式Ri=[hili]。

同理可得，对于一个Mi+1序列(它比Mi序列多一个字节mi+1)来说，对三字节序列[hilimi+1]的运算就等价于对Mi+1序列的运算，其结果就是Mi+1序列的余式Ri+1=[hi+1li+1]o显然，这反映出一种如图1所示的递推运算的规律可见，每一次递推运算都是对一个三字节序列的计算，所以，如何简玳快捷地对三字节序列进行计算是这种算法的又一个关键三字节序列il•算提到简单快捷，人们自然会想到采用查表的办法，例如事先把三字节序列的所有余式计算出来，置于一个称为.余式表”的表格中，供随时读取不过，这样的表格太大，需要224个玳元，也就是要占用225个字节的存储空间，这对单.片机来说是绝对无法接受的，因此，需要想办法减少所占用的存储空间数据字节余式图1递推计算步骤设一个三字节序列Tabe=［abc］、一个TaOO=［aOO］和一个二字节序列Tbc=［bc］o可以用多项式形式表示它们之间的关系为Tabc（x）=TaOO（x）+Tbc（x）,因此，对TaOO来说，而对Tabe来说，其中，QaOO是整数，与余式无关：而RaOO和Tbc都是二字节序列，因而，它们的和（模2加法，即异或运算）仍然是二字节序列（二进制16位，小干生成多项式的17位），因此，它就是Tabe的余式Rabe,即尺血⑺二尺加。

十兀<9）这说明，可以把三字节序列Tabc=［abe］的运算分解成两个步骤来进行，如图2所示1 ,通过查余式表（表1）,读取TaOO=［aOO］的余式RaOO=［haOOIaOO］：2 .将RaOO与［be］进行异或运算，从而得至北abc］的余式Rabc=［habclabc］,UPhabc=haOO?b,labc=laOO?co由于［a00］中只有一个字节不为零，因此，［a00］余式表仅需要256个的元，即占用512个字节图2三字书序列［abc］的计鼓办法4适用于51系列等小片机的算法前面所述的办法可以直接用于51系列等单片机，因为512字节的余式表对它们的程序存储容量来说是完全不成问题的计算直接通过上述的递推过程来进行,每一次递推都是对一个三字节序列进行的计算：第一次是［mim2m3］，结果是［h3I3］：第二次是［h313m4］,结果是［h4l4］；……，第i次是［hi+1li+1mi+2］,结果是［hi+2li+2］：……：最后是［hk+Wk+1mk+2］,最终结果是［hl］如果有k个数据字节，则递推k次下面给出一个三字节序列计算子程序，供每一次递推运算时调用注意，在第一次被调用之前，先将ml、m2和m3分别存入RO、R1和R2中（子程序返回时，计算结果将存放在R0和R1中）。

从第二次调用时开始，每次在调用之前只需先将参与本次运算的字节存入R2即可（第二次是m4,第三次是m5，…，第i次是mi+2,…）当最后一次调用返回后,R0和R1分别存放的就是最终结果h和ICRCMOVDPH,#table;指向余式表下半区MOVDPL,R0;指向对应单元CLRA;MOVCA,@A+DPTR;读余式的高字节XRLAR1;计算余式的高字节MOVRO,A;存入ROINCDPH;指向余式表上半区CLRA;MOVCA,@A+DPTR;读余式的低字节XRLAfR2;计算余式的低字节M0VR1,A;存入R1RET这一子程序只有12条指令，因此十分简捷，而且只占用16个机器周期，也就是说，相当于计算每一个字节只需16个机器周期即可完成，这将比传统的软件算法快十几倍a012：3q55780ABCDZ?□XOODO102L2042339SQS0A550CS70ET81089L2从14AB16BC18CD1AJ1LC£nn!±3!021G32732252S2BS4之9472FT62%93s98318B37BA35ID3BD?3FT£3UE2X246234430420140164B87U7UM5侬A5&AB54B85289569ESEEPSC?€5ACD5&D3XJ&532G721G1106307GD7MF8569548型P7S.BA77A97198738FWE7FED791C7BC4X*58E5688678K708401861280?3823C«TD9EBE®EF3AP8M89959A90AB52B5X5AT5TAB?6A961A710A5O3A33-2A12DJFDCBDCFBBEEBBE98798653BB3BABIA&XTC6T5CC52c223530C&>LMIrwrC&KDDCIU>2ABIOB6D589D49TX7E976Z&e5ED5343E132E32IE510F70FF9FEFBEDFDDCFFCBF1B9F598F78&X*888iA9B1CAAIEBDEWCi2DFI4EEi6F!0WOOA13W220E3W2570469文83D99398加B3DAC33HH21CE37FF3SE02BJ129022P332D2423s52146277UKW4C|CWDF融9908B涧LASM5a44或55827京QD6E138S2PXCMQ|OT5CEP5F8BF9W55网硒QAFIiwro2M3EXFliSEEDCiPliDKCJ4DBDUAB8B9DB5的7C«GMsew4C4?3CA22C83tCBOEPIPPF3BCP5DDF7CAP9iJFEA8FW9FPS6S17nx4K55E742ra33BB2OEM5适用于PIC5片机的算法表1所示的余式表虽然只占用512个字节的程序存储空间，但对于PIC玳片机来说还是太大了,需要再进行乐缩。

思路是这样的：将TaOO=[a00]分解成TeOO=[e00]和TfOO=[f00],并使字节e的上半字节内容与a的上半字节相同但下半字节为零，同时使字节f的下半字节内容与a的下半字节相同但上半字节为零，然后用TeOO和TfOO生成余式表来代替TaOO余式表由于TeOO和TfOO中只有半个字节不为零，所以,每个余式表只需16个单.元（32个字节），两个余式表总共只占用64个字节，这样就可满足PIC的片机的要求由上述思路可知,e=a/\0F0H,f=aAOFH,因此可得，Ta00=Te00?TfOO,同时，还可以证明它们余式的关系为Ra00=Re。