基于FPGA的CRC算法的串行和并行實現

肖艷艷,何曉雄

(合肥工業大學 電子科學與應用物理學院，安徽 合肥 230009)

?

基于FPGA的CRC算法的串行和并行實現

肖艷艷,何曉雄

(合肥工業大學 電子科學與應用物理學院，安徽 合肥 230009)

在數字數據通信系統中, 由于信道傳輸特性不理想以及噪聲等干擾,常常會出現一些異常情況。因此,通常在數據通信中添加循環冗余校驗(cyclic redundancy check,CRC)碼,可以大幅度提高通信的可靠性。文章在論述串行CRC實現的基礎上,對電路結構提出了改進的方案,實現了基于現場可編程邏輯門陣列(field programmable gate array,FPGA)的CRC的串行2、4、8位和并行算法,并用超高速集成電路硬件描述語言(very-high-speed integrated circuit hardware description language,VHDL)實現CRC校驗,將實驗結果下載到DE2,驗證了方案的可行性。

循環冗余校驗碼;串行算法;并行算法;超高速集成電路硬件描述語言;現場可編程邏輯門陣列

0 引 言

數字數據通信系統中, 由于信道傳輸特性不理想以及噪聲等干擾,數字信號會發生畸變, 從而產生誤碼[1]。為了降低誤碼率, 信道差錯控制編碼得到了廣泛的應用。循環冗余校驗(cyclic redundancy check,CRC)碼就是其中一種有效的編碼技術,在移動通信、計算機通信、USB 接口及測控等領域有著廣泛的應用。具體做法如下:在要發送的有用碼后邊添加一個比特串(即CRC)，成一個新的數據來實現數據傳輸差錯檢測[2]。CRC碼的作用是保證數據傳輸的可靠性,它本身并不是系統要求傳輸的數據,所以對系統來說它是冗余的。CRC算法可以用軟件實現,也可以用硬件實現,但軟件實現的速度受限于系統CPU速度。使用硬件實現可以提高計算速度,從而提高系統的通信速率。串行算法由于其原理簡單,易于實現,但速度相對較慢,因此常被用在串行通信中。在高速數據傳輸的場合,需用并行算法實現,該算法增加了數據的吞吐量,但其硬件成本有所增加。本文在串行算法基礎上,對其進行了改進,實現了串行2、4、8位算法以及并行算法。

1 CRC校驗原理

采用CRC 校驗時,發送方和接收方事先約定一個生成多項式G(x),該生成多項式作為除數多項式,將要發送的數據比特序列作為一個多項式[3]M(x) 的系數,該多項式為被除多項式,被除多項式M(x) 與除數多項式的余數多項式R(x)的系數為CRC碼,它添加在要檢測的二進制位串后邊,形成發送碼,如圖1所示。 數據鏈路將發送碼發送到接收方后,接收方同樣將其看成是一個多項式的系數序列,并用相同的生成多項式來除該多項式。 若余數為0,則傳輸無差錯;否則,傳輸有差錯。

圖1 CRC碼

其CRC編碼過程[4-6]如下:設待校驗的信息碼M有k位,即M=(mk-1,mk-2,…,m1,m0),可用多項式M(x)表示為:

(1)

若采用的生成多項式G(x)的最高次冪為r,則有:

(2)

則(1) 式兩端乘以xr得:

(3)

設xrM(x)模-2除以G(x)得到的商多項式為Q(x),余數多項式為R(x)(以下討論均按此約定),即

(4)

由于模-2運算中加減運算的等效性,(4)式等效為:

(5)

其中余數多項式R(x)可表示為:

(6)

將(3)式、(6)式代入(5)式,可得:

(7)

(7)式所對應的碼組M′為k+r位,即

(8)

這就是CRC碼的生成過程,rr-1,rr-2…,r1,r0為校驗位。 由(5)式可知,若信息碼在發送、傳輸及接收過程中沒有發生錯誤,則在接收端將收到的k+r位CRC碼M′除以相同的生成多項式G(x)所產生的余數必然為0,否則可知在通信過程中產生了誤碼。

CRC碼是由生成多項式G(x)按上述算法生成的,但G(x)的選擇并不是隨意的。目前最常用的生成多項式如下:

(1) CRC-8,G(x)=x8+x5+x4+1,R(x)由8位組成。

(2) CRC-9,G(x)=x9+x6+x5+x4+x3+1,R(x)由9位組成。

(3) CRC-12,G(x)=x12+x11+x3+x2+1,R(x)由12位組成。

(4) CRC-16,G(x)=x16+x15+x2+1,R(x)由16位組成[7-8]。

(5) CRC-CCITT,G(x)=x16+x12+x5+1,R(x)由16位組成[9]。

