一种用于128位并行数据的CRC校验矩阵生成方法

摘要

本发明提供一种用于128位并行数据的CRC校验矩阵生成方法，减少了级联结构带来的链路延迟，实现高速串行通信中接收或发送数据的实时校验，用于128位并行数据的CRC校验矩阵的生成方法。该方法提供了直接对128并行数据进行CRC编解码的校验矩阵，从而避免使用延时较大的级联结构，提高了128位并行数据的CRC编解码效率，实现高速串行通信中接收或发送数据的实时校验。基于该校验矩阵的CRC电路可以用于PCIe？3.0物理层中的128位并行数据的实时CRC校验，保证了数据的高效率传输。

说明书

技术领域

本发明属于可靠性编解码领域，涉及一种并行数据的CRC校验矩阵生 成方法，具体涉及一种用于128位并行数据的CRC校验矩阵生成方法。

背景技术

为保证数据通信的可靠性，通常在数据传输中采用CRC编码对被传输 数据进行校验。目前实现CRC编码方式多样，有串行编码方式、查表法和 公式法(也称推导法)等。

串行编码实现方式简单硬件消耗很小，但是由于只能串行处理数据，数 据传输速率非常低。查表法需要存储模块来存储表项，其硬件消耗大，并且 难以实现高位宽的并行数据处理。公式法目前在以太网和PCIe等高速并行 通信中广泛应用，但其迭代推导方式对于高位宽数据(大于16)来讲，推 导比较复杂，因此一般采用基于公式法的级联结构解决并行宽位数据的 CRC编码(即采用多个窄位CRC编码结构级联实现并行宽位数据的CRC 编码，如采用多个面向8位数据编码的CRC模块，通过级联实现对64并行 数据的CRC编码)，级联结构在对宽位并行数据(如128位)进行编解码时 延时较大，无法满足实际的应用需求。

当前，PCIe3.0(8GT/s)在物理层中使用128b/130b编码方式以实现负 载均衡，在单周期内实现对128位并行数据的CRC校验是保证高速串行通 信效率的前提。串行编码、查表法、公式法及基于公式法的级联结构均无法 高效率的实现对128并行数据的CRC编解码。

发明内容

针对现有技术中存在的问题，本发明提供一种用于128位并行数据的 CRC编解码，减少了级联结构带来的链路延迟，实现高速串行通信中接收 或发送数据的实时校验，用于128位并行数据的CRC校验矩阵的生成方法。

本发明是通过以下技术方案来实现：

一种用于128位并行数据的CRC校验矩阵生成方法，其特征在于，包 括如下步骤，

1)根据串行编码CRC的编解码原理，得到当前CRC值与当前数据输 入和前一级CRC值的关系；

2)根据当前CRC值与当前数据输入和前一级CRC值的关系，通过迭 代得到8位并行数据输入的当前CRC值与前一级CRC值和当前8位并行数 据输入的关系；

3)根据步骤2)中得到的CRC前后关系，提取出32x32的前一级CRC 参数矩阵和8x32的当前数据输入参数矩阵；

4)根据步骤3)中的参数矩阵，得到8位并行数据输入的当前CRC值 与前一级CRC值和当前8位并行数据输入的相应表达式，对该表达式进行 四次迭代运算后，得到输入32数据后的CRC值及其对应的表达式；

5)从输入32数据后的CRC值的表达式中提取出前一级CRC值和当前 32为数据输入的参数矩阵；将该参数矩阵中的奇数变为1，偶数变为0，得 到32位并行的当前CRC值与前一级CRC值和当前32位并行数据输入的关 系表达式；

6)对步骤5)中得到的关系表达式按照步骤4)和5)的方法进行四次 迭代，得到128并行数据的当前CRC值与前一级CRC值和当前128位数据 输入的关系矩阵；

7)将步骤6)得到的关系矩阵用于128并行数据编码的实时校验。

优选的，步骤1)中，当前CRC值与当前数据输入和前一级CRC值的 关系为，

$c_{i+1}^{j+1}=c_i^j\oplus \left(g_{i+1}\right(d_{j+1}\oplus c_{31}^j));$

