基于100G以太网的一种并行CRC算法

胡坤焌 黄元峰

摘要：为解决大规模数据传输中CRC校验的实时处理问题，文章提出了一种可同时处理256位数据的并行算法。文章首先通过递推法推导出4位数据并行运算CRC（Cyclical Redundancy Check）关系式，并将表达式系数提出转化为矩阵，在此基础上对矩阵反复迭代，求得256位数据并行计算矩阵。该并行算法推导过程直观易懂，算法实现简单。文章最后采用硬件描述语言对算法进行描述，并搭建了验证环境。仿真验证结果表明了该方案的可行性，达到了设计指标要求，在时钟频率为400MHz的条件下可满足100G以太网中CRC校验需求。

关键词：高速以太网;256位并行数据;CRC编码; 矩阵并行算法;CRC校验

中图分类号：TP319.56        文献标识码：A

文章编号：1009-3044（2022）13-0037-03

1 引言

随着科学技术的发展，数据的存储和传输速度大大提高[1]。由于信息传输过程中的干扰，信号的失真依然难以避免，而通过增加冗余码的方式来对传输数据进行检错和纠错，可大大提高数字通信的可靠性。在多种检错码中，由于CRC编码和解码方法简单、检错能力强等特点，在数字通信中得到广泛应用[2]。如今，网络安全已经是热门的探讨话题[3]，CRC校验也同样在网络安全领域中广泛应用。在IEEE 2010年发布的802.3ba标准中，MAC（Media Access Control）层仍沿用之前的规定，而100Gb/s的数据传输速率使得以往CRC计算方法不再适用，需要采用更高位宽的并行数据来满足现代数字通信对于高吞吐量需求。

CRC编码实现方式多种多样[4]。传统串行编码利用LFSR（Linear Feedback Shift Register）进行级联，其结构简单且容易实现，但缺点是处理效率低下且无法应用到对速度要求较高的场合，因此在高速通信领域中越来越多地使用并行计算的方法。文献[5]中提到的查表法运算较快，但需要存储模块来预先存储表中项目。当并行计算位数每增加一位，所需存储的表项就会呈现指数级增长，由于占用资源多，所以难以应用在高位宽数据场合。文献[6]提出了一种用级联结构实现对64位数据的并行运算，但当进一步提高并行数据位宽时，级联结构就会增多，256位并行计算时需要32个模块，延时大大增加。文献[7]提出了一种128位并行数据的CRC算法，但由于时钟频率的限制，满足不了100Gb/s的吞吐量的需求。

本文提出了一种可实现256位并行数据的CRC编码方案，并对此方案进行了硬件实现。通过对仿真结果进行分析，验证了其准确性并具有一定的实用价值，在时钟频率为400MHz的情况下，其能够满足吞吐量为100Gb/s的需求。

2 CRC校验原理

设通信中待检测的信息码为n位，将此信息码用多项式M表示：

[M=mn-1Xn-1+mn-2Xn-2+…+m1X+m0 ]      （1）

为了计算该数据的CRC，还需要一个称为生成多项式的多项式g（x），其最高次幂为k。待编码的信息序列与多项式g（x）进行模二运算，则会对应生成一个k-1位的冗余码。CRC检验的一般计算流程如下：

1）将式（1）中的多项式M乘以[Xk]，即信息序列左移k位得到式（2）：

[XkM=mn-1Xk+n-1+mn-2Xk+n-2+L+m1Xk+1+m0Xk]     （2）

2）将得出来的结果式（2）除以生成多项式g（x），得到式（3）及相应的余数多项式r（x）：

[XkMg（x）=q（x）+rxgx                                          （3）]

其中r（x）为：

[rx=rk-1xk-1+rk-2xk-2+…+r1x+r0             （4）]

3）将式（2）（4）带入式（3）中，则得到附有CRC码的数据序列式（5）：

[qxgx=XkM+rx=mn-1Xk+n-1+…+m1Xk+1+…+r1x+r0 ]

