前言
在计算机的世界里,所有数据都以二进制的形式存在,而互联网的出现让计算机之间的沟通成为可能,它们彼此通过相互传递数据实现对话.那怎么确保一台计算机向另一台计算机发送的数据没有因为网络波动造成数据跳变呢?因此为了确保每台计算机接受到的数据都是准确无误的,我们需要创造一种校验机制以保证传输数据的正确性.
奇偶校验
现在假设计算机A有一个任务,它需要向计算机B传输一条二进制数据1010.为了确保B接受到的数据没有发生跳变,A就和B约定:"我呢需要在所有的原始数据(当前是1010)前面加一个数字(也就是校验位),加上去以后保证整条数据1的个数为偶数再发给你,你接受到以后看一下整条数据1的个数是不是偶数,如果不是就说明数据发生了跳变."
- A拿到原始数据1010,一看已经有两个1了,所以它的校验位填了一个0,整条数据就成为了01010一起发送给了B
- 果不其然数据在传输过程中最后一位发送了跳变,B接受到的数据是01011,但是它发现1的个数是奇数就知道数据出错了
上述A添加的的校验位使1的个数为偶数称为偶校验.如果双方约定要使1的个数为奇数才算正确就称为奇校验.奇偶校验属于两种校验方式,但是它们的缺点也很明显.第一只能校验出一位数据发生跳变.比如上面的案例01010传输过程中右边两位发生跳变01001,1的个数照样构成了偶数,所以B接受到数据也无法判端其正确性.其次奇偶校验只能判端对错,不能指出哪一位数据发生了错误.
海明码
海明码是基于奇偶校验的基础上创造的一种更加先进的校验方式,它不仅能判端数据是否出错,而且还能指出整条数据中哪一位出了错.它的缺陷是只能校验出一位数据发生跳变,如果多位数据变化它就检测不出来了.但是在现实世界当中,数据发生跳变很大很大的概率是只有一位发生变化,因此海明码也拥有相应的应用场景.
校验原理
假设A有一条数据1010,它需要发送给B,但是为了能纠错,它引入了三个校验位a,b,c.并以下面的形式摆放:
1 0 1 c 0 b a
7 6 5 4 3 2 1
为什么要引入三个校验位以及按照这样的顺序来摆放后面会讲述,接着在每个数据下面标识相应的序号.
异或运算是什么呢?两个二进制数进行异或运算相同为0,相异为1.(比如 1 异或 1 = 0 ，1 异或 0 = 1).⊕为异或运算符.
- 我们先画三个圆,黄色部分先写上abc的序号,也就是1 2 4.随后呢把1 2 4彼此相邻的数字相加标在相邻的区域.比如 1 和 2相邻,相加等于3标在中间.1 和 4相邻相加等于5标在中间.2 和 4相邻相加等于6标在中间.最后的正中间的一块区域标为7.
- 如此一来我们就将 1 0 1 c 0 b a 分为了三组,1 3 7 5 为第一组,1号代表的着校验位a.
- 那么按校验位来分如下:a -- 3 5 7 , b -- 3 6 7 , c -- 5 6 7.
- 我们把a b c每组进行异或运算,每组计算的结果分别作为a b c的值.因此可以计算出a = (3号 异或 5号 异或 7号) = （0 异或 1 异或 1) = 0,同理b = 1 , c = 0.整条数据变成了1010010.
- 现在A将数据1010010发送给B,由于A和B事先约定过如何设置校验位以及摆放顺序的方式,B迅速的进行数据分析.
- B将数据还原成 1 0 1 c 0 b a，其中 c b a 等于 0 1 0.随后呢B也依照序号画了一个和上面一样的圆.
- a的序号为1,B将a和3号 5号 7号对应的值进行异或运算(相当于偶校验)看看是不是等于0从而判端a组的数据有没有出错.
- 我们知道a的值是A通过3 7 5在发送端进行异或运算得到的,现在B接受到后再将a和3 7 5进行异或运算照理说正常情况下应该是等于0的,如果不等于0就说明a组的a 3 7 5 这四个数中有一个数发生了跳变,那么整个a组数据归为错误.随后B又对b组和c组数据进行相同的检测.到了此步B通过计算每组的值只要有一组错误就可以判定整条数据出错,但是还不能够纠错.
- B按校验位将数据分成三组:a -- 3 5 7(1组) , b -- 3 6 7(2组) , c -- 5 6 7(4组) .假如说B计算出1组(也就是a组)出错,由于海明码校验是建立在最多只有一位数据发生跳变的基础上,那么可以说明2组和4组是正常的,那也就可以推出2组的2 3 7 6没出错,4组的4 5 6 7也没出错.结果就只能是1组的1出了错.同样的道理,B计算出1组和2组出错,那么4组肯定是正常的,也就可以推出4 5 6 7这四条数据没有出错.1组和2组的交集是3和7,7被证明没有出错,最后的结果只能是3这一位数据出错了.这便是海明码纠错的原理.
通过上面一整个流程走下来发现,数据纠错的核心是添加了3个校验位,并依据这三个校验位对数据进行了分组.通过不同组间的关联,一旦发现某一个组或多个组同时出错时可以迅速的推断出哪个组中的哪一位数据出现了错误.如此便达到了纠错的目的.那么如何判端应该添加几个校验位,以及怎么按校验位来进行数据分组就成为了接下来的关键.
校验实战
用户A需要向用户B发送一条原始数据 1 0 1 0.那怎么根据原始数据的位数计算出校验位的位数呢?
假设原始数据有n位,校验数据有k位,那么校验位能够表示2^k种情况.我们传递给B的数据等于n + k位,在最多只有一位跳变的前提下,n + k位的数据出错的情况就有n + k种,数据完全正确的情况算一种.那么 2^k 就要能表示出所有的情况才行,因此可以推出下面不等式:
2^k >= n+k+1
现在原始数据n = 4,根据上面不等式不难推出k = 3.那么就设置三位校验位 k3 k2 k1组合到原始数据当中去.那这三个校验位怎么摆放呢?我们可以先从数字中发现一个规律2^0 = 001,2^1 = 010, 2^2 = 100,2^3 = 1000.2的0次方只有第一位为1,一次方只有第二位为1,2次方只有第三位为1.我现在想让k1负责所有原始数据序号第一位为1的分组,k2负责所有原始数据序号第二位为1的分组.那么就让k1的序号 = 2^0 = 1,k2的序号 = 2^1 = 2 ,k3的序号 = 2^2 = 4.(假设有kn,kn的序号等于2^n-1)
按照上面的计算就可以将数据排列如下(并标出序号):
1 0 1 k3 0 k2 k1
7 6 5 4 3 2 1
1. 按照上面的描述现在对数据进行分组:
k1负责原始数据序号第一位为1的数据.比如3号011,5号101,7号111,它们的第一位都为1.分组情况如下:
k1 -- 3 5 7
k2 -- 3 6 7
k3 -- 5 6 7
2. 组分好了现在计算k1,k2和k3的值
k1 = 3号 ⊕ 5号 ⊕ 7号 = 0 ⊕ 1 ⊕ 1 = 0
k2 = 3号 ⊕ 6号 ⊕ 7号 = 0 ⊕ 0 ⊕ 1 = 1
k3 = 5号 ⊕ 6号 ⊕ 7号 = 1 ⊕ 0 ⊕ 1 = 0
3. 那么最终得到的数据为 1 0 1 0 0 1 0,A将此条数据就发给了B
4. B接收到了数据,它也根据2^k >= n+k+1这条公式计算出k = 3,并根据A的计算规则知道k1,k2,k3分别处于哪个位置,随后就推出了k1 = 0,k2 = 1,k3 = 0.
5. 现在B开始校验数据了.他开始做下面的三组运算.
k1 ⊕ 3号 ⊕ 5号 ⊕ 7号 = 0 ⊕ 0 ⊕ 1 ⊕ 1 = 0
k2 ⊕ 3号 ⊕ 6号 ⊕ 7号 = 1 ⊕ 0 ⊕ 0 ⊕ 1 = 0
k3 ⊕ 5号 ⊕ 6号 ⊕ 7号 = 0 ⊕ 1 ⊕ 0 ⊕ 1 = 0
按照正常没出错的情况来讲,三组计算后的结果都为0才正确.假如第一组计算结果为1,那么第二组和第三组的3号,5号,6号,7号以及k2和k3都没出错,从而可以推出k1发生了跳变.假如第一组和第二组计算结果同时为1,那么可以推断出k3,5号,6号,7号没有出错,第一组和第二组的交集是3号和7号,而7号又没问题,只可能是3号发生了跳变.
当然还有更简单的判端方式.假如第一组和第二组计算结果同时为1,那么从下往上将三个组的结果组合在一起就是011,结果等于3,表示3号数据出错了.如此检查和纠错功就全部实现了.