單片機CRC快速算法

1 引言

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

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

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

2　CRC原理

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

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

（1）

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

（2）

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

（3） 或表示為

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

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

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

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

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