有关海明码的计算问题详解050205

数据经过传送、存取等环节，就会发生误码——1变成0或0变成1，这就引出如何发现及纠正误码的问题，称为检错与纠错。为了检错与纠错必须在原始数据位的基础上增加几位校验（冗余）位。

一、码距

一个编码系统中任意两个合法编码之间不同的二进制位数叫这两个码字的码距，而整个编码系统中任意两个码字的最小码距就是该编码系统的码距。

如图1所示的一个编码系统，用三位二进制来表示八个不同信息。在这个系统中，两个码字之间不同的位数从1到3不等，但最小值为1，故这个系统的码距为1。如果任何码字中一位或多位出了差错，结果这个码字就不能与其它码字区分。例如，如果传送信息001，而被误收为011，因011仍是表中的合法码字，接收方仍将认为011是正确的信息。

但是，如果用四个二进数字来编8个码字，那么在码字间的最小距离可以增加到2，如图2的表中所示。

信息序号	二进码字
	a2	a1	a0
0	0	0	0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

图 1

信息序号	二进码字
	a3	a2	a1	a0
0	0	0	0	0
1	1	0	0	1
2	1	0	1	0
3	0	0	1	1
4	1	1	0	0
5	0	1	0	1
6	0	1	1	0
7	1	1	1	1

图 2

 

注意，图2的8个码字相互间最少有两位的差异。因此，如果任何码字的一个数位出差错，就成为一个不用的码字，就能检查出来。例如信息是1001，误收为1011，接收方知道发生了一个差错，因为1011表中没有，不是一个码字。然而，差错不能被纠正。因为，正确码字可以是1001，1111，0011或1010。接收方不能确定原来到底是这4个码字中的哪一个。同时， 在这个系统中，偶数个（2位或4位）差错也无法发现。

为了使一个系统能纠正一位差错，码距最小是3。最小距离为3时，或能纠正一位错，或能检测二位错，但不能同时纠正一位错并检测二位错。编码信息纠错和检错能力的提高需要进一步增大编码系统的码距。 图3的表概括了编码系统的码距为1至7时，码的纠错和检错能力。

在海明码系统中有关系：L-1=C+D。其中L为码距，D为可以检测出的错误位数，C为可以纠正的错误位数，并且有D≥C。

码距	码 能 力
	检错  纠错
1 2 3 4 5 6 7	0    0 1    0 2 或 1 2 并 1 2 并 2 3 并 2 3 并 3

图3

码距越大，纠错能力越强，但数据冗余也越大，即编码效率低了。所以，选择码距要取决于特定系统的要求。数字系统的设计者必须考虑信息发生差错的概率和该系统能容许的最小差错率等因素。

二、海明校验

前面指出过要能纠正信息字中的单个错误，编码系统的码距至少为3。实现这种编码系统的方法之一是海明码。王诚所撰的《计算机组成原理》中，使用的海明校验码距为4，以下叙述以此为依据。

海明码是一种多重奇偶检错系统。它将信息用逻辑形式编码，以便能够检错和纠错。用在海明码中的全部传输码字是由原来的信息和附加的奇偶校验位组成的。每一个这种奇偶位被编在传输码字的特定位置上。这个系统对于错误的数位无论是原有信息位中的，还是附加校验位中的都能指示出来。

使用具有k位数据海明码，所需步骤如下：

1、确定最小的校验位数r，将它们分别记成P₁、P₂、…、P_r。

2、选择r校验位的数值（0或1）以满足必要的奇偶条件，k位数据和r个校验位一起编成长为k+r位的新码字。

3、对所接收的信息作所需的r个奇偶检查。

4、如果所有的奇偶检查结果均为正确的，则认为信息无错误。

如果发现有一个或多个错了，则错误的位由这些检查的结果来唯一地确定或者纠正。

推求海明码时的一项基本考虑是确定所需最少的校验位数r。考虑长度为k位的信息，若附加了r个校验位，则所发送的总长度为k+r。在接收器中要进行r个奇偶检查，每个检查结果或是真或是伪。这个奇偶检查的结果可以表示成一个r位的二进制字，它可以确定最多2^r种不同状态。这些状态中必有一个其所有奇偶测试都是真的，它便是判定信息正确的条件。于是剩下的（2^r-1）种状态，可以用来判定误码的位置。于是导出下一关系：

2^r-1≥k+r

