摘要：CRC（循环冗余校验）算法广泛应用于通信领域，以提高数据传输的准确性。本文针对FPGA应用特点，介绍了一种适合于FPGA实现的CRC 并行计算的设计方法，减少了系统的应用开销，实现更高的工作效率。
关键词：FPGA；CRC；VHDL；HDLC；LFSR
引言
RC 误码检测能力强，抗干扰性能优异，在众多信道编码中得到了广泛应用，目前越来越多的通信设计使用FPGA/CPLD等可编程硬件来实现，使用软件方法进行CRC校验实时性差，不利于系统对错误数据进行及时处理。利用通信硬件实时的对信道数据进行误码检测，大大的改善了信道检测的时效性。传统的CRC多使用串行方式进行计算，整体速度较慢，结合fpga大量可用资源的特点，并行CRC算法得到了越来越多的应用。
本文介绍了一种快速crc算法的实现方法，并已在实际通信中得以验证。
1 CRC介绍
CRC校验的基本思想是利用线性编码理论，串行传送的信息 M（ x）=（m n - 1，m n - 2，m 1，m 0）是一串 n位二进制序列，将信息码用多项式 M（ x）表示：M（ x）=m n - 1 Xn - 1 +m n - 2 Xn - 2 +… +m 1 X +m 0在它被发送的同时，被一个先选择的生成多项式g（x）相除，生成多项式长 r +1位，相除后得到 r位的余数就是校验位，它拼接到原 n位有效信息后面，即形成 CRC 码．CRC 码到达接受方时，接受方的设备一方面接受 CRC 码，一方面用同样的方法与“ 生成多项式”相除，如果正好除尽，表示无信息差错，接受方去掉 CRC 码后面的 r 位校验，收下 k 位有效信息；如果不能除尽时，说明有信息的状态位发生了转变。即出错了，一般要求重新传送一次或者立即纠错。
根据不同的应用，crc有多种生成多项式：
CRC - 16：x16 + x15 + x2 + 1 IBM SDLC
CRC - CCITT：x16 + x12 + x5 + 1 ISO HDLC，ITU X.25.
CRC - 32：3x2+ x26 + x23 + x22 + x16 + x12 + x10 +x8+ x7 + x5 + x4 + x2 + 1 ZIP，RAR，IEEE802LAN /FDDI
2 CRC并行算法分析
（1）CRC计算使用模2运算方法，模2运算与二进制四则运算法则相同，但不考虑借位和进位，及两个位上数字相同为0，不同为1.因此，模2运算本质上可以用异或来实现。
（2）传统的串行CRC计算方法
通常用一个线性反馈移位寄存器（LFSR）来实现CRC的计算。
图1 LFSR
其中 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）
VARIABLE data_temp1：STD_LOGIC_VECTOR（8 DOWNTO 1）；-------- 内部数据暂存器1
VARIABLE crcreg：STD_LOGIC_VECTOR（15 DOWNTO 0）；--------- 校验结果暂存器
VARIABLE C_para：STD_LOGIC_VECTOR（15 DOWNTO 0）：= "1111111111111111"；------------------- 校验初始参数
BEGIN
IF（rst = '0'）THEN
crcreg（15 DOWNTO 0）：= "1111111111111111"； ---------------------------- 初始化校验结果暂存器
rx_crc_buf（15 DOWNTO 0） <= X"FFFF"；
ELSIF（rx_clk'event AND rx_clk ='1'）THEN
data_temp1（8 DOWNTO 1）：= data_buf（7 DOWNTO 0）；----------------- 将需要校验的数据放到缓存区
crcreg（0）：= C_para（8） XOR C_para（12） XOR data_temp1（4） XOR data_temp1（8）；
crcreg（1）：= C_para（9） XOR C_para（13） XOR data_temp1（3） XOR data_temp1（7）；
crcreg（2）：= C_para（10） XOR C_para（14） XOR data_temp1（2） XOR data_temp1（6）；
crcreg（3）：= C_para（11） XOR C_para（15） XOR data_temp1（1） XOR data_temp1（5）；
crcreg（4）：= C_para（12） XOR data_temp1（4）；
crcreg（5）：= C_para（8） XOR C_para（12） XOR C_para（13） XOR data_temp1（3）XOR data_temp1（4）XOR data_temp1（8）；
crcreg（6）：= C_para（9） XOR C_para（13） XOR C_para（14） XOR data_temp1（2）XOR data_temp1（3）；
crcreg（7）：= C_para（10）XOR C_para（14） XOR C_para（15） XOR data_temp1（1）XOR data_temp1（2）XOR data_temp1（6）；
crcreg（8）：= C_para（0） XOR C_para（11） XOR C_para（15） XOR data_temp1（1）XOR data_temp1（5）；
crcreg（9）：= C_para（1） XOR C_para（12） XOR data_temp1（4）；
crcreg（10）：= C_para（2） XOR C_para（13） XOR data_temp1（3）；
crcreg（11）：= C_para（3） XOR C_para（14） XOR data_temp1（2）；
crcreg（12）：= C_para（4） XOR C_para（8） XOR C_para（12）XOR C_para（15） XOR data_temp1（1）XOR data_temp1（4）XOR data_temp1（8）；
crcreg（13）：= C_para（5） XOR C_para（9） XOR C_para（13）XOR data_temp1（3）XOR data_temp1（7）；
crcreg（14）：= C_para（6） XOR C_para（10）XOR C_para（14）XOR data_temp1（2）XOR data_temp1（6）；
crcreg（15）：= C_para（7） XOR C_para（11）XOR C_para（15）XOR data_temp1（1）XOR data_temp1（5）；
C_para（15 DOWNTO 0）：= crcreg（15 DOWNTO 0）；------ 将校验结果作为下次校验的参数
rx_crc_buf（15 DOWNTO 0） <= crcreg（15 DOWNTO 0）；-- 将校验结果存在CRC校验结果寄存器中
END IF；
接收端可采用相同的计算代码来进行接受信号的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.
论文作者:张忠琪
论文发表刊物:《电力设备》2017年第7期
论文发表时间:2017/7/4
标签：多项式论文; 数据论文; 算法论文; 信息论文; 寄存器论文; 方法论文; 通信论文; 《电力设备》2017年第7期论文;