第八章 差错控制编码要点ppt课件.ppt

《第八章 差错控制编码要点ppt课件.ppt》由会员分享，可在线阅读，更多相关《第八章 差错控制编码要点ppt课件.ppt（127页珍藏版）》请在三一办公上搜索。

1、第8章 差错控制技术,8.1 差错控制的基本概念8.2 流量控制方法8.3 常用差错控制编码方法8.4 常用差错控制方法8.5 差错控制的性能估算和应用,必要性：数据通信要求信息传输过程具有高度的可靠性即误码率足够低；然而信号在传输过程中由于传输损耗（噪声，衰损，失真）不可避免要产生一些差错即出现误码。大体上分为：随机差错：由信道的加性随机噪声引起的差错 突发差错：某一段时间内出现一连串的差错 混合差错：既有随机差错又有突发差错,差错控制的基本概念,所谓差错即为误码；差错控制的核心是抗干扰编码，简称差错编码。基本思想：是通过对信息序列作某种变换，使原来彼此独立、互不相关的信息码元产生某种规律性

2、（相关性），从而在接收端根据这种规律性来检查，进而纠正传输信号序列中的差错。变换的方法不同就构成了不同的编码，即信道编码,差错控制的基本概念,通俗地讲，差错控制方法：对要传送的二进制数字信息中增加一些附加的信息，通过增加冗余度使得原来的信息可以检错或纠错。一般来讲，加入的冗余度越多，检错纠错能力（即差错控制能力）越强，传输效率越低。,1.信息码和监督码,信息码（元）：发送用户端欲发送的信息序列。监督码（元）:为了使信息码元产生某种规律性，可按照某种规则在用户信息序列中插入一定数量的新码元，这种新码元叫监督码（元）。信号在交到用户之前应当去掉监督码元。,7,插入监督码元的目的是使原来彼此独立、互

3、不相关的信息码元产生某种规律性（相关性）从而使接收端能够根据这种规律性来检测传输过程是否有误。,2.差错控制的基本特点,引入差错编码控制后，实际传输的 信息序列=（信息码元+监督码元），称为码组。在信道容量既定的情况下，信息传输效率有所降低，但信息传输的可靠性有所提高，既差错控制编码用降低传输效率的代价来提高传输的可靠性。,Why?,同样的信息量要用更多的比特位！,3.差错控制的理论基础,差错编码的想法是否可行？有没有理论依据？,香农信道编码定理,香农信道编码定理：每个信道都具有确定的信道容量C，只要信息传输速率：Rb（bps）=C则理论上就一定存在一种编码方式，使其译码差错概率（即误码率）P

4、e满足：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 香农信道编码定理是差错控制编码的理论基础，通过编译码过程来降低误码率。,香农信道编码定理,从而差错控制编

5、码的基本原理就是：在保持信息位数不变（信息码元）情况下，采用增加码长的方法来降低误码率。,4.差错控制编码的基本原理,5.差错控制实例,信源发出的任何消息通过信源编码表达成二进制信号“0”和“1”的形式。,SourceDestination传输A和B两个消息。,总结：（信息码+监督码=码组）构成的信息序列通过降低信息传输效率来提高传输的可靠性。,差错控制实例,6.编码效率,编码效率：指信息码在码组中所占的比重。假定n=k（信息码长）+r（监督码长），用R表示编码效率=k/n=k/（k+r）当n Pe 可靠性,矛盾！tradeoff!,二 差错控制编码的特性和能力,1.海明（hamming）距离

6、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）距离实例,几何表示：用3位码元构成的8个码组表示

7、立方体中各个顶点；,海明距离（码距）：就是从一个顶点移动到另一个顶点所经历立方体的最少边数；,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、最小距离实例,如果8种码组都作为许用码组，任两个码距间的最小距离为1，记dmin=1;如果4种码组(000 011 101 110)作为许用码组，任两个码距间的最小距离为2，记dmin=2;如果2种码组作为许用码组(000 111)，任两个码距间的最小距离为3，记dmin=3;,所以码组集合中最小距离越大，其抗干扰能力（包括检错和纠错能力）越强。,4.最小距离与抗干扰能力的关系,定理3.1若一种码的最小距离为d0，则它能检查传输错误个数（检错能力）e应满足：d0=e+1定理3.2若一种码的最小距离为d0，则它能纠正传输错误个数（纠错能力）t应满足：d0=2t+1定理3.3若一种码的最小距离为d

