一个名叫
Richard Hanming老爷爷在1950年提出的检验纠错方法，它具有一位纠错能力。
设欲检测的二进制代码为
n位,K为检测位(提供纠错),总共n+k位代码当中检测位满足的关系: 2 k 2^{k} 2k>=(n+k+1) ===此关系也是求不同代码长度n所需要检测位的位数k
设
k个检验位为Pk,Pk-1...P1,
(1)Pi在海明码的第 2 i − 1 2^{i-1} 2i−1位置,比如
P2, 2 2 − 1 2^{2-1} 22−1则海明码的位置为 H 2 H_{_2} H2(2)注意:海明码的任何一位都是由若干个校验位来校验的
其中的对应关系:
被校验的海明码下标等于所有参与检验该位的检验位下标之和
校验位由自己本身校验
Eg: H 12 H_{12} H12,他的下标为12,对应的是8+4(上面的公式求解,要对应二进制)也就是海明码的第8和第4检验位
实际应用举例:
对于8位的数据位,进行海明码校验需要4个校验位( 2 k 2^k 2k>=n+k+1, 2 4 2^4 24>=8+4+1)
令数据位为: D 7 D_7 D7、 D 6 D_6 D6、 D 5 D_5 D5、 D 4 D_4 D4、 D 3 D_3 D3、 D 2 D_2 D2、 D 1 D_1 D1、 D 0 D_0 D0
校验位为: P 4 P_4 P4、 P 3 P_3 P3、 P 2 P_2 P2、 P 1 P_1 P1、 P 4 P_4 P4
形成的海明码: H 12 H_{12} H12、 H 12 H_{12} H12、 H 11 H_{11} H11、 H 10 H_{10} H10… H 1 H_{1} H1
D与P在海明码中的位置| H 12 H_{12} H12 | H 11 H_{11} H11 | H 10 H_{10} H10 | H 9 H_{9} H9 | H 8 H_{8} H8 | H 7 H_{7} H7 | H 6 H_{6} H6 | H 5 H_{5} H5 | H 4 H_{4} H4 | H 3 H_{3} H3 | H 2 H_{2} H2 | H 1 H_{1} H1 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| D 7 D_7 D7 | D 6 D_6 D6 | D 5 D_5 D5 | D 4 D_4 D4 | P 4 P_{4} P4 | D 3 D_{3} D3 | D 2 D_{2} D2 | D 1 D_{1} D1 | P 3 P_{3} P3 | D 0 D_{0} D0 | P 2 P_{2} P2 | P 1 P_{1} P1 |
注意:当中的 H 8 H_{8} H8, H 3 H_{3} H3
第一个
检验位P 1 P_{1} P1是位于 H 1 H_{1} H1的位置,他检验的位置为 H 1 H_{1} H1, H 3 H_{3} H3, H 5 H_{5} H5, H 7 H_{7} H7, H 9 H_{9} H9, H 11 H_{11} H11 就是读一位,隔一位第二个
检验位P 2 P_{2} P2是位于 H 2 H_{2} H2的位置,他检验的位置为 H 2 H_{2} H2, H 3 H_{3} H3, H 6 H_{6} H6, H 7 H_{7} H7, H 10 H_{10} H10, H 11 H_{11} H11 就是读二位,隔2位第三个
检验位P 3 P_{3} P3是位于 H 4 H_{4} H4的位置,他检验的位置为 H 4 H_{4} H4, H 5 H_{5} H5, H 6 H_{6} H6, H 7 H_{7} H7, H 9 H_{9} H9, H 12 H_{12} H12 就是读四位,隔四位第四个
检验位P 4 P_{4} P4是位于 H 8 H_{8} H8的位置,他检验的位置为 H 8 H_{8} H8, H 9 H_{9} H9, H 10 H_{10} H10, H 11 H_{11} H11, H 12 H_{12} H12 就是读8位,隔8位以此类推,
第
n位的校验位的海明位是:从自身开始,读 2 n − 1 2^{n-1} 2n−1位,隔 2 n − 1 2^{n-1} 2n−1位…直到结束
异或运算
一般默认为偶校验,可以
求出每个校验位负责检测的海明位—采用奇校验,将各校验位的偶校验值取反即可$$
&P1=D0⊕D1⊕D3⊕D4⊕D6 \
&P2=D0⊕D2⊕D3⊕D5⊕D6 \
&P3=D1⊕D2⊕D3⊕D7 \
&P4=D4⊕D5⊕D6⊕D7 \$$
对使用海明码的数据进行校验差错检测很简单，
根据上面的方法，我们可以很轻易得知每个校验位负责检测的海明位，
只要对其进行异或运算即可。
$$
&G4=P4⊕D4⊕D5⊕D6⊕D7\
&G3=P3=D1⊕D2⊕D3⊕D7 \
&G2=D2⊕D2⊕D3⊕D5⊕D6 \
&G1=D1⊕D1⊕D3⊕D4⊕D6 \end
$$
1.正常情况:
若采用偶校验，则
G4G3G2G1全为0是表示数据没有错误， 奇校验应全为1，否则即出现了错误。
2.错误情况
当发生错误时，将
G4G3G2G1的值转化为十进制即可知道发生错误的位置 如
G4G3G2G1=0110，即表示H6这个位置的数据发生了错误，只要将其取反即可纠正。
参考链接：海明码（汉明码）详解
