基于FPGA全参数化CRC的推导及实现

阚佳冲等

摘 要： 提出一种新型的全参数化CRC算法。详细地介绍全参数化CRC的算法原理，并给出算法公式的推理过程及结果，通过Verilog语言设计实现，给出了基于FPGA平台的仿真波形图，并成功应用于工程项目当中，最后详细分析了全参数化CRC算法在实现过程中的优势。这里提出的全参数化CRC算法，可以通过参数化配置，实现CRC?4、CRC?8、CRC?12等任何CRC?X的运算，亦可以实现任何数据位宽（数据位宽小于等于CRC校验码位宽）、任意生成多项式的CRC运算。

关键词： 全参数化； CRC算法； Verilog； FPGA； 以太网

中图分类号： TN919?34 文献标识码： A 文章编号： 1004?373X（2015）08?0154?05

0 引 言

在现行的数字通信系统中要进行稳定可靠并且快速的通信，同时又要保证数据在传输过程的准确性，这就需要对通信过程添加差错控制机制[1]。

循环冗余校验码（Cyclic Redundancy Check，CRC）是数据通信领域中比较常应用到的一种差错校验码，它的明显特征就是整个数据包文的信息位和校验码位的位宽可以任意改变。但是现行的CRC校验技术都是针对某一特定领域，或者指定生成多项式，校验码位宽等，具有很大的约束性。如果进行不同CRC校验时就需要重新设计模块，浪费时间精力的同时，多个校验模块又浪费了宝贵的FPGA逻辑资源，同时传统串行CRC算法效率低，很难满足视频信号实时处理的要求[2]。本文即以这个问题为突破口，设计出一个可以在各个领域通用的CRC校验机制。本设计在传统CRC的FPGA串行编码[3]的基础上，通过分析、整理、归纳最终得到适用于不同领域，不同校验码位宽，不同数据位宽，不同生成多项式的CRC运算通用算法，该通用CRC校验算法大大地减少了资源的利用率，仅仅用到极少数目的寄存器，同时又没有借助任何ROM去存储数据，结论证实全参数化的CRC校验算法能够跑到较高的时钟频率。设计通过Verilog进行硬件描述[4]，在基于FPGA平台实现了指定CRC校验功能，并成功应用于工程项目当中。

1 全参数化CRC算法原理

在现有的数字通信系统中CRC校验分为两个部分，即发送方和接收方[5]。发送方用于对接收到的指定位宽包文数据（数据位）进行CRC运算得到指定位宽的CRC校验码；接收方用于对接收到的新包文数据（数据位和校验码位）进行同样的CRC运算，如果结果为0，则代表CRC校验通过，否则不通过。在本设计中通过参数化设计很好地将发送方和接收方的CRC运算逻辑结合到了一个模块当中，即CRC运算模块如图1所示。

1.1 CRC运算串行编码

以g（x）=X8+X6+X5+X3+X+1为例，串行CRC运算的实现如图2所示。编码前要先将电路中的寄存器初始化，然后将串行数据依次从input端输入图2电路，当所有串行数据输入完毕，每个寄存器的最终值即为CRC校验码[3]。

（1） 全参数化CRC的初始值。CRC校验的应用非常广泛，不同领域CRC计算的初始值是不相同的，例如以太网领域，初始值为全1，而在其他领域，初始值为全0或其他值。本文设计的全参数化CRC为了适应这种应用需求，在模块中定义一个参数INIT_VALUE，这样就可以在复位或重新运算时，直接加载INIT_VALUE即可。

（2） 全参数化CRC的生成多项式。多项式g（x）的项系数直接影响数据异或的位置（去除最高次项）。例如g（x）=X8+X6+X5+X3+X+1中，在X6，X5，X3，X、1（X0），项系数为1的项前加上异或，就得到了图2对应的电路。

因此不失一般性，可以假设生成多项式为：

g（x）=X8+P7X7+P6X6+P5X5+P4X4+P3X3+P2X2+P1X+P01

式中：P7～P0表示生成多项式各项前面的系数（最高次项和最低次项固定为1，故P0=1），其对应的电路结构如图3所示。当生成多项式项系数为1时即相应位的P=1，表示当前输入要与前一个寄存器的输出相异或，得到下一时刻的CRC值，例如图2中X6项系数为1即P6=1，而X4的项系数为0即P4=0。