（5）

4）在接收端接收到带CRC码的数据序列后，使用相同的多项式进行模二运算。若余数为0，则表明数据在传输中没有错误。反之，则说明传输发生错误。

通过线性反馈寄存器级联实现的CRC串行计算电路[8]主要由移位寄存器和异或门组成，具体硬件结构如图1所示[9]。每个时钟周期仅能输入1比特数据，并进行相应移位和异或运算后得到计算结果。对于n位的数据来说，则需要n个周期完成CRC值计算。由于串行计算效率低下，一般只被用于低速通信的场合中[10]。

設[cj+1i+1]为第j+1次输入数据的情况下第i+1位CRC的值，[cji]为第j次输入数据的情况下第i位CRC的值，[dj+1]为第j+1位的数据输入，[cj31]为第j位数据输入后的第31位CRC值。由此则可以得到当前此位数据的CRC值与前一位数据及其CRC码之间的关系，即式（6）：

[cj+1i+1=cji⊕gi+1dj+1⊕cj31                          （6）]

3矩阵并行算法

依据以太网的国际标准IEEE 802.3[11]，数据帧中使用的CRC校验模型为CRC-32[12]，其对应的生成多项式g（x）为[13]：

[gx=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1]

对式（6）进行4次递归运算，可得到处理4位数据后的CRC码与初始CRC码和数据之间的关系式，推导出的CRC-32关系式如下：

[c431=c270c430=c260L          L c45=c310⊕c290⊕c280⊕c280⊕c00⊕d3⊕d1⊕d0L          Lc41=c290⊕c280⊕d1⊕d0c40=c280⊕d0]

当前CRC值中的每一位的值都可表达为式（7）：

[c1i=xi31c031⊕L⊕xi0c00⊕yi3d13⊕L⊕yi0d10                   （7）]

其中i为自然数，i=0，1，...，31。x和y分别为初始CRC码及输入的4位数据的系数。

将式（7）表达式中的系数x、y提出，可得到一个36*32的矩阵，如矩阵（1）。

将矩阵（1）进行转置，拆分成两块。其中前32行为系数x组成的32*32 CRC系数矩阵[14]，如矩阵（2）。

后四行为系数y组成的4*32输入数据参数矩阵：

[00100110000010001110110110111000000100110000010001110110110111000000100110000010001110110110111000000100110000010001110110110111]

设：

[C1=C131，C130…C1i…C10]

[C0=C131，C130…C1i…C10]

根据式（2）并将式中的加号替换为异或，可以得到第一次4位数据输入结果，计算公式如式（8）：

[C1=C0*C32*32+D1*D4*32]                       [8]

将式（8）进行一次迭代，可以得到第二次4位数据输入计算结果式（9）：

[C2=C1*C32*32+D2*D4*32=C0*C32*32+D1*D4*32*C32*32+D2*D4*32]             [9]

同理，将式（9）再进行迭代，经过6次迭代后可得到256位数据并行的矩阵表达式，即式（10）：

[C256=C0*C25632*32+D256*D256256*32                       10]

式（10）中[C256]为256位并行数据输入后的CRC值，[D256]为256位并行输入数据，[D256256*32]和[C25632*32]为256位数据并行时的参数矩阵。注意：当用MATLAB计算矩阵时要将矩阵进行奇数变1，偶数变0的处理[15-16]。

256位并行数据的计算流程如图2所示。

4逻辑设计

本文以100G以太网中采用的CRC-32计算为例，该以太网每周期可处理数据位宽为256bit，时钟频率可达400MHz，其逻辑设计结构如图3所示。

在一个时钟周期内，输入256bit待处理数据。根据信号szin、sop对数据进行前补零、字节高低位翻转等预处理操作。将处理结束的数据送入计算模块，得到第一步计算数据crc_s1，并将crc_s1作为下一输入的参数值进行迭代。当eop信号有效时表示输入计算结束，对此时得到的crc_s1进行翻转，取反操作即得到输入CRC码。

