网上唯一一篇请解清楚了FPGA实现并行CRC的文章

并行 CRC 发生器

每种现代通信协议都使用一种或多种错误检测算法。循环冗余校验 (CRC) 是迄今为止最流行的算法。CRC 属性由生成多项式的长度和系数定义。协议规范通常以十六进制或多项式表示法定义 CRC。例如，USB 2.0 协议中使用的 CRC5 在十六进制表示法中表示为 0x5，或在多项式中表示为 G(x)=x 5 +x 2 +1。此 CRC 在硬件中实现为移位寄存器，如下图所示。

问题在于，在许多情况下，移位寄存器实现并不理想。它只允许每个时钟计算一位。如果设计有 32 位宽的数据路径，这意味着每个时钟 CRC 模块都必须计算 32 位数据的 CRC，则此方案将不起作用。必须以某种方式将此串行移位寄存器实现转换为并行 N 位宽电路，其中 N 是设计数据路径宽度，以便每个时钟处理 N位。

我开始研究有关并行 CRC 计算方法的现有文献，发现只有少数几篇论文（[2]、[3]）讨论了这个问题。大多数资料都是学术性的，侧重于问题的理论方面。它们太不切实际，无法在软件或硬件中实现以快速生成代码。

我想出了以下方案，并用它来构建在线并行 CRC 生成器工具。下面是我使用上述 USB CRC5 的步骤的描述。

（1）我们假设 N=数据宽度，M=CRC 宽度。例如，如果我们要为 4 位数据路径生成并行 USB CRC5，则 N=4，M=5。

（2）使用给定的多项式或十六进制表示法实现串行 CRC 生成器例程。使用任何编程语言或脚本都可以轻松实现：C、Java、Perl、Verilog 等。

（3）并行 CRC 实现是 N 位数据输入以及 M 位当前状态 CRC 的函数，如上图所示。我们将构建两个矩阵：当 N=0 时，Mout（下一状态 CRC）是 Min（当前状态 CRC）的函数；当 M=0 时，Mout 是 Nin 的函数。

（4）使用（2）中的例程计算 Min=0 时 N 个值的 CRC。每个值都是独热编码的，也就是说只有一个位被设置。对于 N=4，值为 0x1、0x2、0x4、0x8。Mout = F(Nin,Min=0)

（5）构建 NxM 矩阵，每行按递增顺序包含（3）的结果。例如，第 1 行包含输入 = 0x1 的结果，第 2 行包含输入 = 0x2 的结果，等等。输出为 M 位宽，即所需的 CRC 宽度。以下是 N=4 的 USB CRC5 矩阵。

（6）这个矩阵中的每一列（这也是有趣的部分）代表一个输出位 Mout[i]，它是 Nin 的函数。

（7）使用（3）中的例程计算 Nin=0 时 M 值的 CRC。每个值都是独热编码的，也就是说只有一个位被设置。对于 M=5，值为 0x1、0x2、0x4、0x8、0x10。Mout = F(Nin=0,Min)

（8）构建 MxM 矩阵，每行按递增顺序包含（7）中的结果。以下是 N=4 的 USB CRC5 矩阵

（9）现在，为每个 Mout[i] 位建立一个方程：第 [i] 列中的所有 Nin[j] 和 Min[k] 位都参与方程。参与的输入一起进行异或运算。

Mout[0] = 最小值[1]^最小值[4]^Nin[0]^Nin[3]

Mout[1] = Min[2]^Nin[1]

Mout[2] = Min[1]^Min[3]^Min[4]^Nin[0]^Nin[2]^Nin[3]

Mout[3] = Min[2]^Min[4]^Nin[1]^Nin[3]

Mout[4] = Min[0]^Min[3]^Nin[2]

这就是我们的并行 CRC。

我估计自从 40 多年前发明 CRC 算法以来，已经有人想出了这种方法。我只是找不到它，然后“重新发明轮子”。

