什么是汉明距离?如何确定 CRC 方案的汉明距离?
-
25-09-2019 - |
题
在学习计算机网络课程时,教授谈到了示例代码中 2 个有效代码字之间的汉明距离。我读过有关汉明距离的内容,从区分两个字符串之间的距离差异的角度来看,它是有意义的。例如:
Code Word 1 = 10110
发送方发送码字1,引入错误,接收方收到10100。所以你会看到第四位已损坏。这将导致汉明距离为 1,因为:
Valid Code Word: 10110
Error Code Word: 10100
-----
XOR 00010
2 个字符串的异或结果为 1,因此汉明距离为 1。到那时我就明白了。但随后教授问道:
- 标准CRC-16位协议的汉明距离是多少?
- 标准 CRC-32 位协议的汉明距离是多少?
我有点困惑,想知道是否有人可以帮忙。谢谢。
解决方案
你现在可能已经明白了,但他要求的很可能是 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, vol 41 no 6, June 1993),这意味着它可以保证在 5,275 位或更少的单个消息中检测到最多 5 个翻转位。
顺便说一句,代码字包括校验和,所以你的例子是不正确的。
不隶属于 StackOverflow