Yi's Blog

《程序员教程(第三版)》学习笔记——03.海明码

2012-07-24

海明码是利用奇偶性来检错和纠错的校验方法。在数据位之间插入r个校验位,通过扩大码距来实现检错和纠错。

海明校验

  1. 确定校验位的个数

设: N为待发送海明码的总位数,K是有效信息位数,r是校验位个数(分成r组作奇偶校验,能产生r位检错信息)
校验位的个数 r 应满足公式N=K+r ≤ 2^r-1

  1. 确定数据位与校验位在海明码中的位置。

在海明码中,校验位的位号为2^i,即1、2、4、8、16……其余部分用数据位填充。

  1. 通过校验关系,确定各校验位的值。

数据位的校验码确定:位号为i的校验码,是位号之和等i的数据位的校验位,如下表。

海明码每位所占用的校验位
海明码每位所占用的校验位

每个校验位所校验的数位
每个校验位所校验的数位

例如,对于7位的数据位,进行海明校验需要4个校验位。令数据位为D0、D1、D2……D6 。校验位为P1、P2、P3、P4 。形成的海明码为H1、H2、H3……H11 。

如下图:
海明码校验

P1偶校验:P1、D0、D1、D3、D4、D6
即P1=D0 xor D1 xor D3 xor D4 xor D6
P2偶校验:P2、D0、D2、D3、D5、D6
即P2=D0 xor D2 xor D3 xor D5 xor D6
P3偶校验:P3、D1、D2、D3
即P3=D1 xor D2 xor D3
P4偶校验:P4、D4、D5、D6
即P4=D4 xor D5 xor D6

若采用奇校验,则将各位校验位的偶校验值取反即可。

  1. 检验错误。做以下计算:
    G1=P1 xor D0 xor D1 xor D3 xor D4 xor D6
    G2=P2 xor D0 xor D2 xor D3 xor D5 xor D6
    G3=P3 xor D1 xor D2 xor D3
    G4=P4 xor D4 xor D5 xor D6

若采用偶校验,G4G3G2G1全为0时表示接收到的数据无错误(奇校验则应全为1)。当G4G3G2G1不全为0时说明发生了差错,而且G4G3G2G1的十进制值指出发生错误的位置。例如G4G3G2G1=1010,则说明H10(D5)出错了,取反即可纠正。