漫谈计算机组成原理(六)数据校验方法

本文讲什么?

有一次,知乎上的同学问我:“为什么使用迅雷下载东西的时候,最后的百分之一总是那么慢呢?还有,为什么传输文件的时候,到最后的那一块也是那么慢呢?”
一看这位同学就是个善于发现之人,能成大事。
其实原因非常简单,对于迅雷来说,一般使用的是P2P(点对点)的传输方式,最后的百分之一时(也有可能是下载中的每个时刻),迅雷就把你作为了点对点中的一个点,让其他人从你这里下载资源,如果你下载完成了,那不就是不能明目张胆的这么干了吗,这个时候你只需要将任务暂停,然后重新开始,马上就下载完了;还有一个原因是迅雷正在进行文件的校验,这部分其实是涉及到计算机网络的内容了,今后我们会详细的讲这块的东西。
而对于文件传输的时候,最后的部分也会感觉到慢(很少见),是因为计算机传输比特流的过程中也会去校验文件,看看传过来的比特流是否发生错误。
所以,我们今天的主题是“数据校验方法”。我们讲两种校验方法,一种叫做“海明码(汉明码)校验法”,另外一种是CRC(循环冗余)校验。这两种有着不同的应用场景,下面就来开始正式的内容。

校验方法

上面讲了,在数据传输的过程中是需要进行信息的校验的——因为数据在传输过程中有各种原因(磁场、电流等)会导致数据出错,比特位从0变成1,或者由1变成0。这样就造成了数据出错,所以即时发并予以纠正,就显得尤为重要了,毕竟谁也不想得到错误的信息不是。

海明码校验

海明码由来已久,是理查德·海明于1950年提出的。
首先来说下海明码的数字位:海明码的数字位分成校验位和数据位。那么,什么是数据位什么又是校验位呢?

1 0 1 1 0 1 0 0 1

所谓的校验位,就是用于校验数据位是否正确的辅助数字;而数据位就是真实传输的二进制数。看上面的数字,共有9位,那么哪些是校验位,哪些又是数字位呢?
海明码规定,2^n-1(n=1,2,3,……)位就是校验位。所以上面的数字中:1、2、4、8……就是校验位。除了校验位剩下的就是数据位。
那么,如何确定校验位的个数呢?其实有这样一个公式2^k >= n+k+1。n是需要校验的数据共有多少位,自然可以求出k的值,k就是校验位的个数。

不同的校验位,负责校验的数据位各不相同。下面是校验规则:

图中没有给出的第C8则是负责校验8、9、10、11、12、13、14、15、24……位。其实这也是有规律的,但是上面的这几位一般就够用了,所以感兴趣的同学可以自己看一看究竟有啥规律。
此外,海明码采用的是奇偶校验的方式进行校验,所谓奇偶校验是啥呢?比如说C8负责校验的这几位,奇校验就是这几位再加上C8本身这些数中的1加起来的数量是奇数。同理偶校验就是1的个数加起来是偶数。这个就很好理解了。
接下来,我们来实际做一个例子。

  • 有二进制数1001,要求使用奇校验方式生成海明码。

乍看好像没啥思路,但是我们可以凭着感觉,从1的个数是奇数作为出发点。首先来确定校验位的个数,由公式2^k >= n+k+1可以计算出校验位的个数为3,即1、2、4位,其余为则为真正的数据位1001,如下图所示:

再由C1校验的是1、3、5、7位,则共有两个1,为了满足奇校验的条件,则C1=1。
C2的校验位为2、3、5、7位,则共有两个1,为了满足奇校验的条件,则C2=1。
C4的校验位为4、5、6、7位,则共有1个1,则C4=0.
所以,奇校验的海明码就是1110001。

海明码存在的意义就是为了纠错,所以,他的重要意义在于纠错的过程。

  • 有这样一串海明码,0100111,已知是按照偶校验的原则,找出出错的位。

这个题目复杂在如果有一位出错,那么很有可能会造成C1、C2、C4校验位的1的个数均不是偶数,所以确定起来比较麻烦,我们来看看这究竟是如何解决的。
我们按照之前的校验位原则再列出一张表格:

可以看到,在表格中,C1、C2校验位中的1的个数均为奇数,而C4中的1为偶数个,所以出错肯定是在c1、c2的公共部分。所以确定是第3位出错,则将第三位纠正为0,即原来传输的数据是0101。
以上就是海明码的全部内容,接下来介绍CRC循环冗余校验方法。

循环冗余校验码(CRC)

CRC一般用于磁盘上的数据校验。同时,CRC还应用在计算机网络数据传输过程中的数据校验。
CRC是基于模2运算的校验码。
CRC码是由两部分组成,前部分是信息码,就是需要校验的信息,后部分是校验码,如果CRC码共长n个bit,信息码长k个bit,就称为(n,k)码。编码规则如下:

  • 首先将数据位向左移动l位,则右面空出l个数据位。此时共有n位数据,n=l+k。
  • 运用一个生成多项式g(x)(也可看成二进制数)用模2除上面的式子,得到的余数就是校验码。

实际上,生成多项式是国际上制定的标准,有很多,下面举几个例子:
x^16+ x^12+ x^5+1、x^16+ x^15+ x^2+1、 x^4+ x^3 +x^2+1。
上面的g(x)则还可以堪称二进制数,比如说x^4+ x^3 +x^2+1 (从左向右,取出系数)就是11101(因为x^1没有,则为0)。

  • 信息码是110,则求CRC码

先将110向左移动4位,则为1100000。用11101|1100000(模2运算),最终的结果就是1001,则传输码为110,1100000。

结语

本文详细的介绍了海明码,另外一种CRC校验实际上只是一笔带过,在计算机网络系列文章中我们会详细介绍, 敬请期待。

如果你喜欢我的文章,请帮忙点赞;如果你对本文内容存在疑问,请留言告诉我。您的点赞和留言是对原创作者的最大支持,感谢您的阅读。
此外,本人一直在寻找志同道合的小伙伴,同样如此的可以邮件联系我:roobtyan@outlook.com.
微信公众号:最高权限比特流

发表评论

电子邮件地址不会被公开。 必填项已用*标注