数字与数据通信 31 差错控制

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,数字与数据 通 信,1,1,、一基带传输系统，其形成系统特性，如图所示，,试在下表中的空格填入相应的数值。,2,、有一基带传输系统，采用升余弦滚降，试将,频率利用率填入相应的空格内。,3,、一个,2PSK,系统，数据序列,“,1,”,对应于已调,载波的,180,相位，,“,0,”,对应于已调载波的,0,相位，,按表中的数据序列填出,2PSK,信号的相位。,4,、一个,DPSK,系统，数据序列,“,1,”,，载波相位,与前一码元变化,180,相位，,“,0,”,表示载波相位,与前一码元不变，设初始相位为零。按表中的,数据序列填出,2DPSK,信号的相位。,4,、,一个,DPSK,系统，数据序列,“,1,”,，载波相位,与前一码元变化,90,相位，,“,0,”,表示载波相位,与前一码元变化,270,，设初始相位为零。,填出下表中,2DPSK,信号的相位。,5,、一个,4DPSK,系统，其工作方式按图所示，设,已调载波信号初始相位为,0,，按下表的数据序列,填出已调载波信号对应的相位。,5,、,一个,4DPSK,系统，其工作方式按图所示，设,已调载波信号初始相位为,180,，按下表的数据序列,填出已调载波信号对应的相位。,6,、有预编码的第一类部分响应系统，如图所示，,输入数据序列为,010110010,7,、有预编码的第四类部分响应系统，如图所示，,输入数据序列为,0011010100,一、 差错控制的基本概念及原理（,88,页）,1. 差错控制的基本概念,差错分类和错误图样,第,3,章 差错控制,造成误码的主要原因：,码间干扰：均衡,干扰：差错控制,差错分类,随机噪声和脉冲噪声,随机差错又称独立差错，它是指那些,独立地、稀疏地和互不相关地,发生的差错。随机噪声导致传输中的随机差错。存在随机差错的信道称为,无记忆信道或随机信道,。,突发差错是指一串串，甚至是成片出现的差错，差错之间有,相关性,，差错出现是密集的。脉冲噪声使传输中出现突发差错。存在突发差错的信道称为,有记忆的信道或突发信道,两种错误并存的信道称为,组合信道或复合信道,差错控制的基本思路,在发送端被传送的信息码序列（本身无规律）的基础上，按照一定的规则加入若干监督码元后进行传输，这些加入的码元与原来的信息码序列之间存在着某种确定的约束关系。,在接收数据时，检验信息码元与监督码元之间的既定的约束关系，如该关系遭到破坏，则收端可以发现传输中的错误，乃至纠正错误。,信息码（,k,）,+,监督码（,r,）,=,码组（,n,）,以牺牲,有效性,来换取,可靠性,实际的信道是复杂的，所出现的差错也不是单一的，而是随机和突发错误并存的，只不过有的信道以某种错误为主而已，这两类错误形式并存的信道称为,组合信道或复合信道,。,一般来说，针对随机错误的编码方法和设备比较简单，成本较低，而且效果显著；而纠正突发错误的编码方法和设备较复杂，成本较高，效果不如前者显著。因此，,要根据错误的性质设计编码方案和选择差错控制的方式。,四种差错控制方式（,89,页）,检错重发,(,自动重传请求（,Automatic Repeat-reQuest,：,ARQ),前向纠错（,FEC,：,Forward Error Correction,）,混合纠错（,HEC,：,Hybrid Error Correction,）,信息反馈（,IRQ,：,Information Repeat reQuest,）,检错重发(ARQ),思路：,ARQ,是在发送端对数据序列进行分组编码，加入一定监督码元使之具有一定的检错能力，成为能够发现错误的码组。,接收端收到码组后，按一定规则对其进行有无错误的判别，并把判决结果,(,应答信号,),通过,反向信道,送回发送端。,如有错误，发送端把前面发出的信息重新传送一次，直到接收端认为已正确接收到信息为止。,差错控制方式,1,、检错重发,ARQ,3,种工作思路：,停发等候重发；返回重发；选择重发,发,收,能够发现错误的码,应答信号,(a),检错重发,(ARQ),停发等候重发,信号传递过程是：发送端在,T,W,时间内发送码组,1,给,接收端，然后停止一段时间,T,D,，,T,D,大于应答信号,和线路延时的时间。接收端收到后经检验若未发现,错误，则通过反向信道发回一个认可信号,(ACK),给,发送端，发送端收到,ACK,信号后再发出下一个码组,2,。接收端检测出码组,2,有错，则由反向信道发回一,个否认信号,(NAK),，请求重发。发送端收到,NAK,信,号后重发码组,2,，并再次等候,ACK,和,NAK,信号。,在发送码组之间,有停顿时间,Td,，使传输效率受到影响，但,工作原理简单,，在数据通信中仍得到应用,4,2,t,t,(a),发,收,1,1,ACK,T,D,2,NAK,2,2,ACK,3,3,ACK,4,NAK,4,NAK,4,4,4,返回重发,信号传递过程与停发等候重发不同，其发送端无,停顿地送出一个个连续码组，不再等候接收端返回的,ACK,信号，但一旦接收端发现错误并发回,NAK,信,号，则发送端从下一个码组开始重发前一段,N,组信,号。,N,的大小取决于信号传输及处理所带来的延时。,这种返回重发系统的传输效率比停发等候重发系统有很大改进，在许多数据传输系统中得到应用,t,t,(b),发,收,1,2,3,4,5,6,2,3,4,5,6,7,8,4,5,6,7,8,4,5,1,2,3,4,5,6,2,3,4,5,6,7,8,4,5,6,7,8,N=5,选择重发,选择重发系统也是不断地发送信息码组，,接收端检测到错误后发回,NAK,信号。与返回,重发系统不同的是，发送端不是重发前面的所,有,N,个码组，而是,只重发有错误的那一个码,组，对其它码组不再重发,。,t,t,(c),发,收,1,2,3,4,5,6,2,7,8,9,10,11,12,8,13,14,15,16,17,18,1,2,3,4,5,6,2,7,8,9,10,11,12,8,13,14,15,16,选择重发只重发有错误的码组，所以传输效率更好。但,排序不对，,存储器读出时需要重新排序，恢复正常的码组序列。,因此，在发,送和接收端都需要足够的缓冲存储器容量。,ARQ,的优缺点,需反向信道，实时性差。,ARQ,方式在信息码后面所加的监督码不多，所以信息传输效率较高。,译码设备较简单。,前向纠错,FEC(92,页,),FEC,的思路：,前向纠错系统中，发送端的信道编码器将输入数据序列变换成能够纠正错误的码，接收端的译码器根据编码规律检验出错误的位置并自动纠正。,FEC,的优缺点,不需要反向信道，实时性好。,缺点是所选择的纠错码必须与信道的错码特性密切配合，否则很难达到降低错码率的要求；,译码设备复杂；而要求附加的监督码也较多，传输效率就低。,发,收,可以纠正错误的码,(b),前向纠错,(FEC),随着编码理论和微电子技术的发展，译码设备成本降低，加之这种方式具有能实现单向通信和控制电路简单的优点，因而在实际应用中日益增多。,混合纠错检错（,HEC,）,HEC,的思路：,混合纠错检错方式是前向纠错方式和检错重发方式的结合。,在这种系统中，发送端发出同时具有检错和纠错能力的码，接收端收到码后，检查错误情况，如果错误少于纠错能力，则自行纠正；如果干扰严重，错误很多，超出纠正能力，但能检测出来，则经反向信道要求发端重发。,混合纠错检错方式是前向纠错和检错重发方式的结合,HEC,的优缺点：,混合纠错检错方式在实时性和译码设备复杂性方面是前向纠错和检错重发方式的折衷，因而近几年来，在数据通信系统中采用较多,发,收,可以纠正和发现错误的码,(c),混合纠错检错,(HEC),信息反馈,IQR,思路：在发端不进行纠错编码，接收端把收到的数据序列全部由反向信道送回发送端，发送端自己比较发送的数据序列与返回的数据序列，从而发现是否有错误，并发认为出错的数据再次发送直到没有发现错误为止。,优缺点：优点是不需要纠错和检错的编译码设器，设备简单；缺点是需要和前向信道相同的反向信道，实时性差，发端需要一定量的存储器,信息反馈,又称回程校验,IRQ,方式仅用于传输速率低，数据信道差错率较低，且具有双向传输线路及控制简单的系统中,发,收,数据信息,数据信息,(d),信息反馈,3.6,简单差错控制协议（补充）,3.6.1,停止等待协议,1.,停止等待协议的概念,发送端每发送一个数据帧（对应一个码组）就暂停下来，等待接收端的应答。接收端收到数据帧进行差错检测，若数据帧没错，就向发送端返回一个确认帧,ACK,，发送端再发送下一个数据帧；若接收端检验出数据帧有错，就向发送端返回一个否认帧,NAK,，发送端重发刚才所发数据帧，直到没错为止。,2.,停止等待协议算法,（,1,）数据帧在实际链路上传输的几种情况,数据帧在实际链路上传输有四种情况，如图,3-20,所示。,图,3-20,数据帧在实际链路上传输的几种情况,3.6.2,自动重发请求（,ARQ,）协议,1.ARQ,协议的概念,为了提高通信信道的利用率，满足数据传输高效率的要求，要使发送端能够连续发送数据帧，而不是在每发送完一个数据帧后，就停下来等待接收端的应答。发送端在连续发送数据帧的同时，接收对方的应答帧。若收到确认帧，继续发送数据帧。但若收到否认帧，将出错数据帧或出错数据帧及以后的各帧重发。,根据重发方式的不同，,ARQ,协议,连续,ARQ,协议,和,选择重发,ARQ,协议,连续,ARQ,协议,和,选择重发,ARQ,协议,2.,连续,ARQ,协议,连续,ARQ,协议的重发方式是返回重发，即,发送端从出错数据帧及以后的各帧都要重发。,3.,选择重发,ARQ,协议,选择重发,ARQ,协议的重发方式是选择重发，即,发送端只重发出错数据帧。,连续ARQ协议采用连续发送方式提高了数据传输效率，但是如果出错重传的数据帧较多时，效率又达到降低，故只适合与质量较高的信道使用,选择重发ARQ协议可以避免重复传送哪些本来已经正确到达接收端的数据帧，但是需要在接收端占用更多的缓冲区！,连续ARQ和选择重发ARQ,项目,连续,ARQ,选择重发,ARQ,发送方式,连续发送,连续发送,传输效率,比较高,最高,控制方法,比较简单,比较复杂,缓冲存储器,发送端有,两端都要有,成本,比较低,比较高,3.6.3,滑动窗口协议,在使用连续,ARQ,时，配套使用滑动窗口协议，限制,已经发送的但是未被确认的数据帧的数目,，这种方法既可以循环重复使用数据帧的序号，减少系统的额外开销，又能实现流量控制。,具体实现在发送端设发送窗口，在接收端设置接收窗口,3.6.3,滑动窗口协议,1.,发送窗口,发送窗口用来对发送端进行,流量控制,。发送窗口的尺寸代表,在还没有收到对方确认的条件下，发送端最多可以发送数据帧的个数。,发送窗口用 表示。,由于发送窗口是重复循环使用发送序号，为了避免接收端混淆是新的数据帧还是旧的数据帧，要求发送窗口尺寸与编号比特,n,的关系为,图,3-23,发送窗口的意义,2.,接收窗口,接收窗口用来控制接收数据帧。,只有当接收到数据帧的发送序号落在接收窗口内，才允许将该数据帧收下；否则，一律丢弃。,接收窗口的尺寸用 表示。,在连续,ARQ,协议中， 。,图,3-24,接收窗口的意义,2.,差错控制的基本原理,所谓差错控制编码实际上就是在保持信息的位数不变的情况下，采用,增加码长,的方法来降低误码率。,具体来说：码的检错和纠错能力是用信息量的,冗余度来换取的。,如果我们增加一位码,(,监督码,),，并按一定的规律编码如下：,A B,0 1,0,1,即用两位码取代一位码，编码规律是监督位与信息位相同，,00,和,11,称为许用码组,。而另外的两种组合：,01,和,10,称为禁用码组,。,0 1 1 0,因此，在发送端发出的码组只能是许用码组“,00”,或“,11”,，如果在接收端收到禁用码组“,01”,或者“,10”,，则我们可以判定数据码组在传输中，发生了且发生了一位错码。,结论：加入一位监督码可以检查出一位错码。,那么能检查两位错码吗？,第二个问题现在是能不能纠正一位错码。,要纠正一位错码，必须满足两个条件，一是确定本码组发生了一位码错，二是必须确定错码位置。,下面我们以为,01,例来说明：,01,是禁用码组，可以肯定是发生了一位错，但是,01,既可能是由,00,第二位码错而得来，即“,1”,位错，也可能是由,11,第一位码错而得来，即“,0”,位错。,两者都可能而且概率一样大,。如上图所示。,当出现两位错码后，必然从一个许用码组错成另一个许用码组，因此，接收端收到许用码组，当然就发现不了错误，所以加入一位监督码,不能检查出两位错码,。,0 0 1 1,0 1 1 0,所以能不能检查出几位错码，关键是看最少错几位码就能从一个许用码组错成另一个许用码组。,结论：不能纠正一位错码。,那么怎样才能纠正一位错码呢？,只有再加一位监督码，进一步增加编码的冗余度。,加码的规律及情况如下：,A B,0 0 0 1 1 1,加监督码的规律与前相同，但是，由于码组的长度是,3,，所以,禁用码组应有,6,组,，并可分为,2,组，参见左图。,0 0 1,0 1 0,1 0 0,1 1 0,1 0 1,0 1 1,这种编码方式可以检查出,1,位和两位错码，但是不能检查出三位错码。,1,位,2,位,3,位,所以发生一位错的概率是发生两位错的概率的,10,6,10,12,=10,6,倍，近似可以这样说如果,100,码组出现了次，其中次是,000,的第一位码错造成的，而只有,1,次是,111,后两位码错得来的。,即,99.9999%100%,的概率说明,100,是,000,第一位码“,0”,错成了“,1”,。,能纠正几位错码呢？,只能纠正一位错码。,A B,0 0 0 1 1 1,0 0 1,0 1 0,1 0 0,1 1 0,1 0 1,0 1 1,通过左图可看出，,100,既可能是,A,信息,000,的第一位码“,0”,错成“,1”,，也可能是,B,信息,111,的后两位码“,11”,错成“,00”,。,但是两种情况发生的概率不一样。设传输信道的误信率,P,e,=10,6,，则,000,错成,100,的概率为,10,6,，而,111,错成,100,的概率为,10,6, 10,6,= 10,12,。,结论：加入,2,位监督码就可以纠正,1,位错码。,但是在次中平均有,1,次是错误纠正的，但是没有关系，因为这一次本身就是错误的码组,(,禁用码组,),，只是由一种错误码组纠成了另一种正确码组，没有把正确的许用码组纠成错误的禁用码组就行了。,假设传输信道是随机信道，则在本例中，错一位、二位和三位码的概率的数量级应是,P1=10,6,、,P2 =10,12,和,P3 =10,18,，所以一位错出现的概率远远大于出现二位和三位错的概率之和。,所以能纠正一位错就能纠正绝大多数错误，今后学习的纠错码一般也只要求纠正一位错码,。,由此可见，纠错编码之所以具有检错和纠错能力，是因为在信息码之外附加了监督码，监督码不载荷信息，它的作用是用来监督信息码在传输中有无差错，对接收端的用户来说是多余的，最终也不传送给用户，但它提高了传输的可靠性。,但是，监督码的引入，降低了信道的传输效率。,一般来说，引入监督码越多，码的检错、纠错能力越强，但信道的传输效率下降也越多,。,研究的目标是寻找一种编码方法使所加的监督码元最少而检错、纠错能力又高，且便于实现。,二、 检错和纠错的基本概念,1. 码距与检错和纠错能力,为了说明码距的概念，,把,3,位码元构成的,8,个码组,用一个三维立方体来表,示，图中立方体的各顶点,分别为,8,个码组，,3,位码元,为,A1,，,A2,，,A3,轴的坐标。,A,1,A,2,A,3,(000),(100),(001),(101),(110),(010),(011),(111),码距的几何解释,码重：,在信道编码中，码组中非零码,元的数目为码组的重量,码距：,把两个码组中对应码位上具有不同二进制码元的位数定义为两码组的距离，简称码距。,求两个码组的码距可以用如下的方法：,例,1,：,1 0 1 1 0 0 1, 0 0 1 1 1 0 1,最小距离,dmin,：,在一种编码中，任意两个许用码,组间距离的最小值，即许用码组集合中任意两元素,间的最小距离。,1,0 0 0,1,0 0,2,个“,1”,，码距是,2,例,2,：,1 1 0 0 0 1 1, 1 0 1 1 0 0 0,0,1 1 1,0,1 1,5,个“,1”,，码距是,5,最小码距,dmin,与这种编码的检错和纠错能力的数量关系,为检测,e,个错码，要求最小码距为,d,min,e,1,或则说，若一种编码的最小码距为,d,min,，则它能检出,ed,min,1,个错码。,最小码距,dmin,与这种编码的检错和纠错能力的数量关系,为纠正,t,个错码，要求最小码距为,d,min,2t,1,最小码距,dmin,与这种编码的检错和纠错能力的数量关系,为纠正,t,个错码，同时检测,e,（,et,）,个错码，要求最小码距为,dmin e,t,1,这种方式主要用于混合纠错检错,2.,编码效率,其中，,k,为信息码元的数目 （信息位长度）；,n,为编码组码元的总数（编码后码组长度,n=k+r,）；,r,为监督码元的数目 （监督位长度）。,显然，,R,越大编码效率越高，它是衡量码性能的一个重要参数。,编码效率是指一个码组中信息位所占的比重,3.,纠错编码的分类,按码组的功能分，有,检错码,和,纠错码,两类。,按码组中监督码元与信息码元之间的关系分，有,线性码,和,非线性码,两类。,按照信息码元与监督码元的约束关系，又可分为,分组码,和,卷积码,两类。,分组码：,监督码元仅监督本码组中的信息码元，是常用的编码，码长,n=k+r,，用符号,(n, k),表示。,另外，分组码按许用码组,(,码字,),有无循环性结构又可分为,循环码,和,非循环码,两类。,k,个信息位,r,个监督位,码长,n=k+r,a,n,-,1,a,n,-,2,a,r,a,r,-,1,a,0,分组码的结构规定为,(,a,n-1,，,a,n-2,，,a,r,，,a,r-1,，,a,r-2, ,，,a,0),，前,k,位为信息位，后,r,位为监督位。,卷积码：,每组的监督码元不但与本组码的信息码元有关，还与前面若干组信息码元有关，每个监督码元对它的前后码元都要实行监督，也称连环码。,按照信息码元在编码前后是否保持原来的形式不变，可划分为,系统码,和,非系统码,。,按纠正差错的类型可分为,纠正随机错误的码,和,纠正突发错误的码,。,按照每个码元取值来分，可分为,二进制码,和,多进制码,。,练习题：,练习题：,练习题：,3,个码组为：、,0101101,若用于检错，能检出几位错码？,若用于纠错，能纠正几位错码？,练习题：,码组为：,00000,、,11111,若用于检错，能检出几位错码？,若用于纠错，能纠正几位错码？,若同时用于检错和纠错，能纠检几位错码？,