一种位宽可变的CRC校验算法及硬件实现*

朱正鹏 朱旭锋 李 宾 刘益华 王 超

北京航天自动控制研究所，北京100854

为保证箭上设备数据传输可靠性，箭载计算机设备普遍采用CRC进行数据校验。箭上各设备在收到消息字后需要首先进行CRC校验，校验正确即认为消息正确，然后根据消息中的指令数据控制相应设备输出，箭上计算机通信系统框图如图1所示。

图1 箭上计算机通信系统框图

传统的CRC校验算法是利用C语言在箭上设备DSP或者单片机等CPU处理器芯片上实现，随着可编程逻辑器件性能逐渐强大，很多箭上计算机设备不再配置处理器芯片，而采用硬件描述语言(HDL)在FPGA上实现实时的CRC校验算法。具体实现方式为通过各种通信接口(RS422、1553B、RS485和以太网)接收的数据在FPGA内完成CRC实时校验后将数据送到数据处理模块。

目前普遍使用的基于FPGA的CRC校验算法有传统串行计算法、查表法和并行计算公式推导法等。传统串行计算法只能处理固定位宽数据流，无法适应箭载计算机多种通信接口的需求。查表法优点在于易于实现，但是硬件资源耗费巨大，不满足箭上设备资源有限的要求[1-2]。而并行计算公式法虽然处理速度快，但也只能处理固定位宽数据。以上算法若要满足箭上快速可变位宽数据处理的要求，需要设置多个硬件模块，可移植性差，还会增加箭上设备功耗及硬件实现难度。

为适应新一代运载火箭箭上计算机设备的CRC校验需求，开发一种位宽可变的串行CRC校验算法，以少量硬件资源实现可变位宽输入数据的快速CRC编码，保证数据的快速实时处理以及传输可靠性，且模块化的设计思路利于程序的重复利用和不同箭上计算机设备硬件平台的移植。

1 算法原理及实现方案

1.1 CRC校验基本原理

CRC校验的基本原理是基于串行数据传输的长除法，即将要发送的信息左移若干位，然后与生成多项式进行模2除法，即按位进行异或计算，得到的余数即为CRC校验信息。[3]

将所传送的数据用多项式M(x)表示，其信息长度为n位的二进制，用数学方法表达多项式如式(1)：

M(x)=mn-1xn-1+mn-2xn-2+…+m1x1+m0

(1)

根据要校验的数据长度假定CRC码长度为k位，则生成多项式的阶数为k，用多项式表示如式(2)：

G(x)=gkxk+gk-1xk-1+…+g1x1+g0

(2)

将式(1)的数据序列和式(2)的生成多项式进行如式(3)的计算：

(3)

上式中得到的R(x)即为CRC码，将其附加在原始数据流M(x)后一起发出，则发送端发送的数据T(x)为：M(x)×xk+R(x)。

接收端对数据CRC的校验就是将接收的数据和CRC多项式进行模2除，用多项式表达如式(4)：

(4)

将式(3)代入式(4)得到：

(5)

相同数据流按位异或结果为0，因此式(5)简化为：

(6)

如果接收码流没有出现误码，接收码应当等于上式中发送码T(x)，此时接收码可以被生成多项式G(x)整除。反之，若无法整除，则在传输中发生误码。另外在信息传输中还有一种校验方法，CRC码直接被用于监测通信过程中的误码。传输数据期间，发送端计算每个数据块的CRC，数据块发送完毕后，CRC校验码也发送出去。接收端用同样的生成多项式处理接收到的数据块，若接收的数据无误，则接收端计算得到的CRC码应当和发送端的CRC码一致。

1.2 CRC校验算法硬件实现方法及比较

传统箭载计算机设备主要采用CPU芯片执行C语言软件算法来完成箭上总线通信过程中的CRC校验。本文研究重点是如何使CRC校验从CPU功能模块中剥离出来，可以独立运行于可编程逻辑器件上，并且不同的箭载计算机设备可以通过该算法模块预留的配置接口计算不同位宽消息字的CRC校验结果。

