第九章差错控制编码_sxq

第9章差错控制编码南京航空航天大学信息科学与技术学院通信原理教研组22222copyright信息科学与技术学院通信原理教研组2引言1纠错编码的基本原理2常用的简单编码3线性分组码4循环码5第9章差错控制编码67卷积码网格编码调制33333copyright信息科学与技术学院通信原理教研组39.1引言信道解调信源编码加密调制解密译码信宿噪声同步系统信源编码信道编码差错控制ASKFSKPSKDPSK数字通信的组成A/D数据压缩44444copyright信息科学与技术学院通信原理教研组4采用信道编码在通信过程中，会受到各种外来干扰，如脉冲干扰，随机噪声干扰，人为干扰及通信线路传输性能的限制都将使信号失真。由于以上原因，引起数据信息序列产生错误，称之为差错。随机性错误：前后出错位之间无一定关系，随机、离散出现。突发性错误：差错成串出现，且有一定相关性。差错的两大类型：合理的设计基带信号时域/频域均衡都能有效的提高传输可靠性。发射功率的提高55555copyright信息科学与技术学院通信原理教研组5数字通信中的编码信道编码：信源编码：为提高信号传输的有效性而采取的措施。为提高信号传输的可靠性而采取的措施,亦称差错控制编码。在发送端利用信道编码器在数据信息中增加一些监督信息，使不带规律性或规律性不强的原始数字信号变为带规律性或加强了规律性的数字信号，信道译码器则利用这些规律性来鉴别是否发生错误，或进行错误纠正。差错控制66666copyright信息科学与技术学院通信原理教研组61、差错控制方法（1）前向纠错法FEC所发码具有纠错能力，收端接收后自动纠错，无需反向信道。实时性好，但译码设备复杂，传输效率↓。信源FEC编码信道FEC译码信宿77777copyright信息科学与技术学院通信原理教研组7（2）信息反馈法IF信息信号信息信号发端收端方法和设备简单，无需纠检错编译系统。但需要双向信道，传输效率↓、实时性差。88888copyright信息科学与技术学院通信原理教研组8(3)检错重发法ARQ所发码具有检错能力，收端接收后判决是否出错，通过反向信道发送判决结果，发端据此决定是否重发。译码设备简单，对突发错误有效，要求有反馈信道。信源编码器正向信道译码器信宿缓存器重发控制器反向信道重发判决器工作过程：发送——检测——回复——重发或发送新的数据99999copyright信息科学与技术学院通信原理教研组9①停止等待方式3221221发送端接收端ARQ的三种实现方式：特点：半双工工作，简单，要求的缓存量小，但等待时间较长，传输效率↓1010101010copyright信息科学与技术学院通信原理教研组10②连续重发方式6543254321065432543210退N步方式：从出错帧开始重发优缺点：传输效率↑，但重发的N帧中，大部分为正确，所以仍有浪费。发端缓存必须可存N帧。1111111111copyright信息科学与技术学院通信原理教研组112987654321029876543210只对出错信息重发，因此传输效率大大提高。但收发两端都要有足够的存储空间。③选择重发方式1212121212copyright信息科学与技术学院通信原理教研组12反馈信道ARQFEC编码器正向信道FEC译码器ARQ编码既有纠错能力也有检错能力，收端收到信息码组后在收端进行检测。在纠错范围内：纠正；超出范围：通过ARQ方式进行重发。(4)混合方式1313131313copyright信息科学与技术学院通信原理教研组13（1）根据各码组信息码和监督码的关系分：线性码，非线性码根据监督码元是否仅与本组信息元有关分组码，卷积码（2）根据纠错码组中信息元是否隐蔽分：系统码，非系统码（3）纠错码的分类1414141414copyright信息科学与技术学院通信原理教研组14根据码的用途分：检错码，纠错码（4）根据码元的取值：二进制码，多进制码（5）根据构造编码的数学方法：代数码，几何码，算术码（6）本课程主要讨论纠随机错误的二进制线性分组码。1515151515copyright信息科学与技术学院通信原理教研组15纠错码的发展概况通信的数学理论，Shannon(1948)汉明码，Hamming(1950)级连码，Forney(1966)卷积码及有效译码，(60年代)RS码及有效译码，(60年代)TCM，Ungerboeck(1982),Forney(1984)Turbo码，Berrou(1993)LDPC码，Gallager(1963),Macky(1996)空时编码,Tarokh(2000)1616161616copyright信息科学与技术学院通信原理教研组169.2纠错编码的基本原理1、几个术语码长：码组中码元的数目，常用n表示；码距：两等长码字C1、C2对应位上取值不同的数目，又称为汉明(Hamming)距离，记为d(c1,c2)。码重：码组中非零码元的数目，记为W；1717171717copyright信息科学与技术学院通信原理教研组17n=3时，码距的几何说明：（a2a1a0）a2a1a0（110）（011）d=2110011（111）（000）d=3000111最小码距：在分组码(n,k)中，任意两个码字之间汉明距离的最小值，记为dmin。最小码距的大小关系到编码的检纠错能力。0101011000011818181818copyright信息科学与技术学院通信原理教研组18发送序列C:(1111011000)接收序列R:(0110010110)比较C和R，可写出另一个序列E：1001001110R=C+E序列E定义为错误图样(ErrorPattern)错误图样：1919191919copyright信息科学与技术学院通信原理教研组19A、B两消息，可用一位二进制数表示，A=1、B=0出错时无法判定增加一个监督位，取11→A、00→B再增加一个监督位，取111→A、000→B许用码组：00，11禁用码组：01，10若收到01或10时，可知发生了错误，但不能纠正错误。许用码组：000，111禁用码组：001,010,100,011,101,110如一位错能够纠正错误；若两位错，则只能发现不能纠错2、纠错或检错的原理2020202020copyright信息科学与技术学院通信原理教研组20因此这种（3,1）码，能纠正一个错，发现两个错。但是(3,1)码中，数据位仅为1位，监督位为两位，传输效率↓↓可以看出：差错控制是以牺牲传输效率为代价而换取了传输质量的提高的。纠检错能力与加入的监督元方式和数目有关。2121212121copyright信息科学与技术学院通信原理教研组21分组码的三个参数码长n，信息位k，最小距离d0，用符号(n,k,d0)表示k个信息元an-1an-2……arar-1……a0r个监督元码长：n=k+rR=k/n为编码效率，d0一定(纠错能力一定)时，k/n大，效率高。对被传输的信息序列分组，每组为k个信息元，对每组按某种关系附加(n-k)个监督码元(校验)，形成为n位的码字。这种方法构成的码组称为分组码。3、分组码2222222222copyright信息科学与技术学院通信原理教研组224、分组码的纠(检)错能力与最小码距d0的关系任一（n，k）分组码，若要在码字内能：1/检测e个随机错误，则要求：d0≥e+12/纠正t个随机错误，则要求：d0≥2t+13/纠正t个同时检测e(et)个随机错误，则要求：d0≥e+t+12323232323copyright信息科学与技术学院通信原理教研组231纠（检）错能力的几何解释A1d0eA2（a）A1A2d0et（c）A1d0tA2（b）A2t112424242424copyright信息科学与技术学院通信原理教研组24[例9-1]一个码集，只有两个许用码：0000、1111，试求其纠、检错能力和编码效率。2525252525copyright信息科学与技术学院通信原理教研组25解：根据码距的定义，则该码集d0=4，1/用于检错，e≤d0–1=3，即可检3个错误；2/用于纠错，t≤(d0–1)/2=3/2，取整，即可纠1个错误；3/同时用于纠、检错，d0≥e+t+1（e＞t）取：e=2，t=1，则可满足上式，即可检2个错误同时纠一个错；R=k/n=1/4编码效率：2626262626copyright信息科学与技术学院通信原理教研组264、对纠错编码的要求纠、检错能力强，编码效率高，码长短，编码规律简单。2727272727copyright信息科学与技术学院通信原理教研组275.差错控制编码的效用假设在随机信道中，发送“0”和“1”的错误概率相等，都等于p，且p＜＜1，在码长为n的码组中，发生r个错误的概率为：!()(1)!()!rrnrrnnnPrCppprnr2828282828copyright信息科学与技术学院通信原理教研组28!()(1)!()!rrnrrnnnPrCppprnr例如：当n=7，p=10-³时，则有：371077)1(pP5227101.221)!27(!2!7)2(ppP8337105.335)!37(!3!7)3(ppP由此可见，即使仅能纠正1-2个错误，也可使误码率下降几个数量级。所以差错控制编码具有较大的实际应用价值。2929292929copyright信息科学与技术学院通信原理教研组296.有扰信道编码定理（Shannon第二定理）对于给定的有扰信道，若信道容量为C，只要发送端以低于C的信息速率Rb发送信息，则一定存在一种编码方法，使得译码错误概率P随着码长n的增加，按指数下降至任意小的值，表示为Pe-nE(Rb)E(Rb)为误差指数，RbC时，E(Rb)0。Rbmax=C=Blog2(1+S/N)（bit/s）3030303030copyright信息科学与技术学院通信原理教研组301.码长n和信息速率Rb一定时，随C误差指数E(Rb)P↓随指数下降。其中C=Blog2(1+S/N)（bit/s）2.在C和Rb一定时(RbC)，随码长nP随指数下降(P0)。数字传输系统中，无误码传输的最高信息速率Rbmax=C=Blog2(1+S/N)（bit/s）两个结论：3131313131copyright信息科学与技术学院通信原理教研组31编码性能举例未采用纠错编码时，若接收信噪比等于7dB，编码前误码率约为810-4，图中A点，在采用纠错编码后，误码率降至约410-5，图中B点。这样，增大发送功率,就能降低误码率约一个半数量级。10-610-510-410-310-210-1编码后PeAB信噪比(dB)3232323232copyright信息科学与技术学院通信原理教研组32由图还可以看出，若保持误码率在10-5，图中C点，未采用编码时，约需要信噪比Eb/n0=9.5dB。在采用这种编码时，约需要信噪比7.5dB，图中D点。可以节省功率2dB。通常称这2dB为编码增益。上面两种情况付出的代价是带宽增大。10-610-510-410-310-210-1PeCD信噪比(dB)编码后3333333333copyright信息科学与技术学院通信原理教研组33传输速率和Eb/n0的关系对于给定的传输系统式中，RB为码元速率。若希望提高传输速率，由上式看出势必使信噪比下降，误码率增大。假设系统原来工作在图中C点，提高速率后由C点升到E点。但加用纠错编码后，仍可将误码率降到D点。这时付出的代价仍是带宽增大。10-610-510-410-310-210-1编码后PeCDE信噪比(dB)3434343434copyright信息科学与技术学院通信原理教研组349-3常用的简单编码1、奇偶监督码：k=n-1,r=1的线性码。特点：码组中的1个数是奇数（奇监督码）或偶数（偶监督码）。0021aaann偶监督时，要满足：1021