汉明码

在电信领域中，汉明码（hamming code），也称为海明码，是(7,4)汉明码推广得到的一种线性纠错码，由理查德·卫斯里·汉明于1950年发明。相比而言，简单的奇偶检验码除了不能纠正错误之外，也只能侦测出奇数个的错误。汉明码是完备码，它在于它分组长度相同、最小距离为3的码中能达到最高的码率。

用数学术语来说，汉明码是一种二元线性码。对于所有整数 r ≥ 2，存在一个分组长度 n = 2r − 1、k = 2r − r − 1 编码。因此汉明码的码率为 R = k / n = 1 − r / (2r − 1)，对于最小距离为3、分组长度为 2r − 1 的码来说是最高的。汉明码的奇偶检验矩阵的是通过列出所有长度为 r 的非零列向量构成的。

## 历史

汉明码的发明者理查德·卫斯里·汉明在1948年，运用贝尔模型V（Bell Model V）电脑于贝尔实验室（Bell Labs）工作。输入端是依靠打孔卡（Punched Card），这不免会造成些读取错误。在工作日，当机器检测到错误将停止并闪灯（flash lights），使得操作员能够解决这个错误。在周末和下班期间，没有操作者的情况下，机器只会简单地转移到下一个工作。

汉明在周末工作，他对于不可靠的读卡机发生错误后，总是不得不重新启动程序变得愈来愈沮丧。在接下来的几年中，他为了解决侦错的问题，开发了功能日益强大的侦错算法。在1950年，他发表了今日所称的汉明码，并且时至今日仍在修正错误内存上显示其应用价值。

### 汉明码之前

人们在汉明码出现之前使用过多种检查错误的编码方式，但是没有一个可以在和汉明码在相同空间消耗的情况下，得到相等的效果。

#### 奇偶

奇偶校验是一种添加一个奇偶位元用来指示之前的数据中包含有奇数还是偶数个1的检验方式。如果在传输的过程中，有奇数个位元发生了改变，那么这个错误将被检测出来（注意奇偶位元本身也可能改变）。一般来说，如果数据中包含有奇数个1的话，则将奇偶位元设定为1；反之，如果数据中有偶数个1的话，则将奇偶位元设定为0。换句话说，原始数据和奇偶位元组成的新数据中，将总共包含偶数个1.

奇偶校验并不总是有效，如果数据中有偶数个位元发生变化，则奇偶位元仍将是正确的，因此不能检测出错误。而且，即使奇偶校验检测出了错误，它也不能指出哪一位元出现了错误，从而难以进行更正。数据必须整体丢弃并且重新传输。在一个噪音较大的媒介中，成功传输数据可能需要很长时间甚至不可能完成。虽然奇偶校验的效果不佳，但是由于他只需要一位元额外的空间开销，因此这是开销最小的检测方式。并且，如果知道了发生错误的位元，若将该位元取反，奇偶校验还可以恢复数据。

#### 五取二码

五取二码使用由3个0和2个1组成的五个位元，以此提供十种可能的组合来表示数字 0-9。该方案可以检测所有单比特错误、所有奇数位元错误和一些偶数位元错误（例如两个 “1”位元的翻转）。但是它无法自行纠正这些错误。

## 汉明码

如果一条信息中包含更多用于纠错的位元，且通过妥善安排这些纠错位元使得不同的出错位元产生不同的错误结果，那么我们就可以找出出错位元了。在一个7位元的信息中，单个位元出错有7种可能，因此3个错误控制位元就足以确定是否出错及哪一位元出错了。

汉明研究了包括五取二码在内的编码方案，并归纳了他们的想法。

### 通用算法

下列通用算法可以为任意位元数字产生一个可以纠错一位元（Single Error Correcting）的汉明码。

- 从1开始给数字的数据位元（从左向右）标上序号, 1，2，3，4，5...
- 将这些数据位元的位置序号转换为二进制，1, 10, 11, 100, 101,等。
- 数据位元的位置序号中所有为二的幂次方的位元（编号1，2，4，8，等，即数据位元位置序号的二进制表示中只有一个1）是校验位元
- 所有其它位置的数据位元（数据位元位置序号的二进制表示中至少2个是1）是新的数据位元
- 每一位元的数据包含在特定的两个或两个以上的校验位元中，这些校验位元取决于这些数据位元的位置数值的二进制表示
- 校验位元1覆盖了所有数据位元位置序号的二进制表示倒数第一位元是1的数据：1（校验位元自身，这里都是二进制，下同），11，101，111，1001，等
- 校验位元2覆盖了所有数据位元位置序号的二进制表示倒数第二位元是1的数据：10（校验位元自身），11，110，111，1010，1011，等
- 校验位元4覆盖了所有数据位元位置序号的二进制表示倒数第三位元是1的数据：100（校验位元自身），101，110，111，1100，1101，1110，1111，等
- 校验位元8覆盖了所有数据位元位置序号的二进制表示倒数第四位元是1的数据：1000（校验位元自身），1001，1010，1011，1100，1101，1110，1111，等
- 简而言之，所有校验位元覆盖了数据位置和该校验位元位置的二进制与的值不为0的数。