其中，为第j+1次数据输入后的第i+1位CRC值，为第j次数据 输入后的第i位CRC值，g_i+1为CRC生成多项式中第i+1位的系数，d_j+1为第 j+1次的数据输入，为第j次数据输入后的第31位CRC值，j为自然数， i＝0,1...31。

进一步，步骤2中，8位并行数据输入的当前CRC值与前一级CRC值 和当前8位并行数据输入的关系为，

$c_i^1=x_{31}{c}_{31}^0\oplus x_{30}{c}_{30}^0\oplus \mathrm{...}{x}_i{c}_i^0\oplus \mathrm{...}{x}_0{c}_0^0\oplus y_7{d}_7^1\mathrm{...}\oplus y_j{d}_j^1\mathrm{...}\oplus y_0{d}_0^1,$

其中，为当前CRC值的第i位，为前一级CRC值的第i位 (i＝0,1...31，j＝0,1...7)，为当前的数据输入的第j位；x_i和y_j为该关系中 和的参数，由IEEE802.3中的CRC-32生成多项式决定。

再进一步，步骤3)中提取参数矩阵时，

设由步骤2)得到的8位并行数据输入的当前CRC值为

$C^1=[c_{31}^1,c_{30}^1\mathrm{...}{c}_i^1\mathrm{...}{c}_0^1],$则$C^{1T}={[c_{31}^1,c_{30}^1\mathrm{...}{c}_i^1\mathrm{...}{c}_0^1]}^T;$

将步骤2)包含参数x_i与y_j的带入到列向量C^1T中，其中i＝0,1...31， j＝0,1...7，得到

$\left(\begin{array}{c}{c}_{31}^1=x_{31}{c}_{31}^0\oplus x_{30}{c}_{30}^0\oplus \mathrm{...}{x}_i{c}_i^0\oplus \mathrm{...}{x}_0{c}_0^0\oplus y_7{d}_7^1\mathrm{...}{y}_j{d}_j^1\mathrm{...}\oplus y_0{d}_0^1\\ c_{30}^1=x_{31}{c}_{31}^0\oplus x_{30}{c}_{30}^0\oplus \mathrm{...}{x}_i{c}_i^0\oplus \mathrm{...}{x}_0{c}_0^0\oplus y_7{d}_7^1\mathrm{...}\oplus y_j{d}_j^1\mathrm{...}\oplus y_0{d}_0^1\\ \mathrm{...}\\ c_i^1=x_{31}{c}_{31}^0\oplus x_{30}{c}_{30}^0\oplus \mathrm{...}{x}_i{c}_i^0\oplus \mathrm{...}{x}_0{c}_0^0\oplus y_7{d}_7^1\mathrm{...}\oplus y_j{d}_j^1\mathrm{...}\oplus y_0{d}_0^1\\ \mathrm{...}\\ c_0^1=x_{31}{c}_{31}^0\oplus x_{30}{c}_{30}^0\oplus \mathrm{...}{x}_i{c}_i^0\oplus \mathrm{...}{x}_0{c}_0^0\oplus y_7{d}_7^1\mathrm{...}\oplus y_j{d}_j^1\mathrm{...}\oplus y_0{d}_0^1\end{array}\right)$

按照上式对应关系提取出参数x_i和y_j，得到一个32x40的矩阵CD_40×32^T， 转置后得到40x32的矩阵CD_40×32，将CD_40×32按照x_i和y_j分割开，得到两个分 别关于前一级CRC值和当前数据输入值的参数 矩阵C2C_32×32和D2C_8×32。

再进一步，步骤4)中，得到8位并行数据输入的当前CRC值与前一 级CRC值和当前8位并行数据输入的相应表达式为，

$C^1=C^0*C2C_{32\times 32}\oplus D^1*D2C_{8\times 32};$

根据表达式中C¹、C⁰和D¹之间的关系，得到输入两次8位数据，即输 入16位并行数据后的当前CRC值为，

$C^2=C^1*C2C_{32\times 32}\oplus D^2*D2C_{8\times 32}=(C^0*C2C_{32\times 32}\oplus D^1*D2C_{8\times 32})*C2C_{32\times 32}\oplus D^2*D2C_{8\times 32};$

采用同样处理，继续迭代两次后得到输入四次8位数据，即输入32位 并行数据后的CRC值为，

$C^4=C^3*C2C_{32\times 32}\oplus D^4*D2C_{8\times 32};$

