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校验程序，方便向更长位数数据帧拓展。

1 矩阵法数学原理

首先介绍由传统LFSR结构的串行计算方法推导并行矩阵的过程^[12-13]。以CRC-16为例，它的生成多项式为g(x)=x¹⁶+x¹⁵+x²+1。由LFSR结构可知：每经过一个时钟周期后的CRC校验码寄存器状态与该周期前的校验码寄存器状态关系为式(1)^[12]所示：

$ \left\{ \begin{array}{l} {\boldsymbol{D}_{\left( {15} \right)}}' = {\boldsymbol{D}_{\left( {15} \right)}} + {\boldsymbol{D}_{\left( {14} \right)}} + {i_j}\\ {\boldsymbol{D}_{\left( {14} \right)}}' = {\boldsymbol{D}_{\left( {13} \right)}}'\\ {\boldsymbol{D}_{\left( {13} \right)}}' = {\boldsymbol{D}_{\left( {12} \right)}}\\ \cdots \\ {\boldsymbol{D}_{\left( 2 \right)}}' = {\boldsymbol{D}_{\left( 1 \right)}} + {\boldsymbol{D}_{\left( {15} \right)}} + {i_j}\\ {\boldsymbol{D}_{\left( 1 \right)}}' = {\boldsymbol{D}_{\left( 0 \right)}}\\ {\boldsymbol{D}_{\left( 0 \right)}}' = {\boldsymbol{D}_{\left( {15} \right)}} + {i_j} \end{array} \right. $

(1)

其中，D与D′脚标数字表示CRC-16校验码中的第几位。按照由高到低顺序，第15位用来存储最高有效位(Most Significant Bit, MSB)，第0位用来储存最低有效位(Least Significant Bit, LSB)。“+”号表示异或(XOR)计算。D与D′分别是一个周期运算前、后校验码寄存器中储存值状态。式(1)通过向量和矩阵的形式，建立起每个时钟周期数据i_j串行移入LFSR前的CRC校验码寄存器值D_j和i_j移入LFSR后的校验码寄存器值D_j′之间的数学表达式联系。将式(1)写成如式(2)表示形式^[13]：

$ {\boldsymbol{D}_m} = \boldsymbol{T}{\boldsymbol{D}_{m - 1}} + \boldsymbol{S}{i_{m - 1}} $

(2)

其中：T为n阶方阵，S与D都是n维列向量(n为CRC码位数)。根据CRC生成多项式的不同，相应的T矩阵也不同。CRC-16校验的T和S分别为：

$ \boldsymbol{T} = \left[ {\begin{array}{*{20}{c}} 1&1&0&0&0& \cdots &0&0&0&0\\ 0&0&1&0&0& \cdots &0&0&0&0\\ 0&0&0&1&0& \cdots &0&0&0&0\\ \vdots & \vdots & \vdots & \vdots & \vdots &{}& \vdots & \vdots & \vdots & \vdots \\ 0&0&0&0&0& \cdots &0&1&0&0\\ 1&0&0&0&0& \cdots &0&0&1&0\\ 0&0&0&0&0& \cdots &0&0&0&1\\ 1&0&0&0&0& \cdots &0&0&0&0 \end{array}} \right] $

(3)

$ \boldsymbol{S} = {\left( {1\;0\; \cdots \; \cdots \;1\;0\;1} \right)^T} $

(4)

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

$ {\boldsymbol{D}_m} = {\boldsymbol{T}^M}{\boldsymbol{D}_0} + {\boldsymbol{T}^{m - 1}}\boldsymbol{S}{i_0} + \cdots + \boldsymbol{T}\boldsymbol{S}{i_{m - 2}} + \boldsymbol{S}{i_{m - 1}} $

(5)

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

$ \begin{array}{l} {C_a} = \left( {n - 1} \right){n^2} \times \left( {m - 1 + m - 2 + \ldots + 1} \right) + \left( {n - 1} \right)\\ \;\;\;\;\;\;\;n \times m + n \times m = {n^2}\left( {n - 1} \right)m\left( {m - 1} \right)/2 + {n^2}m \end{array} $

(6)

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

$ \begin{array}{l} {C_m} = {n^3} \times \left( {m - 1 + m - 2 + \cdots + 1} \right) + n \times m + \\ \;\;\;\;\;\;\;n \times n \times m = {n^3}m\left( {m - 1} \right)/2 + {n^2}m + nm \end{array} $

(7)

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

2 Matlab程序实现

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

2.1 Matlab数学计算

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

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

2.2 CRC程序模块生成

程序前半部分将待校验数据帧中的每一位数据i_j在参与计算CRC校验码时的对应信息存入存储空间A中。Matlab后半部分程序将根据A中信息，自动生成符合Verilog HDL语法规则的并行CRC-16校验程序语句。该部分程序语句的核心是由异或计算表达式构成的并行计算结构。Matlab以“write”方式打开用来保存程序语句的外部文件“final_result.txt”并向其中输出生成的程序语句。首先输出的程序开头部分，包括输入、输出端口，内部连线声明，各寄存器初始化、参数定义、以及always循环语句起始等。核心并行CRC校验计算语句由n行表达式构成，每行语句计算n位校验码中的1位并且依据由高位到低位的顺序依次向下排列。输出的每行程序以“crc16out[k] < =”(k=n-1, n-2, …, 0)起始，表示该行语句用来计算16位校验码中的第k位。接下来通过循环依次读取矩阵A中每一行数据，判断其中存储的元素0/1值后进行输出。当在A的第k行第j列(j=0，1，…，m-1)读取到“A_kj=1”时，在对应的第k行后输出对应的表示存放数据i_j的寄存器位“sig c[d]”(其中c、d由数据长度m以及定义的sig寄存器位数确定)以及异或算符；反之，当读取到0值时不进行输出。读取完这一行数据后输出语句结束符号并开始输出A中下一行数据对应的计算语句。输出完全部n行校验码的计算语句后，生成其他Verilog HDL语法要求的必要结束语句，保存并关闭外部文件“final_result.txt”。其中保存的由Matlab生成的并行校验部分程序语句如下程序段所示。

crc16out[15] < =sig1[8]^sig1[6]^sig1[3]^…^sig78[0];

crc16out[14] < =sig1[7]^sig1[6]^sig1[4]^…^sig77[3];

…

crc16out[0] < =sig1[7]^sig1[5]^ …^sig78[1]^sig78[0];

在Windows 7(x86)操作系统, 硬件配置为Intel i3-2120 3.30 GHz处理器，4 GB内存的软、硬件环境下，运行Matlab R2010b版本。由Matlab生成满足Verilog语法规则的CRC-16校验模块的时间(取5次时间的平均值)如表 1所示。

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

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

3 仿真与实验 3.1 仿真部分

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

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

表 2展示了自动生成的校验模块在进行CRC-16校验时占用的FPGA内部资源数。

可以看出，基于矩阵法的并行校验模块占用FPGA内部逻辑单元资源的数量随并行校验数据帧位数m的增加而增加，几乎成正比关系，但即使是并行计算1 024 b长度数据帧的CRC程序占用的FPGA内部资源也仅为约7%。为了换取计算速度而增加占用的该部分FPGA内部的资源量在实际应用中是可以接受的。

3.2 拖曳阵缆系统上实验

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

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

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

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

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

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

实验结果说明在10次数据采集过程中，正常情况下经75 m拖缆上传的数据与经过通路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×10⁶的7位数值。这是因为将接插件拧松后，舱2通过拖缆上传的数据与校验码因为接触不良而发生改变，舱1接收的上传数据和校验码不再对应，因此三个校验码值均不相等。计数器记录的7位数值是数据传输错误的次数。

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

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

4 结语

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