第7章差错控制编码.ppt

《第7章差错控制编码.ppt》由会员分享，可在线阅读，更多相关《第7章差错控制编码.ppt（65页珍藏版）》请在课桌文档上搜索。

1、7.1 概述7.1.1 差错控制编码的概念 在数字通信系统中，编码器分为信源编码（解决通信的有效性问题）和信道编码（解决通信的可靠性问题）信道编码（又称差错控制编码或纠错编码），就是为改善数字信号在信道中传输的可靠性，而对其进行再编码的数据编码技术。差错控制编码：是一种重要的信道编码方式，是以可控制的方式，在信息码组的前后或在码元中间，按照一定的规则附加一些码元，这些码元被称为监督码元。,第7章 差错控制编码,差错控制的概念：信道编码是在经过信源编码的码元序列中增加一些多余的比特，可发现或纠正传输中发生的错误；当信道编码只有发现错码能力而不具备纠正错码能力时，需结合其他措施来纠正错码，否则只能

2、将被发现为错码的码元删除，以避免错码引起的负面影响。上述手段统称为差错控制。,信道中差错的类型：随机差错：由随机噪声导致，表现为独立的、稀疏的和互不相关发生的差错。突发差错：相对集中出现，即在短时段内有很多错码出现，而在其间有较长的无错码时间段，例如由脉冲干扰引起的错码或信道特性产生的衰落等。,7.1.2 差错控制方式,常用的差错控制方式：检错重发（ARQ）常用检错重发系统：前向纠错（FEC）混合纠错（HEC）,常用的差错控制方式,常用的差错控制方式,7.1.2 差错控制方式（1）检错重发方式（ARQ）接收端在收到的信码中检测出错码时，设法通知发送端重发信码，直到正确接收为止。ARQ方式需要反

3、馈信道来反馈收端的重发指令给发送端。常用的检错重发系统有三种：停发等候重发返回重发选择重发,图7.1 检错重发差错控制系统工作原理,（2）前向纠错方式（FEC）前向纠错是一种在接收端能发现错误，并能自动纠正错误的差错控制方式（也称自动纠错方式）。对于二进制系统，如果能够确定错码的位置，就能纠正它。这种方式不需要反馈信道来传递指令，传输实时性好，适合单向通信。,（3）混合纠错方式（HEC）混合纠错方式：是前向纠错方式和检错重发方式的结合。这种方式兼有两者的优点，即对能自动纠正的错误，就自动纠正；超出了自动纠错能力的错误，就通过反馈信道要求重发一次。,7.1.3 纠错码的分类1）按差错控制编码的功

4、能分：检错码、纠错码2）按信息码与监督码间的检验关系分：线性码、非线性码3）按信息码与监督码间的约束关系分：分组码、卷积码4）按信息码的编码前后的形式分：系统码、非系统码5）按信道差错类型分：随机纠错码、突发纠错码6）按用于差错编码的数学方法分：代数码、几何码、算术码7）按不同的进制分：二进制码、多进制码,前面已经提到，信道编码的基本思想是在被传送的信号中附加一些监督码元，并在信息码元和监督码元之间建立某种校验关系。当这种校验关系因传输错误而被破坏时，利用已经建立的校验关系，就可以发现错误并予以纠正。因此，可以说信道编码的这种纠错和检错能力是用增加信号的冗余度换取的。,7.1.4 纠错编码的基

5、本原理,三位二进制码元共有8种可能的组合。若将其全部用来表示天气，则可以表示8种不同的天气状况。,例如,若在传输过程中发生一个误码，则任何一种码组(码字)会错误地变成另外一种码组。这是由于每一种码组都可能出现，没有多余的信息量，因此接收端不可能发现错误，以为发送的就是另外一种码组。若上述8种码组中只选用4种码组来传递信息，例如：,000=晴011=云101=阴110=雨,接收端有可能发现码组中的一个错码,例如，若000(晴)这一码组中错了一位码，则接收到的码组可能变为100或010或001。由于这3种码组都是禁用码组，故接收端在收到禁用码组时，就可以发现错误，即检出了错误。,上述的编码方法只能

6、检测错误，不能纠正错误。例如，当收到的禁用码组为100时，接收端无法判断是哪一位码发生了错误，因为晴(000)、阴(101)、雨(110)三种码组错了一位都可能变成100。,000（晴）011（云）101（阴）110（雨）,码距、编码效率和编码增益：,编码的检错或纠错能力与码字间的最小距离有关。1.码距（汉明距离）：把两个等长码字之间对应码位上具有不同的二进制码元的个数，称为这两个码字的汉明距离，简称码距，用d表示。例如，两个码字11000与10011，它们在第2、4、5位上二进制码元不同，故d=3。2.码重（汉明重量）：分组码中，一个码字中“1”的数目。用w表示，如码字11010，重量W=3

