一種快速CRC算法的硬件實現(xiàn)方法

1、由于數(shù)據(jù)在傳輸和存儲時可能會由于干擾等原因發(fā)生變化,所以一般會采用數(shù)據(jù)校驗來確保數(shù)據(jù)的完整性。CRC(循環(huán)冗余碼)算法是把原始數(shù)據(jù)輸入到一個校驗公式中,生成一定長度的校驗碼,然后把校驗碼添加到原始數(shù)據(jù)的后面,組成新的數(shù)據(jù),對于串行輸入輸出的系統(tǒng),需要循環(huán)計算校驗碼,直到數(shù)據(jù)全部計算結(jié)束 校驗碼的作用是保證數(shù)據(jù)的可靠性,它本身并不是系統(tǒng)要求1傳輸?shù)臄?shù)據(jù),所以對于系統(tǒng)來說是冗余的。計算CRC、組成新數(shù)據(jù)的過程是編碼,用相同的方法把數(shù)據(jù)譯碼,就可以發(fā)現(xiàn)數(shù)據(jù)是否變化。CRC算法可以用軟件實現(xiàn),也可以用硬件實現(xiàn),但軟件計算的速度受限于系統(tǒng)CPU的速度,使用硬件方式來實現(xiàn)可以提高計算速度,從而提升系統(tǒng)的通

2、信效率。最普通的CRC硬件實現(xiàn)方法是串行計算方法,使用一位數(shù)據(jù)輸入,n位長度的原始數(shù)據(jù)連續(xù)計算n次后得出校驗碼,串行計算的電路結(jié)構(gòu)簡單,容易實現(xiàn),可以工作在較高的時鐘頻率下。但隨著通信速度的不斷提高,高的數(shù)據(jù)傳輸帶寬要求CRC的計算速度越來越快,串行計算的方法已經(jīng)不適應(yīng)要求,所以越來越多的使用并行計算方法 。本文先講述串行計算的實現(xiàn)方法,再在2此基礎(chǔ)上作一些改進,產(chǎn)生并行計算的電路結(jié)構(gòu)。1CRC算法在模運算中,模2 2乘法運算2除法只在除數(shù)為1 2多項式表示,多項式的系數(shù)就是序列的值。如101011可以表示為1x5,二進制序列最左邊的二進制位表示次數(shù)最高的多項式系數(shù) 。(x)就是CRC校驗碼,

3、多項式最高次數(shù)為k-1。編碼之后的數(shù)據(jù)為F(x)=xM(x)+R(x),因為模2k加減法運算的結(jié)果相同,所以F(x)=xM(x)-R(x)=Q(x)G(x),在譯碼的時候,對F(x)作模運算,k結(jié)果應(yīng)該為0。如果結(jié)果不為0,說明數(shù)據(jù)在編碼后已經(jīng)發(fā)生了變化。常用的CRC校驗公式 :2串行實現(xiàn)串行計算時,每次輸入一位數(shù)據(jù),輸入數(shù)據(jù)和上一次異或運算的結(jié)果組成新數(shù)據(jù),循環(huán)進行異串行實現(xiàn)的電路結(jié)構(gòu)如圖1所示 。5g的取值范圍是0或1,取0時,表示斷路,不需要異或運算,取1時,表示通路,需要異或運算,其中ig和g都為1。對于k位的CRC校驗,需要k個寄存器,當有新的數(shù)據(jù)輸入后,異或運算立刻得出0k新的CR

