概述
海明码详解
海明码是奇偶校验的一种扩充。它采用多位校验码的方式，在这些校验位中的每一位都对不同的信息数据位进行奇偶校验，通过合理地安排每个校验位对原始数据进行校验位组合，可以达到发现错误，纠正错误的目的。
假设数据位有
m
位，如何设定校验位
k
的长度才能满足纠正一位错误的要求呢
?
我们这里做一个简单的推导。
k
位的校验码可以有
2^k
个值。显然，其中一个值表示数据是正确的，而剩下的
2^k –1
个值意味着数据中存在错误，如果能够满足：
2^k–1>=m + k (m + k
为编码后的总长度
)
，在理论上
k
个校验码就可以判断是哪一位
(
包括信息码和校验码
)
出现问题。
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
，这便是校验位。
注意：
n
校验位
rn
所在位数为
2^n
，其余由信息位填充
;
n
信息位下标从
1
开始，而校验位下标从
0
开始。
例如：
I8
对应的第十二位
12=2^3+2^2
，
I7
对应的第十一位
11=2^3+2^1+2^0
，
I6
对应的第十位
10=2^3+2^1
，
I5
对应的第九位
9=2^3+2^0
，一直写到
I1
对应的第三位。
校验位
rn
由前面位数写成
2
的幂之和中包含
2^n
的位数对应的信息位之和构成
例如：
r3=I8
⊕
I7
⊕
I6
⊕
I5
(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)2^r≥4+r+1
，确定校验位为
3
位
2^3≥4+3+1
。
(2)
列出公式表格。
表
1-6
校验位公式表
|
7
|
6
|
5
|
4
|
3
|
2
|
1
|
位数
|
|
I4
|
I3
|
I2
|
|
I1
|
|
|
信息位
|
|
|
|
|
r2
|
|
r1
|
r0
|
校验位
|
7=2^2+2^1+2^0
，
6=2^2+2^1
，
5=2^2+2^0
，
3=2^1+2^0
r2=I4
⊕
I3
⊕
I2
r1= I4
⊕
I3
⊕
I1
r0= I4
⊕
I2
⊕
I1
(3)
根据公式得
r2=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
|
|
I4
|
I3
|
I2
|
|
I1
|
|
|
信息位
|
|
|
|
|
|
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
|
校验位
|
从而得到
信息
位为
11000100
，校验位为
1000
。
因为
12=2^3+2^2 ;11=2^3+2^1+2^0;10=2^3+2^1; 9=2^3+2^0;7=2^2+2^1+2^0; 6=2^2+2^1 ;5 =2^2+2^0;3=2^1+2^0 ;
可得发送端校验位：
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
接收端收到的码字为：
a6 a5 a4 a3 a2 a1 a0=1 0 1 0 1 0 0
那最多一位错的情况下发送端的发送信息位是什么
?
解答：按监督关系式
S0=0
⊕
0
⊕
1
⊕
0=1
S1=0
⊕
1
⊕
0
⊕
1=0
S2=1
⊕
0
⊕
0
⊕
1=0
得出
S2
⊕
S1
⊕
S0=001
根据值与错码位置的对应关系所以
a0
错误，发送端的发送信息应为
1010101
。
最后
以上就是开放人生为你收集整理的海明码详解的全部内容，希望文章能够帮你解决海明码详解所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复