如果要求能检测出与自动纠正一位错误，并能检测两位错误，应该符合：

2^r-1≥k+r

三、海明码使用实例

设有4位数据D₄D₃D₂D₁=1011，求海明码。

⑴先求校验位数

    根据2^r-1≥4+r得r=4。

⑵编码阵列

    这是求海明码的关键。从理论上讲，校验位可放在任何位置，但习惯上校验位被安排在0、1、2、4、8、…的位置上。据此，可以方便得到口诀——从右到左、先校（验位）后数（据位）、校验阵列对角置“1”，从而就有：

D₄ D₃  D₂  D₁ P₄  P₃ P₂  P₁

S₄               1        

S₃                  1     

S₂                     1  

S₁                        1

其中S_i为构成译码方程的译码位。 

进而第一行置全“1“，校验阵列其余置“0”，最后一行是去除数字阵列第一行后的校验阵列的列值。

D₄ D₃  D₂  D₁ P₄  P₃ P₂  P₁

S₄   1  1  1  1  1  1  1  1

S₃               0  1  0  0

S₂               0  0  1  0

S₁               0  0  0  1

              0  4  2  1

    将此数字阵列左边的数据阵列根据去除数字阵列第一行后的数据阵列列值应该依次为3、5、6、7填入相应数字。

D₄ D₃  D₂  D₁ P₄  P₃ P₂  P₁

S₄   1  1  1  1  1  1  1  1

S₃   1  1  1  0  0  1  0  0

S₂   1  1  0  1  0  0  1  0

S₁   1  0  1  1  0  0  0  1

  7  6  5  3  0  4  2  1

⑶列出编码方程

    取P_i为“1”的行中的所有为“1”的项进行“异或”，得编码方程。

P₄= D₄⊕D₃⊕D₂⊕D₁⊕P₃⊕P₂⊕P₁

P₃= D₄⊕D₃⊕D₂

P₂= D₄⊕D₃⊕D₁

P₁= D₄⊕D₂⊕D₁

    根据已知数据求出校验位0001。

P₃= D₄⊕D₃⊕D₂=1⊕0⊕1=0

P₂= D₄⊕D₃⊕D₁=1⊕0⊕1=0

P₁= D₄⊕D₂⊕D₁=1⊕1⊕1=1

P₄= D₄⊕D₃⊕D₂⊕D₁⊕P₃⊕P₂⊕P₁=1⊕0⊕1⊕1⊕0⊕0⊕1=0

⑷海明编码

    将数据和校验位组合，即得到海明编码：

                          10110001

⑸译码方程的获得

    译码方程的值是接收方判断接收数据的依据，由⑶得到以下方程。

S₄= D₄⊕D₃⊕D₂⊕D₁⊕P₄⊕P₃⊕P₂⊕P₁

S₃= P₃⊕D₄⊕D₃⊕D₂

S₂= P₂⊕D₄⊕D₃⊕D₁

S₁= P₁⊕D₄⊕D₂⊕D₁

⑹接收正确

    如果接收正确译码方程的值应该全部为0。

S₄= D₄⊕D₃⊕D₂⊕D₁⊕P₄⊕P₃⊕P₂⊕P₁=1⊕0⊕1⊕1⊕0⊕0⊕0⊕1=0

S₃= P₃⊕D₄⊕D₃⊕D₂=0⊕1⊕0⊕1=0

S₂= P₂⊕D₄⊕D₃⊕D₁=0⊕1⊕0⊕1=0

S₁= P₁⊕D₄⊕D₂⊕D₁=1⊕1⊕1⊕1=0

⑺接收错误

如果S₄=0，则有两位出错；S₄=1，一位出错，可以纠正。例如接收到的是10010001。

S₄= D₄⊕D₃⊕D₂⊕D₁⊕P₄⊕P₃⊕P₂⊕P₁=1⊕0⊕0⊕1⊕0⊕0⊕0⊕1=1

S₃= P₃⊕D₄⊕D₃⊕D₂=0⊕1⊕0⊕0=1

S₂= P₂⊕D₄⊕D₃⊕D₁=0⊕1⊕0⊕1=0

S₁= P₁⊕D₄⊕D₂⊕D₁=1⊕1⊕0⊕1=1

显然属于S₄=1，一位出错。根据译码方程的值1101查⑵阵列中的对应列，知道D₂发生错误，纠正为10110001。