Skip to content

Latest commit

 

History

History
151 lines (114 loc) · 5.56 KB

海明码.md

File metadata and controls

151 lines (114 loc) · 5.56 KB
Raw

海明码基本思想是分组偶校验，由信息位(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 = 12，记为 H1~H12

校验位所在的位置是 2^(k-1)，P1~P4 对应 H1、H2、H4、H8，信息位填入剩下的空位：

H12 H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1
D8 D7 D6 D5 P4 D4 D3 D2 P3 D1 P2 P1
1 0 1 0 1 0 1 1

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 填入：

H12 H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1
D8 D7 D6 D5 P4 D4 D3 D2 P3 D1 P2 P1
1 0 1 0 0 1 0 1 1 1 1 1

最终得到的海明码为：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：

H12 H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1
D8 D7 D6 D5 P4 D4 D3 D2 P3 D1 P2 P1
正确 1 0 1 0 0 1 0 1 1 1 1 1
H2出错 1 0 1 0 0 1 0 1 1 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：

H12 H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1
D8 D7 D6 D5 P4 D4 D3 D2 P3 D1 P2 P1
正确 1 0 1 0 0 1 0 1 1 1 1 1
H11出错 1 1 1 0 0 1 0 1 1 1 1 1

代入校验方程：

  • 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：

H12 H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1
D8 D7 D6 D5 P4 D4 D3 D2 P3 D1 P2 P1
正确 1 0 1 0 0 1 0 1 1 1 1 1
H2、H9出错 1 0 1 1 0 1 0 1 1 1 0 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：

H13 H12 H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1
P5 D8 D7 D6 D5 P4 D4 D3 D2 P3 D1 P2 P1
0 1 0 1 0 0 1 0 1 1 1 1 1

最终的海明码为：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 且偶检验成功：两位错误，需重传