海明校验 | Mute

海明码是一种多重奇偶检错系统，用于检错和纠错。

以下内容都以例题：“设8位有效信息为01101110，写出它的的海明校验码” 为例。

1.校验位的位数

设海明校验码H_n…H₂H₁共有n位，原始有效信息D_k…D₂D₁共k位，称为(n,k)码，校验位P_r…P₂P₁，包含r个偶校验组，n = k + r 。

为了能指出n位海明码中的所有一位错，每个原始数据位至少位于两个以上的校验组，这样才能通过检错码G_r…G₂G₁对照检错。

n，k，r应满足：n = k + r <= 2 ^r - 1

表为 k 与 r 不同组合的关系

k	1	2 ~ 4	5 ~ 11	12 ~ 26	27 ~ 57
r	2	3	4	5	6

例题原始信息共8位，k = 8， r = 4 ，n = 12 ，称为（12 ，8）码。

2.编码规则

1.校验位在海明码中的映射

校验位P_1-4对应在海明码H_1-12中位置的关系为 2^{n - 1} （n为P中的1~4），如P₁ 对应H_(2^1-1) 就是H₁，P₂ 对应H_(2^2-1) 就是H₂ ，P₃ 对应H_(2^3-1) 就是H₄，P₄ 对应H_(2^4-1) 就是H₈ 。（详见下表）

所有校验位都应该存放在 幂次方 位上，校验位位置映射完成后，将原始数据位D₁D₂…D_k依次填入即可。

所以海明码H₁H₂…H₁₂就是 P₁P₂D₁P₃D₂D₃D₄P₄ D₅D₆D₇D₈

校验位的逻辑表达式

注：” ⊕ “ 符号为异或，相同取0，不同取1 。

P₁ = D₁ ⊕ D₂ ⊕ D₄ ⊕ D₅ ⊕ D₇ = 1（ D₁、…、D₇为下表中P₁所对应的G₁校验组中标记过的原始数据位，以下同理）

P₂ = D₁ ⊕ D₃ ⊕ D₄ ⊕ D₆ ⊕ D₇ = 1

P₃ = D₂ ⊕ D₃ ⊕ D₄ ⊕ D₈ = 0

P₄ = D₅ ⊕ D₆ ⊕ D₇ ⊕ D₈ = 1

代入数据，所以原始数据01101110的海明码为 110011011110

2.校验组（G_{1 ~ 4}）

在G₁行中共有6个 “ √ ” 标记，其对应的海明码分别为H₁、H₃、H₅、H₇、H₉、H₁₁ ，它们所对应的检错码均为 “ ###1 ”（第四位数为1），代表H₁、H₃、H₅、H₇、H₉、H₁₁ 都参与了校验组G₁的校验。（详见下表）

在G₃行中共有5个 “ √ ” 标记，其对应的海明码分别为H₄、H₅、H₆、H₇、H₁₂ ，它们所对应的检错码均为 “ #1## ”（第二位数为1），代表H₄、H₅、H₆、H₇、H₁₂ 都参与了校验组G₃的校验。

校验组G₂、G₄ 同理。

校验组分组为：

G₁ ：P₁ D₁ D₂ D₄ D₅ D₇

G₂ ：P₂ D₁ D₃ D₄ D₆ D₇

G₃ ：P₃ D₂ D₃ D₄ D₈

G₄ ：P₄ D₅ D₆ D₇ D₈

校验组的逻辑表达式：

G₁ = P₁ ⊕ D₁ ⊕ D₂ ⊕ D₄ ⊕ D₅ ⊕ D₇ = 0

G₂ = P₂ ⊕ D₁ ⊕ D₃ ⊕ D₄ ⊕ D₆ ⊕ D₇ = 0

G₃ = P₃ ⊕ D₂ ⊕ D₃ ⊕ D₄ ⊕ D₈ = 0

G₄ = P₄ ⊕ D₅ ⊕ D₆ ⊕ D₇ ⊕ D₈ = 0

表为例题（12，8）码对应的编码规则

海明码	H₁	H₂	H₃	H₄	H₅	H₆	H₇	H₈	H₉	H₁₀	H₁₁	H₁₂
映射关系	P₁	P₂	D₁	P₃	D₂	D₃	D₄	P₄	D₅	D₆	D₇	D₈
检错码	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100
G₁	√		√		√		√		√		√
G₂		√	√			√	√			√	√
G₃				√	√	√	√					√
G₄								√	√	√	√	√

3.检错与纠错

在接收端收到海明码后，按上述分组检验每组的正确性,每组异或为0则该组没出错，否则该组出错。

若G₄G₃G₂G₁ = 0000 ，则大概率没有出错。

若G₄G₃G₂G₁ = 1010 ，则G₄和G₂出错，只有D₆和D₇都参与了检验组G₄和G₂的校验，但D₇还参与了检验组G₁的校验，如果D₇出错，检验组G₁也应该出错，所以出错的位置是D₆ ；也可理解为1010的十进制是10，则海明码H₁₀（数据D₆）出错，将H₁₀取反即可。

注：若十进制对应的位置是校验位P出错，不需要纠正，因为我们只需要确保数据不出错就可以。

若例题中接收方收到的有效信息变为01101111，则G₄G₃G₂G₁ = 1100 ，海明码H₁₂（数据D₈）出错，将H₁₂取反为0即可。