海明码详解

2008年10月15日 星期三 09:20 例题1

已知海明码的关系式 S0=a2+a3+a4+a6 S1=a1+a4+a5+a6 S2=a0+a3+a4+a5

请填充下述S2S1S0值与错误位置的对应表

S2S1S0 | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 --------------------------------------------------------- 错码位置 | 无错| | | | | | |

分析：先看001, 对应S2S1S0就是S0=1，即S0出错，而S0=a2+a3+a4+a6，就看S0的四项里哪一项S1和S2里没有，很明显是a2，所以001下面填a2. 看010, S1错，S1=a1+a4+a5+a6，S1里哪一项S0和S2里没有？是a1，所以010下面填a1

看011，S1和S0都错，那S1和S0里都有哪一项呢？a4和a6，但是S2无错，S2里也有a4，没有a6，所以是a6错，011下面填a6 100,101,110同

看111，S2、S1和S0都错，那么哪一项s2,s1和s0里都有呢？a4，所以111下面填a4

例题2

在海明码编码方法中，若冗余位为3位，且与错码位置的对应关系为 S2S1S0 111 110 101 011 100 010 001 000 错码位置 a6 a5 a4 a3 a2 a1 a0 无错 则S1的监督关系式为( )。

A. S1=a1+a3+a5+a6 B. S1=a2+a3+a4+a6 C. S1=a1+a3+a4+a5 D. S1=a1+a2+a5+a6

解析：由题可知，a1,a3,a5或a6中的一位错都应使S1为1，由此可以得到监督关系式为S1=a1+a3+a5+a6

例3.已知海明码的监督关系式为： S2=a2+a3+a4+a6 S1=a1+a4+a5+a6 S0=a0+a3+a4+a5

接收端收到的码字为a6a5a4a3a2a1a0=1010100，问在最多一位错的情况下发送端发送的码字是什么? (1)根据海明码的监督关系式

S2=a2+a3+a4+a6

S1=a1+a4+a5+a6

S0=a0+a3+a4+a5，得下表：

S2S1S0 000 001 010 011 100 101 110 111

错误位置 无错 a0 A1 a5 a2 a3 a6 a4

(2)将a6a5a4a3a2a1a0=1010100分别代入海明码的监督关系式 得：(其中“+”号表示异或运算)； s2=1+0+1+1=1 s1=0+1=0+1=0 s0=0+0+1+0=1 即s2s1s0=101

(3)查表可知：接收到的比特序列第4位有错，正确的应是： a6a5a4a3a2a1a0=1011100

例4.假设k=4，需要纠正一位错误，则 2^r >= n + 1 = k + r + 1 = 4 + r + 1

解得 r >= 3。我们取r=3，则码长为3+4=7。用a6,a5,...a0表示这7个码元。用s1,s2,s3表示三个监关系式中的校正子。我们作如下规定：

s1 s2 s3 错码的位置 0 0 1 a0 0 1 0 a1

1 0 0 a2 0 1 1 a3 1 0 1 a4 1 1 0 a5 1 1 1 a6 0 0 0 无错

按照表中的规定可知，仅当一个错码位置在a2,a4,a5或a6时校正子s1为1，否则s1为0。这就意味着a2,a4,a5,a6四个码元构成偶校验关系： s1 = a6⊕a5⊕a4⊕a2 (1)式 同理，可以得到：

s2 = a6⊕a5⊕a3⊕a1 (2)式 s1 = a6⊕a4⊕a3⊕a0 (3)式

在发送信号时，信息位a6,a5,a4,a3的值取决于输入信号，是随机的。监督为a2,a1,a0应该根据信息位的取值按照监督关系决定，即监督位的取值应该使上述(1)(2)(3)式中的s1,s2,s3为0，这表示初始情况下没有错码。即 a6⊕a5⊕a4⊕a2 = 0 a6⊕a5⊕a3⊕a1 = 0 a6⊕a4⊕a3⊕a0 = 0

由上式进行移项运算，得到： a2 = a6⊕a5⊕a4 a1 = a6⊕a5⊕a3 a0 = a6⊕a4⊕a3

已知信息位后，根据上式即可计算出a2,a1,a0三个监督位的值。

接收端受到每个码组后，先按照(1)~(3)式计算出s1,s2,s3，然后查表可知错码情况。

例如，若接收到的码字为0000011，按照(1)~(3)计算得到： s1 = 0, s2 = 1, s3 = 1

查表可得在a3位有一个错码。

这种编码方法的最小汉明距离为d=3，所以这种编码可以纠正一个错码或者检测两个错码。