将异或关系转换为数学中相加，可得到C⁴与C⁰以及D¹、D²、D³、D⁴的关系为，

C⁴＝C⁰*C2C_32×32*C2C_32×32*C2C_32×32*C2C_32×32+D¹*D2C_8×32*C2C_32×32*C2C_32×32*C2C_32×32+ D²*D2C_8×32*C2C_32×32*C2C_32×32+D³*D2C_8×32*C2C_32×32+D⁴*D2C_8×32

其中，C⁰为前一级的CRC值，

D¹、D²、D³、D⁴分别为第一、二、三、四次输入的8位数据，

C2C_32×32*C2C_32×32*C2C_32×32*C2C_32×32为C⁰的参数矩阵，

D2C_8×32*C2C_32×32*C2C_32×32*C2C_32×32为D¹的参数矩阵，

D2C_8×32*C2C_32×32*C2C_32×32为D²的参数矩阵，

D2C_8×32*C2C_32×32为D³的参数矩阵，

D2C_8×32为D⁴的参数矩阵。

再进一步，步骤5)中，根据步骤4)中C⁴表达式，令C⁰的参数矩阵 为D¹的参数矩阵为D²的参数矩阵为D³的参数矩阵为 D⁴的参数矩阵为则

$\begin{array}{c}C2C_{32\times 32}^{32}=C2C_{32\times 32}*C2C_{32\times 32}*C2C_{32\times 32}\\ F_{8\times 32}^1=D2C_{32\times 32}*C2C_{32\times 32}*C2C_{32\times 32}*C2C_{32\times 32}\\ F_{8\times 32}^2=D2C_{32\times 32}*C2C_{32\times 32}*C2C_{32\times 32}\\ F_{8\times 32}^3=D2C_{32\times 32}*C2C_{32\times 32}\\ F_{8\times 32}^4=D2C_{32\times 32}\end{array};$

对进行计算，将得到的矩阵中奇数变成 1，偶数变成0；为关于当前32位并行数据的参数矩阵；

令$D2C_{32\times 32}^{32}=\left(\begin{array}{c}{F}_{8\times 32}^1\\ F_{8\times 32}^2\\ F_{8\times 32}^3\\ F_{8\times 32}^4\end{array}\right)$

得到32位并行的当前CRC值与前一级CRC值和当前32位并行数据输 入的关系$C^{32}=C^0*C2C_{32\times 32}^{32}\oplus D^{32}*D2C_{32\times 32}^{32},$其中D³²＝[D¹,D²,D³,D⁴]。

再进一步，步骤6)中，将关系表达式，

$C^{32}=C^0*C2C_{32\times 32}^{32}\oplus D^{32}*D2C_{32\times 32}^{32};$

按照步骤4)和步骤5)的方法迭代计算最终得到128并行数据的当前 CRC值C¹²⁸与前一级CRC值C⁰和当前128位数据输入的关系为，

$C^{128}=C^0*C2C_{32\times 32}^{128}\oplus D^{128}*D2C_{128\times 32}^{128};$

其中，为关于C⁰的参数矩阵，为关于D¹²⁸的参数矩阵。 与现有技术相比，本发明具有以下有益的技术效果：

本发明所述的一种用于128位并行数据校验矩阵生成方法，该方法提供 了直接对128并行数据进行CRC编解码的校验矩阵，从而避免使用延时较 大的级联结构，提高了128位并行数据的CRC编解码效率，实现高速串行 通信中接收或发送数据的实时校验。基于该校验矩阵的CRC电路可以用于 PCIe3.0物理层中的128位并行数据的实时CRC校验，保证了数据的高效 率传输。

附图说明

图1为本发明的校验矩阵生成方法流程图。

具体实施方式

下面结合具体的实施例对本发明做进一步的详细说明，所述是对本发明 的解释而不是限定。

本发明的目的在于通过使用校验矩阵对128位并行数据直接进行CRC 编解码，避免使用级联结构的CRC编解码方法，从而提高128位并行数据 的CRC编解码效率。

本发明所述的用于128位并行数据的CRC校验矩阵生成方法包括如下 步骤：

