【软考】校验码之海明码

1.海明码(Hamming Code)是由贝尔实验室的 Richard Hamming 设计的，是一种利用奇偶性来检错和纠错的校验方法。
2.海明码的构成方法是在数据位之间的特定位置上插入k个校验位，通过扩大码距来实现检错和纠错。
3.设数据位是n位，校验位是k位，则n和必须满足以下关系:2^k-1≥n+k，减一是因为1个校验信息用来指出错误。

2. 编码规则

1.设4个校验位P₄P₃P₂P₁，8个数据位D₇D₆D₅D₄D₃D₂D₁D₀，则对应的海明码为H₁₂H₁₁H₁₀H₉H₈H₇H₆H₅H₄H₃H₂H₁。
2.P₁在海明码的第2⁰位置上，P₂在海明码的第2¹位置上，P₃在海明码的第2²位置上，P₄在海明码的第2³位置上，即H_j=P_i，j=2^i-1。
3.数据位则依序从低到高占据海明码中剩下的位置。
4.海明码中的任何一位都是由若干个校验位来校验的。
5.被校验的海明码位的下标等于所有参与校验该位的校验位的下标之和。
6.校验位由自身校验。

3. 编码过程

1.例如8位的数据位，进行海明校验需要4个校验位，因为2⁴-1=15>(8+4)，减1是因为留一个数判断整体是否有错误。
2.假如数据位为D₇D₆D₅D₄D₃D₂D₁D₀，校验位为P₄P₃P₂P₁，形成的海明码为H₁₂H₁₁H₁₀H₉H₈H₇H₆H₅H₄H₃H₂H₁。
3.按照8,4,2,1位放校验位，即H₈H₄H₂H₁放校验位P₄P₃P₂P₁，得到序列为：D₇D₆D₅D₄ P₄ D₃ D₂ D₁ P₃ D₀ P₂ P₁。
4.数据位 D₇ 的位置为12，分解为8+4，即数据位D₇由校验位 P₄ P₃ 校验。
5.数据位 D₆ 的位置为11，分解为8+2+1，即数据位D₆由校验位 P₄ P₂ P₁ 校验。
6.数据位 D₅ 的位置为10，分解为8+2，即数据位D₅由校验位 P₄ P₂ 校验。
7.数据位 D₄ 的位置为9，分解为8+1，即数据位D₄由校验位 P₄ P₁ 校验。
8.数据位 D₃ 的位置为7，分解为4+2+1，即数据位D₃由校验位 P₃ P₂ P₁ 校验。
9.数据位 D₂ 的位置为6，分解为4+2，即数据位D₂由校验位 P₃ P₂ 校验。
10.数据位 D₁ 的位置为5，分解为4+1，即数据位D₁由校验位 P₃ P₁ 校验。
11.数据位 D₀ 的位置为3，分解为2+1，即数据位D₀由校验位 P₂ P₁ 校验。
12.校验位 P₄ 的位置为8，即校验位P₄由校验位 P₄ 校验。
13.校验位 P₃ 的位置为4，即校验位P₃由校验位 P₃ 校验。
14.校验位 P₂ 的位置为2，即校验位P₂由校验位 P₂ 校验。
15.校验位 P₁ 的位置为1，即校验位P₁由校验位 P₁ 校验。
16.P₁校验P₁、D₀、D₁、D₃、D₄、D₆，使得P₁=D₀⊕D₁⊕D₃⊕D₄⊕D₆。
17.⊕表示异或，同为假，异为真，即1⊕0=1，1⊕1=0，0⊕0=0。
18.P₂校验P₂、D₀、D₂、D₃、D₅、D₆，使得P₂=D₀⊕D₂⊕D₃⊕D₅⊕D₆。
19.P₃校验P₃、D₁、D₂、D₃、D₇，使得P₃=D₁⊕D₂⊕D₃⊕D₇。
20.P₄校验P₄、D₄、D₅、D₆、D₇，使得P₄=D₄⊕D₅⊕D₆⊕D₇。

4. 举个例子

1.数据为0 1 1 0 1 0 0 1，试采用4个校验位求其偶校验方式的海明码。
2.数据位从D₇D₆D₅D₄D₃D₂D₁D₀依次为0 1 1 0 1 0 0 1。
3.校验位P₁=D₀⊕D₁⊕D₃⊕D₄⊕D₆=1⊕0⊕1⊕0⊕1=1。
4.校验位P₂=D₀⊕D₂⊕D₃⊕D₅⊕D₆=1⊕0⊕1⊕1⊕1=0。
5.校验位P₃=D₁⊕D₂⊕D₃⊕D₇=0⊕0⊕1⊕0=1。
6.校验位P₄=D₄⊕D₅⊕D₆⊕D₇=0⊕1⊕1⊕0=0。
7.即偶校验方式海明码H₁₂H₁₁H₁₀H₉H₈H₇H₆H₅H₄H₃H₂H₁ 为 D₇D₆D₅D₄ P₄ D₃ D₂ D₁ P₃ D₀ P₂ P₁
即：0 1 1 0 0 1 0 0 1 1 0 1。

5. 检测错误

1.G₁=P₁⊕D₀⊕D₁⊕D₃⊕D₄⊕D₆。
2.G₂=P₂⊕D₀⊕D₂⊕D₃⊕D₅⊕D₆。
3.G₃=P₃⊕D₁⊕D₂⊕D₃⊕D₇。
4.G₄=P₄⊕D₄⊕D₅⊕D₆⊕D₇。
5.若采用偶校验，则G₄G₃G₂G₁全为0时表示接收到的数据无错误。
5.若采用奇校验，则G₄G₃G₂G₁全为1时表示接收到的数据无错误。
6.若采用偶校验，当G₄G₃G₂G₁不全为0时说明发生了差错，G₄G₃G₂G₁的十进制值指出了发生错误的位置，例如G₄G₃G₂G₁=1010，十进制为8+2=10，说明H₁₀即D₅出错了，将其取反即可纠正错误。