海明码详解

海明码是奇偶校验的一种扩充。它采用多位校验码的方式，在这些校验位中的每一位都对不同的信息数据位进行奇偶校验，通过合理地安排每个校验位对原始数据进行校验位组合，可以达到发现错误，纠正错误的目的。

　1.编码步骤

　　(1)根据信息位数，确定校验位数，2的r次方≥k+r+1，其中，k为信息位数，r为校验位数。求出满足不等式的最小r，即为校验位数。

　　(2)计算机校验位公式。

　　表1-3 校验位公式表

…	12	11	10	9	8	7	6	5	4	3	2	1	位数
…	I8	I7	I6	I5		I4	I3	I2		I1			信息位
…					r3				r2		r1	r0	校验位

　　表1-3其实可以当成一个公式来套用，如有已经编码的数据 1100 1001 0111。我们只需把这些数据填充到校验公式，即可得到信息位与校验位。填充的方法是这样的，首先看数据的最低位(即右边第1位)，最低位为1，把1填充在公式表的r0位置，接着取出数据的次低位数据(即右边第2位)，把它填充到r1位置，把右边第3位数填充到I1位置。依此类推，我们可以得到表1-4。

　　表1-4 校验位公式实例表

…	12	11	10	9	8	7	6	5	4	3	2	1	位数
…	1	1	0	0		0	0	1		1			信息位
…					1				0		1	1	校验位

　　表中第2行数据为1100 001 1，这就是数据1100 1001 0111的编码信息，而表格第3行是1 011，这便是较验位。

　　注意：

　　·校验位rn 所在位数为2的n次方位置，其余由信息位填充;

　　·信息位下标从1开始，而校验位下标从0开始。

(3)求校验位(成功与否的关键)

用我自己的话写（带有局限性）：海明码的位号拆分成校验码位号的2的N-1次幂的和 如图2.6 备注说明 然后校验码的值就等于所校验的所有位值的异或值。over 下面是从网上找的详细解答。

在海明码中， 位号数（1、2、3、……、n）为2的权值的那些位，即：

1(20)、2(21)、4(22)、8(23)、…2r-1位，作为奇偶校验位

并记作: P1、P2、P3 、P4、…Pr，余下各位则为有效信息位。

例如： N=11 K=7 r=4 相应海明码可示意为

位号   1  2   3   4   5   6   7   8   9   10   11

P占位 P1 P2 × P3 × × × P4   ×   ×   ×

其中×均为有效信息，海明码中的每一位分别被P1P2P3P4… Pr 中的一至若干位所校验，其规律是：

第i位由校验位位号之和等于i的那些校验位所校验

如：海明码的位号为3，它被P1P2（位号分别为1,2）所校验

海明码的位号为5，它被P1P3（位号分别为1,4）所校验

归并起来: 形成了4个小组，每个小组一个校验位，校验位的取值，仍采用奇偶校验方式确定。

 

海明码每位所占用的校验位（K=7）

海明码位号	占用的校验位号	备注
1	1	1=1
2	2	2=2
3	1，2	3=1+2
4	4	4=4
5	1，4	5=1+4
6	2，4	6=2+4
7	1，2，4	7=1+2+4
8	8	8=8
9	1，8	9=1+8
10	2，8	10=2+8
11	1，2，8	10=1+2+8

             每个校验位所校验的数位（K=7）

校验位位号	被校验位位号
1（P1）	1，3，5，7，9，11
2（P2）	2，3，6，7，10，11
4（P3）	4，5，6，7
8（P4）	6，9，10，11

 (自我认知：感觉就是码位的拆分，拆分成校验码的2的N—1次方幂的和)

其次，校验位rn由信息码对应位数的幂之和形式中包含有n的信息码异或而得，p1的值由I11（信息码为1）、I9（信息码为0）、I7位（信息码为1）、I5位（信息码为0）、I3（信息码为1）对应的信息码异或而得，

(4)求海明码。根据上面的表格填充后，写出海明码。

　　2.纠错步骤

　　(1)根据海明码的信息位和校验位的分布规则，找出接收到的数据的信息位以及校验位。

　　表1-5校验位公式表

…	12	11	10	9	8	7	6	5	4	3	2	1	位数
…	I8	I7	I6	I5		I4	I3	I2		I1			信息位
…					r3				r2		r1	r0	校验位

　　如有已经编码的数据 1100 1001 0111，则可以根据上表得到编码的信息为：1100 001 1;校验位为：1 011，详细过程在“编码步骤”已详细说明。

(2)接收端对校验位进行验证

　　Sn= rn ( 校验)+ rn (接收)

　　(3)判断校正因子是否有错，并改正。

　　Sn Sn-1 Sn-2……S0二进制对应的是那位就是那位出错，将其改正完成纠错。如1001为第九位，将第九位1变0 (或0变1) 即可。

　　例题1

　　若海明码的监督关系式为：

　　S0=a0+a3+a4+a5

　　S1=a1+a4+a5+a6

　　S2=a2+a3+a5+a6

　　接收端收到的码字为：a6a5a4a3a2a1a0=1010100

　　那最多一位错的情况下发送端的发送信息位是什么?

　　解答：按监督关系式

　　S0=0+0+1+0=1

　　S1=0+1+0+1=0

　　S2=1+0+0+1=0

　　得出S2S1S0=001 根据值与错码位置的对应关系所以a0错误，发送端的发送信息应为1010101。