考研计算机试题

海明校验码
这是由Richard Hamming于1950年提出、目前还被广泛采用的一种很有效的校验方法，是只要增加少数几个校验位，就能检测出二位同时出错、亦能检测出一位出错并能自动恢复该出错位的正确值的有效手段，后者被称为自动纠错。它的实现原理，是在k个数据位之外加上r个校验位，从而形成一个k+r位的新的码字，使新的码字的码距比较均匀地拉大。把数据的每一个二进制位分配在几个不同的偶校验位的组合中，当某一位出错后，就会引起相关的几个校验位的值发生变化，这不但可以发现出错，还能指出是哪一位出错,为进一步自动纠错提供了依据。
假设为k个数据位设置r个校验位，则校验位能表示2r个状态，可用其中的一个状态指出 "没有发生错误"，用其余的2 r -1个状态指出有错误发生在某一位，包括k个数据位和r个校验位，因此校验位的位数应满足如下关系:
2r ≥ k + r + 1 (2.7)
如要能检出与自动校正一位错，并能同时发现两位错，此时校验位的位数r和数据位的位数k应满足下述关系:
2r-1 ≥ k + r (2.8)
按上述不等式，可计算出数据位k与校验位r的对应关系，如表2.2所示。
表2.2
K值 最小的r值
3-4 4
5-10 5
11-25 6
26-56 7
57-119 8
设计海明码编码的关键技术，是合理地把每个数据位分配到r个校验组中，以确保能发现码字中任何一位出错；若要实现纠错，还要求能指出是哪一位出错，对出错位求反则得到该位的正确值。例如，当数据位为3位（用D3 D2 D1表示）时，检验位应为4位（用P4 P3 P2 P1表示）。可通过表2.3表示的关系，完成把每个数据位划分在形成不同校验位的偶校验值的逻辑表达式中。
表2.3 校验位与数据位的对应关系
在P1、P2、P3、P4竖列相应行分别填1，
在该4列的低3横行其它位置分别填0，
在最顶横行的每个尚空位置都分别填1。
若只看低3横行，右4竖列的3个bit的组合值分别为十进制的1