3-2差错处理概述在线视频

各位好

我们已经知道数据链路层的

一个主要的功能

是要保证我们传输的帧是可靠的

但是任何信道

即使是光纤

它也会出错

出了错之后呢就要进行处理

怎么处理这些差错呢

首先你就是要检测出错误

然后再说用什么手段去处理

处理错误的手段呢

通常就是纠错和检错两种

差错的类型分两种

一种是单个的错误

它是分散在各个数据块里面的

还有一类呢是突发错误

集中在某个块里面

我们举个例子

比如说有一个数据块

它的大小是1000个比特

总共有100个这样的块

如果我们的出错率是千分之一

那么单个错误就分散在

每一个数据块里面

也就是说这100个千位块

每个块里面都有一个错误

而突发错误呢

它是集中在一个数据块里边

整个块100个块里面

有一个块是错误的

其他的块都是正确的

一般来讲呢

突发错误比单个的错误

更加难以处理

但是呢我们会用一些巧妙的方法

利用处理单个错误的方法

来应对 对付这个突发的错误

差错处理刚才我们说了有两种

一种是纠错一种是检错

那么纠错是什么呢

是一种前向纠错的技术

当它检查出错误

发现了错误之后

它要试图从错误中恢复出

正确的那个码来

因为纠错码它需要纠错

所以它需要太多的冗余位

纠错的开销是比较大的

它在有线网络里头极少采用

主要用于无线网络里头

而检错码呢

它只能发现错误

不能从错误中恢复

但是呢我们可以通过其他的手段

比如说重传来恢复

局域网里头通常采用的是检错码

两种处理方法

适用于不同的网络环境

下面呢我们来探讨几个跟差错

错误处理相关的几个概念

第一个叫码字

码字指的是包含数据位

和校验位的N位单位

或者N位模式

跟码字相关的另外一个概念呢

叫海明距离

两个码字的海明距离

指的是两个码字之间

不同位的数目

比如说有两个码字

第一个码字

10001001

另外一个码字

10110001

这两个码字

它的海明距离是3

为什么呢

是因为在这两个码字里边

它只有三位码字

就是从第三位开始

第三位、第四位、第五位

这三位码字它是不同的

其他的位都是相同的

那么不同的位数是3

那么它的海明距离就是3

那么这个

两个码字的海明距离

其实是可以用异或来计算的

异或就把这两个码字

按位进行异或的运算

运算的结果里边

你数1的个数

1的个数就是海明距离

全部码字的海明距离

指的是在任意两个码字之间的

海明距离的最小值

作为全部码字的海明距离

比如说有100个码字

它们两两之间都有一个海明距离

最小的那个海明距离是50

那么这个50

就是整个码字的海明距离

海明距离它的物理意义是这样的

就是如果海明距离为d

那么一个码字

要变成另外一个码字的话

至少需要跳变d位

海明距离与检错的关系是这样的

海明距离为d+1的编码

能检测出d位的差错

为什么呢

因为在距离为d+1的检错码里面

只改变d位的错

不可能跳变为另一个合法的码字

我们要注意的是理解这句话

在编码系统里面

既有合法的码字

也有非法的码字

非法的码字指的是错误的码字

举一个例子来看

比如说我们熟知的奇偶校验码

海明距离是2

也就是说d等于2

d等于2就能查出一个错误

2减1一个错误

奇偶校验码

指的是在一个校验位

可以追加到我们要传输的数据后面

举个例子

比如说有一个要传输的数据

是10111000这8位

那如果我们做偶校验的话

我们就数8位里边它1的个数

它1的个数是4个

那么我们在后面

只能追加0

保证编码后的码字里面

1的个数是偶数个

所以它的后面只能追加0

如果我们要采用奇校验的话

我们在这个码字后面

就必须要加一个1了

因为加一个1

才让整个码字它的1的个数是5

是奇数个

下面我们来看一个例子

来理解这个码字

海明距离跟检错

能够检错的位数的关系

比如说一个系统

它要传输的原始的码字是两位数