用户经常会问，为什么他们实现的串行 CRC 与使用相同多项式生成的并行 CRC 不一致。原因如下：
– 串行 CRC 中的位顺序与数据输入并行 CRC 的方式不同
– 输入数据位被反转
– LFSR 的初始化方式不同。许多协议都使用 Fs 来初始化它，而并行 CRC 中也是如此。

---

一种实用的并行 CRC 生成方法（更详细的说明）

你是否了解循环冗余检验 (CRC) 的机制，以至于能够构建一个由任意 CRC 生成多项式描述的定制并行 CRC 电路？本文介绍了一种生成并行 CRC 的 Verilog 或 VHDL 代码的实用方法。其结果是快速生成适用于任意多项式和数据宽度的并行 CRC 代码。

大多数电气和计算机工程师都熟悉循环冗余检验 (CRC)。许多人知道它用于通信协议中以检测位错误，实际上它本质上是模-2 长除法操作的余数。有些人对 CRC 有更深入的了解，知道它是通过使用触发器和 XOR 门实现的线性反馈移位寄存器 (LFSR)。他们可能使用过在线工具或现有示例来为设计生成并行 CRC 代码。然而，很少有工程师能充分理解 CRC 的机制，以便构建由任意 CRC 生成多项式描述的定制并行 CRC 电路。你呢？

在本文中，我将介绍一种生成并行 CRC 的 Verilog 或 VHDL 代码的实用方法。该方法允许快速生成适用于任意多项式和数据宽度的并行 CRC 代码。我还将简要描述其他有趣的方法，并提供更多相关信息。

那么，我为什么要讨论并行 CRC 呢？现有的许多工具可以生成代码，并且有很多流行 CRC 多项式的示例。然而，理解其基本原理通常是有益的，以便实现定制电路或对现有电路进行优化。这是每位从事逻辑设计的工程师都应该理解的主题。

CRC 概述

