关于组成原理:海明码的原理

海明码根本思维是 分组偶校验 ，由信息位(n) 和校验位 (k) 组成，海明码的校验位计算公式：2^k >= n+k+1

• 2^k 示意：k 个校验位对应 2^k 种状态
• n + k + 1 示意：n + k 代表任何一位都可能出错，1 代表一种正确的状态

原理

假如数据位 D8~D1 = 10101011，求海明码？

首先算出校验位，代入公式 2^k >= n + k + 1

• n = 8 -> k = 4

校验位算出是 4 位，记为：P1~P4

海明码位数由信息位和校验位组成：8 + 4 = 13，记为 H1~H12

校验位所在的地位是 2^(k-1)，P1~P4 对应 H1、H2、H4、H8，P5 是偶测验，在最后面 H13；信息位填入剩下的空位：

D1~D8 曾经填入相应的地位，当初须要计算残余的 P1~P4 的值。

求校验位须要先晓得信息位所在位置的二进制（k 位，对应校验位）

• 信息位所在位置：H3/H5/H6/H7/H9/H10/H11/H12

• 信息位的最初一位为 P1，最初第二位为 P2，以此类推

  	P4	P3	P2	P1
  H3	0	0	1	1
  H5	0	1	0	1
  H6	0	1	1	0
  H7	0	1	1	1
  H9	1	0	0	1
  H10	1	0	1	0
  H11	1	0	1	1
  H12	1	1	0	0

校验位对应各信息位二进制数为 1 的组合：

• P1 对应的信息位 H3/H5/H7/H9/H11
• P2 对应的信息位 H3/H6/H7/H10/H11
• P3 对应的信息位 H5/H6/H7/H12
• P4 对应的信息位 H9/H10/H11/H12

将各信息位的值进行异或运算，求得校验位的值：

• P1 -> H3/H5/H7/H9/H11 -> D1⊕D2⊕D4⊕D5⊕D7 -> 1⊕1⊕1⊕0⊕0 -> 1
• P2 -> H3/H6/H7/H10/H11 -> D1⊕D3⊕D4⊕D6⊕D7 -> 1⊕0⊕1⊕1⊕0 -> 1
• P3 -> H5/H6/H7/H12 -> D2⊕D3⊕D4⊕D8 -> 1⊕0⊕1⊕1 -> 1
• P4 -> H9/H10/H11/H12 -> D5⊕D6⊕D7⊕D8 -> 0⊕1⊕0⊕1 -> 0

P1P2P3P4 -> 1110 填入：

最终失去的海明码为：101001011111

纠错

海明码纠错的形式是：各校验位用偶校验进行校验

通过下面失去校验方程是：

• S1：P1⊕D1⊕D2⊕D4⊕D5⊕D7 -> 1⊕1⊕1⊕1⊕0⊕0 -> 0
• S2：P2⊕D1⊕D3⊕D4⊕D6⊕D7 -> 1⊕1⊕0⊕1⊕1⊕0 -> 0
• S3：P3⊕D2⊕D3⊕D4⊕D8 -> 1⊕1⊕0⊕1⊕1 -> 0
• S4：P4⊕D5⊕D6⊕D7⊕D8 -> 0⊕0⊕1⊕0⊕1 -> 0

一位出错

例 1：

代入校验方程：

• S1：P1⊕D1⊕D2⊕D4⊕D5⊕D7 -> 1⊕1⊕1⊕1⊕0⊕0 -> 0
• S2：P2⊕D1⊕D3⊕D4⊕D6⊕D7 -> 0⊕1⊕0⊕1⊕1⊕0 -> 1
• S3：P3⊕D2⊕D3⊕D4⊕D8 -> 1⊕1⊕0⊕1⊕1 -> 0
• S4：P4⊕D5⊕D6⊕D7⊕D8 -> 0⊕0⊕1⊕0⊕1 -> 0

失去谬误位S4S3S2S1：0010，转为十进制为 2，也就是说 H2 处错了。

例 2：

代入校验方程：

• S1：P1⊕D1⊕D2⊕D4⊕D5⊕D7 -> 1⊕1⊕1⊕1⊕0⊕1 -> 1
• S2：P2⊕D1⊕D3⊕D4⊕D6⊕D7 -> 1⊕1⊕0⊕1⊕1⊕1 -> 1
• S3：P3⊕D2⊕D3⊕D4⊕D8 -> 1⊕1⊕0⊕1⊕1 -> 0
• S4：P4⊕D5⊕D6⊕D7⊕D8 -> 0⊕0⊕1⊕1⊕1 -> 1

失去谬误位S4S3S2S1：1011，转为十进制为 11，也就是说 H11 处错了。

S4S3S2S1 指明了出错位在哪里

两位出错

例 1：

代入校验方程：

• S1：P1⊕D1⊕D2⊕D4⊕D5⊕D7 -> 0⊕1⊕1⊕1⊕1⊕1 -> 1
• S2：P2⊕D1⊕D3⊕D4⊕D6⊕D7 -> 1⊕1⊕0⊕1⊕1⊕1 -> 1
• S3：P3⊕D2⊕D3⊕D4⊕D8 -> 1⊕1⊕0⊕1⊕1 -> 0
• S4：P4⊕D5⊕D6⊕D7⊕D8 -> 1⊕1⊕1⊕1⊕1 -> 1

失去谬误位S4S3S2S1：1011，转为十进制为 11，是否阐明了 H11 位出错了呢？

所以 海明码只有一位的纠错能力。

全校验位

为了保障海明码的校验能力，引入全校验位，对海明码整体进行偶校验

因为要进行偶校验，下面的海明码有八个 1，所以最高位 H13 是 0：

最终的海明码为：0101001011111

总结

海明码原理：

1. 确定海明码位数：信息位(n) + 校验位(k)

   • 通过信息位算出校验位：2^k >= n+k+1
2. 校验位的地位编号：2^(k-1)
3. 将信息位填入残余地位
4. 把信息位的地位编号用二进制数示意

5. 二进制数的每一位对应校验位

   • 将二进制数是 1 的进行组合
6. 用异或运算算出校验位，失去海明码
7. 对海明码整体进行偶校验失去最终的海明码

判断根据：

• S4S3S2S1 = 0000 且偶测验胜利：无谬误
• S4S3S2S1 ≠ 0000 且偶测验失败：一位谬误，纠正即可
• S4S3S2S1 ≠ 0000 且偶测验胜利：两位谬误，需重传