海明码的编码和校验方法
海明码（也叫汉明码）具有一位纠错能力。本文以1010110这个二进制数为例解释海明码的编码和校验方法。
编码
确定校验码的位数x
设数据有n位，校验码有x位。则校验码一共有2ˣ种取值方式。其中需要一种取值方式表示数据正确，剩下2ˣ-1种取值方式表示有一位数据出错。因为编码后的二进制串有n+x位，因此x应该满足
$$
2ˣ-1 ≥ n+x
$$
使不等式成立的x的最小值就是校验码的位数。在本例中，n=7，解得x=4。
确定校验码的位置
校验码在二进制串中的位置为2的整数幂。剩下的位置为数据。如图所示。
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 内容 | x1 | x2 | 1 | x3 | 0 | 1 | 0 | x4 | 1 | 1 | 0 |
求出校验位的值
以求x2的值为例。为了直观，将表格中的位置用二进制表示。
| 位置 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 内容 | x1 | x2 | 1 | x3 | 0 | 1 | 0 | x4 | 1 | 1 | 0 |
为了求出x2,要使所有位置的第二位是1的数据（即形如* * 1 *的位置的数据）的异或值为0。即x2^1^1^0^1^0 = 0。因此x2 = 1。
同理可得x1 = 0, x3 = 1, x4 = 0。
| 位置 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 内容 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
因此1010110的海明码为01110100110。
校验
假设位置为1011的数据由0变成了1，校验过程为：
将所有位置形如 * * * 1 , * * 1 * , * 1 * * , 1 * * * 的数据分别异或。
* * * 1 : 0^1^0^0^1^1 = 1
* * 1 * : 1^1^1^0^1^1 = 1
* 1 * * : 1^0^1^0 = 0
1 * * * : 0^1^1^1 = 1
以上四组中，如果一组异或值为1，说明该组中有数据出错了。* * * 1 、* * 1 * 、 1 * * * 的异或都为1，说明出错数据的位置为1011。