基于FPGA的16 bit CRC校验查表法设计

季鹏辉，孟 丁，任勇峰*

(1.中北大学仪器科学与动态测试教育部重点实验室;电子测试技术国家重点实验室，太原030051;2.北京第二炮兵驻699厂军事代表室，北京100076)

循环冗余校验(CRC)是一种实现简单、校验能力很强、在串行通信中广泛采用的校验方式［1］，可提高数据传输的可靠性和准确性。由于FPGA速度快、效率高、灵活稳定、集成度高的特点，因此，FPGA广泛应用于串行通信，来提高串行通信的速度和效率［2］。对于常规的CRC查表法校验而言，通常需要事先生成校验表，然后才能对其进行查询，使查表法的实现复杂、繁琐且不易操作。为了增加CRC查表法校验的可行性和简洁性，本文介绍了基于FPGA IP核实现CRC校验的查表法设计和实现方法。

1 CRC校验基本原理

CRC校验的基本思想是利用线性编码理论，在发送端根据要传送的k位二进制序列，以一定规则产生一个校验用的监督码r位，并附在信息后，构成一个新的二进制码序列数，共(k+r)位，最后发送出去［3］。将待校验数据表示为一个n阶的多项式P(x)，G(x)为 CRC多项式(对于 CRC-16而言，G(x)=x16+x15+x2+1)，则P(x)=Q(x)×G(x)+R(x)，式中R(x)和Q(x)分别是P(x)除以CRC多项式G(x)的余数和商，这个R(x)就是目标CRC校验值。根据CRC校验基本原理，CRC校验可由逐位运算或者查表法实现。

(1)逐位运算法

根据CRC校验基本原理可知，CRC校验实际上是一个循环移位的模2运算，对于CRC-16，通过设置一个17 bit的寄存器，反复移位和进行CRC除法，寄存器中最终值去掉最高位就是所求CRC校验值。逐位运算法在数据每移入一位时，就需重新对每一位进行再次计算。因此，移位操作的次数等于总的数据位数减去16［4］。这种算法简单，容易实现，但它一次只能处理1 bit数据，效率太低。如果发送的数据块比较长，这种算法就不太合适了。

(2)查表法

为提高逐位运算法的效率，查表法的CRC-16校验每次可以处理一个字节(8 bit)，根据异或运算的交换律(A XOR B)XOR C=A XOR(B XOR C)，数据可以先与刚从寄存器移出的字节相异或，通过高8 bit的反复移位和CRC除法，得到CRC余式表的索引值，根据索引值进行查表，再用表值异或寄存器，这样得到的即为CRC校验码，但其缺点是需要占用大量的逻辑资源。

2 方案设计

某总线控制系统中，为了提高数据传输的准确性和可靠性，数据的接收和装载都须使用CRC校验，通过接收的数据帧CRC校验码和查表法产生的CRC校验码一致性来判断数据传输的准确性，数据帧由数据区，CRC校验码，数据区长度组成。

某总线控制系统为高速数字电路，当数据区数据较多时，使用逐位运算法势必会带来速度和功耗的问题，从而造成信号传递过程中延迟。为解决这些问题，本设计采用了查表法，由于查表法基于字节(8 byte)操作，避免了耗时的位运算，故运算量少，速度快的优点，大大优化了系统的设计。查表法一般可由软件或者硬件实现，本设计采用了硬件实现查表法的CRC校验，其原理图框图如图1所示。

进行查表法校验时，应事先计算所有CRC校验码，并将其制作为一表格，将所有的信息组对应的校验元按次序排序起来［5］，考虑到计算CRC校验码和制作表格的复杂性，本设计中采用了FPGA的IP核建立RAM来存放CRC的校验码，从而无需事先生成校验表，使得程序代码少，修改灵活，这样只要识别读入的余式表索引，就能用一条指令找到对应的校验码。

图1 CRC校验硬件实现原理图框图

为此，根据查表法原理，通过如下的步骤实现查表法的16 bit CRC校验。

