16位并行CRC算法的FPGA实现

(整期优先)网络出版时间:2017-07-17
/ 2

16位并行CRC算法的FPGA实现

张忠琪

(天津凯发电气股份有限公司天津300000)

摘要:CRC(循环冗余校验)算法广泛应用于通信领域,以提高数据传输的准确性。本文针对FPGA应用特点,介绍了一种适合于FPGA实现的CRC并行计算的设计方法,减少了系统的应用开销,实现更高的工作效率。

关键词:FPGA;CRC;VHDL;HDLC;LFSR

引言

RC误码检测能力强,抗干扰性能优异,在众多信道编码中得到了广泛应用,目前越来越多的通信设计使用FPGA/CPLD等可编程硬件来实现,使用软件方法进行CRC校验实时性差,不利于系统对错误数据进行及时处理。利用通信硬件实时的对信道数据进行误码检测,大大的改善了信道检测的时效性。传统的CRC多使用串行方式进行计算,整体速度较慢,结合fpga大量可用资源的特点,并行CRC算法得到了越来越多的应用。

本文介绍了一种快速crc算法的实现方法,并已在实际通信中得以验证。

1CRC介绍

CRC校验的基本思想是利用线性编码理论,串行传送的信息M(x)=(mn-1,mn-2,m1,m0)是一串n位二进制序列,将信息码用多项式M(x)表示:M(x)=mn-1Xn-1+mn-2Xn-2+…+m1X+m0在它被发送的同时,被一个先选择的生成多项式g(x)相除,生成多项式长r+1位,相除后得到r位的余数就是校验位,它拼接到原n位有效信息后面,即形成CRC码.CRC码到达接受方时,接受方的设备一方面接受CRC码,一方面用同样的方法与“生成多项式”相除,如果正好除尽,表示无信息差错,接受方去掉CRC码后面的r位校验,收下k位有效信息;如果不能除尽时,说明有信息的状态位发生了转变。即出错了,一般要求重新传送一次或者立即纠错。

根据不同的应用,crc有多种生成多项式:

CRC-16:x16+x15+x2+1IBMSDLC

CRC-CCITT:x16+x12+x5+1ISOHDLC,ITUX.25.

CRC-32:3x2+x26+x23+x22+x16+x12+x10+x8+x7+x5+x4+x2+1ZIP,RAR,IEEE802LAN/FDDI

2CRC并行算法分析

(1)CRC计算使用模2运算方法,模2运算与二进制四则运算法则相同,但不考虑借位和进位,及两个位上数字相同为0,不同为1.因此,模2运算本质上可以用异或来实现。

(2)传统的串行CRC计算方法

通常用一个线性反馈移位寄存器(LFSR)来实现CRC的计算。

图1LFSR

其中g(i)(i=0,1,…,r-1)的通断由生成多项式的对应的系数是0还是1决定,g(i)=1表示通路,g(i)=0与表示断路。

以生成多项式:g(x)=x16+x12+x5+1为例,则相应的g(16),g(12),g(5),g(0)。

在串行CRC算法下,待计算数据逐位的输入CRC移位寄存器进行计算。以一个8比特字节为例,完成一个字节的计算需要8个时钟才能完成。在高速通信下,如果为了提高计算速度,只能提高LFSR的移位时钟,在一些高速接口中,这往往意味着更加复杂的设计方法,对可靠性也增加了很多难度。

如果有方法能将多比特数据同步进行CRC计算,这样就可以在不提高时钟频率的前提下提高了计算速度。

3并行CRC计算方法

分析CRC的LFSR计算流程可知,每一位数据进行CRC计算时,计算结果取决于当前的计算数据,以及此时CRC移位寄存器中的值。

设mi为输入信息码数据(其中i=1,2...8),rij表示rj移位寄存器在第i个信息码输入后的状态值,(j=0,1...15为移位寄存器编号)。由图1可知,r0寄存器第8次移位输出的值r80等于第8个输入信息码m8与r15第7次移位输出的值相加。

r80=r715⊕m8.(1)

在本CRC计算式中,r12,r13,r14,r15间均为直接移位,在移位时钟的作用下可知

r715=r614=r513=r412,

因此式(1)演变为

r80=r412⊕m8.(2)

同理,

r412=r311⊕r315⊕m4.(3)

r311=r210=r19=r08(4)

r315=r214=r113=r012(5)

所以

r80=r80⊕r012⊕m4⊕m8

