李冠楠 李強(qiáng)
(順德職業(yè)技術(shù)學(xué)院 電子與信息工程系,廣東 順德 528300)
CRC校驗(yàn)采用多項(xiàng)式編碼方法。利用生成多項(xiàng)式為k個(gè)數(shù)據(jù)位產(chǎn)生r個(gè)校驗(yàn)位進(jìn)行編碼,其編碼長(zhǎng)度為n=k+r,所以又稱(chēng)為(n,k)碼。其編碼格式如下:
設(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位來(lái);
給定一個(gè)r階的多項(xiàng)式E(x),可以求出一個(gè)校驗(yàn)位表達(dá)式F(x)。E(x)稱(chēng)為該循環(huán)碼的生成多項(xiàng)式。即如下表達(dá)式:
根據(jù)上面公式可知,用W(x)去除生成多項(xiàng)式G(x),商為H(x),余數(shù)則為R(x)。據(jù)此可得:
在CRC編碼過(guò)程中,四則運(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則說(shuō)明數(shù)據(jù)正確,否則根據(jù)余數(shù)的值即可查出差錯(cuò)位。
生成多項(xiàng)式應(yīng)滿(mǎn)足以下條件:
(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)保持不變,與編碼無(wú)關(guān)。
/*以CRC-CCITT為例,按位計(jì)算CRC算法實(shí)現(xiàn),不使用額外空間*/
從上述代碼可知,直接基于問(wè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í)際的意義。
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í)際上,這種算法所要解決的問(wèn)題就是如何對(duì)多字節(jié)序列進(jìn)行除法取余式運(yùn)算的問(wèn)題,從而達(dá)到時(shí)空的權(quán)衡。
設(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來(lái)說(shuō),
其中令二字節(jié)序列余數(shù)Ri-1=[hi-1li-1]
而對(duì)于序列Wi來(lái)說(shuō),可得
因此,對(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]。故以此類(lèi)推便可得到最終結(jié)果。
為了時(shí)空的權(quán)衡我們?cè)诖艘肓瞬楸淼乃枷?,?duì)于三字節(jié)序列如果事先計(jì)算出一字節(jié)即0x00至0xFF之間的所有的余式并匯制成表,這樣就減少了時(shí)間開(kāi)銷(xiāo)且只需占用512個(gè)字節(jié)空間。
設(shè)三字節(jié)序列Tabc=[abc]、Ta00=[a00]和二字節(jié)序列Tbc=[bc]。用多項(xiàng)式表示為T(mén)abc(x)=Ta00(x)+Tbc(x)。
對(duì)于序列Ta00來(lái)說(shuō),
而對(duì)于序列Tabc來(lái)說(shuō),可得
其中,Ra00和Tbc都是二字節(jié)序列,因此Ra00(x)+Tbc(x)仍然是二字節(jié)序列,它是Tabc的余數(shù)Rabc,即
故三字節(jié)序列Tabc可分解為兩個(gè)步驟進(jìn)行計(jì)算:
通過(guò)查表,獲取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)顯得捉襟見(jiàn)肘了,但CRC的計(jì)算速度又不可以太慢,故同理我們可以引入按半字節(jié)計(jì)算CRC的算法。
在以上CRC原算法和改進(jìn)算法的基礎(chǔ)上,本文采用C51編碼實(shí)現(xiàn)了CRC改進(jìn)型數(shù)據(jù)校驗(yàn)算法,并對(duì)各改進(jìn)方案進(jìn)行了效率分析。
經(jīng)過(guò)上述分析,無(wú)論是按字節(jié)還是半字節(jié)來(lái)計(jì)算CRC都采用了一種遞推的思想。一種由小及大,利用一個(gè)問(wèn)題給定實(shí)例的解和同樣問(wèn)題較小實(shí)例的解之間的關(guān)系建立起原問(wèn)題的解。這一算法是基于遞推運(yùn)算的規(guī)律,并且每一次遞推運(yùn)算都是對(duì)一個(gè)三字節(jié)序列的計(jì)算(如圖1所示)。
圖1 三字節(jié)序列[abc]計(jì)算流程
一個(gè)新算法的提出或改進(jìn)是為了追求更高的效率,而對(duì)一個(gè)算法好壞的衡量除了最起碼的正確性、易理解性外,其占用的存儲(chǔ)空間和運(yùn)算時(shí)間也是重要的標(biāo)準(zhǔn)。下面給出了以上三種計(jì)算CRC算法在相同條件、相同問(wèn)題規(guī)模下的實(shí)驗(yàn)數(shù)據(jù)。以下為相關(guān)說(shuō)明:
(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算法效率分析
通過(guò)對(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)合。
可見(jiàn),以上幾種算法從按位計(jì)算CRC的思想出發(fā),并結(jié)合模2運(yùn)算規(guī)則,在蠻力法的基礎(chǔ)上提出了按字節(jié)、半字節(jié)計(jì)算CRC的改進(jìn)策略,也就是從減治和時(shí)空權(quán)衡的角度進(jìn)行問(wèn)題的詮釋?zhuān)砸环N空間換時(shí)間的思想實(shí)現(xiàn)了對(duì)原問(wèn)題的快速、高效求解,從而滿(mǎn)足無(wú)線(xiàn)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.