汉明码校验-纠错

汉明码 : 是一个可以有多个校验位，具有检测并纠正一位错误代码的纠错码
采用汉明码纠错，需要按以下步骤来进行：计算校验位数→确定校验码位置→确定校验码→实现校验和纠错

计算校验位数

获得 校验位数公式： K+r <= 2^r - 1

其中：K 代表收到的有效信息位数，r 表示需要添加的校验码位数。
比如：收到的信息码为 10011101，则 K = 8。

根据上面的公式，求得需要添加的校验码位数为：r = 4

确定校验码位置

知道了校验码的位数，那么它们该放到信息码的哪些位置呢？

校验码必须是放在 2的 n 次方位置，如第1、2、4、8、16、32，……位（对应2⁰、2¹、2²、2³、2⁴、2⁵，……，是从最左边的位数起的）

我们以 P_n 表示第 n 个校验码，假如我们收到的信息码是 10011101，把校验码按照上面的位置插入其中，则生成了新的信息码：P₁P₂1P₃001P₄1101

确定校验码

首先，我们要知道，校验位的值代表了代码字中部分数据位的奇偶性（最终要根据是采用奇校验，还是偶校验来确定），其所在位置决定了要校验的比特位序列。

每一个校验位 ，要校验的 比特位序列计算规则如下：

P_n（第 n 个校验位，也是整个信息码字的第n位）的校验规则是：从当前位数起，校验 2^n-1 位，然后跳过 2^n-1 位，再校验 2^n-1 位，再跳过 2^n-1 位，……

比如 P₁，就是从第1位起，也就是从 P₁ 起，校验 1 位，然后跳过 1 位，再校验 1 位，......
那么 P₁ 要校验的码字为：P₁10110

P₂，就是从第2位起，也就是从 P₂ 起，校验 2 位，然后跳过 2 位，再校验 2 位，......
那么 P₂ 要校验的码字为：P₂10110

类推出 P₃ 要校验的码字为：P₃0011
P₄ 要校验的码字为：P₄1101

根据上面获得比特位序列得知， P₁ 校验码校验的位数是6位。这6位中除了第1位（也就是 P₁ 位）不能确定外，其余5位的值都是已知的，分别为：1、0、1、1、0。现假设采用的是偶校验（也就是要求整个被校验的位中的“1”的个数为偶数；如果“1”的个数为奇数，则是奇校验），从已知的5位码值可知，已有3个“1”，所以此时P₁位校验码的值必须为“1”，得出P₁ = 1

依次推算出 P₂ = 1，P₃ = 0，P₄ = 1

最后得出汉明码为：111000111101

实现校验和纠错

根据以上说的汉明码的配偶原则和配奇原则我们来看汉明码的纠错。设接收到的错误汉明码（按配偶原则配置）是111000111111，我们可以根据上述规律来确定出错位。

二进制序号	1	2	3	4	5	6	7	8	9	10	11	12
接收到的汉明码	1	1	1	0	0	0	1	1	1	1	1	1
校验码位置	P1	P2		P3				P4

那么新的检测位是
P₁ = 第1位+第3位+第5位+第7位+第9位+第11位，即P₁ = 1+1+0+1+1+1 = 1
P₂ = 第2位+第3位+第6位+第7位+第10位+第11位，即P₂ = 1+1+0+1+1+1 = 1
P₃ = 第4位+第5位+第6位+第7位+第12位，即P₃ = 0+0+0+1+1 = 0
P₄ = 第8位+第9位+第10位+第11位+第12位，即P₄ = 1+1+1+1+1 = 1

根据 P₄P₃P₂P₁ 构成的二进制是 1011，将 1011 转换成十进制为 11，说明是第 11 位出错，或者根据配偶原则的规律，其“1”的个数必须是偶数也能判断出是第11位，所以第11位应将“1”改为“0”，那么正确的汉明码应为 111000111101。

那么为什么在汉明码纠错过程中，新的检测位
P₄P₃P₂P₁ 的状态即指出了编码中错误的信息位？

汉明码属于分组奇偶校验，P₄P₃P₂P₁ = 0000，说明接收方生成的校验位和收到的校验位相同，否则说明出错。由于分组时校验位只参加 一组 奇偶校验，有效信息参加至少 两组 奇偶校验，如果校验位出错，P₄P₃P₂P₁ 的某一位将为1，刚好对应位号8、4、2、1；如果有效信息出错，将引起 P₄P₃P₂P₁ 中至少两位为1。

故，上面的第 11 位出错时，造成 P₄P₂P₁ 都出错了。