16位并行CRC算法的FPGA实现

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.