1)根据串行编码CRC的编解码原理，可知当前CRC值与当前数据输 入和前一级CRC值的关系为(其中为第j+1次数 据输入后的第i+1位CRC值，为第j次数据输入后的第i位CRC值，g_i+1为CRC生成多项式中第i+1位的系数，d_j+1为第j+1次的数据输入，为第j 次数据输入后的第31位CRC值，j为自然数，i＝0,1...31)。

根据IEEE802.3中的CRC-32所规定的CRC-32生成多项式 G(x)＝x³²+x²⁶+x²³+x²²+x¹⁶+x¹²+x¹¹+x¹⁰+x⁸+x⁷+x⁵+x⁴+x²+x+1，知g_i对应值 g₃₁＝0，g₃₀＝0…g₀＝1。

2)由步骤1)的迭代关系可推导出8位并行数据输入的当前CRC值与 前一级CRC值和当前8位并行数据输入的关系为 $c_i^1=x_{31}{c}_{31}^0\oplus x_{30}{c}_{30}^0\oplus \mathrm{...}{x}_i{c}_i^0\oplus \mathrm{...}{x}_0{c}_0^0\oplus y_7{d}_7^1\mathrm{...}\oplus y_j{d}_j^1\mathrm{...}\oplus y_0{d}_0^1,$其中为当前CRC值的第 i位，为前一级CRC值的第i位(i＝0,1...31，j＝0,1...7)，为当前的数据 输入的第j位(其中x_i和y_j为表达式 $c_i^1=x_{31}{c}_{31}^0\oplus x_{30}{c}_{30}^0\oplus \mathrm{...}{x}_i{c}_i^0\oplus \mathrm{...}{x}_0{c}_0^0\oplus y_7{d}_7^1\mathrm{...}\oplus y_j{d}_j^1\mathrm{...}\oplus y_0{d}_0^1$中和的参数，由 IEEE802.3中的CRC-32生成多项式决定)。

由步骤1)所述关系式迭代得到的8位并行数据输入的当前CRC值与 前一级CRC值和当前8位数据输入数值的关系，结果如下：

$c_{31}^1=c_{29}^0\oplus c_{23}^0\oplus d_2^1$

$c_{30}^1=c_{31}^0\oplus c_{28}^0\oplus c_{22}^0\oplus d_3^1\oplus d_0^1$

…

$c_0^1=c_{30}^0\oplus c_{24}^0\oplus d_7^1\oplus d_1^1$

3)设由步骤2)得到的8位并行数据输入的当前CRC值为 则将步骤2)包含参数x_i与y_j的带入到列向量C^1T中，(其中i＝0,1...31，j＝0,1...7)，可得

$\left(\begin{array}{c}{c}_{31}^1=x_{31}{c}_{31}^0\oplus x_{30}{c}_{30}^0\oplus \mathrm{...}{x}_i{c}_i^0\oplus \mathrm{...}{x}_0{c}_0^0\oplus y_7{d}_7^1\mathrm{...}{y}_j{d}_j^1\mathrm{...}\oplus y_0{d}_0^1\\ c_{30}^1=x_{31}{c}_{31}^0\oplus x_{30}{c}_{30}^0\oplus \mathrm{...}{x}_i{c}_i^0\oplus \mathrm{...}{x}_0{c}_0^0\oplus y_7{d}_7^1\mathrm{...}\oplus y_j{d}_j^1\mathrm{...}\oplus y_0{d}_0^1\\ \mathrm{...}\\ c_i^1=x_{31}{c}_{31}^0\oplus x_{30}{c}_{30}^0\oplus \mathrm{...}{x}_i{c}_i^0\oplus \mathrm{...}{x}_0{c}_0^0\oplus y_7{d}_7^1\mathrm{...}\oplus y_j{d}_j^1\mathrm{...}\oplus y_0{d}_0^1\\ \mathrm{...}\\ c_0^1=x_{31}{c}_{31}^0\oplus x_{30}{c}_{30}^0\oplus \mathrm{...}{x}_i{c}_i^0\oplus \mathrm{...}{x}_0{c}_0^0\oplus y_7{d}_7^1\mathrm{...}\oplus y_j{d}_j^1\mathrm{...}\oplus y_0{d}_0^1\end{array}\right)$

