ch3(1)_差错控制技术

1、第第3 3章章 差错控制技术差错控制技术3.1 差错控制的基本概念差错控制的基本概念3.2 流量控制方法流量控制方法3.3 常用差错控制编码方法常用差错控制编码方法3.4 常用差错控制方法常用差错控制方法3.5差错控制的性能估算和应用差错控制的性能估算和应用CH3 差错控制技术差错控制技术 必要性必要性： 数据通信要求信息传输过程具有高度的可靠性数据通信要求信息传输过程具有高度的可靠性即误码率足够低；即误码率足够低； 然而信号在传输过程中由于传输损耗（噪声，然而信号在传输过程中由于传输损耗（噪声，衰损，失真）不可避免要产生一些差错即出现衰损，失真）不可避免要产生一些差错即出现误码。误码。 大体

2、上分为：大体上分为： 随机差错随机差错随机噪声随机噪声 突发差错突发差错脉冲噪声脉冲噪声CH3 差错控制技术差错控制技术 解决的办法解决的办法： 一是改善传输信道的电气特性（先进的物一是改善传输信道的电气特性（先进的物理设备要付出成本）提高传输可靠性；理设备要付出成本）提高传输可靠性； 另一种办法在相应的物理设备条件下采用另一种办法在相应的物理设备条件下采用计算机技术进行差错编码和控制，自动检计算机技术进行差错编码和控制，自动检测错误并在可能情况下纠正错误，这就是测错误并在可能情况下纠正错误，这就是所谓的所谓的差错控制技术。差错控制技术。 3.1 差错控制的基本概念差错控制的基本概念3.1.1

3、 差错控制的基本概念差错控制的基本概念3.1.2 差错控制编码的特性和能力差错控制编码的特性和能力 3.1.1差错控制的基本概念差错控制的基本概念 所谓差错即为误码；所谓差错即为误码；差错控制的核心是差错控制的核心是抗干扰编码，简称抗干扰编码，简称差错编码差错编码（属于二次（属于二次编码即信道编码），它的编码即信道编码），它的基本思想基本思想是通是通过对信息序列作某种变换，使原来彼此过对信息序列作某种变换，使原来彼此独立、互不相关的信息码元产生某种规独立、互不相关的信息码元产生某种规律性（相关性），从而在接收端根据这律性（相关性），从而在接收端根据这种规律性来检查，进而纠正传输信号序种规律性来

4、检查，进而纠正传输信号序列中的差错列中的差错。变换的方法不同就构成了。变换的方法不同就构成了不同的编码。不同的编码。 3.1.1差错控制的基本概念差错控制的基本概念1.1.信息码和监督码信息码和监督码2.2.差错控制的基本特点差错控制的基本特点3.3.差错控制的理论基础差错控制的理论基础4.4.差错控制编码的基本原理差错控制编码的基本原理5.5.差错控制实例差错控制实例6.6.编码效率编码效率7.7.差错编码的分类差错编码的分类 1.1.信息码和监督码信息码和监督码 信息码（元）信息码（元）：发送用户端欲发送的信：发送用户端欲发送的信息序列，本来彼此独立，互不相关；由息序列，本来彼此独立，互不

5、相关；由用户控制，最终也交给接收用户。用户控制，最终也交给接收用户。 监督码（元）监督码（元）: :为了使信息码元产生某为了使信息码元产生某种规律性，可按照某种规则在用户信息种规律性，可按照某种规则在用户信息序列中插入一定数量的新码元，这种新序列中插入一定数量的新码元，这种新码元叫监督码（元）。码元叫监督码（元）。监督码元不受用户控制，最终也不交给接监督码元不受用户控制，最终也不交给接受用户。受用户。9 插入监督码元的目的是使原来彼此独插入监督码元的目的是使原来彼此独立、互不相关的信息码元产生某种规立、互不相关的信息码元产生某种规律性（相关性）从而使接收端能够根律性（相关性）从而使接收端能够根

