了解初学者的循环冗余码算法 [英] Understanding Cyclic Redundancy Code algorithm for beginners

问题描述

在 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位looP中吗？将我们带到下一部分：

因此它说要生成一个空的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。

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

解决方案

当心注意：如果在示例IDAT块中使用（00000000）_2和（00000001）_2作为0和1的二进制表示形式，则会错误地计算CRC。 ASCII值 0和 1分别为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 01010100 00000000 00000001 00000000 00000001 00000000 00000001 00000000 00000001 00000000 00000001 00000000）_2。 / p>

与CRC无关紧要，但与块的有效性无关，块的长度字段（即前4个字节）应包含以字节为单位的数据长度仅是11，它是垂直制表符（VT）的ASCII值，它是非打印字符，但可以用十六进制转义序列\x0B（其中（B）_16 = 11）表示为字符串。同样，前3个字节必须包含ASCII值为0（而不是48）的字符，该字符为null（NUL），可以用十六进制转义序列\x00表示为字符串。因此，长度字段必须包含 \x00\x00\x00\x0B之类的内容。

at section 5.5 of the PNG Specification, it discusses this concept in the PNG file format called "CRC" or "Cyclic Redundancy Code". I've never heard of it before, so I'm trying to understand it.

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.

So let me tell you what I understand and what I don't understand about this.

I've heard of polynomials, but in this context I'm a bit confused of how they are implemented here.

In this case, what is "x" supposed to represent? The current bit in the 32-bit looP? Which brings us to the next part:

so it says to make an empty 32-bit number (or rather, all set to 1s, so 32 1s), then it says it's "processed from the least significant bit (1) to the most significant bit (128)", but the question is, the "least...most..significant bit" of what?

Of the other data in the chunk?

How does that work, if the chunk is set in bytes, and this is only 32 bits? What if there are more than 32 bits in the chunk data (which there definitely are?)

Does it mean "least..most..significant bit" of the "polynomial"?

But what does the polynomial represent exactly? What is x^32?

What is x represented by?

Any help with the above questions, and perhaps a simple example with the example IDATA chunk (AKA calculating the CRC chunk for it with basic explanations) would be great:

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

where the last byte "C" should be replaced with that 32-bit CRC thing it was talking about.

Can someone provide me with a practical example?

解决方案

Beware: If you use (00000000)_2 and (00000001)_2 as the binary representations of the 0s and 1s in your example IDAT chunk, you will compute the CRC incorrectly. The ASCII values of '0' and '1' are 48 = (00110000)_2 and 49 = (00110001)_2; similarly, the ASCII values of 'I', 'D', 'A', and 'T' are 73 = (01001001)_2, 68 = (01000100)_2, 65 = (01000001)_2, and 84 = (01010100)_2. So, assuming you meant the values 0 and 1 rather than the characters ‘0’ and ‘1’, what you must compute the CRC of is (01001001 01000100 01000001 01010100 00000000 00000001 00000000 00000001 00000000 00000001 00000000 00000001 00000000 00000001 00000000)_2.

Inconsequentially to the CRC but consequentially to the validity of the chunk, the length field (i.e., the first 4 bytes) of the chunk should contain the length in bytes of the data only, which is 11, which is the ASCII value of a vertical tab (VT), which is a nonprinting character but can be represented in strings by the hexadecimal escape sequence \x0B (in which (B)_16 = 11). Similarly, the first 3 bytes must contain the character for which the ASCII value is 0 (rather than 48), which is null (NUL), which can be represented in strings by the hexadecimal escape sequence \x00. So, the length field must contain something like "\x00\x00\x00\x0B".

这篇关于了解初学者的循环冗余码算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！