1

所以我想在这个暑期项目中使用汉明码纠正消息传输中的错误，但我无法弄清楚它是如何工作的。我在网上看了很多文章，但我对算法不是很了解。任何人都可以简单地解释一下吗？

谢谢。

4

3 回答 3

9

这都是关于汉明距离的。

两个以 2 为底的值之间的汉明距离是它们不同的位数。因此，如果您传输 A，但我收到 B，那么传输中必须切换的位数就是 A 和 B 之间的汉明距离。

当每个码字中的位以某种方式单独传输时，汉明码很有用。我们不在乎它们是串行的还是并行的，但它们不会例如组合成代表几个位的模拟值，或者在编码后压缩/加密。

因此，每个比特都是独立的（以某种固定的概率随机地），要么被正确接收，要么被翻转。假设传输相当可靠，大多数比特都被正确接收。因此，少量比特的错误更有可能发生，而同时出现大量比特的错误则不太可能发生。

因此，汉明码通常旨在纠正 1 位错误和/​​或检测 2 位错误（有关两种主要类型的详细信息，请参阅 Wikipedia 文章）。可以构建纠正/检测更大错误的代码，但 AFAIK 的使用并不多。

该代码通过在“汉明空间”中均匀地隔开代码点来工作，在数学术语中，汉明空间是由相关字长的所有值组成的度量空间，以汉明距离作为度量。想象一下，每个代码点都被一个无效值的小“缓冲区”包围。如果接收到的值不是代码点，则一定发生了错误，因为只传输了有效的代码点。

如果接收到缓冲区中的值，则假设发生 1 位错误，则传输的值与接收的值的距离必须为 1。但由于码点分散，只有一个码点接近。因此，它被“纠正”到该代码点，因为 1 位错误比任何其他代码点产生接收到的值所需的更大错误更有可能。在概率方面，假设我收到了我所做的值，您发送附近代码点的条件概率大于您发送任何其他代码点的条件概率。所以我猜你发送了附近的一个，基于传输的可靠性和每个字的位数有一定的信心。

如果接收到一个与两个代码点等距的无效值，那么我不能说一个比另一个更有可能是真实值。所以我检测到错误，但我无法纠正它。

显然 3 位错误不能由 SECDED 汉明码纠正。收到的值比您实际发送的值更远，而不是其他代码点，我错误地将其“更正”为错误的值。因此，您要么需要足够可靠的传输，以至于您不关心它们，要么您还需要更高级别的错误检测（例如，整个消息的 CRC）。

于 2009-04-16T19:23:05.540 回答
2

具体来自维基百科，算法如下：

  1. 从 1 开始对位进行编号：位 1、2、3、4、5 等。
  2. 以二进制形式写入位数。1、10、11、100、101 等
  3. 所有为 2 的幂的位位置（在其位置的二进制形式中只有一个 1 位）都是奇偶校验位。
  4. 所有其他位位置，在其位置的二进制形式中具有两个或多个 1 位，都是数据位。
  5. 每个数据位都包含在一组唯一的 2 个或更多奇偶校验位中，由其位位置的二进制形式确定。
    1. 奇偶校验位 1 涵盖所有设置了最低有效位的位位置：位 1（奇偶校验位本身）、3、5、7、9 等。
    2. 奇偶校验位 2 涵盖了设置了第二个最低有效位的所有位位置：位 2（奇偶校验位本身）、3、6、7、10、11 等。
    3. 奇偶校验位 4 涵盖了设置了第三个最低有效位的所有位位置：位 4-7、12-15、20-23 等。
    4. 奇偶校验位 8 涵盖了设置了第四个最低有效位的所有位位置：位 8-15、24-31、40-47 等。
    5. 通常，每个奇偶校验位覆盖奇偶校验位置和位位置的二进制与非零的所有位。
于 2009-04-16T19:07:35.140 回答
0

维基百科文章很好地解释了它。

如果您不了解算法的特定方面，那么您将需要重新表述（或详细说明）您的问题，以便有人可以解决您问题的特定部分。

于 2009-04-16T18:26:48.530 回答