7、；3.最小距离：把一个编码的码组集合中，任何两个许用码组之间距离的最小值称为最小距离，用d min表示。,图7.2 码距的几何表示,最小距离是信道编码的一个重要参数，它直接与编码的检错和纠错能力有关。在一般情况下，对于分组码有如下结论：(1)为检测e个错码，最小距离应满足(2)为纠正t个错误，最小距离应满足(3)为纠正t个错误，同时又能够检测e个错误，最小码距应满足,d min e+1,d min 2t+1,d min e+t+1(e t),为了提高纠、检错能力，需要加大码距。要加大码距，就需增加更多的监督码元。这就必然会降低编码效率。因此，在考虑纠、检错能力时，要考虑编码效率。编码效率的定义

8、：信息码的位数与总码元位数之比。编码效率：R=k/nn码组长度为（含监督码元）k信息码元位数r监督码元位数 r=n-k显然，监督码元位数越大，编码效率就越低。因此，编码效率与纠错能力是一对矛盾。,已知8个码组为000000，001110，010101，100011，101101，110110，111000。求：,例如,解：（1）dmin=3（2）因为dmin e+1 且 d min=3 所以 e 2,能检出2位错码；（3）因为dmin 2t+1且dmin=3 所以 t 1,能纠出1位错码；（4）因为dmin t+e+1且dmin=3 所以 t+e 2,又因为et，令e=t=1时才能满足条件，只

9、能同时检测并纠正1位错码；,（1）以上码组的最小距离？（2）将以上码组用于检错，能检出几位错码？（3）若用于纠错，能纠出几位错码？（4）若同时用于检错和纠错，能同时纠、检几位错码？,7.2 几种常用的简单编码7.2.1 奇偶校验码监督码附加在每个信息码组的后面，若监督码元的取值是要使新的码组中“”的数目成为奇数，则称为奇校验码；若监督码元的取值是要使新的码组中“”的数目成为偶数，则称为偶校验码。,奇偶校验码的特点 1）分为奇校验码和偶校验码，两者原理相同；2）监督位只有一位；3）对偶校验码，码组中的“”的数目为偶数，用表达式表示如下：4）对奇校验码，码组中的“”的数目为奇数，用表达式表示如下：

10、5）无论是奇校验码还是偶校验码，都只能检测出奇数个错码，而不能检测偶数个错码。,【例】：字符A的编码1000001为7位，在偶校验中，则加在字符A后面的校验码为0，即10000010。优点：简单 缺点：只能检测出部分传输差错,7.2.2 行列监督码（二维奇偶校验码）,行列监督码（又称二维奇偶校验码、方阵码），它是垂直奇偶校验与水平奇偶校验的组合，其发现差错的能力很强。这种码是将若干码字排列成矩阵，在每行和每列的末尾均加监督码(奇监督或偶监督)。,例如,1100101100010100110001011000011001110101为用户要发送的信息序列，现将每8个码元分成一组编成方阵，对方阵的

11、行与列都进行偶数监督，则在发送端编成如表7-1所示的方阵。,该码对每行或每列的奇数或偶数个错都能检验出来，且可以确定仅一行或一列出现奇数个错的误码的位置并纠正之，但这种码对构成2m2n方阵的错误无法检测出来，如图7-2a所示。,X X X X X X X OX X X X X X X O X X X X X OX X X X X X X OX X X X X X X OX X X X X OX X X X X X X OO O O O O O O O,图中，“X”表示信息位，“O”表示监督位，如“”所示的位置上出现差错，差错数正好为4的倍数，且差错位于构成矩形的四个角上，则二维奇偶监督码不能检

12、测出错误。,图7-2a 二维奇偶监督码的结构,行列监督码适用于检测突发错码。因为突发错码通常成串出现，随后有较长一段无错码区间，所以在某一行中出现多个错码的机会较多，这很容易在按列检查时发现错误。一维奇偶校验码只适用于检测随机错码。二维的奇偶校验码不仅可以检错，还可以纠错。,表7.1 行列监督码示例,7.2.3 恒比码 在恒比码中，每个码组均有相同数目的“”（和“”）。由于“”的数目与“”的数目之比保持恒定，故得名恒比码或称为定比码。由于其中各码组的码重是相等的，故又称为等重码或定权码。在检测时，只要计算接收码组中“”的数目是否对，就知道有无错码。这种码已应用于电报传输中，国际通用的检错重发（

