计算机网络基础知识之海明码

$2.5.4海明码

海明码是由R.HmIMI1ing在1950年首次提出的,它是一种可以纠正一位差错的编码。

可以借用简单奇偶校验码的生成原理来说明海明码的构造方法。若k(=n-1)位信息位an-1an-2…a1加上一位偶校验位a0,构成一个n位的码字an-1an-2...a1a0,则在接收端校验时,可按关系式

S=an-1+an-2+…+a1+a0

来计算。若求得S=0,则表示元错;若S=1,则有错。上式可称为监督关系式,S称为校.正因子。.在奇偶校验情况下,只有一个监督关系式和一个校正因子,其取值只有0或1两种情.况,分别代表元错和有错两种结果,还不能指出差错所在的位置。不难设想,若增加冗余位,也即相应地增加了监督关系式和校正因子,就能区分更多的情况。如果有两个校正因子.
S1和S0,则S1S0取值就有00、01、10或11四种可能的组合,也即能区分四种不同的情况。若其中一种取值用于表示无错(如00),则另外三种(01、10及11)便可以用来指出.不同情况的差错,从而可以进一步区分出是哪一位错。

设信息位为k位,增加r位冗余位,构成一个n=k+r位的码字。若希望用r个监督关系式产生的r个校正因子来区分元错和在码字中的n个不同位置的一位错,则要求满足以下关系式:
2r>=n+1 或 2r>=k+r+1

以k=4为例来说明,则要满足上述不等式,必须r>=3。假设取r=3,则n=k+r=7,即在4位信息位a6a5a4a3后面加上3位冗余位a2a1a0,构成7位码字a6a5a4a3a2a1a0,其中a2、a1和a0分别由4位信息位中某几位半加得到,在校验时,a2、a1和a0就分别和这些位半.加构成三个不同的监督关系式。在无错时,这三个关系式的值S2、S1和S0全为"0"。若a2错,则S2=1,而S1=S0=0;若a1错,则S1=1,而S2=S0=0;若a0错,则s0=1,而S2=S1=0。S2、S1和S0这三个校正因子的其它4种编码值可用来区分a3、a4、a5、a6中的一位错,其对应关系如表2.1。当然,也可以规定成另外的对应关系,这并不影响讨论的一般性。

表2.1 S2 S1 S0 值与错码位置的对应关系

S2 S1 S0 　　000 　001　010　100 　011 　101 　110 　111
错码位置 　　无错　a0 　a1 　a2 　a3 a4 　　a5 　a6
由表可见,a2、a4、a5或a6的一位错都应使S2=1,由此可以得到监督关系式..
S2=a2+a4+a5+a6....
同理可得:S1=a1+a3+a5+a6..
S0=a0+a3+a4+a6
在发送端编码时,信息位a6、a5、a4和句的值取决于输入信号,它们在具体的应用中有l确定的值。冗余位电、a1和ao的值应根据信息位的取值按监督关系式来确定,使上述三式l中的S2、S1和S0取值为零,即
a2+a4+a5+a6=0
a1+a3+a5+a6=0
a0+a3+a4+a6=0
由此可求得:
a2=a4+a5+a6
a1=a3+a5+a6
a0=a3+a4+a6

　　已知信息位后,按上述三式即可算出各冗余位。对于本例来说,各种信息位算出的冗余位如表2.2所示。

表2.2 由信息位算得海明码冗余位

信息位 　　 冗余位　　　信息位　　　 冗余位
a6a5a4a3　　a2a1a0　　a6a5a4a3　　　a2a1a0
0000　　　　 000　　　　 1000　　　　 111
0001　　　　 011　　　　 1001　　　　 100
0010　　　　 101　　　　 1010　　　　 010
0011　　　　 110　　　　 1011　　　　 001
0100　　　　 110　　　　 1100　　　　 001
0101　　　　 101　　　 　1101　　　　 010
0110　　　 　011　　　　 1110　　　　 100
0111　　　　 000 　　　　1111　　　　 111

在接收端收到每个码字后,按监督关系式算出S2、S1和S0,若它们全为"0",则认为无错;若不全为"0",在一位错的情况下,可查表2.1来判定是哪一位错,从而纠正之。例如码字0010101传输中发生一位错,在接收端收到的为0011101,代入监督关系式可算得S2=0、S1=1和S0=1,由表2.1可查得S2S1S0=011对应于a3错,因而可将0011101纠正为00101010。

上述海明码的编码效率为4/7。若K=7,按2r>=k+r+1可算得r至少为4,此时编码.效率为7/11。可见,信息位位数越多时编码效率就越高