簡(jiǎn)單有效的單片機(jī)CRC快速算法

1、簡(jiǎn)單實(shí)用的單片機(jī)CRC快速算法1引言CRC(循環(huán)冗余碼)檢驗(yàn)技術(shù)廣泛應(yīng)用于測(cè)控及通信領(lǐng)域。在很多情況下，CRCH算是匏專用的硬件來(lái)實(shí)現(xiàn)的，但是對(duì)于小型低成本的小片機(jī)系統(tǒng)來(lái)說(shuō)，若要在沒有這些硬件的支持下實(shí)現(xiàn)CRC檢驗(yàn)，首先要解決的就是如何通過軟件高效快速地完成CRC計(jì)算的問題，也就是CRC算法的問題。這里將提供兩種算法，它們稍有不同，一種適用于程序空間大一些的51系列等玳片機(jī)，另一種適用于程序空間的使用條件十分苛刻的PIC單片機(jī)。這些算法按字節(jié)進(jìn)行計(jì)算，僅使用查表和簡(jiǎn)單.的異或運(yùn)算等操作，所以，計(jì)算過程相當(dāng)簡(jiǎn)捷.而計(jì)算速度卻很快。下面先簡(jiǎn)述一下CRC原理，然后再以CRC-CCITT標(biāo)準(zhǔn)生成多項(xiàng)式

2、為例對(duì)算法進(jìn)行說(shuō)明，并給出一個(gè)51系列單片機(jī)子程序和一個(gè)PIC的片機(jī)子程序。2CRC原理CRC檢驗(yàn)原理實(shí)際上就是在一個(gè)p位二進(jìn)制數(shù)據(jù)序列之后附加一個(gè)r位二進(jìn)制檢驗(yàn)碼。字列)，從而構(gòu)成一個(gè)總長(zhǎng)為n=p+r位的二進(jìn)制序列，例如，p位二進(jìn)制數(shù)據(jù)序列D=dp-ldp-2did。,r位二進(jìn)制檢驗(yàn)碼R=rr-1rr-2.rlrO，所得到的這個(gè)n位二進(jìn)制序列就是M=dp-ldp-2dldOrr«lrr-2.rlrO：附加在數(shù)據(jù)序列之后的這個(gè)檢驗(yàn)碼與數(shù)據(jù)序列的內(nèi)容之間存在著某種特定的關(guān)系。如果因干擾等原因使數(shù)據(jù)序列中的某一位或某些位發(fā)生錯(cuò)誤，這種特定關(guān)系就會(huì)被破壞，因此,通過檢查這一關(guān)系，就可以實(shí)現(xiàn)

3、對(duì)數(shù)據(jù)正確性的檢驗(yàn)。校驗(yàn)碼R是通過對(duì)數(shù)據(jù)序列D進(jìn)行二進(jìn)制除法取余式運(yùn)算得到的，它被一個(gè)稱為生成多項(xiàng)式的(r+1)位二進(jìn)制序列G=grgr-1.glgO來(lái)除，用多項(xiàng)式形式表示為至”的中3(1)如)*代力其中，xrD(x)表示將數(shù)據(jù)序列D左移r位(即在D的末尾再增加r個(gè)0位)，Q(x)代表這一除法所得的商，R(x)就是所需的余式。這一運(yùn)算關(guān)系還可以用式(2)來(lái)表達(dá)畋卜時(shí)器(2)其中，Re表示對(duì)括號(hào)內(nèi)的式子進(jìn)行取余式運(yùn)算。檢驗(yàn)碼的編碼計(jì)算如上所述，而檢驗(yàn)過程則是對(duì)M序列直接進(jìn)行除法取余式運(yùn)算，即=(3)G國(guó)"G或表示為( 4)典即=Re所得到的余式R(x)若為零則表示數(shù)據(jù)正確，否則認(rèn)為發(fā)生

