海明码的目的是能够纠正一位误码.假设信息码共有 n 位,海明码共有 h 位,那么总共的码长为 n + h 位.为能检测出 n + h 位编码中其中一位的错误,海明码必须能够表示至少 n + h + 1 种状态,其中 n + h 种表示 n + h 位编码中有一位错误,另外还需要一种来表示整个编码正确无误.则海明码的长度需要满足下列关系：
2 h >= n + h + 1
于是根据这个式子我们可以得出以下的关系表：
h 2 3 4 5 6 7 8
n 1 4 11 12~26 27~57 58~120 121~247
以 4 位信息位为例,由上表可以看出需要的海明码长度为 3.
设信息位为 x4x3x2x1,添加的 3 位海明码为 a3a2a1,信息码和海明码组合之后得到的码为 H7H6H5H4H3H2H1.
错误 无 H1 H2 H3 H4 H5 H6 H7
C1 0 1 0 1 0 1 0 1 C1 = H1 + H3 + H5 + H7 = 0
C2 0 0 1 1 0 0 1 1 C2 = H2 + H3 + H6 + H7 = 0
C3 0 0 0 0 1 1 1 1 C3 = H4 + H5 + H6 + H7 = 0
如上表,在H1～H7中添加的 3 位海明码使得 C1～C3 的值为零.其中C1～C3为校验和.这样当 Hn 传输出错时,有 (C3C2C1)2 = n.
令 H1 = a1,H2 = a2,H4 = a3,
则得出
H7H6H5H4H3H2H1 = x4x3x2a3x1a2a1
将上面的关系代入C1～C3的计算公式,得到
C1 = H1 + H3 + H5 + H7 = a1 + x1 + x2 + x4 = 0
C2 = H2 + H3 + H6 + H7 = a2 + x1 + x3 + x4 = 0
C3 = H4 + H5 + H6 + H7 = a3 + x2 + x3 + x4 = 0
即
a1 + x1 + x2 + x4 = 0
a2 + x1 + x3 + x4 = 0
a3 + x2 + x3 + x4 = 0
即
a3 = x4 + x3 + x2
a2 = x4 + x3 + x1
a1 = x4 + x2 + x1
为何选择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.