并行CRC在FPGA上的實現(xiàn)

莫元勁，黃水永

（廣州數(shù)控設(shè)備有限公司 廣東 廣州 510165）

循環(huán)冗余碼校驗CRC廣泛用于通訊領(lǐng)域和數(shù)據(jù)存儲的數(shù)據(jù)檢錯。很多時候，人們往往選擇C語言來實現(xiàn)CRC對數(shù)據(jù)的校驗檢錯，實現(xiàn)起來也比較簡單，但是其流水線處理方法大大限制了對數(shù)據(jù)流處理的速度。隨著FPGA的大量普及，并行處理數(shù)據(jù)有著傳統(tǒng)流水線無可比擬的巨大優(yōu)勢。使用超前位并行計算方法計算CRC，對通訊領(lǐng)域和數(shù)據(jù)存儲的快速數(shù)據(jù)處理有著重要的意義，筆者根據(jù)超前位計算方法得到在FPGA上面的并行CRC通用計算方法，并可以根據(jù)需要，實現(xiàn)數(shù)據(jù)級聯(lián)計算，得到快速計算數(shù)據(jù)流的CRC方法。

1 CRC編碼解碼原理

1.1 CRC編碼

設(shè) M（x）為信息多項式，G（x）為生成多項式，得到的 CRC位數(shù)為 r，則 M（x）左移 r位，作模 2 除法，得到的商為 Q（x），余數(shù)多項式R（x）即是信息多項式的CRC校驗碼，數(shù)學(xué)表示為[1]：

1.2 CRC解碼

為確保數(shù)據(jù)信息的正確性，信息數(shù)據(jù)經(jīng)過CRC編碼得到CRC校驗碼，校驗碼和信息數(shù)據(jù)一起進(jìn)行數(shù)據(jù)封裝。如圖1所示。

圖1 CRC校驗數(shù)據(jù)封裝Fig.1 CRC data check frame

讀取信息數(shù)據(jù)加CRC校驗碼的時候，再用相同的生成多項式進(jìn)行校驗，若校驗結(jié)果不正確，那證明數(shù)據(jù)信息丟失或者已經(jīng)被破壞。數(shù)學(xué)表示為：

余數(shù)多項式結(jié)果為0為正確[2]，其余結(jié)果都說明數(shù)據(jù)不正確（有些像IEEE802.3中的CRC，因為特別的取反處理，余數(shù)多項式不是0，而是等于0xC704DD7B[3]）。典型CRC在FPGA上的應(yīng)用如圖2所示[4]。

2 串行CRC編碼解碼實現(xiàn)

CRC的編碼解碼可由一般的串行流水線算法來獲得，但是很多時候硬件接口串行的，并行接口也進(jìn)行串行流水線的CRC計算顯然不合理。如：最常用的CRC32生成多項式為：G（x）=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1[5]，串行流水線的硬件實現(xiàn)如圖3所示[4]：

圖3 串行CRC32硬件實現(xiàn)Fig.3 Serial CRC32 hard ware

（圖3中的Dx為D寄存器，⊕為異或運算。）由圖（3）可見，要處理n個數(shù)據(jù)輸入就要延遲n個時鐘周期才能得到CRC的校驗碼。而且很多時候往往硬件接口不是串行數(shù)據(jù)輸入，而是并行數(shù)據(jù)輸入，這就要求要把數(shù)據(jù)流進(jìn)行并行串行轉(zhuǎn)換，處理來很麻煩，不能滿足數(shù)據(jù)流的快速處理。下面介紹一種可以在硬件上實現(xiàn)，基于FPGA并利用超前位計算方法得到任意長度數(shù)據(jù)的并行CRC計算方法。該算法使得數(shù)據(jù)量很大的數(shù)據(jù)流可以在數(shù)據(jù)接收或者發(fā)送的開始時候就可以計算其CRC的校驗值，而不是把整個需要校驗的數(shù)據(jù)放到緩存區(qū)再開始計算校驗值，達(dá)到真正的并行數(shù)據(jù)處理目的。

