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

1 整字節序列的CRC校驗快速算法

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

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

截取Mi的前個字節構成一個序列，即

這兩個序列之間的關系可以表示為

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

對于序列來說，有

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

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

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

不失一般性，設三字節序列 ，那么

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

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

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

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

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

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

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

因為 0≤p＜8

所以 16≤（16+p）＜24

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

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

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

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

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

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

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

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

圖1 算法流程圖

結語

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

責任編輯：gt