CRC校驗(yàn)快速算法的原理及實(shí)現(xiàn)改進(jìn)設(shè)計(jì)

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

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

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

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

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

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

其中是字節(jié)的二進(jìn)制多項(xiàng)式表示形式，是將序列左移一個(gè)字節(jié)。

對(duì)于序列來說，有

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

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

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

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

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

2 任意長(zhǎng)度序列的CRC校驗(yàn)快速算法

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

設(shè)D為任意長(zhǎng)度的二進(jìn)制序列，記長(zhǎng)度為k位，則k總可以表示成的形式。其中s≥0，且0≤p＜8。這樣，就可以將序列D按降冪形式寫成 D（x）=xp［d1d2……ds-1ds］+m（x），dj（1≤j≤s）是位長(zhǎng)為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）為

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

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

因?yàn)?0≤p＜8

所以 16≤（16+p）＜24

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

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

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

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

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

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

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

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

圖1 算法流程圖

結(jié)語

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

責(zé)任編輯：gt