3 并行CRC的實現(xiàn)

具體的算法描述如下：

假設(shè)數(shù)據(jù)輸入的位寬為m，第n個周期輸入數(shù)據(jù)為：

假設(shè)CRC生成多項式階數(shù)為r：

假設(shè)第n-1個周期計算得到的CRC校驗碼為

為了計算得到對應(yīng)第n個周期的數(shù)據(jù)輸入Dn（d）的CRC校驗值 C（n）（c），首先把第 n 個周期輸入數(shù)據(jù) Dn（d）左移 r位，擴(kuò)展為（m+r）位，其中低 r位補(bǔ) 0，即：

同時，實現(xiàn)級聯(lián)運算，把第n-1個周期計算得到的CRC校驗碼 C（n-1）（c）合到第 n 個周期要計算的數(shù)據(jù)里面，進(jìn)行模 2除法計算得到 CRC 校驗值 C（n）（c）。根據(jù)公式（1），C（n）（c）作為第n個周期的余數(shù)，那么有第n個周期要進(jìn)行模2除法計算的數(shù)據(jù)為：

（注：^為異或運算符號。）

為了快速實現(xiàn)模2除法，算法應(yīng)用了一種超前位計算方法。對于該超前位計算方法，利用模2除法運算方法，首先判斷 D``（n）（d）的最高位 dn（m+r-1）^c（n-1）（r-1）是否為 1，若 dn（m+r-1）^c（n-1）（r-1）為 1 則進(jìn)行除數(shù)為 CRC 生成多項式 G（g）的模 2 除法；若最高位 dn（m+r-1）^c（n-1）（r-1）為 0，那么把除數(shù) G（g）當(dāng)作 0，再作模 2除法，得到計算結(jié)果 D```（n）（d），即其運算如圖 4所示：

圖4 模2除法運算結(jié)果Fig.4 Result of module-2 division

然后 ，判斷 D```（n）（d）次高位 dn（m+r-2）^c（n-1）（r-2）^g（r-1）是否為1，再進(jìn)行下一步的計算，其運算過程與 D``（n）（d）最高位的判斷計算一樣，直至到第r步，最后得到的余數(shù)則為該數(shù)據(jù)的CRC校驗值。

對于最高位的判斷運算，因為CRC生成多項式G（g）的最高位 g（r-1）為 1，所以不管 dn（m+r-1）^c（n-1）（r-1）是不是 1，作模 2除法的結(jié)果是 D```（n）（d）的最高位為 0。 也就是說，不管 D``（n）（d）的最高位 dn（m+r-1）^c（n-1）（r-1）是否為 0，經(jīng)過第一步計算，其結(jié)果都是 D```（n）（d）的最高位為 0。

同理，對于余下的r-2次運算采用相同的計算方法進(jìn)行遞推。計算完r次之后，得到的數(shù)據(jù)就是第n個周期輸入數(shù)據(jù)Dn（d），并且第n-1個周期計算得到的 CRC校驗碼為C（n-1）（c）時，對應(yīng) CRC 生成多項式 G（g）的 CRC 校驗值C（n）（c）。

例如，假設(shè)輸入數(shù)據(jù)寬度為8位，CRC生成多項式的為G（g）=g5+g4+g3+1，那么根據(jù)上述算法可以得到在FPGA上面的函數(shù)實現(xiàn)代碼如下：

程序中，DATA_in為8位的數(shù)據(jù)輸入，CRC_last為上次的CRC校驗值，CRC5_D8為CRC計算結(jié)果輸出。

如果要實現(xiàn)任意長度的數(shù)據(jù)CRC校驗，則只需要把上次的數(shù)據(jù)輸入得到的CRC校驗碼作為本次CRC校驗碼輸入，那樣就可以進(jìn)行級聯(lián)，計算得到任意長度的數(shù)據(jù)CRC校驗碼。

