Video在线视频

大家好

这一节我们介绍

校验与校验和

重复传输和冗余编码

既希望发现错误

也努力去纠正数据中的错误

事实上

对于许多软件而言

只要能发现传输错误就够了

因为如果你发现了一个错误

只要请求再发送一份（数据)即可

大不了多发送几次

直到你得到一份没有错漏的拷贝为止

“校验”技术

就是这一思想的具体体现

也是实际应用中最经常使用的策略

比如

几乎所有互联网连接都使用这一技术

为便于理解

我们假设所有待传输的原始信息

都是数字

事实上

能被计算机处理的所有信息

都必须数字化

只有在向人展示信息时

才把数字转译成

数字符号

文本

图形

或图像

因此

这样的假设没有问题

现在让我们看看

“校验”究竟是怎么回事

说实话

校验的方法有很多种

不可能一一列举

我们将着重介绍几种简单的方法

一种是“奇偶校验”

可以说是最简单的一种校验方法

第二种是 “简单校验和”（simple checksum）

第三种是“阶梯校验和”

我们先看奇偶校验

我们知道

在计算机内部

信息的存储与传输

都是基于二进制数“0”和“1”进行的

即任何信息都必须转换成

由“0”和“1”组成的二进制数

才能被计算机

计算

存储

传输

比如我们要传输十进数“56”

在信道中传输的是

其对应的二进制数“00111000”

符号也一样

比如要传输字母“A”

在信道中传输的是二进制数“01000001”

对此

我们有没有一种简单实用的办法

来侦测数据传输过程中

是否出现了错误呢

有

答案就是奇偶校验

奇偶校验就是

通过计算数据中“1”的个数

是奇数还是偶数

来判断数据的正确性

数据传输时

在被校验的数据后

添加一个校验位

以确保数据中“1”的个数

是奇数或偶数

对于奇校验

为确保被传输的数据中

“1”的个数是奇数

若待传输的数据中

“1”的个数是奇数

则校验位设为“0”

否则设为“1”

对于偶校验

为确保被传输的数据中

“1”的个数是偶数

若待传输的数据中“1”的个数是奇数时

则设校验位为“1”

否则设为“0”

接收方收到数据信息时

按照事先约定的校验方法

检查数据中的“1”的个数

就可以发现数据在传输过程中

是否发生了变化

比如双方约定

按奇校验方式传输数据

发送方传输的数据是“10010001”

而接收方收到的数据是“10010101”

显然就有问题了

因为发送方发送的数据中

“1”的个数是奇数

而接收方接收到的数据中

“1”的个数为偶数

所以可以肯定

传输过程某位数据被改变了

这个方法简单有效

而且很有趣

但必须注意的是

如果数据中有多位出现错误

就可能检测不出来

更检测不到错误到底发生在哪一位

尽管方法有不足

但还是得到了实际应用

在数字通信系统中

一般异步传输模式选用偶校验

同步传输模式选用奇校验

在数据存储时

内存中的数据读写也采用了奇偶校验

以提高数据的可靠性

第二种是简单校验和

假定要发送的原始信息是一串个位数

如“4 6 7 5 6”

计算它的简单校验和非常容易

你只需将原始信息中的

所有个位数相加

保留结果的最后一位数

它就是我们所要的简单校验和

比如

原始信息“4 6 7 5 6”所有数字之和是

28

但我们只保留最后一位数

因此这条信息的简单校验和是8

简单校验和计算很容易

关键是怎么用呢

方法也很简单

你只需在原始信息后面

附加校验和

然后一起发送即可

比如

原始信息“4 6 7 5 6”的简单校验和是8

传输时发送“4 6 7 5 6 8”即可

接收方知道采用的是校验和技术

在接收到信息“4 6 7 5 6 8”后

首先计算前5个数的校验和

看它是否与发送过来的

第6个数（即校验和）相同（相等）

如果相同

说明传输过程没有问题

我们不妨看看

如果传输信息时出错了

结果会怎么样

假设其中的数7变成了3

那么你会收到

4 6 3 5 6 8

我们可以计算出

前5个数的校验和为24

最后一位数是4

而不是8

因此可以肯定

消息在传输过程中出现了错误

可以请求重新发送

直到收到正确的信息为止

看起来这一思路非常完美

因为只要在原始信息后面

附加校验和即可

能发现传输过程的错误

信息传输的代价又很低

岂不美哉

但是我们还是别高兴得太早

事情远没有那么完美

