汉明距离是多少?对于CRC方案如何确定? [英] What is the hamming distance, and how do I determine it for a CRC scheme?

问题描述

在学习计算机网络课程时，教授谈到了示例代码中2个有效代码字之间的汉明距离.我已经阅读了汉明距离，从告诉2根弦之间的距离差异的角度来看，这很有道理.例如:

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 

发送方发送代码字1，并且引入了一个错误，接收方接收到10100.因此，您看到第4位已损坏.汉明距离为1，因为:

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

2个字符串的XOR结果为1，因此汉明距离为1.但是教授问:

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:

• 标准CRC-16位协议的汉明距离是多少?
• 标准CRC-32位协议的汉明距离是多少?

我有点困惑，想知道是否有人可以帮忙.谢谢.

I'm a bit confused, and was wondering if someone could help. Thanks.

推荐答案

您可能现在已经知道了，但是他所要求的是最有可能无法检测到CRC代码的最小位错误数.答案取决于消息的宽度，多项式和长度.例如，最著名的CRC-32多项式(0x1EDC6F41)的汉明距离为6或更佳，适用于最多5,275位的消息(Castaglioni，Bräuer，Herrmann:具有24和32位奇偶校验位的循环冗余校验码的优化，IEEE 《通信事务》，1993年6月，第41卷第6期)，这意味着可以保证在一条5275位以下的单个消息中最多检测到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.

这篇关于汉明距离是多少?对于CRC方案如何确定?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！