差错控制编码纠错码.ppt

《差错控制编码纠错码.ppt》由会员分享，可在线阅读，更多相关《差错控制编码纠错码.ppt（66页珍藏版）》请在三一办公上搜索。

1、1,第八章 差错控制编码,2,8.1 引言8.2 纠错编码的基本原理8.3 线性分组码8.4 循环码8.5 小结,3,8.1 引言,在数字信号传输中，由于噪声的存在及信道特性不理想，都可使信号波形失真，从而在接收端就不可避免的产生错误判决。,引起误码原因:,(1)信道特性不理想(乘性干扰):引起码间串扰，通常可采用均衡的办法纠正。(2)噪声影响(加性干扰):需借助各种差错控制编码技术来克服。,一、基本概念,4,差错控制编码又称为信道编码(纠错编码)，要求在满足有效性前提下，尽可能提高数字通信的可靠性,纠错编码：在要传送的数字信息序列中按一定规则加上一些冗余码元（监督位),使序列按满足一定数学规

2、律的码字传输(编码过程);译码:在接收端,利用这种规律性来鉴别传输过程是否发生错误或纠正错误，恢复原始信息序列。,5,二、纠错编码的分类,按功能分：检错码和纠错码 按监督码元与信息码元之间是否存在线性关系分：线性码与非线性码 按信息码元与监督码元之间的约束关系不同分：分组码与非分组码如卷积码按信息码元在编码后是否保持原来的信号形式分：系统码与非系统码按纠正差错的类型分：纠正随机错误的码与纠正突发错误的码 按码元的取值分：二进制码与多进制码,6,三、误码的类型,随机误码,错码出现是随机的、错码之间统计独立。由随机噪声引起存在随机误码的信道称为随机信道,突发误码,错码成串集中出现，在很短的时间出现

3、大量错码，而过后又存在较大的无错码位，且差错之间是相关的例如：脉冲噪声，信道中衰落存在这种差错的信道称为突发信道,7,四、差错控制方法,（1）前向纠错（FEC）,8,优点：无需反向信道、译码总延迟恒定，具有恒定的信息 传输速率,缺点：当纠错能力强时，要增加冗余位；接收可靠性对信道传输条件的恶化很敏感,（2）自动要求重发（ARQ）,9,优点：极低的不可检测概率；编译码简单；对任何信道都有效,缺点：需要反向信道；译码延迟不固定；需要缓冲器,（3）FEC/ARQ混合系统,分为三类：停止等待ARQ、连续ARQ和选择重发ARQ,综合利用FEC延迟小，纠错能力强和ARQ传输可靠性高,10,发端发出同时具有

4、检错和纠错能力的码，收端收到后，检查错误情况：如果错误在纠错能力之内，则自动纠正；若超出纠错能力，但在检错能力之内，则经反向信道要求重发。,注意：不同的纠错编码方法，有不同的检错或纠错能力，一般说来，增加监督码元越多，检错或纠错的能力就越强，提高传输可靠性是以降低传输有效性为代价的。,11,8.2纠错编码的基本原理,简单例子：,3位二进制码组（c1 c2 c3）,其中ci=0或1。此码组有8种不同的组合：,000 001 010 011 100 101 110 111,可分别代表不同的信息含义。若将8种码组都作为有用码组来使用，比如代表8种天气情况：,000（晴），001（雷），010（雹），

5、011（阴），100（风），101（云），110（雨），111（雪）,12,任一码组在传输中若发生一个或多个错码，则将变成另一信息码组,这种编码方法就不具有任何抗干扰能力：,但如果在8种码组中，规定只准使用其中4种来传输信息，比如，许用码组为：,000（晴），011（阴），101（云），110（雨）,这种编码接收端有可能检测码组中出现的一位或三位错误，但不能发现两位错码的情况,接收端收到禁用码组时，就认为发现了错误,13,要想纠正错误，需要增加多余度，比如，只准使用两个码组,14,000（晴）111（阴）,其他均为禁用码组，则它可检测两个错码或能纠正一个错码。,如：接收端接收到禁用码组100，

