计算机知识回顾:海明码

  发布日期:   2017-06-01
  最新修改:   2020-04-03
  阅读次数:   56 次
  • 海明码,又名汉明码,是在电信领域的一种线性调试码,以发明者理查德·卫斯里·汉明的名字命名。海明码在传输的消息流中插入验证码,当计算机存储或移动数据时,可能会产生数据位错误,以侦测并更正单一比特错误。由于海明编码简单,它们被广泛应用于内存(RAM)。

校验原理:


  • 错误校验码有多种,海明码也利用了奇偶校验位的概念,通过在数据位后面增加一定的比特,可以验证数据的有效性。利用一个以上的校验位,海明码不仅可以验证数据是否有效,还能在数据出错的情况下校验得出错误的明确位置。

    注:奇偶校验概念补充:

    • 偶校验:如果给定的数据1的个数是奇数,那么偶校验位为1,使数据的1保持偶数,否则位0;
    • 奇校验:如果给定的数据1的个数是偶数,那么奇校验位为1,使数据的1保持奇数,否则为0;
    • 奇偶校验的选择都是事先规定的。
    • 优点:开销低,只需要增加1为比特就可以得出数据的正确性,但是不能得出出错的数据位置,即不能矫正,只能丢弃重发,而且数据也有可能两个比特同时出错,此时奇偶校验可能是检测不出来的,但在普通微型计算机中这个概率是微乎其微的。

纠错原理:(来自http://bbs.51cto.com/thread-889899-1.html)写的很好。%E5%86%99%E7%9A%84%E5%BE%88%E5%A5%BD%E3%80%82)


假设要传输的数据是a4a3a2a1,数据位长度为4位,设校验位长度为m,那么应该满足2m-1>=m+4。解出,m=3。这个不等式要解释吗?好吧,我给大家解释下,校验位为m位,那么,校验码可以表示的最大十进制数字为2m-1,去掉一位的原因是全0表示传输的数据没有错误!校验码表示能够纠正的二进制数字位数,为了保证能够纠正数据位最高位。那么2m-1至少应该大于等于数据位和校验位长度的总和!好了,设校验码为r3r2r1。根据海明码规定,校验位应放在数据位的2i-1的位置,整理好后设为M7M6M5M4M3M2M1。 好了,最后的问题,怎么计算校验码呢?它怎么纠错呢?这里我们设海明码的监督关系式为S3S2S1。请大家仔细想一想,S1是不是代表三位二进制校验码的最低位,让我们看看有多少位数字参与了S1的运算,很容易看出M1、M3、M5、M7,所以S1=M1⊕M3⊕M5⊕ M7(为什么是这样呢?这里也给大家说明一下。我们看M的下标,它代表什么呢?明白吗?它代表的是数字在传输数据的第几位。7=4+2+1,5=4+1,3=2+1,1=1。可见,这几位数字均参与了第一位的运算,这样,S1=1就能代表数据位的第一位出错了!),同理,S2=M2⊕M3⊕M6⊕M7,S3=M4⊕M5⊕M6⊕M7。我们再来看这三个监督关系式上面我们说到,要想数据位没有错误,S3S2S1=000,通过这可以计算出r3r2r1,因为S1=0,根据异或运算,将M3⊕M5⊕M7看作一个整体,M1=M3⊕M5⊕M7,r1=M1。同理可以计算出r2r1。那么纠错到底是怎么实现的呢?请大家睁大眼睛仔细看上面三个监督表达式。正常情况下,S3S2S1均为0,我们假设M3出现了错误,发生了跳变,那么S2S1将变成什么呢?如果你不知道的话请往回去看看我说的关于异或运算的知识。由上面的监督关系式发现M3参与了S2S1的运算,所以在M3发生跳变的情况下S2S1也将发生跳变,由0变为1,但由于S3未参与M3的运算,其值不变,仍为0。所以监督关系式S3S2S1=011=3,所以在传输数据的第三位出现了错误。同理,可发现M6参与了S3S2的运算,当运算出错时,监督关系式为110=6,也刚好可以判断出是传输数据的第六位出错了。其它的数据位我就不一一举例了

小结:


N=K+r≤2^r-1

  • N:包含校验码的数据总位数;
  • K:数据位数;
  • r:校验码位数;

   转载规则

《计算机知识回顾:海明码字》GajAngels 采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可。