我们不妨看看这个例子

看到了吧

当原始数据中一个数出错

校验和技术是可以发现的

但如果有两个数出错了

就有可能发现不了

如果不解决这一问题

数据传输的可靠性就得不到保障

第三种阶梯校验和

我们可以通过

对校验和技术做一些调整

来解决这个问题

方法是

首先定义一种新的校验和

不妨称之为“阶梯校验和（staircase checksum）”

取这样的名字主要是便于理解它

想象你处于一个楼梯的底部

楼梯台阶编号为123等等

依此类推

要计算阶梯校验和

你得先把每个数乘以楼梯的台阶号

然后才进行相加

结果只保留最后一位数

假设原始数据是“4 6 7 5 6”

其阶梯校验和的计算方式如下

我们保留最后一位数

也就是7

因此原始数据“4 6 7 5 6”的

阶梯校验和为7

为保证数据传输的准确性

我们同时使用

简单校验和及阶梯校验和

这样就确保能发现信息传输过程中

出现的任何两处错误

传输原始数据时

先附加简单校验和

再附加阶梯校验和

比如针对原始数据“4 6 7 5 6”

传输时就发送“4 6 7 5 6 8 7”

接收方收到这些信息时

先核对简单校验和

再核对阶梯校验和

如果都相同（相等）

你就可以断定这条信息

要么是正确的

要么至少有三处或更多处错误

仔细看看下面这个表

可以发现

当数据信息中有一处错误时

它的简单校验和及阶梯校验和

与原始数据不同

当消息中有两处错误时

有可能两个校验和值都不相同

也有可能简单校验和相同

但阶梯校验和不相同

或者简单校验和不同

但阶梯校验和相同

但最终都能发现错误

事实上

数学上已证明

只要错误不超过两处

就可以通过

叠加简单校验和与阶梯校验和

来发现传输过程中的错误

不难意识到

简单校验和与阶梯校验和

用于数据量不大的情况下

效果比较好

如果待传输的数据量比较大

虽然侦测错误方面仍然有效

但可靠性就有所降低了

要提高可靠性

还得在校验和上动脑筋

为了讲述和理解方便

我们假定的校验和

只有一位数字

实际应用时

真正的校验和通常会有多位数字

甚至长达150位

面对大型数据块

使用这种长度的校验和侦测错误

失败的概率极其微小

另外

尽管校验和比较长

但相对于大型数据块来说

传输代价还是较低的

比如

假设你从互联网上下载一个20兆的软件包

使用了一个100位数的校验和

来验证它的正确性

软件包的校验和

也不到软件大小的十万分之一

当然

任何一种技术方案

很难十全十美

特别是面对黑客恶意攻击

而非糟糕信道时

更是如此

对此

计算机科学家们又发明了一种

称为加密哈希函数的特定校验和

使用这种特定的校验和

就能消除这种可能性

上面我们介绍的方法和技术

似乎只与计算机数据通信与存储有关

事实并非如此

在没有计算机之前

先人们就已经使用

校验和的方法抄写《圣经》了

当司马迁用近53万字

记载了中国上千年历史的同时

远在中东的犹太人也用类似的篇幅

记载了自创世纪以来

主要是摩西以来他们祖先的历史

这就是《圣经》中的《旧约》

《圣经》简洁的文风

和中国的《史记》颇有相似之处

但是和《史记》这本

由唯一作者写成的史书不同

《圣经》的写作持续了很多世纪

后世的人在做补充时

看到的是几百年前

甚至上千年前原作的抄本

抄写的错误便在所难免

据说今天也只有牛津大学

保留了一本没有任何错误的古本

做事认真的犹太人要求

在抄写《圣经》时

要虔诚并且打起十二分精神

尤其是写到“上帝”这个词

要去洗手祈祷

但是抄写错误还是难以避免

于是犹太人就发明了一种

类似于“校验和”的方法

他们把每一个希伯来字母

对应于一个数字

这样每行文字加起来

便得到一个特殊的数字

这个数字便成为了这一行的校验码

对于每一列也做同样处理

当犹太学者抄完一页《圣经》时

他们需要把每一行的文字加起来

看看新的校验码是否和原文的相同

如果相同

说明抄写无误

如果不相同

则说明这一行

至少有一个抄写错误

当然

错误对应列的校验码

也一定和原文对不上

这样可以很快找到出错的地方

这背后的原理

和我们今天的各种校验是相同的

好 这一节我们就讲到这