此算法充分利用FPGA的并行處理能力和數(shù)學(xué)算法上的超前位計算原理實現(xiàn)快速有效的CRC計算，與傳統(tǒng)的流水線法、矩陣法[6]等相比有非常大的優(yōu)勢。該算法對于任意寬度的數(shù)據(jù)輸入，和任意生成多項式也都通用，非常靈活，并且算法是基于遞推方法，F(xiàn)PGA的程序也可以由軟件語言VC++，VB等來生成得到，使用非常方便實用。

4 結(jié)果與仿真

使用的FPGA芯片為ALTERA公司的低端芯片EP1C6T144I7，其運算速度最快可達(dá)320 MHz，也就是說 3.2 ns的時間就可以把8位的數(shù)據(jù)的CRC校驗碼計算出來。實現(xiàn)級聯(lián)的計算，如在圖5中，連續(xù)輸入數(shù)據(jù)流0x35、0x65、0x9A、0x3F、0x65、0x10、0xBB、0x8C、0x27、0XB9、0x97、0x8D、0x2C，在剛接完最后一個數(shù)據(jù)0x2C時候就可以得到這一串?dāng)?shù)據(jù)流的CRC校驗值0x08。對比要接收完整個數(shù)據(jù)流再作相應(yīng)的CRC計算有極大的優(yōu)勢。同時使用的FPGA資源非常少，只用了23個邏輯單元，很好地做到速度與資源的平衡。采用更高端的FPGA芯片，速度更高，此算法完全可以滿足10 Gbit的以太網(wǎng)數(shù)據(jù)的CRC校驗計算。

圖5 實現(xiàn)級聯(lián)的CRC仿真結(jié)果時序圖Fig.5 simulated CRC timing of data sequence

5 結(jié)束語

以上算法對于任意位數(shù)據(jù)輸入，任意生成多項式都可通用，任意長度的數(shù)據(jù)通過級聯(lián)可以得到CRC校驗碼輸出，并且采用并行處理和超前位計算，達(dá)到非常高的運算速度。其算法的FPGA實現(xiàn)應(yīng)用也非常廣泛，不論是一般的串行數(shù)據(jù)通訊，還是100 M，1 000 M甚至10 GM的以太網(wǎng)都可以用到。對此Xilinx，Altera等FPGA公司都開發(fā)了相關(guān)的IP（知識產(chǎn)權(quán)）。本算法已經(jīng)成功用于FPGA上的串行數(shù)據(jù)發(fā)送及1 000 MHz/100 MHz以太網(wǎng)等通訊，達(dá)到快速處理數(shù)據(jù)流檢錯的效果。

[1]曹志剛，錢亞生.現(xiàn)代通訊原理[M].北京：清華大學(xué)出版社，1992.

[2]常天海，胡鑒.基于FPGA的CRC并行算法研究與實現(xiàn)[J].微處理機(jī)，2010，4（2）:45-48.

CHANG Tian Hai，HU Jian.Applicating research of CRC parallel algorithm base on FPGA[J].Microprocessors 2010，4（2）：45-48.

[3]Chris Borrelli.IEEE 802.3 Cyclic Redundancy Check[S]2001.

[4]Sunita Jain&Guru Prasanna.在Virtex-5 FPGA中使用CRC 硬模塊[EB/OL]（2008-12）.http://www.doc88.com/P-38579361672.html.

[5]ISO/IEC.IEEE Std 802.3 2000 Edition.Part3.Carrier sense multiple access with collision detection （CSMA/CD）access method and physical layer specifications.[S].2000.

[6]劉昭，蘇厲，金德鵬，等，10G以太網(wǎng)系統(tǒng)中的并行CRC編解碼器設(shè)計[J].電子技術(shù)應(yīng)用，2004，30（4）：47-50.

LIU Zhao，SU Li.，JIN De-peng，et al.Parallel CRC Coder and Decoder Designed in 10G Ethernet System.[J].Application of Electronic Technique，2004，30（4）：47-50.