基于FPGA全參數(shù)化CRC的推導及實現(xiàn)

闞佳沖等

摘 要： 提出一種新型的全參數(shù)化CRC算法。詳細地介紹全參數(shù)化CRC的算法原理，并給出算法公式的推理過程及結果，通過Verilog語言設計實現(xiàn)，給出了基于FPGA平臺的仿真波形圖，并成功應用于工程項目當中，最后詳細分析了全參數(shù)化CRC算法在實現(xiàn)過程中的優(yōu)勢。這里提出的全參數(shù)化CRC算法，可以通過參數(shù)化配置，實現(xiàn)CRC?4、CRC?8、CRC?12等任何CRC?X的運算，亦可以實現(xiàn)任何數(shù)據(jù)位寬（數(shù)據(jù)位寬小于等于CRC校驗碼位寬）、任意生成多項式的CRC運算。

關鍵詞： 全參數(shù)化； CRC算法； Verilog； FPGA； 以太網(wǎng)

中圖分類號： TN919?34 文獻標識碼： A 文章編號： 1004?373X（2015）08?0154?05

0 引 言

在現(xiàn)行的數(shù)字通信系統(tǒng)中要進行穩(wěn)定可靠并且快速的通信，同時又要保證數(shù)據(jù)在傳輸過程的準確性，這就需要對通信過程添加差錯控制機制[1]。

循環(huán)冗余校驗碼（Cyclic Redundancy Check，CRC）是數(shù)據(jù)通信領域中比較常應用到的一種差錯校驗碼，它的明顯特征就是整個數(shù)據(jù)包文的信息位和校驗碼位的位寬可以任意改變。但是現(xiàn)行的CRC校驗技術都是針對某一特定領域，或者指定生成多項式，校驗碼位寬等，具有很大的約束性。如果進行不同CRC校驗時就需要重新設計模塊，浪費時間精力的同時，多個校驗模塊又浪費了寶貴的FPGA邏輯資源，同時傳統(tǒng)串行CRC算法效率低，很難滿足視頻信號實時處理的要求[2]。本文即以這個問題為突破口，設計出一個可以在各個領域通用的CRC校驗機制。本設計在傳統(tǒng)CRC的FPGA串行編碼[3]的基礎上，通過分析、整理、歸納最終得到適用于不同領域，不同校驗碼位寬，不同數(shù)據(jù)位寬，不同生成多項式的CRC運算通用算法，該通用CRC校驗算法大大地減少了資源的利用率，僅僅用到極少數(shù)目的寄存器，同時又沒有借助任何ROM去存儲數(shù)據(jù)，結論證實全參數(shù)化的CRC校驗算法能夠跑到較高的時鐘頻率。設計通過Verilog進行硬件描述[4]，在基于FPGA平臺實現(xiàn)了指定CRC校驗功能，并成功應用于工程項目當中。

1 全參數(shù)化CRC算法原理

在現(xiàn)有的數(shù)字通信系統(tǒng)中CRC校驗分為兩個部分，即發(fā)送方和接收方[5]。發(fā)送方用于對接收到的指定位寬包文數(shù)據(jù)（數(shù)據(jù)位）進行CRC運算得到指定位寬的CRC校驗碼；接收方用于對接收到的新包文數(shù)據(jù)（數(shù)據(jù)位和校驗碼位）進行同樣的CRC運算，如果結果為0，則代表CRC校驗通過，否則不通過。在本設計中通過參數(shù)化設計很好地將發(fā)送方和接收方的CRC運算邏輯結合到了一個模塊當中，即CRC運算模塊如圖1所示。

1.1 CRC運算串行編碼

以g（x）=X8+X6+X5+X3+X+1為例，串行CRC運算的實現(xiàn)如圖2所示。編碼前要先將電路中的寄存器初始化，然后將串行數(shù)據(jù)依次從input端輸入圖2電路，當所有串行數(shù)據(jù)輸入完畢，每個寄存器的最終值即為CRC校驗碼[3]。