9、0，则它的检错能力和纠错能力应满足：d0=e+t+1（e=t）,例3.1 求码集合(000),(011),(101),(110)和(000),(111)最小距离d0及纠（检）错的能力。,实例（P58）,解：最小距离,实 例,检错和纠错能力第一组：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）,三 常用差错控制编码方法,1 奇偶校验编码2 方阵校验码3 恒比码4 正反码5 循环冗余校验编码（CRC）6 卷

10、积码,差错控制的核心就是抗干扰编码，为了提高通信系统的检错和纠错能力，人们创造出许多差错控制编码，比较常用的有奇偶校验编码、循环冗余校验编码、卷积码等。,奇偶校验编码,编码规则：发送端，将所要传输的数据码元分组，在分组数据后面加一位监督码（校验位），使得该组码连同监督码在内的码组中“1”的个数为奇数（奇校验）或偶数（偶校验）。接收端，按照编码规则检查如果发现不符，就说明产生差错，但不能明确差错的具体位置即不能纠错。,公式表示：设码组长度为n，表示为（an-1,an-2,a1,c0）其中前n-1位为信息位，第n位c0为监督位奇校验：an-1an-2a1c0=1即c0=an-1an-2a11偶校验

11、：an-1an-2a1c0=0 即c0=an-1an-2a1,奇偶校验编码,实例,写出下列二进制序列的偶校验码：1001110 0101111,写出下列二进制序列的奇校验码：1100101 0110010,10011100,01011111,11001011,01100100,特点：无论信息位为多少位，监督位只有一位。只能检测信息码组中奇数个错误，对偶数个错误无能为力；,奇偶校验编码,水平奇偶校验,避免简单奇偶校验不能检测突发错误的缺点。编码规则：经过奇偶监督编码的码元序列按行排成方阵，每一行为一组奇偶监督码(见实例)。发送端在发送时则按列的顺序传输；而接收端仍将码元恢复成发送时方阵形式，然后

12、按行进行奇偶校验水平奇偶监督码。,实例,发送端在发送时则按列的顺序传输：,11101 11001 10000 01010 00111,特点：发送端是按列发送码元，而不是按码组（行）发送码元，因此可把本来可能集中发生在一码组中的突发错误分散到方阵中的各个码组，同时又作为整个方阵的行监督；可以发现某一行上所有奇数个错误及长度不大于方阵行数的突发错误。,方阵校验码,又称行列监督码，矩阵码，纵向冗余校验码（LRC，Lognitudinal Redundancy Check），它的码元受到行和列两个方向奇偶监督，又称二维奇偶校验码。编码规则：使的每个码元受到纵向（列）和横向两次监督；将欲发送的信息码按行

