初学者了解循环冗余码算法
Understanding Cyclic Redundancy Code algorithm for beginners
在 section 5.5 of the PNG Specification，它以名为 "CRC" 或 "Cyclic Redundancy Code" 的 PNG 文件格式讨论了这个概念。我以前从未听说过它，所以我正在尝试了解它。
The CRC polynomial employed is
x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2
+ 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），然后它说它是 "processed from the least significant bit (1) to the most significant bit (128)"，但问题是，"least...most..significant bit" 的 什么?
块中的其他数据？
如果块以字节为单位设置，而这只有 32 位，那是如何工作的？如果块数据中有超过 32 位怎么办（肯定有？）
是否表示"polynomial"的"least..most..significant bit"？
但是多项式究竟代表什么？什么是 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。
谁能给我一个实际的例子？
规范包括 link 示例代码：
https://www.w3.org/TR/2003/REC-PNG-20031110/#D-CRCAppendix
规范有错误或令人困惑。
应该是“每个字节的数据从最低有效位（0）到最高有效位（7）处理。
CRC 是一个 33 项多项式，其中每个项都有一位系数，0 或 1，在描述多项式时忽略 0 系数。
将 CRC 视为保存在 32 位寄存器中。该序列是将一个字节的数据异或到 CRC 寄存器最右边的字节，第 7 位到第 0 位（技术上对应于 x^24 到 x^31 的多项式系数）。然后 CRC 是 "cycled" 右边的 8 位（通过 table 查找）。一旦所有数据字节都经过此循环，根据 Mark Adler 的评论，CRC 首先附加到数据最高有效字节，(CRC>>24)&0xff, (CRC>>16)&0xff, (CRC>> 8)&0xff, (CRC)&0xff.
维基文章可能有所帮助。对于计算部分中的示例，被除数将是一个数据字节数组，每个字节的位反转，33 位多项式的位将是非反转的 (0x104C11DB7)。完成计算后，余数的位将被反转并附加到数据字节。
https://en.wikipedia.org/wiki/Cyclic_redundancy_check
Mark Adler 的回答包括 link 一个很好的 CRC 教程。他的回答还解释了多项式中使用的 x。它就像代数中的多项式，只是系数只能为 0 或 1，并且加法（或减法）是使用 XOR 完成的。
what is x
来自 wiki 示例：
data = 11010011101100 = x^13 + x^12 + x^10 + x^7 + x^6 + x^5 + x^3 + x^2
divisor = 1011 = x^3 + x + 1
三个 0 位附加到数据，有效地乘以 x^3:
dividend = 11010011101100000 = x^16 + x^15 + x^13 + x^10 + x^9 + x^8 + x^6 + x^5
然后 crc = dividend % divisor，系数限制为 0 或 1。
(x^16 + x^15 + x^13 + x^10 + x^9 + x^8 + x^6 + x^5) % (x^3 + x + 1) = x^2
11010011101100000 % 1011 = 100
我会推荐阅读 Ross Williams 的 classic "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 的任何内容。它的作用是允许您将这些位串作为多项式进行操作。在对这些多项式进行运算时，您可以像对待代数 class 中的多项式一样对待它们，只是系数被限制在域 GF(2) 中，其中系数只能是 0 或 1。乘法变为与运算，加法变为异或运算。所以 1 加 1 等于 0。你得到了一种新的和不同的方式来加、乘、除位串。这种不同的方式是许多错误检测和纠正方案的关键。
有趣但最终无关紧要的是，如果在一串位的多项式表示中将 x 设置为 2 (通过正确的排序选择），您将获得该位串的整数解释。
注意：如果您使用 (00000000)_2 和 (00000001)_2 作为示例 IDAT 块中 0 和 1 的二进制表示，您将错误地计算 CRC。 '0'和'1'的ASCII值是48 = (00110000)_2和49 = (00110001)_2；类似地，'I'、'D'、'A'和'T'的ASCII值是73 = (01001001)_2, 68 = (01000100)_2, 65 = (01000001) _2，和 84 = (01010100)_2。因此，假设您是指值0和1而不是字符'0'和'1'，则必须计算的CRC（01001001 01000100 01000001 01000001 01010100 000000000000000000000000100000000100000000000000000000000000000000000000000000000000000000000000000000来0000000000来0000000000来州000000000000000000000000000000000000000000000000000000000000000000000000000000000000来=10=]
与CRC无关但与块的有效性相关，块的长度字段（即前4个字节）应仅包含数据的字节长度，即11，这是垂直制表符 (VT) 的 ASCII 值，它是一个非打印字符，但可以用十六进制转义序列 \x0B（其中 (B)_16 = 11）在字符串中表示。同样，前 3 个字节必须包含 ASCII 值为 0（而不是 48）的字符，该字符为空 (NUL)，可以用十六进制转义序列 \x00 在字符串中表示。因此，长度字段必须包含类似“\x00\x00\x00\x0B”的内容。
在 section 5.5 of the PNG Specification，它以名为 "CRC" 或 "Cyclic Redundancy Code" 的 PNG 文件格式讨论了这个概念。我以前从未听说过它，所以我正在尝试了解它。
The CRC polynomial employed is
x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + 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），然后它说它是 "processed from the least significant bit (1) to the most significant bit (128)"，但问题是，"least...most..significant bit" 的 什么?
块中的其他数据？
如果块以字节为单位设置，而这只有 32 位，那是如何工作的？如果块数据中有超过 32 位怎么办（肯定有？）
是否表示"polynomial"的"least..most..significant bit"？
但是多项式究竟代表什么？什么是 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。
谁能给我一个实际的例子？
规范包括 link 示例代码：
https://www.w3.org/TR/2003/REC-PNG-20031110/#D-CRCAppendix
规范有错误或令人困惑。
应该是“每个字节的数据从最低有效位（0）到最高有效位（7）处理。
CRC 是一个 33 项多项式，其中每个项都有一位系数，0 或 1，在描述多项式时忽略 0 系数。
将 CRC 视为保存在 32 位寄存器中。该序列是将一个字节的数据异或到 CRC 寄存器最右边的字节，第 7 位到第 0 位（技术上对应于 x^24 到 x^31 的多项式系数）。然后 CRC 是 "cycled" 右边的 8 位（通过 table 查找）。一旦所有数据字节都经过此循环，根据 Mark Adler 的评论，CRC 首先附加到数据最高有效字节，(CRC>>24)&0xff, (CRC>>16)&0xff, (CRC>> 8)&0xff, (CRC)&0xff.
维基文章可能有所帮助。对于计算部分中的示例，被除数将是一个数据字节数组，每个字节的位反转，33 位多项式的位将是非反转的 (0x104C11DB7)。完成计算后，余数的位将被反转并附加到数据字节。
https://en.wikipedia.org/wiki/Cyclic_redundancy_check
Mark Adler 的回答包括 link 一个很好的 CRC 教程。他的回答还解释了多项式中使用的 x。它就像代数中的多项式，只是系数只能为 0 或 1，并且加法（或减法）是使用 XOR 完成的。
what is x
来自 wiki 示例：
data = 11010011101100 = x^13 + x^12 + x^10 + x^7 + x^6 + x^5 + x^3 + x^2
divisor = 1011 = x^3 + x + 1
三个 0 位附加到数据，有效地乘以 x^3:
dividend = 11010011101100000 = x^16 + x^15 + x^13 + x^10 + x^9 + x^8 + x^6 + x^5
然后 crc = dividend % divisor，系数限制为 0 或 1。
(x^16 + x^15 + x^13 + x^10 + x^9 + x^8 + x^6 + x^5) % (x^3 + x + 1) = x^2
11010011101100000 % 1011 = 100
我会推荐阅读 Ross Williams 的 classic "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 的任何内容。它的作用是允许您将这些位串作为多项式进行操作。在对这些多项式进行运算时，您可以像对待代数 class 中的多项式一样对待它们，只是系数被限制在域 GF(2) 中，其中系数只能是 0 或 1。乘法变为与运算，加法变为异或运算。所以 1 加 1 等于 0。你得到了一种新的和不同的方式来加、乘、除位串。这种不同的方式是许多错误检测和纠正方案的关键。
有趣但最终无关紧要的是，如果在一串位的多项式表示中将 x 设置为 2 (通过正确的排序选择），您将获得该位串的整数解释。
注意：如果您使用 (00000000)_2 和 (00000001)_2 作为示例 IDAT 块中 0 和 1 的二进制表示，您将错误地计算 CRC。 '0'和'1'的ASCII值是48 = (00110000)_2和49 = (00110001)_2；类似地，'I'、'D'、'A'和'T'的ASCII值是73 = (01001001)_2, 68 = (01000100)_2, 65 = (01000001) _2，和 84 = (01010100)_2。因此，假设您是指值0和1而不是字符'0'和'1'，则必须计算的CRC（01001001 01000100 01000001 01000001 01010100 000000000000000000000000100000000100000000000000000000000000000000000000000000000000000000000000000000来0000000000来0000000000来州000000000000000000000000000000000000000000000000000000000000000000000000000000000000来=10=]
与CRC无关但与块的有效性相关，块的长度字段（即前4个字节）应仅包含数据的字节长度，即11，这是垂直制表符 (VT) 的 ASCII 值，它是一个非打印字符，但可以用十六进制转义序列 \x0B（其中 (B)_16 = 11）在字符串中表示。同样，前 3 个字节必须包含 ASCII 值为 0（而不是 48）的字符，该字符为空 (NUL)，可以用十六进制转义序列 \x00 在字符串中表示。因此，长度字段必须包含类似“\x00\x00\x00\x0B”的内容。