13、ARQ）电报通信系统中采用3个“”、4个“”的34码，又称为七中取三码。这种码共有C37=35个码组，分别表示26个字母及其他符号。,表7.2 国际通用的七中取三码,7.2.4 正反码 正反码是一种简单的能够纠错的编码。其中的监督位数目与信息位数目相同，监督码元与信息码元相同（是信息码的重复）或者相反（是信息码的反码），由信息码中“”的个数确定。监督码的编码规则如下：当信息码有奇数个“1”时，则监督码是信息的重复，如信息码为10101，码后的码字为1010110101；当信息码有偶数个“1”时，则监督码是信息码的反码，如信息码为11011，则编码后的码字为1101100100。,解码时先将接收

14、码组中信息码和监督码对应码位模2相加，得到一个合成码。若接收的信息码中有奇数个“1”，则此合成码就是检验码；若接收的信息码中有偶数个“1”，则校验码为合成码的反码。观察校验码中“1”的个数，就能判决信码是否有错并纠正错误。,监督码的解码规则如下：,正反码常用于电报通信，其信息码位数K=5，监督码位数r=5，正反码码长n10。表6-4列出了其利用校验码进行判决和纠错的情况。,表7-2A 正反码纠错表,73 线性分组码,7.3.1 基本概念 分组码一般可用(n，k)表示，其中k是每组信息码元的数目，n是编码码组的码长。r=n-k为每个码组中的监督码元数目。二进制共有2k个不同信息组，相应得到2k个

15、不同的码字，称为许用码组。其余2n-2k个码字未被选用，称为禁用码组。,分组码的监督码元是根据一定的规则，由本组的信息码元经过变换得到。变换规则不同，得到的分组码也就不同。如果在某一种分组码中，监督码与信息码间呈线性代数的关系时，就称为线性分组码。在接收端通过检查一个码组中的k与r之间是否仍然存在发信端那种确定的线性代数关系来发现或纠正错码。,汉明码是一种能够纠正单个错误的线性分组码。它有以下特点：（1）最小码距dmin3，可纠正一位错误；（2）码长n与监督元个数r之间满足关系式：通常二进制汉明码可以表示为：,7.3.2 汉明码,现以(7，4)分组码为例来说明线性分组码的特点。设其码字为A=a

16、6 a5 a4 a3 a2 a1 a0，其中前4位是信息码元，后3位是监督元，可用下列线性方程组来描述该分组码，产生监督码元。显然，这3个方程是线性无关的。经计算可得（7，4）码的全部码字，如表7-3所示。,式（7-3）,【例如】,表7.3（7，4）码的码字表,不难看出，上述（7，4）码的最小码距dmin=3，它能纠正一个错误或检测两个错误。,（7，4）系统汉明码的编码器和译码器电路：,7.3.3 循环码,循环码是线性分组码的一个重要子集，是目前研究得最成熟的一类码，它有许多特殊的代数性质。（n,k）循环码是另一种常用的线性分组系统码。前k位为信息码元，后r=n-k位为监督码元。（1）循环码的

17、特点 特点：它具有封闭性、系统性和循环性。循环码中任一许用码组经过循环移位后，不论右移或左移，移位位数是多少，所得到的码组仍然是许用码组。循环码编码电路简单，性能优良，不仅可以纠正独立的随机错误，还能纠正突发错误。,表7.4（7，3）循环码码字表,一般说来，若（an-1 an-2 a1 a0)是一个循环码组，则（an-2 an-3 a0 an-1)（an-3 an-4 an-1 an-2)（a0 an-1 a2 a1)也是该编码中的码组。,（2）码多项式 为了利用代数理论研究循环码，可以将码组用代数多项式来表示，这个多项式被称为码多项式，用T(x)表示。（n，k）循环码的许用码组可以表示为：例

18、如：表7.4中的第4码组可以用多项式表示为：,想一想,（以降幂顺序排列）,循环码的码多项式特点,把许用码组T=（an-1 an-2 a1 a0)表示为：x为一个任意的实变量，其幂次代表移位次数。当码组T向左循环移i位后的码组，其码多项式为：,码多项式的除法运算：设有A码组（1101）和B码组（10111），则A码多项式为：A(x)=x4+x3+x2+1，B码多项式为：B(x)=x2+x+1，A(x)B(x)得（余数为0）：,（3）循环码的编码方法 循环码T(x)是按下述方法编制的：式中：n-k监督码的位数；m(x)信息码多项式；r(x)余式多项式，即xn-km(x)/g(x)的余式多项式；g(

19、x)生成多项式。,循环码的生成多项式 循环码中次数最低的码多项式（全“0”码字除外）称为生成多项式，用g(x)表示。可以证明生成多项式 g(x)具有以下特性：（1）g(x)是一个常数项为1的 r=n-k 次多项式；（2）g(x)是 xn+1 的一个因式；（3）该循环码中其它码多项式都是g(x)的倍式。（这给出了产生及解译循环码的方法，即发端的码多项式一定能被g(x)整除，接收端 的码多项式不一定能被多项式整除）,循环码的生成多项式,1.循环码T(x)的表示式：2.对于任意n值，必然存在(1)取（x+1)为生成多项式，由此构成的循环码即为简单的偶监督码(n，n-1)。由于g(x)为一阶多项式，因