按照上式对应关系提取出参数x_i和y_j，得到一个32x40的矩阵CD_40×32^T， 转置后得到40x32的矩阵CD_40×32，将CD_40×32按照x_i和y_j分割开，得到两个分 别关于前一级CRC值和当前数据输入值的参数 矩阵C2C_32×32和D2C_8×32；

提取得到的矩阵CD_40×32为

其中前32行为参数矩阵C2C_32×32，后8行为参数矩阵D2C_8×32。

4)由步骤3)知，步骤3)中所述的8位并行数据输入的当前CRC值 根据C¹、C⁰和D¹之间的关系，可直接得到输入 两次8位数据，即输入16位并行数据后的当前CRC值 $C^2=C^1*C2C_{32\times 32}\oplus D^2*D2C_{8\times 32}=(C^0*C2C_{32\times 32}\oplus D^1*D2C_{8\times 32})*C2C_{32\times 32}\oplus D^2*D2C_{8\times 32},$同理，继续迭代两次后得到输入四次8位数据，即输入32位并行数据后的 CRC值，为将异或关系转换为数学中相加，可 得到C⁴与C⁰以及D¹、D²、D³、D⁴(C⁰为前一级的CRC值，D¹、D²、 D³、D⁴分别为第一、二、三、四次输入的8位数据)的关系， C⁴＝C⁰*C2C_32×32*C2C_32×32*C2C_32×32*C2C_32×32+D¹*D2C_8×32*C2C_32×32*C2C_32×32*C2C_32×32+ D²*D2C_8×32*C2C_32×32*C2C_32×32+D³*D2C_8×32*C2C_32×32+D⁴*D2C_8×32

表达式中C2C_32×32*C2C_32×32*C2C_32×32*C2C_32×32为C⁰的参数矩阵， D2C_8×32*C2C_32×32*C2C_32×32*C2C_32×32为D¹的参数矩阵，D2C_8×32*C2C_32×32*C2C_32×32为 D²的参数矩阵，D2C_8×32*C2C_3×232为D³的参数矩阵，D2C_8×32为D⁴的参数矩 阵。

5)根据步骤4)中C4表达式，令C⁰的参数矩阵为D¹的参数 矩阵为D²的参数矩阵为D³的参数矩阵为D⁴的参数矩阵为 则

$C2C_{32\times 32}^{32}=C2C_{32\times 32}*C2C_{32\times 32}*C2C_{32\times 32}*C2C_{32\times 32}$

$F_{8\times 32}^1=D2C_{32\times 32}*C2C_{32\times 32}*C2C_{32\times 32}*C2C_{32\times 32}$

$F_{8\times 32}^2=D2C_{32\times 32}*C2C_{32\times 32}*C2C_{32\times 32}$

$F_{8\times 32}^3=D2C_{32\times 32}*C2C_{32\times 32}$

$F_{8\times 32}^4=D2C_{32\times 32}$

对进行计算，将得到的矩阵中奇数变成 1，偶数变成0。为关于当前32位并行数据的参数矩阵。

令$D2C_{32\times 32}^{32}=\left(\begin{array}{c}{F}_{8\times 32}^1\\ F_{8\times 32}^2\\ F_{8\times 32}^3\\ F_{8\times 32}^4\end{array}\right)$

得到当前CRC值与前一级CRC值和当前32位并行数据的关系

$C^{32}=C^0*C2C_{32\times 32}^{32}\oplus D^{32}*D2C_{32\times 32}^{32}(D^{32}=[D^1,D^2,D^3,D^4\left]\right).$

计算结果矩阵为：

将上面的矩阵中奇数变成1，偶数变成0。矩阵化为

计算并将其纵向合并的到32x32的矩阵为

将上面的矩阵中奇数变成1，偶数变成0。矩阵化为

6)将公式按照步骤4)和步骤5)的方法 迭代计算最终得到128并行数据的当前CRC值C¹²⁸与前一级CRC值C⁰和当 前128位数据输入的关系，$C^{128}=C^0*C2C_{32\times 32}^{128}\oplus D^{128}*D2C_{128\times 32}^{128}$(其中为 关于C⁰的参数矩阵，为关于D¹²⁸的参数矩阵)。

推导得出校验矩阵为

矩阵为

7)将步骤6)得到的关系矩阵用于128并行数据编码的实时校验。