6第六章-差错控制课件

第六章差错控制差错控制主要涉及3个方面的问题：纠错编码的理论和实现；差错控制的方式；信道差错分布的统计特性及其数学模型。在信号传输中，由于受到干扰、噪声等原因产生码型畸变，接收方不能正确辨识信号和恢复信息，产生错误是不可避免的。差错控制就是采用可靠、有效的编码以减少计算机通信系统中传输差错的方法，其目的的是提高传输质量。要想根本解决传输差错问题，降低误码率，提高传输质量，就要改善传输信道的电气特性，使误码率达到要求。但出于经济和技术条件限制，这方面的努力效果不佳。在实际通信系统中，一般采用合适的数据编码和各种差错控制方式来确保传输信息的正确性。在差错控制技术中，对消息数据进行可靠有效的编码是检测错误和纠正错误的基础，而采用适当的差错控制方式，又是提高信息传输效率的重要途径之一。共26页1精选2021版课件第六章差错控制6.1纠错检错编码原理6.2常用的校验编码方式6.3差错控制方法6.4ARQ的各种类型6.5信道的差错特性共26页2精选2021版课件6.1纠错检错编码原理一、差错类型

单位错：在给定的数据单元中只改变一个位，它是一种孤立的差错状态，不影响邻近的其他位。单位错是由热噪声等随机噪声引起的，也称为随机差错或独立差错。突发错：是指几乎是连续发生的一串错，出错的串长度称为突发长度B。长度为B的突发错是指连续B位中的第1个和最后一个位错，中间任意两个相邻错误位之间的正确位数小于规定的标准。突发错的差错之间有相关性，差错是密集、成片出现的。二、校验码的分类数据校验码是一种能发现某些错误或能够纠正本身某些错误的数据编码方法，也称抗干扰码。校验码采用冗余编码方法，在所要传送的数据序列中，按一定的规则加入一些新的码元(称为校验位或监督位)，使这些多余码元与数据码元之间建共26页3精选2021版课件二、校验码的分类立某种相关关系。接收端接收到校验码后，按编码规则进行译码，如不符合编码规则，就判定为出错，并采取某种纠正措施。校验码有不同的分类方式，主要有以下几种。1、检错码和纠错码检错码：只能检错，不能纠错；纠错码：不但能发现错误，而且能够改正错误；一般来讲，在校验码中，监督位所占比例越大，纠、检错的能力就越大。校验码是以降低传输效率为代价而提高通信传输可靠性的。通常用编码效率来衡量编码的冗余度。编码效率是数据位数与整个校验码的位数之比。2、分组码和卷积码(根据数据位和监督位的生成约束关系)分组码：对要传送的信息数据按适当的位数进行分组，编码时附加的监督位仅仅由本组内的信息代码决定，如图6-1所示。共26页4精选2021版课件2、分组码和卷积码码组也称为帧或包，码组中的监督位称为块校验序列(BCS)或帧校验序列(FCS)。卷积码：也是分组的、但它的监督位不仅与本组的信息有关，而且还与前若干组的信息有关。卷积码的纠错能力强、既可纠正随机差错，又可纠正突发差错。卷积码的译码算法比较复杂，不过都有现成的编译码器芯片。3、线性码和非线性码线性码：指数据位与监督位之间的关系为线性关系，即满足一组线性方程式；非线性码：数据位与监督位之间是非线性关系。数据链路层码组就是帧，其上就是包共26页5精选2021版课件4、系统码和非系统码系统码：编码中数据位的形式与原来一致的编码，例如数据位码元在前，监督位码元在后的编码；非系统码：数据位在编码中的位置与原来不一致的编码，例如监督位码元分布在数据位码元中的编码就是非系统编码；三、编码的纠检错能力1、码重、码组距和码距码重(码组的重量):在校验码中，码组中非零码元的个数称为码重。两个码组之间的距离就是两个码组中对应位之间不相同的个数；码距：该编码全部码组内两两之间距离的最小值；2、码距d与检错或纠错能力的关系共26页6精选2021版课件2、码距与检错或纠错能力的关系合法码组可能的合法码组纠错一般采用最大似然规则，即非法码组离哪个合法码组最近，就把该非法码组纠正为那个合法码组。出错位不超过e个出错位不超过t个出错位不超过e个共26页7精选2021版课件3、接收方可能接收的码组接收方接收了一个码组后，会有3种情况发生：码组在传输过程中无差错发生；码组在传输过程中有差错发生，所发生的差错被接收方检测出。当合法码组出错位不等于码距或其整数倍数时，就变成了非法码组，这时接收方就可以根据编码规则发现错误；码组在传输过程中有差错发生，但接收方未能检测出来；当合法码组的出错位数正好等于码距d或其倍数时，该合法码组就有可能变成另外一个合法码组，这时接收方就无法检测出来。上述3种情况的发生概率与校验码的码距直接相关，也与差错控制方法有关。例如d=3，使用检错差错控制方法可以检出2位错；如果使用纠错差错控制方法可以纠正1位错误，如果这个时候发生两位错，经过纠错得到的码就是错误码。共26页8精选2021版课件6.2常用的校验编码方式一、奇偶校验码奇偶校验码的码距为2，无纠错能力，但对所有的奇数位出错都能检测出来，核验电路也比较简单。偶校验(even)；奇校验(odd)；传号校验(mark)，校验位始终为1；空号校验(space)，校验位始终为0；无校验(none)。二、方阵校验码右边方阵码的码距为4，是一种纠错码，具有1位纠错能力，同时能够检测2位错。ASCII字符码奇偶校验码共26页9精选2021版课件三、恒比码恒比码就是使校验码中的1和0的数目之比是一个常数。中国五单位保护电码，见表6-1，能发现一位错，其码距为2。ARQ准确计数编码也是一种恒比码，这种码每个字符有7位，每个字符中所含1的个数相同，都为2个。四、校验和校验和(checksum，或称检查和)通常用于对数据块的校验。它把数据块中的每一个字符代码都按二进制加法求和，然后把所求得的和作为监督位。校验和可以使用不同字节数，但是对高位进位主要有以下几种：按模加，不考虑高位的进位；循环进位，把高位的进位当作最低位再加进去；共26页10精选2021版课件四、校验和(用一个程序实现之)校验和除对高位进位有不同处理之外，对校验和本身也有不同处理方式，例如TCP数据包和IP数据报把16位循环求和取补作为监督位。五、CRC码CRC码的计算方法是用事先约定的一个生成多项式函数G(x)去除0、1数据串，舍弃商，将余数作为监督位(通常称为帧校验序列FCS)，由数据和FCS组成新的数据帧发送。接收端用同样的生成多项式除以接收进来的数据帧，若没有余数．则认为无错。(代数编码理论把二进制序列看成一个多项式)设M为要传输的数据，有k位；P为生成多项式，有n+1位；F为FCS，有n位；T为CRC校验形成的数据项，有k+n位。无差错时，T/P的余数为0。CRC码的具体生成办法是将k位数据左移n位，低位补0，再用n+1位的生成多项式进行模2除，所得的n位余数就是FCS。共26页11精选2021版课件常用的生成多项式有：五、CRC码理论证明，CRC码的检错能力很强。r位生成多项式可检测出所有的单错、双错、奇数位错和突发长度小于或等于r的突发错，对于突发长度为r+1的突发错的检出概率是1-2-r-1，对于突发长度大于r十1的突发错的检出概率是(1-2-r)。根据以上假定可以得到如下运算结果：共26页12精选2021版课件五、CRC码待发送M的比特：1101011生成多项式：监督位序列：1010；CRC码：110101110102nMPQR共26页13精选2021版课件6.3差错控制方法差错控制的基础就是发送具有检错或纠错能力的校验码。如果校验码只有检错能力而无纠锗能力，则需要反向信道(从接收端到发送端的信道)把检测结果反馈给发送端。差错控制方式有3种基本方法，如图6-3所示。反馈重发纠错前向纠错混合纠错共26页14精选2021版课件一、反馈重发(ARQ)纠错方式(要求误码率很低的通信)无论对或错反馈重发纠错方式(ARQ)又叫自动请求重发方式，即通常所说的ARQ(Automatic-RepeatRequest)方式。适用于点对点通信，有三种形式：停止等待ARQ、重返N-ARQ和选择重发ARQ。检错码二、前向纠错方式前向纠措(ForwardErrorCorrection，FEC)是发送端发送能够纠错的码，接收端收到这个纠错码后，不仅能自动地发现错误，而且能根据译码规律自动地纠正数据传输中所出现的错误。适用于点对点通信共26页15精选2021版课件二、前向纠错方式能单向通信；报文可连续传送，无须等待确认；不需要反向信道，可进行一个用户对多个用户的通信(广播或组搔)和辐射状的通信网；发送端不需要暂存数据，通信缓冲器的容量可以小一些。优点：缺点：译码设备比较复杂；灵活性差，所选的纠错码必须与信道的干扰情况紧密对应；纠正较多错误时，冗余码元增多，传输效率随之下降。三、混和纠错(要求码距等于或大于4)混和纠错(HybridErrorCorrection，HEC)是反馈重传纠错和前向纠错方式的综合。混合纠错在一定程度上避免了FEC系统译码设备复杂和ARQ系统信息连惯性差的缺点，但仍要求有反馈信道，而且不能同播(点对点通信)。共26页16精选2021版课件四、其他差错控制方式除了上述3种基本差错控制方式外，还有一些不采用校验码的方法，常用的有回送法、冗余法和多数表决法。这些方法的传输效率都比较低，但思路简单，实现起来比较方便，如图6-5所示。回送法回送法就是接收端把收到的数据原封不动地通过反馈信道送回到发送端，发送端比较发送的与反馈回来的数据，从而发现锚误，并且把传错的数据重发出去，达到使接收端正确接收数据的目的。冗余法冗余法是发送端把数据发送两次，接收端收到后，比较这发送方检错接受方检错共26页17精选2021版课件两份数据。与回送法的差别是判断力在接收瑞，而回送法则判断方在发送瑞。可以认为是一种特殊ARQ检错方式。多数表决法按照冗余法的思路，当发送的数据副本多增加一份时，其码距也随之增加。当码距大于或等于2时，就具有纠错能力。由此可见，数据冗余的份数多于2份，则可以不用反馈通道而实现纠错，而只在接收端进行判断和自动纠错。通常采用的方法是，把数据发送奇数次，接收端收到这些冗余的数据后，对每一位用多数表决法进行判断，取多数为正确位。多数表决法看起来非常笨拙，但是在实际通信系统中经常使用，只不过为了减少冗余，提供效率，常常只对最重要的字段进行冗余。共26页18精选2021版课件6.4ARQ的各种类型ARQ纠错系统的工作方式基本上可分为两种：一种是半双工，称为等待发送系统；另一种是全双工通信方式，称为连续工作系统。停止等待ARQ是半双工通信方式，重返N-ARQ和选择重发ARQ是全双工工作方式。一、停止等待ARQ停止等待ARQ也称为停等ARQ、发送等待ARQ等。它是指发送端发出一个码组后便停止发送，等待接收端的应答响应信号，若接收端回答是已正确接收(ACK)，则发送端便发送下一个码组；若接收端回答的是未正确接收(NAK)，则发送端便把上一个码组重发一遍，直至该码组正确接收为止，如图6-6所示。共26页19精选2021版课件传输效率h：编码效率hC：就是一个码组中的数据位数与总位数之比：等待效率hW：数据信息有效率hs：接收端平均正确接收一个码组，发送端要发送几个码组，误组率PB接收到的错误码组与总发送码组之比，显然其中式子中各符号含义如下：共26页20精选2021版课件二、重返N-ARQ重返N-ARQ((GOBACKN-ARQ)的意思是发生错误时退回N个码组，即重新发送这N个码组，它采取连续发送方式，对每个发送出去的码组不必立即等待具应答信号。在收到应答信号之前,发送方只能最多发送N个码组。当等待发送的时间较长时，为了提高传输效率，常常采用这种方式。N的取值根据不同系统的具体情况而定。N的取法：重返N-ARQ的传输效率可由下式求得：三、选择重发ARQ在重返N-ARQ中，不管已发出的码组有多少个出错，只要共26页21精选2021版课件有一个码组出错，便要重发N个码组。如果设法只重发有错码组，其余N-1个正确的码组先存储起来，不再随有错码组一起重发，省下的时间用来传送新的码组，就可以大大提高传输效率。这就是选择重发ARQ(SRQ，也称为选择拒绝ARQ)的思想。SRQ按全双工工作，需要对称的双向信道。三、选择重发ARQSRQ的传输效率h为：在实际中还应考虑降低传输效率的两个因素：一是缓冲器的容量，二是应答信号的超时。接收端的缓冲存储器不可能无限长，当某一码组经多次重发后仍不能正确接收而接收缓冲器已满时，后面接收的码组即使正确，接收端也要拒收并要求重发。当反向通道传输出错，应答信号无法到达发送端时，也按重发处理。共26页22精选2021版课件四、各种ARQ方式选择原则对于停止等待ARQ方式，当码组长度大于RT(单位为位)。即传输码组的时间大于环路延迟时间时，其传输效率较高，在某些条件下甚至比其他ARQ方式的传输效率还高。但当信道环路延迟时间增大或传输速率R提高时，即使信道质量较好，其传输效率也将很快下降。对于重返2-ARQ方式，当信道质量较好时，其传输效率相当高，只要RT值不大于码组长度，其传输效率不受RT数值的影响。但当信道差错率较高时，其传输效率下降很快，这时如采用SRQ，其传输效率就最高。当RT大于重返2-ARQ的码组长度n时，信道较好时，用加长码组为好；而信道较差时，用重返N-ARQ(N值根据需要来确定)为好，因为重返N-ARQ方式的传输效率随误码率增加而缓慢下降的。当信道较差时(误码率在10-3左右)，并且RT值较大时，短码组的重返N-ARQ方式比停止等待ARQ方式或长码组的重返2-ARQ方式为好。共26页23精选2021版课件6.5信道的差错特性一、信道的差错统计特性1、误码率与误组率2、信道的差错分布类型随机差错：在信道上的差错是随机发生的，每个码元是否有错彼此无关。存在这种差错的信道称为无记忆信道或随机信道，例如微波接力和卫星转发等信道。突发差错：是在某一段时间内差错成片出现而在另一段时间内差错很少。线路接头接触不良、无线信道受雷电干扰等都会产生这类差错。信道差错的数学模型有很多种，在ARQ系统中使用较多的是二元对称信道模型以及修正