32位CRC校驗(yàn)碼的并行算法及硬件實(shí)現(xiàn)

《32位CRC校驗(yàn)碼的并行算法及硬件實(shí)現(xiàn)》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、中圖分類(lèi)號(hào):TP331文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-2552(2007)04-0071-0432位CRC校驗(yàn)碼的并行算法及硬件實(shí)現(xiàn)俞迅(同濟(jì)大學(xué)電子與信息工程學(xué)院,上海200092)摘要:通過(guò)對(duì)CRC校驗(yàn)碼原理的分析,研究了一種并行32位CRC算法。該算法采用遞推的方法,直接得出計(jì)算多位數(shù)據(jù)后的CRC余數(shù)與計(jì)算前余數(shù)之間的邏輯關(guān)系。相對(duì)于一般的按位串行計(jì)算或者查表并行計(jì)算的方法來(lái)說(shuō),該方法運(yùn)算速度快且不需要額外的空間存儲(chǔ)余數(shù)表,十分有利于硬件實(shí)現(xiàn)。關(guān)鍵詞:CRC;模2運(yùn)算;并行CRC算法The32-bitcyclicredundancycheckparallelalgorithman

2、dhardwareimplementationYUXun(CollegeofElectronicandInformationEngineering,TongjiUniversity,Shanghai200092,China)Abstract:Basedonthetheoryofthecyclicredundancycheck,aparallelalgorithmisstudiedinthepaper.Thisalgorithmusesarecursivemethodtocalculatethelogicrelationshipofthechecksum.Differingfromgene

3、ralserialalgorithmortheparallelalgorithmbasedonlist-checking,itisfasteranddoesn’tneedtheex2tramemoryspacetostoretheremainderlist.Itisveryeasytobeimplementedbyhardware.Keywords:Cyclicredundancycheck;modulo2arithmetic;CRCparallelalgorithm計(jì)算機(jī)系統(tǒng)中的數(shù)據(jù),在進(jìn)行讀、寫(xiě)或者傳輸時(shí)出去。可能產(chǎn)生錯(cuò)誤,為了減少和避免錯(cuò)誤的產(chǎn)生,一方面首先,可將待編碼的k位數(shù)據(jù)表

4、示成多項(xiàng)式可以通過(guò)對(duì)特定電路的精心設(shè)計(jì),提高電路的穩(wěn)定M(X):k-1k-2性和可靠性;另一方面則是對(duì)數(shù)據(jù)采用某種編碼,通M(X)=Ck-1X+Ck-2X+?i過(guò)少量的附加電路,使之能發(fā)現(xiàn)某些錯(cuò)誤,甚至能確+CiX+?+C1X+C0定出錯(cuò)位置,進(jìn)而實(shí)現(xiàn)自動(dòng)改錯(cuò)的功能。CRC(循環(huán)其中Ci為0或者1。冗余碼)就是一種常用的錯(cuò)誤檢測(cè)碼,它可以發(fā)現(xiàn)并對(duì)于r位CRC來(lái)說(shuō),校驗(yàn)碼產(chǎn)生的過(guò)程為:糾正數(shù)據(jù)存儲(chǔ)或傳輸過(guò)程中連續(xù)出現(xiàn)的多位錯(cuò)誤,將M(X)左移r位,然后除以一個(gè)被稱(chēng)為生成因此在介質(zhì)存儲(chǔ)和網(wǎng)絡(luò)通信方面得到了廣泛的應(yīng)多項(xiàng)式的G(X),所得余數(shù)就是CRC校驗(yàn)碼。這里,用。隨著技術(shù)的發(fā)展,數(shù)據(jù)存儲(chǔ)和

5、傳輸速度大大提生成多項(xiàng)式G(X)是一個(gè)r+1位的多項(xiàng)式。高,在一些高速的場(chǎng)合如usb2.0或者快速以太網(wǎng)用公式表示如下:r中,傳統(tǒng)的串行CRC算法已不能滿(mǎn)足速度上的要M(X)·xR(X)=Q(X)+求,而必須采用速度更快的并行算法。G(X)G(X)其中Q(X)為商,在CRC的計(jì)算過(guò)程中不需要關(guān)注,1CRC校驗(yàn)碼原理簡(jiǎn)介R(X)為余數(shù),就是需要的CRC碼。CRC的計(jì)算使CRC校驗(yàn)的基本思路是利用線(xiàn)性碼原理,對(duì)需要進(jìn)行傳輸?shù)脑糼位二進(jìn)制數(shù)據(jù)按照一定的規(guī)則收稿日期:2006-11-20處理,產(chǎn)生一個(gè)r位的校驗(yàn)碼并附加在原始數(shù)據(jù)后作者簡(jiǎn)介:俞迅(1982-),男,同濟(jì)大學(xué)微電子與固體電子學(xué)在讀

6、碩面,形成一個(gè)k+r位的二進(jìn)制數(shù)據(jù),最后一起發(fā)送士研究生,研究方向?yàn)榧呻娐非岸嗽O(shè)計(jì)及仿真。—71—用的是模2運(yùn)算,即不帶進(jìn)位和借位的按位加減,這轉(zhuǎn)換成二進(jìn)制序列就是在邏輯上等同于異或運(yùn)算。1000001001100000100011101101101112串行32位CRC算法為了便于表達(dá),記為:設(shè)cj31+cj30+?+cjj32(dk-1+g32,g31,?,g2,g1,g0(2)31x30x1x+c0=xk-1xdk-2其中,gi對(duì)應(yīng)于生成多項(xiàng)式的系數(shù),取0或者1。k-2x+?+d0)modG(x)j為計(jì)算前的CRC多項(xiàng)式,gi為生成多項(xiàng)式G(x)定義ci為計(jì)算了第j位數(shù)據(jù)后所得C

7、RC值的第的第i位系數(shù)。i位,d3,d2,d1,d0為讀入的數(shù)據(jù)順序,最初時(shí)的000000則新讀入一位數(shù)據(jù)d′后,CRC值為:c31,c30,c29,?,c2,c1,c0?；舅枷刖褪?2k-1k-2ix(dk-1x+dk-2x+?+dix+d0x+連續(xù)套用式(1)給出的串行公式4次,以期得出處理4033k-1k-2i4位數(shù)據(jù)后cd′)modG(x)=x(dk-1x+dk-2x+?+dix+i與ci和d3,d2,d1,d0之間的邏輯