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

1 引言

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

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

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

2　CRC原理

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

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

（1）

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

（2）

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

（3） 或表示為

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

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

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

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

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