CRC校驗(yàn)碼在單片機(jī)中的程序?qū)崿F(xiàn)及其冗余碼表的求取

由單片機(jī)嵌入式系統(tǒng)與微機(jī)組成的工業(yè)檢測和數(shù)據(jù)采集系統(tǒng)中，計(jì)算機(jī)與單片機(jī)之間經(jīng)常需要進(jìn)行數(shù)據(jù)通信。在數(shù)字通信過程中，干擾有可能使接收到的二進(jìn)制數(shù)和發(fā)送的不一致，造成“0”和“1”互變的差錯(cuò)。一個(gè)實(shí)用的通信系統(tǒng)必需能發(fā)現(xiàn)這種差錯(cuò)，并加以糾正或給出重新發(fā)送信息。CRC（CyclicRedundancy Code循環(huán)冗余碼），也稱多項(xiàng)式編碼。是一種檢錯(cuò)效率高、原理簡單、易于實(shí)現(xiàn)的通信編碼，是目前在數(shù)字通信領(lǐng)域應(yīng)用最為廣泛的一種檢驗(yàn)方式。如16位的 CRC—CCITT標(biāo)準(zhǔn)可以檢測出所有的單位錯(cuò)、雙位錯(cuò)、奇位數(shù)錯(cuò)及小于等于16位的突發(fā)錯(cuò)，大于17位的突發(fā)錯(cuò)檢錯(cuò)率為99．9984％［1］。可見， CRC碼的檢錯(cuò)率要大大高于一般的奇偶校驗(yàn)。因此CRC校驗(yàn)可以應(yīng)用于重要數(shù)據(jù)的通信場合，如下位機(jī)運(yùn)行狀態(tài)的檢測、運(yùn)行模式或參數(shù)的在線重設(shè)置等。

對于8位的單片機(jī)系統(tǒng)，要實(shí)現(xiàn)CRC通信就必須編寫生成CRC碼的指令程序，且由于單片機(jī)的程序存儲器很少、運(yùn)算速度也比較低，因此要求程序代 碼盡量少，算法必須簡單。下面將以CRC—CCITT標(biāo)準(zhǔn)為例來介紹CRC通信碼的單片機(jī)實(shí)現(xiàn)過程。

1　CRC校驗(yàn)碼的構(gòu)成　

　　
求得余式R(x)，使等式左端的代數(shù)式恰為CRC校驗(yàn)式G（x）的整數(shù)倍。則將其與待發(fā)送的數(shù)據(jù)多項(xiàng)式xr·M（x）相加得到的r＋k次多項(xiàng)式的各個(gè)系數(shù)（mk－1，mk－2，…，m1，m0，rr－1，rr－2，…，r1，r0）作為編碼一起發(fā)送，其中高k位是信息位，低r位是附加校驗(yàn)位。在數(shù)據(jù)接收端，再對接收到的信息碼進(jìn)行校驗(yàn)，如能被同 一個(gè)G（x）整除，則表明通信正確；若余數(shù)不為0，表示數(shù)據(jù)傳輸有誤，從而達(dá)到檢錯(cuò)的目的。

CRC校驗(yàn)雖然不能100％檢測出錯(cuò)誤，但它的漏檢率相當(dāng)?shù)?。漏檢概率和所選取的校驗(yàn)標(biāo)準(zhǔn)相關(guān)，國際上已有多種CRC校驗(yàn)式標(biāo)準(zhǔn)。其中8位的CRC碼標(biāo)準(zhǔn)有CDT約定，其校驗(yàn)式為G（x）＝x8＋x2＋x＋1；16位的標(biāo)準(zhǔn)有CCITT（國際電報(bào)電話咨詢委員會推薦）標(biāo)準(zhǔn)G（x）＝x16＋x12＋x5＋1，和IBM公司提出的CRC－16標(biāo)準(zhǔn)G（x）＝x16＋x12＋x2＋1；校驗(yàn)錯(cuò)誤效率最高的是具有32位CRC校驗(yàn)碼的

2　多字節(jié)信息序列CRC碼的快速算法　

假設(shè)需要傳送的一組信息碼N為k個(gè)字節(jié)二進(jìn)制序列：
　　Nk＝［n1 n2……nk］

其中的ni為信息碼中的各個(gè)字節(jié)。

以16位校驗(yàn)碼的CRC—CCITT標(biāo)準(zhǔn)來說明生成校驗(yàn)冗余碼的快速算法。N（x）在計(jì)算冗余碼的時(shí)候應(yīng)該在后面補(bǔ)充兩個(gè)零字節(jié)，作為待計(jì)算的信息碼。為方便起見，還統(tǒng)一用N（x）表示。

對應(yīng)的前k－1個(gè)字節(jié)構(gòu)成的序列可以表示為：

關(guān)系，若已知算式Nk－1的余項(xiàng)Rk－1，就可以求得Nk的余項(xiàng)Rk，已知Rk－2，就可求得Rk－1，依次類推。因?yàn)樾ｒ?yàn)式G（x）的最高項(xiàng)為16次，x8 Rk－1（x）＋nk（x）的最高冪次不超過23，所以最后可歸結(jié)為求［n1 n2 n3］3字節(jié)序列余項(xiàng)的問題，每次遞推都進(jìn)行3字節(jié)的求余運(yùn)算。按照上述的方法，很容易編制單片機(jī)上CRC校驗(yàn)碼的實(shí)現(xiàn)程序。