CRC硬件校验方法有传统串行计算法、查表法和并行计算法3种实现方式。本文依据新一代运载火箭箭上计算机设备需求，基于传统的串行计算法提出一种位宽可变的串行CRC校验算法，下面对这几种实现方法进行分析比较。

1.2.1 传统串行计算法

传统串行计算法是根据CRC码多项式定义，采取除法硬件电路实现，按照一组线性反馈移位寄存器和模2加单元完成硬件除法功能。对于固定位宽的待校验数据，传统串行计算法是按位产生CRC，也就是通过一个线性反馈一位寄存器(LFSR)按每次输入一位的方式产生CRC。该方法原理清晰、实现简单，但是每个时钟周期仅能处理1bit数据，速度较慢，且只能处理固定位宽数据流，可移植性差。

以CRC-CCCITT为例，使用多项式x16+x12+x5+1(简记为0x11021)的串行电路如图2所示，图中G[0]=G[5]=G[12]=1[4-5]。

图2 串行计算法硬件回路

1.2.2 按字节处理的查表法

利用查表法计算CRC时，让数据字节与累加器中的高位字节“异或”，得到组合值(该组合值CRC值已建立并存在表中)，组合值再与累加器中的低位字节“异或”。由于移位操作少，因此在用查表法计算时，速度比串行计算法快4～10倍。查表法是目前使用较多的一种CRC校验实现方式，代码量少，但是需要硬件提供一个较大的查找表(LUT，Look-Up Table)。当以8位的传送信息字节与16位累加器高8位异或时，累加器中的新值为异或后的组合值加上未改变的低8位值，因此只有28=256种可能组合值，可以事先计算好组合值并存入查找表中。

1.2.3 多比特并行计算法

并行计算法可以根据生成多项式的反馈特性，将串行的比特反馈等效成并行计算等式。由图2可以看出，各移位寄存器的存数即为CRC余数值，当进行串行CRC运算时，当前的CRC余数值仅与当前信息码的最前一位输入值和前一状态的CRC余数值相关。因此，在进行多比特并行CRC运算时，多比特信息码一次输入并行运算电路产生的CRC值应当和多比特信息码一次输入串行运算电路产生的CRC值相同。基于该思想，文献[3-4]将串行计算法改为并行计算法，并给出并行数据的CRC-CCITT编码电路结构图(图3)。

图3 并行计算编码电路结构图

图3中，R0～R15作为存放余数的寄存器，输入待校验的数据位N位并行数据D(N-1 downto 0)。并行数据通过一个并行运算电路和余数寄存器中的数据进行运算，得到的结果依然保存在余数寄存器中。每个时钟周期完成N位的CRC运算并将结果保存在CRC(N-1 downto 0)中，在下一个时钟对后续并行数据继续运算。对应不同的输入数据位宽N，并行计算法的推导公式是不一样的，需要根据输入数据位宽改变推导算法。

1.2.4 位宽可变的串行计算法

从图2传统的串行计算法硬件电路的实现不难看出，电路的主要结构是寄存器和异或门。而针对不同位宽的待校验数据的主要差别在于寄存器个数、初始化值、异或门输入位及最后待校验值的处理上。如果每种位宽的数据都按传统计算实现，虽然功能没有问题，但从硬件资源上造成一定程度的浪费。

本文提出的位宽可变的串行计算法将不同位宽的校验编码进行一体化设计，控制通道由moor状态机实现，控制不同位宽的编码校验操作。如图4流程图所示，硬件模拟算法如下：

a)首先在要传输的数据块之后补2个字节的零；

b)设置一个CRC寄存器，并赋初值为0；

c)将数据块第一个8位字符与16位CRC寄存器低8位进行异或，并将结果存入CRC寄存器；

d)将CRC寄存器右移一位，并给最高位补0，移出并检查最低位的值；

e)若最低位值为0，则重复d步骤；若为1，CRC寄存器与多项式码进行异或；

f)重复d步和e步直到8次移位全部完成，此时一个8位数据处理完毕；

g)重复c到f直到所有数据全部处理完成；

h)CRC寄存器最终的内容即为CRC值。

图4 位宽可变的串行计算法流程图

1.2.5 实现方法比较

