通俗易懂讲通 奇偶校验 (Parity Check) 和 汉明码 (海明码、Hamming Code)

奇偶校验（Parity check）

奇偶校验是一种添加一个奇偶位用来指示之前的数据中包含有奇数还是偶数个1的检验方式

偶校验

• 编码过程：

  当实际数据中“1”的个数为偶数的时候，校验位是“0”，反之校验位是“1”，换句话说，数据位（N位）和 校验位（1位）组成的 编码数据（N+1位）中，将总共包含偶数个1。

• 校验过程：

  检查 编码数据（N+1位），如果其包含偶数个 1，则 校验通过

偶校验 举例

数据发送方和接收方约定使用偶校验来检查传输的数据，原始数据为 00001111


数据发送方：

为了满足发送出去的数据中包含偶数个1，校验位应该为 0，所以我们发送出去的编码数据是 000011110

数据接收方：

• 当接收到的数据是 000011110 时，检查 000011110 中 1 的个数，共 4 个，符合偶校验要求
• 当接收到的数据是 000011100 时，1 的个数为3，发现不符合偶校验的要求，此时需要重新发送数据
• 当接收到的数据是 000011101 时，符合偶校验的要求，此时的数据是错的，但是奇偶校验无法检测出来

从上面可以看出，奇偶校验并不总是有效，如果数据中有偶数个位发生变化，仍能通过奇偶校验，因此不能检测出错误

而且，即使奇偶校验检测出了错误，它也不能指出是哪一位出现了错误，从而难以进行更正，数据必须整体丢弃并且重新传输

在一个噪音较大的媒介中，成功传输数据可能需要很长时间甚至不可能完成。虽然奇偶校验的效果不佳，但是由于他只需要一位额外的空间开销，因此这是开销最小的检测方式。

汉明码（Hamming code）

使用一位奇偶校验位无法纠正发生错误的数据，汉明使用了一种 二进制下标 编码 奇偶校验范围 的方法实现一位错误检测并纠正

编码 及 校验

• 编码过程：

1. 将整个编码位置从左到右由 1 开始依次编号

2. 将所有编号为 2 的整数次幂的位标记为奇偶校验位 p_n（1, 2, 4, 8, 16, …）

3. 原始数据填充在其余位置 d_n，

4. 奇偶校验位填充规则

   • 校验位 1 （001₂） 由 第 xxx1₂ 数据位得到（x表示0或1，对应的十进制编码位置为 1，3，5，7，9，11，13，…）

   • 校验位 2 （010₂） 由 第 xx1x₂ 数据位得到（对应的十进制编码位置为 2，3，6，7，10，11…）

   • 校验位 4 （100₂） 由 第 x1xx₂ 数据位得到（对应的十进制编码位置为 4_7，1215，20~23，…）

   • 校验位 8 （100₂） 由 第 1xxx₂ 数据位得到（对应的十进制编码位置为 8_15，2431，40~47，…）

   • ……

     具体的得到方法和奇偶校验相同

• 校验过程：

  分别对各个校验位进行奇偶校验，未通过的校验位将他们的下标相加得到错误位置的下标

汉明码 举例

数据发送方和接收方约定使用偶校验来检查传输的数据，原始数据为 00001111


数据发送方：

首先填充原始数据得到 _ _ 0 _ 0 0 0 _ 1 1 1 1，然后填充偶校验位

• 将原始数据 第 3，5，7，9，11 位作为 校验位 1 的 数据位，得到 00011，其中 1 的个数是 2，那么校验位 1 填充 0，得到 0 _ 0 _ 0 0 0 _ 1 1 1 1， 也就是说，原始数据 第 1，3，5，7，9，11 位 这6位数据中 1 的个数为偶数
• 将原始数据 第 3，6，7，10，11 位作为 校验位 2 的 数据位，得到 00011，其中 1 的个数是 2，那么校验位 2 填充 0，得到 0 0 0 _ 0 0 0 _ 1 1 1 1， 也就是说，原始数据 第 2，3，6，7，10，11 位 这6位数据中 1 的个数为偶数
• 将原始数据 第 5，6，7，12 位作为 校验位 4 的 数据位，得到 0001，其中 1 的个数是 1，那么校验位 4 填充 1，得到 0 0 0 1 0 0 0 _ 1 1 1 1， 也就是说，原始数据 第 4，5，6，7，12 位 这5位数据中 1 的个数为偶数
• 将原始数据 第 9，10，11，12 位作为 校验位 8 的 数据位，得到 1111，其中 1 的个数是 4，那么校验位 8 填充 0，得到 0 0 0 1 0 0 0 0 1 1 1 1， 也就是说，原始数据 第 8， 9，10，11，12 位 这5位数据中 1 的个数为偶数
  
  
  

最终得到的发送出去的 数据 是 000100001111

数据接收方：

情况1：

• ​接收到的数据为 000100001111
• 分别对 校验位 1,2,4,8 的 编码数据 <1，3，5，7，9，11>，<2，3，6，7，10，11>，< 4，5，6，7，12>，<8， 9，10，11，12> 进行偶校验，即 000011，000011，10001，01111，他们的 1 的个数均为偶数，通过校验，说明数据准确

