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