奇偶校验与海明码

数据是由一堆 01 串组成的. 要看这些 01 串在传输过程中有没有出现错误, 最简单的方法就是比较一下接收到的数据和发送的数据是否相同. 但是, 接收数据的人怎么知道发送的 “正确数据” 是多少呢? 所以这就很有意思了.

奇偶校验

数据在传输的过程中, 出错的数据一般来说比较少, 1 位以上出错的概率很低. 数据是 01 串, 如果一位出错, 那么发生错误之后, 1 或者 0 的数量的奇偶性将会改变. 检查数据的奇偶性, 就是 奇偶校验Parity Check 的思想.

水平校验

奇偶校验的原理是, 事先约定好, 信息数据中 1 的个数一定是奇数. 如果这个数据的 1 的个数是偶数, 那就在数据开头加上一个 1. 如果本身就是奇数, 那就在开头加一个 0, 保持奇偶性不变. 偶校验就是在数据前加一个数 (也有可能是后? 无所谓, 估计考试加在哪会事先说, 不然没法做), 使得数据中 1 的个数为偶数. 加的这个数称为 校验位.

垂直校验

把数据分行, 然后垂直做奇偶校验.

数据
  10100101001101101100110010101011

按 8 位分行
  10100101
  00110110
  11001100
  10101011

垂直做奇校验
  00001011

水平垂直校验

再加个水平校验码

数据
  10100101001101101100110010101011

按 8 位分行, 前加上水平校验码
  1 10100101
  1 00110110
  1 11001100
  0 10101011

垂直做奇校验, 前加上水平校验码 (或者垂直也是一样的, 反正都是总和)
  0 00001011

奇偶校验只能检测出 (一位) 数据错误, 不知道哪一位发生错误, 无法纠正错误.

最小码距

两个数据不同的位数叫码距. 一组合法的编码, 两两之间比较, 有 $\binom n m$ 个码距, 其中最小的一个叫最小码距.

纠错原理

直觉告诉我们, 添加更多的校验信息 (校验码的位数), 可以做到检测更多位数的数据错误, 甚至知道哪一位发生错误.

纠错原理说的就是, 最小码距越大, 检错能力和纠错能力就越强. 有一个公式:

$$L - 1 = D + C, D \ge C$$

$L$ 是最小码距, $D$ 是检错位数, $C$ 是纠错位数.

不会证明.

拿个例子感性理解一下, 1100, 1111, 0011, 0000 这组编码的最小码距 $L = 2$. 在传输的过程中, 如果接收到了这样的数据 1110, 那么它肯定发生了错误. 但是不知道是哪一位发生了错误 (有可能是 1111 的第 0 位错了, 也可能是 1100 的第 1 位错了). 同样, 如果接收到了 0010, 也只能知道发生了一位错误, 不能纠正. 通过枚举不难发现, 任何一个数据, 有且仅有某一位出错, 我一定知道, 但是完全无法知道是哪一位. 于是 $D = 1, C = 0$. $D = 2$. $L - 1 = D + C, D \ge C$ 成立.

如果只有 1111 和 0000 这样的编码, 最小码距 $L = 4$. 当接收到了 1110 这样的数据, 不仅能知道发生了一位错误, 还能纠正这一位错误. (当然如果是 0000 高 3 位出错那就无法检验了). 但是两位发生错误, 比如 0011, 只能检测, 并不能够纠正. 所以, $C = 1$. 而发生 3 位错误压根就检测不出来, 故 $D = 2$. $L - 1 = D + C, D \ge C$ 成立.

不懂纠错原理也没关系, 一开始压根就不想写, 看到作业里有一个题才写的.

海明码

海明码是根据纠错原理, 在数据中巧妙地添加若干个校验位 (合起来称为校验码), 使得 $L$ 变大, 从而提高检错和纠错的能力. 校验码应对数据的变化比较敏感, 才能够增大最小码距. (有点文件哈希校验的味道了哈哈.)

为了使编码具有 1 位纠错的能力, 可以这样考虑一下: 首先在原来 $n$ 位数据中加 $k$ 位校验码, 总共 $n + k$ 位的数据, 一共有 $n + k$ 种 1 位出错情况, 加上一种不出错情况, 一共是 $n + k + 1$ 种情况. 这些情况都要能够与校验码做一个映射 (不一定要一一对应, 但情况要映射到唯一的校验码). $k$ 位校验码能够储存的信息是 $2^k$. 所以就有如下关系式:

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