（1） 全參數(shù)化CRC的初始值。CRC校驗的應用非常廣泛，不同領域CRC計算的初始值是不相同的，例如以太網(wǎng)領域，初始值為全1，而在其他領域，初始值為全0或其他值。本文設計的全參數(shù)化CRC為了適應這種應用需求，在模塊中定義一個參數(shù)INIT_VALUE，這樣就可以在復位或重新運算時，直接加載INIT_VALUE即可。

（2） 全參數(shù)化CRC的生成多項式。多項式g（x）的項系數(shù)直接影響數(shù)據(jù)異或的位置（去除最高次項）。例如g（x）=X8+X6+X5+X3+X+1中，在X6，X5，X3，X、1（X0），項系數(shù)為1的項前加上異或，就得到了圖2對應的電路。

因此不失一般性，可以假設生成多項式為：

g（x）=X8+P7X7+P6X6+P5X5+P4X4+P3X3+P2X2+P1X+P01

式中：P7～P0表示生成多項式各項前面的系數(shù)（最高次項和最低次項固定為1，故P0=1），其對應的電路結構如圖3所示。當生成多項式項系數(shù)為1時即相應位的P=1，表示當前輸入要與前一個寄存器的輸出相異或，得到下一時刻的CRC值，例如圖2中X6項系數(shù)為1即P6=1，而X4的項系數(shù)為0即P4=0。

經(jīng)過對比圖2和圖3電路，會發(fā)現(xiàn)如果去掉圖3電路相應位置的異或門（圈內(nèi)部分）即可變換成圖2生成多項式的電路。因此，本設計通過控制P值，進而控制圖3中相應位置異或門有無，最終使算法達到覆蓋任意形式的生成多項式。

1.2 全參數(shù)化CRC并行編碼

為了提高CRC校驗速度，現(xiàn)將由單比特輸入改為多比特同時輸入，此時的CRC校驗機制和串行編碼相同，因此，可由CRC串行編碼推導出最終的并行編碼，步驟如下：

1.2.1 k（x）公式推導

假設圖3中與數(shù)據(jù)輸入input相連異或門的輸出設為k（x），其中x表示連續(xù)輸入的單比特數(shù)據(jù)，文中用d（x）表示。則由圖3可得到R7～R0各個寄存器次態(tài)的表達式如表1所示。

如果要將輸入的串行1比特數(shù)據(jù)改為4 b數(shù)據(jù)，首先要根據(jù)串行單比特數(shù)據(jù)編碼的思想，得到當d0，d1，d2，d3到

來時相應的k（x）的值，如表2所示，其 中C7～C0表示所有寄存器的當前值。

根據(jù)表2進行推導，可以得到當輸入x比特數(shù)據(jù)后k（x）表達式為：

k（x）=dx^C（n-x-1）^[（P（i-x）&k0^…^（P（i-1）&k（x-1））]

進一步整理得：

[kx=dx^C（n-x-1）^a=0x-1 Pn-a-1k（x-a-1）， n>x>0d0 ^ C（n-1）， x=0]

式中n表示CRC校驗碼的位寬。

1.2.2 Ri（x）公式推導

假設Ri（x）表示每個寄存器最終值，根據(jù)類似的推導方法，利用表1的公式，在表2的基礎上進行計算推導，根據(jù)串行編碼的原理，當d0，d1，d2，d3到來時，每個寄存器都會刷新一次輸出值，如表3所示，其中i表示模塊當前寄存器標號，C7～C0表示i個寄存器的當前值。

推導過程和第1.2.1節(jié)所述一致，表3中表示當前輸入第4 b數(shù)據(jù)的結果，以此為基礎進一步推導出第x位數(shù)據(jù)輸入后，寄存器最終值的表達式。

整理得到最終的Ri（x）的通用表達式：

