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)。除了这是用 table 做的，我还没有准备好 table !它确实说最后的 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 分支，该分支也会更新余数(如果最高位为零)。此外，请注意，余数的更新本质上是将其上移，然后将空的底部位设置为输入位串的下一位。所以 + 操作基本上是在执行 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
}