计算机在数据传输方面，为了防止传输过程中丢失数据等异常情况发生，往往需要进行内容校验，今天就和大家说说错误检测与矫正。
具体的实现很简单——在传输的数据中加入一些校验位数。
那么这些校验位数是如何工作的呢？我们就从最简单的校验方式开始说起。
数据传输对于计算机而言就是二进制传输，每一位就是一个bit，奇偶校验最大的特点就是只需要增加一个bit即可进行校验。奇偶校验位是对给定位数的二进制数中1的个数是奇数还是偶数的二进制数，它有两种类型——奇校验位和偶校验位。如果一组给定数据位中1的个数是奇数，那么偶校验位就置为1，从而使得总的1的个数是偶数。如果给定一组数据位中1的个数是偶数，那么奇校验位就置为1，使得总的1的个数是奇数。
奇偶校验位的作用是，保证二进制数据中出现的1的个数是奇数或者偶数。
如下这些例子，红色位表示校验位，黑色位表示真实传输数据。
| 原始数据 | 1的个数 | 奇校验 | 偶校验 |
| 0000000 | 0 | 00000001 | 00000000 |
| 1000011 | 3 | 10000110 | 10000111 |
| 1100011 | 4 | 11000111 | 11000110 |
| 1111111 | 7 | 11111110 | 11111111 |
奇偶校验位可以检测数据传输中1出现的奇偶次数是否正确，但是它并不能告诉计算机错误出在哪里，所以在应用中一旦奇偶校验检测失败，则数据全部放弃。
我整理了奇偶校验的使用及特点：
1. 使用一位数据能够达到的最好的校验码效果。
2. 检测存在概率，如果丢失两个1，则无法检测。
3. 数据传输时，不适合检测数据噪音大的场景。
4. 实现上硬件要求友好，仅需要异或门即可实现。
5. 不能进行纠错，出错时数据需放弃。
6. 被广泛用于计算机硬件中，如许多微处理器的指令高速缓存中都包括奇偶校验位保护。
在冗余磁盘阵列（RAID）中，为了保证一定的数据容错性，也会采用奇偶校验的方式，在这里被称作奇偶校验块。具体原理就是，对于给定两个数据块，通过XOR生成第三个数据块（奇偶校验块），这样如果第一个数据块丢失，则可以通过第二个数据块和第三个数据块进行复原。
数据块1:01101101
数据块2:11010100
数据块3:10111001
如果数据块1丢失，只需要将2和3进行XOR，即可得到数据块1：01101101。
和简单的奇偶校验位不同，还有水平奇偶校验、垂直奇偶校验和水平垂奇偶校验这三种。
具体原理就是将数据分割成m*n的矩阵，然后进行二维度校验。通过字面意思，我们就比较清楚，水平和垂直类似只不过校验方向不同，而水平垂直奇偶校验则是两者的合体。
通过举例大家就会明白了，假设数据是由长度为20位的二进制构成，m = 5， n = 4，则矩阵如下：
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
水平奇偶校验就是根据矩阵的四行，分别生成4个独立的奇偶校验位，这里以偶校验位(浅粉色)参考：
| 1 | 0 | 1 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 |
垂直偶校验位（浅绿色）：
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 |
水平垂直偶校验位：
| 1 | 0 | 1 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 |
可以看出，水平垂直奇偶校验位需要m + n - 1个位，优势是可以修复单个错误位。
奇偶校验只能验证数据的有效性，如果检验为无效，则只能废弃无法进行很好的纠错，这个问题让汉明很不爽。
1940年，小伙儿汉明像往常一样在贝尔实验室，运用贝尔模型V 电脑进行工作。机器输入端是依靠打孔卡，而打孔这一操作有时候会读取错误，每次错误发生就会有个小灯一闪一闪，汉明就要人工去处理下。周末不上班的时候就尴尬了，没人处理，机器只能跳过执行下一个操作。
有个周末，汉明正好在工作，小灯一闪他就去较正一下，又一闪就再去较正一下。他感觉很不爽，工作很low，决定好好研究一个检测算法，直接检测出来错误在哪里，工作就省事多了。伟大的发明在此诞生——汉明码！！！
汉明码有多牛逼？
1. 汉明码是应用最广泛的校验码，如内存（RAM）普遍集成。
2. 没有一个校验码，能在相同空间消耗的情况下，达到汉明码效果。
如果一条信息中包多个用于纠错的位，且通过妥善安排这些纠错位使得不同的出错位产生不同的错误结果，那么我们就可以找出出错位了。在一个7位的信息中，单个位出错有7种可能，因此3个错误控制位就足以确定是否出错及哪一位出错了。汉明研究了包括五取二码在内的编码方案，并归纳了他们的想法。
wikipedia很清楚的描述了通用算法：
1. 从1开始给数字的数据位（从左向右）标上序号, 1，2，3，4，5...
2. 将这些数据位的位置序号转换为二进制，1, 10, 11, 100, 101,等。
3. 数据位的位置序号中所有为二的幂次方的位（编号1，2，4，8，等，即数据位位置序号的二进制表示中只有一个1）是校验位。
4. 所有其它位置的数据位（数据位位置序号的二进制表示中至少2个是1）是数据位。
5. 每一位的数据包含在特定的两个或两个以上的校验位中，这些校验位取决于这些数据位的位置数值的二进制表示。
从图中可以看出：
1. 校验位1覆盖了所有数据位位置序号的二进制表示倒数第一位是1的数据：1（校验位自身，这里都是二进制，下同），11，101，111，1001，等
2. 校验位2覆盖了所有数据位位置序号的二进制表示倒数第二位是1的数据：10（校验位自身），11，110，111，1010，1011，等
3. 校验位4覆盖了所有数据位位置序号的二进制表示倒数第三位是1的数据：100（校验位自身），101，110，111，1100，1101，1110，1111，等
4. 校验位8覆盖了所有数据位位置序号的二进制表示倒数第四位是1的数据：1000（校验位自身），1001，1010，1011，1100，1101，1110，1111，等
5. 简而言之，所有校验位覆盖了数据位置和该校验位位置的二进制与的值不为0的数。
Leave a Reply