4、錯(cuò)誤。3快速算法的基本思路這里僅以CRCCCR7標(biāo)準(zhǔn)生成多項(xiàng)式為例進(jìn)行說(shuō)明。CRCCCITT是一個(gè)17位生成多項(xiàng)式G=10001000000100001,用多項(xiàng)式形式表示為G(x)=x16+x12+x5+1,由它產(chǎn)生的檢驗(yàn)碼R的二進(jìn)制位數(shù)是16位(2字節(jié))。單片機(jī)的操作是以字節(jié)形式進(jìn)行的，所以，算法應(yīng)以字節(jié)為旗位進(jìn)行運(yùn)算。這里將把用字節(jié)構(gòu)成的二進(jìn)制序列稱為“字節(jié)序列”，顯然，的片機(jī)的數(shù)據(jù)序列、檢驗(yàn)碼以及它倆組成的序列M都是字節(jié)序列，或者說(shuō)是“影字節(jié)序列工實(shí)際上，這種算法所要解決的問題就是如何對(duì)多字節(jié)序列進(jìn)行除法取余式運(yùn)算的問題。多字節(jié)序列運(yùn)算規(guī)律首先設(shè)一個(gè)由i個(gè)字節(jié)ml、m2mi1、mi構(gòu)成的

5、8xi位二進(jìn)制序列，并用字節(jié)形式表示它為Mi=(m1m2mi-1mi.然后再截取Mi的前(i-1)個(gè)字節(jié)構(gòu)成一個(gè)Mi-1序列，Mi-1=m1m2mi1,這兩個(gè)序列之間的關(guān)系可以用多項(xiàng)式表示為Mi(x)=x8Mi1(x)+mi(x),其中，mi(x)是字節(jié)mi的二進(jìn)制多項(xiàng)式表示形式，而x8Mi.1(x)表示將Mi1序列左移一個(gè)字節(jié)。對(duì)于序列Mi1來(lái)說(shuō)，如"=必_倒十0幽G(x)21G(x)皿其中，二字節(jié)序列余式Ri-1=hMIMo而對(duì)于Mi序列來(lái)說(shuō)，可得M印_Atfs-lN+叫_Fo.卜/國(guó)-向十叫你住)兩麗殳"函''這一結(jié)果的前一項(xiàng)為一整數(shù)，所以它與余式無(wú)關(guān)

6、，這樣，余式只可能出現(xiàn)在后一項(xiàng)中。因此，對(duì)x8Ri1(x)+mi(x)取余式運(yùn)算就等價(jià)于對(duì)Mi(x)的取余式運(yùn)算，用式(4)的形式表示為x8Ri1(x)+mi(x)代表一個(gè)由Ri-1和mi共同組成的三字節(jié)序列hi1li"mi,而且對(duì)這個(gè)三字節(jié)序列的取余式運(yùn)算就等于對(duì)Mi序列的取余式運(yùn)算，其結(jié)果就是Mi序列的余式Ri=hili。同理可得，對(duì)于一個(gè)Mi+1序列(它比Mi序列多一個(gè)字節(jié)mi+1)來(lái)說(shuō)，對(duì)三字節(jié)序列hilimi+1的運(yùn)算就等價(jià)于對(duì)Mi+1序列的運(yùn)算，其結(jié)果就是Mi+1序列的余式Ri+1=hi+1li+1o顯然，這反映出一種如圖1所示的遞推運(yùn)算的規(guī)律。可見，每一次遞推運(yùn)算都是對(duì)

7、一個(gè)三字節(jié)序列的計(jì)算，所以，如何簡(jiǎn)玳快捷地對(duì)三字節(jié)序列進(jìn)行計(jì)算是這種算法的又一個(gè)關(guān)鍵。三字節(jié)序列il算提到簡(jiǎn)單快捷，人們自然會(huì)想到采用查表的辦法，例如事先把三字節(jié)序列的所有余式計(jì)算出來(lái)，置于一個(gè)稱為.余式表”的表格中，供隨時(shí)讀取。不過，這樣的表格太大，需要224個(gè)玳元，也就是要占用225個(gè)字節(jié)的存儲(chǔ)空間，這對(duì)單.片機(jī)來(lái)說(shuō)是絕對(duì)無(wú)法接受的，因此，需要想辦法減少所占用的存儲(chǔ)空間。數(shù)據(jù)字節(jié)余式圖1遞推計(jì)算步驟設(shè)一個(gè)三字節(jié)序列Tabe=abc、一個(gè)TaOO=aOO和一個(gè)二字節(jié)序列Tbc=bco可以用多項(xiàng)式形式表示它們之間的關(guān)系為Tabc（x）=TaOO（x）+Tbc（x）,因此，對(duì)TaOO來(lái)說(shuō)，而對(duì)T

8、abe來(lái)說(shuō)，其中，QaOO是整數(shù)，與余式無(wú)關(guān)：而RaOO和Tbc都是二字節(jié)序列，因而，它們的和（模2加法，即異或運(yùn)算）仍然是二字節(jié)序列（二進(jìn)制16位，小干生成多項(xiàng)式的17位），因此，它就是Tabe的余式Rabe,即尺血二尺加。）十兀。）<9）這說(shuō)明，可以把三字節(jié)序列Tabc=abe的運(yùn)算分解成兩個(gè)步驟來(lái)進(jìn)行，如圖2所示。1 ,通過查余式表（表1）,讀取TaOO=aOO的余式RaOO=haOOIaOO：2 .將RaOO與be進(jìn)行異或運(yùn)算，從而得至北abc的余式Rabc=habclabc,UPhabc=haOO?b,labc=laOO?co由于a00中只有一個(gè)字節(jié)不為零，因此，a00余式表僅

9、需要256個(gè)的元，即占用512個(gè)字節(jié)。圖2三字書序列abc的計(jì)鼓辦法4適用于51系列等小片機(jī)的算法前面所述的辦法可以直接用于51系列等單片機(jī)，因?yàn)?12字節(jié)的余式表對(duì)它們的程序存儲(chǔ)容量來(lái)說(shuō)是完全不成問題的。計(jì)算直接通過上述的遞推過程來(lái)進(jìn)行,每一次遞推都是對(duì)一個(gè)三字節(jié)序列進(jìn)行的計(jì)算：第一次是mim2m3，結(jié)果是h3I3：第二次是h313m4,結(jié)果是h4l4；，第i次是hi+1li+1mi+2,結(jié)果是hi+2li+2：最后是hk+Wk+1mk+2,最終結(jié)果是hl。如果有k個(gè)數(shù)據(jù)字節(jié)，則遞推k次。下面給出一個(gè)三字節(jié)序列計(jì)算子程序，供每一次遞推運(yùn)算時(shí)調(diào)用。注意，在第一次被調(diào)用之前，先將ml、m2和m3

