问题 单项选择题

利用海明码(HammingCode)纠正单位错,如果有6位信息位,则需要加入()位冗余位。

A.2

B.3

C.4

D.5

答案

参考答案:C

解析:

[分析]: 按照海明的理论,纠错码的编码就是把所有合法的码字尽量安排在n维超立方体的顶点上,使得任一对码字之间的距离尽可能大。如果任意两个码字之间的海明距离是d,则所有少于等于d-1位的错误都可以检查出来,所有少于d/2位的错误都可以纠正。一个自然的推论是,对某种长度的错误串,要纠正它就要用比仅仅检测它多一倍的冗余位。

如果对于m位的数据,增加k位冗余位,则组成n=m+k位的纠错码。对于2m个有效码字中的每一个,都有n个无效但可以纠错的码字。这些可纠错的码字与有效码字的距离是1,含单个错误位。对于一个有效的消息总共有n+1个可识别的码字。这n+1个码字相对于其他2m-1个有效消息的距离都大于1。这意味着总共有2m(n+1)个有效的或是可纠错的码字。显然这个数应小于等于码字的所有可能的个数,即2n。于是,有

2m(n-1)<2n

因为n=m+k,所以得出

m+k+1<2k

对于给定的数据位m,上式给出了k的下界,即要纠正单个错误,A必须取最小值。据此可以计算如下:

m=6,6+k+1<2k,可取k=4,得到6+4+1=11<24=16

单项选择题
单项选择题 A1/A2型题