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

Question

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

使用的 CRC 多项式是

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

在 PNG 中，32 位 CRC 初始化为全 1，然后每个字节的数据从最低有效位 (1) 到最高有效位 (128) 进行处理。处理完所有数据字节后，将反转 CRC（取其补码）。该值首先传输（存储在数据流中）MSB。为了区分字节和排序，将 32 位 CRC 的最低有效位定义为 x31 项的系数。

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

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

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

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

块中的其他数据？

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

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

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

x代表什么？

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

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

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

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

标签： javascriptpngcrclibpngcrc32

Answer 1

I would recommend reading Ross Williams' classic "A Painless Guide to CRC Error Detection Algorithms". Therein you will find in-depth explanations and examples.

The polynomial is simply a different way to interpret a string of bits. When you have n bits in a register, they are most commonly interpreted either as just that, a list of n independent bits, or they are interpreted as an integer, where you multiply each bit by two raised to the powers 0 to n-1 and add them up. The polynomial representation is where you instead interpret each bit as the coefficient of a polynomial. Since a bit can only be a 0 or a 1, the resulting polynomials never actually show the 0 or 1. Instead the xⁿ term is either there or not. So the four bits 1011 can be interpreted to be 1 x³ + 0 x² + 1 x¹ + 1 x⁰ = x³ + x + 1. Note that I made the choice that the most significant bit was the coefficient of the x³ term. That is an arbitrary choice, where I could have chosen the other direction.

As for what x is, it is simply a placeholder for the coefficient and the power of x. You never set x to some value, nor determine anything about x. What it does is allow you to operate on those bit strings as polynomials. When doing operations on these polynomials, you treat them just like the polynomials you had in algebra class, except that the coefficients are constrained to the field GF(2), where the coefficients can only be 0 or 1. Multiplication becomes the and operation, and addition becomes the exclusive-or operation. So 1 plus 1 is 0. You get a new and different way to add, multiply, and divide strings of bits. That different way is key to many error detection and correction schemes.

It is interesting, but ultimately irrelevant, that if you set x to 2 in the polynomial representation of a string of bits (with the proper ordering choice), you get the integer interpretation of that string of bits.