闞佳沖等

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

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

中圖分類號(hào)： TN919?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2015）08?0154?05

0 引 言

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

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

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

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

1.1 CRC運(yùn)算串行編碼

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

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

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

因此不失一般性，可以假設(shè)生成多項(xiàng)式為：

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

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

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

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

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

1.2.1 k（x）公式推導(dǎo)

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

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

來時(shí)相應(yīng)的k（x）的值，如表2所示，其 中C7～C0表示所有寄存器的當(dāng)前值。

根據(jù)表2進(jìn)行推導(dǎo)，可以得到當(dāng)輸入x比特?cái)?shù)據(jù)后k（x）表達(dá)式為：

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

進(jìn)一步整理得：

[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校驗(yàn)碼的位寬。

1.2.2 Ri（x）公式推導(dǎo)

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 以太網(wǎng)FCS

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

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

3.2 串行通信CRC?16校驗(yàn)

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

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

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

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

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

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

4 結(jié) 語

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

參考文獻(xiàn)

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

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

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

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

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

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

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

[8] 季鵬輝.基于FPGA的16bitCRC校驗(yàn)查表法設(shè)計(jì)[J].電子器件，2013，8（4）：581?583.