6、据这种规律性来检测传输过程是否有据这种规律性来检测传输过程是否有误。误。2.差错控制的基本特点差错控制的基本特点 引入差错编码控制后，实际传输的引入差错编码控制后，实际传输的 信息序列信息序列=（信息码元（信息码元+监督码元）监督码元），称为，称为码组。码组。 在信道容量既定的情况下，信息传输速在信道容量既定的情况下，信息传输速率有所降低，但信息传输的可靠性有所提率有所降低，但信息传输的可靠性有所提高，既差错控制编码用高，既差错控制编码用降低降低通信系统通信系统信息信息传输的有效性传输的有效性的代价来的代价来提高信息传输的可提高信息传输的可靠性靠性。Why?同样的信息量要用更多的比特位！同样的

7、信息量要用更多的比特位！3.差错控制的理论基础差错控制的理论基础香农信道编码定理香农信道编码定理 香农信道编码定理 ：每个信道都具有每个信道都具有确定的信道容量确定的信道容量C，只要信息传输速率：，只要信息传输速率：Rb（bps）=C则理论上就一定存在一种则理论上就一定存在一种编码方式，使其译码差错概率（即编码方式，使其译码差错概率（即误码误码率率）Pe满足：满足：Pe=A e-n E(Rb)式中式中n n码字长度（码长）码字长度（码长） E E（R Rb b）误差指数（当误差指数（当R Rb b=C00）A A正系数正系数P Pe eN Ne eN N误码率是指二进制码元在数据误码率是指二进

8、制码元在数据传输系统中被传错的概率传输系统中被传错的概率 ；N N为传输的为传输的二进制码元总数，二进制码元总数， N Ne e为被传错的码元数。为被传错的码元数。香农信道编码定理香农信道编码定理E E（R Rb b）与）与R Rb b的关系如图所示：的关系如图所示： C 使使E(Rb ) 或或 n 使使e-nE(Rb ) 可见要使可见要使Pe满足要求：满足要求：一是增加信道容量一是增加信道容量C C，从而使，从而使E E（Rb ）增加（通信硬件系统设计人员通常采增加（通信硬件系统设计人员通常采用的方法）；用的方法）；另一种方法是只要另一种方法是只要R Rb b=C=连环码。连环码。差错编码的

9、分类差错编码的分类 (4)(4)按照纠正错误的类型可分为按照纠正错误的类型可分为纠正随机错纠正随机错误的码误的码和和纠正突发错误的码纠正突发错误的码。 (5)(5)按照每个码元取值来分按照每个码元取值来分二进制码二进制码和和多进多进制码制码。 3.1.2 差错控制编码的特性和能力差错控制编码的特性和能力1.1.海明（海明（hamminghamming）距离）距离2.2.最小距离最小距离3.3.海明距离（码距）海明距离（码距）4.4.最小距离与抗干扰能力的关系最小距离与抗干扰能力的关系1.1.海明（海明（hamminghamming）距离）距离 1.1.海明海明（hamming）距离：）距离：指

