基于Matlab的并行循环冗余校验Verilog代码自动生成方法

薛俊　段发阶　蒋佳佳　李彦超　袁建富　王宪全

摘要：

在水声信号探测数据的传输过程中，现场可编程门阵列（FPGA）通过传统串行方法对长数据帧进行循环冗余校验（CRC）时无法达到速度要求，而更快速的并行校验方法存在因编程复杂带来的实际工程应用困难问题。为了满足传输对校验速度的需求，降低编程难度和缩短编程时间，设计了一种借助Matlab对任意长度数据帧自动编写并行CRC程序语句的方法。该计算方法基于矩阵法数学原理，借助Matlab完成所有数学推导计算过程，然后直接输出符合Verilog HDL语法规则的并行CRC校验程序语句。通过在Quartus Ⅱ 9.0中仿真，进一步在民用拖曳声呐阵列系统上进行数据传输实验，验证了Matlab自动编程方法的有效性：校验程序的自动编写输出能在几十秒内完成，同时生成的并行CRC校验程序能在满足数据传输速度要求的情况下正确地计算出系统中传输协议定义的长数据帧的校验码。

关键词：

循环冗余校验；并行计算；Matlab；Verilog硬件描述语言；现场可编程门阵列

中图分类号：

TN919.3+3

文献标志码：A

Abstract：

During underwater signal data transmission process， using Field Programmable Gate Array （FPGA） to calculate Cyclic Redundancy Check （CRC） code with traditional serial calculating method cannot meet the demand of fast computation； however， parallel checking method， which is much faster， has difficulty in practical engineering application because of programming complexity. In order to meet the demand of transmission speed， to eliminate programming difficulty and time waste， a method was proposed to automatically generate parallel CRC calculating code for any length data frames by Matlab. It finished all the mathematical deductions based on matrix method and calculations with the help of Matlab and then generated parallel CRC calculating program which conforms to the Verilog HDL grammar rules. Finally， the CRC calculation program statements generated by Matlab were first simulated in Quartus II 9.0 and then demonstrated by data transmission experiments on a civil towed sonar system. The results prove the validity of the proposed method， its programming and generation can be finished in tens of seconds， and the CRC module can accurately figure out CRC code of every long data frame defined by transmission protocol within requested time.

英文关键词Key words：

Cyclic Redundancy Check （CRC）； parallel computing； Matlab； Verilog Hardware Description Language （Verilog HDL）； Field Programmable Gate Array （FPGA）

0引言

在現代数字通信中，循环冗余校验（Cyclic Redundancy Check， CRC）是一种广泛运用于通信网络以及自定义数据传输协议中的数据传输检错方法[1-3] 。CRC校验主要分为串行法和并行法两类。采用串行方法计算校验码时，待校验数据随时钟节拍依次逐位移入线性反馈移位寄存器（Linear Feedback Shift Register， LFSR）中，当数据输入完成时获得CRC校验码[4]。该方法实现简单，是目前较常用方法，但该方法受时钟节拍频率限制。在许多大规模数据传输应用场合，如使用拖曳声呐阵列进行水声信号探测，石油、地质勘探等，当数据帧传输频率达到几百兆赫兹且数据在处理器内部不再是逐位串行输入输出时，在常用处理芯片如现场可编程门阵列（Field Programmable Gate Array， FPGA）中采用串行方法进行CRC校验难以满足速度需求。此时，必须对传统的LFSR 结构进行改进或采用新的并行CRC计算结构来提升校验速度[5-6]。

