海明码

1.海明码的概念

　　海明码是一种可以纠正一位差错的编码。它是利用在信息位为k位，增加r位冗余位，构成一个n=k+r位的码字，然后用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错。它必需满足以下关系式：
　　　　　　　　　２^r>=n+1  或  2^r>=k+r+1
　　海明码的编码效率为：
　　　　　　　　　　　　R=k/(k+r)
　　式中 k为信息位位数
　　　　 r为增加冗余位位数

　2.海明码的生成与接收

　方法一：（按教科书）

　1)海明码的生成。

　例1.已知：信息码为："0010"。海明码的监督关系式为：
　　　　　　　　S₂=a₂+a₄+a₅+a₆
　　　　　　　　S₁=a₁+a₃+a₅+a₆
　　　　　　　　S₀=a₀+a₃+a₄+a₆
　　　　求：海明码码字。

　　解：1)由监督关系式知冗余码为a₂a₁a₀。
　　　　2)冗余码与信息码合成的海明码是："0010a₂a₁a₀"。
　　　　　设S₂=S₁=S₀=0,由监督关系式得：
　　　　　　　　a₂=a₄+a₅+a₆=1
　　　　　　　　a₁=a₃+a₅+a₆=0
　　　　　　　　a₀=a₃+a₄+a₆=1
　因此，海明码码字为："0010101"
　　　　
　2)海明码的接收。

　例2.已知：海明码的监督关系式为：
　　　　　　　　S₂=a₂+a₄+a₅+a₆
　　　　　　　　S₁=a₁+a₃+a₅+a₆
　　　　　　　　S₀=a₀+a₃+a₄+a₆
　　　　　　接收码字为："0011101"(n=7)

　　　　求：发送端的信息码。

　　解：1)由海明码的监督关系式计算得S₂S₁S₀=011。
　　　　2)由监督关系式可构造出下面错码位置关系表：

　　　　3)由S₂S₁S₀=011查表得知错码位置是a₃。
　　　　4)纠错--对码字的a₃位取反得正确码字："0 0 1 0 1 0 1"
　　　　5)把冗余码a₂a₁a₀删除得发送端的信息码："0010"

　方法二：(不用查表，方便编程)

　1)海明码的生成（顺序生成法）。

　例3.已知：信息码为：" 1 1 0 0 1 1 0 0 "　(k=8)
　　　　求：海明码码字。
　　解：1)把冗余码A、B、C、…，顺序插入信息码中，得海明码
　　　　　　码字:" A B 1 C 1 0 0 D 1 1  0  0 "
　　　　  　码位:　1 2 3 4 5 6 7 8 9 10 11 12  
　　　　　其中A,B,C,D分别插于2^k位(k=0,1,2,3)。码位分别为1,2,4,8。
　　　　2)冗余码A,B,C,D的线性码位是：(相当于监督关系式)
　　　　　　A->1,3,5,7,9,11；
　　　　　　B->2,3,6,7,10,11； 
　　　　　　C->4,5,6,7,12；(注 5=4+1；6=4+2；7=4+2+1；12=8+4)
　　　　　　D->8,9,10,11,12。
　　　　3)把线性码位的值的偶校验作为冗余码的值(设冗余码初值为0)：
　　　　　　A=∑(0,1,1,0,1,0)=1
　　　　　　B=∑(0,1,0,0,1,0)=0
　　　　　　C=∑(0,1,0,0,0)　=1
　　　　　　D=∑(0,1,1,0,0)　=0
　　　　4)海明码为:"1 0 1 1 1 0 0 0 1 1 0 0"

　2)海明码的接收。

　例4.已知：接收的码字为："1 0 0 1 1 0 0 0 1 1 0 0"(k=8)
　　　　求：发送端的信息码。
　　解：1)设错误累加器(err)初值=0
　　　　2)求出冗余码的偶校验和，并按码位累加到err中：
　　　　　　A=∑(1,0,1,0,1,0)=1　err=err+2⁰=1
　　　　　　B=∑(0,0,0,0,1,0)=1　err=err+2¹=3
　　　　　　C=∑(1,1,0,0,0)　=0　err=err+0 =3
　　　　　　D=∑(0,1,1,0,0)　=0　err=err+0 =3
　　　　　由err≠0可知接收码字有错，
　　　　3)码字的错误位置就是错误累加器(err)的值3。
　　　　4)纠错--对码字的第3位值取反得正确码字：
　　　　　　"1 0 1 1 1 0 0 0 1 1 0 0"
　　　　5)把位于2^k位的冗余码删除得信息码："1 1 0 0 1 1 0 0"