13、排成一个矩阵，每行的最后加上一个奇偶监督码元；在每列最后也加上一个监督码元，进行奇偶校验；最后按行或列码组的顺序发送。,XXXXXXXX X XXXXXXXXXXXX X X XXXXXXXXX X XXXXXXX,方阵校验码结构,实例,发送端在发送时则按列(或行）的顺序传输：111010 110011 100001 010100 001111接收端仍将码元恢复成发送时方阵形式，然后按行、列进行奇偶校验,列监督码元,特点：可以检测出某行某列上的奇数个错误和长度不大于行（列）数的突发错误。可以检测出某行或某列上偶数个错误不能纠正差错数正好是4的倍数且位置在行列矩阵/子矩阵的4个顶点上的差错,方阵

14、校验码,失效！,恒比码(定比码),编码规则：恒比码中每码组中“1”和“0”个数保持恒定比例，接收端在检测接收到的码组中“1”的数目是否对就知道是否出错。实例：我国电传机传输汉字时使用数字代表汉字，采用的所谓“保护电码”就是一种“3：2”或“5中取3”的恒比码。C52=10个许用码组英文电报采用“7中取3”或“4：3”恒比码，共有C73=35个许用码组,正 反 码,多用于10单位电码的前向自动纠错设备中，能纠正一位差错，发现大部分两位错。n=k+r 且 k=r=51.编码规则：(1)当信息码中“1”的个数为奇数时，监督码与信息码相同（正码）10101 10101(2)当信息码中“1”的个数为偶数

15、时，监督码与信息码相反（反码）10100 01011,2.解码方法：(1)将接收到信息码与监督码按相应的码位模2加（异或），得到一个新的5位码组。(2)根据接收到的信息码中“1”的个数：if“1”的个数为奇数，则取新5位码组为校验码组if“1”的个数为偶数，则取新5位码组的反码为校验码组,正 反 码,正反码判决表,（3），最后可按下表，根据检验码组中“1”的个数进行判断及纠正可能发现的错码,实例：,已知信息码11010使用正反码差错控制方式，试问下列接收端收到的数据是否有错？能否纠正？11010 11010 10010 11010 11010 01010 10000 11010,（1）编码：1

16、1010（信息码）11010（监督码）11010 11010（正反码）（2）解码：接收端11010 11010 接收端10010 11010 接收端11010 01010 接收端10000 11010判断：,11010+11010 00000 结果为0，正确。,10010+11010 01000由于接收信息码中为偶数个1，所以检验码取反，10111，信息码中有一位出错，根据判决2，出错位置就是检验码组中0所对应的位置，纠正后为11010,11010+01010 10000由于接收信息码中为奇数个1，所以检验码不变，根据判决3，监督码码中有一位出错，出错位置就是检验码组中1所对应的位置，纠正后为

17、11010,10000+01010 01010检验码中1的个数1，根据判决4，无法判断和纠错,前面奇偶校验对一个字符校验一次，适合异步通讯；而CRC对一个数据块（frame）校验一次，适合同步通讯。在串行同步通信中，几乎都使用这种校验方法。如磁盘信息的读/写等。,循环冗余校验编码（CRC）,循环冗余校验编码（CRC）,Cyclic Redundancy checking(CRC)循环冗余校验，又称多项式码。在循环冗余校验中，是通过在数据单元末尾加一串冗余比特，使得整个数据单元可以被另一个预定的二进制数所整除。,任何一个二进制数序列可以和一个只含有0和1两个系数的代数多项式建立起一一对应的关系。

18、,多 项 式,多 项 式,任何一个n位的二进制数都可以用一个n-1 次的多项式来表示,这种多项式叫码多项式（又叫信息多项式）。码多项式与二进制序列之间的一一对应关系：（an-1 an-2a1a0）N A(x)=an-1Xn-1+an-2Xn-2+a1X+a0X0,码多项式,多项式 二进制序列实例,以n=3位二进制数为例 二进制数 对应多项式 000 001 010 011 100 101 111,0,1,x,x+1,x2,x2+1,x2+x+1,1011011 x6+x4+x3+x+1 x5+x4+x2+x 110110,CRC校验的基本思想是：根据欲发送的k位信息位构成的报文，发送器生成一个

19、r比特的序列，称为帧校验序列FCS,将r位FCS（即CRC码）附加到k位信息序列之后作为实际发送的数据帧（k+r位），这个帧所对应二进制序列恰好能够被某个预先确定的数（生成多项式）整除。接收器用相同的数去除传来的帧。如果无余数，则认为无差错；如果余数不为0，则认为传输出错。,CRC码生成和校验基本分为三步：第一步：在数据单元(k位）的末尾加上r个0。r是一个比预定除数的比特位数(r十1)少1的数。第二步：采用二进制除法将新的加长的数据单元（k+r位)除以除数。由此除法产生的余数就是校验码。,CRC码的生成,自定义的生成多项式,第三步：用从第二步得到的r个比特的CRC码替换数据单元末尾附加的r个

20、0。如果余数位数小于r，最左的缺省位数为0。如果除法过程根本未产生余数（也就是说，原始的数据单元本身就可以被除数整除）那么以r个0作为CRC码替换余数所在的位置。产生的比特模式正好能被除数整除。,CRC码的生成,CRC码校验：到达接收方的数据单元首先到达的是数据，然后是CRC校验码。接收方将整个数据串当作一个整体去除以用来产生循环冗余校验余数的同一个除数。如果数据串无差错地到达接收方，循环冗余校验器将产生余数0。因此数据单元将通过检验。如果在传输中数据单元被改变，除法将产生非零余数，因此数据单元将通不过检验。,CRC码的校验,自定义的生成多项式,0,G(X),补0数比除数G(X)位数少1,余数

21、,位数等于附加0数,不够补零,111010100011010 CRC校验码 信息码 CRC冗余校验码,CRC校验码的生成器和校验器,发送方,接收方,生成多项式G(x):求CRC码时所用的“除数”所对应的多项式叫生成多项式。在串行通信中通常使用下列三种生成多项式G（X）来产生CRC码。CRC-16：G(x)=X16+X15+X2+1，美国二进制同步系统中采用。CRC-CCITT：G(x)=X16+X12+X5+1，CCITT推荐。CRC-32：G(x)=X32+X26+X23+X22+X16+X12+X11+X10+X8+1X7+X5+X4+X2+X+1,生成多项式,CRC码性能,CRC码是很有

22、效的差错校验方法。常用的CRC除数通常有13、17，或是33个比特，不可检测的错误可能降低到几乎近于零。CRC接收电路再配上适当的硬件电路不仅可以检错，而且可以纠错，纠错能力很强特别适合检测突发性错误，在数据通信中得到较广泛的应用。,总结CRC码特点,可靠性好，不可检测的错误可能降低到几乎为零。设备简单，纠错能力强，适合检测突发性错误,卷 积 码,1.概述2.编码器3.解码器,1.概述,前面介绍的编码方法都是线性分组码，即监督码只负责监督检验本码组中的信息码元。如果每组的监督码元不但与本组码的信息码元有关，而且还与前面若干组信息码元有关，每个监督码元对它的前后码元都实行监督，前后相连，具有连环

23、监督的作用；因此我们称为连环码，即卷积码。卷积码由 P.Elias于1955年最先提出，整个编解码过程一环扣一环，连锁地进行下去。,2.编码器,(2,1,3)卷积码编码电路,（状态标识S0S3）:m1 m2,当输入5位信息10110时，输出码字和状态转移是,S0 1/11 S1 0/10 S21/00 S1 1/01 S3 0/01S2,网 格 图,00100111,状 态 转 换 图,卷积码的维特比（Viterbi）解码,基本思想：属于最大似然算法，既把接收序列与所有可能的发送序列进行比较，选择一种码距最小的序列作为发送序列。接收一段，计算和比较一段，选择一段有最有可能的码段，从而达到整个码

24、序列是一个最大似然值的序列。,维特比算法例：设卷积码为(n,k,m)=(3,1,3)码 现在的发送信息位为1101为了使移存器中的信息位全部移出，在信息位后面加入了3个“0”，即1101000编码后的发送序列：111 110 010 100 001 011 000接收序列：111 010 010 110 001 011 000(红色为错码)发送序列的约束长度为N=3，所以首先需考察3个信息段，即考察3n 9比特，即接收序列前9位“111 010 010”。,解码第1步由网格图可见，沿路径每一级有4种状态a,b,c和d。每种状态只有两条路径可以到达。故4种状态共有8条到达路径。比较网格图中的这8

25、条路径和接收序列之间的汉明距离。例如，由出发点状态a经过3级路径后到达状态a的两条路径中上面一条为“000 000 000”。它和接收序列“111 010 010”的汉明距离等于5；下面一条为“111 001 011”,它和接收序列的汉明距离等于3。,将这8个比较结果列表如下：比较到达每个状态的两条路径的汉明距离，将距离小的一条路径保留，称为幸存路径。这样，就剩下4条路径了，即表中第2,4,6和8条路径。,解码第2步：继续考察接收序列中的后继3个比特“110”计算4条幸存路径上增加1级后的8条可能路径的汉明距离。计算结果列于下表中。表中总距离最小为2，其路径是abdc+b，相应序列为111 1

26、10 010 100。它和发送序列相同，故对应发送信息位1101。,在编码时，信息位后面加了3个“0”，使寄存器中信息位全部移出。若把这3个“0”仍然看作是信息位，则可以按照上述算法继续解码。这样得到的幸存路径网格图示于下图中。图中的粗线仍然是汉明距离最小的路径。,若已知这3个码元是（为结尾而补充的）“0”，则在解码时就预先知道在接收这3个“0”码元后，路径必然应该回到状态a_000。而由图可见，只有两条路径可以回到a状态。所以，这时上图可以简化成：,维特比译码能纠正部分错，但并不能纠正所有可能发生的错误，当错误模式超出卷积码的纠错能力时，译码后的输出序列就会带有错误。,寄存器：是能够寄存一组

27、二进制信息的逻辑部件。,由D型触发器组成的4位寄存器,补充：寄存器,触发器,能寄存一位二进制信息的单元电路称为触发器。触发器有两个输出端：“1”端和“0”端（见下页图）。两个输出端的极性总是相反（“1”端为高电平，“0”端就为低电平；“1”端为低电平，“0”端就为高电平）没有外界作用，触发器状态保持不变，即所存的信息不变。在一定的外界作用下，触发器能从一种状态变到另一种状态并保持住。,D触发器,在SET端（置“1”端）加一负脉冲，触发器变为“1”状态。在CLR端（置“0”端）加一负脉冲，触发器变为“0”状态。平常，SET端和CLR端为高电平。CP端为接收脉冲（或称打入脉冲）输入端。当CP端没有

28、接收脉冲时，即一直处于固定的电位时，触发器的状态保持不变。在CP端加一接收脉冲，在脉冲的上升沿（由低变高）时，如果此刻代码输入端D为0，则触发器变为0，如果D为1，则触发器变为1。也就是说，接收的信息（或说成打入到触发器中的信息）取决于接收脉冲的上升沿时刻代码输入端的状态。接收脉冲过后D型触发器的状态保持不变。,由D触发器构成4位移位寄存器,D触发器实现二分频电路,差错控制方法,1 差错控制方法（1）自动请求重发(ARQ)1.停止等待ARQ 2.返回N帧（Go-Back-N）ARQ 3.选择性重发ARQ（2）前向纠错控制方法（FEC）（3）混合纠错控制方法（HEC)（4）信息反馈（5）其它差错

