海明码

组成

海明码具有一位纠错能力，通过插入多位冗余码来进行错误检测和纠正。

假设数据码原码有$k$位，那么，假设需要$r$位冗余码来纠错，那么新的码总共有$n = k + r$位。想要能做到纠正和错误检测，那么冗余码就要覆盖所有出错的情况，共有$2^n$种，加上完全正确的$1$种，即：

$$2^r \ge n + 1 = k + r +1$$

将数据从$1$开始编号，第$2^i$为校验位，其他位为数据位。

计算

第$i$位校验位$C_i$负责位置编号二进制第$\log i+1$低位为$1$的数据位，例如：

• $C_1$负责$1,3,5,7$……位（倒数第一位为$1$）
• $C_2$负责$2,3,6,7$……位（倒数第二位为$1$）
• $C_4$负责$4,5,6,7$……位（倒数第三位为$1$）

计算校验位主要有配奇原则和配偶原则，就是要让这一校验位所负责的位数（包括校验位自己）里面，$1$的数量分别是奇数或偶数。

配偶原则：

$$C_i = D_1 \oplus D_2 \oplus ... \oplus D_m$$

配奇原则：

$$C_i = \overline {D_1 \oplus D_2 \oplus ... \oplus D_m}=1\oplus D_1 \oplus D_2 \oplus ... \oplus D_m$$

纠错

重新计算每一位校验位：

配偶原则：

$$P_i=C_i \oplus D_1 \oplus D_2 \oplus ... \oplus D_m$$

配奇原则：

$$P_i=\overline{C_i \oplus D_1 \oplus D_2 \oplus ... \oplus D_m}=1 \oplus C_i \oplus D_1 \oplus D_2 \oplus ... \oplus D_m$$

对于配奇或者配偶原则，得到的$P_i$都应该是$0$，如果不是，那么就说明有错，错误的位置是：

$$...P_4 P_2 P_1$$

将这一位取反就是正确的值。