莫元勁，黃水永

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

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

CRC的編碼解碼可由一般的串行流水線算法來獲得，但是很多時候硬件接口串行的，并行接口也進行串行流水線的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個數據輸入就要延遲n個時鐘周期才能得到CRC的校驗碼。而且很多時候往往硬件接口不是串行數據輸入，而是并行數據輸入，這就要求要把數據流進行并行串行轉換，處理來很麻煩，不能滿足數據流的快速處理。下面介紹一種可以在硬件上實現(xiàn)，基于FPGA并利用超前位計算方法得到任意長度數據的并行CRC計算方法。該算法使得數據量很大的數據流可以在數據接收或者發(fā)送的開始時候就可以計算其CRC的校驗值，而不是把整個需要校驗的數據放到緩存區(qū)再開始計算校驗值，達到真正的并行數據處理目的。

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

具體的算法描述如下：

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

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

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

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

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

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

為了快速實現(xiàn)模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上面的函數實現(xiàn)代碼如下：

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

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

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

4 結果與仿真

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

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

5 結束語

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

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

[2]常天海，胡鑒.基于FPGA的CRC并行算法研究與實現(xiàn)[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以太網系統(tǒng)中的并行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.