29、控制方式2 差错控制的性能估算和应用,利用我们前面介绍的抗干扰编码（或叫差错控制编码）来控制传输系统的传输差错的方法，称为差错控制。,差错控制的两种基本思想：一是通过差错编码，使得接收端译码器能发现错误并准确地判断差错的位置从而自动纠正它们。另一个就是在接收端能够发现错误但无法自动纠错，请求发送端重发数据等方式来达到纠正错误的目的。,差错控制的工作方式可分为四类：自动请求重发（ARQ），前向纠错（FEC），混合纠错（HEC）和信息反馈（IRQ），另外还有诸如像冗余法，多数表决法（重复编码）等，下面分别加以介绍。ARQ Auto Request for RetransmissionFEC For

30、ward Error CorrectionHEC Hybrid Error CorrectionIRQ Information Repetition Request,差错控制方式分类,（1）ARQ:自动请求重发,又称反馈重发发送端首先对发送序列（信息码）进行差错编码，生成一个可以检错的校验序列（监督码），然后连同数据一起发送出去；（无法纠错）接收端根据校验序列的编码规则判决是否出错，并把判决结果通过反馈通道传回给发送端：,ARQ传输差错处理方法,通常处理传输差错的办法如下：肯定确认：接收端收到一个帧后未发现错误，回送一个确认信号，用ACK表示。否定确认：用NAK表示。超时重发(Overtime

31、)：发送端发出一个帧后开始计时，如果在规定的时间内没有收到应答信号（ACK或NAK），则认为发生帧丢失的或确认信号丢失。必须重发。,ARQ:自动请求重发,1.停止-等待ARQ2.返回N帧（Go-Back-N）ARQ3.选择性重发ARQ,1.停止-等待ARQ,(1)基本概念：发送端：发送一帧数据 等待确认（ACK/NAK）重发上一帧或发送下一帧数据获得ACK之前，发送端必须备份已发送的一帧数据Timer:avoid Deadlock frame lost接收端：等待接收数据，并校验正确，将接收到的数据帧上交网络层并回送ACK错误，丢弃接收到的数据帧并回送NAK,?,1.停止-等待ARQ,解决问题

