计算机数据通信教程第6章 差错控制.ppt

第6章 差错控制第6章 差错控制6.1 产生差错的原因6.2 差错控制方法6.3 常用的检错与纠错码 6.4 ARQ原理 习题 第6章 差错控制6.1 产生差错的原因数字信号在传输过程中通常会受到干扰的影响，使得在接收端可能发生错误判决噪声干扰造成的差错有两种，一种是在传输过程中每隔一段时间会出现一到两个误码，我们称之为随机误码；另一种是在传输过程中一小段时间内会出现大量错码，我们称之为突发误码 第6章 差错控制6.2 差错控制方法 差错控制方法，常用的有四种：1) 检错重发法(ARQ)2) 前向纠错法(FEC)3) 混合纠错法(HEC)4) 反馈检验法(IRQ)第6章 差错控制6.3 常用的检错与纠错码 差错控制能够实现的核心是采用了差错控制编码，在发送端对要传输的数据信号按照一定的规则加上一些监督码元，监督码元与信息码元之间按一定规则结合在一起形成信道编码，在接收端若发现监督码元与信息码元之间的关系与规定的规则不符，就可以检出错误和纠正错误所谓信息码元是指原始的信息数据；所谓监督码元是指为了检错和纠错而在信息码元 后增加的“冗余”码元第6章 差错控制差错控制编码是信息论中的一个重要的研究内容，差错控制编码有很多种，常见的有以下几种：(1) 根据信息码元和监督码元之间的检验关系可分为线性码和非线性码。

若信息码元和监督码元之间的关系满足二进制加法运算法则，则为线性，称为线性码；若信息码元和监督码元之间的关系不满足二进制加法运算法则，则为非线性，称为非线性码第6章 差错控制(2) 根据信息码元和监督码元之间的关系是否只局限在由当前信息码元和监督码元组成的一个码字内，可分为分组码和卷积码3) 根据接收端是只能检测出错误还是既可以检测出错误又可以纠正错误，可分为检错码和纠错码4) 根据码字中的信息码元是否与原始数据信息位一致可分为系统码和非系统码第6章 差错控制6.3.1 奇偶校验码奇偶校验码是一种最简单的检错码，在计算机的数据传输中得到了广泛的应用奇偶校验码分为两种：奇校验与偶校验其原理很简单，在信息码元后面加上一位监督码元，若信息码元与监督码元的关系是使信息码 元与监督码元组成的码字中“1”的个数为偶数个，则为偶校验；若信息码元与监督码元的关系是使信息码元与监 督码元组成的码字中“1”的个数为奇数个，则为奇校验若数据传输过程中码字中的任一位发生错误，势必破坏这种奇偶监督关系，从而可以发现错误第6章 差错控制设信息码元为，若为偶校验，则监督码元c为若为奇校验，则监督码元c为第6章 差错控制6.3.2 水平垂直校验码水平垂直校验码又称二维奇偶校验码。

发送时可以逐行传输，也可以逐列传输，接收端将接收到的数据仍排成发送时的矩阵形式，然后按照与发送端统一的校验关系检测是否有错例如，设有7个7位信息码元组成的矩阵，其奇偶监督码元(以奇校验为例)如下：第6章 差错控制信 1 0 0 1 1 1 0 10 1 0 0 1 0 0 1息 0 0 1 1 0 0 1 01 0 0 1 1 1 1 0码 1 1 1 0 0 1 0 10 1 0 1 1 0 0 0元 1 1 0 1 0 0 1 10 0 1 0 1 1 1 11 1 0 0 0 1 1 1 监 督 码 元第6章 差错控制6.3.3 海明码差错控制编码中用得较多的有一种线性分组码所谓线性分组码，它的信道编码方式是在k位信息码元后加上r位监督码元，监督码元与信息码元之间构成线性关系。

