基于WSN的CRC算法的改進(jìn)與實(shí)現(xiàn)

李冠楠 李強(qiáng)

（順德職業(yè)技術(shù)學(xué)院 電子與信息工程系，廣東 順德 528300）

1.CRC算法介紹

CRC校驗(yàn)采用多項(xiàng)式編碼方法。利用生成多項(xiàng)式為k個(gè)數(shù)據(jù)位產(chǎn)生r個(gè)校驗(yàn)位進(jìn)行編碼，其編碼長(zhǎng)度為n=k+r，所以又稱為（n，k）碼。其編碼格式如下：

1.1 編碼規(guī)則[1]

設(shè)有k個(gè)數(shù)據(jù)位，需要添加r個(gè)校驗(yàn)位，n=k+r，其編碼規(guī)則如下：

用W(x)=W W…W表示k個(gè)數(shù)據(jù)位，把W(x)左移r位，即相當(dāng)于W(x)×2，給校驗(yàn)位空出r位來；

給定一個(gè)r階的多項(xiàng)式E(x)，可以求出一個(gè)校驗(yàn)位表達(dá)式F(x)。E(x)稱為該循環(huán)碼的生成多項(xiàng)式。即如下表達(dá)式：

根據(jù)上面公式可知，用W(x)去除生成多項(xiàng)式G(x)，商為H(x)，余數(shù)則為R(x)。據(jù)此可得：

在CRC編碼過程中，四則運(yùn)算采用模2運(yùn)算，即不考慮借位和進(jìn)位。所以有：

M(x)+R(x)即為所求n位CRC碼，它應(yīng)是生成多項(xiàng)式G(x)的倍式，即可以被G(x)整除。

校驗(yàn)數(shù)據(jù)時(shí)用數(shù)據(jù)的n位CRC編碼去除G(x)，若余數(shù)為0則說明數(shù)據(jù)正確，否則根據(jù)余數(shù)的值即可查出差錯(cuò)位。

1.2 生成多項(xiàng)式特點(diǎn)

生成多項(xiàng)式應(yīng)滿足以下條件：

（1）任何一位發(fā)生錯(cuò)誤，W(x)×2+R(x)即CRC碼除以G(x)的余數(shù)不能為0；

（2）余數(shù)繼續(xù)作模2除，應(yīng)使余數(shù)循環(huán)；

（3）若要能糾正一位錯(cuò)，則不同的碼位錯(cuò)不能有相同的余數(shù)，且當(dāng)給定生成多項(xiàng)式后，余數(shù)與出錯(cuò)位之間的對(duì)應(yīng)關(guān)系應(yīng)保持不變，與編碼無關(guān)。

1.3 原算法實(shí)現(xiàn)[2]

/*以CRC-CCITT為例，按位計(jì)算CRC算法實(shí)現(xiàn)，不使用額外空間*/

從上述代碼可知，直接基于問題的描述和所涉及的概念出發(fā)，利用按位計(jì)算CRC，雖然代碼簡(jiǎn)單（也可采用模擬硬件電路按位操作加以實(shí)現(xiàn)），所占用的內(nèi)存比較少，但其最大的缺點(diǎn)就是一位一位地計(jì)算會(huì)占用很多的處理器處理時(shí)間，尤其在高速通訊的場(chǎng)合，這個(gè)缺點(diǎn)更是不可容忍，因而實(shí)現(xiàn)對(duì)它的改進(jìn)具有理論和實(shí)際的意義。

2.CRC算法改進(jìn)

2.1 快速算法基本思想[3]

CRC常用的生成多項(xiàng)式如 CRC-16、CRC-CCITT和CRC-32，由它們產(chǎn)生的校驗(yàn)碼字節(jié)數(shù)均為整數(shù)個(gè)字節(jié)。而單片機(jī)的操作是以字節(jié)形式進(jìn)行的，所以，算法應(yīng)以字節(jié)為單位進(jìn)行運(yùn)算。顯然，單片機(jī)的數(shù)據(jù)序列、校驗(yàn)序列都是字節(jié)序列。實(shí)際上，這種算法所要解決的問題就是如何對(duì)多字節(jié)序列進(jìn)行除法取余式運(yùn)算的問題，從而達(dá)到時(shí)空的權(quán)衡。

2.2 多字節(jié)序列運(yùn)算規(guī)律

設(shè)一個(gè)由i個(gè)字節(jié)構(gòu)成的字節(jié)序列Wi=[w1w2……wi-1wi]，取其前i-1個(gè)字節(jié)構(gòu)成一個(gè)新的序列Wi-1=[w1w2……wi-2wi-1]，則兩個(gè)序列之間的關(guān)系可以用多項(xiàng)式表示為Wi(x)=x8Wi-1(x)+mi(x)。

其中，mi(x)表示mi的二進(jìn)制多項(xiàng)式形式，x8Wi-1(x)表示將Wi-1左移一個(gè)字節(jié)。

對(duì)于序列Wi-1來說，

其中令二字節(jié)序列余數(shù)Ri-1=[hi-1li-1]

而對(duì)于序列Wi來說，可得

因此，對(duì)x8Ri-1（x）+wi(x)取余式運(yùn)算就等價(jià)于對(duì)Wi(x)的取余式運(yùn)算，即

其中，x8Ri-1（x）+wi(x)表示一個(gè)由Ri-1和mi共同組成的三字節(jié)序列[hi-1li-1wi]，故對(duì)它取余式運(yùn)算就等于對(duì)Mi序列的取余式運(yùn)算，其結(jié)果就是Mi序列的余式Ri=[hili]。故以此類推便可得到最終結(jié)果。

2.3 變字節(jié)序列的計(jì)算

