海明码的计算方法
海明码是一种具有纠错功能的校验码.本文简单地介绍海明码的计算方法.
海明码的目的是能够纠正一位误码.假设信息码共有 n 位,海明码共有 h 位,那么总共的码长为 n + h 位.为能检测出 n + h 位编码中其中一位的错误,海明码必须能够表示至少 n + h + 1 种状态,其中 n + h 种表示 n + h 位编码中有一位错误,另外还需要一种来表示整个编码正确无误.则海明码的长度需要满足下列关系：
2 h >= n + h + 1
于是根据这个式子我们可以得出以下的关系表：
h 2 3 4 5 6 7 8
n 1 4 11 12~26 27~57 58~120 121~247
以 4 位信息位为例,由上表可以看出需要的海明码长度为 3.
设信息位为 x4x3x2x1,添加的 3 位海明码为 a3a2a1,信息码和海明码组合之后得到的码为 H7H6H5H4H3H2H1.
错误 无 H1 H2 H3 H4 H5 H6 H7
C1 0 1 0 1 0 1 0 1 C1 = H1 + H3 + H5 + H7 = 0
C2 0 0 1 1 0 0 1 1 C2 = H2 + H3 + H6 + H7 = 0
C3 0 0 0 0 1 1 1 1 C3 = H4 + H5 + H6 + H7 = 0
如上表,在H1～H7中添加的 3 位海明码使得 C1～C3 的值为零.其中C1～C3为校验和.这样当 Hn 传输出错时,有 (C3C2C1)2 = n.
令 H1 = a1,H2 = a2,H4 = a3,则得出
H7H6H5H4H3H2H1 = x4x3x2a3x1a2a1
将上面的关系代入C1～C3的计算公式,得到C1 = H1 + H3 + H5 + H7 = a1 + x1 + x2 + x4 = 0 C2 = H2 + H3 + H6 + H7 = a2 + x1 + x3 + x4 = 0 C3 = H4 + H5 + H6 + H7 = a3 + x2 + x3 + x4 = 0
即a1 + x1 + x2 + x4 = 0 a2 + x1 + x3 + x4 = 0 a3 + x2 + x3 + x4 = 0
即a3 = x4 + x3 + x2a2 = x4 + x3 + x1a1 = x4 + x2 + x1
海明码1.海明码的概念海明码是一种可以纠正一位差错的编码.它是利用在信息位为k位,增加r位冗余位,构成一个n=k+r位的码字,然后用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错.它必需满足以下关系式：2^r>=n+1 或 2^r>=k+r+1海明码的编码效率为：R=k/(k+r)式中 k为信息位位数r为增加冗余位位数 2.海明码的生成与接收方法一：1)海明码的生成.例1.已知：信息码为："0010".海明码的监督关系式为：S2=a2+a4+a5+a6S1=a1+a3+a5+a6S0=a0+a3+a4+a6求：海明码码字.1)由监督关系式知冗余码为a2a1a0.2)冗余码与信息码合成的海明码是："0010a2a1a0".设S2=S1=S0=0,由监督关系式得：a2=a4+a5+a6=1a1=a3+a5+a6=0a0=a3+a4+a6=1因此,海明码码字为："0010101"2)海明码的接收.例2.已知：海明码的监督关系式为：S2=a2+a4+a5+a6S1=a1+a3+a5+a6S0=a0+a3+a4+a6接收码字为："0011101"(n=7)求：发送端的信息码.1)由海明码的监督关系式计算得S2S1S0=011.2)由监督关系式可构造出下面错码位置关系表：S2S1S0000001010100011101110111错码位置无错a0a1a2a3a4a5a63)由S2S1S0=011查表得知错码位置是a3.4)纠错--对码字的a3位取反得正确码字："0 0 1 0 1 0 1"5)把冗余码a2a1a0删除得发送端的信息码："0010"