單片機CRC快速算法

1 引言

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

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

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

2　CRC原理

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

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

（1）

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

（2）

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

（3） 或表示為

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

3 快速算法的基本思路 這里僅以CRC-CCITT標準生成多項式為例進(jìn)行說(shuō)明。CRC-CCITT是一個(gè)17位生成多項式G＝[1 0001 0000 0010 0001]，用多項式形式表示為G(x)＝x16＋x12＋x5＋1，由它產(chǎn)生的檢驗碼R的二進(jìn)制位數是16位（2字節）。 單片機的操作是以字節形式進(jìn)行的，所以，算法應以字節為單位進(jìn)行運算。這里將把用字節構成的二進(jìn)制序列稱(chēng)為“字節序列”，顯然，單片機的數據序列、檢驗碼以及它倆組成的序列M都是字節序列，或者說(shuō)是“多字節序列”。 實(shí)際上，這種算法所要解決的問(wèn)題就是如何對多字節序列進(jìn)行除法取余式運算的問(wèn)題。3.1 多字節序列運算規律 首先設一個(gè)由i個(gè)字節 m1、m2、......、mi-1、mi 構成的8×i位二進(jìn)制序列，并用字節形式表示它為Mi ＝[ m1 m2 ...... mi-1 mi ]，然后再截取Mi的前（i-1）個(gè)字節構成一個(gè)Mi-1序列，Mi-1＝[ m1 m2 ...... mi-1 ]，這兩個(gè)序列之間的關(guān)系可以用多項式表示為Mi(x)＝x 8Mi-1(x)＋mi(x)，其中，mi(x)是字節mi的二進(jìn)制多項式表示形式，而x8Mi-1(x)表示將Mi-1序列左移一個(gè)字節。 對于序列Mi-1來(lái)說(shuō)，

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

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

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