|
CRC（循環(huán)冗余校驗(yàn)碼）編碼是數(shù)字信號傳輸中用得較普遍的一種差錯控制編碼。它不但可以用于糾正獨(dú)立的隨機(jī)錯誤,也可以用于糾正突發(fā)錯誤。CRC校驗(yàn)通常是靠專用硬件電路來實(shí)現(xiàn)的,但很多系統(tǒng)為了降低成本,常常利用單片機(jī)或微處理器編程來完成這一功能。因此,在器件處理能力有限的情況下,如何提高CRC 校驗(yàn)軟件計(jì)算的速度,是開發(fā)者最為關(guān)心的問題。 1 整字節(jié)序列的CRC校驗(yàn)快速算法 文獻(xiàn)[1]提出了一種針對整字節(jié)的CRC快速算法。它的基本思想是預(yù)先生成一個余式表,通過查表,利用遞推原理進(jìn)行快速計(jì)算。現(xiàn)以 CCITT（國際電話電報(bào)咨詢委員會）建議的,用于基本型數(shù)據(jù)傳輸規(guī)程的生成多項(xiàng)式為例,簡要介紹此先驗(yàn)算法的基本原理。 設(shè)M為由i個字節(jié)組成的8×i位二進(jìn)制序列,用字節(jié)形式表示為 
截取Mi的前個字節(jié)構(gòu)成一個序列,即
這兩個序列之間的關(guān)系可以表示為
其中是字節(jié)的二進(jìn)制多項(xiàng)式表示形式,是將序列左移一個字節(jié)。 對于序列來說,有
其中,是商多項(xiàng)式,為一整數(shù)項(xiàng);為最高次冪小于15的余數(shù)項(xiàng)。而對于Mi序列,
其中為整數(shù)項(xiàng),因此對多項(xiàng)式取余即等效于對多項(xiàng)式取余,記做
這樣就形成了遞推關(guān)系。對于序列,已知就可知,已知就可知,最后就變成了求三字節(jié)序列的余式項(xiàng)的問題。 不失一般性,設(shè)三字節(jié)序列 ,那么
我們可以預(yù)先做好一個16×16的[a00]形式的余式表,通過查余式表可以很快知道,而是小于等于16位的二字節(jié)序列,除以的余式即為本身。(4)式中的加法運(yùn)算為模2加（異或運(yùn)算）。運(yùn)用此算法就可很快求出整字節(jié)的CRC校驗(yàn)碼。 2 任意長度序列的CRC校驗(yàn)快速算法 上述算法,只適用于信息長度為整字節(jié)的情形;但在實(shí)際應(yīng)用中,往往會遇到計(jì)算非整字節(jié)的CRC校驗(yàn)碼。一種解決方法是,在信息數(shù)據(jù)前補(bǔ)零,即將信息數(shù)據(jù)右移,使之成為整字節(jié)來計(jì)算,這對于信息數(shù)據(jù)序列不長的情況還是奏效的;但遇到長數(shù)據(jù)序列,若對每一個字節(jié)均進(jìn)行移位操作,則計(jì)算量明顯增加,這一缺點(diǎn)對于實(shí)時性要求高的系統(tǒng)來說尤其明顯。下面以生成多項(xiàng)式為例,提出一種改進(jìn)算法,可實(shí)現(xiàn)任意長度序列快速CRC校驗(yàn)運(yùn)算。 設(shè)D為任意長度的二進(jìn)制序列,記長度為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算法求出。因?yàn)樯啥囗?xiàng)式G(x)=x16+x12+x5+1的最高次冪為 16,所以序列D(x)的余式RD(x)為
其中
現(xiàn)在來討論xpRM(x)的計(jì)算。RM(x)可以按照上述整字節(jié)的快速算法算出結(jié)果。因?yàn)镽M(x)的位長為16,xpRM(x)相當(dāng)于 RM(x)向左移p位,位長為(16+p)。 因?yàn)?0≤p＜8 所以 16≤(16+p)＜24 xpRM(x)可以看成一個3字節(jié)序列,定義
其中是2字節(jié)序列,長16位,小于生成多項(xiàng)式17位。它們除以生成多項(xiàng)式的余式即為本身,所以
是為樣式的余式,可以由余式表直接獲得,所以(1)式又可寫為
這就是改進(jìn)后的非整字節(jié)CRC校驗(yàn)快速算法。它不需要進(jìn)行大量的數(shù)據(jù)移位對齊,比起整字節(jié)的算法,只增加了兩次查表和兩次異或運(yùn)算,可見其運(yùn)算量并沒有顯著增加。 值得提出的是,在文獻(xiàn)[1]提出的整字節(jié)CRC校驗(yàn)快速算法中,推導(dǎo)遞推公式(3)時,作者并沒有考慮到序列用于計(jì)算CRC校驗(yàn)碼時要先移16 位（生成多項(xiàng)式為時）。若讀者按照此法,直接用序列來做運(yùn)算,顯然是不對的,必將導(dǎo)致錯誤結(jié)果。 3 適用于單片機(jī)或微處理器的算法流程 為了編程方便,我們將需處理的信息序列做以下變形。重寫(4)式,在整字節(jié)部分的M(x)后補(bǔ)2字節(jié)的“0”,得到新數(shù)列
其中,用取代M(x)做編程計(jì)算,算法流程如圖1所示。
圖1 算法流程圖 結(jié)語 任意長度非整字節(jié)的CRC快速算法適用的范圍很廣,只需預(yù)先在內(nèi)存中生成一個余式表,通過查余式表就可以快速計(jì)算。由于算法的每一步遞推都是以字節(jié)為單位的,這樣就比傳統(tǒng)的以位為單位的算法要快上十幾倍。數(shù)據(jù)序列的長度越長,其體現(xiàn)的優(yōu)越性就越高。而且算法不要求用于計(jì)算的序列為整字節(jié),任意位長均適用,在實(shí)際應(yīng)用中效果顯著。 參考文獻(xiàn) 1. 韓炬 簡單適用的單片機(jī)快速算法 2000(2) 2. 王新梅 糾錯碼--原理與方法 2001 3. 常曉明.潘衛(wèi)華.王建東 CRC 校驗(yàn)及其軟件實(shí)現(xiàn) 1995(6) 作 者：國防科技大學(xué) 劉小匯 王飛雪 來 源：單片機(jī)與嵌入式系統(tǒng)應(yīng)用 2003（10） |