5仿真验证

为了验证矩阵计算的正确性，使用传统串行计算和矩阵计算的方法对相同的输入值进行编码，在Modalism SE-64搭建的平台上进行仿真验证，再将两者的仿真结果进行对比。由仿真波形可以看出，当输入值为63时，利用矩阵计算的CRC值为32xec7dd02d，而使用传统串行计算最后的结果值也为32xec7dd02d。另外选取不同输入值进行校验，皆可得到相同的结果，说明矩阵计算的方法是正确的。

说明：图4中clk为时钟信号，din为当前的输入值，crc为计算结果。由于使用矩阵法可一次处理256位数据，所以可单周期完成运算。图5中data为总输入值，din为当前输入值，一个时钟周期输入1比特的0或1。

注意：在本次使用矩阵法和串行方式对输入值进行计算时均没有加入数据预处理和结果处理部分，仅为驗证相同输入情况下矩阵计算的正确性。

6结论

本文介绍了CRC并行和串行两种实现方式，并分析了如今主流高位宽并行算法的特点，然后基于4位并行数据的矩阵算法，通过反复迭代得到可应用于高位宽输入的计算矩阵。利用本文的思想和方法可以方便地得出不同的并行度下的CRC计算矩阵，并应用到不同场合的数据校验中。本文以256位数据并行为例，用硬件描述语言对算法进行硬件实现并搭建验证环境。仿真验证结果表明，在时钟频率为400MHz情况下，数据吞吐量可达到100Gb/s，本文的思想和方法能够满足100G以太网中高速网络通信中进行CRC计算校验的要求。

参考文献：

[1] 夏忠海，任勇峰，贾兴中，等.基于FPGA的CRC查表法设计及优化[J].电测与仪表，2017，54（3）：54-59，88.

[2] 杨卫平.CRC计算实现方法[J].电子技术与软件工程，2018（9）：158-159.

[3] 黄丽丽.大数据背景下的计算机网络安全探讨[J].电脑知识与技术，2021，17（23）：38-39.

[4] 姚威.循环冗余校验码并行算法的研究与实现[J].计算机与数字工程，2006，34（9）：112-114.

[5] 周凯，田枫，李爱国.基于查表法CRC检错码改进算法的研究与实现[J].微型电脑应用，2017，33（8）：12-14.

[6] 王涛，屈代明，江涛.降低SCL译码错误的级联极化码[J].中兴通讯技术，2019，25（1）：5-11.

[7] 赵坤鹏，吴龙胜，马徐瀚，等.一种基于矩阵的并行CRC校验算法[J].电子设计工程，2017，25（3）：85-88.

[8] 李永基，魏文军.基于LFSR的CRC校验码在FPGA上的实现[J].兰州交通大学学报，2015，34（6）：91-94.

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

[10] 朱正鹏，朱旭锋，李宾，等.一种位宽可变的CRC校验算法及硬件实现[J].航天控制，2019，37（2）：42-48.

[11] Cheng C，Parhi K K.High-speed parallel CRC implementation based on unfolding，pipelining，and retiming[J].IEEE Transactionson Circuits and Systems II：Express Briefs，2006，53（10）：1017-1021.

[12] 張颖，郭志君.10G以太网高速CRC的FPGA实现与优化[J].网络安全技术与应用，2018（12）：58-60.

[13] Ahmad A，Hayat L.Selection of polynomials for cyclic redundancy check for the use of high speed embedded： an algorithmic procedure[J].WSEAS Transactions on Computers，2011，10（1）：16-20.

[14] 陈基昕，王忠，赵锦宇.基于CAN总线的改进CRC校验算法设计[J].工业控制计算机，2018，31（5）：37-38.

[15] 时亚丽.基于FPGA的CRC32校验查找表算法的设计[J].山东工业技术，2016（10）：215.

[16] 王爽.CAN总线控制器CRC校验码的设计原理及实现[J].微处理机，2019，40（3）：25-28.

【通联编辑：代影】