CRC演算程序开发外文翻译资料

英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料

流水线循环冗余校验（CRC）计算

Mathys Walma

英特尔公司

M / S JF3-211

Hillsboro，俄勒冈州，97124，

美国电子邮件：mathys.c.walma at intel.com

电话：（503）264-4706

摘要

传统的计算CRC的方法遭受收益递减。将数据宽度加倍不会使最大数据吞吐量加倍，最坏情况的时序路径会变得更慢。在传统实现方法中的各种反馈使得流水线存在问题。然而，用于高吞吐量协议的片上数据宽度不断增加。减少静态功耗方面的挑战是推动这种趋向更广泛的数据路径的一个因素。

本文讨论了一种用于流水线计算CRC的方法，例如ISO-3309 CRC32。该方法允许通过改变数据宽度和流水线级的数量独立地缩放电路频率和数据吞吐量。当管道延迟对时钟来说影响很小时，管道延迟可以通过增加管道面积来减少。此外，它允许计算输入的数据不是完整的宽度。这通常发生在分组的结尾，虽然有时数据到达突发，它可能发生在分组的中间。最后，有一个可喜的副作用是，它为我们提供了有效地更新已知的良好CRC值的能力，其中分组中的小数据子集已经改变。这是路由器中经常需要的功能，例如更新IPv4数据包中的TTL字段。

关键词：CRC，循环冗余校验，流水线，LFSR，线性反馈移位寄存器

1. 介绍

在设计芯片时，设计人员面临着平衡各种因素（如面积，静态和动态功率以及产量）的挑战。这些因素中的每一个根据目标应用而不同地加权。处理收缩的总趋势是更宽的数据路径。这是因为泄漏功率的指数增加限制了增加电路工作频率的传统方法。同时，对更多吞吐量的需求是不合理的。

继续定义通信标准，将吞吐量提高。例如，10Gbps IEEE 802.3ak在2003年被标准化，现在已经开始定义100Gbps IEEE 802.3。为了以合理的频率支持这些高吞吐量，使用大量比特的宽数据路径。CRC在几乎所有通信协议中被用作检测传输错误的有效方法。本文的重点是显示CRC吞吐量如何与数据宽度和面积成线性比例。同样，管道延迟可以近似线性地换取面积。工作频率也可以换取面积。

CRC计算通常表示为线性反馈移位寄存器（LFSR）。为了增加此计算中的并行性，通常的方法是展开串行实现。不幸的是，展开会增加最坏情况的时序路径。 每个输入比特的数量的加倍大约使每个异或门的输入的数量增加一倍，并且因此恶化延迟。 由于计算结果被反馈以计算下一个值，所以面积加倍导致最大吞吐量的倍数小于两倍。

总之，本文讨论了一种用于计算CRC的硬件架构，其提供了许多好处：

1）流水线允许添加寄存器级以便针对特定的操作频率

2）一旦获得目标操作频率，可以达到吞吐量要求缩放数据宽度

3）区域面积可以通过组合级而换取流水线等待时间，然而最大操作频率可以通过在每个级的输出处添加多路复用器而产生轻微影响

4）计算对小于输入数据宽度是直接的

5）当分组的小子集改变时修改已知的良好CRC不需要馈送整个分组通过6）可以对乱序到达的数据计算CRC可能需要迭代前三个点，以满足所需的设计要求。

II．提前准备的工作

现已经有许多关于并行化CRC计算的工作。在此我们讨论了几个已经审查过的。

在[1]中，讨论了串行实现，并对未来的吞吐量进行了外推。

在[2]中，示出了提供一些前景的流水线架构。流水线中的级数等于一次处理的位数。这导致了具有路径宽度的等待时间的增加。

在[3]中，另一种方法用于使用线性系统理论来展开串行实现。分组大小被假定为CRC输入大小的倍数。

在[4]中有一个流水线实现，但是同时处理5个不同的数据包。分组通常串行到达，因此在处理可以开始之前，必须缓冲4个分组。

在[5]中显示了用于实现可变输入宽度CRC算法的Verilog源。它还依赖于展开串行实现。随着输入宽度增加，最坏情况的延迟增加。

在[6]中，有一个Web窗体，可以生成固定的输入宽度实现常见的CRC多项式。数据输入的最大宽度为256位。随着输入宽度增加，最坏情况的延迟增加。

在[7]中，讨论了一种随着输入宽度的增加减少最坏情况的延迟的方法。使用具有较少反馈项但是也是CRC32多项式的倍数且度为123的多项式来计算CRC。在分组的末尾，对较大的多项式执行最终除法，以获得最后的CRC32结果。该实现用于并行处理8位，然而更大数量的并行位将需要更大的多项式，这可能证明是有问题的。

