javascript - 了解初学者的循环冗余码算法

Question

在 section 5.5 of the PNG Specification ，它以称为“CRC”或“循环冗余码”的PNG文件格式讨论了这个概念。我以前从未听说过它，所以我试图理解它。

The CRC polynomial employed is

x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1

In PNG, the 32-bit CRC is initialized to all 1's, and then the data from each byte is processed from the least significant bit (1) to the most significant bit (128). After all the data bytes are processed, the CRC is inverted (its ones complement is taken). This value is transmitted (stored in the datastream) MSB first. For the purpose of separating into bytes and ordering, the least significant bit of the 32-bit CRC is defined to be the coefficient of the x31 term.

所以让我告诉你我理解的和我不理解的。

我听说过多项式，但在这种情况下，我对它们在这里的实现方式有些困惑。

在这种情况下，“x”应该代表什么？ 32 位循环中的当前位？这将我们带到下一部分:

所以它说要创建一个空的 32 位数字(或者更确切地说，全部设置为 1，所以 32 1)，然后它说它“从最低有效位 (1) 处理到最高有效位 (128)”，但是问题是，什么是“最不……最……最重要的一点”？

block 中的其他数据？

如果 block 以字节为单位设置，并且这只有 32 位，那它是如何工作的？如果 block 数据中有超过 32 位怎么办(肯定有？)

这是否意味着“多项式”的“最少..最多..有效位”？

但是多项式究竟代表什么？ x^32 是什么？

x代表什么？

对上述问题的任何帮助，也许还有一个简单的例子，比如 IDATA block (也就是用基本解释为它计算 CRC block )会很好:

0 0 2 3 IDAT 0 1 0 1 0 1 0 1 0 1 0 C

最后一个字节“C”应该用它所说的那个 32 位 CRC 替换。

有人可以给我一个实际的例子吗？

Answer 1

我会推荐阅读罗斯威廉姆斯的经典 "A Painless Guide to CRC Error Detection Algorithms" .您将在其中找到深入的解释和示例。

多项式只是解释一串位的不同方式。当您在寄存器中有 n 位时，它们最常被解释为 n 独立位的列表，或者它们被解释为整数，您将每个位乘以 2 的 0 到 n-1 次幂并将它们相加。多项式表示是您将每个位解释为多项式系数的地方。由于一个位只能是 0 或 1，因此生成的多项式实际上不会显示 0 或 1。相反，xn 项要么存在要么不存在。所以四个位 1011可以解释为 1 x3 + 0 x2 + 1 x1 + 1 x0 = x3 + x + 1。请注意，我选择最高有效位是 x3 项的系数。这是一个任意的选择，我本可以选择另一个方向。

至于 x 是什么，它只是 x 的系数和幂的占位符。您永远不会将 x 设置为某个值，也不会确定有关 x 的任何内容。它的作用是允许您将这些位串作为多项式进行运算。在对这些多项式进行运算时，您就像在代数课中的多项式一样对待它们，只是系数被限制在 GF(2) 域中，其中系数只能是 0 或 1。乘法变为与运算，加法变成异或运算。所以 1 加 1 就是 0。你得到了一种新的不同的方法来加、乘和除位串。这种不同的方式是许多错误检测和纠正方案的关键。

有趣但最终无关紧要的是，如果您在位串的多项式表示中将 x 设置为 2(使用正确的排序选择)，您将获得该位串的整数解释。