32、Deadlock:TimerRepeated data frame:add NO.field（编号）n the data frame,1.停止-等待ARQ,状态序号：收发双方都维持一个状态序号，用来记录链路上期待正确接收、确认的帧序号(2)操作要点：初始化：将收发两端状态序号初始化为0状态序号通过1bit的数据来维持即可（序号非0即1）发送端：每送出一个数据帧（数据帧的序号为本地状态号，第一个数据帧序号为0），然后要更新本地状态序号（设用V1(s)表示）中。发送重复帧先恢复原来V1(s)接收端：每送出一个ACK帧，其序号应当提取本地新的状态号V2(s)(刚刚更新过)检测出错误不更新V2(s),

33、1.停止-等待ARQ,（两者一至如何，两者不一至如何？）,答：若两者一致，则说明是新的数据帧，要更新本地状态序号，并回送确认帧。并且，准备接收下一个数据帧。若发现不一致，则说明是重复帧，应该丢弃之，并且不改变状态序号的值，但仍需向发送端回送一个确认帧。而帧的序号应该为本地状态序号的值。,接收端：每收到一个数据帧，将其序号与本地的状态序号V2(s)相比较。,1.停止-等待ARQ,发送端：每收到一个确认帧，将其序号与本地的状态序号V1(s)相比较。,（两者一至如何，两者不一至如何？）,答：若两者一至，则说明传输正确，可以发送新的一数据帧，并更新本地状态序号；准备接收下一数据帧。若发现不一至，说明是

