基于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