CRC（循环冗余校验）了解优化

Question

在过去的几天里，我一直在努力了解 CRC 的工作原理。我坚持推荐用于其实施的特定优化。

我的理解：

*CRC 是多项式除法，其中位表示 x 的幂。我可以进行除法（使用常规多项式除法或使用位）并正确获得 CRC。

*移位寄存器用于保存余数。它是 n 位（对于 n 次多项式），因为每次减法最多影响 n 位。一旦整个消息通过寄存器，它就包含除法余数。

我被困的地方：

在此页面上：http : //en.wikipedia.org/wiki/Computation_of_cyclic_redundancy_checks 实现部分有一些伪代码。我对第一个伪代码和它的两个问题很好（尽管第一个很容易解决）。我无法理解第二个，以及 xor 的关联性/交换性如何帮助。手动，我看到第二个伪代码有效，但为什么呢？

其他来源：其他一些文章给出了相同的优化（在寄存器的左侧而不是右侧提供位）。特别是，这篇文章：http : //www.ross.net/crc/download/crc_v3.txt 在第 10 节中做到了（文本搜索单词 mangled）。除了这是用桌子做的，我还没有准备好桌子！它确实说最后的 n 次迭代仅用于获取寄存器左侧的消息尾部，我理解这一点，但我再次无法理解这里的优化。

编辑：我找到了另一个参考资料（第 8 页）：http : //www.hackersdelight.org/crc.pdf 但这仍然没有帮助。它说预乘与后乘相同，但我不明白这是怎么回事，因为当在寄存器左侧找到 1 位时，这会更改寄存器中的位（以触发减法）。

谢谢。感谢您对我的好奇心的帮助！

担

Answer 1

在第一个伪代码中，余数用输入位串的前导部分进行初始化。然后在迭代过程中，在每一步中，余数都会上移，并且现在空出的底部位将被输入位串中的下一位填充。为了完成该操作，输入位串需要追加零。这些零将在计算过程中通过余数有效地清除数据。

在第二个伪代码中，余数开始清零（全是零）。在迭代期间，输入位串中的下一位直接放置在余数的顶部位置。因此，完成计算不需要初始化和刷新。此外，对最高位的测试和余数运算的上移被重新排序。

您可以通过以下几个转换步骤将第一个伪代码算法转换为第二个伪代码算法。

从基本算法的伪代码开始（代码片段1）：

function crc(bit array bitString[1..len], int len) {
    remainderPolynomial  := polynomialForm(bitString[1..n])   // First n bits of the message
    for i from 1 to len {
        remainderPolynomial  := remainderPolynomial * x + bitString[i+n] * x0   // Define bitString[k]=0 for k>len
        if coefficient of xn of remainderPolynomial = 1 {
            remainderPolynomial  := remainderPolynomial xor generatorPolynomial
        }
    }
    return remainderPolynomial
}

第一个转换是交换更新余数多项式和测试最高位的顺序，即我们可以测试第二最高位（在上移之前），然后在分支中if更新余数，然后与生成多项式进行异或运算，并且添加else分支，该分支还更新余数（如果最高位为零）。此外，请注意，余数的更新本质上是将其上移，然后将空的底部位设置为输入位串中的下一位。所以+操作基本上就是doing 0 + ?，这相当于0 xor ?。通过应用这些原则，我们现在得到以下等效的伪代码：

function crc(bit array bitString[1..len], int len) {
    remainderPolynomial  := polynomialForm(bitString[1..n])   // First n bits of the message
    for i from 1 to len {
        if coefficient of xn-1 of remainderPolynomial = 1 {
            remainderPolynomial  := (remainderPolynomial * x xor bitString[i+n] * x0) xor generatorPolynomial
        } else {
            remainderPolynomial  := remainderPolynomial * x xor bitString[i+n] * x0
        }
    }
    return remainderPolynomial
}

现在，请注意，在循环中我们将bitString[i+n]其放置在x0位置上。然后该位在后续计算期间向上移动。我们可以从概念bitString[i+n] * x0上改为bitString[i] * xn. 如果我们将其从分支中取出if/else并在上移余数 ( ... * x) 之前执行此操作，我们会得到... xor bitString[i] * xn-1。因为我们现在将输入位串中的位放置在余数的顶部，所以我们只需在开头清除余数，不需要附加零来通过余数寄存器刷新数据。瞧，我们现在有了修改后的算法的伪代码（代码片段 2）：

function crc(bit array bitString[1..len], int len) {
    remainderPolynomial  := 0
    for i from 1 to len {
        remainderPolynomial  := remainderPolynomial xor (bitstring[i] * xn-1)
        if (coefficient of xn-1 of remainderPolynomial) = 1 {
            remainderPolynomial  := (remainderPolynomial * x) xor generatorPolynomial
        } else {
            remainderPolynomial  := remainderPolynomial * x
        }
    }
    return remainderPolynomial
}