34、重复的确认帧，只需丢弃即可，继续等待所期望的确认帧。,总结：发送端的状态序号值等于下次准备发送的数据帧的序号；而接收端的状态序号表示当前期望接收的数据帧的序号。,链路数据传输过程：正常,链路数据传输过程：数据帧出错,链路数据传输过程：数据帧丢失,链路数据传输过程：确认帧丢失,2.返回N帧（Go-Back-N）ARQ,(1)基本想法：发送端连续发送data frame if有错,则回退N帧继续连续发送data frame（重发所有其它帧，不管它是否正确接收）(2)缓冲区大小：发送端：需要一个能存储N个数据帧的缓冲区（重发表），以便随时准备重发。接收端：对检测出有错的那个数据帧之后的N-1帧，不论

35、正确与否都一律丢弃，故只需能够存储一个数据帧的缓冲区即可。,（3）返回N帧ARQ示意图,ACK1,ACK2,NAK3,NAK4,NAK5,NAK6,NAK7,NAK8,NAK9,ACK3,ACK4,ACK5,ACK6,NAK7,提交网络层,提交网络层,丢弃,丢弃,接收端,发送端,回退N帧：N=滑动窗口大小发送端:每收到ACK帧，继续发送新数据每收到NAK帧，回退N帧，即重发出错帧以及其后发送的 N-1 帧数据（不管它们是否正确）,（4）传输过程几种情况,数据帧和确认帧都正常数据帧出错（丢失），返回NAK（启动Timer）回退N帧数据帧正确而确认帧出现错误：后继收到的确认帧为ACK后继收到的确认

36、帧为NAK,ACK帧出现差错，但数据确实有送到，使用更后面的ACK帧来确认当前ACK出错的帧（一个ACK帧确认多个数据帧）,回退N帧,（5）返回N帧ARQ操作要点,(1)数据帧和确认帧都正常：不出现差错或丢失（1）发送端连续发送数据帧而不等待确认帧，直到收到第一帧的确认帧为止决定下一步操作（2）发送端在重发表中保存N个数据帧的备份（3）重发表按FIFO规则操作（4）接收端对每一个正确接收到的数据帧返回一个确认(ACK)帧,（5）每一个数据帧包含一个唯一的序号（6）接收端保存一个接收序列表，保存最后正确接收到一帧数据（7）当一收到相应数据帧的确认(ACK)帧，发送端从重发表重删除该数据帧,(2)