就是00、01、10和11

这四个值

假如我们采用偶校验来进行编码

编码后的码字就是

000、011、101和110

假如说这个时候

接收方收到一个码字是001

它在系统里面发现

这个001它不是这四个

合法码字中的任何一个

所以它知道这是一个非法的码字

所以它立刻就判断

这是一个错误的码字

出错了

检查出错误来了

那么001

我们知道可能它就是000

跳变一位之后变成的

所以它就判定为错

这是一个正确的检错方法

但是如果说我们的系统

收到一个000

这是一个合法的码字

是正确的

接收方只能把它判定为正确

因为它是四个合法码字中的一个

但是我们不排除

它是110跳变两个

就把11这两位跳变为0

跳变2之后变成的一个错误码字

但是系统对这种情况

是无能为力的

海明距离等于2的奇偶校验

是可以检查出一个错误的

发生一个比特的跳变

我们可以检测出来

但是如果发生两个比特

这样的偶数个跳变

接收方是无能为力的

是无法检测出这个错误

认为这个码字是正确的

这是它的局限性

接下来我们看一下

海明距离与纠错的关系

海明距离为2d+1的编码

能纠正d位差错

为什么呢

因为在这个时候

如果一个码字

有发生d位的错误

那么它仍然距离原来的码字最近

是d

距离是d

那么我们就可以直接恢复出

正确的码字来

它离谁最近

它就恢复出那个码字

这是海明距离与纠错的关系

我们举一个例子来看一看

比如说有一个系统

有四个合法的码字

这四个合法的码字呢都是十位的

第一个是10个0

第二个是5个0 5个1

第三个是5个1 5个0

第四个是10个1

这四个码字

它们的海明距离是5

利用刚才那句话

描述的2d+1等于5

我们可以算出d等于2

所以我们可以纠正出

两位错误来

假如说我们的发送方

发送的是5个0 5个1

这样的码字

接收方收到的码字却是这样的

7个0 3个1

接收方接下来它会做这样一个事情

它会把这个码字和

合法的码字进行海明距离的计算

它看这个码字离谁的海明距离更小

也就是说离谁更近

它发现呢

这个码字离5个0 5个1

它的海明距离是2

是最小的

所以

它就把这个码字纠正为5个0 5个1

就恢复出正确的码字来了

我们再看另外一个例子

发送方发送的是10个0

接收方收到了一个码字

是7个0 3个1

也就是说

后面的3个0发生了跳变

跳变成了3个1

发生了3个跳变

能不能够纠正出错误来呢

我们来看一下

接收方收到这个码字

它做的工作仍然是第一步去看

它是不是合法的码字

它发现这个码字

在不是4个合法码字之一

所以它是有错误的

但是它离哪个码字最近呢

它发现它离5个0 5个1

这个码字的海明距离只有2

是最近的

所以它就把这个码字

恢复成5个0 5个1

但是我们知道

发送方发送的不是这个

是10个0

所以就错了

也就是说

刚才那句话

海明距离相距为2d+1的编码系统

它只能够纠正出d位错误

绝对不可能纠正出d+1位

或者更多的错误来

像刚才我们这个例子就是

它的海明距离是5

所以它顶多能纠正两位错误

发生了三位错误

它就无能为力了

就犯错了

随着海明距离的增加

纠错的能力也增加了

也就是说

海明距离越大

纠错能力越强

比如说我们的海明距离为3

可以纠正一个错误

而海明距离为5

才可以纠正出两个错误来

当一个系统中的海明距离

增加的时候

合法的码字就减少了

即信道的利用率

或者编码的效率就降低了

其实这是一对矛盾

小结一下

在通信世界里边

可以说不存在完美的信道

任何信道都会出错

错误呢

分成单个错误和突发的错误两类

处理错误的手段呢也有两类

纠错和检错

这两类方法呢各有优缺点

你需要根据不同的传输环境

来选择其中的一种

海明距离量度了两个码字之间的

不同位数

海明距离也决定了

能够纠错或检错的位数