6、若认为只有一个错码，可纠正，若错码数不超过2个，只能检测错误,4种信息完全可以由2位二进制数字来表示，即前两位。可见，第三位完全是多余的，这第三位就作为附加的监督码,15,一、纠错编码的基本思想,发送端按照某种规则在信息序列上附加监督码元，接收端则按照同一规则检查两者间关系 码的检错和纠错能力是用信息量的冗余来换取的。添加的冗余越多，码的检错、纠错能力越强，但信道的传输效率下降也越多。以牺牲通信的有效性（信息传输速率）来提高可靠性,16,二、纠错编码的理论基础,理论依据：Shannon信道编码定理定理指出：对于一给定的有干扰信道，若其信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在

7、一种编码方法，使编码错误概率P随着码长n的增加，按指数下降到任意小的值。,E（R）称为误差指数，n编码长度，R信息发送速率,17,三、编码距离与纠错检测的关系,码重：二进编码序列V中，包含1的个数为该码组的重量（权），W(v),码距：两个等长码组V1,V2中对应码位上不同二进制码元的个数，也叫汉明距离，d(V1,V2),例：V111001100和V2=10010111 重量分别为W14，W25；它们的距离为d(V1,V2)=5。,两码组间的汉明距离也等于两码组对应位模二加后所得码组的重量,几个基本概念,18,最小码距：对于某种编码，所含的全部码组之间的最小距离，成为该码的最小码距，用dmin表

8、示,最小码距的大小直接关系着这种编码的检错和纠错能力，它是衡量各种码抗干扰能力大小的标准。码组的最小距离越大，说明码字间的最小差别越大，抗干扰能力越强。,最小码距与检错和纠错能力的关系,1)如果 一个码能检错不多于e个错，则要求,2)如果 一个码能纠正不多于t个错，则要求,19,如果 一个码能纠正不多于t个错，同时可以检e个错误 则要求,四、编码效率,设编码序列长度与所包含的信息位数分别为n,k，则编码效率指一个码组中信息位所占比重：,20,编码效率是衡量码性能的一个重要参量，编码效率与抗干扰能力这两个参数是相互矛盾的,编码的主要任务就是如何找到一种编码，在满足一定误码率要求的前提下，尽量提高

9、编码效率。,五、编码增益,描述编码系统对非编码系统性能的改善程度，定义为在给定误码率要求下，非编码系统与编码系统之间所需信噪比的差。,编码增益越大越好,21,8.3线性分组码,一、基本概念,分组码,将信息码首先分成若干组，然后为每组信码附加若干位监督码元，这种编码称之为“分组码”,分组码一般用（n,k）表示，k是信息码的位数，n是码组长度，监督码元位数r=n-k，分组码结构,码长n=k+r,k个信息位,r个监督位,22,注意：在分组码中，监督码仅监督本码组中的信息码元。在非分组码中如卷积码，监督码元除了与本组信息码元有关，还与其它组的信息码元有关,线性码,码组中监督码元和信息码元之间满足线性变

10、换关系，由一组线性方程（监督方程）构成。线性码是一种代数码。奇偶监督码是最简单的线性码。,23,二、几种简单的线性分组码,1、重复码,(n,1)的线性分组码，最小码距为n，当n很大时，编码效率低，纠错能力强，,2、奇偶校验码,只有一个监督码（校验位）的（n,n-1）的分组码。分为两种：奇数校验码和偶数校验码,24,奇数校验码：附加一位监督码，使码组中“1”的个数为奇数,设码字（vn-1,vn-2,v1,v0），v0为监督元，则有：vn-1 vn-2 v1 v01（8-1）,在接收端，按上式计算各码元，若结果为0认为有错；否则，无错。如：11010 0,模2加,偶数校验码：附加一位监督码，使码组

