问汉明代码是如何工作的？

EN

让我们试着解释一下：

我们有一个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个校验比特，你就有一个n比特的检错码。如果你有2n个校验比特，你就有一个n比特的纠错码。

当然，您应该对“有效”代码进行排序，这样它们就不会彼此交错。

这是非常高层次的概述。

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.

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

汉明码(和其他类型的纠错码，如里德-所罗门)基于计算额外数据(而不是简单的复制)的公式。添加的比特取决于数据比特的组合，其方式是当在接收端重复计算时，复制中的错误产生可检测的变化模式。

为了说明起见，让我们从简单的奇数奇偶校验开始，添加单个比特以确保消息中的总比特数是奇数。因此，消息10110110变为101101100 (5个1，不需要额外的1)，消息10010110变为100101101 (4个1，需要额外的1)。如果您收到一条101101101消息，并且看到有6个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

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

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

有关纠错码的更多一般信息，请访问here