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

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

1、中圖分類號:TP331文獻(xiàn)標(biāo)識碼:A文章編號:1009-2552(2007)04-0071-0432位CRC校驗(yàn)碼的并行算法及硬件實(shí)現(xiàn)俞迅(同濟(jì)大學(xué)電子與信息工程學(xué)院,上海200092)摘要:通過對CRC校驗(yàn)碼原理的分析,研究了一種并行32位CRC算法。該算法采用遞推的方法,直接得出計算多位數(shù)據(jù)后的CRC余數(shù)與計算前余數(shù)之間的邏輯關(guān)系。相對于一般的按位串行計算或者查表并行計算的方法來說,該方法運(yùn)算速度快且不需要額外的空間存儲余數(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ī)系統(tǒng)中的數(shù)據(jù),在進(jìn)行讀、寫或者傳輸時出去?？赡墚a(chǎn)生錯誤,為了減少和避免錯誤的產(chǎn)生,一方面首先,可將待編碼的k位數(shù)據(jù)表

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

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

6、碩面,形成一個k+r位的二進(jìn)制數(shù)據(jù),最后一起發(fā)送士研究生,研究方向?yàn)榧呻娐非岸嗽O(shè)計及仿真?！?1—用的是模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對應(yīng)于生成多項(xiàng)式的系數(shù),取0或者1。k-2x+?+d0)modG(x)j為計算前的CRC多項(xiàng)式,gi為生成多項(xiàng)式G(x)定義ci為計算了第j位數(shù)據(jù)后所得C

7、RC值的第的第i位系數(shù)。i位,d3,d2,d1,d0為讀入的數(shù)據(jù)順序,最初時的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之間的邏輯