通用并行CRC计算方法及FPGA实现

仇晓涛

摘要：循环冗余校验（CRC）码是诸多信道编码方式中最常用的一种编码，也是一种检错概率高且容易硬件实现的检错码，因检错能力强、容易实现而得到广泛应用。首先，本文介绍了循环冗余校验的算法原理，分析了CRC校验码的具体运算过程；其次，本文在原算法的基础上提出一种高速并行CRC算法，并以CRC-CCITT为例，推导出8位并行运算的CRC- CCITT逻辑关系式；最后，本文根據推导的8位并行运算的逻辑关系式，描述了8位并行的CRC- CCITT硬件实现电路。将该算法与现有的查找表法的性能进行分析比较发现，该算法具有节省逻辑资源、运行速度快等特点。

关键词：循环冗余校验；生成多项式；并行计算；FPGA

中图分类号：TN911.22  文献标志码：A

0 引言

当数字信号在实际的无线信道通信系统中进行传输时，由于噪声的干扰以及不良信道传输特性的影响，该数字信号不可避免地在接收端产生误码。抗干扰是无线通信信道数据传输中的关键问题之一，可以通过信道编码来解决。在诸多信道编码方法中，循环冗余校验（Cyclic Redundancy Check，CRC）码是一种在数据通信领域中广泛使用的检错码，因检错能力强、容易实现而得到广泛应用［1-3］。CRC码不但可以有效地抗随机干扰，还可以有效地抗突发干扰，因此，在各种通信系统、计算机系统、磁记录以及存储中得到广泛的应用。

1 CRC校验码原理

CRC校验码由一个二进制的多项式产生，若该多项式的最高次幂为k，则可以产生k-1位的冗余码。选取合适的二进制多项式，不但可以使CRC校验码检测出所有奇数位随机误码，还可以检测出突发长度小于等于k-1位的突发误码。

CRC校验码的编码步骤：

设D=（dn-1，dn-2，…，d1，d0）为n位的待校验的二进制数据流，用多项式D（x）表示：

D（x）=dn-1Xn-1+dn-2Xn-2+…+d1X+d0（1）

如果所用生成多项式G（x）的最高次幂为k，在式（1）等号的两侧同时乘以Xk，化简可得出：

XkD（x）=dn-1Xk+n-1+dn-2Xk+n-2+…+d1Xk+1+d0Xk（2）

XkD（x）模2除以G（x），用Q（x）表示商多项式，R（x）表示余数多项式，可得：

XkD（x）+R（x）=Q（x）G（x）（3）

余数多项式R（x）可表示为：

R（x）=rk-1Xk-1+rk-2Xk-2+…+r1X+r0（4）

将式（2）和式（4）代入式（3），得：

Q（x）G（x）=XkD（x）+R（x）=dn-1Xk+n-1+dn-2Xk+n-2+…+d1Xk+1+d0Xk+rk-1Xk-1+rk-2Xk-2+…+r1X+r0（5）

式（5）对应的码组为n+k位，即：

D′=（dn-1，dn-2，…，d1，d0，rk-1，rk-2，…，r1，r0）（6）

由D到D′的计算过程就是CRC的编码步骤，rk-1，rk-2，…，r1，r0为校验位。式（1）～式（6）的计算步骤表明，CRC校验码的编码步骤中的运算需要模2除运算，产生的余数就是CRC码的校验位。同理，接收端将接收到的n+k位信息码除以相同的生成多项式G（x），根据式（3），如果产生的余数为0，则认为接收端接收到的二进制数据流正确无误码；否则就认为接收端接收到的二进制数据流在传输过程中产生了误码。

CRC校验码的通用串行电路如图1所示，其中，符号代表表示模2加运算，表示加权乘法运算。用r0，r1，…，rk-2，rk-1表示k个二进制移位寄存器的状态值，该寄存器的移位由外部同步时钟控制。生成多项式G（x）的系数用gi（i=1，2，…k-1）表示，其取值只有0或者1两个状态，物理意义上0表示无反馈，是断开；1表示有反馈，是闭合。当生成多项式G（x）确定时，可进一步简化图1的电路。本文以CRC-CCITT的生成多项式G（x）=X16+X12+X5+1为例，此时g0=g5=g12=1，相应地简化串行电路，如图2所示。

该CRC-CCITT串行电路只用到了基本的异或门和移位寄存器逻辑单元。如果在高速数字通信系统中采用CRC串行运算，就需要高速串行同步时钟及相应的高速器件，极大地增加了电路的硬件成本以及实现复杂度。该问题通常可以采用并行运算的处理方法解决，因此需要研究一种并行CRC处理电路。

2 并行计算与实现

CRC余数值即各个二进制移位寄存器中的状态值，进行串行运算时，当前的CRC余数值取决于输入的二进制数据流的当前值和前一个状态的二进制移位寄存器中的余数值。如果进行并行运算，以8位二进制数据流并行运算为例，即同时输入8位二进制数据流到并行运算电路所产生的CRC余数与相继输入连续8位二进制数据流到串行运算电路所产生的CRC余数相同，则称这两种电路是等效的。因此，可以推导出CRC的并行运算方法［4］。

