2.6 海明校验

（1）原理

海明校验同CRC校验一样，信息位数k和校验位数r应满足：$k + r <= 2 ^ r - 1$;

设k + r位海明码从左到右依次为$1, 2, 3, ......, k + r$位， r位校验位记为$P_i(i = 1, 2, 3, …)$，分别位于$k + r$位海明编码的第$2 ^ {i-1}（i = 1, 2, …, r）$位上，其余位依次放置被校验的数据位。

如：
$ (7, 4)$海明校验码（$7$个信息位和$4$个校验位）中校验位和被校验信息的排列关系如下：

其中$P_i$为校验位，$b_i$为信息位；

（2）海明码的校验及其实现：

$H_j$位的数据被编号小于$j$的若干个海明位号之和等于$j$的校验位所校验
(由于编号的二进制表示中只有一个$1$的二进制位都被校验码占了，因此任意的信息位都至少有两个校验位校验)

由此可采用偶校验来计算出$P_1$ ~ $P_4$四个校验位的值；

因此：
$P_1 = b_1 \bigoplus b_2 \bigoplus b_4 \bigoplus b_5 \bigoplus b_6$
$P_2 = b_1 \bigoplus b_3 \bigoplus b_4 \bigoplus b_6 \bigoplus b_7$
$P_3 = b_2 \bigoplus b_3 \bigoplus b_4$
$P_4 = b_5 \bigoplus b_6 \bigoplus b_7$

例如：
设被传送的信息$b_1b_2b_3b_4b_5b_6b_7 = 1011000$, 采用偶校验；

则：
$P_1 = b_1 \bigoplus b_2 \bigoplus b_4 \bigoplus b_5 \bigoplus b_6 = 1 \bigoplus 0 \bigoplus 1 \bigoplus 0 \bigoplus 0 = 0$
$P_2 = b_1 \bigoplus b_3 \bigoplus b_4 \bigoplus b_6 \bigoplus b_7 = 1 \bigoplus 1 \bigoplus 1 \bigoplus 0 \bigoplus 0 = 1$
$P_3 = b_2 \bigoplus b_3 \bigoplus b_4 = 0 \bigoplus 1 \bigoplus 1 = 0$
$P_4 = b_5 \bigoplus b_6 \bigoplus b_7 = 0 \bigoplus 0 \bigoplus 0 = 0$

因此，得到的海明编码$H = 01100110000$；

（3）设置指错字$G_4G_3G_2G_1$

$G4 = P_4 \bigoplus b_5 \bigoplus b_6 \bigoplus b_7$
$G3 = P_3 \bigoplus b_2 \bigoplus b_3 \bigoplus b_4$
$G2 = P_2 \bigoplus b_1 \bigoplus b_3 \bigoplus b_4 \bigoplus b_6 \bigoplus b_7$
$G1 = P_1 \bigoplus b_1 \bigoplus b_2 \bigoplus b_4 \bigoplus b_5 \bigoplus b_6$

如果$G_4G_3G_2G_1$为$0$则表示无错误，反之指出出错的海明码位号

（4）海明编码的检错和纠错举例：

1、接着上面的例子，当传输无错时，接受方收到的编码就为 $01100110000$；

则：

$G4 = P_4 \bigoplus b_5 \bigoplus b_6 \bigoplus b_7 = 0 \bigoplus 0 \bigoplus 0 \bigoplus 0 = 0$
$G3 = P_3 \bigoplus b_2 \bigoplus b_3 \bigoplus b_4 = 0 \bigoplus 0 \bigoplus 1 \bigoplus 1 = 0$
$G2 = P_2 \bigoplus b_1 \bigoplus b_3 \bigoplus b_4 \bigoplus b_6 \bigoplus b_7 = 1 \bigoplus 1 \bigoplus 1 \bigoplus 1 \bigoplus 0 \bigoplus 0 = 0$
$G1 = P_1 \bigoplus b_1 \bigoplus b_2 \bigoplus b_4 \bigoplus b_5 \bigoplus b_6 = 0 \bigoplus 1 \bigoplus 0 \bigoplus 1 \bigoplus 0 \bigoplus 0 = 0$

$G_4G_3G_2G_1 = 0 0 0 0$ , 表明接收无错；

2、假设传输出错，收到的编码为$ 01100110001$；

则：

$G4 = P_4 \bigoplus b_5 \bigoplus b_6 \bigoplus b_7 = 0 \bigoplus 0 \bigoplus 0 \bigoplus 1 = 1$
$G3 = P_3 \bigoplus b_2 \bigoplus b_3 \bigoplus b_4 = 0 \bigoplus 0 \bigoplus 1 \bigoplus 1 = 0$
$G2 = P_2 \bigoplus b_1 \bigoplus b_3 \bigoplus b_4 \bigoplus b_6 \bigoplus b_7 = 1 \bigoplus 1 \bigoplus 1 \bigoplus 1 \bigoplus 0 \bigoplus 1 = 1$
$G1 = P_1 \bigoplus b_1 \bigoplus b_2 \bigoplus b_4 \bigoplus b_5 \bigoplus b_6 = 0 \bigoplus 1 \bigoplus 0 \bigoplus 1 \bigoplus 0 \bigoplus 1 = 1$

$G_4G_3G_2G_1 = 1 0 1 1$ , 表明第十一位数接收出错；

当只有一位出错时，指错字能够定位错误，故可配备适当电路和异或门来修正出错位；

（5）特点：

• 指错字$G_4G_3G_2G_1$ 为 $0000$时不一定无错

例如：$P1、b1、P2$三位同时出错，则$G_4G_3G_2G_1$依然为$0000$；

• 对于同一个指错字的值（非$0$），无法分辨是出现了一位错误还是出现了两位错误；

例如：仅$b3$出错或者$b1、b2$同时出错时，指错字$G_4G_3G_2G_1$ 均为 $0110$；