Video在线视频

大家好

这一节我们介绍

自纠错技术及其应用

通过前面的学习

我们已经知道

通过校验有可能判断

数据传输过程中是否发生错误

进一步

大家肯定会问

到底是哪一个数字

或者二进制位出错了

我们有可能监测出来并予以纠正吗

这就是本节要介绍的

数据传输过程中的

错误定位及自纠错技术

为了便于理解

错误定位技术的思想和方法

假定要传输的信息由数字0到9组成

并且假设要传输的信息

恰好是由16个数字组成的数字串

您可能会说

哪有这么巧的事

这个其实不难

如果要传输的信息比较长

可将其分割成

若干个16个数字长的块

如果要传输的信息块

没有16个数字这么多

可以用0补足16个数字

假设要传输这么一串数字

发送方可以按如下步骤操作

一 将上述16个数字按照从左往右

自上往下重新排列成

一个4行4列的样式

就像这样

二 计算每一行的简单校验和

并添加在每行的右侧

比如 要得到第二行的校验和

只需要计算

五加四加三加六等于十八

保留最后一位数8

得到这么一个结果

三 再计算每一列的简单校验和

并添加在每列的底部

比如 要得到第三列的校验和

容易计算

三加三加五加九等于二十

保留最后一位数0

所得到的整个结果就像这样

四 按照从左到右

自上往下的方式

把上述数字重新排列成一个数字串

就会得到这么一个

24个数字的数字串

这就是用于发送端发送的数字串

由于信道不可靠

数据传输有可能出错

比如其中有一个数字发生了改变

变成了另外一个数字

具体是哪一个数字发生了改变

其实并不重要

重要的是我们怎么知道哪一个改变了

并设法恢复其“原貌”

我们不妨假定

收到的24位数字串是这么个样子

接收方按照下面的步骤来操作

就可以进行错误定位以及自纠错了

一 把接收到的数字串按先后顺序

排成这么一个五行五列的方阵

应该注意到

最后一行和最后一列

对应的就是

随原始信息一起发送来的校验和

二 重新计算

每一行每一列的简单校验和

以便与接收到的校验和进行对比

结果如图所示

可见 这里有两组校验和

一组是接收到的

一组是计算出来的

如果传输没有任何错误

那么这两组校验和的值

应该完全相同

如果传输过程中

有一位数字发生了变化

则两组校验和肯定不一样

在这儿 我们发现

这两组校验和确实不太一样

第三行的5和0

第二列的3和8

这就说明

错误肯定是在第三行 第二列

问题找到了

怎么纠正呢

也就是怎么知道

正确的数字是什么呢

解决这个问题也不难

只要用一个能让两个校验和

都正确的数字替换出错的7即可

我们知道

第二列的校验和本应为3

但结果却是8

换句话说

校验和需要减去5

我们把错误的7减掉5

得到2

也可以通过检查第三行

来验证这一改变

这样一来

错误同时被定位和纠正了

三 去掉校验和

然后按从左到右

自上而下的顺序重新排列

所得的结果就是我们应该接收到的

正确的数字串

在计算学科中

这种定位错误的方法也称为

二维奇偶校验码

到此 以上我们讨论的方法

都是以数据传输为例展开的

事实上

这些思想和方法在信息存储方面

也得到非常好的应用

比如CD

DVD

和计算机硬盘

都非常依赖纠错码

否则我们无法享受

它们在数据存储方面的可靠性

校验和的方法

已经在生活中得到了较为普遍的应用

图书的国际标准图书号ISBN

是一个有10位数字的号码

其中最后的一位数字

并不是图书的标识

而是一个校验码

就像我们之前说的奇偶校验码

用来检验整个号码是否有错误

当我们使用ISBN号订购图书时

如果有一位数字出错

则通过校验和可以检查出来

不至于使我们买到错误的图书

另外一种相似的校验码为条形码

当我们在大型购物城

购物结帐时

收银员都在用一个手持设备

扫描所购物品上的条形码

如果条形码读错了

扫描器就会报警

收银员就会重新扫描

最为普遍的互联网协议TCP

也在其发送的每块数据包上使用校验和

如果收到一个校验和不正确的包

就直接丢弃它

TCP协议在必要的时候

会自动传输这些包

好 这一节我们就讲到这

谢谢大家