(6) CRC-32,G(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1,R(x)由32 位組成。

本次CRC碼的串行和并行實現所采用的生成多項式均為G(x)=x8+x5+x4+1,每次處理的數據位寬為16。

2 串行算法實現

計算CRC碼一般采用移位寄存器和一些異或門實現,其原理如圖2所示。

圖2 串行實現原理圖

移位寄存器的初值設置為0000-0000,串行實現時,其仿真波形如圖3所示,每當輸入一個數據,移位寄存器crc-reg的值經過移位和異或更新1次。當16位輸入數據date=1100101110100001全部輸入到移位寄存器時,此時的寄存器crc-reg的01111101值就是輸入的16位數據對應 的CRC碼。然后發送端將輸入數據和CRC碼組成新的數據發送,新的數據為:data-out=110010111010000101111101。接收端接收到數據后重新計算輸入數據的CRC值,然后將發送端發送來的CRC校驗位與接收端剛剛計算的CRC相異或,crc-val的值為0,error輸出為0,data-ture為1100101110100001。理論結果和仿真結果一致,接下來的數據輸出如圖3所示,與第1組數據一樣。

圖3 CRC校驗的1位串行實現仿真波形

由此可見,串行計算的硬件實現簡單,易于操作。但1個時鐘周期只能處理1位數據,處理數據的速度較慢、效率較低,只適用在低速數據傳輸的串行輸入輸出系統中。而在高速數據傳輸系統中不適用,因此對1位串行算法進行了改進,實現了1個時鐘周期同時處理2、4、8位數據。這樣依次有效地提高了數據處理速度，從而提高了系統的傳輸速度。

本文只對4位的串行輸入介紹。與1位串行實現不同的是,1個時鐘周期同時處理4位輸入數據,這樣輸入的16位數據只需要4個時鐘周期,仿真結果如圖4所示。

圖4 CRC校驗的4位串行實現仿真波形

3 并行算法實現

并行實現是在串行算法實現的基礎上做了進一步的改進。上述在1位串行的基礎上實現了2、4、8位串行CRC的計算,而全并行的實現只要在8位串行的基礎上稍加改進,將1個時鐘周期處理8位輸入數據改為1個時鐘周期處理16位輸入數據就可實現全并行CRC的計算。其原理框圖和串行CRC計算的原理框圖類似,也是用移位寄存器實現,主要verilog編碼如下:

crc-temp=8'b0;

for (i=15;i>=0;i=i-1)

begin

temp=data-in[i] ＾ crc-temp[7];

for(j=7;j>5;j=j-1)

crc-temp[j]=crc-temp[j-1];

crc-temp[5]=temp ＾ crc-temp[4];

crc-temp[4]=temp ＾ crc-temp[3];

for(k=3;k>0;k=k-1)

crc-temp[k]=crc-temp[k-1];

crc-temp[0]=temp;

end.

并行CRC實現的頂層模塊主要有數據輸入控制模塊、數據發送模塊和數據接收模塊。其信號端口定義見表1所列。各模塊的功能如下:

(1) 數據輸入控制模塊。主要是控制數據的輸入,根據數據地址的選擇控制數據的輸出。

(2) 數據發送模塊。主要是用移位寄存器計算輸入數據的CRC值,組成新的數據發送給接收端。

(3) 數據接收模塊。將發送端傳來的數據進行儲存,重新計算輸入數據的CRC值,將前后2次的CRC值進行比較,判斷數據在傳輸中是否出現錯誤。若出現錯誤,判斷是否1位出錯,若1位出錯,則糾錯;若2位以上出錯，則請求重發。

表1 并行CRC校驗頂層模塊信號端口定義

頂層模塊仿真結果如圖5所示,由圖5可以到出,當數據輸入控制端傳來數據data=1100101110100001時,發送端開始工作,在下1個時鐘周期計算出第1組數據的CRC碼crc-reg=01111101,然后將計算出來的CRC值放在輸入數據的后面形成新的數據data-out=110010111010000101111101發送出去。

圖5 CRC校驗的并行實現仿真波形

接收端接收到發送端傳來的數據后,重新計算輸入數據的CRC值,記為crc-reg-rec,將該值與發送端計算的crc-reg異或,即crc-val=crc-reg-rec ＾ crc-reg,若crc-val值為0,則error為0,數據傳輸無誤;若crc-val值不為0,error為1,數據傳輸錯誤。不同位出錯對應的CRC值見表2所列。若crc-reg的值出現在表2中,說明在數據傳輸中出現1位數據傳輸錯誤,對應的出錯位為data[n],n代表出錯位數,檢測出第n位出錯后只要將對應的出錯位取反即為正確值。若crc-val的值沒有出現在表2中,說明數據傳輸中,有2位或2位以上的數據出錯。

表2 不同位出錯對應的CRC值

4 測試方法及仿真結果

測試結果以并行CRC校驗結果為例,頂層模塊的輸入輸出信號見表1所列,輸入的信息碼是預先存儲在存儲器中,每個16位信息碼對應一個4位的地址信號,在圖3的data里可以看到預先設置的數據信號。為方便,將地址信號寫成1個計數器,當reset=0,data-valid=1時,每到1個時鐘的上升沿,地址信號加1。將程序通過Quartus ii下載到DE2電路板上,在電路板上運行后的仿真結果可以通過Quartus ii的tools下面的SignalTap II Logic Analyzer查看，測試結果如圖6所示。

當reset=1,data-valid=0時,復位的同時輸入數據無效,下一個時鐘上升沿,reset=0,data-valid=1,復位無效,數據輸入有效,每個時鐘上升沿,發送端發送1個24位信息碼(前16位為輸入數據信號,后8位為數據信號對應的校驗碼),接收端接收到數據后將數據信號校驗碼分離,重新計算校驗碼,具體分析與圖4分析結果一致。仿真結果和測試結果一致,說明該設計方法是有效的,符合設計要求。

圖6 并行CRC校驗算法測試結果

5 結 論

本文基于CRC原理,詳細介紹了CRC的硬件實現。CRC的硬件實現有2種方式,即串行實現和并行實現。本文在串行算法實現的基礎上,對其結構進行了改進,同時實現了2、4、8位串行數據的實現,使得數據傳輸速率依次提高。該結構可以使用在滿足不同數據傳輸速率的傳輸系統中,因此一定程度上優化了1位串行CRC算法帶來的問題。為了進一步優化電路結構,本文在8位串行實現的基礎上,實現了CRC的全并行算法,并用modelsim進行了電路仿真,同時搭建了測試平臺對代碼進行了動態的全面測試。本文設計的優點是相對于串行設計方法,速度大大提高,設計方法簡單、效率高,占用硬件資源少；缺點是該設計只能每個時鐘處理16位數據信號,若是多通道處理,則能進一步提高數據吞吐量。

[1] 張德云,尹勇生，劉志文，等.面向USB應用的CRC編解碼電路的設計與實現[J].合肥工業大學學報(自然科學版,2005,28(3):292-295.

[2] 蔣安平.循環冗余校驗碼(CRC)的硬件并行實現[J].微電子學與計算機,2007,24(2):107-109,112.

[3] 張焱,任勇峰,齊蕾,等.基于FPGA的CRC校驗算法的實現[J].電子器件,2015,38(1):222-226.

[4] 朱榮華.一種CRC并行計算原理及實現方法[J].電子學報,1999,27(4):143-145.

[5] 姚威.循環冗余校驗碼并行算法的研究與實現[J].計算機與數字工程,2006,34(9):112-114.

[6] 王海光.并行CRC算法硬件實現研究與VHDL設計[J].漳州師范學院學報(自然科學版),2007(4):51-56.

[7] 吳從中,尹夕振,彭樂.USB3.0頭包信息中CRC-16的Verilog實現[J].合肥工業大學學報(自然科學版),2012,35(5):632-635.

[8] 石林艷,羅漢文.CRC循環冗余校驗碼并行算法的FPGA實現[J].通信技術與應用,2005(8):60-63.

[9] PAN Yun,GE Ning,DONG Zaiwang.RC look-up optimization for single-bit error correction[J].Tsinghua Science & Technology,2007,12(5):620-623.

(責任編輯 閆杏麗)

Serial and parallel implementation of CRC algorithm based on FPGA

XIAO Yanyan,HE Xiaoxiong

(School of Electronic Science and Applied Physics, Hefei University of Technology, Hefei 230009, China)

In digital data communication systems, due to the non-ideal channel transmission characteristics and the noise interference, some abnormal situation often appears in serial communication. Thus, adding the cyclic redundancy check(CRC) check code in the data communication can greatly improve the reliability of communication. On the basis of the analysis of the serial CRC implementation, the improved circuit structure is proposed and the two, four, eight bits serial algorithm and parallel algorithm of CRC based on the field programmable gate array(FPGA) are implemented. The CRC check is realized by using the very-high-speed integrated circuit hardware description language(VHDL), and then the experimental results are downloaded to DE2 to verify the feasibility of the scheme.

cyclic redundancy check(CRC); serial algorithm; parallel algorithm; very-high-speed integrated circuit hardware description language(VHDL); field programmable gate array(FPGA)

2015-07-29；

2015-10-15

中科院重點實驗室開放課題資助項目(IIMDKFJJ-13-06;IIMDKFJJ-14-04)

肖艷艷(1990-),女,安徽淮北人,合肥工業大學碩士生;

何曉雄(1956-),男,安徽宿松人,合肥工業大學教授,博士生導師.

10.3969/j.issn.1003-5060.2016.10.013

TN919.1

A

1003-5060(2016)10-1362-05