|
CRC（循環冗余校驗碼）編碼是數字信號傳輸中用得較普遍的一種差錯控制編碼。它不但可以用于糾正獨立的隨機錯誤,也可以用于糾正突發錯誤。CRC校驗通常是靠專用硬件電路來實現的,但很多系統為了降低成本,常常利用單片機或微處理器編程來完成這一功能。因此,在器件處理能力有限的情況下,如何提高CRC 校驗軟件計算的速度,是開發者最為關心的問題。 1 整字節序列的CRC校驗快速算法 文獻[1]提出了一種針對整字節的CRC快速算法。它的基本思想是預先生成一個余式表,通過查表,利用遞推原理進行快速計算�，F以 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)為
其中
現在來討論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快速算法適用的范圍很廣,只需預先在內存中生成一個余式表,通過查余式表就可以快速計算。由于算法的每一步遞推都是以字節為單位的,這樣就比傳統的以位為單位的算法要快上十幾倍。數據序列的長度越長,其體現的優越性就越高。而且算法不要求用于計算的序列為整字節,任意位長均適用,在實際應用中效果顯著。 參考文獻 1. 韓炬 簡單適用的單片機快速算法 2000(2) 2. 王新梅 糾錯碼--原理與方法 2001 3. 常曉明.潘衛華.王建東 CRC 校驗及其軟件實現 1995(6) 作 者：國防科技大學 劉小匯 王飛雪 來 源：單片機與嵌入式系統應用 2003（10） |
