基于WSN的CRC算法的改進與實現

李冠楠 李強

（順德職業技術學院 電子與信息工程系，廣東 順德 528300）

1.CRC算法介紹

CRC校驗采用多項式編碼方法。利用生成多項式為k個數據位產生r個校驗位進行編碼，其編碼長度為n=k+r，所以又稱為（n，k）碼。其編碼格式如下：

1.1 編碼規則[1]

設有k個數據位，需要添加r個校驗位，n=k+r，其編碼規則如下：

用W(x)=W W…W表示k個數據位，把W(x)左移r位，即相當于W(x)×2，給校驗位空出r位來；

給定一個r階的多項式E(x)，可以求出一個校驗位表達式F(x)。E(x)稱為該循環碼的生成多項式。即如下表達式：

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

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

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

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

1.2 生成多項式特點

生成多項式應滿足以下條件：

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

（2）余數繼續作模2除，應使余數循環；

（3）若要能糾正一位錯，則不同的碼位錯不能有相同的余數，且當給定生成多項式后，余數與出錯位之間的對應關系應保持不變，與編碼無關。

1.3 原算法實現[2]

/*以CRC-CCITT為例，按位計算CRC算法實現，不使用額外空間*/

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

2.CRC算法改進

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

CRC常用的生成多項式如 CRC-16、CRC-CCITT和CRC-32，由它們產生的校驗碼字節數均為整數個字節。而單片機的操作是以字節形式進行的，所以，算法應以字節為單位進行運算。顯然，單片機的數據序列、校驗序列都是字節序列。實際上，這種算法所要解決的問題就是如何對多字節序列進行除法取余式運算的問題，從而達到時空的權衡。

2.2 多字節序列運算規律

設一個由i個字節構成的字節序列Wi=[w1w2……wi-1wi]，取其前i-1個字節構成一個新的序列Wi-1=[w1w2……wi-2wi-1]，則兩個序列之間的關系可以用多項式表示為Wi(x)=x8Wi-1(x)+mi(x)。

其中，mi(x)表示mi的二進制多項式形式，x8Wi-1(x)表示將Wi-1左移一個字節。

對于序列Wi-1來說，

其中令二字節序列余數Ri-1=[hi-1li-1]

而對于序列Wi來說，可得

因此，對x8Ri-1（x）+wi(x)取余式運算就等價于對Wi(x)的取余式運算，即

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

2.3 變字節序列的計算

為了時空的權衡我們在此引入了查表的思想，對于三字節序列如果事先計算出一字節即0x00至0xFF之間的所有的余式并匯制成表，這樣就減少了時間開銷且只需占用512個字節空間。

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

對于序列Ta00來說，

而對于序列Tabc來說，可得

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

故三字節序列Tabc可分解為兩個步驟進行計算：

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

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

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

3.改進算法實現

在以上CRC原算法和改進算法的基礎上，本文采用C51編碼實現了CRC改進型數據校驗算法，并對各改進方案進行了效率分析。

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

圖1 三字節序列[abc]計算流程

4.算法效率分析

一個新算法的提出或改進是為了追求更高的效率，而對一個算法好壞的衡量除了最起碼的正確性、易理解性外，其占用的存儲空間和運算時間也是重要的標準。下面給出了以上三種計算CRC算法在相同條件、相同問題規模下的實驗數據。以下為相關說明：

（1）按位計算

—按位計算CRC算法（b_CRC）

— 執行時間（b_CRC_t）：-ms

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

（2）按字節計算

—按字節計算CRC算法（B_CRC）

— 執行時間（B_CRC_t）：-ms

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

（3）按半字節計算

—按半字節計算CRC算法（HB_CRC）

— 執行時間（HB_CRC_t）：-ms

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

表1列出了三種計算CRC算法的對比（對應圖2）。

表1 三種計算CRC算法對比表

圖2 CRC算法效率分析

通過對改進算法的編碼實現，并在大量調試、統計和比較的基礎上，我們可以得出以下結論：以上介紹的三種求CRC的程序，按位求法速度較慢，但占用最小的內存空間；按字節查表求CRC的方法速度較快，但占用較大的內存；按半字節查表求CRC的方法是前兩者的均衡，即不會占用太多的內存，同時速度又不至于太慢，比較適合8位小內存的單片機的應用場合。

可見，以上幾種算法從按位計算CRC的思想出發，并結合模2運算規則，在蠻力法的基礎上提出了按字節、半字節計算CRC的改進策略，也就是從減治和時空權衡的角度進行問題的詮釋，以一種空間換時間的思想實現了對原問題的快速、高效求解，從而滿足無線MESH網絡內節點的通信要求。

[1]王春森.程序員教程[M].北京：清華大學出版社,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校驗及其軟件實現[J].電子技術應用,1995(6)：67-71.