在[8]中，对分组数据的无序片段计算CRC。检查CRC计算，并且示出如何可以组合分组分段的CRC以形成用于整个分组的CRC。本文应用[8]的数学结果到硬件流水线实现。

III．传统CRC结构的问题

典型的CRC LFSR如图1所示。这示出了CRC32的一种可能的结构。总共有32个寄存器位，为了简洁，省略了中间的位。图中的运算是异或逻辑运算。每次一个位被移入。对于CRC32，在分组开始处的寄存器的状态被设置为全1。这相当于从寄存器设置为全0并反转数据的第一个32位开始。每个字节以至少重要的位顺序馈送。在分组结束时，寄存器被反转，并且所得到的比特被附加到分组的末尾。表I示出了用于逐渐并行实施CRC32的最大尺寸的异或门。这些数字源自在[6]在线生成的VHDL实现。到达256位宽的时候，最大异或门有157个输入。实际上，如果N是CRC计算中的输入比特的数量，则N / 2用作最大异或门的大小的下限。随着N变大，N / 2变成对于最大尺寸的x门的更好的近似。

X输入异或门的最低延迟形式是具有2个输入异或门的二叉树的形式。 通过树的最坏情况延迟是O（log2（X））。 对于大N，N的每个加倍大约使最大xor门尺寸加倍。 这给二叉树增加了额外的级别，这通过一个两个输入异或门的延迟增加了最坏情况的延迟。 同样，芯片上的路由成为时序约束。 计算值必须通过从输出返回到输入的增加距离; 通过已经高度拥挤的地区。

到现在为止，图片应该是清晰的，传统的方法通过增加并行性提供减少的回报。 解决方案是消除传统方法中的反馈。

IV．理论

[8]中的论文很好地概述了本文中使用的理论。该方法可以概括为分而治之。这里重复这个理论是为了完整性。 CRC计算是线性运算。因此它具有叠加的性质。给定两个消息，A和B：属性1：CRC（Aoplus;B）= CRC（A）oplus;CRC（B）该属性可能不明显。例如在CRC32中，存在第一个32位数据位的反转，以及最终结果被反相。如果从计算中移除这两个反演操作，则性质1是显而易见的。下一个属性是当0位的序列附加到消息A的结尾时对LFSR状态发生的情况。从图1可以看出，去除了最右边的xor门并且CRC [31]不变地反馈。 LFSR的下一个状态ai 1变成仅仅其当前状态ai的函数。实际上，从文献[8]，示出了LFSR的下一个状态ai 1可以通过将LFSR状态向量ai乘以在GF（2）下的操作2的矩阵H来确定。矩阵H是LFSR的反馈项的函数。在数学符号中，这是：

(1)

当

CRC(A)= (2)

CRC(Aamp;＇０＇)= (3)

符号A＆rsquo;0rsquo; 用于表示附加有一个零的消息A。 为了在P附加零之后找到LFSR的状态，矢量ai可以乘以H乘P次，或者由于矩阵乘法的相关性，可以乘以HP。 这更紧凑地示出为：

P = HP· （4）

这导致以下属性：属性2：将P个零附加到消息A与对CRC（A）乘以HP 在实践中，P的值具有有限范围，因为对具有最大长度的分组计算CRC。 这个最大分组长度定义了用于表示P的比特数。LetP由l比特组成，表示为P [1-1：0]

观察公式5，可以看出，乘以HP可以被分解为乘以H1，H2，H4，直到H2I-1，基于P的哪些比特等于1.对于等于P的比特 到0，当使用单位矩阵（H 0）时，值a ij不受影响。 所有这些矩阵功率可以预先计算。

V.应用

使用上一节中提到的两个属性，可以进行流水线CRC计算。 分组可以被分解为片，使得当这些片被拼凑在一起时，获得原始分组。 分解发生在两个阶段。 首先是固定大小的称为Bi的位块。

1. 前台

管道中的第一级称为前置级。 前置处理Bi，计算它们的CRC。 有两种主要方式来划分分组。 这些如图2所示。

第一种情况不需要修改最终计算的CRC值，但是需要提前知道分组大小。第二种情况是当最终分组大小未预先知道时。最终的CRC值需要在包结束时修改，以便由于过量零而反转LFSR状态。这需要不同的矩阵G，其逆转H的效果。被表示为Tie低的分组的部分示出了在分组的任一端处的Bi的一部分，其中比特应当被设置为零。这是为了填充分组长度以便是长度的倍数。阻塞过程最好由一个例子来说明。假定Bi具有长度8并且等于“Bi（7）Bi（6）Bi（5）Bi（4）Bi（3）Bi（2）Bi（1）Bi（0）”， “Bi（7）0000000”，“0Bi（6）000000”，...，“0000000Bi（0）”。可以预先计算这些中的每一个的CRC。然后使用属性1，Bi的CRC等于每个预计算值的xor，其中在该位位置中存在1。前置级可以扩展到多于8位。它还可以被流水线化以便满足期望的频率。

