ch3(3)-常用差错控制方法

1、3.4差错控制方法 3.4差错控制方法 3.4.1自动请求重发(ARQ) 1. 停止等待ARQ 2.返回N帧（Go-Back-N）ARQ 3.选择性重发ARQ 3.4.2 前向纠错控制方法（FEC） 3.4.3 混合纠错控制方法（HEC) 3.4.4 信息反馈 3.4.5 其它差错控制方式3.5 差错控制的性能估算和应用1利用我们前面介绍的抗干扰编码（或叫差错控制编码）来控制传输系统的传输差错的方法，称为差错控制。根据抗干扰编码结构的不同和利用抗干扰编码控制差错的方法不同形成了不同的差错控制工作方式。2差错控制的两种基本思想：一是通过差错编码，使得接收端译码器能发现错误并准确地判断差错的位置从

2、而自动纠正它们。 另一个就是在接收端能够发现错误但无法自动纠错，请求发送端重发数据等方式来达到纠正错误的目的。3按照这种基本思想，在数据通信中，利用差错控制编码进行系统传输的差错控制的工作方式可分为四类：自动请求重发（ARQ），前向纠错（FEC），混合纠错（HEC）和信息反馈（IRQ），另外还有诸如像冗余法，多数表决法（重复编码）等，下面分别加以介绍。ARQ Auto Request for RetransmissionFEC Forward Error CorrectionHEC Hybrid Error CorrectionIRQ Information Repetition Reques

3、t差错控制方式分类43.4.1 ARQ: 自动请求重发又称反馈重发发送端首先对发送序列（信息码）进行差错编码，生成一个可以检测出错误的校验序列（监督码），然后连同数据一起发送出去； 接收端根据校验序列的编码规则判决是否出错，并把判决结果通过反馈通道传回给发送端： 5(1)ARQ传输差错处理方法通常处理传输差错的办法如下：肯定确认：接收端收到一个帧后未发现错误，回送一个确认信号，用ACK表示。否定确认：用NAK表示。超时重发(Overtime)：发送端发出一个帧后开始计时，如果在规定的时间内没有收到确认信号（ACK或NAK），则认为发生帧丢失的或确认信号丢失。必须重发。SourceDestina

4、tionACKNAKOvertime6(2)ARQ技术ARQ技术结合流量控制又分为三种形式：1.停止等待ARQ (Stop_and_Wait)2.返回N帧ARQ (Go_back_N)3.选择重发ARQ (Selective_Retransmit)73.4.1 ARQ: 自动请求重发1.停止-等待ARQ2.返回N帧（Go-Back-N）ARQ3.选择性重发ARQ81.停止-等待ARQ(1)基本概念：这是一种结合停止-等待流量控制技术的ARQ技术。发送端：发送一帧数据 等待确认（ACK/NAK） 重发上一帧或发送下一帧数据获得ACK之前，发送端必须备份已发送的一帧数据Timer: avoid D

5、eadlock frame lost接收端：等待接收数据，并校验正确，将接收到的数据帧上交网络层并回送ACK错误，丢弃接收到的数据帧并回送NAK91.停止-等待ARQ细节Deadlock: TimerRepeated data frame: add NO. field in the data frameGive up frame: data frame / ACK、NAK101.停止-等待ARQ状态序号：收发双方都维持一个状态序号，用来记录链路上期待正确接收、确认的帧序号(2)操作要点(P72)：初始化：将收发两端状态序号初始化为0状态序号通过1bit的数据来维持即可（序号非0即1）发送端：每

6、送出一个数据帧（数据帧的序号非零即1，第一个数据帧序号为0），将其序号写入本地状态序号（设用V(s)表示）中。 111.停止-等待ARQ（两者一至如何，两者不一至如何？）答：若两者一致，则说明是新的数据帧。应该回送确认帧。并且更新本地状态序号，准备接收下一个数据帧。若发现不一致，则说明是重复帧，应该丢弃之，并且不改变状态序号的值，但仍需向发送端回送一个确认帧。而帧的序号应该为刚才收到的数据帧的序号。121.停止-等待ARQ发送端：每收到一个确认帧，将其序号与本地的状态序号相比较。（两者一至如何，两者不一至如何？）答：若两者一至，则说明传输正确，可以发送新的一数据帧，并更新本地状态序号；准备接收