采用奇校验还是偶校验都是可行的。偶校验从数学的角度看更简单一些，但在实践中并没有区别。

校验位元一般的规律可以如下表示：

数据位元位置｜1｜2｜3｜4｜5｜6｜7｜8｜9｜10｜11｜12｜13｜14｜15｜16｜17｜18｜19｜20｜...

编码后数据位置｜p1｜p2｜d1｜p4｜d2｜d3｜d4｜p8｜d5｜d6｜d7｜d8｜d9｜d10｜d11｜p16｜d12｜d13｜d14｜d15

奇偶校验位元覆盖率｜p1｜X｜X｜X｜X｜X｜X｜X｜X｜X｜X

p2｜X｜X｜X｜X｜X｜X｜X｜X｜X｜X

p4｜X｜X｜X｜X｜X｜X｜X｜X｜X

p8｜X｜X｜X｜X｜X｜X｜X｜X

p16｜X｜X｜X｜X｜X

表中只给出了20个编码后的位元（5个奇偶校验位元，15个数据位元）。观察上表可发现一个比较直观的规律：第i个检验位元是第2i-1位元，从该位元开始，检验2i-1位元，跳过2i-1位元......依次类推。例如上表中第3个检验位元p4从第23-1=4位元开始，检验4、5、6、7共4位元，然后跳过8、9、10、11共4位元，再检验12、13、14、15共4位元......

要检查某一位元的错误，则需检查某一位元所包含的所有奇偶校验位元。这种错误的模式被叫做伴随式错误。如果所有奇偶校验位元是正确的，就没有错误。除此以外的情况，错误的奇偶校验位元的位置的和将识别错误的位元。例如，如果位置为1、2、8的奇偶校验位元指示了一个错误，那么位置为1+2+8=11的位元出错了。如果只有一个奇偶校验位元指示了错误，那么该奇偶校验位元自身出错了。

### 例子

对11000010进行汉明编码，求编码后的码字。

- 列出表格，从左往右（或从右往左）填入数字，但2的次方的位置不填。

位置｜1｜2｜3｜4｜5｜6｜7｜8｜9｜10｜11｜12

数据｜1｜1｜0｜0｜0｜0｜1｜0

- 把数据行有1的列的位置写为二进制。

位置｜1｜2｜3｜4｜5｜6｜7｜8｜9｜10｜11｜12

数据｜1｜1｜0｜0｜0｜0｜1｜0

二进制｜0011｜0101｜1011

- 收集所有二进制数字，求异或。$0011 \oplus 0101 \oplus 1011 =1101$

- 把1101依次填入表格中2的次方的位置（低位元在左）。

位置｜1｜2｜3｜4｜5｜6｜7｜8｜9｜10｜11｜12

数据｜1｜1｜0｜0｜0｜0｜1｜0

二进制｜0011｜0101｜1011

校验｜1｜0｜1｜1

- 所以编码后的码字是101110010010。

## 带附加奇偶校验码的汉明码（SECDED）

加一个位元元在数列的最前面，采用奇校验码或偶校验码，用以检验后面的汉明码是否有错。

## (7,4)汉明码

<image>

1950年，汉明发明了(7,4)代码。其编码由4资料位元元到7位元，增加三个奇偶校验码。(7,4)汉明码可以检测并纠正单位元元错误，且也能检测双位元元错误。

## 建立奇偶检验矩阵

矩阵$\mathbf{G} := \begin{pmatrix} I_k | -A^T \\ \end{pmatrix}$被称为（标准）生成矩阵线性(n,k)码。

和$\mathbf{H} := \begin{pmatrix} A | I_{n-k} \\ \end{pmatrix}$被称为奇偶检验矩阵。

## 编码

范例

从上述矩阵我们有2k=24=16码词。

二进制码$\overrightarrow{x}$的码词可以从$\overrightarrow{x}=\overrightarrow{a}G$得到。对$\overrightarrow{a}=a_1a_2a_3a_4$和$a_i$存在$F_2$(一个只有0和1的二元域）。

故此码表即是所有4个三元组（k个三元组）。

因而，（1,0,1,1）编码为（0,1,1,0,0,1,1）。

## (8,4)汉明码

<image>

(7,4)汉明码可以很容易地编码为一个(8,4)码，通过在(7,4)编码词（参见(7,4)汉明码）上附加一个额外的奇偶位元。

这可以用下面修正的矩阵相加：

$$\mathbf{G} := \begin{pmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\ 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \end{pmatrix}_{8,4}$$

和

$\mathbf{H} := \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0\\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{pmatrix}_{4,8}$。

注意，$\mathbf{H}$并非用标准形式表示。为了得到$\mathbf{G}$，原子行操作能够被用来获得一个等价的矩阵对陈形式的$\mathbf{H}$：

$\mathbf{H} = \left(\left.\begin{array}{cccc} 0 & 1 & 1 & 1\\ 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1\\ 1 & 1 & 1 & 0\end{array}\right|\begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\end{array}\right)_{4,8}$。

## 外部链接

- CGI script for calculating Hamming distances（from R. Tervo, UNB, Canada）