目前，国内外学者提出了许多种提升CRC校验速度的方法。如Cheng等[7]通过改进LFSR结构，使其具有一定的并行能力并提高了运算速度。文献[8-9]介绍了通过查询码表的方法来计算校验码的方法，但该方法需要预先计算出CRC校验码值，当数据帧位数较长时，对应码表将会变得比较复杂，同时会占用较多的处理器内部储存空间。文献[10]提出了一种多通道同步CRC计算的方法，将整个数据分成E段，每段同时计算该段校验码，最后由E个子校验码共同计算出数据整体的CRC校验码；该方法在数据帧长度较长时数学理论推导繁琐，实际在FPGA中编程较复杂。文献[11-12]对并行CRC计算实现方法之一的矩阵法进行了介绍。矩阵法以向量和矩阵的数学形式表示出每个时钟周期输入LFSR中的数据与该时钟周期前、后两次CRC校验码寄存器值的关系。通过该关系逐次递推，最终递推出m（m表示待校验数据位数）位数据串行输入后的CRC校验码值。矩阵法具有数学推导逻辑关系相对简明、易于向位数更多的数据扩展等优点。但随着待校验数据帧长度的增加，该方法中矩阵迭代次数也随即增多，线性代数计算过程愈加复杂，同时得出的CRC校验程序语句更加冗长，使得人工程序编写、输入的过程容易产生差错。以上两点因素制约了矩阵法在FPGA中对多字节长数据帧进行CRC校验的应用。同时，在数据传输量大、传输速度快的实际工程应用场合，如地震勘探仪器、海洋声学仪器等由于串行CRC校验方式无法满足速度需求，它们也需要一种有效的、方便的并行CRC校验编程方法。

综上所述，本文设计了一种通过Matlab自动完成基于Verilog语言的 CRC并行校验程序编写的方法。该方法借助Matlab自动完成了所有线性代数运算，并将获得的结果翻译输出成符合Verilog 语法要求的CRC校验程序语句。将输出的程序语句在Quartus Ⅱ 9.0开发环境中生成并行CRC校验模块，该模块可直接应用。同时，该方法可以生成任意长度数据的CRC校验程序，方便向更长位数数据帧拓展。

将式（2）依次递推m次，就能将寄存器中的最终计算出的CRC校验码值Dm通过第0时钟周期的初值D0以及在m时钟周期内移入的m位数据ij表示出来，即如式（5）所示：

Dm=TmD0+Tm-1Si0+…+TSim-2+Sim-1（5）

如果同时输入m位数据ij，式（5）中所有的参数将都成为已知量。此时只需要一个时钟周期就能计算得到列向量Dm的具体值。因此，采用并行计算的方式将不用等待每位待校验数据随时钟节拍移入计算结构，仅需要较短的几个时钟周期便能计算出数据的CRC校验码。但矩阵法中大量的矩阵、向量间加法、异或计算以及多次乘法带来了庞大的计算量，给人工计算和编程带来困难。可以计算出式（5）中总共进行加法和异或运算的次数Ca为：

Ca=（n-1）n2×（m-1+m-2+…+1）+（n-1）

n×m+n×m=n2（n-1）m（m-1）/2+n2m（6）

总共需要的矩阵向量间乘法次数Cm为：

Cm=n3×（m-1+m-2+…+1）+n×m+

n×n×m=n3m（m-1）/2+n2m+nm（7）

可以看出，矩阵法的运算量十分巨大，并且将随着待编码数据帧长度m以及校验码位数n的增加而迅速增加。

2Matlab程序实现

Matlab中程序主要分成两个部分。第一步是完成其中复杂的线性代数运算，即计算式（5），并将结果信息保存到一个建立的n×m维度储存空间A中，其中n与m表示的含义与前文定义相同。第二步将A中存储的信息翻译成对应的CRC计算程序语句信息，然后根据A中信息自动生成符合Verilog HDL语法规则的CRC校验码计算程序语句，并将生成的程序语句保存在一个外部txt文件中。Matlab中程序的流程如图1所示。

2.1Matlab数学计算

由于CRC校验存在多种不同的校验类型（如CRC8，CRC16，CRCCCITT，CRC32等），校验计算使用的相关参数也不相同，在Matlab编程时预先输入不同校验类型对应的不同参数，其中包括每种校验类型对应的n维矩阵T与向量S等。在实际使用时，只需要根据CRC校验类型选择调用对应的参数以及输入待校验数据帧长度m，Matlab将根据前面选择和输入的参数创建一个n×m维空间A来储存计算过程中的结果。接下来通过循环计算Dm表达式中每项Tm-jS，即得到m个n维列向量Ej。