10、分別存入RO、R1和R2中（子程序返回時(shí)，計(jì)算結(jié)果將存放在R0和R1中）。從第二次調(diào)用時(shí)開始，每次在調(diào)用之前只需先將參與本次運(yùn)算的字節(jié)存入R2即可（第二次是m4,第三次是m5，第i次是mi+2,）。當(dāng)最后一次調(diào)用返回后,R0和R1分別存放的就是最終結(jié)果h和I。CRCMOVDPH,#table;指向余式表下半?yún)^(qū)MOVDPL,R0;指向?qū)?yīng)單元CLRA;MOVCA,A+DPTR;讀余式的高字節(jié)XRLAR1;計(jì)算余式的高字節(jié)MOVRO,A;存入ROINCDPH;指向余式表上半?yún)^(qū)CLRA;MOVCA,A+DPTR;讀余式的低字節(jié)XRLAfR2;計(jì)算余式的低字節(jié)M0VR1,A;存入R1RET這一子程序只

11、有12條指令，因此十分簡(jiǎn)捷，而且只占用16個(gè)機(jī)器周期，也就是說(shuō)，相當(dāng)于計(jì)算每一個(gè)字節(jié)只需16個(gè)機(jī)器周期即可完成，這將比傳統(tǒng)的軟件算法快十幾倍。a012：3q55780ABCDZ?XOODO102L20423。&39SQS0A550CS70ET81089L2。從14AB16BC18CD1AJ1LC£nn!±3!021G32732252S2BS4之9472FT62%93s98318B37BA35ID3BD?3FT£3UE2X246234430420140164B87U7UM5儂A5&AB54B85289569ESEEPSC?5ACD5&D3XJ

12、&532G721G1106307GD7MF8569548型P7S.BA77A97198738FWE7FED791C7BC4X*58E5688678K708401861280?3823C«TD9EBE®EF3AP8M89959A90AB52B5X5AT5TAB?6A961A710A5O3A33-2A12DJFDCBDCFBBEEBBE98798653BB3BABIA&XTC6T5CC52c223530C&>LMIrwrC&KDDCIU>2ABIOB6D589D49TX7E976Z&e5ED5343E132E32IE510F7

