在Virtex-5 FPGA中使用CRC硬模块
2008-12-12 14:40:55
来源：《半导体器件应用》2008年12月刊
1 前言
数据损坏是与数据传输和存储有关的首要问题。只要是在通道上传输数据，就总会有出现某些错误的有限概率。
关键是接收模块要能区分无错消息和有错消息。检错有多种方法，其中大多数都是专门为此目的引入冗余位。数据通信中常用的检错方法包括奇偶码、汉明码和循环冗余校验（CRC），其中 CRC 使用最广泛。
CRC 根据一个给定的数据位组算出，然后在传输或存储之前附加到数据帧尾部。接收或检索到帧后，对其内容重新计算 CRC，以此来验证其有效性，确保数据无误。
本文简述 CRC 计算所依据的原理，并且探讨用线性反馈移位寄存器实现其硬件的方法。然后，我们把注意力转向 Xilinx@VirtexTM-5 LXT／SXT 器件中存在的 CRC 硬模块。
2 原理
加法和减法运算是用模 2 算法执行，也就是说，这两种运算与“异或”（XOR）运算相同。除了没有进位，多项式算法中的两数相加与普通二进制算法中的多数相加相同。
例如：二进制消息流 11001O11 表达为 x7+x6+x3+x+1。传输点与接收点约定一个固定多项式，称为生成器多项式，这是 CRC 计算的关键参数。
将数据解释为一个多项式的系数，用一个给定的生成器多项式除这些系数。除得的余数就是 CRC。假设有一个m 位消息序列和一个 r 阶生成器多项式，发射器创建一个 n 位（n=m+r）序列，称为帧校验序列（FCS），使这个（m+r）位合成帧可以被一个预先确定的序列整除。
发射器将 r 个 0 位附加到 m 位的消息，并且用生成器多项式除所得 m+r-1 阶多项式。这样可得到一个阶数等于或小于（r-1）的余数多项式。该余数多项式有 r 个系数，这些系数形成校验和。将商丢弃。传输的数据是原 m 位消息后附 r 位校验和。
在接收器上，可以按以下两种标准方法之一评估所接收数据的有效性：
(1) 对收到的前 m 个位再次计算校验和，然后与收到的校验和（收到的后 r 个位）进行比较；
(2) 对收到的全部（m+r）个位计算校验和，然后与一个 0 余数进行比较。
为了说明第二种方法如何得出 0 余数，我们做如下约定：
M=消息的多项表达式；
R=发射器上所算得余数的多项表达式；
G=生成器多项式；
Q=用 G 除 M 得到的商。
传输的数据对应于多项式 Mxr-R。变量 xr 表示消息为容纳校验和而产生的一个r位移位。
我们知道：
Mxr=QG+R
在发射器上将校验和 R 附加到消息中相当于从消息中减去余数。于是，传输的数据变为 Mxr-R=QG，这显然是 G 的倍数。这就是我们在第二种情况下得到 0 余数的过程。
不过，这一过程对所传输数据中首 0 位和尾 0 位的个数不敏感。换句话说，无论消息插入还是删除尾 0 位，余数都保持为 0，从而使错误漏检，这表明不会复原成同样的位序列。下面介绍一种克服这一缺点的变通办法。
3 剩余法
实际上，校验和经过反演后才附加到消息中。这就使接收器上算出的余数（超过 m+r 位）不为 0。在这类情况下，接收器上得到的余数是一个固定值，称为多项式的剩余值。
假定 % 符号在下列表达式中表示模运算。
对于未经反演附加校验和的情况：
(Mxr-R)xr％G=0
在这种情况下，接收器会执行与发射器一样的移位运算。
现在，考虑校验和在发射器上经反演后附加到消息流的情况：
(Mxr-Rc)xr％G
其中，Rc 表示经过反演的校验和。
还可以将其写成：
(Mxr-R+(xr-1+…+x+1))xr％G
一个位的反码与其对 1 异或运算的结果相同。这里的 + 号表示模 2 算法中的加法（请注意，在模 2 算法中，加法和减法运算相同）。
在这种情况下，余数与以下表达式相同：
(xr-1+…+x+1)xr％G
对于给定的生成器多项式来说，此表达式的计算结果将是一个常数。
最常用的 CRC 32 生成器多项式是：
G(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1该式在十六进制中是 04C11DB7。
与 CRC-32 对应的常数剩余值在十六进制中是 C704DD7B。对于给定的生成器多项式 G 来说，无论在输入端提供何种数据样式，剩余值仍为常数。
4 硬件实现
CRC 校验和的计算是多项式除法过程。在硬件中实现该过程需要使用一个移位寄存器（亦称 CRC 寄存器）。
该移位寄存器的长度与生成器多项式的阶数相同。
CRC 计算过程如下：
(1) 初始化CRC寄存器；
(2) 持续获取消息位，直到获得所有消息位。如果CRC 寄存器中的高阶位是 1，则向左移一位，并且将其结果与 G 进行异或运算。否则，仅向左移一位。
对给定消息完成所有这些步骤后，CRC 寄存器中剩下的就是余数。
可以用一种称为线性反馈移位寄存器（LFSR）的电路执行这些步骤。图 1 所示为用 CRC32 多项式计算 CRC 的 LFSR 实现方法。请注意，异或门的布局取决于生成器多项式中项值为 1 的对应项的系数。图中的编号方框各代表一个存储元件（触发器）。
5 CRC 模块
CRC 的硬件实现使用一个简单的 LFSR。这种电路虽然实现起来简单，但对于一个 n 位数据流来说，要占用 n 个时钟周期来计算 CRC 值。在必须以较高速度处理数据帧的高速数据网络应用中，这样的延迟是无法忍受的。这类高速网络应用迫切需要对并行数据流实现 CRC 生成和校验。
Virtex-5 LXT／SXT 器件中实现的 CRC 模块可帮助设计人员加速校验和计算。
Virtex-5 LXT／SXT 器件中的 CRC 硬模块基于 CRC32 多项式。Virtex-5 FPGA 含有 CRC32 和 CRC64 两种硬模块，能以一个时钟周期的延迟 4 位和 8 位数据输出生成 CRC。其界面简单易用。硬模块对给定的消息流起着 CRC 计算器的作用，同时提供一些针对 CRC 的参数作为输入。CRC 的比较功能已经超出硬模块的范围，应集成到FPGA 架构中。
FPGA 中的每个 CRC 硬模块异步计算一个 32 位校验和。图 2 是说明硬模块架构的模块框图。CRC 硬模块提供一个位反演和字节反转的输出。
图 3 所示为 CRC 硬模块的应用概况。在发射器上，CRC 经计算后附加到给定数据包的尾部。在接收器上，对连带发射器所附加的 CRC 一起接收到的整个数据包重新计算 CRC。
所收数据包的有效性用剩余法来确定。对于本例中的 CRC32 多项式来说，剩余值的计算结果将是十六进制的 1CDF4421，这其实就是 C704DDB7 的位反演和字节反转值。字节反转和位反演的概念如图 4 所示。
图 5 所示为正常 CRC 运算的波形。
我们还提供一个 LogiCORETM CRC 向导，其中为Virtex-5 器件中的 CRC 硬模块提供一个 LocalLink 封装。其内核还提供了一个说明如何使用 CRC 硬模块的设计实例。此外，内核提供了各种选项，如流水线处理、补数计算和转置。
有关详情，可访问www. xilinx. com/cn/crcwizard。
6 结论
Xilinx FPGA 中的 CRC 模块使设计人员能够轻松地将检错机制加入到各种设计中。可以用 CORE GeneratorTM 软件中提供的 CRC Wizard IP 加入符合不同协议（如 Aurora和 PCIExpress）的检错功能。
有关 Virtex-5 FPGA 中的嵌入式 CRC 模块的详情，参见《Virtex-5RocketIOTM GTP 收发器用户指南（UGl96）》，其网址为：WWW. xilinx. com/cn/bvdocs/userguides/ugl96. pdf。
数据损坏是与数据传输和存储有关的首要问题。只要是在通道上传输数据，就总会有出现某些错误的有限概率。
关键是接收模块要能区分无错消息和有错消息。检错有多种方法，其中大多数都是专门为此目的引入冗余位。数据通信中常用的检错方法包括奇偶码、汉明码和循环冗余校验（CRC），其中 CRC 使用最广泛。
CRC 根据一个给定的数据位组算出，然后在传输或存储之前附加到数据帧尾部。接收或检索到帧后，对其内容重新计算 CRC，以此来验证其有效性，确保数据无误。
本文简述 CRC 计算所依据的原理，并且探讨用线性反馈移位寄存器实现其硬件的方法。然后，我们把注意力转向 Xilinx@VirtexTM-5 LXT／SXT 器件中存在的 CRC 硬模块。
2 原理
加法和减法运算是用模 2 算法执行，也就是说，这两种运算与“异或”（XOR）运算相同。除了没有进位，多项式算法中的两数相加与普通二进制算法中的多数相加相同。
例如：二进制消息流 11001O11 表达为 x7+x6+x3+x+1。传输点与接收点约定一个固定多项式，称为生成器多项式，这是 CRC 计算的关键参数。
将数据解释为一个多项式的系数，用一个给定的生成器多项式除这些系数。除得的余数就是 CRC。假设有一个m 位消息序列和一个 r 阶生成器多项式，发射器创建一个 n 位（n=m+r）序列，称为帧校验序列（FCS），使这个（m+r）位合成帧可以被一个预先确定的序列整除。
发射器将 r 个 0 位附加到 m 位的消息，并且用生成器多项式除所得 m+r-1 阶多项式。这样可得到一个阶数等于或小于（r-1）的余数多项式。该余数多项式有 r 个系数，这些系数形成校验和。将商丢弃。传输的数据是原 m 位消息后附 r 位校验和。
在接收器上，可以按以下两种标准方法之一评估所接收数据的有效性：
(1) 对收到的前 m 个位再次计算校验和，然后与收到的校验和（收到的后 r 个位）进行比较；
(2) 对收到的全部（m+r）个位计算校验和，然后与一个 0 余数进行比较。
为了说明第二种方法如何得出 0 余数，我们做如下约定：
M=消息的多项表达式；
R=发射器上所算得余数的多项表达式；
G=生成器多项式；
Q=用 G 除 M 得到的商。
传输的数据对应于多项式 Mxr-R。变量 xr 表示消息为容纳校验和而产生的一个r位移位。
我们知道：
Mxr=QG+R
在发射器上将校验和 R 附加到消息中相当于从消息中减去余数。于是，传输的数据变为 Mxr-R=QG，这显然是 G 的倍数。这就是我们在第二种情况下得到 0 余数的过程。
不过，这一过程对所传输数据中首 0 位和尾 0 位的个数不敏感。换句话说，无论消息插入还是删除尾 0 位，余数都保持为 0，从而使错误漏检，这表明不会复原成同样的位序列。下面介绍一种克服这一缺点的变通办法。
3 剩余法
实际上，校验和经过反演后才附加到消息中。这就使接收器上算出的余数（超过 m+r 位）不为 0。在这类情况下，接收器上得到的余数是一个固定值，称为多项式的剩余值。
假定 % 符号在下列表达式中表示模运算。
对于未经反演附加校验和的情况：
(Mxr-R)xr％G=0
在这种情况下，接收器会执行与发射器一样的移位运算。
现在，考虑校验和在发射器上经反演后附加到消息流的情况：
(Mxr-Rc)xr％G
其中，Rc 表示经过反演的校验和。
还可以将其写成：
(Mxr-R+(xr-1+…+x+1))xr％G
一个位的反码与其对 1 异或运算的结果相同。这里的 + 号表示模 2 算法中的加法（请注意，在模 2 算法中，加法和减法运算相同）。
在这种情况下，余数与以下表达式相同：
(xr-1+…+x+1)xr％G
对于给定的生成器多项式来说，此表达式的计算结果将是一个常数。
最常用的 CRC 32 生成器多项式是：
G(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1该式在十六进制中是 04C11DB7。
与 CRC-32 对应的常数剩余值在十六进制中是 C704DD7B。对于给定的生成器多项式 G 来说，无论在输入端提供何种数据样式，剩余值仍为常数。
4 硬件实现
CRC 校验和的计算是多项式除法过程。在硬件中实现该过程需要使用一个移位寄存器（亦称 CRC 寄存器）。
该移位寄存器的长度与生成器多项式的阶数相同。
CRC 计算过程如下：
(1) 初始化CRC寄存器；
(2) 持续获取消息位，直到获得所有消息位。如果CRC 寄存器中的高阶位是 1，则向左移一位，并且将其结果与 G 进行异或运算。否则，仅向左移一位。
对给定消息完成所有这些步骤后，CRC 寄存器中剩下的就是余数。
可以用一种称为线性反馈移位寄存器（LFSR）的电路执行这些步骤。图 1 所示为用 CRC32 多项式计算 CRC 的 LFSR 实现方法。请注意，异或门的布局取决于生成器多项式中项值为 1 的对应项的系数。图中的编号方框各代表一个存储元件（触发器）。
5 CRC 模块
CRC 的硬件实现使用一个简单的 LFSR。这种电路虽然实现起来简单，但对于一个 n 位数据流来说，要占用 n 个时钟周期来计算 CRC 值。在必须以较高速度处理数据帧的高速数据网络应用中，这样的延迟是无法忍受的。这类高速网络应用迫切需要对并行数据流实现 CRC 生成和校验。
Virtex-5 LXT／SXT 器件中实现的 CRC 模块可帮助设计人员加速校验和计算。
Virtex-5 LXT／SXT 器件中的 CRC 硬模块基于 CRC32 多项式。Virtex-5 FPGA 含有 CRC32 和 CRC64 两种硬模块，能以一个时钟周期的延迟 4 位和 8 位数据输出生成 CRC。其界面简单易用。硬模块对给定的消息流起着 CRC 计算器的作用，同时提供一些针对 CRC 的参数作为输入。CRC 的比较功能已经超出硬模块的范围，应集成到FPGA 架构中。
FPGA 中的每个 CRC 硬模块异步计算一个 32 位校验和。图 2 是说明硬模块架构的模块框图。CRC 硬模块提供一个位反演和字节反转的输出。
图 3 所示为 CRC 硬模块的应用概况。在发射器上，CRC 经计算后附加到给定数据包的尾部。在接收器上，对连带发射器所附加的 CRC 一起接收到的整个数据包重新计算 CRC。
所收数据包的有效性用剩余法来确定。对于本例中的 CRC32 多项式来说，剩余值的计算结果将是十六进制的 1CDF4421，这其实就是 C704DDB7 的位反演和字节反转值。字节反转和位反演的概念如图 4 所示。
图 5 所示为正常 CRC 运算的波形。
我们还提供一个 LogiCORETM CRC 向导，其中为Virtex-5 器件中的 CRC 硬模块提供一个 LocalLink 封装。其内核还提供了一个说明如何使用 CRC 硬模块的设计实例。此外，内核提供了各种选项，如流水线处理、补数计算和转置。
有关详情，可访问www. xilinx. com/cn/crcwizard。
6 结论
Xilinx FPGA 中的 CRC 模块使设计人员能够轻松地将检错机制加入到各种设计中。可以用 CORE GeneratorTM 软件中提供的 CRC Wizard IP 加入符合不同协议（如 Aurora和 PCIExpress）的检错功能。
有关 Virtex-5 FPGA 中的嵌入式 CRC 模块的详情，参见《Virtex-5RocketIOTM GTP 收发器用户指南（UGl96）》，其网址为：WWW. xilinx. com/cn/bvdocs/userguides/ugl96. pdf。
本文为哔哥哔特资讯原创文章，未经允许和授权，不得转载，否则将严格追究法律责任；
暂无评论