10、两个不同的指两个不同的码组其对应码位（二进制位）的码元不同码组其对应码位（二进制位）的码元不同的个数，简称的个数，简称码距码距 ；用用d表示表示：nikijiaad1)(式中式中表示模表示模2 2加（异或）加（异或） n n表示码组长表示码组长度度a akiki和和a ajiji表示第表示第k k个码组和第个码组和第j j个码组的第个码组的第i i位码元位码元 例：（10111011）和（）和（01000100）两码组间距离：）两码组间距离：d= d= （1011010010110100）=4 =4 （0000）和（）和（0000）两码组间码距：）两码组间码距：d=0 d=0 （0101）和（

11、）和（1111）两码组间距）两码组间距离：离：d=1 d=1 （001001）和（）和（100100）两码组间距离）两码组间距离：d=2d=2（101101）和（）和（010010）两码组间距离：）两码组间距离：d=3d=3海明（海明（hamminghamming）距离实例）距离实例 2.2.最小距离：最小距离：一个一个中，任何两个码中，任何两个码组间海明距离组间海明距离( (即码距即码距) )的最小值称为码组集的最小值称为码组集合的最小距离。用合的最小距离。用d0d0或或d dminmin表示表示: : 表示 )(min/01minnikijiaadd式中式中表示模表示模2 2加加 n n表

12、示码组长度表示码组长度a akiki和和a ajiji表示第表示第k k个码组和第个码组和第j j个码组的第个码组的第i i位位码元码元 minmin表示最小值表示最小值2.2.最小距离最小距离 举例： 码组集合码组集合 （000000）（）（001001）（）（010010）（）（011011）（100100）（）（101101）（）（110110）（）（111111） d0=1 d0=1 没有检错能力。没有检错能力。 码组集合码组集合 （000000）（）（011011）（）（101101）（110110） d0=2 d0=2 能检测出能检测出1 1位码位出错。位码位出错。 码组集合码组集

13、合 （000000）（）（111111） d0=3 d0=3 能能检测出检测出2 2位出错并能纠正位出错并能纠正1 1位错误位错误。最小距离实例最小距离实例n如果如果8 8种码组都作为许用码组，任两个种码组都作为许用码组，任两个码距间的最小距离为码距间的最小距离为1 1，记，记dmin =1; =1;n如果如果4 4种码组种码组(000 011 101 110)(000 011 101 110)作为许作为许用码组，任两个码距间的最小距离为用码组，任两个码距间的最小距离为2 2，记记dmin =2; =2;n如果如果2 2种码组作为许用码组种码组作为许用码组(000 111)(000 111)，

14、任两个码距间的最小距离为任两个码距间的最小距离为3 3，记，记dmin =3;=3;n所以码组集合中最小距离越大，其抗干扰能力（包括检错和纠错能力）越强。 几何表示：几何表示：用用3 3位码元构成的位码元构成的8 8个码组表个码组表示立方体中各个顶点示立方体中各个顶点；n3.3.海明距离（码距）海明距离（码距）就是从一个顶点移就是从一个顶点移动到另一个顶点所经历立方体的最少边动到另一个顶点所经历立方体的最少边数；数；n则所谓则所谓最小距离最小距离就是立方体中从一个顶就是立方体中从一个顶点移到另一个顶点所经历的最少边数点移到另一个顶点所经历的最少边数 。3.3.海明距离（码距）海明距离（码距）n

15、3.3.海明距离（码距）海明距离（码距）就是从一个顶点移动就是从一个顶点移动到另一个顶点所经历立方体的最少边数；到另一个顶点所经历立方体的最少边数；n则所谓则所谓最小距离最小距离就是立方体中从一个顶点就是立方体中从一个顶点移到另一个顶点所经历的最少边数移到另一个顶点所经历的最少边数 。4.4.最小距离与抗干扰能力的关系最小距离与抗干扰能力的关系 定理定理3.13.1若一种码的最小距离为若一种码的最小距离为d0d0，则它能，则它能检查传输错误个数（检错能力）检查传输错误个数（检错能力）e e应满足：应满足：d0=e+1d0=e+1 定理定理3.23.2若一种码的最小距离为若一种码的最小距离为d0

16、d0，则它能，则它能纠正传输错误个数（纠错能力）纠正传输错误个数（纠错能力）t t应满足：应满足：d0=2t+1d0=2t+1 定理定理3.33.3若一种码的最小距离为若一种码的最小距离为d0d0，则它的，则它的检错能力和纠错能力应满足：检错能力和纠错能力应满足：d0=e+t+1 d0=e+t+1 （e=te=t） 例例3.1 3.1 求码集合求码集合(000),(011),(101),(110)(000),(011),(101),(110)和和(000),(111)(000),(111)最小距离最小距离d d0 0及纠（检）错的及纠（检）错的能力。能力。 实例（实例（P53）解：最小距离实例

17、实例 检错和纠错能力检错和纠错能力第一组：第一组：d0=2，e=d0 1=1，可检测出一个错，可检测出一个错，（定理（定理1）第二组：第二组： d0 =3e=d0 1=2，可检测出二个错，（定理可检测出二个错，（定理1） t=(d0-1)/2=1，可纠正一个错，（定理可纠正一个错，（定理2） e+t=d0-1=2 ，令（，令（t=e） e=1，t=1， 纠错、检错各纠错、检错各1，（定理，（定理3）3.2 3.2 流量控制流量控制： 流量控制必要性：流量控制必要性：任何设备都有一个处理数据任何设备都有一个处理数据的速率限制，并且存储输入数据的存储容器的速率限制，并且存储输入数据的存储容器容量也

18、是有限的。接收设备必须在达到这些容量也是有限的。接收设备必须在达到这些限制之前通知发送设备并且请求发送设备发限制之前通知发送设备并且请求发送设备发送较少的数据帧或是暂停一会。送较少的数据帧或是暂停一会。 缓冲区缓冲区：接收方在使用输入数据之前必须对接收方在使用输入数据之前必须对它们它们进行校验和处理进行校验和处理，这种处理的速率通常，这种处理的速率通常比传输速率要低。因此，每个接收设备都必比传输速率要低。因此，每个接收设备都必须有一块存储器，叫做须有一块存储器，叫做缓冲区缓冲区，用来在进行，用来在进行处理之前保存输入数据。处理之前保存输入数据。3.2 3.2 流量控制流量控制 1.流量控制是为

19、了是为了确保发送端发送的数据确保发送端发送的数据不会超出接收端接收数据能力的一种技术不会超出接收端接收数据能力的一种技术，即避免接收端即避免接收端缓冲区缓冲区不够用的情况，它是不够用的情况，它是数据由数据由数据链路层（低层）交给网络层数据链路层（低层）交给网络层（高层）的中转站（高层）的中转站。 发送方从高层获取的数据在传输发送方从高层获取的数据在传输之前、接收方将接收到的数据在之前、接收方将接收到的数据在提交给高层之前一般都要用一个提交给高层之前一般都要用一个缓冲区来暂存。缓冲区来暂存。 2.2.流量控制模型流量控制模型 发送方发送方接收方接收方从从主主机机取取数数据据上上交交主主机机DAT

20、A1DATA4DATA3DATA2 无差错无差错 时间时间发送方发送方接收方接收方从从主主机机取取数数据据上上交交主主机机DATA1DATA2 有差错和丢失有差错和丢失DATA3DATA43.3.常用流量控制方式常用流量控制方式 停止等待停止等待(stop(stopandandwait)wait)流量控制方式流量控制方式: :一次发送一帧一次发送一帧 滑动窗口滑动窗口(sliding(slidingwindow)window)流量控制方式：流量控制方式：一次发送若干帧。一次发送若干帧。3.2 3.2 流量控制流量控制 3.2.1 停止停止等待流量控制等待流量控制 3.2.2 3.2.2 滑动窗

21、口流量控制滑动窗口流量控制3.2.1 停止停止等待流量控制等待流量控制 在停止等待流量控制协议中：在停止等待流量控制协议中： 发送方每发送一帧后就等待来自接收方的一发送方每发送一帧后就等待来自接收方的一个应答帧（帧个应答帧（帧=数据数据+控制信息）；控制信息）； 接收方收到数据后回送应答帧接收方收到数据后回送应答帧（ACK/NAK）；）； if ACK then发送下一帧发送下一帧 else（NAK）重发原来的帧；）重发原来的帧； 发送和等待过程不断重复，直到发送端发发送和等待过程不断重复，直到发送端发送一个结束帧（送一个结束帧（EOT）为止。）为止。AcknowledgeNegative A

22、cknowledgeEnd of Transmission 停止等待停止等待协议协议流量控制模型流量控制模型data iACKdata i+1发出一帧发出一帧等待，直到收到等待，直到收到ACK才发送下一帧才发送下一帧发送方发送方接收方接收方工作过程：工作过程：SendReceive/Ack(nak)Resend结束结束 ifif接收方对接收方对EOTEOT帧回送应答帧帧回送应答帧 thenthen终止传输。终止传输。报文（来自网络层）控制：报文（来自网络层）控制： 小报文小报文 大报文：分块变成小的数据块，解决接收缓冲区大报文：分块变成小的数据块，解决接收缓冲区容量有限容量有限/ /传输延迟问

23、题传输延迟问题 控制特点：控制特点： 每一帧（每次只能传输一帧）数据都要确认和检每一帧（每次只能传输一帧）数据都要确认和检验验 效率低，速度慢，不适合实时系统。效率低，速度慢，不适合实时系统。3.2.2 3.2.2 滑动窗口流量控制滑动窗口流量控制 在停止等待流量控制协议中：在停止等待流量控制协议中：每次只允许传送每次只允许传送一一帧帧； 在在滑动窗口流量滑动窗口流量控制协议中：控制协议中：允许一次传送允许一次传送多帧多帧，从而大大提高效率。从而大大提高效率。 发送方在收到应答信息前可以发送发送方在收到应答信息前可以发送若干帧，若干帧，帧帧可以直接依次发送；可以直接依次发送； 接收方只对接收方

24、只对一些帧一些帧进行应答确认，使用一个确进行应答确认，使用一个确认帧（应答帧认帧（应答帧ACK/NAKACK/NAK）对多个数据帧的接收）对多个数据帧的接收进行确认；当接收端发出一个进行确认；当接收端发出一个ACKACK信号，它就信号，它就在其中包含了在其中包含了预期接收预期接收的下一帧编号。的下一帧编号。 使得使得SlidingSlidingwindowwindow依次传输多个帧依次传输多个帧 3.2.2 3.2.2 滑动窗口流量控制滑动窗口流量控制 1.1.基本术语基本术语2.2.发送窗口发送窗口3.3.接收窗口接收窗口4.4.实例：窗口滑动的动态过程实例：窗口滑动的动态过程5.5.窗口大

25、小的限制因素窗口大小的限制因素1.1.基本术语基本术语 窗口：窗口：收发双方都要创建的内存缓冲区，收发双方都要创建的内存缓冲区，用以存放数据帧；并且对收到应答之前可用以存放数据帧；并且对收到应答之前可以传输的数据帧的数目进行限制。以传输的数据帧的数目进行限制。 窗口大小：窗口大小：一次最多发送的数据帧数目，一次最多发送的数据帧数目，设为设为n n帧数据，则帧数据，则数据帧以模数据帧以模n n方式进行编方式进行编号号（便于双方应答确认），即为（便于双方应答确认），即为0 0，1 1，2 2，n-1n-1，且，且窗口大小窗口大小n-1n-1不能涵盖所不能涵盖所有有n n帧数据（帧数据（n=2n=2

26、k k ，K K是序号的位数）。是序号的位数）。 如如n=8 n=8 则数据帧编号则数据帧编号0 0，1 1，2 2，3 3，4 4，5 5，6 6，7 7，0 0，1 1，2 2，3 3， 012345 6701232.发送窗口发送窗口321076543210这个边界每当这个边界每当发送发送1 1帧就向帧就向右移动右移动1 1帧帧当接收到应答帧后，这个边当接收到应答帧后，这个边界一次向右移动若干帧；界一次向右移动若干帧；移动的距离是最后一次ACK帧中的编号和现在收到的ACK帧的编号差值（模n）方向方向发送端发送端传输开始时，窗口中的内容就是要发送的数据帧。传输开始时，窗口中的内容就是要发送的

27、数据帧。每发送一帧数据之后窗口左边界向右移每发送一帧数据之后窗口左边界向右移1帧。帧。每收到一个确认帧后窗口右边界向右扩张若干帧：每收到一个确认帧后窗口右边界向右扩张若干帧：ACK N表示前面表示前面0，1，2，N-1累计累计N帧已经帧已经无损失地到达，可发送第无损失地到达，可发送第N帧以及其后的数据。帧以及其后的数据。因此：因此：当数据帧发送出去时，发送方滑动窗口从当数据帧发送出去时，发送方滑动窗口从左边开始收缩；当应答帧到来时，发送方滑动窗左边开始收缩；当应答帧到来时，发送方滑动窗口从右边开始扩张。口从右边开始扩张。3.接收窗口接收窗口321076543210这个边界每当这个边界每当接收接

28、收1 1帧就向帧就向右移动右移动1 1帧帧当发送一个应答帧（当发送一个应答帧（ACKACK）后，）后，这个边界一次向右移动若干这个边界一次向右移动若干帧；帧；移动的距离是最后一次ACK帧中的编号和当前的ACK帧的编号差值（模n）接收端接收端传输开始时，窗口中的内容是空，窗口大小传输开始时，窗口中的内容是空，窗口大小表示待接收数据缓冲单元的大小（即发送表示待接收数据缓冲单元的大小（即发送ACK帧前可接收数据帧数）帧前可接收数据帧数）每收到一个数据帧之后窗口左边就向右移一每收到一个数据帧之后窗口左边就向右移一帧。帧。 每确认发送一个应答信号（每确认发送一个应答信号（ACK）窗口就）窗口就可一次向右

29、移动若干帧；移动距离是最后一可一次向右移动若干帧；移动距离是最后一次次ACK帧中编号与当前帧中编号与当前ACK帧中编号的差值。帧中编号的差值。因此因此：当接收数据帧时，接收方滑动窗口从当接收数据帧时，接收方滑动窗口从左边开始收缩；当发送应答帧后，接收方滑左边开始收缩；当发送应答帧后，接收方滑动窗口从右边开始扩张。动窗口从右边开始扩张。4.实例：窗口滑动的动态过程实例：窗口滑动的动态过程0 1 2 3 4 5 6 7 0 1 2 3 4 5窗口：n=8帧 窗口大小：n-1=70 1 2 3 4 5 6 7 0 1 2 3 4 5Send 3(0-2) data frames0 1 2 3 4 5

30、 6 7 0 1 2 3 4 50 1 2 3 4 5 6 7 0 1 2 3 4 5Receive 3 data frames0 1 2 3 4 5 6 7 0 1 2 3 4 50 1 2 3 4 5 6 7 0 1 2 3 4 5Send ACK30 1 2 3 4 5 6 7 0 1 2 3 4 50 1 2 3 4 5 6 7 0 1 2 3 4 5ACK3Receive ACK30 1 2 3 4 5 6 7 0 1 2 3 4 50 1 2 3 4 5 6 7 0 1 2 3 4 5ACK3Send 3(3-4) data frames 0 1 2 3 4 5 6 7 0 1 2

31、 3 4 50 1 2 3 4 5 6 7 0 1 2 3 4 5Receive 2 data frames0 1 2 3 4 5 6 7 0 1 2 3 4 50 1 2 3 4 5 6 7 0 1 2 3 4 5Send ACK50 1 2 3 4 5 6 7 0 1 2 3 4 50 1 2 3 4 5 6 7 0 1 2 3 4 5ACK5Receive ACK55432107654321054321076543210已经发送的最后一帧已经确认的最后一帧ACK5SR已成功发出已成功发出的数据帧的数据帧将发出的数据帧将发出的数据帧已正确接收已正确接收的数据帧的数据帧将收到的数据帧将收到的

32、数据帧帧序号帧序号窗口后沿窗口后沿窗口前沿窗口前沿帧序号帧序号窗口后沿窗口后沿窗口前沿窗口前沿5.5.窗口大小的限制因素窗口大小的限制因素 即编号的限制是由帧中特设的即编号的限制是由帧中特设的序号字段序号字段来来决定。决定。 用用k bit长的字段来存放序号，则序号的范长的字段来存放序号，则序号的范围从围从0到到(2K-1)即模即模2K流量控制形式流量控制形式 上述（上述（n-1）大小的）大小的Slidingwindow要求要求接收方必须能容纳紧跟在最后一次确认帧接收方必须能容纳紧跟在最后一次确认帧后的（后的（n-1）帧）帧 切断对方帧流量方式切断对方帧流量方式：大多数协议通过引：大多数协议通

33、过引入入RNR报文帧来完全切断对方的帧流量，报文帧来完全切断对方的帧流量，此报文帧确认前面几个帧已正确接受，但此报文帧确认前面几个帧已正确接受，但禁止后续帧的发送；禁止后续帧的发送；RNR 6表示表示“第第0帧到帧到第第5帧共帧共6帧已正确接收但无法再接收任何帧已正确接收但无法再接收任何帧帧”，在此后任一时刻可通过，在此后任一时刻可通过接收方接收方发送发送一个正常一个正常ACK帧来重新启动滑动窗口。帧来重新启动滑动窗口。 Receive not ready双向信息传输：双向信息传输： 源站源站和和目的站目的站都要维护都要维护两个两个滑动窗口，滑动窗口，一一个用于发送，一个用于接收，且双方都要个用于发送，一个用于接收