7、下一数据帧。若发现不一至，说明是重复的确认帧，只需丢弃即可，继续等待所期望的确认帧。总结：发送端的状态序号值等于刚发送完的数据帧的序号；而接收端的状态序号表示当前期望接收的数据帧的序号。13链路数据传输过程：正常14链路数据传输过程：数据帧出错15链路数据传输过程：数据帧丢失16链路数据传输过程：确认帧丢失17停-等ARQ的算法流程SGet 1st Data from Network LayerV(s) = 0N(s)= V(s)Save Data Frame to BufferSend Buffered Data Frame to Physical LayerStart TimerWait

8、EventReceived ACKReceived NAKTime OutGet Next Data V(s) = 1-V(s)RV(r) = 0Wait Data FrameReceived Frame, and Test if Error occursCorrectErrorN(s) = V(r) ?Discard FramePass Data toNetwok Layer Send ACKSend NAKSend ACKV(r)= 1-V(r)N(s)表示数据帧序号NY18连续重发请求ARQ为了减小占空比，提高传输效率，人们又提出了连续重发请求（continuous ARQ）的方法，这是

9、一种结合滑动窗口流量控制技术的方法。连续重发请求,不等前帧确认便发下一帧，即连续发送数据帧，将等待确认时间利用起来，从而大大提高传输效率。 19连续重发请求ARQ为了保证接收端的数据链路层按照发送的顺序将数据帧提交给上层（网络层），接收端对后继的正确帧的处理方式决定了发送端重发错误帧的方法。返回N帧（Go-Back-N）ARQ: GBN选择性重发ARQ(Selective Repeat): SR连续重发请求，能够提高传输效率，但是在实现上相应需要更大的缓冲区（存贮空间，Buffer）202.返回N帧（Go-Back-N）ARQ(1)基本想法： 连续发送data frame if有错,则回退N帧

10、连续发送data frame（重发所有其它帧，不管它是否正确接收） (2)缓冲区大小：发送端：需要一个能存储N个数据帧的缓冲区（重发表），以便随时准备重发。接收端：对检测出有错的那个数据帧之后的N-1帧，不论正确与否都一律丢弃，故只需能够存储一个数据帧的缓冲区即可（仅当在没有考虑流量控制的情况可以这样！）。21（3）返回N帧ARQ示意图12345678934567891011121378910123456789345678910111213ACK1ACK2NAK3回退N帧重传NAK4NAK5NAK6NAK7NAK8NAK9ACK3ACK4ACK5ACK6NAK7回退N帧重传提交网络层提交网络层

11、丢弃丢弃接收端发送端22回退N帧：N=滑动窗口大小发送端:每收到ACK帧，继续发送新数据每收到NAK帧，回退N帧，即重发出错帧以及其后发送的 N-1 帧数据（不管它们是否正确）23（4）传输过程数据帧和确认帧都正常数据帧出错（丢失），返回NAK（启动Timer）回退N帧数据帧正确而确认帧出现错误 ：后继收到的确认帧为ACK后继收到的确认帧为NAK24（5）返回N帧ARQ操作要点(1)数据帧和确认帧都正常：不出现差错或丢失（1）发送端连续发送数据帧而不等待确认帧，直到收到第一帧的确认帧为止决定下一步操作（2）发送端在重发表中保存N个数据帧的备份（3）重发表按FIFO规则操作（4）接收端对每一个正

12、确接收到的数据帧返回一个确认(ACK)帧25（5）每一个数据帧包含一个唯一的序号（6）接收端保存一个接收序列表，保存最后正确接收到一帧数据（7）当一收到相应数据帧的确认(ACK)帧，发送端从重发表重删除该数据帧26(2)数据帧出错（帧受损坏、丢失）：（1）假设第 N+1 帧数据出错（2）接收端立即返回 NAK(N+1)，指出最后正确接收到的是第 N 帧（3）接收端同时清除其后的其它数据帧，直到收到正确的第(N+1)帧（4）为避免死锁（ACK/NAK丢失），一般发送端在发送一帧数据的同时启动定时器27（5）一旦正确收到第(N+1)帧，接收端就继续正常工作（6）发送端可以接收确认、否认帧（ACK/

