由單片機嵌入式系統(tǒng)與微機組成的工業(yè)檢測和數(shù)據(jù)采集系統(tǒng)中,計算機與單片機之間經(jīng)常需要進(jìn)行數(shù)據(jù)通信。在數(shù)字通信過程中,干擾有可能使接收到的二進(jìn)制數(shù)和發(fā)送的不一致,造成“0”和“1”互變的差錯。一個實用的通信系統(tǒng)必需能發(fā)現(xiàn)這種差錯,并加以糾正或給出重新發(fā)送信息。CRC(CyclICRedundancy Code循環(huán)冗余碼),也稱多項式編碼。是一種檢錯效率高、原理簡單、易于實現(xiàn)的通信編碼,是目前在數(shù)字通信領(lǐng)域應(yīng)用最為廣泛的一種檢驗方式。如16位的 CRC—CCITT標(biāo)準(zhǔn)可以檢測出所有的單位錯、雙位錯、奇位數(shù)錯及小于等于16位的突發(fā)錯,大于17位的突發(fā)錯檢錯率為99.9984%[1]??梢?, CRC碼的檢錯率要大大高于一般的奇偶校驗。因此CRC校驗可以應(yīng)用于重要數(shù)據(jù)的通信場合,如下位機運行狀態(tài)的檢測、運行模式或參數(shù)的在線重設(shè)置等。
對于8位的單片機系統(tǒng),要實現(xiàn)CRC通信就必須編寫生成CRC碼的指令程序,且由于單片機的程序存儲器很少、運算速度也比較低,因此要求程序代 碼盡量少,算法必須簡單。下面將以CRC—CCITT標(biāo)準(zhǔn)為例來介紹CRC通信碼的單片機實現(xiàn)過程。
1 CRC校驗碼的構(gòu)成
求得余式R(x),使等式左端的代數(shù)式恰為CRC校驗式G(x)的整數(shù)倍。則將其與待發(fā)送的數(shù)據(jù)多項式xr·M(x)相加得到的r+k次多項式的各個系數(shù)(mk-1,mk-2,…,m1,m0,rr-1,rr-2,…,r1,r0)作為編碼一起發(fā)送,其中高k位是信息位,低r位是附加校驗位。在數(shù)據(jù)接收端,再對接收到的信息碼進(jìn)行校驗,如能被同 一個G(x)整除,則表明通信正確;若余數(shù)不為0,表示數(shù)據(jù)傳輸有誤,從而達(dá)到檢錯的目的。
CRC校驗雖然不能100%檢測出錯誤,但它的漏檢率相當(dāng)?shù)?。漏檢概率和所選取的校驗標(biāo)準(zhǔn)相關(guān),國際上已有多種CRC校驗式標(biāo)準(zhǔn)。其中8位的CRC碼標(biāo)準(zhǔn)有CDT約定,其校驗式為G(x)=x8+x2+x+1;16位的標(biāo)準(zhǔn)有CCITT(國際電報電話咨詢委員會推薦)標(biāo)準(zhǔn)G(x)=x16+x12+x5+1,和IBM公司提出的CRC-16標(biāo)準(zhǔn)G(x)=x16+x12+x2+1;校驗錯誤效率最高的是具有32位CRC校驗碼的
2 多字節(jié)信息序列CRC碼的快速算法
假設(shè)需要傳送的一組信息碼N為k個字節(jié)二進(jìn)制序列:
Nk=[n1 n2……nk]
其中的ni為信息碼中的各個字節(jié)。
以16位校驗碼的CRC—CCITT標(biāo)準(zhǔn)來說明生成校驗冗余碼的快速算法。N(x)在計算冗余碼的時候應(yīng)該在后面補充兩個零字節(jié),作為待計算的信息碼。為方便起見,還統(tǒng)一用N(x)表示。
對應(yīng)的前k-1個字節(jié)構(gòu)成的序列可以表示為:
關(guān)系,若已知算式Nk-1的余項Rk-1,就可以求得Nk的余項Rk,已知Rk-2,就可求得Rk-1,依次類推。因為校驗式G(x)的最高項為16次,x8 Rk-1(x)+nk(x)的最高冪次不超過23,所以最后可歸結(jié)為求[n1 n2 n3]3字節(jié)序列余項的問題,每次遞推都進(jìn)行3字節(jié)的求余運算。按照上述的方法,很容易編制單片機上CRC校驗碼的實現(xiàn)程序。
3 CRC校驗碼在51單片機上的實現(xiàn)
以CRC-CCITT標(biāo)準(zhǔn)為例,按前面多字節(jié)數(shù)據(jù)CRC冗余碼的構(gòu)造過程,51系列單片機計算多字節(jié)數(shù)據(jù)的CRC碼程序如下。其中,從31H開始存放信息字節(jié)數(shù)據(jù),算得校驗碼的高8位存于R3,低8位存于R4。
4 CRC碼的查表方法
上面的程序中,每次計算一組3字節(jié)的CRC余項需要進(jìn)行8次循環(huán)操作,每次循環(huán)包括2字節(jié)的數(shù)據(jù)移動,和3次異或操作。對于時間要求嚴(yán)格的 數(shù)據(jù)采樣場合,速度可能跟不上。這時可以把對1字節(jié)通信數(shù)據(jù)的所有取值(共256個)求得CRC碼做成一個余項表,用查表的方法來代替余項的循環(huán)求取過程。
設(shè)一普通3字節(jié)碼為Tabc=[a b c],把它分解為一特殊的后2字節(jié)為零的3字節(jié)序列Ta00=[a 00],和一個2字節(jié)序列Tbc=[b c],可以由多項式表
其中Qa00為整數(shù)的商式,Ra00和Tbc都是最高次不超過15的余項,它們的和就是Tabc(x)的余項。每次取信息碼的3字節(jié)序列Tabc,先查表得出其中Ta00(x)的余項Ra00(x),這是一個2字節(jié)的多項式,把它和余下的2字節(jié)序列Tbc進(jìn)行異或操作,得到新的3字節(jié)序列的高2字節(jié),然后取信息碼的下一字節(jié)附于其后構(gòu)成新的3字節(jié)序列再分解為Ta00和,循環(huán)查表計算。運用這種方法可以很快求出多字節(jié)信息碼Mk的CRC冗余校驗碼。
建立16位CRC的檢驗碼表共需要2×256個字節(jié)。對于80C51系列的單片機來說,程序存儲器ROM一般都有4KB以上的空間,容量上可以滿足要求。
下面給出CRC校驗碼表的求取程序:
每種校驗規(guī)則校驗碼的最高位都為1,為編程方便,將其最高位去掉,把校驗碼的位數(shù)湊成是一個字節(jié)的整數(shù)倍。CRC—CCITT的校驗式為G(x)=x16+x12+x5+1,去掉高位后,校驗碼為0001000000100001(1021H)。取一個用來比較的16位數(shù)CRC—BYTE=8000H,逐次比較信息碼的最高位是否為1,是則將1記錄在暫存單元CRC—Temp的最低位,如果是0,則低位左移入0,每次暫存單元和信息單元循環(huán)左移,相當(dāng)于把信息字節(jié)的數(shù)據(jù)逐位從左移入暫存單元中。當(dāng)暫存單元的最高位變?yōu)?,說明已移入了16位數(shù)據(jù),然后把暫存單元再左移一次,和16位校驗碼做異或操作,也就相當(dāng)于進(jìn)行模2除。因為暫存單元被移出的最高位1和校驗碼被舍去的最高位1異或,其結(jié)果必然為零,也就等于進(jìn)行了17位異或操作。把所得的余式存放在暫存單元中,接著循環(huán),直到將信息碼和補充在尾部的零字節(jié)都操作結(jié)束,把最后的余式復(fù)給CRC—Variable輸出,完成對一個余項式的處理。
這種方法的好處是很容易實現(xiàn)對8位或者32位的校驗式求取余項表進(jìn)行擴展,只需將CRC—MODEL改為8位或32位的校驗式模型,比較字節(jié)CRC— BYTE改為80H和800000H,追加末尾0字節(jié)LAST—BYTE改為1和4個,然后再把對應(yīng)于16位數(shù)據(jù)變量CRC—Variable的 unsigned short型,改為un-signed char或unsigned long就可以了。
5 結(jié)束語
利用CRC實現(xiàn)程序可以計算出各種標(biāo)準(zhǔn)下的CRC校驗冗余碼表。在單片機容量允許的情況下,可以利用查表進(jìn)行CRC校驗。在對時間要求不高、對存儲容量要求嚴(yán)格的場合,可以直接利用循環(huán)計算來求得余項。編程使用8051系列單片機匯編語言,可以實現(xiàn)最少和高效的指令代碼。該程序算法也可應(yīng)用于 M68HC和PIC17等系列單片機上。
參考文獻(xiàn)
[1]Joe Campbell著.徐國定,廖衛(wèi)東譯.串行通訊C程序員指南[M].北京:清華大學(xué)出版社.1990.
[2]韓炬.CRC算法實現(xiàn)[J].煤炭科學(xué)技術(shù),2000,(2):11-15.