线性反馈移位寄存器（LFSR）是一种使用特定的逻辑运算（通常是XOR）给出前一个状态的输出，然后将此输出作为反馈作为下一个状态的输入的移位寄存器。
在LFSR中，有一个“抽头”的概念，就是通过逻辑运算影响下一次移位输出的寄存器。抽头可以用一个模2的特征多项式来表示[4]，即特征多项式中所有系数必须为1或0。
例如，图1中，抽头序列为[8, 2, 1]，其特征多项式可以表示为如式（4）所示。
（4）
在特征多项式中，常数“1”并不代表抽头位，它代表输入位，最高位一般代表输出位。
3 设计思路与解决方案
3.1 传统的CRC计算方法
流行的CRC计算方法有两种：串行LFSR计算和查表法。
（1）第一种方法是必须将数据逐个串行输入，然后通过LFSR设置以实现所需的抽头。这种方法实现起来比较简单，只需要确定要使用的LFSR。但计算时间相对较长，一个时钟周期只能计算一位输出数据。
（2）第二种方法是查表法，就是事先把输出和输入的每一位的对应关系整理成一张表，计算的时候直接把输入的数据填进去，只需要一个周期就可以计算出所有的输出，但是这种方法也有缺陷，输入的数据长度必须给定，不能改变。例如AHB总线（Advanced High Performance Bus）是ARM的AMBA系列的高速总线，主要用于高速设备。
AHB总线为AMBA[5]，HSIZE[2:0]信号设置为010（即总线宽度为32位）[3]。因此，此方法每次只能计算最多32位数据。如果改变总线宽度，例如HSIZE[2:0]设置为011（总线宽度64位），则必须重新整理输入输出关系表，相当于重写一个新的模块，繁琐且无法重复使用。
本文设计的CRC计算模块结合了第一种和第二种方法并进行了改进，可以在一个周期内得到输出结果，并且支持任意长度的输入数据。
3.2 利用LFSR实现串行CRC计算
以CRC-8为例，CRC-8的串行CRC计算模块实现流程图如图2所示。
用一个二进制数来表示这个生成多项式。根据CRC的性质，由于最高位×8的系数必定为1，所以用二进制数表示生成多项式时，可以省去×8，因此生成多项式用二进制数表示为：g = 00000111。定义反馈因子feedback = c[7]⊕din，分别对应抽头×8和×0。从图中可知c[0] = feedback。对于抽头×2和×1，可得c[2] = feedback⊕c[1]，c[1] = feedback⊕c[0]。LFSR的其余非抽头位均满足c[i+1] = c[i]。观察到，除了×0以外，其余位（包括抽头和非抽头位）都含有异或的公共因子c[i-1]，而是否含有异或因子feedback可以通过g[i]与feedback进行与运算得到。 至此，我们可以得到串行CRC8的计算通式如公式5[5]所示。
（5）
接下来我们从CRC-8推广到CRC-N。对于CRC-N，根据CRC生成多项式的性质，抽头必定包含×n和×0，因此反馈因子feedback＝c[n]⊕din，对于×0抽头，满足c[0]＝feedback，对于其余抽头，满足c[i]＝feedback⊕c[i-1]（n＞0），对于无抽头的抽头，满足c[i]＝c[i-1]，因此是否包含异或因子feedback可以通过feedback与c[i-1]进行AND操作得到。
综上所述，CRC-N的计算一般公式如公式6所示。
（6）
3.3 实现并行CRC计算
上面实现的串行CRC计算模块crc_comb用于实现任意输入数据宽度、任意CRC版本的并行计算模块。假设输入数据长度为frame_size，则必须调用串行CRC模块计算frame_size次，并在第0次计算时给出输入的初值crc_init，将第i次计算的结果作为第i+1次计算（0＜i＜frame_size）的crc_in，这样才能得到最终的CRC计算结果。因此串行CRC模块需要实例化frame_size次。在Verilog-2001中增加了可合成的generate语句，可以多次实例化。
图3为并行CRC计算模块实现流程图，该模块可以实现任意输入数据长度、任意模式的并行CRC计算。其中crc_comb_out[i]为crc_comb模块第i次实例化计算出的CRC值。
4 仿真结果
图4显示了仿真结果。为了证明设计的模块支持不同版本的CRC计算，该模块被实例化四次，给出了不同的g_x值。这里使用第1节中提到的典型g_x值。
输入数据0x27。从图中可以看出CRC-8、CRC-12、CRC-16、CRC-CCITT的计算结果分别为0x15、0x176、0x00d2、0x5485。将数据输入格氏CRC计算器，得到图5所示的计算结果（限于篇幅，仅截取某一种CRC-8的计算结果，实际操作中进行了多次不同模式的CRC计算，结果与仿真结果一致）。从图中可以看出计算结果为0xF5，与仿真结果一致，因此CRC计算模块功能正确。
5 结论
本文通过模拟查表法和直接运算法，通过Verilog实现了一种新的CRC运算方法，可以在一个周期内实现CRC运算。但会存在组合逻辑过长影响电路运算速度的问题，实际应用中可根据具体情况插入流水线，提高运算速度。
参考
[1]夏忠海,任永锋,贾兴忠,郭嘉鑫.基于FPGA的CRC查表法设计及优化[J].电测与仪表,2017,54(03):54-59+88.
[2] 冯玉春, 张如琴. 利用ARM微控制器快速实现ModBus协议中CRC校验[J]. 单片机与嵌入式系统应用, 2016, 16(05): 49-52.
[3]Conti M,Caldari M,Vece GB等.AMBA AHB总线不同仲裁算法的性能分析[C].设计自动化会议,2004.
[4]郝宏伟.基于FPGA的跳跃式线性反馈移位寄存器在伪随机序列算法中的应用[J].控制与信息技术,2018(02):56-60.
[5] 李昂, 李旭, 关杰. 基于猜测的太乙序列密码算法攻击[J]. 信息工程大学学报, 2017, 18(06): 749-753.
===========================
《集成电路应用》国内统一期刊号CN 31-1325/TN，国际标准期刊号ISSN 1674-2583，是国家新闻出版广电总局首批批准的中文一级学术期刊，首发于CNKI，来源有CNKI、维普、万方数据、CSCD等数据库，是我国集成电路行业唯一经国家批准的学术月刊。《中国科技期刊（扩大版）》影响因子为0.611。《集成电路应用》主管单位为中国电子信息集团（CEC），国家一级期刊。
