第11章差错控制编码课件.ppt

第11章 差错控制编码,11.1 概述 11.2 纠错编码的基本原理 11.3 纠错编码的性能11.4 简单的实用编码 11.5 线性分组码11.6 循环码,11.1 概述,从差错角度看，按加性干扰引起的错码分布规律的不同，信道可以分为三类：（1）随机信道：在此信道中错码的出现是随机的，且错码之间是统计独立的。（2）突发信道：在此信道中错码是成串集中出现的，（3）混合信道：既存在随机错码又存在突发错码，且哪一种都不能忽略不计的信道 对于不同类型的信道，应采用不同的差错控制技术。,差错控制方法，常用 的有以下几种（1）检错重发法（ARQ）接收端在收到的信码中检测出（发现）错码时，即设法通知发送端重发，直到正确收到为止。所谓检测出错码是指在若干接收码元中知道有一个或一些是错的，但不一定知道该错码的准确位置。采用这种差错控制方法需要具备双向信道。,（2）前向纠错法（FEC）接收端不仅能在收到的信码中发现有错码，还能够纠正错码。对于二进制系统，如果能够确定错码的集团，就能够纠正它。这种方法不需要么向信道，也不存在由于反复重发而延误时间，实时性好，但是纠错设备要比检错设备复杂。,（3）反馈校验法（IF）接收端将收到的信码原封不动地转发回发送端，并与原发送信码相比较。如果发现错误，则发送端再进行重发。这种方法原理和设备都较简单，但需要有双向信道。传输效率较低。,(4)检错删除：它和检错重发的区别在于，在接收端发现错码后，立即将其删除，不要求重发。这种方法只适用在少数特定系统中，在那里发送码元中有大量多余度，删除部分接收码元不影响应用。,当出现少量错码并在接收端能够纠正时，即用前向纠错法纠正；当错码较多而超过纠正能力但尚能检测时，就用检错重发法。此外，在某些特定场合，可采用检错删除法，即接收端将其中存在错误的部分码元删除，不送给输出端。此法适用于信息内容有大量多余度或多次重复发送的场合。,为使接收端能够识别接收到的信码有无错码。可以由发送端的信道编码器在信息码元序列中增加一些监督码元。这些监督码元和信码之间有一定的关系，使接收端可以利用这种关系由信道译码器来发现或纠正可能存在的错码。,在信息码元序列中加入监督码元就称为差错控制编码，也称为纠错编码。不同的编码方法，有不同的检错或纠错能力，有的编码只能检错，不能纠错。一般来说，编码中增加的监督码元越多，它检（纠）错的能力就越强，但它的编码效率（或传码率）也就越低。,可见，差错控制编码原则上是以降低信息传输速率为代价来换取提高传输可靠性。,ARQ方式的主要优点是：（1）只需要少量的多余码元就能获得极低的输出误码率；（2）要求使用的检错码基本上与信道的差错统计特性无关；（3）其检错译码器与前向纠错法中的纠错译码器相比，成本和复杂性均低得多。,但其缺点是：（1）由于需要反向信道，故不能用于单向传输系统，并且实现实现重发控制比较复杂；（2）当信道干扰增大时，整个系统可能处在重发循环中，因而通信效率降低，甚至不能通信；（3）不大适于要求严格实时传输的系统。,11.2 纠错编码的基本原理,在讨论检错和纠错问题之前，我们先介绍一下数字通信中码元的两种错误形式：随机错误和突发错误。(1)随机错误。由随机噪声引起的码元错误，其特点是码元中任意一位或几位发生从0变1或从1变0的错误是相互独立的，彼此之间没有联系，一般不会引起成片的码元错误。,(2)突发错误。由突发噪声引起的码元错误，比如，闪电、电器开关的瞬态、磁带缺陷等都属于突发噪声。该错误的特点是各错误码元之间存在相关性，因此是成片出现，也就是说突发错误是一个错误序列，该序列的首部和尾部码元都是错的，中间的码元有错的也有对的，但错的码元相对较多，错误序列的长度（包括首和尾在内的错误所波及的段落长度）称为突发长度。,假设要发送一组具有八个状态的数据信息“000”（晴），“001”（云），“010”（阴），“011”（雨），“100”（雪），“101”（霜），“110”（雾），“111”（雹）。我们首先要用二进制码对数据信息进行编码，显然，用3位二进制码就可完成。但任一码组在传输中若发生一个或多个错码，则将变成另一信息码组。这时，接收端将无法发现错误。,因此，以这种编码形式得到的数字信号在传输过程中不具备检错和纠错的能力，这是我们所不希望的。但若在上述8种码组中只准许使用4种来传送信息，如：“000”（晴），“011”（云），“101”（阴），“110”（雨），这时，虽然只能传送4种不同的信息，但是接收端却有可能发现码组中的一个错码。,在许用码组000、011、101、110中，右边加上的1位码元就是监督码元，它的加入原则是使码组中1的个数为偶数，这样监督码元就和前面2位信息码元发生了关系，这种编码方式称为偶校验，反之，如果加入原则是使码组中1的个数为奇数，则编码方式称为奇校验。现在我们再看一下出现误码的情况，假设许用码组000出现1位误码，即变成001、010或100三个码组中的一个，可见这三个码组中1的个数都是奇数，是禁用码组。,信息位和监督位关系,因此，当收信端收到这三个码组中的任何一个时，就知道是误码，用这种方法可以发现1位或3位出现错误的码组，而无法检出2位错误，因为一个码组出现2位错误，其奇偶性不变。那么，收信端能否从误码中判断哪一位发生错误了呢（即纠正错误）？比如对误码001而言，如果是1位发生错误，原码可能是000、101或011；如果3位都错，原码就是110，我们现在无法判断出原码到底是哪一组。也就是说，通过增加1位监督码元，我们可以检出1位或3位错误（3位出错的概率极小），但无法纠正错误。,要想纠正错误，还要增加多余度。即通过增加监督码元的位数来增加检错位数或实现纠错功能。如规定许用码组只有两个：“000”（晴）、“111”（雨），其它都是禁用码组，则能够检测两个以上错码，或能够纠正一个错码。,可见，简单地增加1位监督码元并没有提高检错与纠错能力，那么，检错与纠错能力到底与什么有关呢？在回答这个问题之前，我们先介绍分组码的概念：将信息码分组，为每组信码附加若干监督码的编码方式称为分组码。在分组码中，监督码元仅监督本码组中的信息码元。,分组码一般用符号（n，k）表示，若中n是码组的总位数，又称为码组的长度（码长），k是码组中信息码元的数目，n-k=r为码组中的监督码元数目，或称监督位数目。在分组码中，把码组中“1”的个数称为码组的重量，简称码重。把两个码组中对应位上数字不同的位数称为码组的距离，简称码距。码距又称汉明距离。,码距反映的是码组之间的差异程度，比如，00和01两组码的码距为1；011和100的码距为3。那么，多个码组之间相互比较，可能会有不同的码距，其中的最小值被称为最小码距（用d0表示）。比如，000、001、110三个码组相比较，码距有1和2两个值，则最小码距为1。,根据理论推导，可以得出以下结论：(1)在一个码组内要想检出e位误码，要求最小码距为 d0e+1(2)在一个码组内要想纠正t位误码，要求最小码距为 d02t+1(3)在一个码组内要想纠正t位误码，同时检测出e位误码（et）,要求最小码距为 d0t+e+1（et）,显然，要提高编码的纠、检错能力，不能仅靠简单地增加监督码元位数（即冗余度），更重要的是要加大最小码距（即码组之间的差异程度），而最小码距的大小与编码的冗余度是有关的，最小码距增大，码元的冗余度就增大，但码元的冗余度增大，最小码距不一定增大。因此，一种编码方式具有检错和纠错能力的必要条件是信息编码必须有冗余，而充分条件是码元之间要有一定的码距。,11.3 纠错编码的性能,由纠错编码原理可知:（1）为减少接收错误码元数量，需要在发送信息码元序列中加入监督码元。结果使发送序列增长，冗余度增大。（2）若仍须介质发送信息码元速率不变，则传输速率必须增大。结果增大了系统带宽。（3）系统带宽的增大将引起系统中噪声功率增大，使信噪比下降。结果使系统接收码元序列中的错码增多。,一般说来，采用纠错编码后，误码率总是能够得到很大改善的，改善的程度和所用的编码有关。,上面两种情况付出的代价是带宽增大。对于给定的传输系统，其传输速率和Eb/n0的关系为式中：RB为码元速率。,11.4 简单的实用编码,1.奇偶监督码 奇偶监督码是数据通信中最常见的一种简单检错码，其编码规则是：把信息码先分组，形成多个许用码组，在每一个许用码组最后（最低位）加上一位监督码元即可。加上监督码元后使该码组中1的数目为奇数的编码称为奇数监督码，为偶数的编码称为偶数监督码。,假设一个码组的长度为n，表示为（an-1an-2an-3:a0），其中前n-1位是信息码，最后一位a0为监督位，那么，对于偶数监督码必须保证,监督码元a0的取值（0或1）可由下式决定：,对于奇数监督码必须保证,监督码元a0的取值（0或1）可由下式决定：,根据奇偶监督码的规则我们可以看到，当码组中的误码为偶数时，校验失效。比如有两位发生错误，会有这样几种情况：00变成11、11变成00、01变成10、10变成01，可见无论哪种情况出现都不会改变码组的奇偶性，偶数监督码中1的个数仍为偶数，奇数监督码中1的个数仍为奇数。因此，简单的奇偶监督码只能检测出奇数个位发生错误的码组。,2.二维奇偶监督码 二维奇偶监督码又称方阵码。二维奇偶校验码比一维奇偶校验码多了个列校验，因此，其检错能力有所提高。除了检出行中的所有奇数个误码及长度不大于行数的突发性错误外，还可检出列中的所有奇数个误码及长度不大于列数的突发性错误。前述的一维奇偶监督码一般只适于检测随机错误。,二维奇偶监督码不仅可用来检错，还可用来纠正一些错码。例如，当码组中仅在一行中有奇数个错误时，则能够确定错码位置，从而纠正它。,表1 二维偶监督码,3.恒比码 恒比码的编码原则是从确定码长的码组中挑选那些“1”和“0”个数的比值一样的码组作为许用码组。这种码通过计算接收码组中“1”的数目是否正确，就可检测出有无错误。表2是我国邮电部门在国内通信中采用的五单位数字保护电码，它是一种五中取三的恒比码。,不难看出这种码的最小码距是2，它能够检出码组中所有奇数个错误和部分偶数个错误。该码也是非线性分组码，但不是系统码，其主要优点是简单，适用于对电传机或其它键盘设备产生的字母和符号进行编码。,每个码组的长度为5，其中“1”的个数为3，每个许用码组中“1”和“0”个数的比值恒为3/2。许用码组的个数就是5中取3的组合数，即 C+3-5=5!/(3!2!)=10，正好可以表示10个阿拉伯数字。,表2 五单位保护电码表,4.正反码 正反码是一种简单的纠正错码的编码。其中的监督位数目与信息位数目相同，监督码元与信息码元相（信息码元的重复）或者相反（是信息码的反码），则由信息码中“1”的个数而定。如电报通信用的正反码的码长n=10，其中信息位k=5，监督位r=5。其编码规则为：,（1）当信息位中有奇数个“1”时，监督位是信息位的简单重复；（2）当信息位有偶数个“1”时，监督位是信息位的反码。,接收端解码的方法为：先将接收码组中信息位和监督位按位模2相加，得到一个5位的合成码组，然后，由此合成码组产生一校验码组。若接收码组的信息位中有奇数个“1”，则合成码组就是校验码组；若接收码组的信息位中有偶数个“1”，则取合成码组的反码作为校验码组。最后，观察校验码组中“1”的个数，按表3进行判决及纠正可能发现的错码。,11.5 线性分组码,一、线性分组码定义：信息码元与监督码元之间可以用一组线性方程来表示，且监督码元仅由本码组的信息码元确定。二、线性分组码的表示：（n，k），监督位 r=n-k 其编码效率=k/n,三、线性分组码的性质：（1）封闭性，即任意两个许用码组之模2和仍为一许用码组；（2）码组的最小码d0距等于非零码的最小码重。设有一（n，k）线性分组码，即c1、c2、cn，其中信息码组为d1、d2、dk，分组码码组系统格式见下图。具有这种结构的线性分组码又叫做线性分组系统码。,四、汉明码：要纠正（n，k）线性分组码中的单个错误，则监督码元的个数r必须满足关系2n-k（n+1）。当2n-k=（n+1）时所得的线性编码就是汉明码。可以由此推知汉明码的两个特性：（1）只要给定r，就可确定线性分组码的码长n=2r-1及信息码元的个数k=n-r。,（2）在信息码元长度相同、纠正单个错误线性分组码中，汉明码所用的监督码元个数r最少，相对而言的编码效率最高。不难发现，无论码长n为多少，汉明码的最小码距d0=3，所以它只能纠正1位错码。,五、编码要求：从已知的k个信息码元中求出满足要求的r=n-k个监督码元（校验码），然后附在信息码元之后构成个码组。,六、编码过程：例 有一个线性分组码的（n，k）为（7，3）即 C6 C5 C4 C3 C2 C1 C0 k r,1、设已知确定监督位的线性方程为 C3=C6+C4 C6+C4+C3=0 C2=C6+C5+C4 C6+C5+C4+C2=0 C1=C6+C5 C6+C5+C1=0 C0=C5+C4 C5+C4+C0=0,2、根据线性方程可得出所有许用码组 C6 C5 C4 C3 C2 C1 C0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 0 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 1 0 0 1 1 1 1 0 1 0 0 1 1 1 1 0 1 0 0,3、根据改写后的线性方程有下列矩阵关系 C6 1 0 1 1 0 0 0 C5 0 1 1 1 0 1 0 0 C4=0 1 1 0 0 0 1 0 C3 0 0 1 1 0 0 0 1 C2 0 C1 C0,其中，令 1 0 1 1 0 0 0 P11 P12 P13P1K 1 0 1 H=1 1 1 0 1 0 0=P21 P22 P23P2K 0 1 0 1 1 0 0 0 1 0.0 1 1 0 0 0 1 Pr1 Pr2 Pr3PrK 0 0 1=P Ir 为监督矩阵，其中:列数=n，行数=k，P为rk阶矩阵，Ir为r阶单位方阵,4、引入Q矩阵：令 Q=PT，或 P=QT（倒置矩阵）得出 G=Ik Q Ik k阶单位方阵 G 生成矩阵综上所述：只要找到了线性分组码的生成矩阵G，编码的方法就完全确定了。,【例题1】已知一个（7，4）线性分组码的生成矩阵,求该信息码的监督矩阵，并列出所有许用码组。,解：因为,=IkQ 1 1 0 1 0 1 1则 Q=0 1 1 P=QT=1 1 1 0 1 1 1 0 1 1 1 1 0 1,所以 1 0 1 1 1 0 0 C6+C4+C3+C2=0 H=P Ir=1 1 1 0 0 1 0 C6+C5+C4+C1=0 0 1 1 1 0 0 1 C5+C4+C3+C0=0 即有线性方程组,C2=C6+C4+C3C1=C6+C5+C4C0=C5+C4+C3,根据线性方程组可到许用码组,从许用码组可看出其d0=3 因此其检错能力 d0e+1 e d0-1=2 纠错能力 d02t+1 t(d0-1)/2=1,设 A为发送码组，它是一n列的行矩阵。B为接收码组，且是一n列的行矩阵，即 B=bn-1bn-2b0 则发送码组和接收码组之差为 B A=E(模2)它就是传输中产生的错码行矩阵 E=en-1en-2e0 其中 ei=0，当 bi=ai（表示接收码元无错）1，当 biai（表示接收码元有错）,11.6 循 环 码,一、循环码的概念：（1）循环码是线性分组码的一个重要分支，它具有较强的纠错能力，而且其编码和译码电路很容易用移位寄存器实现。（2）循环码是一种分组码，它除了具有线性分组码的封闭性之外，还具有一个独特的性质即循环性。,（3）循环码可定义为：对于一个（n，k）线性码C，若其中的任一码组向左或向右循环移动任意位后仍是C中的一个码组，则称C是一个循环码。如c=c1，c2，cn是一个循环码组，对它左循环移位一次，得到c（1）=c2，c3，cn，c1也是许用码组，移位i次得到c(i)=ci+1，ci+2，cn，c1，ci还是许用码组。不论右移或左移，移位位数多少，其结果均为循环码组。,在代数编码理论中，可以把循环码组中各码元当作一个多项式的系数，即把一个长为n的码组表示为 c(x)=c1xn-1+c2xn-2+cn,式中，c(x)称为码多项式，变量x称为元素，其幂次对应元素的位置，它的系数即为元素的取值（我们不关心x本身的取值），系数之间的加法和乘法仍服从模2规则。比如一个（7，3）循环码（见表11-6）中第7个码组为（1100101），则该码组可表示为 c7(x)=1x6+1x5+0 x4+0 x3+1x2+0 x+1=x6+x5+x2+1,表115 一种（7，3）循环码的全部码组,二、循环码的生成多项式通过代数变换，可以得到循环码的表示式：T(x)=m(x)g(x)式中，m(x)表示信息码元的代数多项式;g(x)称为循环码的生成多项式。显然，生成的循环码的多项式T(x)由其码组长度 n及生成多项式g(x)所决定，它是g(x)的倍式，即凡能被g(x)除尽，且次数不超过(n-1)的多项式，一定是这一组循环码的码多项式。,那么，如何确定生成多项式呢？数学分析发现，g(x)是一个能除尽xn+1的(n-k)阶多项式，所以，对xn+1进行因式分解所得到的因式就是g(x)。因此g(x)必须是一个常数项不为“0”的（n-k）次多项式，而且，这个g(x)还是这种（n，k）码中次数为（n-k）的唯一的一个多项式。我们称这唯一的（n-k）多项式g(x)为码的生成多项式。一旦确定了g(x)，则整个（n，k）循环码就被确定了。,三、循环码的编码过程：(1)将k位信息位对应的码多项式m(x)乘以Xn-k，得y(x)；(2)用y(t)除以生成多项式G(x)，得余式r(x)；(3)将余式r(x)对应的码列出，即为其校验码(监督码)；(4)将信息码与监督码一起则构成循环码。,例 有（7，3）线性码，设其生成多项式G(x)=X4+X3+X2+1，试写出信息位为101的循环码，并写出其全部码组。解：（1）信息码为101，所以 m(x)=X2+1 Xn-k=Xr=X4，则 y(x)=X4 m(x)=X6+X4（2）生成多项式 G(x)=X4+X3+X2+1 所以 y(x)/G(x)=（X6+X4）/（X4+X3+X2+1）=X2+X+1X+1(余式)即 r(x)=X+1，其对应的监督码为0011,（4）这样信息码101对应的循环码为1010011；（5）则其全部码组 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 1 0 1 0 0 1 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 1 1 1,（6）数据在传输过程中，若没有发生差错，则接收端收到的循环码序列一定能被同一生成多项式整除。例 循环码1010011对应的多项式为X6+X4+X+1 生成多项式G(x)=X4+X3+X2+1则（X6+X4+X+1）/（X4+X3+X2+1）=X2+X+10 能整除表示没出现错码。,四、循环码的编码电路 从以上可知，构造系统循环码时，只需将信息码多项式m(x)提升（n-k）阶（即乘以xn-k），然后以g(x)为模（即除以g(x)），所得余式r(x)就是要求的监督码元多项式。这一编码过程可以用下式表示出来：xn-k m(x)/g(x)=q(x)+r(x)/g(x)这里，g(x)为商式。由此得到的系统循环码多项式为 T(x)=xn-k m(x)+r(x)这样，系统循环码的编码过程就变成用除法求余式的问题。,多项式除法可以用带反馈的线性移位寄存器来实现。有两种不同的除法电路形式：内接异或（模2加）门电路和外接异或门电路，实际中通常采用内接异或门除法电路。,五、循环码的译码 考虑噪声为加性干扰的情况，设信道干扰的多项式表示式为，发送循环码的多项式，则收端收到的码多项式为：R(x)=e(x)+T(x)如果没有干扰，即e(x)=0，则R(x)=T(x)，那么，R(x)/g(x)=0，反过来说，只要R(x)/g(x)0，则一定有误码存在。因此，我们就以余项是否为零为判别码组中有无错码。,因此，原则上纠错可按下述步骤进行：（1）用生成多项式g(x)除接收码组R(x)，得出余式r(x)；（2）按余式r(x)，用查表的方法或通过某种计算得到错误图样E(x)。（3）从R(x)中减去E(x)，便得到已经纠正错码的原发送码组T(x)。这种解码方法称为捕错解码法。,