11、中“1”的个数为偶数，,vn-1 vn-2 v1 v00,即满足：,（8-2）,（8-1）与(8-2)叫做监督方程或监督关系式,25,在接收端，按上式计算各码元，若结果为1认为有错；否则，无错。如：11010 1,注意：只能检测奇数个错误，当错码为奇数个时，由于打乱了码字中”1”个数的奇偶性，故能发现差错。但当错码为偶数个时，因码字中1个数奇偶性保持不变，则无法发现错码。,特点：结构简单，易于实现，编码效率高，虽然不理想，但干扰不严重时，且码长不长的情况下仍很有用。,26,3、方阵码,也叫二维奇偶校验码（矩阵码、行列监督码），其基本原理与简单的奇偶校验码相似。不同的是每个码元都要受到行和列的两

12、项监督,编码方法：,将所要传送的码序列编成一个方阵，方阵中每一行为一个码组。每行的最后加上一个监督码元，进行奇偶监督。在每列的最后也加上一个监督码，进行奇偶监督,27,例：若发送码序列为（1100100111 0100011100 0010011110 0101011000 0110000001 11）,求其奇偶监督方阵,1 1 0 0 1 0 0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0 经编码后的校验位

13、和信息位一起传输:（110010011100100011100000100111101010101100000110000001）,28,特点：（1）有可能检测偶数个错误，但是不能检测在方阵中构成 矩形四个角的错误，因为在行列两个方向均有偶数个错误。（2）适于检测突发错码，能纠正突发错误，如当码组中仅在一行有奇数个错误时，能够确定错误位置，并纠正它。（3）,29,4、恒比码（等比码或等重码）,每个码组中含“1”和“0”的个数的比例恒定在检测时，计算接收码组中“1”的数目是否正确，能检测 出所有奇数个错误，并能部分检测出偶数个错误（成对交 换错误检测不出）简单，适用于电传机或其它键盘设备产生的字

14、母和符号,例：我国电传机用“5中取3”恒比码表示10个数字,30,表 我国五单位保护电码表,在国际无线电报通信中，广泛采用“7中取3”恒比码。,（是一种五中取三码）,31,四、线性分组码编码原理,1、汉明码：能纠正单个随机错误且编码效率较高的线性分组码，其参数：,监督位：,码长：,信息位：,最小距离：,编码效率：,当m很大时，,32,2、以（7，4）汉明码为例来说明编码原理,设码字为a6 a5 a4a3 a2 a1 a0，,信息码元a6、a5、a4、a3来源于待编码的信息序列；监督码元 a2、a1、a0的取值应根据信息码元按监督 关系式来决定,a6+a5+a4+a2=0a6+a5+a3+a1=

15、0a6+a4+a3+a0=0,a2=a4+a5+a6a1=a3+a5+a6a0=a3+a4+a6,（8-3）,每个方程分别为某一个监督码元的奇偶校验方程。通常称这几个线性方程为对应码的一致监督关系式或一致校验方程,33,给定信息位后，根据上式算出各监督位，该编码的所有码组如下表,34,（1）监督矩阵（奇偶校验矩阵）,1 a6+1 a5+1 a4+0 a3+1 a2+0 a1+0 a0=01 a6+1 a5+0 a4+1 a3+0 a2+1 a1+0 a0=01 a6+0 a5+1 a4+1 a3+0 a2+0 a1+1 a0=0,a6+a5+a4+a2=0a6+a5+a3+a1=0a6+a4+

16、a3+a0=0,上式监督关系式(8-3)可写成,35,写成矩阵形式,可记为：HVT=0T 或VHT=0,36,H称为线性码监督矩阵,rn阶矩阵 监督矩阵H确定了编码时监督码元与信息码元的关系，可由H和信息码元求出全部码组 把具有PIr形式的H矩阵称为典型形式的监督矩阵，其中P为r k阶矩阵,Ir为r r阶单位方阵 H矩阵的各行应线性无关。矩阵若能写成典型形式，则其各行一定线性无关,监督矩阵特点:,37,(2)生成矩阵,对（7,4）线性码，由其一致监督方程式，再附加4个等式,a6=a6a5=a5a4=a4a3=a3a2=a4+a5+a6a1=a3+a5+a6a0=a3+a4+a6,38,39,k

