汉明校验·简明教程
汉明校验·简明教程
汉明校验·简明教程
一、简介
汉明码是由 Richard Hamming 于 1950 年提出的，它具有 一位 纠错能力。
新增的汉明码校验位数应满足如下关系：
$$
2^{k} \geqslant n+k+1
$$
其中k为校验位位数，n位数据位数。
同时，我要强调的是汉明校验码的生成和校验都都两种原则，希望读者要对概念进行清晰地把握，不可一知半解：
$$
\text{汉明校验}
\begin{cases}
\text{按配偶原则的校验}\
\text{按配奇原则的校验}
\end{cases}
$$
这里直接阐述配偶和配奇的原则会比较抽象，我们放到具体的例子中来看，会更加易懂。
二、汉明码生成
- 确定校验位的个数
使用公式【 $2^{k} \geqslant n+k+1$ 】计算需要的k，其中 k 是检验位的数量，n 是数据位的数量；
举个逆子：原欲发送数据为：0101，此时我们可得n=4，则欲使
$2^k \geq 4+k+1$，k最小为3，即校验位个数为3。
- 安置校验位
我们规定：所有的校验位均放置在第 $2^n$ 位，也就是第1、2、4、8…位置等都是校验位，n从0开始，到k-1结束。
上例中k=3，则校验位的位置为：① $2^0=1$ ；② $2^1=2$ ；③ $2^2 =4$；即3位校验位放在最后要发送数据的第1，第2，第4个位置。
- 填充数据位
在非校验位的其他位置上填写真正的数据，填充后汉明码应如如下形式才对：
c 1 c_1 | c 2 c_2 | 0 | c 3 c_3 | 1 | 0 | 1 |
|---|
其中 $c_1$，$c_2$，$c_3$ 为待确定值的校验位。
- 画表计算校验位的值
我们的原则是，位置代表的二进制写好后， 每一行值为1的二进制位分为一组 ；然后，你会发现， 每一行校验位的位置是互斥的，只有一个校验位值为1 。也就是说，一个校验位会和若干数值位搭配，组成一组。
然后我们可以引出配奇和配偶原则了：
- 配奇原则 ：通过配置校验位 $C_j$，使得该组1的个数为 奇数 个，那么该组的各位进行异或操作必为
1 - 配奇原则 ：通过配置校验位 $C_j$，使得该组1的个数为 偶数 个，那么该组的各位进行异或操作必为
0
基于这样的发现，我们让 同一组各数据位进行异或 （两个二进制位异或，相同结果为0，不同为1）运算，按照 配偶原则 ，可得结果如下计算所示：
$$
\text{配偶原则}
\begin{cases}
C_1 \oplus 0 \oplus 1 \oplus 1 \Longrightarrow C_1=0\
C_2 \oplus 0 \oplus 0 \oplus 1 \Longrightarrow C_2=1\
C_3 \oplus 1 \oplus 0 \oplus 1 \Longrightarrow C_3=0
\end{cases}
$$
我们怎么理解上面的 $C_1 C_2 C_3$ 的取值？
【 $C_1 =0$】，是因为和它一组的数据位为011中有偶数个1，按照 配偶 原则，已经有偶数个1了，那我就不用管了；反之看第二组，【 $C_2 =1$】，这是因为第二组的数据位为001，只有奇数个1，按照配偶原则， $C_2$ 要置1才能保证第二组的1为偶数个。第三组同理。
刚好在这里把配奇的原则也讲一下，上面的 $C_1 C_2C_3$ 如果按照配奇原则会是多少呢？如下（如果你理解了配偶原则，配奇也很简单）：
配奇原则
$$
\begin{cases}
C_1=\overline{0\oplus1\oplus1}\Longrightarrow C_1=1\
C_2=\overline{0\oplus0\oplus1}\Longrightarrow C_2=0\
C_3=\overline{1\oplus0\oplus1}\Longrightarrow C_3=1
\end{cases}
$$可见，配奇的结果和配偶的结果刚好相反，这是因为异或操作的原理使得如果同一组中的数据位有偶数个1那么异或必为0，那么取反得校验位为1，那么组合起来（数据位有偶数个1，校验位有1个1，相加肯定是奇数咯）1的个数就是奇数个咯，完成奇配置。
- 书写完整的汉明码（配偶原则）
如第四步所计算，得到三个校验位的值后，将其值填充到校验位所对应的位置，将校验位的值填充进行，写出完整的汉明码，上例的汉明码为
1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
C 1 C_1 | C 2 C_2 | P 1 P_1 | C 3 C_3 | P 2 P_2 | P 3 P_3 | P 4 P_4 |
0 | 1 | 0 | 0 | 1 | 0 | 1 |
三、汉明码校验
按照配偶原则，假设我们收到了0110101，已知这是一个传输出错的汉明码
按照配偶原则，假设我们收到了1001100，已知这是一个传输出错的汉明码
- 提取小组（配奇原则）
1001100总位数为7，则易推得校验位为3位；再根据分组规则，我们可得到三组数据如下：
- 组1（1357）=1010
- 组2（2367）=0000
- 组3（4567）=1100
- 校验（配偶原则）
我们按照 配偶 原则，将原来的分组的各组各位 异或 运算，若为0则表示该位没出错，否则表示出错。
上述汉明码，我们进行如下计算：
$$
g1=0\oplus1\oplus1\oplus1=1\
g2=1\oplus1\oplus0\oplus1=1\
g3=0\oplus1\oplus0\oplus1=0
$$
欸，汉明码只能纠错1位，那到底是哪一位出错了呢？其实呀，这里并不能只管看出来，但是汉明码的神奇之处就在于，校验后的k位数值的二进制逆序组合转化为十进制表示的数值就是出错的位置。
如上例，计算完得到 $g_1g_2g_3$=110，我们逆序得到011，其十进制表示3，那么就是第三位出错了，瞅瞅是不是😁发的是0100101接收到的是0110101,确实是第3位出错了。
- 校验（配奇原则）
我们按照 配奇 原则，将原来的分组的各组各位 异或后取反 运算，若为0则表示该位没出错，否则表示出错。
上述汉明码，我们进行如下计算：
$$
g1=\overline{1\oplus0\oplus1\oplus0}=1\
g2=\overline{0\oplus0\oplus0\oplus0}=1\
g3=\overline{1\oplus1\oplus0\oplus0}=1
$$
此时得到 $g_1g_2g_3$=111，逆序得到111。111十进制表示7，那么第七位出错了；检查一下呗，发的是1001101接收到的是1001100,确实是第7位出错了。