(1)初始化寄存器;

(2)寄存器高八位与待传输的信息字节进行异或运算，得出一个指向余式表的索引;

(3)寄存器左移八位;

(4)余式表索引表值与寄存器做异或运算;

(5)如果数据未接收完，则重复(2)(3)(4)步，否则执行第(6)步;

(6)寄存器的内容即为CRC码。

3 内部逻辑设计

根据某总线控制系统要求，系统在接收到RS-422转义数据后，在FPGA中被解码为原始数据，CRC校验正确后数据被再转义回传给计算机。为此，FPGA内部逻辑可划分为:

(1)422接收模块:主要用于数据帧的接收，并将接收的数据帧存入下一级FIFO中;

(2)CRC控制模块:主要用于CRC校验的实现，将FIFO中数据读出，通过对存有CRC校验码余式表的查询，进行16 bit CRC的校验。

如图2 Xilinx原理图所示，re422为422接收模块，ctr_crc为CRC控制模块，RAM4K为存储16 bit CRC校验表全部校验码的RAM。

图2 FPGA实现16 bit CRC校验查表法设计原理图

为了构造16 bit CRC校验余式表，本设计通过Xilinx中CORE Generator生成IP核和设置IP核的参数来建立Block RAM，即图2中RAM4K模块。通过Uedit创建*.coe文件，将16 bit CRC校验余式表中所有CRC码写入*.coe文件，并将其导入RAM中，实现16 bit CRC校验余式表的建立，以此代替相关程序直接生成查表法所需的CRC校验码，使本设计代码减少，修改灵活，并且避免了重复设计，提高了工作效率。其中，RAM的地址为CRC索引值。图3即为RAM中的部分CRC余式表值。

图3 RAM中的CRC余式表值

16 bit CRC校验查表法校验流程如图4所示。

图4 16 bit CRC校验查表法校验流程图

判断串行通信是否正确，通过对数据区中的数据进行CRC查表法校验得到的校验码与直接从数据帧中读出的CRC码进行对比，相等即数据通信正确，否则就错误。

RS-422接收模块将接收的数据帧存入FIFO，CRC控制模块从FIFO中读出数据，从FIFO中读出一个数据时，初始化CRC寄存器(CRC初始值为0xFFFF)，CRC寄存器高8位与数据位异或，其值即为余式表索引值也就是RAM地址，CRC寄存器左移8位，与RAM中读出的余式表值异或，存入到CRC寄存器中。重复以上操作，直到读完FIFO中所有数据，此时，CRC寄存器中值即为数据帧的CRC校验码。若和读出的CRC校验码相等，则校验正确;反之，则继续等待正确的数据帧到来。

本设计采用 Xilinx公司 Spartan-3AN系列XC3S200AN FPGA芯片作为主控制器，使用18.432 M晶振，通过VHDL语言对FPGA编程，为灵活、高效的实现CRC校验的查表法设计，采用了状态机，对于高速数字电路来说，状态机是一种重要的时序逻辑电路，用其来描述数字电路的控制单元和运算单元。本论文分别给出了查表法和通过逐位运算法实现CRC-16校验的部分VHDL程序代码［6-7］，如表1所示。

表1 实现CRC-16校验部分VHDL程序代码

else rd_en＜ =＇0＇;addrd＜=addrd+1;w_state＜=wr0;end if;……end case;逐位运算法实现CRC-16的部分程序case w_state is……when wr0=＞rd_en＜ =＇1＇;w_state＜=wr1;when wr1=＞datard＜=cdin;--读FIFO中数据cnt＜=cnt+1;w_state＜=wr2;when wr2=＞crc_reg＜=datard＆ "00000000";w_state＜=wr3;when wr3=＞crc_reg＜=crc_reg(15 downto 0)＆ ＇0＇;--寄存器左移1位cnt1＜=cnt1+1;w_state＜=wr4;when wr4=＞crc_reg＜=crc_reg xor X"8005";--寄存器与CRC多项式异或w_state＜=wr5;when wr5=＞if cnt＜lenth then if cnt1=8 then rd_en＜ =＇0＇;addrd＜=addrd+1;cnt1＜=(other=＞＇0＇);w_state＜=wr0;else w_state＜=wr3;end if;else w_state＜=wr6;end if;……end case;