13、NAK）ACK：继续发送后继帧NAK：回退N帧重发28(3)数据帧正确而确认帧出现错误 ：发送端收到后继的肯定应答帧ACKACK(N) ACK(N+1)error or lostBut the sender can receive ACK(N+2), So the sender can acknowledge Nth and (N+1)th frame; That is to say that ACK frame can accumulate his acknowledging functions. After this, the sender can continue to work.为什么

14、接收端必须对每一个正确接收的数据帧都为ACK？? ?29发送端收到后继的否定应答帧NAK发送端收到 NAK(N+1)，这时可以从重发表中看到应该确认的数据帧是第N帧，所以发现失序，必须回退并从第N帧起开始重发。问题一：假设丢失或出错的确认帧本来就是NAK(N)，接收端继续正常工作。问题二：假设丢失或出错的确认帧本来是ACK(N)，接收端会收到重复的第N帧数据，不能正常工作；解决办法：本地状态序号与帧序号相比较30(6)Go_Back_N中的状态序号The functions of the state number are nearly same in the Go_Back_ N and St

15、op_and _Wait error-controlling methods;But their operations are not same.LN_R, LN_S 表示收、发双方的状态序号TN_R , TN_S 表示收、发双方传输的数据帧序号在Go_Back_ N 方案中，帧序号需要log2N比特来维持，状态序号与帧序号的取值区间完全相同。假定序号为TN_S=1的数据帧出错，因而该数据帧被接收端丢弃。31Go_Back_N中的状态序号因为TN_S=1的数据帧未被正确接收，所以LN_R不增加，并给发送端回送NAK(TN_R=1)帧。当收到TN_S= 2的数据帧，因为LN_R不等于TN_S，所

16、以接收端将此帧丢失，并给发送端返回一个NAK(TN_R=2)帧。发送端收到NAK(TN_R=2)帧，立即发现重发表中显然有两个未被确认的数据帧，即TN_S=1和TN_S=2的两个帧，因此将此两帧重发。若从LN_S=1的角度来看，同样说明原来TN_S=1的数据帧未被确认，应该回退到此帧开始重发。32RV(r) = 0Wait Data FrameReceived Frame, and Test if Error occursCorrectErrorN(s) = V(r) ?Discard FramePass Data toNetwok Layer Send ACKSend NAKSend ACK

17、V(r)= (V(r)+1)%MAX(7)连续ARQ的算法流程SGet !st Data from Network LayerV(s) = 0N(s)= V(s)Save Date Frame to BufferSend Buffered Data Frame to Physical LayerStart TimerWait EventReceived ACKReceived NAKTime OutGet Next Data V(s) = (V(s)+1)%MAXGBNN33(8)返回N帧ARQ存在问题返回N帧ARQ因连续发送数据帧而提高传输效率。发送端要维持和滑动窗口一样大小的缓冲区，备份已

18、发送的数据；并且重发时不管出错数据帧其后的数据帧是否有错，一律重发，使传输效率降低。通信链路较差、误码率较大时，go_back_N就不一定优于stop_and_wait另外在长传播延时链路上go_back_N传输效率也较低。343.选择性重发ARQ在返回N帧ARQ的基础上改进而来，也是一种ARQ连续方案。 发送端连续发送数据帧接收端接收确认：ACK(N)连续发送NAK(N)发送端根据NAK（N）中N确认重发出错帧；即对重发帧有个选择，避免对后继正确数据帧的多余重发，较返回N帧方案效率有明显提高。35（1）选择性重发ARQ示意图1234567893101161213141516176121814

19、1234567893101161213141516176ACK1ACK2NAK3ACK4ACK5NAK6ACK7ACK8ACK9ACK3ACK10NAK6ACK11重传与4、5号帧一起提交网络层提交网络层暂存与缓冲区中暂存与缓冲区中重传NAK12ACK13NAK14ACK15ACK16ACK17ACK6与711号帧一起提交网络层重传重传36（2）选择性重发ARQ存在问题选择性重发ARQ在效率上获得的增加，是以复杂的接收控制机制和巨大的缓冲容量为代价的。在链路较差以致较多出现多个错和单个数据帧连续出错的情况下，重发帧和接收帧的缓存提取以及接收后的排序问题都比较复杂。37(3)GBN & SR控制