37、数据帧出错（帧受损坏、丢失）：（1）假设第 N+1 帧数据出错（2）接收端立即返回 NAK(N+1)，指出最后正确接收到的是第 N 帧（3）接收端同时清除其后收到的的其它数据帧，直到收到正确的第(N+1)帧（4）为避免死锁（ACK/NAK丢失），一般发送端在发送一帧数据的同时启动定时器,（5）一旦正确收到第(N+1)帧，接收端就继续正常工作（6）发送端可以接收确认、否认帧（ACK/NAK）ACK：继续发送后继帧NAK：回退N帧重发,(8)返回N帧ARQ存在问题,返回N帧ARQ因连续发送数据帧而提高传输效率。发送端要维持和滑动窗口一样大小的缓冲区，备份已发送的数据；并且重发时不管出错数据帧其后的

38、数据帧是否有错，一律重发，使传输效率降低。通信链路较差、误码率较大时，go_back_N就不一定优于stop_and_wait（经常回退）另外在长传播延时链路上go_back_N传输效率也较低。（重发N帧花费时间）,3.选择性重发ARQ,在返回N帧ARQ的基础上改进而来，也是一种ARQ连续方案。发送端连续发送数据帧接收端接收确认：ACK(N)连续发送NAK(N)发送端根据NAK（N）中N确认重发出错帧；只重发错误的帧，避免对后继正确数据帧的多余重发，较返回N帧方案效率有明显提高。,（1）选择性重发ARQ示意图,ACK1,ACK2,NAK3,ACK4,ACK5,NAK6,ACK7,ACK8,AC

39、K9,ACK3,ACK10,NAK6,ACK11,与4、5号帧一起提交网络层,提交网络层,暂存与缓冲区中,暂存与缓冲区中,重传,NAK12,ACK13,NAK14,ACK15,ACK16,ACK17,ACK6,与711号帧一起提交网络层,重传,重传,（2）选择性重发ARQ存在问题,选择性重发ARQ在效率上获得的增加，是以复杂的接收控制机制和巨大的缓冲容量为代价的。在链路较差以致较多出现单个数据帧连续出错的情况下，重发帧和接收帧的缓存提取以及接收后的排序问题都比较复杂。因此，应用不如回退N帧ARQ广泛。,(3)GBN&SR控制技术比较,Go_Back_N ARQ:发送方需要较大的缓冲区，以便重传

40、 接收方缓冲区仅为1适于信道出错率较少的情况Selective Repeat ARQ接收方也需要较大的缓冲区，以便按正确顺序将分组提交网络层适于信道质量不好的情况,ARQ技术的主要特点,ARQ要求有反馈回路，系统需采用双工通讯方式控制规程和过程较复杂，但与FEC相比复杂性和成本要低的多反馈重传，效率较低，不适合于实时传输系统,（2）前向纠错控制方法FEC,发送端逐行纠错编码，码组冗余度大具有自动纠错能力，然后发送这种能纠错的码接收端译码并自动纠正传输差错特点：a 无反馈过程，可采用单工通讯b 传输系统延时小，实时性强c 纠错码，编码冗余度大，传输效率有所下降d 控制规程简单，但编译码设备较复杂

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

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

43、ame）：10110010 10110010 10110010,差错控制的性能估算和应用,1.性能估算方法：二元对称信道：是指传输信息只有1和0两种可能的信道，设两种信息传错的概率相同均为p，传对的概率为q=1-p,应用：(1)出现少量错误在接收端能纠正时选用前向纠错法（FEC）。(2)当错码较多超过纠错能力但在检错能力范围内时,可用反馈纠错法（ARQ）。(3)有时可以降低有效信息传输速度为代价来提供传输质量。(4)同一信道传输几种信息时，信道的差错率指标可按信息组成中主要部分的差错要求来挑选。,差错控制的应用,（5）具体情况具体分析：当数据不能随便抛弃而反馈系统又没有时，就必须采用前向纠错技术。如果设备允许，则可采用反馈纠错系统。有些情况可将检错纠错结合使用。,第六次作业,