什么是汉明距离？如何确定 CRC 方案的汉明距离？
在学习计算机网络课程时，教授谈到了示例代码中 2 个有效代码字之间的汉明距离。我读过有关汉明距离的内容，从区分两个字符串之间的距离差异的角度来看，它是有意义的。例如：
Code Word 1 = 10110
发送方发送代码字 1，并且引入了错误，接收方收到 10100。因此您会看到第 4 位已损坏。这将导致汉明距离为 1，因为：
Valid Code Word: 10110
Error Code Word: 10100
-----
XOR 00010
2 个字符串的异或结果为 1，因此汉明距离为 1。到目前为止我是这么理解的。但教授接着问：
- 标准 CRC-16 位协议的汉明距离是多少？
- 标准 CRC-32 位协议的汉明距离是多少？
我有点困惑，想知道是否有人可以帮忙。谢谢。
While studying for a class in computer networks, the prof talked about the hamming distance between 2 valid code words in a sample code. I have read about hamming distance, and it makes sense from the perspective of telling the difference distance between 2 strings. For example:
Code Word 1 = 10110
The sender sends code word 1, and there is an error introduced, and the receiver receives 10100. So you see that the 4th bit was corrupted. This would result in the a hamming distance of 1 because:
Valid Code Word: 10110
Error Code Word: 10100
-----
XOR 00010
The XOR of the 2 strings results in one 1, so the hamming distance is 1. I understand it up to that point. But then the prof asks:
- What is the hamming distance of the standard CRC-16 bit protocol?
- What is the hamming distance of the standard CRC-32 bit protocol?
I'm a bit confused, and was wondering if someone could help. Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
你现在可能已经明白了，但他要求的很可能是 CRC 码无法检测到的最小比特错误数。答案取决于消息的宽度、多项式和长度。例如，对于高达 5,275 位的消息，最著名的 CRC-32 多项式 (0x1EDC6F41) 的汉明距离为 6 或更好（Castaglioni、Bräuer、Herrmann：Optimization of Cyclic Redundancy-Check Codes with 24 and 32 Parity Bits，IEEE Transactions on Communications，第 41 卷第 6 期，1993 年 6 月），这意味着它可以保证在 5,275 位或更少的单个消息中检测到最多 5 个翻转位。
顺便说一句，代码字包括校验和，所以你的例子是不正确的。
You probably figured it out by now, but what he asked for was most likely the minimum number of bit errors that a CRC code would not detect. The answer depends on the width, the polynomial and the length of the message. For instance, the best known CRC-32 polynomial (0x1EDC6F41) has a Hamming distance of 6 or better for messages of up to 5,275 bits (Castaglioni, Bräuer, Herrmann: Optimization of Cyclic Redundancy-Check Codes with 24 and 32 Parity Bits, IEEE Transactions on Communications, vol 41 no 6, June 1993) which means it is guaranteed to detect up to 5 flipped bits in a single message of 5,275 bits or less.
BTW, the code word includes the checksum, so your example is incorrect.