3　CRC校驗(yàn)碼在51單片機(jī)上的實(shí)現(xiàn)　

以CRC－CCITT標(biāo)準(zhǔn)為例，按前面多字節(jié)數(shù)據(jù)CRC冗余碼的構(gòu)造過程，51系列單片機(jī)計(jì)算多字節(jié)數(shù)據(jù)的CRC碼程序如下。其中，從31H開始存放信息字節(jié)數(shù)據(jù)，算得校驗(yàn)碼的高8位存于R3，低8位存于R4。

4　CRC碼的查表方法

上面的程序中，每次計(jì)算一組3字節(jié)的CRC余項(xiàng)需要進(jìn)行8次循環(huán)操作，每次循環(huán)包括2字節(jié)的數(shù)據(jù)移動，和3次異或操作。對于時(shí)間要求嚴(yán)格的 數(shù)據(jù)采樣場合，速度可能跟不上。這時(shí)可以把對1字節(jié)通信數(shù)據(jù)的所有取值（共256個(gè)）求得CRC碼做成一個(gè)余項(xiàng)表，用查表的方法來代替余項(xiàng)的循環(huán)求取過程。

設(shè)一普通3字節(jié)碼為Tabc＝［a b c］，把它分解為一特殊的后2字節(jié)為零的3字節(jié)序列Ta00＝［a 00］，和一個(gè)2字節(jié)序列Tbc＝［b c］，可以由多項(xiàng)式表

其中Qa00為整數(shù)的商式，Ra00和Tbc都是最高次不超過15的余項(xiàng)，它們的和就是Tabc（x）的余項(xiàng)。每次取信息碼的3字節(jié)序列Tabc，先查表得出其中Ta00（x）的余項(xiàng)Ra00（x），這是一個(gè)2字節(jié)的多項(xiàng)式，把它和余下的2字節(jié)序列Tbc進(jìn)行異或操作，得到新的3字節(jié)序列的高2字節(jié)，然后取信息碼的下一字節(jié)附于其后構(gòu)成新的3字節(jié)序列再分解為Ta00和，循環(huán)查表計(jì)算。運(yùn)用這種方法可以很快求出多字節(jié)信息碼Mk的CRC冗余校驗(yàn)碼。

建立16位CRC的檢驗(yàn)碼表共需要2×256個(gè)字節(jié)。對于80C51系列的單片機(jī)來說，程序存儲器ROM一般都有4KB以上的空間，容量上可以滿足要求。

下面給出CRC校驗(yàn)碼表的求取程序：

每種校驗(yàn)規(guī)則校驗(yàn)碼的最高位都為1，為編程方便，將其最高位去掉，把校驗(yàn)碼的位數(shù)湊成是一個(gè)字節(jié)的整數(shù)倍。CRC—CCITT的校驗(yàn)式為G（x）＝x16＋x12＋x5＋1，去掉高位后，校驗(yàn)碼為0001000000100001（1021H）。取一個(gè)用來比較的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位校驗(yàn)碼做異或操作，也就相當(dāng)于進(jìn)行模2除。因?yàn)闀捍鎲卧灰瞥龅淖罡呶?和校驗(yàn)碼被舍去的最高位1異或，其結(jié)果必然為零，也就等于進(jìn)行了17位異或操作。把所得的余式存放在暫存單元中，接著循環(huán)，直到將信息碼和補(bǔ)充在尾部的零字節(jié)都操作結(jié)束，把最后的余式復(fù)給CRC—Variable輸出，完成對一個(gè)余項(xiàng)式的處理。

這種方法的好處是很容易實(shí)現(xiàn)對8位或者32位的校驗(yàn)式求取余項(xiàng)表進(jìn)行擴(kuò)展，只需將CRC—MODEL改為8位或32位的校驗(yàn)式模型，比較字節(jié)CRC— BYTE改為80H和800000H，追加末尾0字節(jié)LAST—BYTE改為1和4個(gè)，然后再把對應(yīng)于16位數(shù)據(jù)變量CRC—Variable的 unsigned short型，改為un－signed char或unsigned long就可以了。

5　結(jié)束語

利用CRC實(shí)現(xiàn)程序可以計(jì)算出各種標(biāo)準(zhǔn)下的CRC校驗(yàn)冗余碼表。在單片機(jī)容量允許的情況下，可以利用查表進(jìn)行CRC校驗(yàn)。在對時(shí)間要求不高、對存儲容量要求嚴(yán)格的場合，可以直接利用循環(huán)計(jì)算來求得余項(xiàng)。編程使用8051系列單片機(jī)匯編語言，可以實(shí)現(xiàn)最少和高效的指令代碼。該程序算法也可應(yīng)用于 M68HC和PIC17等系列單片機(jī)上。

參考文獻(xiàn)
［1］Joe Campbell著．徐國定，廖衛(wèi)東譯．串行通訊C程序員指南［M］．北京：清華大學(xué)出版社．1990．
［2］韓炬．CRC算法實(shí)現(xiàn)［J］．煤炭科學(xué)技術(shù)，2000，（2）：11－15．