设数据码字为10010011,采用海明码进行校验,则必须加入()比特冗余位才能纠正一位错。
A.2
B.3
C.4
D.5
参考答案:C
解析:
[分析]: 海明(Hamming)研究了用冗余数据位来检测和纠正代码差错的理论和方法。按照海明的理论,可以在数据代码上添加若干冗余位组成码字,码字之间的海明距离是一个码字变成另一个码字时必须改变的最小位数。海明用数学分析的方法说明了海明距离的几何意义,n位的码字可以用/2维空间的超立方体的一个顶点来表示,两个码字之间的海明距离就是超立方体的两个对应顶点之间的一条边,而且这是两顶点(从而两个码字)之间的最短距离,出错的位数小于这个距离都可以被判断为就近的码字。这就是海明码纠错的原理,它用码位的增加(因而通信量的增加)来换取正确率的提高。
按照海明的理论,纠错编码就是把所有合法的码字尽量安排在n维超立方体的顶点上,使得任一对码字之间的距离尽可能大。如果任意两个码字之间的海明距离是d,则所有少于等于d-1位的错误都可以检查出来,所有少于d/2位的错误都可以纠正。
如果对于m位的数据,增加k位冗余位,则组成n=m+k位的纠错码。对于2m个有效码字中的每一个,都有n个无效但可以纠错的码字,这些可纠错的码字与有效码字的距离是1,含单个出错位。这样,对于一个有效的消息总共有n+1个可识别的码字。这 n+1个码字相对于其他2m-1个有效消息的距离都大于1。这意味着总共有2m(n+1)个有效的或是可777纠错的码字。显然这个数应小于等于码字的所有可能的个数,即2n。于是,有
2m(n+1)<2n
因为n=m+k,得出
m+k+l<2k
对于给定的数据位阴,上式给出了k的下界,即要纠正单个错误,k必须取的最小值。
在本题中,数据码字为10010011的m=8,由上式计算出的k的最小值应为4。