分类：
2010-04-09 13:53:09
假设数据位有m位，如何设定校验位k的长度才能满足纠正一位错误的要求呢?我们这里做一个简单的推导。
k位的校验码可以有 个值。显然，其中一个值表示数据是正确的，而剩下的 –1个值意味着数据中存在错误，如果能够满足： –1>m + k (m + k为编码后的总长度)，在理论上k个校验码就可以判断是哪一位(包括信息码和校验码)出现问题。
1.编码步骤
(1)根据信息位数，确定校验位数，2r≥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 所在位数为2n，其余由信息位填充;
·信息位下标从1开始，而校验位下标从0开始。
例如：I8 对应的第十二位12=23+22，I7，对应的第十一位11=23+21+20，I6 对应的第十位10=23+21，I5 对应的第九位9=23+20，一直写到I1对应的第三位。
校验位rn 由前面位数写成2的幂之和中包含2n 的位数对应的信息位之和构成
例如： r3=I8 I7 I6 I5
注意：其中“ ”是异或运算，在异或运算中：
0 1=1;
1 0=1;
0 0=0;
1 1=0;
(3)求校验位。根据上面我们所说的计算公式可以求出校验位。
(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
求信息1011的海明码。
解答：
我们可以按照上面所说的编码步骤进行解题：
(1)2r≥4+r+1，确定校验们为3位23≥4+3+1。
(2)列出公式表格。
表1-6校验位公式表
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 位数 |
| I4 | I3 | I2 | I1 | 信息位 | |||
| r2 | r1 | r0 | 校验位 |
7=22+21+20，6=22+21，5=22+20，3=21+20
r2=I4+ I3+ I2
r1= I4+ I3+ I1
r0= I4+ I2+ I1
(3)根据公式得r 2 =0，r1 =0，r0=1
(4)加入表格。
表1-7 对表1-6填充数据后的表格
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 位数 |
| 1 | 0 | 1 | 1 | 信息位 | |||
| 0 | 0 | 1 | 校验位 |
则海明码为1010101
例题2
信息位8位的海明码，在接收到报文110010100000，判断传输是否出错，并求出发送端发送的信息位。
解答：
2r≥8+r+1，确定校验位为4位24≥4+4+1。
表1-8校验位公式表
| 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 位数 |
| I8 | I7 | I6 | I5 | I | I | I | I | 信息位 | ||||
| r3 | r2 | r1 | r0 | 校验位 |
按照上面的海明码信息位和校验位的分布情况表，对接收数据进行分解：
表1-9 对表1-8填充数据后的表格
| 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 位数 |
| 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 信息位 | ||||
| 1 | 0 | 0 | 0 | 校验位 |
因为12=23+22 ;11=23+21; 9=23+20;7=22+21+20; 6=22+21 ;5 =22+20;3=21+20 ;
可得发送端校验位：
r3= I8+ I7+ I6+ I5;
r2= I8+ I4+ I3+ I2;
r1= I7+ I6+ I4+ I3 + I1;
r0= I7+ I5+ I4+ I2+ I1。
接收端可根据以下关系验证是否出错
S3= r3+ I8+ I7+ I6 + I5;
S2= r2+ I8+ I4 + I3 + I2;
S1= r1+ I7+ I6 + I4 + I3+ I1;
S0= r0+ I7+ I5 + I4 + I2+ I1;
注意：其中的rn为接收端校验位。
由上面的算式得S3 S2 S1 S0=1001，从而得知第九位出错，所以信息位为11010100。此外，若S3 S2 S1 S0全为0，则证明传输正确。
例题3
若海明码的监督关系式为：
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。