情况2：

• 接收到的数据为 100100001111 （正确数据的第1位 0 变成了 1）
• 分别对 校验位 1,2,4,8 的 <1，3，5，7，9，11>，<2，3，6，7，10，11>，< 4，5，6，7，12>，<8， 9，10，11，12> 进行偶校验，即 100011，000011，10001，01111，校验位 1 的编码数据 未通过检验，发生错误的地方在 第 1 位；将第1位取反即可获得正确的数据

情况3：

• 接收到的数据为 000100001110 （正确数据的第12位 1 变成了 0）
• 分别对 校验位 1,2,4,8 的 <1，3，5，7，9，11>，<2，3，6，7，10，11>，< 4，5，6，7，12>，<8， 9，10，11，12> 进行偶校验，即 000011，000011，10000，01110，校验位 4 和 校验位 8 的编码数据 未通过检验，发生错误的地方在 第 4+8 = 12 位；将第12位取反即可获得正确的数据

情况4：

• 接收到的数据为 000100001100 （正确数据的第11、12位 1 变成了 0）
• 分别对 校验位 1,2,4,8 的 <1，3，5，7，9，11>，<2，3，6，7，10，11>，< 4，5，6，7，12>，<8， 9，10，11，12> 进行偶校验，即 000010，000010，10000，01100，校验位 1、2、4 的编码数据 未通过检验， 1+2+4 = 7 ，实际上发生错误的位置并不是第七位，说明这种方法无法发现两位错误的情况

这样，我们就能够发现并纠正一位数据出错的情况，这种模式称为 SEC （Single-Error Correction）


但是，如果出现了两个错误，我们仍没有办法发现两位错误的情况

DED

不过，我们可以为发送出去 整体的数据 再添加一个奇偶校验位，这种模式成为 DED (Double-Error Detection）

• 当所有校验位 通过校验 时，说明数据没有出错
• 当整体校验位 未通过校验，而其他校验位 至少有一个 未通过校验 时，说明发生了 一位可纠正错误
• 当整体校验位 通过校验，而其他校验位 至少有一个 未通过校验 时，说明发生了 两位错误
• 当整体校验位 未通过校验，而其他校验位 全部 通过校验 时，说明整体校验位发生了错误
  
  
  

为上面的数据 000100001111 添加一个 整体校验位 p（使用偶校验），得到新数据 0001000011111

情况1：

• 接收到的数据为 0001000011111
• 分别对 校验位 1,2,4,8 的 编码数据 <1，3，5，7，9，11>，<2，3，6，7，10，11>，< 4，5，6，7，12>，<8， 9，10，11，12> 以及整个数据 进行偶校验，即 000011，000011，10001，01111，0001000011111， 他们的 1 的个数均为偶数，通过校验，说明数据准确

情况2：

• 接收到的数据为 0001000011101 （正确数据的第12位 1 变成了 0）
• 分别对 校验位 1,2,4,8 的 <1，3，5，7，9，11>，<2，3，6，7，10，11>，< 4，5，6，7，12>，<8， 9，10，11，12> 以及整个数据 进行偶校验，即 000011，000011，10000，01110，0001000011101，校验位 4、8 的编码数据 和 整个数据 未通过校验，说明发生了一位可纠正错误，发生错误的地方在 第 4+8 = 12 位；将第12位取反即可获得正确的数据

情况3：

• 接收到的数据为 0001000011001 （正确数据的第11、12位 1 变成了 0）
• 分别对 校验位 1,2,4,8 的 <1，3，5，7，9，11>，<2，3，6，7，10，11>，< 4，5，6，7，12>，<8， 9，10，11，12> 以及整个数据 进行偶校验，即 000010，000010，10000，01100，0001000011001，校验位 1、2、4 的编码数据 未通过校验，但是 整个数据 通过了校验，说明出现了 两位错误（但是不知道是哪里出错）

情况4：

• 接收到的数据为 0001000011110 （正确数据的第13位 1 变成了 0）
• 分别对 校验位 1,2,4,8 的 编码数据 <1，3，5，7，9，11>，<2，3，6，7，10，11>，< 4，5，6，7，12>，<8， 9，10，11，12> 以及整个数据 进行偶校验，即 000011，000011，10001，01111，0001000011110， 只有 整个数据 没有通过校验，说明仅仅是 整个数据的校验位 发生了错误，将其取反即可得到正确是数据

汉明码纠错原理

从编码过程可以看到
校验位 1 （001₂） 由 第 xxx1₂ 数据位得到，如果 校验位 1 没有通过校验，说明 编码位置 为 xxx1₂ 的数据中有一个是错的，也就是说，错的那个数据的编码位置 为 xxx1₂
校验位 4 （100₂） 由 第 0100₂ 数据位得到，如果 校验位 4 通过校验，说明 编码位置 为 x1xx₂ 的数据都是正确的，也就是说，错的那个数据的编码数据 为 x0xx₂

这样，我们就可以通过检查各个校验位得到错误数据的编码位置了，然后，在二进制中数据 非0即1，将错误数据位取反就得到正确数据了