17、 n阶矩阵，编码方法完全由生成矩阵G确定把具有IkQ形式的G矩阵称为典型形式的生成矩阵，其中，Ik为kk阶单位方阵，Q为k r阶矩阵V可看成是G矩阵的各行的线性组合，为保证不同的信息分组对应不同的码字，G矩阵各行应线性无关,生成矩阵特点：,40,3、线性分组码伴随式（或校验子）,监督关系式 HVT=0T 或VHT=0,码字是由H矩阵所确定的线性方程组的解，所以可以由H矩阵来检验接收的序列是否为码字,若接收到码字R=V+E，E为错误矢量（或错误图样）,计算,SRHT=(V+E)HT=VHT+EHT=EHT,当S0表明没错，此时E0；否则，S不为0，表明有错，E也不为0。,S称为校验子（伴随式）,

18、41,任意两个许用码组模2和仍为一许用码组，即具有封闭性。两码组之间的距离是另一码组的重量，最小码距=非零码的最小码重(1的个数）,4、线性分组码最小码距及性质,许用码字,42,设（7,4）线性码的生成矩阵G为：,当信息位为0001时，（1）试求其后的监督位。（2）监督矩阵H,43,解：（1）,44,（2）监督矩阵H根据生成矩阵和监督矩阵的关系：G=IkQ，H=PIr其中P=QT，可得监督矩阵H为：,45,8.4循环码,一、循环码的编码原理,循环码是一种重要的线性分组码，是在代数学基础上建立起来的，编码和解码设备都不太复杂，且有较强的检（纠）错能力。,特点：封闭性 循环性：即码中任一码组循环一

19、位(将最右端的码元移 到左端或反之）以后，仍为该码中的一个码组。,46,若(vn-1,vn-2,v1,v0)是一(n,k)循环码的码组，则(vn-2,vn-3,v1,v0,vn-1)(vn-3,vn-4,v0,vn-1,vn-2)(v0,vn-1,vn-2,vn-3,v2,v1)也都是该循环码的码组。,1、码多项式,设一个(n,k)线性分组码，其中的每个码字V=(vn-1,vn-2,v1,v0)可用一个n-1 次多项式表示，即,V(x)=vn-1xn-1+vn-2xn-2+v1x+v0,47,如：对于（7，3）循环码的任意码组可表示为：V(x)=a6x6+a5x5+a4x4+a3x3+a2x2

20、+a1x+a0如码组（1100101）对应的码多项式可表示为 V(x)=1*x6+1*x5+0*x4+0*x3+1*x2+0*x+1=x6+x5+x2+1,码多项式与码字的关系：本质上是一回事，仅是表示方法的不同而已。x仅是码元位置的标志。并不关心x的取值。,48,一种（7，3）循环码的全部码字,49,若一个整数m可以表示为:,则有mp（模n），同样对于多项式而言：,则可以写为：F(x)R(x)（模N(x)）。,即一任意多项式F(x)被一个n次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x),50,例如码组（1100101）对应的码多项式可为：V7(x)=x6+x5+x2+1其

21、被x2+1除得x6+x5+x2+1 x+1（模x2+1）,重要结论,在循环码中，若V(x)是一个长为n的许用码组，Vi(x)为V(x)码组向左循环移位i次的结果，也是一许用码组，则xi V(x)在按模xn+1运算下，也是一许用码组。即 xi V(x)Vi(x)（模xn+1）,51,例如：,其对应的码组为0101110，它正是表5-10中第3码字。,结论：一个码长为n的(n，k)循环码，它必为按模xn+1运算的一个余式。,52,2、循环码的生成多项式与生成矩阵,循环码完全由其码组长度n和生成多项式g(x)所决定 问题：寻找构成生成矩阵的k个线性无关的许用码组,（n，k)循环码中一定能找到这样一个

