基于FPGA的CRC算法的串行和并行實(shí)現(xiàn)

肖艷艷,何曉雄

(合肥工業(yè)大學(xué) 電子科學(xué)與應(yīng)用物理學(xué)院，安徽 合肥 230009)

?

基于FPGA的CRC算法的串行和并行實(shí)現(xiàn)

肖艷艷,何曉雄

(合肥工業(yè)大學(xué) 電子科學(xué)與應(yīng)用物理學(xué)院，安徽 合肥 230009)

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

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

0 引 言

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

1 CRC校驗(yàn)原理

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

圖1 CRC碼

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

其中余數(shù)多項(xiàng)式R(x)可表示為:

(6)

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

(7)

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

(8)

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

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

(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碼的串行和并行實(shí)現(xiàn)所采用的生成多項(xiàng)式均為G(x)=x8+x5+x4+1,每次處理的數(shù)據(jù)位寬為16。

2 串行算法實(shí)現(xiàn)

計(jì)算CRC碼一般采用移位寄存器和一些異或門實(shí)現(xiàn),其原理如圖2所示。

圖2 串行實(shí)現(xiàn)原理圖

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

圖3 CRC校驗(yàn)的1位串行實(shí)現(xiàn)仿真波形

由此可見,串行計(jì)算的硬件實(shí)現(xiàn)簡單,易于操作。但1個(gè)時(shí)鐘周期只能處理1位數(shù)據(jù),處理數(shù)據(jù)的速度較慢、效率較低,只適用在低速數(shù)據(jù)傳輸?shù)拇休斎胼敵鱿到y(tǒng)中。而在高速數(shù)據(jù)傳輸系統(tǒng)中不適用,因此對1位串行算法進(jìn)行了改進(jìn),實(shí)現(xiàn)了1個(gè)時(shí)鐘周期同時(shí)處理2、4、8位數(shù)據(jù)。這樣依次有效地提高了數(shù)據(jù)處理速度，從而提高了系統(tǒng)的傳輸速度。

本文只對4位的串行輸入介紹。與1位串行實(shí)現(xiàn)不同的是,1個(gè)時(shí)鐘周期同時(shí)處理4位輸入數(shù)據(jù),這樣輸入的16位數(shù)據(jù)只需要4個(gè)時(shí)鐘周期,仿真結(jié)果如圖4所示。

圖4 CRC校驗(yàn)的4位串行實(shí)現(xiàn)仿真波形

3 并行算法實(shí)現(xiàn)

并行實(shí)現(xiàn)是在串行算法實(shí)現(xiàn)的基礎(chǔ)上做了進(jìn)一步的改進(jìn)。上述在1位串行的基礎(chǔ)上實(shí)現(xiàn)了2、4、8位串行CRC的計(jì)算,而全并行的實(shí)現(xiàn)只要在8位串行的基礎(chǔ)上稍加改進(jìn),將1個(gè)時(shí)鐘周期處理8位輸入數(shù)據(jù)改為1個(gè)時(shí)鐘周期處理16位輸入數(shù)據(jù)就可實(shí)現(xiàn)全并行CRC的計(jì)算。其原理框圖和串行CRC計(jì)算的原理框圖類似,也是用移位寄存器實(shí)現(xiàn),主要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實(shí)現(xiàn)的頂層模塊主要有數(shù)據(jù)輸入控制模塊、數(shù)據(jù)發(fā)送模塊和數(shù)據(jù)接收模塊。其信號端口定義見表1所列。各模塊的功能如下:

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

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

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

表1 并行CRC校驗(yàn)頂層模塊信號端口定義

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

圖5 CRC校驗(yàn)的并行實(shí)現(xiàn)仿真波形

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

表2 不同位出錯(cuò)對應(yīng)的CRC值

4 測試方法及仿真結(jié)果

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

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

圖6 并行CRC校驗(yàn)算法測試結(jié)果

5 結(jié) 論

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

[1] 張德云,尹勇生，劉志文，等.面向USB應(yīng)用的CRC編解碼電路的設(shè)計(jì)與實(shí)現(xiàn)[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版,2005,28(3):292-295.

[2] 蔣安平.循環(huán)冗余校驗(yàn)碼(CRC)的硬件并行實(shí)現(xiàn)[J].微電子學(xué)與計(jì)算機(jī),2007,24(2):107-109,112.

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

[4] 朱榮華.一種CRC并行計(jì)算原理及實(shí)現(xiàn)方法[J].電子學(xué)報(bào),1999,27(4):143-145.

[5] 姚威.循環(huán)冗余校驗(yàn)碼并行算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)與數(shù)字工程,2006,34(9):112-114.

[6] 王海光.并行CRC算法硬件實(shí)現(xiàn)研究與VHDL設(shè)計(jì)[J].漳州師范學(xué)院學(xué)報(bào)(自然科學(xué)版),2007(4):51-56.

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

[8] 石林艷,羅漢文.CRC循環(huán)冗余校驗(yàn)碼并行算法的FPGA實(shí)現(xiàn)[J].通信技術(shù)與應(yīng)用,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.

(責(zé)任編輯 閆杏麗)

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

中科院重點(diǎn)實(shí)驗(yàn)室開放課題資助項(xiàng)目(IIMDKFJJ-13-06;IIMDKFJJ-14-04)

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

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

10.3969/j.issn.1003-5060.2016.10.013

TN919.1

A

1003-5060(2016)10-1362-05