Video在线视频

大家好

这一节

我们介绍

重复传输与冗余编码

让我们看一个美国电影

《真实谎言》里面的一个片段

大家看到了

由于噪音太大

男主人公在不断地重复

The bridge is out

The bridge is out

生活中也经常有这样的情况发生

比如

如果有人在电话信号

不是很好的情况下

告诉你一个电话号码或者是银行账号

而要你记录下来

你通常都要求对方至少重复说几遍

以便核对号码准确无误

甚至你记录好以后

还要念给对方听一次才放心

这就是这里所说的

“重复”的思想和方法

看来思想和方法是够简单的

那么计算机之间

数据通信可否采用这种方法呢

要想通过一个不可靠的信道

进行可靠的通信

其中最根本的

也是我们最熟悉的方法

就是“重复传输”

也就像生活中一样

把要传输的信息重复传送多次

我们不妨看个实例

银行试图通过互联网

把你的账户余额传给你

我们假定你的账户余额是

5213．75元

并且网络很不稳定

每传输一个数字

都有20％的概率出错

也就是变成别的数字

这样

你第一次接收

并看到的账户余额

可能是5293．75元

显然

你没办法知道这个数值

是否正确

因为网络信道不稳定

某个数字可能在传输的过程中出错了

而你又没有办法分辨

怎么办呢

您可以要求银行重复传输多次

然后推测出正确的值

不妨假定重复传输了5次

每次看到的结果是

第一次 5293.75

第二次 5213.75

第三次 5213.11

第四次 5443.75

第五次7218.75

可以看到

有时候不止一位数字出错

当然也有完全正确的时候

比如第二次

现在的关键是

你没法知道哪儿有错

自然也没法认定

第二次传输是正确的

但我们知道每一个数字

传输出错的概率是20%

正确的概率是80%

我们可以统计

同一个数字

多次传输所得到的结果

选出频率最高的那个数字做为结果

正确的可能性最大

按照这一方法

依据5次接收的结果

选出的可能性最大的结果是

5213.75

这种方法

看起来确实很简单有效

但我们能高枕无忧吗

显然不能

稍加分析就会发现两个问题

一 我们假定

这个信道的出错率只有20％

现实世界中

也许信道的出错率远高于20％

比如达到50%甚至更高时

那么这个方法还管用吗

二 你无法保证

结果是绝对正确的

上述方法只是一个推测

认为出现频率高

它就最有可能为真

但这不是绝对

只是可能

幸运的是

这两个问题还不难解决

我们只需要增加重新传输的次数

直到可靠性高到让我们满意为止

比如

假设信道的出错概率

是50％而不是20％

我们可以要求银行

重复传输1000次

而不是5次

这样我们就可以解决问题了

我们以第一位数字为例

由于出错率是50％

大约有一半的机会

能正确地传输“5”

另一半的机会

就是其他数字了

因此

总的来说

传输1000次

大约会有500次是“5”

如果出现

其他每个数字的概率相同

那其他每个数字

都会出现50次左右

500次和50次（相）比

我们当然可以确定

结果是“5”而不是别的数字了

看起来

似乎没有问题了

通过重复传输

不可靠通信的问题

能够被有效地解决

出错率基本上能被消除

可以“万事大吉”了

你还真别高兴得太早

虽然网络传输1000次

“5213.75”确实很容易

不费什么事儿

可数据量更大

要传输的信息更多的时候

问题就来了

假定

张三要下载一个200MB的软件

李四要上传一部1.5GB的电影

王五要在网上玩大型游戏

等等

如果涉及的

数据信息都要重复多次传输

那整个网络肯定要崩溃

即使不崩溃

也不知道要慢成什么样子

显然

我们还需要别的

更好的思想

方法和技术

这就是冗余编码

实际中

可靠通信最基本的思想和方法

那就是你

不能仅传输需要传输的数据

我们把这样的数据

称之为原始信息

你还要额外发送一些

多余的信息

以增加传输的可靠性

计算机科学家们

称这些额外增加的信息为“冗余”

增加冗余的方法有多种

我们先介绍冗余编码

它把原始信息

转换成一条更长的冗余信息

原始信息被删除

取而代之的是一条

更长的不同的信息

当接收方收到这条冗余信息时

又能将其转换回原始信息

即便这条冗余的信息

在糟糕的信道中

传输时受到了某种程度的破坏

我们还是以

传输“5213.75”为例

假如用英语单词

简单地把余额拼出来

结果就是

five two one three point seven five

不妨再次假设信道的出错率为20%

也就是约20％的字符

在传输过程中会变成其他字符

这样

接收方收到的信息

也许就变成了这个样子

看起来确实有点别扭

甚至有些讨厌

但是任何熟知英语的人

都应该能猜出

这条被破坏的信息

所表示的数据

应该是“5213.75”

这些用来替换的符号串

我们不妨称之为编码模式

被替换的数字

我们不妨称之为原始符号

现在我们就可以明白

这种冗余方法的传输过程了

要传输一组信息

您首先要将每个原始符号

替换成对应的编码模式

然后在不可靠的信道里面发送

当接收方接收包含

冗余的信息时

查看冗余信息的每个部分

检查其是否为有效的编码模式

如果它是有效的编码模式

就把它转换为相应的符号

如果不是有效的编码模式

那就找出与它最接近的编码模式

并把它转换成相应的原始符号

通过这种方法

信道传输过程中的任何改变

都能被识别出来

然后被纠正

真是一个不错的“idea”

原始信息不需要多次重复发送

只是用另一些符号串

进行替换而已

这些增加的信息就是“冗余”

虽然替换后

要发送的信息长度增加了

但总体效率

应该比“重复发送”高

必须明确的是

上述冗余编码方法

阐述的仅仅是一种

解决问题的思想和方法

实际应用时

还需要改良

事实上

计算机科学家们

早已找到了更漂亮的编码模式

1947年

理查德·汉明

在贝尔实验室发明的

（7，4）汉明码（Hamming code）

就是一个实用的

真实有效的编码方法

汉明码最明显的区别

是用0和1进行编码的

这也不难理解

事实上

在计算机存储

和传输数据的最底层

所有的数据和符号

都被转化为0和1的串

这是大家都知道的

编码时

每一组4位数字

都加入了冗余信息

产生了一个7位的编码模式

解码时

您首先要为

接收到的7位模式寻找完全匹配

如果寻找完全匹配失败

就选择最接近的匹配

您也许会担心

现在我们在和0

和1打交道

也许相近的匹配不只一个

最后可能会选择

错误的编码模式进行解码

令人放心的是

这种特殊编码的设计非常精巧

7位编码模式中的任何错误

都能得到确定无疑的纠正

这得归功于数学的美

但在这

我们没必要深究其细节

为什么冗余编码

在实际应用中

要比重复传输更受欢迎呢

主要原因是效率和代价

客观上两种方法

都需要传输很多额外的信息

只是重复传输

需传输的信息量巨大

代价很高

而冗余编码相对来说代价低

特别是科学家们

找到了冗余度低很多的编码模式

这就是汉明码

它在侦测错误的概率上

效率惊人

好

这一节我们就讲到这