汉明码

背景

汉明码的背景可以追溯到20世纪50年代，当时数字通信和数据存储技术正在迅速发展。在这个时期，数据传输和存储中的错误是一个普遍存在的问题。由于噪声、干扰、损坏等原因，数据在传输和存储过程中可能会发生错误，这会导致数据的丢失或损坏。
为了解决这个问题，人们开始研究纠错码。纠错码是一种编码方案，可以在数据传输和存储过程中检测和纠正错误。汉明码是最早的纠错码之一，它由美国数学家理查德·汉明（Richard Hamming）在20世纪50年代发明。
汉明码的主要优点是可以检测并纠正单个比特的错误。这使得它在数字通信和数据存储中得到广泛应用。例如，在计算机内存中，汉明码可以检测和纠正内存中的单个比特错误。在数字通信中，汉明码可以用于检测和纠正传输过程中的单个比特错误。
随着技术的不断发展，汉明码也在不断演化和改进。例如，扩展汉明码可以检测和纠正多个比特的错误。在实际应用中，人们还使用其他类型的纠错码，如卷积码和重复码等。这些编码方案都旨在提高数据传输和存储的可靠性和稳定性。 —— GPT 4

预备知识

奇偶校验

这是一种最简单的判断数据是否正确的办法。最常使用的是偶校验。它使用1-bit额外的数据来保证整个数据的”1”的个数是偶数。我们可以根据收到的数据里的”1”的个数来判断数据是否是正确的。偶校验可以检测出1-bit错误，但不能纠错。

汉明距离

汉明距离是两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如：
$$
\begin{aligned}
10{\color{red}1}1{\color{red}1}01\\
10{\color{red}0}1{\color{red}0}01
\end{aligned}
$$
之间的汉明距离是2。

最小汉明距离

最小汉明距离是指一个编码中，任意两个码字之间的最小汉明距离。以 2 out of 5 code (用5-bit表示0~9 10个十进制数字，5个bit里面有两个为1) 为例，它的最小汉明距离是2。

最小汉明距离与纠错能力

错误检测

仍然以 2 out of 5 code 为例，我们先列出所有可能的码字：
$$
\begin{aligned}
00011->1\\
00101->2\\
00110->3\\
01001->4\\
01010->5\\
01100->6\\
10001->7\\
10010->8\\
10100->9\\
11000->0
\end{aligned}
$$
假如原文为 $00110$，但是在传输的过程中发生了位翻转，收到的码字是 $00111$，那么我们可以知道至少有一个bit发生了错误。因为这并不是一个有效码字。一般地，如果一种编码的最小汉明距离为$d$，则它可以检测出$d-1$位错误。

错误纠正

上述的 2 out of 5 code 不能纠正错误。
然而足够多的冗余位可以使我们纠正有限的错误。最简单的例子：
要传输的信息是 $01$，在传输时我们将其重复3次 $010101$，这样即使有一位发生了位翻转，我们也可以通过另外两个copy来复原它。
Ujjal Bhowmik教授的课件说：

Given a code word $C$, we can define a neighborhood $N_k(C)$ of distance $k$ around $C$ as the set of bit patterns with Hamming distance ≤ $k$ from $C$. If up to k bits flip in a stored copy of $C$, the final bit pattern falls within $N_k(C)$.
Assume that up to $k$ bits flip in a stored bit pattern $C$ to produce a final bit pattern $F$. We know that F is in $N_k(C)$. When can we identify $C$, given only $F$? Only when $N_k(C)$ does not overlap with neighborhood $N_k(D)$ for any other code word $D$.
If we want to correct $k$ errors, we need the neighborhoods $N_k(C)$ and $N_k(D)$ to be disjoint for any pair of code words $C$ and $D$.
In other words, to correct $k$ errors, the distance between code words must be at least $2k + 1$. But that’s Hamming distance!

这一段话有点抽象，我尝试用简单一点的语言来解释。
先说结论，如果一种编码能够纠正 $k$ 个错误，那么它的最小汉明距离至少为 $2k + 1$。也就是说，最小汉明距离为 $k$ 的编码能够完成至多 $\lfloor\frac{k - 1}{2}\rfloor$的纠错。它的原理大概是这样的：
纠正位翻转的过程是无效码字才有效码字的转变，这一个过程实际上是找到了一个最接近接收到的无效码字的有效码字。我们假设一钟编码的最小汉明距离为 $2k$，但是数据在传输过程钟发成了 $k$ 位位翻转，那么它就会有两种相同汉明距离的方式变成有效码字，我们就无法确定应该使用哪一种。再比如，假设一种编码的最小汉明距离位 $2k - 1$，但是数据在传输过程中发生了 $k$ 位位翻转，那么离他最近的有效码字(离他汉明距离为 $k - 1$)并不是它的原码字，所以无法正确纠错。对于最小距离小于$2k - 1$的编码也是如此。

汉明码

汉明码是一种通用、高效且最小汉明距离为3的编码。它提供了一种纠正1-bit错误的简单方法。
首先我来介绍如何计算原始数据的汉明码。
对于一个 $N$ 位的汉明码：

