广东商学院分数线-春节回家

海明码（又称汉明码）：海明码是在信息字段中插若干位数据，用于监督码字里的哪一位数
据发生了变化，具有一位纠错能力。假设信息位有k位，整个码字的长度就是k+r；每一位
的数据只 有两种状态，不是1就是0，有r位数据就应该能表示出
2
种状态，如果每一种状
态代 表一个码元发生了错误，有k+r位码元，就要有k+r种状态来表示，另外还要有一种状
态来表示数据 正确的情况，所以
21kr
才能检查一位错误，即
2kr1
。例 如，
信息数据有4位，由
2kr1
得r>=3，也就是至少需要3位监督数据才 能发现并改正1
位错误。比如：给8个学员进行编号，可以用三位数来编码：学号为000 、001 „„、111；
也可以用五位数来编号：学号为00000 、00001 、00010 、„„、0 0111，但是没有必要用
五位呀，只要能满足编码的要求就可以了，所以我们只需要求出满足条件的最 小的k值即可。
海明码求解具体步骤：
① 确定校验码的位数k
② 确定校验码的位置
③ 确定数据的位置
④ 求出校验位的值
下面开始实战练习。假设我们要推导D= 101101这串二进制的海明码，按照步骤一步步
来：
① 确定校验码的位数k
数据的位数k=6，按照上面说的公式来计算满足条件r的最小值，如下公式：

21kr

即：
27r

解此不等式得：满足不等式的最小r=4，也就是D=10 1101的海明码应该有6+4=10位，
其中原数据6位，校验码4位。
② 确定校验码的位置
不妨设设这4为校验码分别为
P
1
、
P
2
、
P
3
、
P
4
；数据从左到右为
D
1
、
D
2
、„„、
D
6
。
编码后的数据共有6+4=10位，设为
M
1
、
M
2
、„„
M
10
。
校验码
P
i
（i取1,2,3,4）在 编码中的位置为
2
i1
r
rr
r
r
r
， 如下表所示：

M
1

甲
P
1



M
2

P
2

M
3


M
4

P
3

M
5


M
6


M
7


M
8

P
4

M
9


M
10





③ 确定数据的位置
这个很简单，除了校验码的位置 其余的就是数据的位置，填充进去就可以了，于是可以
把数据信息先填进去，见“乙”行，下面就是最关 键的部分，求出校验位的值啦！！！

M
1

甲
P
1


乙

④ 求出校位的值
M
2

P
2


M
3

D
1

1
M
4

P
3


M
5

D
2

0
M
6

D
3

1
M
7

D
4

1
M
8

P
4


M
9

D
5

0
M
10

D
6

1



这个公式不是难，99%左右的考生都能看懂海明码的求解过程，但是真正能够过目不忘的相信就是极少数了，很多考生在论坛抱怨躺在床上眼睛一闭，一睁，就忘记了一半。眼睛

< br>再一闭，一睁，基本上就等于没有看了。与其这样，倒不如考前几天突击一下。其实完全没
有必要 死记硬背，该公式是有规律可循的，基本没有任何一本教材讲过，笔者也是无意中在
一篇论文中看见，所 以与大家分享。
假设出错位为
e
1
、e
2
、e
3
、e
4
，现在我们需要做的就是将
M
1
、
M
2
、„„
M
10
和
e
1
、e
2

、
e
3
、e
4
的关系对应出来，只要这个关系出来了，所有 的问题都解决了。演示几个，剩下
的考生自己推导（看了肯定会）。
M
1
下标 中的1可以表示成0001，这里的0001分别对应
，由于
e
1
的值为1， 所以
M
1
只和
e
1
有关。
M
3
下 标中的3可以
e
4
、e
3
、e
2
、e
1< br>（倒过来看）
表示成0011，所以
M
3
和
e
1、e
2
有关；
M
7
下标中的7可以表示成0111，所以
M
7
和
e
1
、e
2
、
e
3有关；其他以此类推，只需要将这些有关的用异或符号

连接起来即可，最后可得如下公式：

e
1
M
1
M
3
M
5
M
7
M
9


e
2
M
2
M
3
M
6
M
7
M
10


e
3
M
4
M5
M
6
M
7


e
4
M
8
M
9
M
10

然后将第③步求出那张表中的数据对应过来，即

e
1
P
1
D
1
D
2
D
4
D
5< br>

e
2
P
2
D
1
D
3
D
4
D
6


e
3
P
4
D
2
D
3
D
4


e
4
P
8
D
5
D
6

如果海明码没有错误信息，
e
1
、e
2
、e
3
、e
4
都为0，等式右边的值也得为0，由于是异
或，所以
P< br>i
（i取1,2,3„）的值跟后边的式子必须一样才能使整个式子的值为零，故：

P
1
D
1
D
2
D
4
D< br>5


P
2
D
1
D
3< br>D
4
D
6


P
3
D
2
D
3
D
4


P
4
D
5
D
6

下面只需要将值代入计算即可，

P
1
D
1D
2
D
4
D
5
= 1

0

1

0 = 0

P
2
D
1
D
3
D
4
D
6
= 1

1

1

1 = 0

P
3
D
2
D
3
D
4
= 0

1

1 = 0

P
4
D
5
D
6
= 0

1 = 1
大功告成，把
P
i
的值填写到第③步求出的那张表中，看“丙” 行，就可以得到海明码。

M
1

甲
P
1


乙 0

M
2

P
2

0
M
3

D
1

1
M
4

P
3

0
M
5

D
2

0
M
6

D
3

1
M
7

D
4

1
M
8

P
4

1
M
9

D
5

0
M
10

D
6

1



即最后的海明码为：；
但是考研知识点还没有完，知道了怎么编写海明码，当然需要知道怎么校验，如下：
现在假设 第五位出错了，也就是第五位在传输的过程中被改为”1“了。即得到的数据
为。现在要找出错误的位置 （假设现在不知道出错的位置）。
继续使用：

e
1
M
1
M
3
M
5
M
7
 M
9
= 0

1

1

1

0 = 1

e
2
M
2
 M
3
M
6
M
7
M
10
=0

1

1

1

1 = 0

e
3
M
4
M
5
M6
M
7
=0

1

1

1 = 1
e
4
M
8
M
9
M
10
= 1

0

1 = 0
按照
e
4
、e
3
、e
2
、e
1
的排序方式得到的二进制序列为：01 01，恰好对应十进制5，是不
是找到了出错的位置？那赶快把第五位取反吧。
让我们再来总结一下吧：
编写海明码的过程：
① 确定校验位的位数
② 把数值为按序写出来，
M
1
,.....
校验码
P
i
（i取1,2,3,4）在编码中的位置为
2
M
N
，
将校验码的位 置写出来，然后按序写出数据位
③ 求出出错位
e
1
,.....e
m
与
M
1
,.....M
N
的对应关系，然后就可以写出
P
i
与数据位的对应
关系，进而求出
P
i

④ 最后将
P
i
填入数据位，海明码就形成了
校验海明码的过程：
① 直接上来写出出错位
e
1
,.....e
m
与
M
1
,.....M
N
的对应关系，计算出
e
1
, .....e
m
的值
② 求出二进制序列
e
m
,.... .e
1
对应十进制的值，则此十进制数就是出错的位数，取反即
可得到正确的编码。
补充两个概念：
（1）海明码如果要检测d位错误，需要一个海明距为d+1的编码方 案；如果要纠出d
位错误，需要一个海明距为2d+1的编码方案，记住即可；
（2）海明码的纠错能力恒小于等于检错能力。
以上为海明码全部考研知识点。

i1
，