经过对比图2和图3电路，会发现如果去掉图3电路相应位置的异或门（圈内部分）即可变换成图2生成多项式的电路。因此，本设计通过控制P值，进而控制图3中相应位置异或门有无，最终使算法达到覆盖任意形式的生成多项式。

1.2 全参数化CRC并行编码

为了提高CRC校验速度，现将由单比特输入改为多比特同时输入，此时的CRC校验机制和串行编码相同，因此，可由CRC串行编码推导出最终的并行编码，步骤如下：

1.2.1 k（x）公式推导

假设图3中与数据输入input相连异或门的输出设为k（x），其中x表示连续输入的单比特数据，文中用d（x）表示。则由图3可得到R7～R0各个寄存器次态的表达式如表1所示。

如果要将输入的串行1比特数据改为4 b数据，首先要根据串行单比特数据编码的思想，得到当d0，d1，d2，d3到

来时相应的k（x）的值，如表2所示，其 中C7～C0表示所有寄存器的当前值。

根据表2进行推导，可以得到当输入x比特数据后k（x）表达式为：

k（x）=dx^C（n-x-1）^[（P（i-x）&k0^…^（P（i-1）&k（x-1））]

进一步整理得：

[kx=dx^C（n-x-1）^a=0x-1 Pn-a-1k（x-a-1）， n>x>0d0 ^ C（n-1）， x=0]

式中n表示CRC校验码的位宽。

1.2.2 Ri（x）公式推导

假设Ri（x）表示每个寄存器最终值，根据类似的推导方法，利用表1的公式，在表2的基础上进行计算推导，根据串行编码的原理，当d0，d1，d2，d3到来时，每个寄存器都会刷新一次输出值，如表3所示，其中i表示模块当前寄存器标号，C7～C0表示i个寄存器的当前值。

推导过程和第1.2.1节所述一致，表3中表示当前输入第4 b数据的结果，以此为基础进一步推导出第x位数据输入后，寄存器最终值的表达式。

整理得到最终的Ri（x）的通用表达式：

