汉明代码如何工作？

在传输数据时,汉明代码显然允许您重新创建已损坏的数据(纠错码).

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

是否有更好的纠错解决方案(与重传相对)？是否存在转播更好的情况？

我们试着解释一下:

我们有一个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个校验位,则会有一些纠错码.

当然,您应该订购"有效"代码,以便它们不会相互接壤.

这是真正的高级概述.

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

并且不匹配的校验位正是受第三个数据位影响的校验位.这不是一个真正的,强大的纠错方案; 它只是一个草图,用于说明冗余构建如何帮助确定错误的确切性质.

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

有关错误代理代码的更多常规信息,请参见此处