為了時(shí)空的權(quán)衡我們?cè)诖艘肓瞬楸淼乃枷耄瑢?duì)于三字節(jié)序列如果事先計(jì)算出一字節(jié)即0x00至0xFF之間的所有的余式并匯制成表，這樣就減少了時(shí)間開銷且只需占用512個(gè)字節(jié)空間。

設(shè)三字節(jié)序列Tabc=[abc]、Ta00=[a00]和二字節(jié)序列Tbc=[bc]。用多項(xiàng)式表示為Tabc(x)=Ta00(x)+Tbc(x)。

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

而對(duì)于序列Tabc來說，可得

其中，Ra00和Tbc都是二字節(jié)序列，因此Ra00(x)+Tbc（x）仍然是二字節(jié)序列，它是Tabc的余數(shù)Rabc，即

故三字節(jié)序列Tabc可分解為兩個(gè)步驟進(jìn)行計(jì)算：

通過查表，獲取Ta00=[a00]的余式Ra00=[ha00la00]

計(jì)算 Rabc=[habclabc]，其中 habc=ha00⊕b，labc=la00⊕c

很顯然，對(duì)于三字節(jié)序列只需建立一字節(jié)即0x00到0xFF的余式表，即按字節(jié)求CRC的思想，由于采用了查表法，大大提高了計(jì)算速度。但對(duì)于廣泛運(yùn)用的8位微處理器，代碼空間有限，對(duì)于要求256個(gè)CRC余式表（共512字節(jié)的內(nèi)存）已經(jīng)顯得捉襟見肘了，但CRC的計(jì)算速度又不可以太慢，故同理我們可以引入按半字節(jié)計(jì)算CRC的算法。

3.改進(jìn)算法實(shí)現(xiàn)

在以上CRC原算法和改進(jìn)算法的基礎(chǔ)上，本文采用C51編碼實(shí)現(xiàn)了CRC改進(jìn)型數(shù)據(jù)校驗(yàn)算法，并對(duì)各改進(jìn)方案進(jìn)行了效率分析。

經(jīng)過上述分析，無論是按字節(jié)還是半字節(jié)來計(jì)算CRC都采用了一種遞推的思想。一種由小及大，利用一個(gè)問題給定實(shí)例的解和同樣問題較小實(shí)例的解之間的關(guān)系建立起原問題的解。這一算法是基于遞推運(yùn)算的規(guī)律，并且每一次遞推運(yùn)算都是對(duì)一個(gè)三字節(jié)序列的計(jì)算（如圖1所示）。

圖1 三字節(jié)序列[abc]計(jì)算流程

4.算法效率分析

一個(gè)新算法的提出或改進(jìn)是為了追求更高的效率，而對(duì)一個(gè)算法好壞的衡量除了最起碼的正確性、易理解性外，其占用的存儲(chǔ)空間和運(yùn)算時(shí)間也是重要的標(biāo)準(zhǔn)。下面給出了以上三種計(jì)算CRC算法在相同條件、相同問題規(guī)模下的實(shí)驗(yàn)數(shù)據(jù)。以下為相關(guān)說明：

（1）按位計(jì)算

—按位計(jì)算CRC算法（b_CRC）

— 執(zhí)行時(shí)間（b_CRC_t）：-ms

—額外空間：0Byte（恒定）

（2）按字節(jié)計(jì)算

—按字節(jié)計(jì)算CRC算法（B_CRC）

— 執(zhí)行時(shí)間（B_CRC_t）：-ms

—額外空間：512Byte（恒定）

（3）按半字節(jié)計(jì)算

—按半字節(jié)計(jì)算CRC算法（HB_CRC）

— 執(zhí)行時(shí)間（HB_CRC_t）：-ms

—額外空間：32Byte（恒定）

表1列出了三種計(jì)算CRC算法的對(duì)比（對(duì)應(yīng)圖2）。

表1 三種計(jì)算CRC算法對(duì)比表

圖2 CRC算法效率分析

通過對(duì)改進(jìn)算法的編碼實(shí)現(xiàn)，并在大量調(diào)試、統(tǒng)計(jì)和比較的基礎(chǔ)上，我們可以得出以下結(jié)論：以上介紹的三種求CRC的程序，按位求法速度較慢，但占用最小的內(nèi)存空間；按字節(jié)查表求CRC的方法速度較快，但占用較大的內(nèi)存；按半字節(jié)查表求CRC的方法是前兩者的均衡，即不會(huì)占用太多的內(nèi)存，同時(shí)速度又不至于太慢，比較適合8位小內(nèi)存的單片機(jī)的應(yīng)用場(chǎng)合。

可見，以上幾種算法從按位計(jì)算CRC的思想出發(fā)，并結(jié)合模2運(yùn)算規(guī)則，在蠻力法的基礎(chǔ)上提出了按字節(jié)、半字節(jié)計(jì)算CRC的改進(jìn)策略，也就是從減治和時(shí)空權(quán)衡的角度進(jìn)行問題的詮釋，以一種空間換時(shí)間的思想實(shí)現(xiàn)了對(duì)原問題的快速、高效求解，從而滿足無線MESH網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)的通信要求。

[1]王春森.程序員教程[M].北京：清華大學(xué)出版社,2002：75-93.

[2]W.Ye,J.Heidemann,D.Estrin.An energy-efficient MAC protocol for wireless sensor networks[J].The 21st Int'l Annual Joint Conf.on the IEEE Computer and Communications Societies(INFOCOM 2002).New York,USA,2002：1-10.

[3]常曉明.CRC校驗(yàn)及其軟件實(shí)現(xiàn)[J].電子技術(shù)應(yīng)用,1995(6)：67-71.