[Rix= C（i-x-1）^b=0xPi-bk（x-b）， x

為了實現(xiàn)本設計的全參數(shù)化CRC，模塊需要定義相關參數(shù)。其中輸入數(shù)據(jù)的位寬可通過參數(shù)DAT_W來設置；所有寄存器的初始值，可通過參數(shù)INIT_VALUE來設置；CRC校驗碼的位寬則可通過控制寄存器的個數(shù)來進行設置，即改變參數(shù)CRC_W，P表示生成碼的低CRC_W位，可通過參數(shù)CRC_POLY來設置。這樣就實現(xiàn)了兼容不同領域，不同CRC校驗碼位寬，不同生成多項式，不同輸入數(shù)據(jù)位寬的全參數(shù)化CRC運算算法。

2 全參數(shù)化CRC算法實現(xiàn)

在Verilog 2001里，新增加了generate語句，同時又拓展了generate用法。除了允許復制產(chǎn)生primitive和module的多個實例化，同時也可以復制產(chǎn)生多個reg、parameter、assign、always、initial等。因此通過generate去實現(xiàn)這兩個公式是個不錯的選擇。

根據(jù)上述推導出的公式，運用硬件描述語言Verilog中的generate將表達式k（x），Ri（x）表達式轉換成Verilog代碼，下面是generate生成公式的部分程序，見圖4。

圖5為CRC運算的仿真波形，按照上節(jié)所述進行參數(shù)設置：輸入數(shù)據(jù)位寬DAT_W=8，CRC校驗碼位寬CRC_W=8，其中選定運算的生成多項式為g（x）=X8+X7+X4+X3+X+1，則參數(shù)CRC_POLY=10011011，最后設置INIT_VALUE=0。

圖5中當輸入有效數(shù)據(jù)data后，crc_out就會輸出指定位寬的CRC校驗碼，testbench設置的第一個輸入數(shù)據(jù)為10101101，本地時鐘打一拍后即可得到CRC校驗碼00000111，并且仿真結果與Matlab中的數(shù)據(jù)結果完全一致，全參數(shù)化CRC運算機制的快速、準確一目了然。但這只是完成了全參數(shù)化CRC運算模塊的一部分內(nèi)容，即生成校驗碼，下面實現(xiàn)用生成好的校驗碼和原始數(shù)據(jù)實現(xiàn)CRC校驗查錯，CRC校驗仿真結果如圖6所示，輸入的數(shù)據(jù)（信息位）與圖5中的相同，但是在進行CRC校驗的時候要在8位數(shù)據(jù)的后面加上8位校驗碼，也就是此時的輸入數(shù)據(jù)有16位，其他幾個參數(shù)仍保持不變。由于圖5的數(shù)據(jù)只有8位，所以為了便于觀察比較在進行一次CRC運算后都進行了初始化，但是在進行圖5操作的時候就要等待數(shù)據(jù)完全輸入后才進行初始化。

如圖6所示，仿真波形圖顯示當數(shù)據(jù)位和校驗碼位輸入完畢后，輸出crc_out為0，可以很直觀的看到全參數(shù)CRC校驗機制快速準確地實現(xiàn)了CRC校驗功能。

3 全參數(shù)化CRC算法應用

為了更好說明全參數(shù)化CRC校驗的優(yōu)勢，文中列舉出FPGA利用以太網(wǎng)幀數(shù)據(jù)傳輸以及與上位機通信過程當中的具體應用。

3.1 以太網(wǎng)FCS

以太網(wǎng)幀格式包括前導碼（7 B）、幀起始定界符（1 B）、目的MAC地址（6 B）、源MAC地址（6 B）、類型/長度（2 B）、數(shù)據(jù)（46～1 500 B）、幀校驗序列FCS（4 B）。在項目中將OV7670攝像頭采集的圖像數(shù)據(jù)經(jīng)過SDRAM緩存后[6]，讀出攝像頭圖像數(shù)據(jù)并輸入到CRC運算模塊，經(jīng)過CRC運算模塊后圖像數(shù)據(jù)加上了用于以太網(wǎng)傳輸?shù)腇CS字段（32位CRC校驗碼），之后經(jīng)由以太網(wǎng)傳輸給網(wǎng)絡其他主機。流程如圖7所示。

