第3章 差错控制技术.ppt

第3章 差错控制技术,3.1 差错控制的基本概念 3.2 流量控制方法 3.3 常用差错控制编码方法 3.4 常用差错控制方法 3.5差错控制的性能估算和应用,ch3 差错控制技术,必要性： 数据通信要求信息传输过程具有高度的可靠性即误码率足够低； 信号在传输过程中由于传输损耗（噪声，衰损，失真）不可避免要产生一些差错即出现误码。 大体上分为： 随机差错随机噪声 突发差错脉冲噪声,ch3 差错控制技术,解决的办法： 一是改善传输信道的电气特性（先进的物理设备要付出成本）提高传输可靠性； 另一种办法在相应的物理设备条件下采用计算机技术进行差错编码和控制，自动检测错误并在可能情况下纠正错误，这就是所谓的差错控制技术。,3.1 差错控制的基本概念,3.1.1 差错控制的基本概念 3.1.2 差错控制编码的特性和能力,3.1.1差错控制的基本概念,所谓差错即为误码；差错控制的核心是抗干扰编码，简称差错编码（属于二次编码即信道编码），它的基本思想是通过对信息序列作某种变换，使原来彼此独立、互不相关的信息码元产生某种规律性（相关性），从而在接收端根据这种规律性来检查，进而纠正传输信号序列中的差错。变换的方法不同就构成了不同的编码。,3.1.1差错控制的基本概念,1.信息码和监督码 2.差错控制的基本特点 3.差错控制的理论基础 4.差错控制编码的基本原理 5.差错控制实例 6.编码效率 7.差错编码的分类,1.信息码和监督码,信息码（元）：发送用户端欲发送的信息序列，本来彼此独立，互不相关；由用户控制，最终也交给接收用户。 监督码（元）:为了使信息码元产生某种规律性，可按照某种规则在用户信息序列中插入一定数量的新码元，这种新码元叫监督码（元）。 监督码元不受用户控制，最终也不交给接受用户。,9,插入监督码元的目的是使原来彼此独立、互不相关的信息码元产生某种规律性（相关性）从而使接收端能够根据这种规律性来检测传输过程是否有误。,2.差错控制的基本特点,引入差错编码控制后，实际传输的 信息序列=（信息码元+监督码元），称为码组。 在信道容量既定的情况下，信息传输速率有所降低，但信息传输的可靠性有所提高，既差错控制编码用降低通信系统信息传输的有效性的代价来提高信息传输的可靠性。,why?,同样的信息量要用更多的比特位！,3.差错控制的理论基础,差错编码的想法是否可行？ 有没有理论依据？,香农信道编码定理,香农信道编码定理 ：每个信道都具有确定的信道容量c，只要信息传输速率： rb（bps）=c则理论上就一定存在一种编码方式，使其译码差错概率pe满足： pe=a e-n e(rb) 式中 香农另一个定理: 通信系统极限传输速率,n码字长度（码长） e（rb）误差指数（当rb0） a正系数 penen误码率是指二进制码元在数据传输系统中被传错的概率 ；n为传输的二进制码元总数， ne为被传错的码元数。,香农信道编码定理,e（rb）与rb的关系如图所示：,c 使e(rb ) 或 n 使e-ne(rb ) ,可见要使pe满足要求： 一是增加信道容量c，从而使e（rb ）增加（通信硬件系统设计人员通常采用的方法）； 另一种方法是只要rb=c增加码长n 可使pe随n的增加而指数下降，如果n则pe 香农信道编码定理是差错控制编码的理论基础，通过编译码过程来降低误码率。,香农信道编码定理,从而差错控制编码的基本原理就是：在保持信息位数不变（信息码元）情况下，采用增加码长的方法来降低误码率。,4.差错控制编码的基本原理,5.差错控制实例,信源发出的任何消息通过信源编码表达成二进制信号“0”和“1”的形式。, sourcedestination传输a和b两个消息。 用一位二进制数表示：“0”a；“1”b 传输过程中出现错码，接收端无从发现，无检错和纠错能力。,用两位二进制数：“00”a “11”b 称为许用码组 “01”和“10”未定义，称为禁用码组。 s：00 d：00 01 10 s: 11 d： 11 ,表示附加一位监督码以后码组具有了检测1位错码，但因译码器不能判别哪位是错码，不具备纠正错码的能力；且无法检测错2位错码。,差错控制实例,用三位二进制数: 000”a “111”b 称为许用码组 “001” “010” “011” “100” “101” “110” 皆是禁用码组,s：000 d：000 001 010 011 100 101 110 111,差错控制实例,表明附加两个码元（监督码）以后码组具备检测1位和2位错码的能力；并且可根据“大数”规则来纠正一个错误，即3位码组中有2个或3个“0”/“1”码，则判为“000”/“111”。此时具备纠正一位错码的能力；但无法纠正两位出错和检测3位出错的 总结：（信息码+监督码=码组）构成的信息序列通过降低信息传输速率来提高传输的可靠性（降低误码率）。,差错控制实例,6.编码效率,编码效率：指信息码在码组中所占的比重。 假定n=k（信息码长）+r（监督码长），用r表示编码效率 r=k/n=k/（k+r） r 传输有效 n pe 可靠性 编码方案 传输速度,矛盾！ tradeoff!,ff,7.差错编码的分类,(1)按码组的功能分为检错码和纠错码：检错码能在译码器上发现错误，但不能自动纠正错误，纠错码不仅能在译码器上发现错误，而且能自动纠正错误，它是我们最重要的抗干扰码。 (2)按码组监督码元与信息码元之间的关系分线性码和非线性码两类:所谓线性码是指监督码和信息码之间的关系是线性关系实际运算的大都是线性码。,差错编码的分类,(3)按码组中监督码元与信息码元的约束关系，又分为分组码和卷积码两类： 所谓分组码将k个信息码元划为一组，然后由这k个码元按照一定的规则产生r个监督码元，从而组成n=k+r的码组；在分组码中，监督码元仅监督本码组中的信息码元。分组码用（n，k）表示，并且将其结构规定为：,差错编码的分类,an-1,an-2.ar ar-1,a1,a0 信息码（k） 监督码（r） n=k+r,差错编码的分类,卷积码中，每组的监督码元不但与本组码的信息码元有关而且还与前面若干组信息码元有关；即不是分组监督，而是每个监督码元对它的前后码元都实行监督，前后相连。=连环码。,差错编码的分类,(4)按照纠正错误的类型可分为纠正随机错误的码和纠正突发错误的码。 (5)按照每个码元取值来分二进制码和多进制码。,3.1.2 差错控制编码的特性和能力,1.海明（hamming）距离 2.最小距离 3.海明距离（码距） 4.最小距离与抗干扰能力的关系,1.海明（hamming）距离,1.海明（hamming）距离：指两个不同的码组其对应码位（二进制位）的码元不同的个数，简称码距 ；用d表示：,式中表示模2加（异或） n表示码组长度 aki和aji表示第k个码组和第j个码组的第i位码元,例： （1011）和（0100）两码组间距离：d= （10110100）=4 （00）和（00）两码组间码距：d=0 （01）和（11）两码组间距离：d=1 （001）和（100）两码组间距离：d=2 （101）和（010）两码组间距离：d=3,海明（hamming）距离实例,2.最小距离：一个码组集合中，任何两个码组间海明距离(即码距)的最小值称为码组集合的最小距离。用d0或dmin表示:,式中表示模2加 n表示码组长度 aki和aji表示第k个码组和第j个码组的第i位码元 min表示最小值,2.最小距离,举例： 码组集合（000）（001）（010）（011）（100）（101）（110）（111） d0=1 没有检错能力。 码组集合（000）（011）（101）（110） d0=2 能检测出1位码位出错。 码组集合（000）（111） d0=3 能检测出2位出错并能纠正1位错误。,最小距离实例,如果8种码组都作为许用码组，任两个码距间的最小距离为1，记dmin =1; 如果4种码组(000 011 101 110)作为许用码组，任两个码距间的最小距离为2，记dmin =2; 如果2种码组作为许用码组(000 111)，任两个码距间的最小距离为3，记dmin =3;,所以码组集合中最小距离越大，其抗干扰能力（包括检错和纠错能力）越强。,3.海明距离（码距）,3.海明距离（码距）就是从一个顶点移动到另一个顶点所经历立方体的最少边数； 则所谓最小距离就是立方体中从一个顶点移到另一个顶点所经历的最少边数 。,4.最小距离与抗干扰能力的关系,定理3.1若一种码的最小距离为d0，则它能检查传输错误个数（检错能力）e应满足：d0=e+1 定理3.2若一种码的最小距离为d0，则它能纠正传输错误个数（纠错能力）t应满足：d0=2t+1 定理3.3若一种码的最小距离为d0，则它的检错能力和纠错能力应满足：d0=e+t+1 （e=t）,例3.1 求码集合(000),(011),(101),(110)和(000),(111)最小距离d0及纠（检）错的能力。,实例（p53）,解：最小距离,实例,检错和纠错能力 第一组：d0=2，e=d0 1=1，可检测出一个错，（定理1） 第二组： d0 =3 e=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 流量控制,1.流量控制是为了确保发送端发送的数据不会超出接收端接收数据能力的一种技术，即避免接收端缓冲区不够用的情况，它是数据由数据链路层（低层）交给网络层（高层）的中转站。,发送方从高层获取的数据在传输之前、接收方将接收到的数据在提交给高层之前一般都要用一个缓冲区来暂存。,2.流量控制模型,3.常用流量控制方式,停止等待(stopandwait)流量控制方式:一次发送一帧 滑动窗口(slidingwindow)流量控制方式：一次发送若干帧。,3.2 流量控制,3.2.1 停止等待流量控制 3.2.2 滑动窗口流量控制,3.2.1 停止等待流量控制,在停止等待流量控制协议中： 发送方每发送一帧后就等待来自接收方的一个应答帧（帧=数据+控制信息）； 接收方收到数据后回送应答帧（ack/nak）； if ack then发送下一帧 else（nak）重发原来的帧； 发送和等待过程不断重复，直到发送端发送一个结束帧（eot）为止。,acknowledge negative acknowledge,end of transmission, 停止等待协议流量控制模型,i=0 or1,工作过程： sendreceive/ack(nak)resend结束 if接收方对eot帧回送应答帧 then终止传输。 报文（来自网络层）控制： 小报文 大报文：分块变成小的数据块，解决接收缓冲区容量有限/传输延迟问题 控制特点： 每一帧（每次只能传输一帧）数据都要确认和检验 效率低，速度慢，不适合实时系统。,3.2.2 滑动窗口流量控制,在停止等待流量控制协议中：每次只允许传送一帧； 在滑动窗口流量控制协议中：允许一次传送多帧，从而大大提高效率。 发送方在收到应答信息前可以发送若干帧，帧可以直接依次发送； 接收方只对一些帧进行应答确认，使用一个确认帧（应答帧ack/nak）对多个数据帧的接收进行确认；当接收端发出一个ack信号，它就在其中包含了预期接收的下一帧编号。 使得slidingwindow依次传输多个帧,3.2.2 滑动窗口流量控制,1.基本术语 2.发送窗口 3.接收窗口 4.实例：窗口滑动的动态过程 5.窗口大小的限制因素,1.基本术语,窗口：收发双方都要创建的内存缓冲区，用以存放数据帧；并且对收到应答之前可以传输的数据帧的数目进行限制。 窗口大小：一次最多发送的数据帧数目，设为n帧数据，则数据帧以模n方式进行编号（便于双方应答确认），即为0，1，2，n-1，且窗口大小n-1不能涵盖所有n帧数据（n=2k ，k是序号的位数）。,如n=8 则数据帧编号0，1，2，3，4，5，6，7，0，1，2，3，,2.发送窗口,发送端,传输开始时，窗口中的内容就是要发送的数据帧。 每发送一帧数据之后窗口左边界向右移1帧。 每收到一个确认帧后窗口右边界向右扩张若干帧：ack k表示前面0，1，2，k-1累计k帧已经无损失地到达，可发送第n帧以及其后的数据。 因此：当数据帧发送出去时，发送方滑动窗口从左边开始收缩；当应答帧到来时，发送方滑动窗口从右边开始扩张。,3.接收窗口,接收端,传输开始时，窗口中的内容是空，窗口大小表示待接收数据缓冲单元的大小（即发送ack帧前可接收数据帧数） 每收到一个数据帧之后窗口左边就向右移一帧。 每确认发送一个应答信号（ack）窗口就可一次向右移动若干帧；移动距离是最后一次ack帧中编号与当前ack帧中编号的差值。 因此：当接收数据帧时，接收方滑动窗口从左边开始收缩；当发送应答帧后，接收方滑动窗口从右边开始扩张。,4.实例：窗口滑动的动态过程,窗口：n=8帧 窗口大小：n-1=7,send 3(0-2) data frames,receive 3 data frames,send ack3,receive ack3,send 3(3-4) data frames,receive 2 data frames,send ack5,ack5,receive ack5,5.窗口大小的限制因素,即编号的限制是由帧中特设的序号字段来决定。 用k bit长的字段来存放序号，则序号的范围从0到(2k-1)即模2k,流量控制形式,上述（n-1）大小的slidingwindow要求接收方必须能容纳紧跟在最后一次确认帧后的（n-1）帧 切断对方帧流量方式：大多数协议通过引入rnr报文帧来完全切断对方的帧流量，此报文帧确认前面几个帧已正确接受，但禁止后续帧的发送；rnr 6表示“第0帧到第5帧共6帧已正确接收但无法再接收任何帧”，在此后任一时刻可通过接收方发送一个正常ack帧来重新启动滑动窗口。,receive not ready,双向信息传输：,源站和目的站都要维护两个滑动窗口，一个用于发送，一个用于接收，且双方都要向对方发送数据帧和确认帧；为提高效率，采用了一种“捎带技术”即每个数据帧除了开辟一个存放帧序号字段之外，还增加一个用存放确认序号的字段，这两个字段放在一个数据帧同时发送