海明码如何工作? [英] How does the Hamming code work?

问题描述

在传输数据时，汉明码显然可以让您重新创建通过电线损坏的数据(纠错码).

When transmitting data, the Hamming code apparently allows you to recreate data that has been corrupted over the wire (an error correcting code).

这是如何工作的，其局限性是什么?

How does this work and what are its limitations, if any?

是否有更好的纠错解决方案(与重传相对)?在某些情况下重传更好吗?

Are there any better solutions for error correction (as opposed to retransmission)? Are there circumstances where retransmission is better?

推荐答案

让我们尝试解释一下:

我们有一个3位数字.可能性可以表示为一个立方体，其中每个位代表一个轴.八个可能性迫在眉睫.

We have a 3 bit number. The possibilities can be presented as a cube where each bit represent an axis. The eight possibilities are on the corners.

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

每个缺陷(例如101读为100)都会导致多维数据集上一行的移位.

Each defect (for example 101 is read as 100) results in a shift on a line on the cube.

如果我们将两位用于数据，将第三位用于奇偶校验(例如，偶校验).我们失去了4个数据点.但是它的优点是我们可以检测到单个位故障(将偶数1转换为奇数1). 奇数用*标记.而且我们看到每个奇数(错误传输)的单词都被偶数(正确传输)的单词所包围.因此，如果我们收到100，我们可以确定它是错误的.

If we use two bits for the data and the third for a parity check (say for example even parity). We lose 4 datapoints. But it has the advantage that we can detect a single bit failure (which transforms an even count of 1's into an odd count of ones). The odd numbers are marked with a *. And we see that each odd (wrongly transmitted) word is cornered by even (rightfully transmitted) words. So if we receive 100, we can be sure it is wrong.

但是(只有一点点失败)正确的表示可能是000、101或110.因此，我们可以检测到出了什么问题，但是我们无法检测出出了什么问题:

But (with a single bit failure) the correct representation could have been 000, 101 or 110. So we can detect something has been wrong but we cannot detect what was wrong:

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

这称为一位错误检测代码.

This is called a one bit error detecting code.

如果我们使用另一位进行检查，从而删除了一个数据.我们剩下1个数据位和2个校验位". 在这种情况下，假设000和111是有效的数据表示形式，而其他六个则不是.现在，如果在运输过程中碰到一点，我们就会遇到一个有趣的情况. 如果我们发送000并接收010，我们将看到010有一个有效邻居(000)和两个无效邻居(110和011).因此，现在我们知道我们打算发送000并能够纠正该错误:

If we use another bit for checking and thus remove one for the data. We are left with 1 databit and 2 "check bits". In this case, lets assume 000 and 111 are valid data representations and the other six are not. Now we have an interesting situation if one bit is mangled during transport. If we send 000 and receive 010, we see that 010 has one valid neighbor (000) and two invalid ones (110 and 011). So now we know that we intended to send 000 and are able to correct that:

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

这称为一位纠错码.

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

Please note that a one bit error correcting code is also a two bit error detecting code.

更笼统地说.

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

If you have n check bits, you have a n bit error detecting code. If you have 2n check bits, you have a n bit error correcting code.

您当然应该对有效"代码进行排序，以使它们不会彼此相邻.

Of course you should order the "valid" codes so that they do not border on each other.

这篇关于海明码如何工作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！