摘 要： 該文介紹了一種數(shù)據(jù)傳輸中的差錯(cuò)檢測(cè)技術(shù)—CRC校驗(yàn)原理，以及CRC校驗(yàn)碼的構(gòu)造過(guò)程。給出了CRC碼在80C51系列單片機(jī)中的實(shí)現(xiàn)程序，及其冗余碼表的求取程序。
關(guān)鍵詞： CRC；80C51；校驗(yàn)
由單片機(jī)嵌入式系統(tǒng)與微機(jī)組成的工業(yè)檢測(cè)和數(shù)據(jù)采集系統(tǒng)中，計(jì)算機(jī)與單片機(jī)之間經(jīng)常需要進(jìn)行數(shù)據(jù)通信。在數(shù)字通信過(guò)程中，干擾有可能使接收到的二進(jìn)制數(shù)和發(fā)送的不一致，造成“0”和“1”互變的差錯(cuò)。一個(gè)實(shí)用的通信系統(tǒng)必需能發(fā)現(xiàn)這種差錯(cuò)，并加以糾正或給出重新發(fā)送信息。CRC（CyclicRedundancy Code循環(huán)冗余碼），也稱多項(xiàng)式編碼。是一種檢錯(cuò)效率高、原理簡(jiǎn)單、易于實(shí)現(xiàn)的通信編碼，是目前在數(shù)字通信領(lǐng)域應(yīng)用最為廣泛的一種檢驗(yàn)方式。如16位的 CRC—CCITT標(biāo)準(zhǔn)可以檢測(cè)出所有的單位錯(cuò)、雙位錯(cuò)、奇位數(shù)錯(cuò)及小于等于16位的突發(fā)錯(cuò)，大于17位的突發(fā)錯(cuò)檢錯(cuò)率為99．9984％［1］�？梢�(jiàn)， CRC碼的檢錯(cuò)率要大大高于一般的奇偶校驗(yàn)。因此CRC校驗(yàn)可以應(yīng)用于重要數(shù)據(jù)的通信場(chǎng)合，如下位機(jī)運(yùn)行狀態(tài)的檢測(cè)、運(yùn)行模式或參數(shù)的在線重設(shè)置等。
對(duì)于8位的單片機(jī)系統(tǒng)，要實(shí)現(xiàn)CRC通信就必須編寫生成CRC碼的指令程序，且由于單片機(jī)的程序存儲(chǔ)器很少、運(yùn)算速度也比較低，因此要求程序代 碼盡量少，算法必須簡(jiǎn)單。下面將以CRC—CCITT標(biāo)準(zhǔn)為例來(lái)介紹CRC通信碼的單片機(jī)實(shí)現(xiàn)過(guò)程。
1 CRC校驗(yàn)碼的構(gòu)成
傳送一K位信息的數(shù)據(jù)：M＝（mk－1，mk－2，…，m1，m0），若將其視為一多項(xiàng)式的系數(shù)，它對(duì)應(yīng)的多項(xiàng)式為：
m0。將信息碼后面添加r個(gè)0，可構(gòu)成多項(xiàng)式xr·
m0 xr。將其作為被除式，選擇一個(gè)r次的CRC校驗(yàn)式G（x）來(lái)除，得到一個(gè)商式Q（x）和余式R（x）。
之所以要填r個(gè)0，是因?yàn)镚（x）為r次多項(xiàng)式，余式R（x）最多為r－1次多項(xiàng)式，追加在xr·M（x）的后面，不會(huì)影響數(shù)據(jù)信息的系數(shù)。
CRC碼的計(jì)算過(guò)程為模2除法取余式的過(guò)程。 由于采用模除，沒(méi)有進(jìn)位和錯(cuò)位，故加減都相當(dāng)于異
求得余式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ù)接收端，再對(duì)接收到的信息碼進(jìn)行校驗(yàn)，如能被同 一個(gè)G（x）整除，則表明通信正確；若余數(shù)不為0，表示數(shù)據(jù)傳輸有誤，從而達(dá)到檢錯(cuò)的目的。
例如要傳送8位數(shù)據(jù)91H（10010001），可把它看成是7次多項(xiàng)式M（x）＝x7＋x4＋1的系數(shù)，CRC校驗(yàn)碼為4次多項(xiàng)式G（x）＝x4＋x2＋1，系數(shù)為10101。x4·M（x）為100100010000，模2除法的詳細(xì)計(jì)算過(guò)程如圖1所示。算得的余式R（x）為1011，將其附加于數(shù)據(jù)信息后面，發(fā)送的數(shù)據(jù)編碼為
其中前8位是信號(hào)信息，后4位是計(jì)算得來(lái)的附加校驗(yàn)信息。接收端用G（x）檢驗(yàn)正確后，合棄后4位，得到有用的用戶數(shù)據(jù)信息。從圖1的計(jì)算過(guò)程可以看出，雖然每次運(yùn)算都有5位參與，但最左面的高位總是為1，且運(yùn)算結(jié)果為0。
CRC校驗(yàn)雖然不能100％檢測(cè)出錯(cuò)誤，但它的漏檢率相當(dāng)?shù)�。漏檢概率和所選取的校驗(yàn)標(biāo)準(zhǔn)相關(guān)，國(guó)際上已有多種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（國(guó)際電報(bào)電話咨詢委員會(huì)推薦）標(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)來(lái)說(shuō)明生成校驗(yàn)冗余碼的快速算法。N（x）在計(jì)算冗余碼的時(shí)候應(yīng)該在后面補(bǔ)充兩個(gè)零字節(jié)，作為待計(jì)算的信息碼。為方便起見(jiàn)，還統(tǒng)一用N（x）表示。
對(duì)應(yīng)的前k－1個(gè)字節(jié)構(gòu)成的序列可以表示為：