对Matlab编程时需要注意以下几点：首先，Matlab中能精确存储的整形数位数远低于Tm-jS计算过程中产生数据的位数；若直接计算Tm-jS，计算过程将产生截断误差或产生报错导致程序无法运行。因此，需要先将矩阵、向量转换为symbol型对象，以symblol型数据类型参加数学运算，否则即使计算得出结果也将因为丢失精度而失去意义。其次，Ej中第k位元素值Ej[k]的数学含义是：m数据中的im-1-j位在16位校验码中第k位的计算中进行异或计算的总次数。由异或运算的定义可知：数据a与数据b进行偶数次异或运算时，结果仍然是a本身，与b無关；只有它们进行奇数次异或运算时，结果才由a、b共同决定。因此，若元素Ej[k]的值是偶数，表示数据帧中的im-1-j位对校验码第k位的计算不产生影响；反之，Ej[k]是奇数时则表示im-1-j位对校验码中的第k位计算有贡献，需要在计算式中反映出该位数据值。为了得到数据的奇偶性，可将Ej中每个元素转化为char型后提取末位数数值，进行mod（Ej[k]，2）判断。结果是奇数则将1储存到前面定义的储存空间A中第k行第j列，反之在对应位置储存0。

从表1可以看出：在CRC校验种类确定后，Matlab生成校验模块的时间较短，可在几十秒钟内完成，并且运行时间与待校验数据长度m基本成正比。

与项目之前采用的人工程序编写方式进行比较。人工CRC校验程序编写方式是：手动操作数学计算软件进行一次向量、矩阵运算，产生一次结果。编程者根据CRC运算的数学含义，将线性代数运算的结果翻译为对应计算程序语句并输入开发环境。以拖曳声呐阵列系统项目中数据传输为例，传输协议规定每一个电子舱所负责收集的16道水听器数据在打包完成后数据帧总长度是78B（702b）。这表示当人工编程时，需要对应进行线性代数计算和对应程序输入702次。如果仅考虑每次编程者程序输入的时间，编程者在操作熟练后至少需要2min。在输入完成后也需要至少一次相同长时间的检查来防止人工操作产生差错。所以仅校验计算式程序输入这一项需要的总时间至少是：702×2×2=2808min，约等于47h。同时，这个时间还不包括其他因素，如操作软件时间、校正差错时间等额外时间。而借助于软件自动生产程序，从表1可知即使对1024b长数据帧进行并行CRC校验编程也仅需要约38s，显著少于人工操作时至少需要的47h时间，极大地提高了编程的效率，降低了项目成员编程负担。同时，由Matlab自动产生的程序语句准确率高，避免了人工操作可能产生的差错。

3仿真与实验

3.1仿真部分

选择CRC16校验形式，输入一次并行校验数据宽度128b， Matlab将生成的CRC校验程序储存在txt文件中。将程序直接拷贝到Quartus Ⅱ 9.0开发环境中，在工程中生成CRC校验功能模块，并对该模块进行仿真。仿真FPGA的型号采用的是实验室在研究用声呐拖曳阵缆系统上正在使用的ALTERA公司Cyclone Ⅲ系列EP3C25F324I7N型。仿真实验工程顶层.bdf文件中各个模块如图2所示。

通过计算机产生伪随机序列来模拟实际使用中可能遇到的各种数据信号。左侧模块是伪随机序列产生模块rand_num_gene，通过它产生128b长度的伪随机序列，传入右侧的并行CRC校验模块crc16_paral和下方的基于LFSR结构的串行CRC校验模块crc16_serial。由伪随机序列模拟的待校验数据分别以并行和串行的方式分别随时钟节拍pclk与sclk进入到两个模块中进行CRC校验，分别按照两种方式计算出CRC校验码，并在串行校验模块计算完成后比较两组CRC校验码值。通过比较两个模块对相同的2000组伪随机序列的校验结果，发现两个模块计算得出的CRC校验码完全相同，只存在计算消耗时间的不同，并行校验模块仅需要2个时钟周期即可计算出校验码值，而串行校验模块需要128个时钟周期。这表明由Matlab自动生成的并行CRC校验计算程序的正确性。图3表示显示的是crc16_paral的时序图，圆框圈出的数据是并行计算得到的CRC校验码值。

3.2拖曳阵缆系统上实验

将自动生成的并行CRC校验模块运用到民用拖曳声呐阵缆系统项目中的水声数据传输过程中进行实验。

