單片機(jī)CRC快速算法

1 引言

CRC（循環(huán)冗余碼）檢驗(yàn)技術(shù)廣泛應(yīng)用于測(cè)控及通信領(lǐng)域。在很多情況下，CRC計(jì)算是靠專用的硬件來(lái)實(shí)現(xiàn)的，但是對(duì)于小型低成本的單片機(jī)系統(tǒng)來(lái)說(shuō)，若要在沒(méi)有這些硬件的支持下實(shí)現(xiàn)CRC檢驗(yàn)，首先要解決的就是如何通過(guò)軟件高效快速地完成CRC計(jì)算的問(wèn)題，也就是CRC算法的問(wèn)題。

這里將提供兩種算法，它們稍有不同，一種適用于程序空間大一些的51系列等單片機(jī)，另一種適用于程序空間的使用條件十分苛刻的PIC單片機(jī)。這些算法按字節(jié)進(jìn)行計(jì)算，僅使用查表和簡(jiǎn)單的異或運(yùn)算等操作，所以，計(jì)算過(guò)程相當(dāng)簡(jiǎn)捷，而計(jì)算速度卻很快。

下面先簡(jiǎn)述一下CRC原理，然后再以CRC-CCITT標(biāo)準(zhǔn)生成多項(xiàng)式為例對(duì)算法進(jìn)行說(shuō)明，并給出一個(gè)51系列單片機(jī)子程序和一個(gè)PIC單片機(jī)子程序。

2　CRC原理

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-1dp-2 ......d1d0]，r位二進(jìn)制檢驗(yàn)碼R＝[rr-1 rr-2....r1 r0]，所得到的這個(gè)n位二進(jìn)制序列就是M＝[dp-1dp-2 ......d1d0 rr-1 rr-2....r1 r0]； 附加在數(shù)據(jù)序列之后的這個(gè)檢驗(yàn)碼與數(shù)據(jù)序列的內(nèi)容之間存在著某種特定的關(guān)系。如果因干擾等原因使數(shù)據(jù)序列中的某一位或某些位發(fā)生錯(cuò)誤，這種特定關(guān)系就會(huì)被破壞,因此,通過(guò)檢查這一關(guān)系, 就可以實(shí)現(xiàn)對(duì)數(shù)據(jù)正確性的檢驗(yàn)。

校驗(yàn)碼R是通過(guò)對(duì)數(shù)據(jù)序列D進(jìn)行二進(jìn)制除法取余式運(yùn)算得到的，它被一個(gè)稱為生成多項(xiàng)式的（r＋1）位二進(jìn)制序列G＝[gr gr-1 .... g1 g0]來(lái)除，用多項(xiàng)式形式表示為

（1）

其中，xrD(x)表示將數(shù)據(jù)序列D左移r位（即在D的末尾再增加r個(gè)0位），Q(x)代表這一除法所得的商，R(x)就是所需的余式。這一運(yùn)算關(guān)系還可以用式（2）來(lái)表達(dá)

（2）

其中，Re[ ]表示對(duì)括號(hào)內(nèi)的式子進(jìn)行取余式運(yùn)算。 檢驗(yàn)碼的編碼計(jì)算如上所述，而檢驗(yàn)過(guò)程則是對(duì)M序列直接進(jìn)行除法取余式運(yùn)算，即

（3） 或表示為

（4） 所得到的余式R(x)若為零則表示數(shù)據(jù)正確，否則認(rèn)為發(fā)生錯(cuò)誤。

3 快速算法的基本思路 這里僅以CRC-CCITT標(biāo)準(zhǔn)生成多項(xiàng)式為例進(jìn)行說(shuō)明。CRC-CCITT是一個(gè)17位生成多項(xiàng)式G＝[1 0001 0000 0010 0001]，用多項(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í)際上，這種算法所要解決的問(wèn)題就是如何對(duì)多字節(jié)序列進(jìn)行除法取余式運(yùn)算的問(wèn)題。3.1 多字節(jié)序列運(yùn)算規(guī)律 首先設(shè)一個(gè)由i個(gè)字節(jié) m1、m2、......、mi-1、mi 構(gòu)成的8×i位二進(jìn)制序列，并用字節(jié)形式表示它為Mi ＝[ m1 m2 ...... mi-1 mi ]，然后再截取Mi的前（i-1）個(gè)字節(jié)構(gòu)成一個(gè)Mi-1序列，Mi-1＝[ m1 m2 ...... mi-1 ]，這兩個(gè)序列之間的關(guān)系可以用多項(xiàng)式表示為Mi(x)＝x 8Mi-1(x)＋mi(x)，其中，mi(x)是字節(jié)mi的二進(jìn)制多項(xiàng)式表示形式，而x8Mi-1(x)表示將Mi-1序列左移一個(gè)字節(jié)。 對(duì)于序列Mi-1來(lái)說(shuō)，

(5)
其中，二字節(jié)序列余式Ri-1＝［hi-1 li-1］。 而對(duì)于Mi序列來(lái)說(shuō)，可得

(6) 這一結(jié)果的前一項(xiàng)為一整數(shù)，所以它與余式無(wú)關(guān)，這樣，余式只可能出現(xiàn)在后一項(xiàng)中。因此，對(duì)x8Ri-1(x)＋mi(x)取余式運(yùn)算就等價(jià)于對(duì)Mi(x)的取余式運(yùn)算,用式（4）的形式表示為

(7) x8Ri-1(x)+mi(x)代表一個(gè)由Ri-1和mi共同組成的三字節(jié)序列[ hi-1 li-1 mi]，而且對(duì)這個(gè)三字節(jié)序列的取余式運(yùn)算就等于對(duì)Mi序列的取余式運(yùn)算，其結(jié)果就是Mi序列的余式Ri＝[ hi li ]。同理可得，對(duì)于一個(gè)Mi+１序列（它比Mi序列多一個(gè)字節(jié)mi+1）來(lái)說(shuō)，對(duì)三字節(jié)序列[ hi li mi+1]的運(yùn)算就等價(jià)于對(duì)Mi+1序列的運(yùn)算，其結(jié)果就是Mi+1序列的余式Ri+1＝[ hi+1 li+1 ]。 顯然，這反映出一種如圖1所示的遞推運(yùn)算的規(guī)律?？梢?jiàn)，每一次遞推運(yùn)算都是對(duì)一個(gè)三字節(jié)序列的計(jì)算，所以，如何簡(jiǎn)單快捷地對(duì)三字節(jié)序列進(jìn)行計(jì)算是這種算法的又一個(gè)關(guān)鍵。