Hanming Code

汉明码的组成

汉明码是由 Richard Hanming 于 1950 年提出的，具有一位纠错能力

由纠错理论得 L - 1 = D + C (D ≥ C)
即编码最小距离 L 越大，则其检测错误的位数 D 越大，纠正错误的位数 C 也越大，且纠错能力恒小于或等于检错能力

设欲检测的二进制代码为 n 位，为使其具有纠错能力，需添加 k 位检测位，组成 n + k 位的代码，k 应满足
2^k - 1 ≥ n + k

n	k(min)
1	2
2~4	3
5~11	4
12~26	5
27~57	6
58~120	7

设 n + k 位代码自左至右依次编为第 1, 2, 3, …, n + k 位，而将 k 位检测位记作 C_i (i = 1, 2, 4, 8, …)，分别安插在 n + k 位代码编号的第 1, 2, 4, 8, …,
2^{k - 1} 位上

Ci	检测
C1	检测的 g1 小组包含 1, 3, 5, 7, 9, 11, … 位
C2	检测的 g2 小组包含 2, 3, 6, 7, 10, 11, 14, 15, … 位
C4	检测的 g3 小组包含 4, 5, 6, 7, 12, 13, 14, 15, … 位
C8	检测的 g4 小组包含 8, 9, 10, 11, 12, 13, 14, 15, 24, … 位

有如下特点：

1. 每个小组 g_i 有一位且仅有以为为它所独占，这一位是其他小组所没有的，即 g_i 小组独占第 2^{i - 1} 位
2. 每两个小组 g_i 和 g_j 共同占有一位是其他小组没有的，即每两小组 g_i 共同占有第 2^{i - 1} + 2^{j - 1} 位
3. 每三个小组 g_i、g_j 和 g_l 共同占有第 2^{i - 1} + 2^{j - 1} + 2^{l - 1} 位，是其他小组所没有的
4. 以此类推

令 b₄b₃b₂b₁ = 0101，则
C₁ = b₄ ⊕ b₃ ⊕ b₁ = 0
C₂ = b₄ ⊕ b₂ ⊕ b₁ = 1
C₄ = b₃ ⊕ b₂ ⊕ b₁ = 0
故 0101 的汉明码为 0100101

汉明码的纠错过程

汉明码的纠错过程实际上是对传送后的汉明码形成新的检测位 P_i，根据 P_i 的状态便可直接指出错误的位置
P₁ = 1 ⊕ 3 ⊕ 5 ⊕ 7 = C₁ ⊕ b₄ ⊕ b₃ ⊕ b₁
P₂ = 2 ⊕ 3 ⊕ 6 ⊕ 7 = C₂ ⊕ b₄ v b₂ ⊕ b₁
P₄ = 4 ⊕ 5 ⊕ 6 v 7 = C₄ ⊕ b₃ v b₂ ⊕ b₁

设已知传送的正确汉明码为 0100101，若传送后接收到的汉明码为 0100111，其出错位可以按照以下步骤确定

二进制序号	1	2	3	4	5	6	7
正确的汉明码	0	1	0	0	1	0	1
接收到的汉明码	0	1	0	0	1	1	1

则新的检测位为

P₄ = 4 ⊕ 5 ⊕ 6 ⊕ 7 = 0 ⊕ 1 ⊕ 1 ⊕ 1 = 1
P₂ = 2 ⊕ 3 ⊕ 6 ⊕ 7 = 1 ⊕ 0 ⊕ 1 ⊕ 1 = 1
P₁ = 1 ⊕ 3 ⊕ 5 ⊕ 7 = 0 ⊕ 0 ⊕ 1 ⊕ 1 = 0

P₄P₂P₁ = 110 = 6
所以是第 6 位出错

汉明码常常被用在纠错一位的场合，若欲实现检错两位，实用时还得再增添一位检测位