第12章 差错控制编码,内容简介： 12.1 引言 12.2 纠错编码的原理 12.3 常用的简单编码 12.4 线性分组码 12.5 循环码,主要内容： 1.基本概念：码重,码距,检错能力,纠错能力 2.常用编码 3.线性分组码 4.循环码,回放,信道,解调,信源,编码,加密,调制,解密,译码,信宿,噪声,同步系统,信源编码 信道编码 误差控制,ASK FSK PSK DPSK,数字通信的组成,在通信过程中，会受到各种外来干扰，如脉冲干扰，随机 噪声干扰，人为干扰及通信线路传输性能的限制都将使信号失 真。由于以上原因，引起数据信息序列产生错误，称之为差错。,实际信道中，上述两种错误常同时存在。,随机性错误：前后出错位之间无一定关系，随机、离散出现。 突发性错误：差错成串出现，且有一定相关性。,差错的两大类型：,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。,码距的大小关系到编码的纠检错能力。,例：10011 w=3 01101 d=4,n=3时，码距的几何说明：,（ a2 a1 a0 ）,a2,a1,a0,（ 110） （ 011 ）,d=2,110,011,（ 111） （ 000 ）,d=3,000,111, 增加一个监督位，取11A、00B,若收到01或10时， 可知发生了错误，但不能纠正错误。, 再增加一个监督位，取111A、000B,如一位错： B001 A110；若两位错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个随机错误，则要求：d0 e+1 2/ 纠正t个随机错误，则要求：d0 2t+1 3/ 纠正t个同时检测e(et)个随机错误，则 要求： d0 e+t+1,纠（检）错能力的几何解释,e检错能力 t纠错能力,（1）,时能检出e个或e个以下错码。,（2）,（3）,时能纠正t个或t个以下错码。,时能检出t个或e个以下错码。,4、对纠错编码的要求,纠、检错能力强，编码效率高，码长短， 编码规律简单。,例：,一个码集，只有两个许用码：0000、1111， 试求其纠检错能力和编码效率。,解：,根据码距的定义，则该码集d 0 = 4，,1/ 用于检错，e d0 1=3，即可检3个错误；,2/ 用于纠错，t (d01)/2=3/2，取整，即可纠1个错误；,3/ 同时用于纠、检错， d0 e+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个数是奇数（奇监督码） 或偶数（偶监督码）。,序 码 字 序 码 字 号 信息码元 监督元 号 信息码元 监督元 a4 a3 a2 a1 a0 a4 a3 a2 a1 a0 0 0 0 0 0 0 8 1 0 0 0 1 1 0 0 0 1 1 9 1 0 0 1 0 2 0 0 1 0 1 10 1 0 1 0 0 3 0 0 1 1 0 11 1 0 1 1 1 4 0 1 0 0 1 12 1 1 0 0 0 5 0 1 0 1 0 13 1 1 0 1 1 6 0 1 1 0 0 14 1 1 1 0 1 7 0 1 1 1 1 15 1 1 1 1 0,码长5的偶监督码,偶监督码编码器,偶监督码的检错电路,例：一数据序列： 11100 10111 01101 10001 10101,试对其进行（6，5）偶校验编码，写出码序列 并分析其抗干扰能力,解：,（6，5）,将数据序列每5码元分组，,并作：,的运算,可得出编码数据序列：,111001101110011011100010101011,只能检测出奇数个错误，不能发现偶数个错误， 也不能纠错。, ,二. 二维奇偶监督码,行监督位,列监督位,水平垂直奇偶校验码： 又称行列监督码或二维奇偶监督码。 特点： 对水平方向和垂直方向的码元同时实施奇偶监督。,1 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 0 0 1 1 1 1 0 0,行 列 监 督 码,特点：,（1）能检测出每一行（列）中的奇数个或偶数个错码，但不能检测出行列同时成偶数个出现的错码。,（2）能检测突发性错误（成串错码）。,（3）能纠正错码。,恒比码： 又称等重码或定1码。 特点： 码组中0，1的个数保持不变。 若码长为n，码重为w，则此码的码字个数 为：Cnw，禁用码字个数为：2n - Cnw,例如：我国的电报，每个汉字用四个10进制数表 示，每位10进制数就采用 3：2 恒比码构 成的5位码组来表示。,码字的个数C53 =10,检错能力较强，可检出所奇数和部分偶数错误。,作业：,正反码： 简单的可纠错编码，信元数等于监督元数 特点： 信息位中，有奇数个1时，监督位重复信息位； 信息位中，有偶数个1时，监督位取信息位的反码；,可纠一位、检测所有两位错和部分两位以上的错误。,例：,11001 1100111001,10001 1000101110,(n,k) 其中k=n/2 编码效率： R=k/n=1/2,四.正反码,例：信息位：11001 监督位：11001 信息位：10001 监督位：01110,1.编码规则：,（1）当信息位中有奇数个1时，监督位是信息位的简单重复。,（2）当信息位中有偶数个1时，监督位是信息位的反码。,例：11001 11001=00000 10001 01110=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）分组码为例,计算监督位,判断错码位置,按上述方法构造的纠正单个错误的线性