汉明码

在计算机科学和电信中，汉明码是线性纠错码家族。 汉明码可以检测一位和两位错误，或者在不检测未纠正错误的情况下纠正一位错误。 相比之下，简单的奇偶校验码不能纠正错误，只能检测奇数位的错误。 汉明码是完美的代码，也就是说，它们实现了块长度和最小距离为三的代码的最高可能率。

在数学上，汉明码是一类二进制线性码。 对于每个整数 r ≥ 2，都有一个码字，块长度 n = 2r − 1，消息长度 k = 2r − r − 1。因此汉明码 s 的速率为 R = k / n = 1 − r / ( 2r − 1)，这对于最小距离为 3 的代码（即从任何代码字到任何其他代码字所需的最少比特更改次数为 3）和块长度为 2r − 1 的代码来说是最高可能的。奇偶校验 -汉明码的校验矩阵是通过列出长度为r的所有非零列来构造的，这意味着汉明码的对偶码是缩短的阿达玛码。 奇偶校验矩阵具有任意两列成对线性无关的性质。

由于汉明码添加到数据中的冗余有限，它们只能在错误率较低时检测和纠正错误。 计算机内存（通常是RAM）就是这种情况，比特错误极其罕见，汉明码被广泛使用，而具有这种纠错系统的RAM就是ECC RAM（ECC内存）。 在这种情况下，通常使用具有一个额外奇偶校验位的扩展汉明码。 扩展的汉明码实现了四的汉明距离，这使得解码器能够区分何时最多出现一个一位错误以及何时发生任何两位错误。 从这个意义上说，扩展汉明码是单纠错双检错，简称SECDED。

Hamming 在周末工作，并且由于检测到错误而不得不从头开始重新启动他的程序，这让他越来越沮丧。 在一次录音采访中，汉明说，所以我说，“该死，如果机器能检测到错误，为什么它不能定位错误的位置并纠正它？”。 在接下来的几年里，他致力于纠错问题，开发了一系列越来越强大的算法。 1950 年，他发表了现在称为汉明码的内容，至今仍在 ECC 内存等应用中使用。

在汉明码之前使用了许多简单的错误检测代码，但在相同的空间开销下，没有一个像汉明码那样有效。

奇偶校验添加一位，指示前面数据中的个数（值为 1 的位位置）是偶数还是奇数。 如果在传输中改变了奇数位，消息将改变奇偶校验，此时可以检测到错误； 然而，改变的位可能是奇偶校验位本身。 最常见的约定是奇偶校验值为 1 表示数据中有奇数个 1，奇偶校验值为 0 表示有偶数个 1。 如果更改的位数为偶数，则校验位有效，不会检测到错误。

此外，奇偶校验不指示哪个位包含错误，即使它可以检测到错误。 数据必须完全丢弃并从头开始重新传输。 在嘈杂的传输介质上，成功的传输可能需要很长时间，或者可能永远不会发生。 然而，虽然奇偶校验的质量很差，但由于它只使用一个位，因此这种方法的开销最少。

五分之二代码是一种编码方案，它使用由三个 0 和两个 1 组成的五个位。 这提供了十种可能的组合，足以表示数字 0–9。 该方案可以检测所有单个位错误、所有奇数位错误和一些偶数位错误（例如两个 1 位的翻转）。 但是它仍然无法纠正任何这些错误。

当时使用的另一个代码多次重复每个数据位，以确保它被正确发送。