拖曳声呐系统的作用是将拖曳阵缆内呈直线阵列分布的各道水听器采集的水声信号收集、处理后上传至上位机进行后续处理和使用。由于拖缆较长，水听器分布距离较远，数据的远距离传输需要通过缆间電子舱集中处理以及进行中继。同时，拖曳声呐阵缆在水下环境工作时存在着如低温、振动、外部拖曳产生的拉、压应力等可能影响数据传输可靠性的因素。所以为了保证数据帧传输的可靠性，有必要对向岸基、船基上位机上传的数据进行CRC校验。在拖曳声呐系统的数据传输协议中，定义每帧数据在不包含2B CRC校验码时，由14B帧头加64B数据共78B组成，协议同时规定每字节数据是9b。因此每次组帧完毕后需同时校验 702b长度数据。在几千赫兹频率的高速率采样下，总体成百上千道数的水听器将带来巨大的数据量，如果依靠传统串行方式，FPGA内部时钟频率无法达到速度要求。

在天津大学青年湖内进行的声呐系统数据传输实验如图4所示。

电子舱1与电子舱2经过一段75m长的内含水听器的声呐阵缆相连。为了便于实验操作，将电子舱1与舱2从湖中移出，放置于岸上靠近位置；并将舱1、2内电路板（传输板Tr与采集板Cl）从不锈钢水密外壳中取出。阵列其余缆段与电子舱仍然以直线阵列形式布放于湖中采集水下声信号。系统正常工作时，电子舱2本级以及下级舱采集的水声数据经舱2逐级上传到电子舱1中（如图中②部分）。另一方面，为了检验传输数据的正确性，将电子舱2的传输板通过4根15cm长的屏蔽双绞线（如图4中电子舱1、2间连线①所示）与在一旁的电子舱1上传输板相连，直接进行数据的传输。此时，下级到达舱2的每一帧数据同时经过两条传输通路上传：一条通路是按照正常工作时经过75m拖缆上传。该通路传输距离较长且位于水下，可能受到的环境影响因素较多。另一条通路是近距离的直接数据交换，位于岸上稳定环境，传输距离较短，不易出现差错。因此，实验将通路1选作对照组，以它作为正确的基准，将经过通路2上传的数据帧与CRC校验码与由通路1上传的数据帧与校验码对比，即可知道数据上传是否出现差错以及检验CRC校验是否有效。同时在电子舱1的传输板程序中设置一个计数器，记录通道1与通道2上传的数据的不同次数。

声呐阵列采集的水下数据为湖中背景噪声。该背景噪声是一个无规律的连续信号，数值随机，适合作为拖缆长时间采集的数据。声呐阵列以4000Hz的采样频率采集10组水下背景噪声，每次连续采集6×106次数据，每次采集持续约25min。

在实验的过程中计算机通过USB blaster连接到电子舱1传输板上FPGA，通过Quartus内的Signal Tap II逻辑分析仪实时查看数据波形。如图5所示，dat_out通道显示电子舱1接收到的电子舱2经由通道1双绞线直接上传的数据与CRC码。在两字节0前的两个9b字节02Eh与0B6h是CRC16校验码（最高位补充0）；sig79与sig80两个通道显示的是舱1接收到的通过传输通道2上传的CRC校验码；out11与out22两个通道显示的是电子舱1传输板本地再次对传输通道2上传数据进行CRC校验得到的校验码。可以看到， sig79和sig80以及out11和out22分别与的两字节CRC校验码相同，均为02Eh和0B6h。此时error_flag信号也一直置于高电平，10组采集结束后，每组完成后计数器记录数值是0。

实验结果说明在10次数据采集过程中，正常情况下经75m拖缆上传的数据与经过通路1上传的舱2数据和校验码完全相同，电子舱1到电子舱2间数据传输没有出现错误，并且CRC校验码也正确计算。实验结果符合预期。

进一步实验：改变传输通路，使传输通路2产生数据传输错误。由于声呐拖缆内电线包裹在专用复合材料拖缆皮中且充有特殊专用液体，难以干扰，不易破坏。于是实验选择通过人为将裸露的电子舱2与相连拖缆段之间的舱缆接插件接口故意拧松，造成传输线因接触不良引起传输数据改变。再次重复上述10次采集过程，观察数据传输结果变化。