图2中二进制移位寄存器的状态值用rij表示，输入的二进制数据流用di（表示第i个输入的二进制数据）表示，其中，i=1，2，…，n，为输入的数据流序号（表示r的第i次变化，其中，n=4，8，16，32，表示数据流的并行度），j=0，1，…，k-1，为移位寄存器的编号（此处k=16），由此可得：

根据表1中的逻辑关系式，可以很容易地实现8位并行的CRC- CCITT硬件运算电路，其硬件实现过程如图3所示。

上述CRC并行运算方法的推导步骤虽然是以8位并行CRC-CCITT运算为例进行的，但该方法具有普遍适用性，即使用该方法可以推导出各种CRC生成多项式的不同并行度（包括16位、32位，甚至是64位）的并行运算逻辑关系式。

3 性能分析

查找表方法既可以用软件实现，也可以用硬件实现。在余数表中存储相应的余数，再通过查找该余数表的方法就可以进行该CRC生成多项式的运算。

分析比较查找表和并行运算两种方法，可以得出如下结论。

本研究提出的CRC并行运算方法无需存储查找表方法中所必需的CRC余数表。该并行运算方法不但可节约硬件电路的成本，还提高了电路的运算速度。在查找表方法中，电路的硬件实现不仅需要FPGA内部资源，还必须使用存储庞大CRC余数表的外部高速存储器件以及FPGA的输入、输出引脚。硬件电路所产生的总时延包括两级异或门时延、寄存器锁存时延、输入输出引脚时延以及读取外部高速存储器件存放数据的时延。由于使用了存储CRC余数表的外部存储器件，硬件电路处理时会产生较大的时延，电路需要使用更高的处理时钟。如果依据本研究提出的直接硬件实现法，以Xilinx FPGA XC7K480T实现CRC-CCITT为例［2］，完全可以使用FPGA的内部逻辑资源来实现，硬件电路所产生的总时延包括两级异或门时延和寄存器锁存时延，产生的时延较小。

本研究提出的CRC实现法可提高并行运算的并行度。在查找表方法中，随着并行度的增加，CRC余数表所需的存储空间会急剧增大，为节省空间，查找表法中的并行度一般被限制在8位以内。例如：当运算并行度为16位数据的CRC校验码时，其余数表长度达到65 536（216）项；当运算并行度为32位数据的CRC校验码时，其余数表长度高达4 294 967 296（232）项，这对FPGA有限的资源来说是不太现实的。假如要进行数据传输率为3.3 Gbps的数据传输，就必须要求电路处理时钟的频率达到1/0.3 ns=3 333 MHz，不仅大多数FPGA无法满足如此高的时钟频率，规模的专用集成电路也很难满足这个要求。对于本研究提出的CRC并行运算方法，当数据的并行度为8位或者更大（如32位，甚至是64位）时，可以有效地降低处理时钟的频率，即使使用普通的CMOS器件也可以实现速率很高的CRC运算，如用Xilinx FPGAXC7K325T可以实现超过3.3 Gbps甚至5.0 Gbps的CRC运算［5］。

4 结语

本研究对CRC运算原理进行了分析，在此基础之上推导和实现了一种通用的并行CRC运算的方法。此种方法可以方便快捷地实现不同数据并行度的各种生成多项式的CRC运算，运用硬件来实现该算法也相对容易，尤其是对于需要提高并行度（大于8）的高速通信系统的CRC运算。与查找表法相比较，该方法具有优越性和现实性。

參考文献

［1］王新梅，肖国镇.纠错码原理与方法［M］，西安：西安电子科技大学出版社，2001.

［2］李云松，宋锐，雷杰，等.Xilinx FPGA设计基础［M］.西安：西安电子科技大学版社，2008.

［3］樊昌信.通信原理［M］.北京：国防工业出版社，2001.

［4］张树刚，张遂南，黄士坦.CRC校验码并行计算的FPGA实现［J］.计算机技术与发展，2007（2）：56-58，62.

［5］俞讯.32位CRC校验码的并行算法及硬件实现［J］.信息技术，2007（4）：71-74.

（编辑 王永超）

General parallel CRC computing method and implementation based on FPGA

Qiu  Xiaotao

（CEC Defense Technology Company Limited， Nanjing 210000， China）

Abstract：  Cyclic redundancy check （CRC） code is one of the most commonly used code in channel codes. It is an error detection code with high detection probability and easy hardware implementation. It is widely used for its simple implementation and strong error detection ability. Firstly， this paper introduces the algorithm principle of cyclic redundancy check， and analyzes the specific calculation process of CRC. Secondly， this paper proposes a high-speed parallel CRC algorithm， and takes CRC-CCITT as an example to derive the CRC-CCITT logic relation of 8-bit parallel computing. Finally， according to the deduced logic relation of 8-bit parallel computing， the hardware implementation circuit of 8-bit parallel CRC-CCITT is given. Compared with the existing lookup table methods， the algorithm has the characteristics of saving logical resources and high speed.

Key words： cyclic redundancy check; generator polynomial; parallel computing; FPGA