闞佳沖等

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

關鍵詞： 全參數化； CRC算法； Verilog； FPGA； 以太網

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

0 引 言

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

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

1 全參數化CRC算法原理

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

1.1 CRC運算串行編碼

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

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

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

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

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

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

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

1.2 全參數化CRC并行編碼

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

1.2.1 k（x）公式推導

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

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

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

根據表2進行推導，可以得到當輸入x比特數據后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）表示每個寄存器最終值，根據類似的推導方法，利用表1的公式，在表2的基礎上進行計算推導，根據串行編碼的原理，當d0，d1，d2，d3到來時，每個寄存器都會刷新一次輸出值，如表3所示，其中i表示模塊當前寄存器標號，C7～C0表示i個寄存器的當前值。

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

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

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

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

2 全參數化CRC算法實現

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

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

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

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

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

3 全參數化CRC算法應用

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

3.1 以太網FCS

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

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

3.2 串行通信CRC?16校驗

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

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

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

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

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

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

4 結 語

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

參考文獻

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

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

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

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

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

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

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

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