1. 前台之后

下一个阶段是前台输出发生了什么。 这发生在几个阶段，并且依赖于属性2，更具体地等式5.这用于将0的数目附加到Bi，将其放置在分组中的正确位置。 该位置是从分组结束的位计算的，其中CRC计算结束。 该值称为Oi。 参见图。 图3示出了这些后续阶段如何进入流水线的示例。 每个连续阶段使用不同的H的功率，检查Oi的相应位是否被设置，并且如果是，则乘以该功率。 当使用Oi的每个位时，可以从管线中移除它，从而减少需要保存的状态量。 大多数数据包使用字节作为最小单位，因此Oi的三个最低有效位可以连接到零，如果是这种情况，从而消除管道中的三个阶段。 这也意味着不使用H1，H2和H4。

如果Oi具有M个位，那么总共有M 2个计算级，包括前置级和最终累积级（使用属性1）。 整个结构是前馈的，除了累积阶段。 寄存器可以放置在沿着级的任何地方，以便针对特定的工作频率。 唯一需要的寄存器是累积阶段中的最后一个寄存器。 累加阶段应该不提供时序问题，因为它是按位xor运算。 LFSR状态与矩阵的逻辑乘法等价于xor树，每个输出位是平均输入位的一半的xor。

1. 修改的包

计算修改的包的新的CRC是经常进行的操作。 如果CRC值已知是好的，则更加有效地只是馈送修改的数据，Birsquo;，并且不馈送整个分组。 这个算法很好地适应这个操作。 通过两次馈送相同的{Bi，O i}对去除了该对的对CRC计算的影响。 一旦Bi被去除，B？ i可以通过{Birsquo;，O i}。 事实上， ioplus;Bi，O i}通过完成相同的操作，仅仅沿着管线馈送一个值。

1. 无序分组数据

如果分组数据不按顺序到达，则需要计算对应于新分组数据的位置的Oi。只要Oi准确，一旦所有分组片段被馈送通过，最后的CRC应当是正确的。接收的数据可以是输入宽度的子集，只要未使用的位被连接为低。这对于数据到达突发的情况是有利的。

1. 区域交易管道延迟

从图3可以看出，在每个阶段，一次检查一位Oi。如果一次检查两个比特的Oi，则每个级的基本结构将如图1所示。 4.由于添加了MUX，最终结果略大于两倍的面积。通过组合级的延迟应当小于两个原始级的和，假设矩阵乘法延迟大于附加MUX延迟。如果级继续被组合，则MUX延迟将变得更大，这可能需要MUX本身被流水线化，从而否定原始目的。

1. 处理图2中的情况

如V-A部分所述，当分组的大小未预先知道时，可以根据图2中的情况2来阻止分组。

这可以通过向Oi分配第一Bi的最大分组大小来处理。通常，Oi-x等于Oi-x·尺寸（Bi）。一旦接收到分组的末尾，需要调整最后的CRC值。这是为了去除附加到分组末尾的多余的零。

这涉及使用使H的操作反转的矩阵G.需要将矩阵G提高到过量零的数量的幂。这可以通过使用等式5与H一样来完成。该计算需要每个分组进行一次，因此可以根据性能要求在软件或硬件中进行。

1. CRC32示例

作为示例，为CRC32显示了H和G的值。 H的值在等式6中示出.G的值在等式7中示出。这两个矩阵在附录中列出。

这些矩阵用于乘以CRC32 LFSR，ai的状态。向量ai可以写为[CRC [0]，CRC [1]，...，CRC [30]，CRC [31]] T。检查图。 1，了解这与CRC32 LFSR的关系。

对CRC32的要求是反转第一个32个数据位，以及反转最后的CRC值。这些要求不会使此算法无效，并且可以添加处理它们的逻辑，而没有性能损失。

VI.比较

已经为CRC32实现了流水线算法的VHDL。 Bi的大小从64比特变化到2048比特，Oi的大小固定为12比特。 至少有14个寄存器级，较大的输入宽度在前置级中有一个额外的级。 顶层的示意图如图1所示。 5为1024位宽版本。 偏移

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[140618]，资料为PDF文档或Word文档，PDF文档可免费转换为Word