同样在实验过程中通过Signal TapⅡ查看实时数据数值，如图6所示：电子舱1接收到的通道1上传的校验码是07Ch与020h，sig79与sig80两个通道显示的接收由通道2上传的CRC校验码是022h与0B6h，而out11与out22两个通道显示的舱1本地再次对通道2上传数据校验得到的两字节校验码是0A5h与00Ah。三者均不相同。此时，通道error_flag标志位产生了两个时钟周期低电平。在每次采集结束后，计数器的数值不再为0，而是一个不一定相等的小于6×106的7位数值。这是因为将接插件拧松后，舱2通过拖缆上传的数据与校验码因为接触不良而发生改变，舱1接收的上传数据和校验码不再对应，因此三个校验码值均不相等。计数器记录的7位数值是数据传输错误的次数。

实验现象说明只要数据传输过程出现错误，通过上级电子舱再次对数据计算CRC校验过程就能知道上传的数据与它对应的校验码不再对应。此时CRC校验的确起到了差错检验的效果。借助于CRC校验能有效地发现并定位在拖曳声呐阵列中的发生的数据传输错误。

通过上述仿真与实验，验证了通过本文方法快速的生成CRC校验模块的正确性与实用性。

4结语

CRC校验在数据传输通信中应用广泛并且发挥着重要作用。本文结合拖曳声呐阵列系统中大量数据快速CRC校验的实际应用需求，设计了一种通过Matlab自动完成数学计算并生成CRC校验程序模块的方法。该方法只需要确定CRC校验类型以及并行校验数据位数，即可快速自动生成满足Verilog HDL语法规则的CRC校验程序，生成的程序可直接在开发环境中生成模块并在FPGA上使用。该方法相比人工编程极大地节约了编程时间，有效地避免了人工编程易出现差错的问题。在开发环境中仿真和在实际拖曳声呐阵列系统上的运用验证了使用该方法计算CRC的正确性与实用性。自动CRC校验程序生成方法在通过FPGA进行大规模数据传输的应用场合拥有广阔前景。

参考文献：

[1]

SPRACHMANN M. Automatic generation of parallel CRC circuits [J]. IEEE Design and Test， 2001， 18（3）： 108-114.

[2]

KOOPMAN P. 32bit cyclic redundancy codes for Internet applications [C]// DSN 02： Proceedings of the 2002 International Conference on Dependable Systems and Networks. Washington， DC： IEEE Computer Society， 2002： 459-468.

[3]

GRYMEL M， FURBER S B. A novel programmable parallel CRC circuit [J]. IEEE Transactions on Very Large Scale Integration Systems， 2011， 19（10）： 1898-1902.

[4]

MATHUKIYA H H， PATEL N M. A novel approach for parallel CRC generation for high speed application [C] // Proceedings of the 2012 International Conference on Communication Systems and Network Technologies. Washington， DC： IEEE Computer Society， 2012： 581-585.

[5]

AYINALA M， PARHI K K. Highspeed parallel architectures for linear feedback shift registers [J]. IEEE Transactions on Signal Processing， 2011， 59（9）： 4459-4469.

[6]

ENGDAHL J R， CHUNG D. Fast parallel CRC implementation in software [C] // ICCAS 2014： Proceedings of the 2014 14th International Conference on Control， Automation and Systems. Piscataway， NJ： IEEE， 2014： 546-550.

[7]

CHENG C， PARHI K K. Highspeed parallel CRC implementation based on unfolding， pipelining， and retiming [J]. IEEE Transactions on Circuits and Systems Ⅱ Express Briefs， 2006， 53（10）： 1017-1021.

[8]

KOUNAVIS M E， BERRY F L. Novel table lookupbased algorithms for highperformance CRC generation [J]. IEEE Transactions on Computers， 2008， 57（11）： 1550-1560.

[9]

李剑锋.新的高性能CRC查表算法[J].计算机应用，2011，31（S1）：181-182.（LI J F. Highperformance CRC algorithm based on lookup table [J]. Journal of Computer Applications， 2011， 31（S1）： 181-182.）

[10]

徐展琦，裴昌幸，董淮南.一種通用多通道并行CRC计算及其实现[J].南京邮电大学学报（自然科学版），2008，28（2）：53-57.（XU Z Q， PEI C X， DONG H N. Generalized CRC computation algorithm with multiple channels and its implementation [J]. Journal of Nanjing University of Posts and Telecommunications （Natural Science）， 2008， 28（2）： 53-57.）