-2

假设我们正在使用一个纠错码，它将允许对长度为 7 的内存字纠正所有单位错误。我们已经计算出需要 4 个校验位，所有码字的长度将为 11。码字是根据文中介绍的汉明算法创建的。我们现在收到以下代码字： 1 0 1 0 1 0 1 1 1 1 0 假设偶校验，这是一个合法的代码字吗？如果不是，根据我们的纠错码，错误在哪里？

Ps 需要一些帮助来解决这个汉明码问题，这是一本书的问题。提前致谢 ：）

4

1 回答 1

0

码字是根据文中介绍的汉明算法创建的。

这是一条重要的信息，你不觉得吗？:-)

没有算法，我们无法确定有效性，所以我会给你一个通用的方法。

每个校验位通常适用于某些位子集。假设七个位是b6through b0。计算四个校验位以提供以下子集的偶校验：

     1  0  1  0  1  0  1
ca  b6 b5    b3 b2 b1 b0  1+0+0+1+0+1   + (ca = 0)
cb  b6    b4    b2    b0  1+1+1+1       + (cb = 0)
cc  b6       b3       b0  1+0+1         + (cc = 0)
cd     b5          b1 b0  0+0+1         + (cd = 1)

现在，如果您没有得到与数据匹配的校验位序列，理想情况下，您将能够计算出需要更改哪个单个数据或校验位才能修复它。这只有在您可以确保每个校验位计算都经过精心设计以添加最大的额外信息时才有效。

这可能是我上述计算的失败，因为我只是凭空将它拉出来。但是，由于我的意图只是在没有您的算法的情况下解释这个概念，所以这无关紧要。

确保算法有效的一种方法是暴力破解它：

  • 获取所有可能的 11 位值的列表。其中只有 2048 个，因此并不繁重。现在，丢弃那些已经没问题的（我们只对无效的感兴趣）。
  • 反过来，切换每个位（11 个）并查看该项目是否有效。
  • 如果没有位切换使其有效，则这不是单个位错误，因此可以安全地忽略。
  • 如果一位切换使其有效，那么您有足够的信息来解决这种情况。
  • 如果不止一位切换使其有效，则您没有足够的信息来解决这种情况。

最重要的是，如果可以通过单个位切换（上面的倒数第二个要点）使每个位错误的可能性都有效，则更正代码是完美的。

您还应该检查以确保如果切换单个位，每个有效的都将变为无效，但我将把它留作练习，因为您现在应该有足够的信息来说明如何执行此操作。

于 2020-11-13T00:40:47.183 回答