13、0FF9FEFBEDFDDCFFCBF1B9F598F78&X*888iA9B1CAAIEBDEWCi2DFI4EEi6F!0WOOA13W220E3W2570469文83D99398加B3DAC33HH21CE37FF3SE02BJ129022P332D2423s52146277UKW4C|CWDF融9908B澗LASM5a44或55827京QD6E138S2PXCMQ|OT5CEP5F8BF9W55網(wǎng)硒QAFIiwro2M3EXFliSEEDCiPliDKCJ4DBDUAB8B9DB5的7C«GMsew4C4?3CA22C83tCBOEPIPPF3BCP5DDF7CAP9

14、iJFEA8FW9FPS6S17nx4K55E742ra33BB2OEM5適用于PIC5片機(jī)的算法表1所示的余式表雖然只占用512個(gè)字節(jié)的程序存儲(chǔ)空間，但對(duì)于PIC玳片機(jī)來(lái)說(shuō)還是太大了,需要再進(jìn)行樂縮。思路是這樣的：將TaOO=a00分解成TeOO=e00和TfOO=f00,并使字節(jié)e的上半字節(jié)內(nèi)容與a的上半字節(jié)相同但下半字節(jié)為零，同時(shí)使字節(jié)f的下半字節(jié)內(nèi)容與a的下半字節(jié)相同但上半字節(jié)為零，然后用TeOO和TfOO生成余式表來(lái)代替TaOO余式表。由于TeOO和TfOO中只有半個(gè)字節(jié)不為零，所以,每個(gè)余式表只需16個(gè)單.元（32個(gè)字節(jié)），兩個(gè)余式表總共只占用64個(gè)字節(jié)，這樣就可滿足PIC的片機(jī)的

15、要求由上述思路可知,e=a/0F0H,f=aAOFH,因此可得，Ta00=Te00?TfOO,同時(shí)，還可以證明它們余式的關(guān)系為Ra00=Re00?RfOO,也就是說(shuō),如果設(shè)Ra00=haOOlaOO、Re00=heOOleOO1RfOO=hfOOIfOO,則ha00=heOO?hfOO,la00=le00?IfOOo這樣，三字節(jié)序列a00的計(jì)算可由圖3所示的方法來(lái)進(jìn)行,其中，e00和f00余式表見表2和表3,表2e00余式表0010勃40曲鈕I忖90柏的C0to202ODOO123!24623653*5AJ56CA67E9T918883MB5EMA7DBD94CCB7DFD2ZEF1F0001

16、0203(M0506070509GA.0BOC0DGEOF000010212042306340弘60A50C670E781089E29AL4ABL6BCISCDLADEICEFIEF顯:然，對(duì)于PIC單片機(jī)來(lái)說(shuō)，三字節(jié)序列abe的il算需要綜合圖2和圖3所示的兩種辦法來(lái)進(jìn)行，下而就給出一個(gè)這樣的PIC子程序，它的使用與上面所述的51系列單片機(jī)子程序基本相同，即，在第一次被調(diào)用之前，先將ml、m2和m3分別存入通用寄存器BYTEa、BYTEb和BYTEc中：從第二次調(diào)用時(shí)開始，每次在調(diào)用之前只需先將參與本次運(yùn)算的字節(jié)存入BYTEc即可（第二次是m4,第三次是m5.，第i次是mi+2,）。每次子程

17、序返回時(shí)，計(jì)算結(jié)果將存放在BYTEa和BYTEb中,最后一次調(diào)用返回后,BYTEa和BYTEb分別存放的就是最終結(jié)果h和L子程序中,除BYTEa.BYTEb和BYTEc外,ADDR、RESULTh和RESULTI也是通用寄存器。STARTMOVLWDATAeMOVWFADDR:將e00余式表首地址DATAe存入ADDRSWAPFBYTEa.0ANDLWOFH：求e和e指定的e00余式高字節(jié)的相對(duì)地址ADDWFADDR,1：取其絕對(duì)地址，存入ADDRMOVFADDR,0：把這一絕對(duì)地址再存入WCALLTABLE：查表，返回時(shí)heOO放在W中MOVWFRESULTh：把heOO存入RESULThMOVLW16ADDWFADDR.0：求e指定的e00余式低字節(jié)的絕對(duì)地址CALLTABLE：查表，返回時(shí)leOO放在W中MOVWFRESULTI：把leOO存入RESULTIMOVLWDATA!MOVWFADDR：將f00余式表首地址DATAf存入ADDRMOVFBYTEa,0ANDLWOFH：求f和f指定的f00余式高字節(jié)的相對(duì)地址ADDWFADDR,1：取其絕對(duì)地址，存入ADDRMOVFADDR,0