下面说明具体如何做这个映射.

首先校验码第 $k$ 位应该插入数据的 $2^k$ 位置. 例如校验码为 $H_3H_2H_1H_0$, 数据为 $D_4D_3D_2D_1D_0$, 那么合起来传输的数据应该为:

$$\begin{array}{ccccccccc} D_4 & H_3 & D_3 & D_2 & D_1 & H_2 & D_0 & H_1 & H_0 \\ 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \\ \color{yellow}1\color{none}00\color{red}1 & \color{yellow}1\color{none}000 & 0\color{green}1\color{#6495ED}1\color{red}1 & 0\color{green}1\color{#6495ED}1\color{none}0 & 0\color{green}1\color{none}0\color{red}1 & 0\color{green}1\color{none}00 & 00\color{#6495ED}1\color{red}1 & 00\color{#6495ED}1\color{none}0 & 000\color{red}1 \end{array}$$

表中第一行是传输的数据, 第二行是数据的下标, 第三行是下标的二进制表示.

如上图所示, $H_0$ 的下标为 $(0001)_2$, 它负责检测下标形如 $\texttt{xxx}1$ 的数据有没有出现错误. 上表红色标记的地方, 就是它负责校验的数据. 有 $H_0$, $D_0$, $D_1$, $D_3$, $D_4$. 校验的方法采用 偶校验. 即 $H_0$ 的取值要使得表达式 $H_0 \oplus D_0 \oplus D_1 \oplus D_3 \oplus D_4 = 0$ 成立. 换句话说, $H_0 = D_0 \oplus D_1 \oplus D_3 \oplus D_4$. 同理, $H_1$ 负责校验的数据在表中用蓝色标出, $H_2$ 负责校验的数据用绿色标出, $H_3$ 负责的数据用黄色标出.

形式化地,

$$H_k = \bigoplus_{i \wedge k = k, i \ne k} Q_i$$

其中, $Q$ 是插入了校验码的数据.

比如有数据 $D = 01011$, 那么 $Q = 0H_3101H_21H_1H_0$. 根据上述公式 (其实算的时候得手拆二进制, 毕竟人不是计算机), 得 $H_0 = 1$, $H_1 = 0$, $H_2 = 0$ $H_3 = 0$, 校验码 $H = 0001$, 传输的数据 $Q = 001010101$.

接收到数据后, 对所有 $H_k$ 负责的数据进行偶校验, 如果校验失败, 即出现了 1, 则说明数据出现错误. 比如, 上述数据在传输的过程中, $Q_9(D_4)$ 出现了错误, 那么 $\bigoplus\limits_{i \wedge (1000)_2 = (1000)_2} Q_i = 1$ ($H_3$ 负责校验的位), 且 $\bigoplus\limits_{i \wedge (0001)_2 = (0001)_2} Q_i = 1$ ($H_0$ 负责校验的位).

为方便表示, 设 $P_k$ 为校验位所负责的位数据的异或和. 即:

$$P_k = \bigoplus_{i \wedge k = k} Q_i$$

这个等式在书上被称为校验方程 (西电的书, 不知道是不是自己造的概念).

如果数据不出错 (不考虑一位以上的错误), 则 $P_k = 0$. 如果出错, 则至少有一个 $P_k = 1$.

很容易发现, 一个数据位被多个校验位负责校验. 仔细观察还可以得知, 该位下标二进制表示下的 1 分别被不同的校验位负责. 于是, 如果某一位出错, 通过判断校验信息, 就能立即知道是哪一位出错, 然后纠正 (取反). 比如 $P_3 = 1$, $P_0 = 1$, 其他都为 $0$, 那么就是 $Q_9$ 出错 ($9 = (1001)_2$). 更一般地, 二进制数 $P = P_3P_2P_1P_0$ 如果不为 $0$, 那 $P$ 就是出错的数据位置, 即 $Q_P$ 出错. ($P = 0$ 当然就是没有出错啦.)

所以, 海明码具有 一位纠错 能力.

海明码中的纠错原理

从上面可以看到, 海明码具有 一位检错 + 一位纠错 能力, 即 $D = C = 1$.

下面来证明一下海明码的最小码距 $L = 3$.

由纠错原理, $L - 1 = D + C$, 即 $3 - 1 = 1 + 1$ 成立.