海明码

1.什么是海明码:

一个名叫Richard Hanming老爷爷在1950年提出的检验纠错方法，它具有一位纠错能力。

2.海明码的计算方法:

设欲检测的二进制代码为n位,K为检测位(提供纠错),总共n+k位代码

当中检测位满足的关系: $2^{k}$ >=(n+k+1) ===此关系也是求不同代码长度n所需要检测位的位数k

1.海明码的编码规则

设k个检验位为Pk,Pk-1...P1,

n个数据位为Dn-1,Dn-2,....D1,D0对应的海明码为Hn+k,Hn+k+1,....H1

那么检验位与海明码的位置对应关系:

(1)Pi在海明码的第 $2^{i-1}$ 位置,比如P2, $2^{2-1}$ 则海明码的位置为 $H_{_2}$

(2)注意:海明码的任何一位都是由若干个校验位来校验的

其中的对应关系:

被校验的海明码下标等于所有参与检验该位的检验位下标之和

校验位由自己本身校验

Eg: $H_{12}$ ,他的下标为12,对应的是8+4(上面的公式求解,要对应二进制)也就是海明码的第8和第4检验位

实际应用举例:

对于8位的数据位,进行海明码校验需要4个校验位( $2^k$ >=n+k+1, $2^4$ >=8+4+1)

令数据位为: $D_7$ 、 $D_6$ 、 $D_5$ 、 $D_4$ 、 $D_3$ 、 $D_2$ 、 $D_1$ 、 $D_0$

校验位为: $P_4$ 、 $P_3$ 、 $P_2$ 、 $P_1$ 、 $P_4$

形成的海明码: $H_{12}$ 、 $H_{12}$ 、 $H_{11}$ 、 $H_{10}$ … $H_{1}$

具体过程:

(1)确定`D`与`P`在海明码中的位置

$H_{12}$	$H_{11}$	$H_{10}$	$H_{9}$	$H_{8}$	$H_{7}$	$H_{6}$	$H_{5}$	$H_{4}$	$H_{3}$	$H_{2}$	$H_{1}$
$D_7$	$D_6$	$D_5$	$D_4$	$P_{4}$	$D_{3}$	$D_{2}$	$D_{1}$	$P_{3}$	$D_{0}$	$P_{2}$	$P_{1}$

注意:当中的 $H_{8}$ , $H_{3}$

(2)计算检验位

第一个检验位 $P_{1}$ 是位于 $H_{1}$ 的位置,他检验的位置为 $H_{1}$ , $H_{3}$ , $H_{5}$ , $H_{7}$ , $H_{9}$ , $H_{11}$ 就是读一位,隔一位

第二个检验位 $P_{2}$ 是位于 $H_{2}$ 的位置,他检验的位置为 $H_{2}$ , $H_{3}$ , $H_{6}$ , $H_{7}$ , $H_{10}$ , $H_{11}$ 就是读二位,隔2位

第三个检验位 $P_{3}$ 是位于 $H_{4}$ 的位置,他检验的位置为 $H_{4}$ , $H_{5}$ , $H_{6}$ , $H_{7}$ , $H_{9}$ , $H_{12}$ 就是读四位,隔四位

第四个检验位 $P_{4}$ 是位于 $H_{8}$ 的位置,他检验的位置为 $H_{8}$ , $H_{9}$ , $H_{10}$ , $H_{11}$ , $H_{12}$ 就是读8位,隔8位

以此类推,

第n位的校验位的海明位是:从自身开始,读 $2^{n-1}$ 位,隔 $2^{n-1}$ 位…直到结束

(3)对校验位对应的数据进行`异或运算`

一般默认为偶校验,可以求出每个校验位负责检测的海明位—采用奇校验,将各校验位的偶校验值取反即可

$$
&P1=D0⊕D1⊕D3⊕D4⊕D6 \
&P2=D0⊕D2⊕D3⊕D5⊕D6 \
&P3=D1⊕D2⊕D3⊕D7 \
&P4=D4⊕D5⊕D6⊕D7 \

$$

(4)校验错误

对使用海明码的数据进行校验差错检测很简单，根据上面的方法，我们可以很轻易得知每个校验位负责检测的海明位，只要对其进行异或运算即可。

$$

&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
$$

(5)判定

1.正常情况:

若采用偶校验，则G4G3G2G1全为0是表示数据没有错误，

奇校验应全为1，否则即出现了错误。

2.错误情况

当发生错误时，将G4G3G2G1的值转化为十进制即可知道发生错误的位置

如G4G3G2G1=0110，即表示H6这个位置的数据发生了错误，只要将其取反即可纠正。