通过表1可知，对一个字节的数据进行CRC-16校验，查表法需要7个时钟周期，而逐位运算则需要40个时钟周期(5×8 bit)，本设计采用了18.432 M的外接晶振，数据块长度为134个字节，则这两种方法所需的时间如表2所示，查表法运算量少，速度快的优点很明显的体现出来。

表2 CRC-16校验所需时钟和时间

4 实验验证

本设计使用Xilinx ISE 10.1进行编译和综合。为了验证本设计的正确性，采用了ChipScope Pro Analyzer虚拟逻辑分析仪，对其进行在线逻辑分析，通过设定触发条件将信号实时的保存于Block RAM中，然后通过JTAG接口传送到计算机，最后在用户计算机屏幕上显示出波形［8］。如图5、图6中16 bit CRC校验查表法设计逻辑分析图所示。

图5 16 bit CRC校验查表法设计逻辑分析图(1)

图6 16 bit CRC校验查表法设计逻辑分析图(2)

其中，lenth为数据区长度，crc为数据帧CRC校验码，crc_reg为CRC寄存器，rd_en为读FIFO使能信号，addrd为读FIFO的地址，datard为从FIFO中读出的数据。由图4流程图和图5可知，先读数据帧CRC校验码和长度，当rd_en上升沿到来时，FIFO中读出的数据datard为0xFFD1和0x0086(低字节先发送，高字节后发送)，即 crc为0xFFD1，lenth为0x0086(十进制为134)，此时开始读数据区数据，CRC寄存器初值为0xFFFF，初始化后变为0x0000，如图5所示。

在从FIFO中读出最后一个数据0x5A之前，CRC寄存器crc_reg为0xA4F1，左移一个字节crc_reg变为0xF100，其高8 bit 0xA4与0x5A异或，得到余式表索引值254，其余式表值为0x0ED1(如图3所示)，则 CRC=余式表值 XOR crc_reg=0x0ED1 XOR 0xF100=0xFFD1，很显然，crc和crc_reg相等，如图6所示。证明了通信过程中的CRC校验的正确性，同时也验证了本设计的正确性和可行性。

5 结束语

采用查表法实现CRC校验，使实际中的应用变的简单易行。FPGA的使用让设计变的简单，尤其是IP核的使用，用RAM构造的16 bit CRC校验余式表使源程序更加简洁明了。ChipScope Pro Analyzer的使用缩短了设计时间，也方便了本论文设计的验证。在某总线控制器实际应用中，也证明了本设计的可行性，并表现出良好的性能。

［1］孙志雄，谢海霞.基于FPGA的CRC编解码器实现［J］.电子器件，2012，35(6):657-660.

［2］叶懋，刘宇红，刘桥.CRC码的FPGA实现［J］.重庆工学院学报，2007，21(3):85-87.

［3］刘新宁，王超，胡晨，等.一种快速CRC算法的硬件实现方法［J］.电子器件，2003，26(1):88-91.

［4］莫元劲，黄水永.并行CRC在FPGA上实现［J］.电子设计工程，2011，19(15):133-135.

［5］刘会杰，张乃通.基于查表法的快速CRC算法设计［J］.通信技术，2002，124(4):8-10.

［6］常天海，胡鉴.基于FPGA的CRC并行算法研究与实现［J］.微处理器，2010，4(2):45-48.

［7］任勇峰，庄新敏.VHDL与硬件实现速成［M］.北京:国防工业出版社，2005.

［8］王杰，王诚，谢龙汉.Xilinx FPGA/CPLD设计手册［M］.北京:人民邮电出版社，2011.