15

传输数据时，汉明码显然允许您重新创建已通过线路损坏的数据（纠错码）。

这是如何工作的，如果有的话，它的局限性是什么？

有没有更好的纠错解决方案（而不是重传）？是否存在重传更好的情况？

4

6 回答 6

39

让我们试着解释一下：

我们有一个 3 位数字。可能性可以表示为一个立方体，其中每个位代表一个轴。八种可能性都在拐角处。

000 --------001
 | \         | \
 | 100---------101
 |  |        |  |
 |  |        |  |
010-|-------011 |
   \|          \|
   110---------111

每个缺陷（例如 101 被读取为 100）都会导致立方体上的一条线发生偏移。

如果我们将两位用于数据，第三位用于奇偶校验（例如偶校验）。我们丢失了 4 个数据点。但它的优点是我们可以检测到单个位故障（它将偶数个 1 转换为奇数个 1）。奇数标有*。我们看到每个奇数（错误传输的）单词都被偶数（正确传输的）单词逼入绝境。因此，如果我们收到 100，我们可以确定它是错误的。

但是（有一个位失败）正确的表示可能是 000、101 或 110。所以我们可以检测到错误，但我们无法检测到错误：

 000 -------*001
  | \         | \
  |*100---------101
  |  |        |  |
  |  |        |  |
*010-|-------011 |
    \|          \|
    110--------*111

这称为一位错误检测码。

如果我们使用另一位进行检查，从而为数据删除一位。我们剩下 1 个数据位和 2 个“校验位”。在这种情况下，假设 000 和 111 是有效的数据表示，而其他六个不是。现在我们有一个有趣的情况，如果在传输过程中损坏了一个位。如果我们发送 000 并接收 010，我们会看到 010 有一个有效邻居（000）和两个无效邻居（110 和 011）。所以现在我们知道我们打算发送 000 并且能够更正它：

 000 -------*001
  | \         | \
  |*100--------*101
  |  |        |  |
  |  |        |  |
*010-|------*011 |
    \|          \|
   *110---------111

这称为一位纠错码。

请注意，一位纠错码也是两位错误检测码。

更笼统地说。

如果您有 n 个校验位，则您有一个位错误检测代码。如果您有 2n 个校验位，则您有一个位纠错码。

当然，您应该订购“有效”代码，以免它们彼此相邻。

于 2008-12-23T11:28:25.610 回答
13

这是真正的高级概述。

Suppose that every time I send a message, I send thrie copies of the text.
Suppose that every time I send z message, I send three copies of the teyt.
Suppose that every tyme I send a message, I send three copies if the tezt.

通过比较字符并在每个位置进行简单多数表决，您可以更正单个错误字符。然而，这种方案的成本（必须发送的数据量）很高，并且它没有捕捉到不同副本的相应位置出现两个错误的不太可能但可能的情况（如上面示例的最后一个字） ）。

汉明码（和其他类型的纠错码，如 Reed-Solomon）基于计算额外数据的公式（而不是简单的重复）。添加的位取决于数据位的组合，当在接收端重复计算时，复制中的错误会产生可检测的变化模式。

为了说明起见，让我们从简单的奇校验开始，添加一个位以确保消息中的总位数是奇数。因此消息10110110变为101101100（五个 1，不需要额外的 1）并且消息10010110变为100101101（四个 1，需要额外的 1）。如果你收到一个 的消息，101101101看到有六个 1，你就知道有错误，但不知道在哪里。假设我们添加更多奇偶校验位，每个奇偶校验位仅取决于消息的一部分，如下所示，通过复制所考虑的位并使用“-”表示忽略的位：

10110110
1-1-0-1- => 0
-0-1-1-0 =>  1
10--01-- =>   1
--11--10 =>    0
1011---- =>     0
----0110 =>      1

所以完整的信息是10110110011001。现在假设一个传输错误改变了消息中的第三位，所以它读为10010110011001。当接收方重新运行错误检查计算时，匹配失败：

10010110
1-0-0-1- => 1*
-0-1-1-0 =>  1
10--01-- =>   1
--01--10 =>    1*
1001---- =>     1*
----0110 =>      1

而不匹配的校验位正是受第三个数据位影响的校验位。这不是一个真正的、稳健的纠错方案；这只是一个草图，用于说明构建冗余如何帮助识别错误的确切性质。

于 2008-12-23T13:58:17.897 回答
5

您将在此处找到有关其工作方式的详细信息

有关纠错码的更多一般信息可在此处获得

于 2008-12-23T10:45:14.730 回答
3

有关汉明码的信息可在此处和此处获得。

至于适用性，这解释了原因：

  1. 像汉明这样的纠错码适用于不能请求重传的单工信道。

  2. 错误检测加重传通常是首选，因为它更有效。

为了比较，考虑每比特错误率的通道。让块大小为 1000 位。

为了纠正单个错误（通过汉明码），每个块需要 10 个校验位。要传输 1000 个块，需要 10,000 个校验位（开销）。为了检测单个错误，每个块一个奇偶校验位就足够了。要传输 1000 个块，只需要重新传输一个外部块（由于每比特的错误率），从而仅产生 2001 (= 1000 + 1001) 比特的开销。

于 2008-12-23T11:05:24.250 回答
0

汉明码是一种数学技巧，可以纠正串行传输中多达 4 个丢失的位。它还用于支持现代存储芯片中的“奇偶校验位”。

限制在可以恢复的比特数，最多不超过4。如果丢失超过4比特，则需要重传。

不同的情况需要不同的纠错技术。其中一些技术列在此处的其他帖子中。

于 2008-12-23T11:22:32.703 回答
0

@GameCat 以及 2 位错误检测代码。

在这种情况下，假设 111 已更改为 100。那么我们可以确定有 2 位错误并且我们知道这一点，因为 111 和 100 之间的距离是 2 位，而 000 和 100 之间的距离是 1 位。因此，如果我们知道存在 2 位错误，我们就可以确定什么是正确的值。

于 2010-03-08T15:50:57.033 回答