4、C,寄存器在時鐘沿移位,等待新的輸入數(shù)據(jù),反復(fù)循環(huán),就可以計算出CRC的值。串行的方法雖然可以計算各種CRC,但是一個時鐘周期只能計算一位數(shù)據(jù),效率比較低,只適用于低速的串行輸入輸出系統(tǒng),而當數(shù)據(jù)傳輸?shù)乃俣群芨?或者是多位數(shù)據(jù)并行傳輸時,需要引入并行計算的實現(xiàn)方法,并行的實現(xiàn)方法可以在一個時鐘內(nèi)對多位數(shù)據(jù)進行編碼,從而提高了CRC的計算速度。3并行實現(xiàn)并行CRC計算,可以在串行計算的基礎(chǔ)上改進電路結(jié)構(gòu)來實現(xiàn)。在串行實現(xiàn)中一個時鐘周期處理一位數(shù)據(jù),如果能夠把串行實現(xiàn)中多個時鐘周期處理的數(shù)據(jù)集中到一個時鐘周期內(nèi)處理,就達到并行處理的目的了。先分析一下串行實現(xiàn)中每一位CRC校驗碼的生成過程,CRC的

5、模2多項式為4CRC的長度為k,R是在計算j位原始數(shù)據(jù)后CRC的值所對應(yīng)的模2多項式,r 表示第i位的值,jr是R 第i-1位寄存后的值,g是校驗公式對應(yīng)的數(shù)據(jù)位(g、g為1),d是輸入的第j位原i-1、j-1始數(shù)據(jù)。j-1i0kj所以有這個函數(shù)關(guān)系式表示R 只和R 有關(guān),所以在電路實現(xiàn)時只計算R ,而不用計算2j+12j-12j2j+12j-1R R 。從R 到R 計算兩位數(shù)據(jù)的輸入,在串行實現(xiàn)中移位寄存兩次,需要兩2j2j+12j-12j+1個時鐘周期,現(xiàn)在一個周期就可以完成,說明串行實現(xiàn)可以轉(zhuǎn)化為兩位的并行實現(xiàn)。圖2和圖3比較了串行實現(xiàn)和并行實現(xiàn)結(jié)構(gòu)上的區(qū)別。具體到CRC每一位的值,在串

6、行實現(xiàn)中有上面的公式將串行的電路結(jié)構(gòu)轉(zhuǎn)換成了兩位輸入的并行電路結(jié)構(gòu),根據(jù)相應(yīng)的校驗公式,可理的位數(shù)為w,只需用相同的方法將r 推算到r 一級就可以了。i、ji、j-w對于算法CRC-16,如果計算的數(shù)據(jù)長度是100個字節(jié),時鐘頻率為1MHz,串行計算的時間為800s,而16位并行輸入的計算時間為50s。并行實現(xiàn)的計算速度是串行實現(xiàn)的w倍(w是并行數(shù)據(jù)輸入的寬度),所以當并行輸入的數(shù)據(jù)寬度比較大時,速度上的差異是非常明顯的。并行計算的缺點是使用了多級組合邏輯的反饋,將產(chǎn)生較大的門延遲,特別是在計算時鐘的頻率很高時,時鐘周期非常小,對時延的要求比較高,比如實現(xiàn)32位并行輸入的CRC-32,會產(chǎn)生31次異或操作,電路的門延時可能會很大,而超出系統(tǒng)的時延限度,這取決于組合電路的具體結(jié)構(gòu)。組合邏輯在綜合的時候,將產(chǎn)生圖4的電路結(jié)構(gòu) 。5圖4所示結(jié)構(gòu)的組合邏輯的延時是各個異或門的累加,異或次數(shù)多了以后,延時是很大的,所Z=(AB)(CD)(EF),電路的功能不變,但綜合出的電路結(jié)構(gòu)如圖5的延時分散到多個并行的分支上,將門延時從5級降低到3級。對于w位數(shù)據(jù)的異或操作,圖4的結(jié)構(gòu)將產(chǎn)生w級門延時,圖5的結(jié)構(gòu)將產(chǎn)生logw(表示取小數(shù)部分不等于0就加1)級12門延時,優(yōu)化后的結(jié)構(gòu)的延時以指數(shù)級減少。4結(jié)束語CRC現(xiàn)了CRC的并行計算。并行實現(xiàn)方式適