并行CRC在FPGA上的實現

莫元勁，黃水永

（廣州數控設備有限公司 廣東 廣州 510165）

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

1 CRC編碼解碼原理

1.1 CRC編碼

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

1.2 CRC解碼

為確保數據信息的正確性，信息數據經過CRC編碼得到CRC校驗碼，校驗碼和信息數據一起進行數據封裝。如圖1所示。

圖1 CRC校驗數據封裝Fig.1 CRC data check frame

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

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

2 串行CRC編碼解碼實現

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

圖3 串行CRC32硬件實現Fig.3 Serial CRC32 hard ware

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

3 并行CRC的實現

具體的算法描述如下：

假設數據輸入的位寬為m，第n個周期輸入數據為：

假設CRC生成多項式階數為r：

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

為了計算得到對應第n個周期的數據輸入Dn（d）的CRC校驗值 C（n）（c），首先把第 n 個周期輸入數據 Dn（d）左移 r位，擴展為（m+r）位，其中低 r位補 0，即：

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

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

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

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

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

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

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

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

程序中，DATA_in為8位的數據輸入，CRC_last為上次的CRC校驗值，CRC5_D8為CRC計算結果輸出。

如果要實現任意長度的數據CRC校驗，則只需要把上次的數據輸入得到的CRC校驗碼作為本次CRC校驗碼輸入，那樣就可以進行級聯，計算得到任意長度的數據CRC校驗碼。

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

4 結果與仿真

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

圖5 實現級聯的CRC仿真結果時序圖Fig.5 simulated CRC timing of data sequence

5 結束語

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

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

[2]常天海，胡鑒.基于FPGA的CRC并行算法研究與實現[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以太網系統中的并行CRC編解碼器設計[J].電子技術應用，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.