每个现代通信协议都使用一种或多种错误检测算法。CRC 是其中最流行的。CRC 的属性由生成多项式的长度和系数定义。协议规范通常以十六进制或多项式表示法定义 CRC。例如，在 USB 协议中使用的 CRC5 以十六进制表示为 0x5，或以多项式表示法为 (G(x) = x^5 + x^2 + 1。

该 CRC 通常在硬件中实现为具有串行数据输入的线性反馈移位寄存器 (LFSR)（见图 1）。

在许多情况下，串行 LFSR 实现的 CRC 对于给定设计并不理想。由于串行数据输入，它每个时钟周期只允许计算一个数据位的 CRC。如果设计有一个 N 位数据路径——这意味着每个时钟周期 CRC 模块必须计算 N 位数据的 CRC——则串行 CRC 将无法工作。一个例子是 USB 2.0，它在物理层以 480 MHz 传输数据。典型的 USB PHY 芯片与处理协议的芯片之间具有 8 位或 16 位数据接口。检查或生成 CRC 的电路必须在该速度下工作。

Listing 1—This Verilog module implements parallel USB CRC5 with 4-bit data
//==========================================================================
// Verilog module that implements parallel USB CRC5 with 4-bit data
//==========================================================================
module crc5_parallel(
input [3:0] data_in,
output reg[4:0] crc5,
input rst,
input clk);
// LFSR for USB CRC5
function [4:0] crc5_serial;
input [4:0] crc;
input data;
begin
crc5_serial[0] = crc[4] ^ data;
crc5_serial[1] = crc[0];
crc5_serial[2] = crc[1] ^ crc[4] ^ data;
crc5_serial[3] = crc[2];
crc5_serial[4] = crc[3];
end
endfunction
// 4 iterations of USB CRC5 LFSR
function [4:0] crc_iteration;
input [4:0] crc;
input [3:0] data;
integer i;
begin
crc_iteration = crc;
for(i=0; i<4; i=i+1)
crc_iteration = crc5_serial(crc_iteration, data[3-i]);
end
endfunction
always @(posedge clk, posedge rst) begin
I f(rst) begin
crc5 <= 5'h1F;
end
else begin
crc5 <= crc_iteration(crc5,data_in);
end
end
endmodule
//==========================================================================

我遇到的另一个更为复杂的应用涉及计算在 288 位宽的内存控制器上写入和读取数据的 64 位 CRC（两个具有 ECC 位的 64 位 DDR DIMM）。为了实现更高的吞吐量，CRC 的串行 LFSR 实现必须转换为一个并行 N 位宽的电路，其中 N 是设计的数据路径宽度，以便每个时钟周期处理 N 位。这就是并行 CRC 实现，本文将对此进行讨论。图 2 是并行 CRC 的简化框图。

尽管 CRC 是在近半个世纪前发明的并已广泛应用，但它仍然在研究界引发了很多兴趣。关于不同并行 CRC 实现的研究论文和专利不断涌现，这些研究提供了速度和逻辑面积的改进。我在查找可用文献和网络资源时发现了一些关于硬件描述语言 (HDL) 的并行 CRC 计算方法的论文（请参见本文末尾的资源部分）。然而，大多数论文都是学术性的，侧重于并行 CRC 生成的理论方面，实用性较低，不适合快速生成具有任意数据和多项式宽度的 CRC HDL 代码。该方法的另一个要求是，并行 CRC 生成器必须能够接受任意数据宽度（而不仅仅是 2 的幂），以便具有实用价值。

回到 USB 2.0 CRC5 的例子，适合用于多项式宽度为 5 的并行 CRC 的数据宽度是 11，因为使用 CRC5 的 USB 数据包是 16 位的。另一个例子是具有 128 位数据路径的 16 通道 PCI Express（16 个 8 位符号）。由于数据包的开始是 K 码符号，并不参与 CRC 计算，因此并行 CRC 数据宽度为 120 位。

在深入讨论并行 CRC 主题之前，我将简要回顾模-2 多项式算术。多项式以以下形式表示：

多项式的加法和减法操作使用逐位异或（XOR）。例如：

• 多项式乘以二是左移，除以二的无符号除法是右移。模-2 多项式除法与整数的长除法实现方式相同。
• 循环左移和右移分别是模 (2 mod 2n – 1)的乘法和除法。

Listing 2—This Verilog function implements the serial USB CRC5.
//=============================================================
// Verilog function that implements serial USB CRC5
//=============================================================
function [4:0] crc5_serial;
input [4:0] crc;
input data;
begin
crc5_serial[0] = crc[4] ^ data;
crc5_serial[1] = crc[0];
crc5_serial[2] = crc[1] ^ crc[4] ^ data;
crc5_serial[3] = crc[2];
crc5_serial[4] = crc[3];
end
endfunction
//============================================================

Listing 3—This pseudocode is an example of CRCPARALLEL.
//=============================================================
routine CRCparallel(Nin, Min)
Mout = Min
for(i=0;i<N;i++)
Mout = CRCserial(Nin , Mout)
return Mout
//=============================================================

并行CRC发生器

我将从一个生成并行 USB CRC5 的 Verilog 模块开始讨论，数据宽度为 4 位（见列表 1）。综合工具将根据目标 FPGA 或 ASIC 技术生成电路。然而，本文的目的是解释如何使用 XOR 门和触发器来获取一个并行 CRC 电路。

接下来，我将描述我在多个项目中使用的生成并行 CRC 的实用方法。该方法适用于任何多项式和数据大小，与目标技术无关。随后，我还将介绍其他具有一些有用特性的实现方法。

逐步描述将伴随一个关于 USB CRC5 多项式 G(x)=x5+x2+1G(x) = x^5 + x^2 + 1G(x)=x5+x2+1 和 4 位数据宽度的并行 CRC 生成示例。该方法借鉴了 Guiseppe Campobello 等人在论文《Parallel CRC Realization》中描述的理论，以及 G. Albertango 和 R. Sisto 在《Parallel CRC Generation》中的研究，利用简单的串行 CRC 生成器和 CRC 的线性特性来构建并行 CRC 电路。

步骤

步骤 1：设定 $N$ 为数据宽度，$M$ 为 CRC 多项式宽度。对于 4 位数据路径的并行 USB CRC5，$N=4$ 和 $M=5$。

步骤 2：实现给定多项式的串行 CRC 生成例程。这是一个简单的过程，可以使用不同的编程语言或脚本（例如 C、Java、Verilog 或 Perl）完成。你可以使用列表 2 中的 Verilog 函数 crc5_serial 进行串行 USB CRC5。将此例程称为 CRCSERIAL。你还可以构建一个例程 CRCparallel(Nin, Min)，它简单地调用 CRCSERIAL $N$ 次（数据位的数量）并返回 $MOUT$。列表 3 中的伪代码是 CRCPARALLEL 的示例。

步骤 3：并行 CRC 实现是 $N$ 位数据输入和 $M$ 位当前 CRC 状态的函数，如图 2 所示。我们将构建两个矩阵。矩阵 $H1$ 描述 $MOUT$（下一个 CRC 状态）作为 $NIN$（输入数据）的函数，当 $MIN=0$ 时。因此，$MOUT=CRCPARALLEL(NIN,MIN=0)$，矩阵 $H1$ 的大小为 $[N\times M]$。矩阵 $H2$ 描述 $MOUT$ 作为 $MIN$（当前 CRC 状态）的函数，当 $NIN=0$ 时。因此，$MOUT=CRCPARALLEL(NIN=0,MIN)$，矩阵 $H2$ 的大小为 $[M\times M]$。

步骤 4：构建矩阵 $H1$。使用步骤 2 中的 CRCPARALLEL 例程，计算当 $MIN=0$ 时 $NIN$ 的 $N$ 个值的 CRC。这些值采用一位热编码（one-hot encoding）——即每个 $NIN$ 值仅设置一个位。对于 $N=4$，这些值为十六进制的 0x1、0x2、0x4、0x8。表 1 显示了 USB CRC5 的矩阵 $H1$ 值，$N=4$。

步骤 5：构建矩阵 $H2$。使用步骤 2 中的 CRCPARALLEL 例程，计算当 $NIN=0$ 时 $MIN$ 的 $M$ 个值的 CRC。这些值也采用一位热编码。对于 $M=5$，$MIN$ 值为十六进制的 0x1、0x2、0x4、0x8、0x10。表 2 显示了 USB CRC5 的矩阵 $H2$ 值，$N=4$。

步骤 6：你准备好构建并行 CRC 方程。矩阵 $H1$ 的列 $i$ 中每个设置的位 $j$——这是该方法的关键部分——参与位 $MOUT[i]$ 的并行 CRC 方程，作为 $NIN[j]$。同样，矩阵 $H2$ 的列 $i$ 中每个设置的位 $j$ 参与位 $MOUT[i]$ 的并行 CRC 方程，作为 $MIN[j]$。

所有参与的输入 $MIN[j]$ 和 $NIN[j]$ 形成 $MOUT[i]$ 并被一起 XOR 运算。对于 USB CRC5，$N=4$ 时的并行 CRC 方程如下：

$MOUT$ 是并行 CRC 的实现。我使用表 1 和表 2 来推导方程。该方法之所以有效，是因为我们构建矩阵 $H1$ 和 H

$H2$ 的方式，使得行是线性无关的。我们还利用了 CRC 是线性运算的事实：

这意味着在进行 CRC 计算时，输入数据的线性组合对应于输出 CRC 的线性组合。具体而言，每个参与的输入 $NIN[j]$ 和 $MIN[j]$ 可以通过 XOR 运算结合在一起，形成新的 CRC 状态 $MOUT[i]$。这种线性特性使得我们能够有效地利用矩阵形式来简化并行 CRC 的实现。通过这种方法，可以快速生成适用于各种数据宽度和多项式的并行 CRC 代码。

未完待续