第十二章-差错控制xin.ppt

第12章差错控制编码,内容简介：12.1引言12.2纠错编码的原理12.3常用的简单编码12.4线性分组码12.5循环码,主要内容：1.基本概念：码重,码距,检错能力,纠错能力2.常用编码3.线性分组码4.循环码,回放,信道,解调,信源,编码,加密,调制,解密,译码,信宿,噪声,同步系统,信源编码信道编码误差控制,ASKFSKPSKDPSK,数字通信的组成,在通信过程中，会受到各种外来干扰，如脉冲干扰，随机噪声干扰，人为干扰及通信线路传输性能的限制都将使信号失真。由于以上原因，引起数据信息序列产生错误，称之为差错。,实际信道中，上述两种错误常同时存在。,随机性错误：前后出错位之间无一定关系，随机、离散出现。突发性错误：差错成串出现，且有一定相关性。,差错的两大类型：,12.1引言,数字通信中的编码分为：,信道编码：,信源编码：,为提高信号传输的有效性而采取的措施。,为提高信号传输的可靠性而采取的措施。亦称差错控制编码。,在发送端利用信道编码器在数据信息中增加一些监督信息，使不带规律性或规律性不强的原始数字信号变为带规律性或加强了规律性的数字信号，信道译码器则利用这些规律性来鉴别是否发生错误，或进行错误纠正。,差错控制,1、差错控制方法,方法和设备简单，无需纠检错编译系统。但需要双向信道，传输效率、实时性差。,(3)检错重发法ARQ,所发码具有检错能力，收端接收后判决是否出错，通过反向信道发送判决结果，发端据此决定是否重发。,译码设备简单，对突发错误有效，要求有反馈信道。,工作过程：发送检测回复重发或发送新的数据,停止等待方式,ARQ的三种实现方式：,特点：半双工工作，简单，要求的缓存量小，但等待时间较长，,传输效率,连续重发方式,退N步方式：从出错帧开始重发例N=4,优缺点：传输效率，但重发的N帧中，大部分为正确，所以仍有浪费。发端缓存必须可存N帧。,只对出错信息重发，因此传输效率大大提高。但收发两端都要有足够的存储空间。,选择重发方式,反馈信道,ARQ,FEC编码器,正向信道,FEC译码器,ARQ,编码既有纠错能力也有检错能力，收端收到信息码组后在收端进行检测。在纠错范围内：纠正；超出范围：通过ARQ方式进行重发。,(4)混合方式,（1）,根据各码组信息码和监督码的关系分：线性码，非线性码,根据监督码元是否仅与本组信息元有关分组码，卷积码,（2）,根据纠错码组中信息元是否隐蔽分：系统码，非系统码,（3）,根据码的用途分：检错码，纠错码,（4）,根据码元的取值：二进制码，多进制码,（5）,根据构造编码的数学方法：代数码，几何码，算术码,（6）,2、纠错码的分类,12.2纠错编码的基本原理,1、几个术语,本课程主要讨论纠随机错误的二进制线性分组码。,码长：码组中码元的数目，常用n表示；,码距：两等长码字C1、C2对应位上取值不同的数目，又称为汉明(Hamming)距离，记为d(c1,c2)。,码重：码组中非零码元的数目，记为W；,最小码距：在分组码(n,k)中，任意两个码字之间汉明距离的最小值，记为dmin。,码距的大小关系到编码的纠检错能力。,例：10011w=301101d=4,n=3时，码距的几何说明：,（a2a1a0）,a2,a1,a0,（110）（011）,d=2,110,011,（111）（000）,d=3,000,111,增加一个监督位，取11A、00B,若收到01或10时，可知发生了错误，但不能纠正错误。,再增加一个监督位，取111A、000B,如一位错：B001A110；若两位错011,110则只能发现不能纠错,可以看出：差错控制是以牺牲传输效率为代价而换取了传输质量的提高的。纠检错能力与加入的监督元数目成正比。,2、纠错或检错的原理,分组码的三个参数码长n，信息位k，最小距离d0，用符号(n,k,d0)表示,R=k/n为编码效率，d0一定(纠错能力一定)时，k/n大，效率高。,对被传输的信息序列分组，每组为k个信息元，对每组按某种关系附加(n-k)个监督码元(校验)，形成为n位的码字。这种方法构成的码组称为分组码。,分组码的表示：符号（n，k）,n码组的总位数,k码组中信息码元的数目,r=n-k监督码元的数目,编码效率,R越大，信息位比重大，有效性越高。,3、分组码的纠(检)错能力与最小码距d0的关系,任一（n，k）分组码，若要在码字内能：1/检测e个随机错误，则要求：d0e+12/纠正t个随机错误，则要求：d02t+13/纠正t个同时检测e(et)个随机错误，则要求：d0e+t+1,纠（检）错能力的几何解释,e检错能力t纠错能力,（1）,时能检出e个或e个以下错码。,（2）,（3）,时能纠正t个或t个以下错码。,时能检出t个或e个以下错码。,4、对纠错编码的要求,纠、检错能力强，编码效率高，码长短，编码规律简单。,例：,一个码集，只有两个许用码：0000、1111，试求其纠检错能力和编码效率。,解：,根据码距的定义，则该码集d0=4，,1/用于检错，ed01=3，即可检3个错误；,2/用于纠错，t(d01)/2=3/2，取整，即可纠1个错误；,3/同时用于纠、检错，d0e+t+1（et）取：e=2，t=1，则可满足上式，即可检2个错误同时纠一个错；,R=k/n=1/4,编码效率：,5.差错控制编码的效用：,假设在随机信道中，发送“0”和“1”的错误概率相等，都等于p，且p1，在码长为n的码组中，发生r个错误的概率为：,例如：当n=7，p=10时，则有：,由此可见，即使仅能纠正1-2个错误，也可使误码率下降几个数量级。所以差错控制编码具有较大的实际应用价值。,例12-1已知8个码组为：（O00000），（001110），（010101），（011011），（100011），（1O1101），（110110），（111000），（1）求以上码组的最小码距；（2）若此8个码组用于检错，可检出几位错？（3）若用于纠错码，能纠几位？（4）若同时用于纠错和检错，纠错、检错性能如何？,（1）,（2）,（3）,（4）,例12-2已知两码组（0000）和（1111），若该码组用于检错，能检出几位错码？若用于纠错，能纠正几位错码？若同时用于纠错和检错，问各能纠、检几位错码？,（1）,（2）,（3）,一.奇偶监督码,在信息为后加一位校验位,12.3常用的简单编码,奇监督码,偶监督码,特点：只能检测出奇数个错码，不能检测出偶数,奇偶监督码：k=n-1,r=1的线性码。特点：码组中的1个数是奇数（奇监督码）或偶数（偶监督码）。,序码字序码字号信息码元监督元号信息码元监督元a4a3a2a1a0a4a3a2a1a0000000810001100011910010200101101010030011011101114010011211000501010131101160110014111017011111511110,码长5的偶监督码,偶监督码编码器,偶监督码的检错电路,例：一数据序列：1110010111011011000110101,试对其进行（6，5）偶校验编码，写出码序列并分析其抗干扰能力,解：,（6，5）,将数据序列每5码元分组，,并作：,的运算,可得出编码数据序列：,111001101110011011100010101011,只能检测出奇数个错误，不能发现偶数个错误，也不能纠错。,二.二维奇偶监督码,行监督位,列监督位,水平垂直奇偶校验码：又称行列监督码或二维奇偶监督码。特点：对水平方向和垂直方向的码元同时实施奇偶监督。,110010100000100001101001111000011100111000001010101010111000111100,行列监督码,特点：,（1）能检测出每一行（列）中的奇数个或偶数个错码，但不能检测出行列同时成偶数个出现的错码。,（2）能检测突发性错误（成串错码）。,（3）能纠正错码。,恒比码：又称等重码或定1码。特点：码组中0，1的个数保持不变。若码长为n，码重为w，则此码的码字个数为：Cnw，禁用码字个数为：2n-Cnw,例如：我国的电报，每个汉字用四个10进制数表示，每位10进制数就采用3：2恒比码构成的5位码组来表示。,码字的个数C53=10,检错能力较强，可检出所奇数和部分偶数错误。,作业：,正反码：简单的可纠错编码，信元数等于监督元数特点：信息位中，有奇数个1时，监督位重复信息位；信息位中，有偶数个1时，监督位取信息位的反码；,可纠一位、检测所有两位错和部分两位以上的错误。,例：,110011100111001,100011000101110,(n,k)其中k=n/2编码效率：R=k/n=1/2,四.正反码,例：信息位：11001监督位：11001信息位：10001监督位：01110,1.编码规则：,（1）当信息位中有奇数个1时，监督位是信息位的简单重复。,（2）当信息位中有偶数个1时，监督位是信息位的反码。,例：1100111001=000001000101110=11111,2.译码方法,（1）将码组中的信息码与监督码进行模2加得合成码组。,（2）若信息码中有奇数个1，则合成码组即为检验码组。若信息码中有偶数个1，则合成码组的反码即为检验码组。,（3）观察检验码组中1的个数，按p278进行检错和纠错。,12.4线性分组码,线性分组码中信息码元和监督码元是用线性方程联系起来的。线性码建立在代数学群论基础上，线性码各许用码组的集合构成代数学中的群，因此，又称群码。主要性质任意两许用码组之和(模2和)仍为一许用码组。(封闭性)码的最小距离等于非零码的最小重量。,奇偶监督码是一种最简单的线性码，偶校验时,S称为校正子，又称伴随式。S=0无错，S=1有错。一般，由r个监督方程式计算得r个校正子，可以用来指示2r-1种错误，对于一位误码来说，就可以指示2r-1个误码位置。对于(n,k)码，如果满足2r-1n则可能构造出纠正一位或一位以上错误的线性码。,设分组码(n,k)中k=4,为纠正一位错码,要求r3,则n=k+r=7,一.以（7，4）分组码为例,计算监督位,判断错码位置,按上述方法构造的纠正单个错误的线性分组码称为汉明码。码长n=2r1信息位k=2r1r监督位r,（1）,（2）,码字：A=（）,其中信息位：,监督位：,若分组码可用下列线性方程组表示：,（“”为模2加）,则：该分组码为（7，4）线性分组码（共有16个码字）,表9-2(7,4)码的码字表,性质：,（1）封闭性：任意2个许用码组之和（模2加）仍为一个许用码组。,（2）有零元：,（3）有负元：,（4）结合律成立：,（任一码字即为本身的负元）,编码速率=,（1）改写为,表示成矩阵形式,=,二.监督矩阵H,用矩阵表示为：,并记为：,H阵可表示为：,（阶）,（阶单位阵）,矩阵H称为（7，4）线性分组码得监督矩阵。上式也称为典型监督矩阵。若不是典型监督矩阵要用初等变换化成典型矩阵。,三.生成矩阵G,若信息码元已知，通过监督矩阵可以求出监督码元。,用矩阵表示：,或,将上式扩展可以由已知信息码元求得整个码组。,令：,G称为生成矩阵,典型监督矩阵和典型生成矩阵存在以下关系式：,例：（7，4）,全部码字为：,四.伴随式（校正子）S,设发送码字为，接收码字为，由于干扰，噪声可能引入误差，使接收码组与发送码组不同，因此有，其中是传输中产生的错误行矩阵。对于二进制码元有:,E矩阵中哪一位码元为1就表示接收码字中对应位有错。E称为错误图样。,模2,在接收端用H来检测接收B中的错码。,令：,伴随式或校正子：,如果B与A相同，则：,否则：,又,表示校正子S仅与信道的错误图样E有关，而与发送的码字A无关。,表9-3(7,4)码S与E的对应关系,五.如何利用S完成纠错,对（7，4）线性分组码,设B中最高位有错，错误图样,它的转置,恰好是典型H阵的第一列。,同理可求出：,若次高位有错,，即恰好是H的第二列。,因此，在接收码组中只错一位码元情况下，计算出的校正子S总是和典型监督矩阵中的某一行相同。,例：,与第三列相同,正确码组为：,六.汉明码,汉明码是一种可以纠正单个随机错误的线性分组码。它的最小码距，监督元位数，码长，信息元位数，编码效率当r很大时，因此是一种高效码。,上例中的（7，4）线性分组码就是汉明码，并且任意调换H矩阵中各列的结果不会影响纠，检错能力。,例设且有3个接收码组,验证3个接收码组是否发生差错？若在某码组中有错码，错码的校正子是什么？然后再指出发生错码的码字中，哪位有错？,解：1）若无错，则错误图样为0，S为0,B1无错,B2错,B3错,2）,S2=H第1列E=100000第1位错同理S3=H第3列E=001000第3位错,12.5循环码,一.概念,1.循环码：线性分组码,（1）封闭性,（2）循环性：循环码中任一许用码组经过循环移位之后，所得到的码组仍为一许用码组。,2.码多项式,循环码的一许用码组可表示为：,其中：x为码元位置标记，不考虑其取值。码元只取“1”或“0”。,例:(7，3）循环码中第二个码组,如何实现移位：乘一个x相当于码左移一位。,3.按模运算,若,（的次数小于）,则：,称为按模运算后的余式。,例：,4.规律,（1）循环码中，将许用码组左移一位得到的码字记为：。其码多项式为：,可以证明：,（2）根据循环码的定义，均为许用码字。因此下列结论：若是许用码字，则在按模运算下，也是许用码字。,即：若,则也是许用码字。,例:(7，3）循环码,则：,那么,其码字为。,二.生成多项式与生成矩阵G,1.(n，k)循环码码组集合中（全“0”除外）最高阶数最小的多项式（n-k）阶称为生成多项式，记为g(x)。,2.集合中其它码多项式都是运算下的余式。即可以由生成多项式g(x)产生循环码的全部码字。,3.生成矩阵G,循环码的生成矩阵多项式可以写成,以（7，3）循环码为例,经线性变换，将G整理成典型生成矩阵。,整个码组可表示为：,任意一个码多项式都能被g(x)整除。,三.监督多项式、监督矩阵,1.对于(n，k)循环码，可分解成g(x)和其它因式的乘积。,记为：,称h(x)为监督多项式，其矩阵形式为：,以（7，3）循环码为例,2.,对于（7，3）循环码，g(x)的最高次为4,所以，有两种方案,第一种方案：,码字：,第二种方案：,码字：,例:已知(7，4）循环码的生成多项式为（1）求典型生成矩阵和典型监督矩阵；（2）输入信息码为11001011，求编码后的系统码；（3）全部码组；（4）纠、检错能力,解：,全部码字为：,四.编码电路,1.对于(n，k)循环码中，可用多项式表示为：,其中：m(x)为不大于（k-1）次的多项式，代表信息码元。r(x)为不大于(r-1)次的多项式，代表监督码元。,或：,该式提供了循环码编码的数学依据。,2.步骤：方法（一）,（1）信息多项式m(x)左移n-k位。（相当于）,（2）求其模g(x)的余式r(x),（3）余式的系数作监督码元，附加在信息码元之后形成循环码。,方法二：对于给定的信息码组m(x)和G(x),直接相乘即可。方法三：对于给定的信息码组m(x)和g(x)，相应的码多项式为T(x),例:已知(7，3）循环码的生成多项式为求信息位为101时的码字。解：,3.编码电路,首先，四级移位寄存器清零，三位信息码元到来时，门1断开，门2接通，直接输出信息元。第3次移位脉冲来时将除法电路运算所得的余数存入四级移位寄存器，第47次移位时，门2断开，门1接通，输出监督码元（即余数）。当一个码字输出完毕后就将移位寄存器清零，等待下一组信息码元输入后重新编码。,4.解码,（1）只检错,设发送码组为A，接收码组为B。,B不出错时，有B(x)=A(x),则：能整除。,余数不为0时，B有错。,框图：,（2）纠错,用B(x)除以g(x)得到余式按余式用查表的方法或通过某种运算得到E(x)。T(x)=-E(x),例：12-6令为(7，4)循环码的生成多项式。(1)求出该循环码的生成矩阵和监督矩阵；(2)若两个信息码组分别为(1001)和(0110),求出这两个循环码组；(3)画出其编码器原理框图。,解：（1）,（2）,（3）,（4）,9.6卷积码在编码器复杂性相同的情况下,卷积码的性能优于分组码.,卷积码把k个信息位编n位,k和n通常很小,特别适宜于串行形式传输,延时小.n个码元与当前段的k个信息位有关,而且与前N-1段的信息有关,编码过程相互关联的码元为Nn个.N或nN称为卷积码的约束长度,常把卷积码记作(n,k,N),卷积码的一般结构,由上图可以看到，n个输出比特不仅与当前的k个输入信息有关，还与前（N-1）k个信息有关。通常将N称为约束长度，（有的书的约束长度为Nn）。常把卷积码记为：（n，k，N）其编码效率为：k/n,卷积码的图解表示,（3，1，2）卷积码