数据通信课件第三章.ppt

1,第3章 差错控制,2,本章内容、重点和难点,本章内容 差错控制的基本概念、基本原理及基本方式。 检错与纠错的基本概念、码距与检错纠错能力。 奇偶校验码、汉明码、线性分组码、循环码和卷积码。 ARQ原理及滑窗协议。 本章重点 差错控制的基本方式。 码距与检错纠错能力。 线性分组码、循环码。 ARQ原理及滑窗协议。 本章难点 线性分组码、循环码。 ARQ原理及滑窗协议。,第3章差错控制,3,学习本章目的和要求, 了解差错控制的基本概念和基本原理。 掌握差错控制的基本方式及码距与检错纠错能力。 掌握奇偶校验码、汉明码、线性分组码和循环码的编码和解码。 掌握ARQ原理及滑窗协议。,第3章差错控制,4,3.1 差错控制的基本概念,造成误码的原因主要有：一是信道不理想造成的符号间干扰；二是噪声对信号的干扰。 对于前者通常通过均衡方法可以改善以至消除。后者是造成传输差错的主要原因。差错控制是对后者采取的技术措施，目的是提高传输的可靠性。 1差错控制的基本概念 差错即误码。差错控制的核心是差错控制编码，即在信息码元序列中加入监督码元就称为差错控制编码，也称为纠错编码。,5,3.1 差错控制的基本概念,2差错类型 噪声分为两类：随机噪声和脉冲躁声。随机噪声导致随机差错，脉冲噪声造成突发差错。 随机差错，又称独立差错，是指错码的出现是随机的，且错码之间是统计独立的。存在这种差错的信道称为随机信道，例如，微波接力和卫星转发信道。 突发差错，是指成串集中出现的错码，即在一些短促的时间区内会出现大量错码，而在这些短促的时间区间之间又存在较长的无错码区间。产生突发差错的信道称为突发信道，如短波等信道。 既存在随机差错又存在突发错误，且哪一种都不能忽略不计的信道称为混合信道。,6,3.2 差错控制的基本方式与基本原理,1差错控制的基本方式 常用的差错控制方式一般有下面4种类型，如图3-1所示。 （1）检错重发（又称自动请求重发ARQ），如图3-1（a）。 这种差错控制方式是在发送端对数据序列按一定的规则进行编码，使之具有一定的检错能力，成为能够检测错误的码组（检错码）。接收端收到码组后，按编码规则校验有无错码，并把校验结果通过反向信道反馈到发送端。如无错码，就反馈继续发送信号。如有错码，就反馈重发信号，发送端把前面发出的信息重新传送一次，直到接收端正确收到为止。 优点：检错码构造简单，插入的监督码位不多，设备不太复杂。缺点：实时性差，且必须有反向信道，通信效率低。,7,3.2 差错控制的基本方式与基本原理,图3-1 差错控制的基本类型,8,3.2 差错控制的基本方式与基本原理,（2）前向纠错（简称FEC） 前向纠错系统中，发送端的信道编码器将输入数据序列按某种规则变换成能够纠正错误的码，接收端的译码器根据编码规律不仅可以检测出错码，而且能够确定错码的位置并自动纠正。如图3-1（b）所示。 优点：不需要反馈信道，也不存在由于反复重发而延误时间，实时性好。 缺点：附加的监督码较多，传输效率低，纠错设备比检错设备复杂。,9,3.2 差错控制的基本方式与基本原理,（3）混合纠错检错 混合纠错检错方式是前向纠错方式和检错重发方式的结合，如图3-1（c）所示。 在这种系统中，发送端发送同时具有检错和纠错能力的码，接收端收到码后，检查错误情况，如果错误少于纠错能力，则自行纠正；如果错误很多，超出纠错能力，但未超出检错能力，即能判决有无错码而不能判决错码的位置，此时收端自动通过反向信道发出信号要求发端重发。 混合纠错检错方式在实时性和译码复杂性方面是前向纠错和检错重发方式的折衷，在数据通信系统中采用较多。,10,3.2 差错控制的基本方式与基本原理,（4）反馈校验 反馈校验方式又称回程校验，如图3-1（d）所示。 接收端把收到的数据序列原封不动地转发回发送端，发端将原发送的数据序列与返送回的数据序列比较。如果发现错误，则发送端进行重发，直到发端没有发现错误为止。 优点：不需要纠错、检错的编解码器，设备简单。 缺点：需要有双向信道，实时性差，且每一信码都相当于至少传送了两次，所以传输效率低。,11,3.2 差错控制的基本方式与基本原理,2差错控制的基本原理 差错控制的核心是差错控制编码，不同的编码方法，有不同的检错或纠错能力，有的编码只能检错，不能纠错。一般，付出的代价越大，检（纠）错的能力就越强。 纠错编码之所以具有检错和纠错能力，是因为在信息码之外附加了监督码。监督码不载荷信息，它的作用是用来监督信息码在传输中有无差错，对用户来说是多余的，但它提高了传输的可靠性。但是，监督码的引入，降低了信道的传输效率。 因此，通过纠错编码所提高的可靠性是以牺牲信道利用率为代价换取的。一般说来，引入监督码越多，码的检错、纠错能力越强，但信道的传输效率下降也越多。,12,3.3 检错与纠错的基本概念,3.3.1 码距与检错纠错能力 1基本概念 码重：码组中非零码元的数目为码组的重量，简称码重。例如，“010”码组的码重为1，“011”码组的码重为2。 码距：把两个码组中对应码位上具有不同二进制码元的位数定义为两码组的距离，简称码距。例如，（00）与（01）码距为1，（110）与（101）码距为2。 汉明距离：在一种编码中，任意两个码组间距离的最小值，称为这一编码的最小码距或称为这一编码的汉明（Hamming）距离，以dmin表示。如，在3位码组中，若8种码组都作为许用码组时，任意两码组间的最小距离为1，记作dmin=1。对于 的编码组，可以在三维空间中说明码距的几何意义。如图3-2所示。,13,3.3.1 码距与检错纠错能力,图3-2 码距的几何解释,图3-3 码距与检错纠错能力的关系,14,3.3.1 码距与检错纠错能力,2码距与纠检错能力 （1）为检测e个错码，要求最小码距 dmine+1（3-1） （2）为纠正个错码，要求最小码距 dmin2t+1（3-2） （3）为纠正个错码，同时检测e（et）个错码，要求最小码距 dmin e+t+1（3-3） 上述三式可以分别用图3-3（a）、 （b）和（c）来加以说明。 纠检结合：在某些情况下，要求对于出现较频繁但错码数很少的码组，按前向纠错方式工作；同时对一些错码数较多的码组，在超过该码的纠错能力后，能自动按检错重发方式工作，以降低系统的总误码率。这种方式就是“纠检结合”。,15,3.3.2 编码效率,编码效率是指一个码组中信息位所占的比重，用R来表示。即 （3-4） 其中，k为信息码元的数目（信息位长度）；n为编码组码元的总数（编码后码组长度：n=k+r）；r 为监督码元的数目（监督位长度）。 显然，R越大编码效率越高。,16,3.3.3 纠错编码分类,（1）按码组的功能分，有检错码和纠错码两类。 在译码器能够检测出错码，但不知道错码的准确位置的码，称为检错码，它没有自动纠正错误的能力。 在译码器中不仅能发现错误，而且知道错码的准确位置，自动进行纠正错误的码，则称为纠错码。 （2）按码组中监督码元与信息码元之间的关系分，有线性码和非线性码两类。 线性码是指监督码元与信息码元之间的关系呈线性关系，即可用一组线性代数方程联系起来；非线性码指的是二者是非线性关系，目前很少使用。,17,3.3.3 纠错编码分类,（3）按照信息码元与监督码元的约束关系，又可分为分组码和卷积码两类。 分组码是将信息序列以每k个码元分组，通过编码器在每k个码元后按照一定的规则产生r 个监督码元，组成长度为n=k+r 的码组，每一码组中的r 个监督码元仅监督本码组中的信息码元，而与别组无关。分组码一般用符号（n，k）表示，其结构规定为图3-4的形式。分组码又可分为循环码和非循环码两类。 卷积码是把信源输出的信息序列，以每k0个码元分段，通过编码器输出长为n0（n0k0）的一段码。但该段码的（n0 k0）个监督码元不仅与本段码信息码元有关，而且还与前面m1段的信息码元有关，前后形成了约束关系。一般用（ n0, k0 ,m）表示。,18,3.3.3 纠错编码分类,（4）按照信息码元在编码前后是否保持原来的形式不变，可划分为系统码和非系统码。 系统码的信息码元和监督码元在分组内有确定的位置，而非系统码中信息码元则改变了原来的信号形式。系统码的编码和译码相对比较简单些，得到广泛应用。 （5）按纠正差错的类型可分为纠正随机错误的码和纠正突发错误的码。 （6）按照每个码元取值来分，可分为二进制码与多进制码。 图3-5示出了各种抗干扰编码的类型。,19,3.3.3 纠错编码分类,图3-5 抗干扰码的分类,图3-4 分组码的结构,20,3.4 几种差错控制编码介绍,常用的差错控制编码有： 奇偶校验码 线性分组码 循环码 卷积码,21,3.4.1 奇偶校验码,奇偶校验码是一种检错码，又称奇偶监督码，属于分组码。 1一般奇偶校验码 奇偶校验码分奇校验码和偶校验码，两者构成原理是一样的。 （1）基本原理 在奇偶校验码中，无论信息位有多少位，校验位只有一位。 编码规则：先将所要传输的数据码元分组，在分组数据后面附加一位校验位，使得该组码连同校验位在内的码组中的“1”的个数为偶数（称为偶校验）或奇数（称为奇校验），在接收端按同样的规律检查，如发现不符就说明产生了差错，但是不能确定差错的具体位置，即不能纠错。,22,3.4.1 奇偶校验码,在偶检验时，满足下式条件 （3-5） 在奇校验时，满足下式条件 （3-6） 表3-1是按偶校验规则插入监督位的。 （2）纠错能力 只能发现单个或奇数个错误，而不能检测出偶数个错误。被用于以随机错误为主的计算机通信系统。此方法难于对付突发错。,表3-1 偶校验监督码,23,3.4.1 奇偶校验码,2垂直奇偶校验码 （1）基本原理 垂直奇偶校验是在b7位表示字符的数据位后再附加第b8位校验位，表3-2以ASCII码的数字09为例说明垂直奇偶校验的编码。 接收端根据收到的b1 b7重新计算奇偶校验码元，将此与收到的b8相比较。如相同则无错，否则存在错误。 （2）纠错能力 垂直奇偶校验编码，无论是采用偶校验还是奇校验，将检出全部奇数个差错，而出现的全部偶数个差错均不能发现。,24,3.4.1 奇偶校验码,表3-2垂直奇偶校验,25,3.4.1 奇偶校验码,3水平奇偶校验码 （1）基本原理 将要进行奇偶校验的码元序列按行排成方阵，每行为一组奇偶校验码（见表3-3），但发送时则按列的顺序传输，接收端仍将码元排成发送时的方阵形式，然后按行进行奇偶校验。 （2）纠错能力 可发现某一行上所有奇数个错误及所有长度方阵中行数的突发错。,表3-3水平奇偶校验码,26,3.4.1 奇偶校验码,4二维奇偶校验码 （1）基本原理 二维奇偶校验码又称行列校验码或方阵码。其方法是水平监督的基础上对表3-3方阵中每一列再进行奇偶校验，就可得到表3-4所示的方阵。发送是按列序顺次传输。,表3-4二维奇偶校验码,27,3.4.1 奇偶校验码,（2）纠错能力 能发现某行或某列上的奇数个错误和长度不大于行数（或列数）的突发错误。 有可能检测出偶数个错码。因为如果每行的监督位不能在本行检出偶数个错误时，则在列的方向上有可能检出。当然，在偶数个错误恰好分布在矩阵的4个顶点时，这样的偶数个错误检测不出来。 可以纠正一些错误。例如，当某行某列均不满足监督关系而判定该行该列交叉位置的码元有错，从而纠正这一位上的错误。 检错能力强，又有一定纠错能力，且实现容易得到广泛应用。,28,3.4.2 汉明码及线性分组码,1汉明码 汉明码是一种能够纠正一位错码且编码效率较高的线性分组码。 （1）基本原理 奇偶校验时，如按偶校验，由于使用了一位监督位a0，故它就能和信息an1 an2 a1一起构成一个代数式，如式（3-5）所示。在接收端解码时，实际上就是在计算 （3-7） 若S=0，就认为无错；若S=1，则认为有错。上式称为监督关系式，S 称为校正子。一个校正子S只有0和1两种取值，只能代表有错和无错两种信息，而不能指出错码的位置。,29,3.4.2 汉明码及线性分组码,如果监督位增加一位，即变成两位，则将增加一个类似于式（3-7）的监督关系式，接收时按照两个监督关系式就可计算出两个校正子，记作S1和S2。 S1 ，S2共有4种组合：00，01，10，11，故能表示4种不同信息。若用其中一种表示无错，则其余221=3种就有可能用来指示一位错码的3种不同位置。 同理，若有r位监督位，就可构成r个监督关系式，计算得出的校正子有r 位，可用来指示一位错码的2r1个可能位置。 一般来说，若码长为n，信息位数为k，则监督位数r=nk。若用r个监督位构造出r个监督关系式来指示一位错码的n种可能位置，则要求 2r1n或2r k+r+1（3-8） 上式是汉明码的必要条件。,30,3.4.2 汉明码及线性分组码,（2）编码示例 设分组码（n，k）中k=4。为了纠正一位错码，由式（3-8）可知，要求监督位数r3。 若取r =3，则n=k+r=7。用a6a5a0表示这7个码元，用S1，S2 ，S3 表示3个监督关系式中的校正子，则S1，S2 ，S3 的值与错码位置的对应关系可以规定如表3-5所列。,表3-5校正子与错码的位置,31,3.4.2 汉明码及线性分组码,由表3-5的规定可知，仅当发生一个错码，其位置在a2 ，a4 ，a5或a 6， 校正子S1为1，否则为0。这就意味着a2 ，a4， a5和a 6 四个码元构成偶数监督关系，即 （3-9） 同理 a1 ，a3 ，a5和a 6及a0 ，a3 ，a4和a 6 也分别构成偶数监督关系 （3-10） （3-11） 发送端编码时，监督位应使上3式中的S1，S2，S3均为0，于是有：,（3-12） 解出,（3-13）,已知信息位，就可算出监督位。由此得出如表3-6所示许用码组。,32,3.4.2 汉明码及线性分组码,接收端收到每个码组后，先按式（3-9），式（3-10）和式（3-11）计算出S1，S2和S3，如不全为0，再按表3-5确定误码的位置，然后加以纠正。例如，若接收码组为0100101，按式计算可得： S1 =0， S2 =1， S3 =1，由表3-5可知在a3位有一错码。,表3-6（7，4）汉明码的许用码组,33,3.4.2 汉明码及线性分组码,（3）纠检错能力 按上述方法构成的码称为汉明码。表3-6所列的（7，4）汉明码的最小码距dmin=3，因此，根据式（3-1）和式（3-2）可知，这种码能纠正一个错码或检测两个错码。 （4）编码效率 汉明码有着较高的编码效率，它的效率为 当n很大时，编码效率接近1，可见汉明码是一种高效码。,34,3.4.2 汉明码及线性分组码,2线性分组码 （1）监督矩阵 线性分组码是指分组码中信息码元和监督码元是用线性方程联系起来的一种差错控制码。如（7，4）汉明码，式（3-12）就是一组线性方程的例子。现将它改写成 （3-14） 上式中已将“”简写为“+”，仍表示“模2”加。,35,3.4.2 汉明码及线性分组码,式（3-14）也可以写成矩阵形式 （模2）（3-15） 简记为 HA T=0T或AH T=0 （3-16） 其中 H = A=a6 a5 a4 a3 a2 a1 a0 0=0 0 0,H 称为线性码的监督矩阵。H 给定，监督位和信息位的关系就定了。,36,3.4.2 汉明码及线性分组码,从式（3-14）和式（3-15）都可看出，H 的行数就是监督关系式的数目，它等于监督码元的数目r，而H 的列数就是码长n，这样H 为rn 阶矩阵。 式（3-15）中的矩阵H 可以分成两部分 （3-17） 式中P为rk阶矩阵，Ir为rr 阶单位方阵。将具有PIr形式的H 矩阵称为典型形式的监督矩阵。,37,3.4.2 汉明码及线性分组码,（2）生成矩阵 类似于式（3-12）改变成式（3-15）中矩阵形式那样，式（3-13）也可以改写成 （3-18） 比较式（3-17）和式（3-18），可以看出式（3-18）右式前部矩阵即为P。对式（3-18）两侧作矩阵转置，得 Q （3-19）,38,3.4.2 汉明码及线性分组码,式中Q为一kr 阶矩阵，它为矩阵P的转置，即 Q=P T （3-20） 式（3-19）表明，信息位给定后，用信息位的行矩阵乘矩阵Q就可计算出各监督位。 要得到整个码组，将Q的左边加上一个kk阶单位方阵，就构成一个新的矩阵G，即 （3-21） G 称为生成矩阵，因为由它可以产生码组，即有 A=a6a5a4a3a2a1a0=a6a5a4a3G （3-22）,39,3.4.2 汉明码及线性分组码,上式表明，如果找到了码的生成矩阵G，则编码的方法就完全确定了。具有IkQ形式的生成矩阵称为典型生成矩阵。 【例3-1】设（7，4）线性码的生成矩阵为 ，当信息位为0001时，试求其后的监督位，并求G的监督矩阵H。 解 （1）根据G 可知 ，由式（3-19）可知,40,3.4.2 汉明码及线性分组码,所以当信息位为0001时，其监督位为011。 （2） 又P=QT可知 所以 H=PIr=,41,3.4.2 汉明码及线性分组码,（3）校正子和检错 发送的码组A在传输中可能出现误码，因此接收码组一般说来与A不一定相同。若设接收码组为一n列的行矩阵R，即 R=rn1,rn2, r0（3-23） 则发送组和接收码组之差为 RA=E （模2）（3-24） E就是传输中产生的错码行矩阵，且 E =en1,en2,e0（3-25） 式中 若ei=0表示无错；若ei=1，则表示有错。如，若发送码组A=1000111，接收码组R=1000011，则错码矩阵E=0000100。,42,3.4.2 汉明码及线性分组码,接收端译码时，按下式计算可将接收码组R代入式（3-16）中计算。假设式（3-16）的右端为S，则 RH T=S （3-26） 将R=A+E 代入上式，可得 S=(A+E)H T=AH T+EH T （3-27） 由式（3-16）知AH T=0，所以 S=EH T （3-28） 由上式可知，S（校正子或监督子）只与E有关，而与A无关，即校正子S与错误图样E之间有确定的线性变换关系，因此可以根据校正子S与错误图样E的关系表中确定错码位置。如表3-5那样。,43,3.4.2 汉明码及线性分组码,（4）线性分组码主要性质 封闭性 所谓封闭性，是指一种线性码中的任意两个许用码组之和（逐位模2和）仍为这种码中的一个许用码组。 码的最小距离等于非零码的最小重量 线性分组码具有封闭性，因而两个码组之间的距离必是另一码组的重量。故码的最小距离即是码的最小重量（除全“0”码组外）。 监督关系 在线性码中，码组中的监督码元并不固定地监督某位或某几位信息码元，而是码组中的所有监督码元共同监督码组中的所有信息码元和监督码元。,44,3.4.3 循环码,1循环码的特性 循环性：循环码中任一许用码组经过循环移位后（将最右端的码元移至左端，或相反）所得到的码组仍为该码集中的一许用码组。表3-7可以直观看出这种码组的循环性 。 封闭性：一个码集中的任何两个码组相加后所得到的新的码组仍是该码集中的一个码组。 表3-7（7，3）循环码的一种码组,45,3.4.3 循环码,2循环码的码多项式 若一个码组A=(an1, an2, a1 , a0 )，用相应的多项式表示为 A(x)=(an1 xn1+ an2xn2+a1x+a0) （3-29） 称A(x)为码组A的码多项式。 表3-7中的（7，3）循环码中的任一码组可以表示为 A(x)=(a6x6+a5x5+a4x4+a3x3+a2x2+a1x1+a0) 例如，表中的第7码组可以表示为 （3-30） 在这种多项式中，x仅是码元位置的标记。称这种多项式为码多项式。,46,3.4.3 循环码,3码多项式的按模运算 在整数运算中，有模运算。一般来说，若一整数可以表示为 pn 式中Q为整数。在模n运算下，有 mp （模） 若一任意多项式F(x)被一n次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即 或F (x)=N(x)Q(x)+R(x)（3-31） 则写为 F(x)R(x) （模N(x)）（3-32）,47,3.4.3 循环码,例如，x3被（x3+1）除得余项1，即 则有 x31 （模x3+1） 同理 x5+x2+1x2+x+1 （模x4+1） 就循环码来说，若是一个长为n的许用码组A(x)，则xi A(x)在按模（xn+1）运算下，亦是一个许用码组，即若 xi A(x)A (x) （模xn+1）（3-33） 则A (x)也是一个许用码组。 可见：一个长为n的（n,k）循环码，它必是按模（xn+1）运算的一个余式。,48,3.4.3 循环码,4循环码的生成多项式和生成矩阵 （1）循环码的生成多项式 在循环码中，一个（n,k）码有2k个不同的码组。若用g(x)表示其中前（k1）位皆为“0”，而第k位及第n位为1的码组为循环码的一个许用码组，根据循环性，按式（3-33），则xg(x)，x2g(x)，xk1g(x)都是它的许用码组，连同g(x)共同构成k个许用码组，即为所要求的码组，而g(x)称为生成多项式，一旦确定了g(x)，则整个（n,k）循环码就可确定了。,49,3.4.3 循环码,由上述定义可知，g(x)具有如下特点。 g(x)连“0”的长度最多只能有（k1）位。 g(x)必是一个常数项为“1”的码多项式。 g(x)的最高幂次为nk次。 即g(x)是幂次大于（nk）的系数为“0”，xnk及x0的系数为“1”，其他系数为“0”或“1”的码多项式。我们称这唯一的（nk）次多项式g(x)为循环码的生成多项式。 可以证明，生成多项式g(x)必定是（xn+1）的一个（nk）因式，证明从略。,50,3.4.3 循环码,（2）循环码的生成矩阵 由循环码的生成多项式可得出其生成矩阵G为 G(x)= （3-37） 例如，在表3-7所给出的循环码中，n=7，k=3，nk=4。可见，唯一的一个nk=4次码多项式代表的码组是第二码组0010111，相对应的码多项式（即生成多项式）g(x)=x4+x2+x+1。将此g(x)代入上式，则其生成矩阵为,51,3.4.3 循环码,G(x)= 或表示成 G = （3-38） 上例中的G不符合G=IkQ形式，将其转换成为典型的生成矩阵，即 G= =IkQ （3-39） 将三位信息位a6a5a4与G相乘便可得到全部码组，即 A=a6a5a4G，如表3-7所示。,52,3.4.3 循环码,5循环码的编码方法 设信息位的码多项式表示为 m(x)=mk1xk1+mk2xk2+m1x+m0（3-40） 其中系数mi 为1或0。 信息位在循环码的码多项式中应表现为多项式xnkm(x)（成为最高幂次为nk+k1=n1）。显然 xnkm(x)=mk1xn1+mk2xn2+m1xnk+1+m0 xnk 它从幂次xnk1起至x0的（nk）位的系数都为0。 若用g(x)除xnkm(x)可得 式中，r (x)为幂次小于（nk）的余式。,53,3.4.3 循环码,上式可改写成： xnkm(x)+r (x)=Q(x)g(x) （3-41） 上式表明，多项式xnkm(x)+r(x)为g(x)的倍式，则xnkm(x)+r(x)必定是由g(x)生成的循环码中的码字，而r(x)为该码字的监督码元所对应的多项式。 由此，可得到循环码的编码原则。 （1）用xnk乘m(x)。实际上是把信息码后附上（nk）个“0”。 （2）用g(x)除xnkm(x)，得到商Q(x)和余式r(x)，即 （3-42） （3）联合xnkm(x)和r (x)得到系统码多项式，编出的码组A(x)为 A(x)=xnkm(x)+r(x) （3-43）,54,3.4.3 循环码,【例3-2】使用生成多项式g(x)=x4+x3+1产生m(x)=x7+x6+x5+x2+x 对应的循环码组。 解 用xnk乘m(x)得 用g(x)除xnkm(x)，得余式r(x) 所以r(x)=x2+x。 联合xnkm(x)和r(x)得到系统码多项式A(x) A(x)=x11+x10+x9+x6+x5+x2+x 得码组A=111001100110,55,3.4.3 循环码,6循环码的解码方法 在接收端可以将接收码组R(x)用原生成多项式g(x)去除。即有 （3-44） 当余项为零时，无错码，当余项不为零时有错码。如图3-6所示。,图3-6 循环码解码示意图,注：如果信道中错码的个数超过于这种编码的检错能力，恰好使有错码的接收码组能被g(x)所整除。这种错误称为不可检错误。,56,3.4.3 循环码,【例3-3】一组8比特的报文块（帧）11100110通过数据传输链路传输，采用CRC进行差错检测，如用的多项式为11001，试举例说明：（a）FCS的产生过程；（b）FCS的检测过程。 解 对于报文11100110的FCS的产生如图3-7（a）所示。 在接收机上，整个接收的比特序列被同一生成多项式除，如图3-7（b）所示。第一个例子中没发生错误，得到的余数为0；第二个例子中，在发送比特序列的末尾发生了4bit的突发差错，得到的余数不为0，说明传输出现了差错。,57,3.4.3 循环码,图3-7 FCS编译码举例,58,3.4.3 循环码,纠错可按下述步骤进行。 （1）用生成多项式g(x)除接收码组R(x)=A(x)+E(x)，得出余式r (x)。 （2）按余式r (x)用查表的方法或通过某种运算得到错误图样E(x)，例如，通过计算校正子和利用类似表3-5的关系，就可确定错码的位置。 （3）从R(x)中减去E(x)，便得到已纠正错误的原发送码组A(x)。 7常用的CRC码：如表8-3所示。,表3-8 常用的CRC码,59,3.4.4 卷积码,卷积码又称连环码，是一种非分组码，主要应用于前向纠错（FEC）数据通信系统中。 1基本概念 卷积码是在任何一段规定时间内编码器产生的n个码元，不仅取决于这段时间中的k个信息码元，而且还取决于前N1段规定时间内的信息码元。这时，监督位监督着这N段时间内的信息。 这N段时间内的码元数目nN 称为这种码的约束长度。通常把卷积码记作（n,k,N），其编码效率为R=k/n。 2编码原理 如图3-8和图3-9所示。这种卷积码的参量为k=1，n=2，N=6，约束长度为nN=12。,60,3.4.4 卷积码,图3-8 一种卷积码编码器,图3-9 一种卷积码编码器的输入与输出关系,61,3.4.5 滑窗协议,ARQ分为停等式ARQ和连续式ARQ，连续式ARQ又分为退回N步ARQ和选择重发ARQ。 1停等式ARQ （1）工作原理 发送方每发完一数据帧，停下来等待接收方应答，同时启动超时定时器，若发送方收到一确认帧，接着发送下一数据帧，若接收到一否认帧或超时定时器到时仍未收到对方应答则重发上一数据帧。 接收方每收到一帧都要给出应答，若收到一正确帧或重发帧，发回确认帧，若收到一错误帧，发回否认帧。 （2）收发示例：如图3-10（a）所示。 （3）特点：传输效率低，但工作原理简单。,62,3.4.5 滑窗协议,2退回N步ARQ （1）工作原理 发端可不等待应答信号到达连续发送若干个数据帧（N帧），且每发完一帧后，都启动超时定时器，若发方收到第一帧的确认帧，继续发送第（N+1）帧，若接收到一否认帧或超时定时器到时仍未收到对方应答，则重发自该帧起的所有数据帧，即重发前N帧。 接收端接收到若干数据帧后发回应答，确认帧表示正确接收该帧及以前各帧，否认帧表示对当前帧的否认，同时也表示对以前各帧的确认。接收方只能按序接收，若收到乱序的帧，则一律丢弃。 （2）收发示例：如图3-10（b）所示。这里N5。 （3）特点：传输效率较高。但当N较大时，效率会大大下降。,63,3.4.5 滑窗协议,3选择重传ARQ （1）工作原理 在退回N步ARQ基础上，当一个帧有错时，只发有错的这一帧，其余（N1）个正确帧先接收存储起来，待有错帧经重发正确后，一起再发确认帧，收端将收到的帧重新排序，送给用户。 （2）收发示例： 如图3-10（c）所示。 （3）特点：传输效率最高，但它的成本也最贵，接收端必须有足够的存储空间，把接收到的帧重新排序后送给用户。 可见，选择重传ARQ方式可以接收乱序帧，而退回N步ARQ方式的收端只能按顺接收。,64,3.4.5 滑窗协议,图3-10 ARQ差错控制系统的工作方式,65,3.4.5 滑窗协议,4滑动窗口 （1）发送窗口 发送窗口是指发端在未收到确认的条件下，最多可以连续发送数据帧的数量。用“WT”表示发送窗口。如图3-11所示， WT =5。 （2）滑窗协议 接收窗口是接收站需要帧缓存的最大个数，用“WR ” ，如图3-12所示，只有当接收的帧号落在接收窗口内时才允许将该帧收下。 当接收窗口保持不动时， WT 无论如何不会旋转，只有当WR发生旋转后， WT 才可向前旋转，收发窗口按照此规律不断沿顺时针方向旋转（滑动），因此这种协议称作滑窗协议。 引入“窗口”概念后，我们可用有限的位数来表示帧的序号，并可进行流量控制。发送窗口和接收窗口在帧序号上滑动。,66,3.4.5 滑窗协议,图3-11 发送窗口控制发端的发送速率,图3-12 接收窗口的意义,67,3.4.5 滑窗协议,说明： 发送窗口宽度WT和接收窗口宽度WR可以不等。 当WT 1而WR =1时，滑动窗口协议即为退回N步ARQ。 当WT 1而WR1时，滑动窗口协议即为选择重传ARQ。 当WT =1， WR =1，滑动窗口协议即为停等式ARQ。 “捎带”确认。为提高信道利用率，采用“捎带”法返回应答帧。 滑窗协议不仅起差错控制的作用，而且也用于进行流量控制。 窗口大小。如表3-9所示。 表3-9发送窗口和接收窗口的限度,68,小结,1数据通信中，降低误码率的基本方法是采用差错控制编码。 2在一种码的集合中码组间的最小码距称为汉明距离。最小码距和它的检错能力之间存在一定的关系。 3差错控制方式分为检错重发、前向纠错、混合纠错和信息反馈。 4常用的差错控制编码有：奇偶监督码、汉明码、线性分组码、循环码和卷积码等。 5在线性分组码中，当用个监督位来指示一位错码的种可能的位置时，要求2r1n，或2rk+r+1。 6循环码是除了具有线性码的一般性质外，还有循环性。介绍了循环码的生成、编码和解码。,69,小结,8卷积码是一种非分组码，它在规定的N段时间内编码器产生的码元不仅决定于这段时间的k位信息码元，而且还决定于前N1段时间的信息码元。 9ARQ分为停等式ARQ和连续式ARQ，连续式ARQ又分为退回步ARQ和选择重发ARQ。停等式ARQ传输效率最低，退N步ARQ居中，而选择重传ARQ的传输效率最高。另选择重传ARQ可以接收乱序帧，而退步ARQ只能按顺接收。 10当WT1而WR=1时，为退N步ARQ。当WT1，WR1时，为选择重传ARQ。当WT =1，WR=1，为停等式ARQ。退回N步ARQ协议的WR=1时， WT 2n1，而选择重传ARQ协议的 ， 。,