这样,我们建立了8位信息码和CRC寄存器初始值的计算关系,得到了第8位数据经过CRC后相应的第0个寄存器的结果。类似,我们可推理得到8位数据经过CRC后相应的各个寄存器的结果。

同理,我们也可以针对不同的生成多项式,或不同长度的信息码采用此方法进行CRC并行计算。

4并行算法实现

根据推导出的计算公式,很容易用可编程语言实现异或运算。

使用VHDL语言实现8位并行crc计算的主要代码如下,其中,CRC寄存器初始值设为全‘1’,以规避空闲态数据为全“0”时无法正确计算的现象:

CRC_CHECK:PROCESS(rst,rx_clk,crc_calculate_flag,cur_state)

VARIABLEdata_temp1:STD_LOGIC_VECTOR(8DOWNTO1);--------内部数据暂存器1

VARIABLEcrcreg:STD_LOGIC_VECTOR(15DOWNTO0);---------校验结果暂存器

VARIABLEC_para:STD_LOGIC_VECTOR(15DOWNTO0):="1111111111111111";-------------------校验初始参数

BEGIN

IF(rst='0')THEN

crcreg(15DOWNTO0):="1111111111111111";----------------------------初始化校验结果暂存器

rx_crc_buf(15DOWNTO0)<=X"FFFF";

ELSIF(rx_clk'eventANDrx_clk='1')THEN

data_temp1(8DOWNTO1):=data_buf(7DOWNTO0);-----------------将需要校验的数据放到缓存区

crcreg(0):=C_para(8)XORC_para(12)XORdata_temp1(4)XORdata_temp1(8);

crcreg(1):=C_para(9)XORC_para(13)XORdata_temp1(3)XORdata_temp1(7);

crcreg(2):=C_para(10)XORC_para(14)XORdata_temp1(2)XORdata_temp1(6);

crcreg(3):=C_para(11)XORC_para(15)XORdata_temp1(1)XORdata_temp1(5);

crcreg(4):=C_para(12)XORdata_temp1(4);

crcreg(5):=C_para(8)XORC_para(12)XORC_para(13)XORdata_temp1(3)XORdata_temp1(4)XORdata_temp1(8);

crcreg(6):=C_para(9)XORC_para(13)XORC_para(14)XORdata_temp1(2)XORdata_temp1(3);

crcreg(7):=C_para(10)XORC_para(14)XORC_para(15)XORdata_temp1(1)XORdata_temp1(2)XORdata_temp1(6);

crcreg(8):=C_para(0)XORC_para(11)XORC_para(15)XORdata_temp1(1)XORdata_temp1(5);

crcreg(9):=C_para(1)XORC_para(12)XORdata_temp1(4);

crcreg(10):=C_para(2)XORC_para(13)XORdata_temp1(3);

crcreg(11):=C_para(3)XORC_para(14)XORdata_temp1(2);

crcreg(12):=C_para(4)XORC_para(8)XORC_para(12)XORC_para(15)XORdata_temp1(1)XORdata_temp1(4)XORdata_temp1(8);

crcreg(13):=C_para(5)XORC_para(9)XORC_para(13)XORdata_temp1(3)XORdata_temp1(7);

crcreg(14):=C_para(6)XORC_para(10)XORC_para(14)XORdata_temp1(2)XORdata_temp1(6);

crcreg(15):=C_para(7)XORC_para(11)XORC_para(15)XORdata_temp1(1)XORdata_temp1(5);

C_para(15DOWNTO0):=crcreg(15DOWNTO0);------将校验结果作为下次校验的参数

rx_crc_buf(15DOWNTO0)<=crcreg(15DOWNTO0);--将校验结果存在CRC校验结果寄存器中

ENDIF;

接收端可采用相同的计算代码来进行接受信号的CRC计算,如果接受crc与发送crc的结果相同,则可认为传输正确,负责,信息再传输的过程中发生了变化,系统则对通信进行错误处理。

5结束语

本方案已成功经过的仿真运算,并且在实际的设计中得到了验证。

参考文献:

[1]张德云.面向USB应用的CRC编解码电路的设计与实现[J].合肥工业大学学报(自然科学版),2005,28(3):292~295。

[2]王新梅,肖国镇.纠错码一原理与方法(M).西安:西安电子科技大学出版社,2001。

[3]雷伏容.清华大学出版社。《VHDL电路设计》。

[4]俞讯,32位CRC校验码的并行算法及硬件实现。信息技术,2007,4:72~74.