[Rix= C（i-x-1）^b=0xPi-bk（x-b）， x

为了实现本设计的全参数化CRC，模块需要定义相关参数。其中输入数据的位宽可通过参数DAT_W来设置；所有寄存器的初始值，可通过参数INIT_VALUE来设置；CRC校验码的位宽则可通过控制寄存器的个数来进行设置，即改变参数CRC_W，P表示生成码的低CRC_W位，可通过参数CRC_POLY来设置。这样就实现了兼容不同领域，不同CRC校验码位宽，不同生成多项式，不同输入数据位宽的全参数化CRC运算算法。

2 全参数化CRC算法实现

在Verilog 2001里，新增加了generate语句，同时又拓展了generate用法。除了允许复制产生primitive和module的多个实例化，同时也可以复制产生多个reg、parameter、assign、always、initial等。因此通过generate去实现这两个公式是个不错的选择。

根据上述推导出的公式，运用硬件描述语言Verilog中的generate将表达式k（x），Ri（x）表达式转换成Verilog代码，下面是generate生成公式的部分程序，见图4。

图5为CRC运算的仿真波形，按照上节所述进行参数设置：输入数据位宽DAT_W=8，CRC校验码位宽CRC_W=8，其中选定运算的生成多项式为g（x）=X8+X7+X4+X3+X+1，则参数CRC_POLY=10011011，最后设置INIT_VALUE=0。

图5中当输入有效数据data后，crc_out就会输出指定位宽的CRC校验码，testbench设置的第一个输入数据为10101101，本地时钟打一拍后即可得到CRC校验码00000111，并且仿真结果与Matlab中的数据结果完全一致，全参数化CRC运算机制的快速、准确一目了然。但这只是完成了全参数化CRC运算模块的一部分内容，即生成校验码，下面实现用生成好的校验码和原始数据实现CRC校验查错，CRC校验仿真结果如图6所示，输入的数据（信息位）与图5中的相同，但是在进行CRC校验的时候要在8位数据的后面加上8位校验码，也就是此时的输入数据有16位，其他几个参数仍保持不变。由于图5的数据只有8位，所以为了便于观察比较在进行一次CRC运算后都进行了初始化，但是在进行图5操作的时候就要等待数据完全输入后才进行初始化。

如图6所示，仿真波形图显示当数据位和校验码位输入完毕后，输出crc_out为0，可以很直观的看到全参数CRC校验机制快速准确地实现了CRC校验功能。

3 全参数化CRC算法应用

为了更好说明全参数化CRC校验的优势，文中列举出FPGA利用以太网帧数据传输以及与上位机通信过程当中的具体应用。

3.1 以太网FCS

以太网帧格式包括前导码（7 B）、帧起始定界符（1 B）、目的MAC地址（6 B）、源MAC地址（6 B）、类型/长度（2 B）、数据（46～1 500 B）、帧校验序列FCS（4 B）。在项目中将OV7670摄像头采集的图像数据经过SDRAM缓存后[6]，读出摄像头图像数据并输入到CRC运算模块，经过CRC运算模块后图像数据加上了用于以太网传输的FCS字段（32位CRC校验码），之后经由以太网传输给网络其他主机。流程如图7所示。

在系统顶层文件中参数例化CRC运算模块，根据以太网FCS[7]帧格式的要求，具体参数定义为：DAT_W=32，CRC_W=32，CRC_POLY=32h04811D37，INIT_VALUE=32′hFFFFFFFF。

3.2 串行通信CRC?16校验

系统与上位机进行通信时，同样也会由于各种各样的干扰和噪声的影响，导致接收到不正确的数据，因此系统设计时，在FPGA与上位机通信的时候也采取了CRC校验机制，系统采用了常用的16位CRC校验方式来实现上位PC机通讯系统中的差错校验。

同样也在系统顶层文件中参数例化CRC运算模块，根据串行通信要求，具体参数定义为：DAT_W=16，CRC_W=16，CRC_POLY=16′h8005，INIT_VALUE=16′h0000。

系统中例化全参数化CRC模块后，相关统计信息如表5所示。

经过对工程系统的测试分析，与传统的CRC校验机制相比，全参数化的CRC算法，可以大大地提高校验速率。例如上述系统中的CRC?16，CRC?32的时钟都能达到372 MHz，用到了极少的寄存器资源的同时，又缩短了CRC校验的时间，并且又适用于多种不同CRC校验工作。

整个工程中用到多种CRC校验机制，只是简单通过例化出不同参数的CRC运算模块即可，方便快捷的解决了校验问题。

全参数CRC校验与传统CRC校验查表法和串行编码校验[8]的对比如表6所示。

4 结 语

本文设计算法具有通用性，可以广泛应用于数据通信领域，设计得出的适用于不同领域满足不同需要的全参数化CRC算法，不仅运算速度快，而且节省资源。通过Verilog语言描述实现，且很好地应用在基于FPGA平台的工程实践当中。因此本设计提出的全参数化CRC运算通用表达式，能够满足现行通信系统的准确性，快速性，节约性等的要求。随着大信息时代的来临，无论什么领域对于数据传输都有很严格的要求，但苦于没有一个能够兼容多领域且可以个性化设置的CRC校验机制，本设计可以很好地解决这个问题，实现预想的CRC数据校验功能。

参考文献

[1] 李继东，王博，袁晨光.在通信过程中用C语言实现CRC校验[J].内燃机与动力装置，2009（z1）：43?46.

[2] 张友，郑世军.一种PSI滤波器设计中的并行CRC算法[J].电视技术，2005（3）：28?29.

[3] 石全峰，徐东明，谢庆胜，等.CRC算法在以太网数据帧中的应用及其硬件实现[J].广东通信技术，2010（3）：32?36.

[4] 夏宇闻.Verilog数字系统设计教程[M].北京：北京航空航天大学出版社，2009.

[5] 吕晓敏.嵌套循环冗余码（CRC）的优化与检验[D].杭州：浙江大学，2012.

[6] 杨月娥.基于FPGA的视频帧同步机的设计[J].电视技术，2009（9）：30?32.

[7] 顾文斌，王怡，马莉.基于FPGA的CRC算法的实现[J].计算机与现代化，2008（5）：111?113.

[8] 季鹏辉.基于FPGA的16bitCRC校验查表法设计[J].电子器件，2013，8（4）：581?583.