如表1所示，对于硬件实现来说，查表法需要占用芯片面积构造一个ROM实现的表，在硬件资源紧张的情况下，CRC计算可以有2种方式:1)本文提出的位宽可变的串行方式；2)并行公式推导计算的方式。位宽可变的串行计算算法结构规则，程序模块可移植性强，硬件资源耗费少，可靠性高，缺点是每个时钟周期只能计算1位的结果，速度较慢，适用于数据位宽多变的通讯模式。并行方式是每次输入一组并行数据，同时产生出CRC结果。并行方式处理速度较快，但是需要根据数据位宽改变算法，适合用于传输固定位宽数据的高速通讯模式。

表1 实现方法比较

*注：T表示FPGA本地时钟周期。

2 数据位宽可变的CRC编码的HDL实现

根据1.2.4节所述位宽可变的串行计算法实现方案，模块设计利用VHDL语言进行硬件描述，标识符为crc16_dataN.vhd，并通过ModelSim SE PLUS 6.5a进行仿真。

如图5所示，模块使用5个状态的状态机完成一次计算过程：IDLE_ST，START_CAL_ST，CHECK_BIT_ST，XOR_ST和DONE_ST。

图5 状态机流程图

IDLE_ST：crc_r赋值为全’0’。跳转条件：当data_valid为’1’，跳转到START_CAL_ST。

START_CAL_ST：data_tmp赋值为data_latch & x"0000"，crc_tmp高17位赋值为生成多项式，低位全补’0’，MSB赋值为N+15。跳转条件：直接跳转到CHECK_BIT_ST。

CHECK_BIT_ST：如果MSB>15 并 data_tmp(MSB)=’0’,则将MSB减1，并把crc_tmp右移1位，高位补’0’。跳转条件：如果MSB小于或等于15，跳转到DONE_ST；如果MSB>15并且data_tmp(MSB) =’1’，跳转到XOR_ST。

XOR_ST：data_tmp与crc_tmp异或并存入data_tmp；crc_tmp右移，高位补’0’；MSB减1。跳转条件：直接跳转到CHECK_BIT_ST。

DONE_ST：crc_valid置’1’,crc_r赋值为data_tmp的低16位。跳转条件：完成了一次计算，跳转到IDLE_ST。

2.1 实现说明

模块的管脚特性及信号说明如表2所示，表中data信号的位宽N为外部用户可配置参数，该参数为需要进行CRC校验数据的位宽，N必须为8的倍数，类型为整数。

表2 模块信号说明表

表3列出模块实现所需的内部寄存器，N为外部输入信号data的位宽。当data_valid=’1’时，data_latch将输入的data锁存。本模块CRC生成多项式用"10001000000100001"来表示。

表3 模块内部寄存器说明表

2.2 仿真验证

根据模块接口特性编写TestBench仿真文件，利用ModelSim对模块进行仿真验证。仿真思路为：分别选取16bit、32bit和64bit随机数据作为待编码数据，工作频率选为25MHz，验证所编写的IP核的有效性和参数可扩展性。如图6所示，当输入16bit并行数据x"ABFE"时，输出CRC码为x"344F"；如图7所示，当输入32bit并行数据x"FFFFABFE"时，输出CRC码为x"6D75"；如图8所示，当输入64bit并行数据x"00000000FFFFFFFF"时，输出CRC码为x"3F2E"。

3 结果分析

设计采用VHDL硬件描述语言实现，可以很好地应用于各类FPGA平台的工程实践上。如表4所示，分别用Xilinx的XQV600系列芯片、Actel的A3P1000系列芯片、Altera的EP2C35系列芯片对该模块进行硬件实现，资源耗费统计结果与器件型号及综合使用的工具有很大的关系。

图6 CRC码为x"344F"

图7 CRC码为x"6D75"

图8 CRC码为x"3F2E"

表4 不同FPGA平台资源耗费统计

4 结论

分析了CRC计算原理的基础上，用VHDL硬件语言实现一种输入数据位宽可变的CRC校验算法。该方法较其他实现方式具有可配置、可靠性高及占用资源少的优点，方便在各类FPGA平台上实现。目前该算法模块已应用于我国新一代运载火箭箭上计算机系统，并在多次正式飞行试验中得到成功应用及验证。