信息码元确定后，监督码元可以根据编码规则，通过 线性运算得到线性分组码构成如图6-1所示第6章 差错控制图6-1 线性分组码的构成 第6章 差错控制前面讨论奇偶校验码时，若为偶校验，则监督码元c为若为奇校验，则监督码元c为那么，在接收端译码时，只要计算第6章 差错控制若为偶校验，S=0，就认为无错；若S=1，就认为 有错若为奇校验，S = 1，就认为无错；若S = 0，就 认为有错我们把S的计算式称为监督关系式，S称为校正子在海明码中，我们将监督码元增加一位，相应地设计出两个监督关系式，得到两个校正子的值，两个 校正子就有四种可能的取值组合：00、01、10、11，表示了四种不同的情况其中一种表示无错，另外三 种则可能表示出现一个误码情况下的三个出错位置 依此类推，若有r位监督码元，就能指出一个误码情况 下的(2r –1)个出错位置，这就是海明码的工作机理第6章 差错控制一般来讲，若码长为n，信息码元的位数为k，则监督码元的位数为r=n–k，如果要求r个监督码元构造出来的监督关系式能够指出一位误码的n种可能位置，则必须满足关系式2r -1≥n 即2r≥r+k+1第6章 差错控制面以(7，4)码为例来说明海明码如何构造以及如何实现。

所谓(7，4)码，是指码长n=7，信息码元的位数k= 4的码型，为了能纠正一位误码，根据2r – 1≥n的计算式，则要求监督码元的位数r ≥3现取r=3，n=k+r=7a6 a5 a4 a3 a2 a1 a0表示这7个码元，S1、S 2、S 3为三个监督关系式中的校正子，S1、S2、S3的值与误码位置的对应关系可根据简单、有规律、易识别原则进行设定 ，设S1、S2、S3的值与误码位置的对应关系如表6-1所示(偶校验)第6章 差错控制表6-1 校正子与误码位置设定真值表 第6章 差错控制由表可知，a6、a 5、a 4、a 3、a 2、a 1、a 0与S1、S2、S3之间的函数关系式为发送端编码时，信息位a6、a5、a4、a3的值是随机的输入信息，监督位a2、a1、a0则与信息位的取值和监督关系有关，即监督位应使S1、S2、S3的值为0，表示无错，即第6章 差错控制已知信息位后，可直接根据上式计算出监督位，计算结果如表6-2所示 第6章 差错控制表6-2 发送码元真值表 第6章 差错控制接收端收到一个码组后，先根据S1、S2、S3的计算式得到S1、S2、S3的值，然后根据表6-1判断误码情况。

例如，若接收码组为1100100，则可知S1=1，S2 =0，S3=1由表6-1可知，a4出错，正确码组应为1110100海明码的编码电路也很简单，如图6-2所示 第6章 差错控制图6-2 海明码编码电路第6章 差错控制6.3.4 循环冗余校验码循环码中所谓的循环，是指若C=(Cn−1 Cn−2… C0 )是编码中的一个码字，则C循环移位(左移或右移)后所形成的码字都是该编码中的码字，即其所有码字为第6章 差错控制我们以一种(7，3)循环码为例，可得到其所有码字列表，如表6-3所示对于表中的码字，我们通常用码多项式T(x)来表示把码字中的码元当作多项式的系数(取0或1)，则n长的码字可表示为第6章 差错控制表6-3 (7, 3)循环码字 第6章 差错控制 例如(7, 3)循环码，设其信息位为111，生成多项式 g(x)=x4+x3+x2+x1，则其编码过程如下：(1) 将信息位左移n−k = 4位，得xn−k m(x)：11100002) 求余数即1110000/11101=100+0100/11101故余数为：0100(3) 合并，T(x)=xn−km(x)+r(x)，即1110000+0100 = 1110100。