1. 从最低位向最高位分别编号为1~N (注意是从1开始的)
2. 使所有第2的幂次位作为校验位，假设为第 P 位
   接下来我会以(7,4)汉明码(4-bit有效数据，3位校验位)来举例：
3. 第 P 位使得所有 使得二进制权为P且该位为1，即(P AND K) == P 的第 K 位 成为偶校验。（可能有点抽象，下面会举例）

假设一个码字为$x_7x_6x_5x_4x_3x_2x_1$，注意没有 $x_0$，那么校验位为 $x_4$, $x_2$, $x_1$。数据位为 $x_7$, $x_6$, $x_5$, $x_3$。
我们把校验位放在一起写成一个二进制数，$x_4x_2x_1$。这个二进制数刚好可以表示0~7。
$x_1$使得$x_1$, $x_3$, $x_5$, $x_7$为偶校验。因为二进制权$1=2^0，$对应第0位，$x_1$, $x_3$, $x_5$, $x_7$二进制的第0位都是1。
$x_2$使得$x_2$, $x_3$, $x_6$, $x_7$为偶校验。因为二进制权$2=2^1，$对应第1位，$x_2$, $x_3$, $x_6$, $x_7$二进制的第1位都是1。
$x_4$使得$x_4$, $x_5$, $x_6$, $x_7$为偶校验。因为二进制权$4=2^2，$对应第2位，$x_4$, $x_5$, $x_6$, $x_7$二进制的第2位都是1。

我们来看一个图

如果数据传输没有错误，每个圈都满足偶校验。如果传输过程中有一位发生了位翻转，导致一个或多个圈不满足偶校验，比如红色和黄色圈不满足偶校验而蓝色仍然满足偶校验，那我们就可以得出是第三位发生了位翻转，我们只需要翻转第三位就能得到正确的数据。
虽然我们能通过图像找到错误的位并纠正，但是当位数多的时候，我们将难以画出图像，我已我们需要一种代数化的解法。我们注意到，一组数据满足偶校验，他们的异或值为0，反之为1。在上面的图中，重叠部分的数字是所在圈的数字之和。在上一段所说的例子之中，红色圈的异或值为1，黄色圈的异或值为1，蓝色圈的异或值为0。将4, 2, 1作为权重将对应圈的异或值排列成二进制数，即 $011$，也就是十进制3，也就是第三位发生了位翻转。
总结一下，我们刚刚事实上算了3个异或：
$$
\begin{aligned}
e_1 = x_1 \oplus x_3 \oplus x_5 \oplus x_7\\
e_2 = x_2 \oplus x_3 \oplus x_6 \oplus x_7\\
e_4 = x_4 \oplus x_5 \oplus x_6 \oplus x_7
\end{aligned}
$$
那么二进制数 $e_4e_2e_1$ 就是发生位翻转的位数。如果$e_4e_2e_1$为0，说明三个圈都满足偶校验，没有发生位翻转。

一般地，为了找到哪一位发生了位翻转，我们只需要计算出上述的每一个 $e_{2^k}$，在排列成二进制数，就能得到发生位翻转的位数。

如果还是不能我们是如何定位到位翻转的位数的，我像用一道数学题来说明：

假设你1000酒，其中一瓶有剧毒，其余没有毒，不论是喝到有毒酒还是含有有毒酒的混合液体都会在喝后一个小时死亡。现在你有10只小白鼠，请问如何只使用一小时找到那瓶有毒的酒？

解：我们把1000瓶酒从1~1000编号并写成10位二进制，把10只小白鼠从1~10编号。每只小白鼠分别对应二进制的一位。比如小白鼠1对应二进制的第1位，小白鼠2对应二进制的第2位。
我们让小白鼠1喝所有二进制第1位为1的酒，小白鼠2喝所有二进制第2位为1的酒，以此类推。
1小时后，如果小白鼠1死了，那么有毒酒的二进制第一位一定为1，如果小白鼠2死了，那么有毒酒的二进制第二位一定为1，以此类推。于是我们能够得到有毒酒编号的二进制数。这样我们就能在一个小时的时候找到那瓶有毒的酒。

SEC-DED Code

SEC-DED Code (Single Error Correction, Double Error Detection) 是带有奇偶校验的汉明码，是汉明码的一种拓展。它在汉明码的基础上增加了一位奇偶校验位，我们通常使用带有奇校验的汉明码(在汉明码的最高位之前增加奇校验位)。这样，这种编码的最小汉明距离变成了4。它最多能纠正 $\lfloor \frac{4-1}{2} \rfloor = 1$ 位错误。但是当发生两位错误时，由于到最近的正确码字的距离为2，有不止一种可能，所以无法纠错。这就能避免原本汉明码在处理两位时候的错误纠错。
下面举一个具体的例子：
传输前的原始数据为 $1001$，它的带有奇校验的汉明码为 $01001100$。在传输的过程中发生了一位位翻转变成了 $01001000$。为了处理错误，我们先按照正常汉明码的步骤处理它的最低7-bit，得到 $e_4e_2e_1=100$，纠正第4位错误后变成 $01001100$，这时再判断最高位，看是否满足奇校验，如果是，则成功纠正一位错误，如果不满足奇校验，说明发生了两位错误，无法纠正。