20、此只有一位监督码。(x+1)的任何倍式的码重必定保持偶数，其最小码距dmin=2。(2)以 为生成多项式，由于生成多项式为n-1阶多项式，故信息码位数为1。它只有两个许用码组：全“0”和全“1”，因此这种循环码是（n,1）重复码，其最小码距dmin=n。,T(x)=m(x)g(x),循环码的生成多项式,(3)例如：（7，3）循环码 g(x)可由x7+1分解因式（系数按模二加运算）得到：,编码过程 首先需要根据给定循环码的参数（n，k）确定生成多项式g(x)，即从（xn+1）的因子中选一（n-k）次多项式作为g(x)。然后，利用循环码的编码特点，即所有循环码多项式T(x)都可以被g(x)整除，来

21、定义生成多项式g(x)。下面就将以上各步处理加以解释：,【编码举例】信息码为110，生成多项式为g(x)=x4+x3+x2+1，编出对应的（7，3）码组。编码方法归结为以下几步：（1）用xn-k乘m(x)。这一运算实际上是把信息码后附加上（n-k）个“0”。信息码为110，m(x)=x2+x，n-k=7-3=4时，xn-km(x)=x4(x2+x)=x6+x5(相当于1100000）,（2）求r(x)。用生成多项式g(x)除xn-km(x)，得到商和余式r(x)，即,相当于1100000/11101,（3）编码输出系统循环码多项式T(x)为：,上述三步编码过程，在硬件实现时，可以利用除法电路来

22、实现。,g(x)的次数等于移位寄存器的级数，g(x)=xo,x1,x2.,xr的非零系数对应移位寄存器的反馈抽头。首先，移位寄存器清零。3位信息码元输入时，门1断开，门2接通，直接输出信息元。第3次移位脉冲到来时将除法电路所得的余数存入移位寄存器。第47移位时，门1接通，门2断开，输出监督码元。此时输入信息码元为110。,2、译码过程 循环码的译码可以分三步进行：（1）由接收到的码多项式B(x)计算校正子（伴随式）多项式S(x)；,（2）由校正子S(x)确定错误图样E(x)；（3）将错误图样E(x)与B(x)相加，纠正错误。,（4）循环码的其他常见类型1）BCH码 BCH码是一种特别重要的循环

23、码，是目前研究得最为透彻的一类纠错码。2）R-S码 R-S码是里德所罗门码（Reed Solomon Code）的简称，于20世纪60年代提出，是一类非二进制BCH码。,7.4 卷积码,卷积码：监督码元不仅与本组的信息有关，而且还与以前码组的信息有约束关系，各组之间具有相关性。,卷积码中编码后的n个码元不仅与当前段的k个信息有关，而且也与前面（N-1）段的信息有关，编码过程中相互关联的码元为nN个。因此，这N段时间内的码元数目nN通常被称为这种码的约束长度。由于与前面m段规定时间内的信息位有关，这里的mN-1，通常用（n，k，m）表示卷积码。m为编码存储，n为码长，k为信息码元位数，(n，k)

24、称为子码，通常较短。,卷积码的编码规则：先将信息序列分成长度为k的子组，然后编成长为n的子码，其中长为r=n-k的监督码元不仅与本子码的k个信息码元有关，而且还与前面m个子码的信息码元密切相关。即各子码内的监督码元不仅对本子码有监督作用，而且对前面m个子码内的信息元也有监督作用。,例如：卷积码的n=2，k=1，m=2，因此，它的约束长度nN=n(m+1)=23=6。,【例】下图是（3,1,2）卷积码编码器。它由两级移位寄存器（mj-1,mj-2）、两个模二加法器和开关电路组成。编码前，各级寄存器清零，信息码元按m1,m2,mj,的顺序送入编码器。每输入一个信息码元mj，开关电路依次接到x1.j,x2.j和x3.j各端点一次。,卷积码,当输入数据D=11010时，可以计算出码字，如表,a,b,c,d分别表示mj-2,mj-1的四种状态：00，11，10，11。当第一位信息码元为1时，即m1=1，因mj-2,mj-1=00，故输出比特x1.jx2.jx3.j=111;当第二位信息码元为1时，即m2=1，因mj-2,mj-1=01，故输出比特x1.jx2.jx3.j=110；依此类推。为保证输入的全部信息位11010都能通过移位寄存器，还必须在信息位后加3个零。,图7.3 卷积码编码器的一般结构图,