20、技术比较Go_Back_N ARQ :发送方需要较大的缓冲区，以便重传适于信道出错率较少的情况Selective Repeat ARQ接收方也需要较大的缓冲区，以便按正确顺序将分组提交网络层适于信道质量不好的情况38选择重发ARQ与回退N帧ARQ之间的区别：（1）接收设备必需有排序的逻辑功能，以便与对接收的帧进行排序。同时，在发送了NAK帧后，还必需有存储所接收的帧的功能，直到损坏了的帧被替换。（2）发送设备必需具有查找机制，以便帮助它发现和选择只需要重传的帧。39（3）为了有助于选择ACK的编号，和NAK的编号一样，必需指明所接收的（或丢失的）那一帧，而不是所期待的那一帧。（4）选择重发AR

21、Q所要求的窗口大小比与回退N帧ARQ要小，此时才能有效地工作。推荐选择重发ARQ窗口的大小为小于或等于（n+1）/2，而回退N帧ARQ的大小为n-1。40ARQ技术的主要特点ARQ要求有反馈回路，系统需采用双工通讯方式控制规程和过程较复杂，但与FEC相比复杂性和成本要低的多反馈重传，效率较低，信息随机接收；不适合于实时传输系统 41 3.4.2 前向纠错控制方法（FEC）发送端逐行纠错编码，码组冗余度大具有自动纠错能力，然后发送这种能纠错的码接收端译码并自动纠正传输差错传输过程： S 可纠错码D特点：a 无反馈过程，可采用单工通讯b 传输系统延时小，实时性强c 纠错码，编码冗余度大，传输效率有

22、所下降d 控制规程简单，但编译码设备较复杂。 423.4.3混合纠错控制方法（HEC ）基本做法：HEC将ARQ和FEC方式结合起来，发送端发送不仅能检测错误，而且能够在一定程度内纠正错误的编码；接收端译码器收到码组后，首先检测传输是否有错，if有错，且差错在码组纠错能力以内自动纠错，否则请求发送器重发。传输过程： 能纠错就纠错，不能纠就重发技术特点： a 降低FEC编译码的复杂性b 提高ARQ方式信息连贯性 433.4.4 信息反馈信息反馈（Information Repeat Request，IRQ）方式，也称为回程校验方式，在发送端检测错误 传输过程： 接收端接收数据保存并原样返回 发送

23、端检测是否有错,如有错，重传；无错，继续传送下一帧。 44信息反馈技术特点： a 无需差错编码 ，信息冗余度小； b 需要反馈回路；c 发送端检错，信息传输距离加大一倍，因而可能导致额外的差错和重传；d系统发、收端均需较大容量的存储器来存储传输信息，以备检错和输出。 e传输率很低 ,很少应用。453.4.5 其它差错控制方式冗余法：Data frame 发送两份copy，接受端判断这两份copy是否一致。多数表决法：重复码接收端判决正确次数大于传错的次数即可例如发送数据：10110010（1）逐位重复：111 000 111 111 000 000 111 000（2）分段重复：1011 10

24、11 1011 0010 0010 0010（3）信息块（frame）：10110 10110010正反码： 463.5 差错控制的性能估算和应用1.性能估算方法：二元对称信道：是指传输信息只有1和0两种可能的信道，设两种信息传错的概率相同均为p，传对的概率为q=1-p11001-P1-PPP：传错的概率1P：传对的概率47例3.8 重复码设n次重复码的长度为n，当差错位数m(n+1)/2时，解码就发生错误，通常比特差错率p 1，故差错超过的部分可忽略不计，于是重复码的差错率为 48例3.9 (2,1)连环码3.3.5节所介绍(2,1)的连环码，能纠正一位差错，束缚长度为2位，故当连续4位中出现2位以上差错时，解码就出错。因此，它的差错率近似为49例3.10 奇偶校验码奇偶监督码只能发现奇数个差错，不能发现偶数个差错，下面计算它不能发现差错的概率。显然，这是计算偶数个差错的概率，通常p 1，出现两个差错的概率要比出现四个、六个等的差错的概率大得多，故不能发现的差错概率主要由出现两个差错的概率所决定。按式（3.16 )50例3.4