CRC（循環(huán)冗余校驗碼）編碼是數(shù)字信號傳輸中用得較普遍的一種差錯控制編碼。它不但可以用于糾正獨立的隨機錯誤，也可以用于糾正突發(fā)錯誤。CRC校驗通常是靠專用硬件電路來實現(xiàn)的，但很多系統(tǒng)為了降低成本，常常利用單片機或微處理器編程來完成這一功能。因此，在器件處理能力有限的情況下，如何提高CRC 校驗軟件計算的速度，是開發(fā)者最為關(guān)心的問題。

1 整字節(jié)序列的CRC校驗快速算法

文獻［1］提出了一種針對整字節(jié)的CRC快速算法。它的基本思想是預(yù)先生成一個余式表，通過查表，利用遞推原理進行快速計算?，F(xiàn)以 CCITT（國際電話電報咨詢委員會）建議的，用于基本型數(shù)據(jù)傳輸規(guī)程的生成多項式為例，簡要介紹此先驗算法的基本原理。

設(shè)M為由i個字節(jié)組成的8×i位二進制序列，用字節(jié)形式表示為

截取Mi的前個字節(jié)構(gòu)成一個序列，即

這兩個序列之間的關(guān)系可以表示為

其中是字節(jié)的二進制多項式表示形式，是將序列左移一個字節(jié)。

對于序列來說，有

其中，是商多項式，為一整數(shù)項;為最高次冪小于15的余數(shù)項。而對于Mi序列，

其中為整數(shù)項，因此對多項式取余即等效于對多項式取余，記做

這樣就形成了遞推關(guān)系。對于序列，已知就可知，已知就可知，最后就變成了求三字節(jié)序列的余式項的問題。

不失一般性，設(shè)三字節(jié)序列 ，那么

我們可以預(yù)先做好一個16×16的［a00］形式的余式表，通過查余式表可以很快知道，而是小于等于16位的二字節(jié)序列，除以的余式即為本身。（4）式中的加法運算為模2加（異或運算）。運用此算法就可很快求出整字節(jié)的CRC校驗碼。

2 任意長度序列的CRC校驗快速算法

上述算法，只適用于信息長度為整字節(jié)的情形;但在實際應(yīng)用中，往往會遇到計算非整字節(jié)的CRC校驗碼。一種解決方法是，在信息數(shù)據(jù)前補零，即將信息數(shù)據(jù)右移，使之成為整字節(jié)來計算，這對于信息數(shù)據(jù)序列不長的情況還是奏效的;但遇到長數(shù)據(jù)序列，若對每一個字節(jié)均進行移位操作，則計算量明顯增加，這一缺點對于實時性要求高的系統(tǒng)來說尤其明顯。下面以生成多項式為例，提出一種改進算法，可實現(xiàn)任意長度序列快速CRC校驗運算。

設(shè)D為任意長度的二進制序列，記長度為k位，則k總可以表示成的形式。其中s≥0，且0≤p＜8。這樣，就可以將序列D按降冪形式寫成 D（x）=xp［d1d2……ds-1ds］+m（x），dj（1≤j≤s）是位長為8的字節(jié)，m為序列D除掉整字節(jié)后余下的位，為非整字節(jié)。記序列 M（x）=［d1d2……ds-1ds］，那么

M（x）為整字節(jié)序列，其余式RM（x）可用前面介紹的整字節(jié)CRC算法求出。因為生成多項式G（x）=x16+x12+x5+1的最高次冪為 16，所以序列D（x）的余式RD（x）為

其中 ，即形成兩個余式的模2加（異或運算），m（x）的長度小于1字節(jié)，所以RM（x）是［a00］形式的余式，通過查余式表可以很快得到。

現(xiàn)在來討論xpRM（x）的計算。RM（x）可以按照上述整字節(jié)的快速算法算出結(jié)果。因為RM（x）的位長為16，xpRM（x）相當于 RM（x）向左移p位，位長為（16+p）。

因為 0≤p＜8

所以 16≤（16+p）＜24

xpRM（x）可以看成一個3字節(jié)序列，定義

其中是2字節(jié)序列，長16位，小于生成多項式17位。它們除以生成多項式的余式即為本身，所以

是為樣式的余式，可以由余式表直接獲得，所以（1）式又可寫為

這就是改進后的非整字節(jié)CRC校驗快速算法。它不需要進行大量的數(shù)據(jù)移位對齊，比起整字節(jié)的算法，只增加了兩次查表和兩次異或運算，可見其運算量并沒有顯著增加。

值得提出的是，在文獻［1］提出的整字節(jié)CRC校驗快速算法中，推導(dǎo)遞推公式（3）時，作者并沒有考慮到序列用于計算CRC校驗碼時要先移16 位（生成多項式為時）。若讀者按照此法，直接用序列來做運算，顯然是不對的，必將導(dǎo)致錯誤結(jié)果。

3 適用于單片機或微處理器的算法流程

為了編程方便，我們將需處理的信息序列做以下變形。重寫（4）式，在整字節(jié)部分的M（x）后補2字節(jié)的“0”，得到新數(shù)列

其中，用取代M（x）做編程計算，算法流程如圖1所示。

圖1 算法流程圖

結(jié)語

任意長度非整字節(jié)的CRC快速算法適用的范圍很廣，只需預(yù)先在內(nèi)存中生成一個余式表，通過查余式表就可以快速計算。由于算法的每一步遞推都是以字節(jié)為單位的，這樣就比傳統(tǒng)的以位為單位的算法要快上十幾倍。數(shù)據(jù)序列的長度越長，其體現(xiàn)的優(yōu)越性就越高。而且算法不要求用于計算的序列為整字節(jié)，任意位長均適用，在實際應(yīng)用中效果顯著。

責任編輯：gt