Dutor

海明码的目的是能够纠正一位误码。假设信息码共有 n 位，海明码共有 h 位，那么总共的码长为 n + h 位。为能检测出 n + h 位编码中其中一位的错误，海明码必须能够表示至少 n + h + 1 种状态，其中 n + h 种表示 n + h 位编码中有一位错误，另外还需要一种来表示整个编码正确无误。则海明码的长度需要满足下列关系：

2 ^h >= n + h + 1

于是根据这个式子我们可以得出以下的关系表：

以 4 位信息位为例，由上表可以看出需要的海明码长度为 3。

设信息位为 x₄x₃x₂x₁，添加的 3 位海明码为 a₃a₂a₁，信息码和海明码组合之后得到的码为 H₇H₆H₅H₄H₃H₂H₁。

如上表，在H₁～H₇中添加的 3 位海明码使得 C₁～C₃ 的值为零。其中C₁～C₃为校验和。这样当 H_n 传输出错时，有 (C₃C₂C₁)₂ = n。

令 H₁ = a₁, H₂ = a₂, H₄ = a₃,
则得出

H₇H₆H₅H₄H₃H₂H₁ = x₄x₃x₂a₃x₁a₂a₁

将上面的关系代入C₁～C₃的计算公式，得到
C₁ = H₁ + H₃ + H₅ + H₇ = a₁ + x₁ + x₂ + x₄ = 0
C₂ = H₂ + H₃ + H₆ + H₇ = a₂ + x₁ + x₃ + x₄ = 0
C₃ = H₄ + H₅ + H₆ + H₇ = a₃ + x₂ + x₃ + x₄ = 0

即
a₁ + x₁ + x₂ + x₄ = 0
a₂ + x₁ + x₃ + x₄ = 0
a₃ + x₂ + x₃ + x₄ = 0

即
a₃ = x₄ + x₃ + x₂
a₂ = x₄ + x₃ + x₁
a₁ = x₄ + x₂ + x₁

为何选择H1、H2、H4作为校验码而不是H1H2H3？
这是因为校验码必须使C3C2C1都为0，而根据公式
C1 = H1 + H3 + H5 + H7 = 0
C2 = H2 + H3 + H6 + H7 = 0
C3 = H4 + H5 + H6 + H7 = 0
要想使得对任何x4×3×2×1都能求出唯一的a3a2a1，
那么只能选择H4H2H1.
假设选择H3=a3，那么H3是等于H7+H5+H1，还是H7+H6+H2呢？
所以只能选择在三个式子中各出现一次的H4H2H1。