在系統(tǒng)頂層文件中參數(shù)例化CRC運算模塊，根據(jù)以太網(wǎng)FCS[7]幀格式的要求，具體參數(shù)定義為：DAT_W=32，CRC_W=32，CRC_POLY=32h04811D37，INIT_VALUE=32′hFFFFFFFF。

3.2 串行通信CRC?16校驗

系統(tǒng)與上位機進行通信時，同樣也會由于各種各樣的干擾和噪聲的影響，導致接收到不正確的數(shù)據(jù)，因此系統(tǒng)設計時，在FPGA與上位機通信的時候也采取了CRC校驗機制，系統(tǒng)采用了常用的16位CRC校驗方式來實現(xiàn)上位PC機通訊系統(tǒng)中的差錯校驗。

同樣也在系統(tǒng)頂層文件中參數(shù)例化CRC運算模塊，根據(jù)串行通信要求，具體參數(shù)定義為：DAT_W=16，CRC_W=16，CRC_POLY=16′h8005，INIT_VALUE=16′h0000。

系統(tǒng)中例化全參數(shù)化CRC模塊后，相關統(tǒng)計信息如表5所示。

經(jīng)過對工程系統(tǒng)的測試分析，與傳統(tǒng)的CRC校驗機制相比，全參數(shù)化的CRC算法，可以大大地提高校驗速率。例如上述系統(tǒng)中的CRC?16，CRC?32的時鐘都能達到372 MHz，用到了極少的寄存器資源的同時，又縮短了CRC校驗的時間，并且又適用于多種不同CRC校驗工作。

整個工程中用到多種CRC校驗機制，只是簡單通過例化出不同參數(shù)的CRC運算模塊即可，方便快捷的解決了校驗問題。

全參數(shù)CRC校驗與傳統(tǒng)CRC校驗查表法和串行編碼校驗[8]的對比如表6所示。

4 結 語

本文設計算法具有通用性，可以廣泛應用于數(shù)據(jù)通信領域，設計得出的適用于不同領域滿足不同需要的全參數(shù)化CRC算法，不僅運算速度快，而且節(jié)省資源。通過Verilog語言描述實現(xiàn)，且很好地應用在基于FPGA平臺的工程實踐當中。因此本設計提出的全參數(shù)化CRC運算通用表達式，能夠滿足現(xiàn)行通信系統(tǒng)的準確性，快速性，節(jié)約性等的要求。隨著大信息時代的來臨，無論什么領域對于數(shù)據(jù)傳輸都有很嚴格的要求，但苦于沒有一個能夠兼容多領域且可以個性化設置的CRC校驗機制，本設計可以很好地解決這個問題，實現(xiàn)預想的CRC數(shù)據(jù)校驗功能。

參考文獻

[1] 李繼東，王博，袁晨光.在通信過程中用C語言實現(xiàn)CRC校驗[J].內(nèi)燃機與動力裝置，2009（z1）：43?46.

[2] 張友，鄭世軍.一種PSI濾波器設計中的并行CRC算法[J].電視技術，2005（3）：28?29.

[3] 石全峰，徐東明，謝慶勝，等.CRC算法在以太網(wǎng)數(shù)據(jù)幀中的應用及其硬件實現(xiàn)[J].廣東通信技術，2010（3）：32?36.

[4] 夏宇聞.Verilog數(shù)字系統(tǒng)設計教程[M].北京：北京航空航天大學出版社，2009.

[5] 呂曉敏.嵌套循環(huán)冗余碼（CRC）的優(yōu)化與檢驗[D].杭州：浙江大學，2012.

[6] 楊月娥.基于FPGA的視頻幀同步機的設計[J].電視技術，2009（9）：30?32.

[7] 顧文斌，王怡，馬莉.基于FPGA的CRC算法的實現(xiàn)[J].計算機與現(xiàn)代化，2008（5）：111?113.

[8] 季鵬輝.基于FPGA的16bitCRC校驗查表法設計[J].電子器件，2013，8（4）：581?583.