22、码组：前面的k-1位都是0，而第k位及第n位为1，其它各位gi为0或1：（00001gn-k-1gn-k-2 g2 g11),53,其对应的码多项式为g(x)，且 g(x)一定是码中唯一的一个n-k次多项式，这唯一的n-k次多项式g(x)称为码的生成多项式,可以证明生成多项式g(x)具有以下特性：（1）g(x)是一个常数项为1的 次多项式；（2）g(x)是 的一个因式；（3）该循环码中其它码多项式都是g(x)的倍式。g(x)，xg(x)，xk-1g(x),54,g(x)，xk-1g(x)都是许用码组，连同g(x)共k个许用码组，构成码的生成矩阵G(x),注：该生成矩阵并不是典型形式的，但可通过

23、线性变换变换成典型的生成矩阵。,55,一旦生成多项式g(x)确定以后，该循环码的生成矩阵G(x)就可以确定，进而该循环码的所有码字就可以确定。生成矩阵G(x)的每一行都是一个码组。,例试求（7，3）循环码的生成多项式和生成矩阵。,生成多项式g(x)是xn+1的一个因式，且g(x)是一个n-k次因式。因此，就可以先对xn+1进行因式分解，找到它的n-k次因式。,56,解2：对（7,3）循环码，n=7，k=3,r=4第一步：对x7+1进行因式分解得：x7+1=(x+1)(x3+x2+1)(x3+x+1).(1)第二步：构造r=n-k次生成多项式g(x)。要从式（1）中找到r=n-k=4次的因子,这

24、样的因子有两个：(x+1)(x3+x2+1)=x4+x2+x+1(a)(x+1)(x3+x+1)=x4+x3+x2+1(b)第三步：若按(a)构成生成多项式:生成多项式为：g(x)=x4+x2+x+1,57,生成矩阵为：,将第1行与第3行模2加作为第1行，则有,为典型生成矩阵,58,若按(b)构成生成多项式:生成多项式为：g(x)=x4+x3+x2+1生成矩阵为：,进行线性变换，得典型生成矩阵为：,59,3、循环码的监督多项式与监督矩阵,其中 是 逆多项式,1、方法1：,60,方法2：,根据生成矩阵和监督矩阵的关系求：G=IkQ，H=PIr其中P=QT,例试求（7，3）循环码的监督多项式和监督

25、矩阵。已知生成多项式g(x)=x4+x3+x2+1,61,二、循环码的编码、解码方法,1、编码方法,（1）原理,62,首先从xn+1的因子中选一个（n-k）次多项式作为g(x)；然后，利用循环码的编码特点，即所有循环码多项式V(x)都可以被g(x)整除，来定义生成多项式g(x)。,(2)编码步骤,设信息位对应的多项式为m(x)用xn-k乘m(x)，相当于把信息码后附加上（n-k）个“0”用g(x)除xn-k m(x)，得到余式为r(x)编出码组为：V(x)=xn-k m(x)+r(x),63,例题 设（7，3）循环码的生成多项式为g(x)=x4+x2+x+1，待编码信息位为110，求对应循环码

26、码组。,即余式r(x)=x2+1于是，对应码组V(x)=xn-k m(x)+r(x）=x6+x5+x2+1 编码为1100101,解：m(x)=x2+x，xn-k m(x)=x4(x2+x)=x6+x5,64,2、译码方法,（1）目的检错、纠错,（2）采用手段：,判断接收到的码组多项式B(x)是否能被生成多项式g(x)整除作为依据 当传输中未发生错误时，B(x)=V(x)，则接收的码组B(x)必能被g(x)整除；若传输中发生了错误，B(x)V(x)，B(x)不能被g(x)整除 B(x)V(x)，B(x)能被g(x)整除 不可检错误,65,3、译码步骤,由接收到的码多项式B(x)计算校正子（伴随式）多项式S(x)；即求解B(x)整除g(x)的余式r(x)由校正子S(x)确定错误图样E(x)；将错误图样E(x)与B(x)相加，纠正错误。,66,8.4小结,1、纠错编码的基本概念,码重、码距、编码效率、最小码距，差错控制方法,2、最小码距与检测纠错能力的关系,3、线性分组码的编码译码原理，监督矩阵和生成矩阵 的概念,