海明码

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

• 2^k 表示：k 个校验位对应 2^k 种状态

• n + k + 1 表示：n + k 代表任何一位都可能出错，1 代表一种正确的状态

所有的幂次位都是校验位，代表一组的偶校验值。

1. 确定海明码位数：信息位(n) + 校验位(k) :通过信息位算出校验位：2^k >= n+k+1

2. 校验位的位置编号：2^(k-1)

3. 将信息位填入剩余位置

4. 把信息位的位置编号用二进制数表示

5. 二进制数的每一位对应校验位.将二进制数是 1 的进行组合

6. 用异或运算算出校验位，得到海明码

7. 对海明码整体进行偶校验得到最终的海明码

假设数据为10101011

1. 求校验位k，代入公式 2^k >= n + k + 1。校验位算出是 k=4位，记为：P1~P4

2. 海明位h：由信息位和校验位组成：8 + 4 = 12，记为 H1~H12

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

1. 计算剩余的 P1~P4 的值。求校验位需要先知道信息位所在位置的二进制（k 位，对应校验位）

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

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

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

• P1 对应的信息位 H3/H5/H7/H9/H11

• P2 对应的信息位 H3/H6/H7/H10/H11

• P3 对应的信息位 H5/H6/H7/H12

• P4 对应的信息位 H9/H10/H11/H12

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

- P4 = H9/H10/H11/H12 → D5⊕D6⊕D7⊕D8 → 0⊕1⊕0⊕1 → 0

- P3 = H5/H6/H7/H12 → D2⊕D3⊕D4⊕D8 → 1⊕0⊕1⊕1 → 1

- P2 = H3/H6/H7/H10/H11 → D1⊕D3⊕D4⊕D6⊕D7 → 1⊕0⊕1⊕1⊕0 → 1

- P1 = H3/H5/H7/H9/H11 → D1⊕D2⊕D4⊕D5⊕D7 → 1⊕1⊕1⊕0⊕0 → 1

1. 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

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

S4S3S2S1 = 0000 且整体偶检验成功：无错误

S4S3S2S1 ≠ 0000 且整体偶检验失败：一位错误，纠正即可

S4S3S2S1 ≠ 0000 且整体偶检验成功：两位错误，需重传

一位出错

代入校验方程：

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 指明了出错位在哪里

两位出错

代入校验方程：

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

同一编码中，任意两个合法编码之间不同二进制位数的最小值

0011 与 0001 的码距为 1，一位错误时无法识别

0000、0011、0101、0110、1001、1010、1100、1111 等编码码距为 2。 任何一位发生变化，如 0000 变成 1000 就从有效编码变成了无效编码，容易检测到这种错误

校验码中增加冗余项的目的就是为了增大码距

1. 码距 ≥ e+1 : 可检测 e 个错误

2. 码距 ≥ 2t+1 : 可纠正 t 个错误

3. 码距 ≥ e+t+1 : 可纠正 t 个错误，同时检测 e 个错误(e ≥ t)