循环冗余校验码的硬件实现可由移位寄存器和除法电路实现，随着微处理器和数字信号处理器的应用日益广泛，其编解 码的实现已变得较为容易第6章 差错控制6.4 ARQ原理 自动请求重发系统通常简称为ARQ系统，其基本组成方框图如图6-3所示 第6章 差错控制图6-3 ARQ系统组成方框图第6章 差错控制ARQ的具体实现可分为多种方式：第6章 差错控制6.4.1 等待式ARQ等待式ARQ是指发送端发出一帧数据后，就等待接收端的确认如果接收端确认收到的是正确的数据帧， 则向发送端发回一个确认帧ACK，发送端收到ACK后，继续发送下一个数据帧；如果接收端经差错检测确认收 到的是错误的数据帧，则向发送端发回一个否认帧NCK，发送端在收到NCK后，重发这个在传送过程中出现差错的数据帧数据帧在链路上传输有以下几种情况：正 常情况、数据帧出错、数据帧丢失、应答帧丢失如图6-4所示第6章 差错控制图6-4 数据帧在链路上传输的几种情况 (a) 正常情况；(b) 数据帧出错；(c) 数据帧丢失；(d) 应答帧丢失 第6章 差错控制6.4.2 回退N步ARQ等待式ARQ，由于每发一次数据帧后都要等待应答， 信道的利用率很低。

回退N步ARQ则是在发完每一个数据帧后，不是停下来等待应答，而是继续发送下一个数据帧 ，是一种连续式ARQ回退N步ARQ原理如图6-5所示，要 求第一帧的应答信号在第N帧尚未发送之前到达，若不能到 达，应增加帧的长度或增加N的值，图中设N=6当第一帧发出后，不等待应答信号的到达便立刻发出 第二帧、第三帧直至第N帧，若第N帧发送结束之前收到的 第一帧的应答信号为ACK，则继续发送第N+1帧，若应答 信号为NAK，则从错的那一帧开始重发，相当于回退了N步，后面的已发的帧即使正确也要进行重发 第6章 差错控制图6-5 回退N步ARQ(N=6)第6章 差错控制6.4.3 选择重传ARQ选择重传ARQ是指在传输过程中收到NAK信号后，不是回退到错误处，重新将后面所有帧全部重传，而是将已经收到的帧存储起来，只将出错的帧进行重传这就需 要接收端和发送端都具备存放N帧的缓存其原理如图6-6所示(N=6)第6章 差错控制图6-6 选择重传ARQ 第6章 差错控制6.4.4 滑动窗口协议我们知道，在连续式ARQ中，由于发送端发送的下一帧数据并不需要等到前一帧数据的ACK信号到来后再发送，为了防止重帧以及方便接收端的排序，我们通过给帧编号的方法来实现连续传输。

但如果不加限制地依次编号，帧的编号会越来越大，以至于在数据和应答帧中，编号会占去绝大部分的信道容量，这在实际应用中是绝对不允许的在这种情况下，我们引入滑动窗口协议，对收发两端进行适当的控制第6章 差错控制如图6-7所示，当发送端发完了5个帧时(0号帧至4号帧)，发送窗口已满，停止发送，进入等待设不久0号帧的确认ACK到达，则发送窗口边界右移一格，这时发送端就可以发送5号帧，因为5号帧已经在窗口中了设1、2、3号帧的确认帧ACK已到达，则发送窗口边界右移三格，继续可以发送的帧号是6、7和0号此时的0号帧由于发送窗口的限制，是在收到了前面0号帧确认信息的基础上才允许发送的，故不会与之混淆第6章 差错控制图6-7 发送窗口示意图第6章 差错控制滑动窗口协议中发送窗口的宽度WT和接收窗口的宽度WR的取值不一定要相等，不同的取值表示了不同的传输方式：(1) WT＞1，WR = 1时，滑动窗口协议即回退N步ARQ；(2) WT＞1，WR ＞1时，滑动窗口协议即选择重传ARQ；(3) WT =1时，滑动窗口协议即等待式ARQ第6章 差错控制习 题 1．什么是差错控制？为什么要进行差错控制？2．主要的差错控制有哪几种？3．什么是水平垂直校验码？请举例说明。

4．奇偶校验码与水平垂直校验码有何异同5．一码长n=15的海明码，监督位r至少应为多少？编码效率又为多少？第6章 差错控制6．简述ARQ方式的基本原理7．等待式ARQ中，应答帧为何不需要序号？8．滑动窗口协议中，窗口的大小与几种ARQ方式有何关系？。