汉明校验·简明教程

汉明校验

一、简介

汉明码是由 Richard Hanming 于 1950 年提出的，它具有一位纠错能力。

新增的汉明码校验位数应满足如下关系： $2^{k}\geqslant n+k+1$ ，其中k为校验位位数，n位数据位数。

二、汉明码生成

确定校验位的个数与汉明码位数

使用公式【 $2^{k}\geqslant n+k+1$ 】计算需要的k，其中 k 是检验位的数量，n 是数据位的数量；

举个逆子：原欲发送数据为：0101，此时我们可得n=4，则欲使 $2^k\geq4+k+1$ ，k最小为3，即校验位个数为3；则未来将要生成的汉明码位数为原数据4位+3位校验位共7位。
安置校验位

我们规定：所有的校验位均放置在第 $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_2$	0	$c_3$	1	0	1

其中 $c_1$ ， $c_2$ ， $c_3$ 为待确定值的校验位。

画表计算校验位的值

在这里插入图片描述

我们的原则是，位置代表的二进制写好后，每一行值为一的二进制位分为一组；然后，你会发现，每一行校验位的位置是互斥的，只有一个为1。

基于这样的发现，我们让汉明码那一行的未知数放在等式左边，其他已知的数值位放在等式右边进行异或（两个二进制位异或，相同结果为0，不同为1）运算，即可得到对应的校验位的值，如下计算所示：
$C_1=0\oplus1\oplus1=0\\ C_2=0\oplus0\oplus1=1\\ C_3=1\oplus0\oplus1=0$

书写完整的汉明码

如第四步所计算，结合原来的位置，将校验位的值填充进行，写出完整的汉明码，上例的汉明码为

0 1 0 0 1 0 1

三、汉明码校验

假设我们收到了0110101，已知这是一个传输出错的汉明码

提取校验位

0110101总位数为1，则易推得校验位为3位；再根据校验位的插入规则，我们可得到三位校验码分别在第1，2，4位，则可得校验码为010
校验

我们按照生成校验码时的规则，将原来的分组的各组与其对应的校验码进行异或运算，若为0则表示该位没出错，否则表示出错。

上述汉明码，我们进行如下计算：
$p1=0\oplus1\oplus1\oplus1=1\\ p2=1\oplus1\oplus0\oplus1=1\\ p3=0\oplus1\oplus0\oplus1=0$
欸，汉明码只能纠错1位，那到底是哪一位出错了呢？其实呀，这里并不能只管看出来，但是汉明码的神奇之处就在于，校验后的k位数值的二进制逆序组合转化为十进制表示的数值就是出错的位置。

如上例，计算完得到 $p_1p_2p_3$ =110，我们逆序得到 $p_3p_2p_1$ =011，其十进制表示3，那么就是第三位出错了，瞅瞅是不是😁