第11章 差错控制编码 电信课件.ppt

,第11章 差错控制编码,本章知识点:1、了解差错控制技术种类 2、掌握纠错编码原理、最小码距和检错、纠错之间关系；了解奇偶监督码、恒比码编码方法。3、掌握线性分组码编码和译码方法 4、掌握循环码编码和译码方法,11.1 概述11.2 纠错编码的基本原理11.3 纠错编码的性能11.4 简单的实用编码11.5 线性分组码11.6 循环码11.7 卷积码11.8 Turbo码11.9 低密度奇偶校验码11.10 网格编码调制11.11 小结,第11章 差错控制编码,2023年1月22日,3,为保证运送途中不出现打碎灯泡的情况,有效性,可靠性,11.1 概述,2023年1月22日,4,通信中的情况：,针对乘性干扰,针对加性干扰,合理选择调制/解调方法，增大发射功率,采用均衡等措施,11.1 概述,2023年1月22日,5,11.1 概述,差错控制编码,2023年1月22日,6,11.1 概述,信道分类(从差错控制角度看)：,随机信道：错码的出现是随机的。,突发信道：错码是成串集中出现的。,混合信道：既存在随机错码又存在突发错码。,差错控制技术的种类：,检错重发,前向纠错,反馈校验,检错删除,信道编码分类：,线性码和非线性码,分组码和卷积码,系统码和非系统码,2023年1月22日,7,11.1 概述,不同的编码方法，有不同的检错或纠错能力。,多余度：就是指增加的监督码元多少。例如，若编码序列中平均每两个信息码元就添加一个监督码元，则这种编码的多余度为1/3。,编码效率(简称码率)：设编码序列中信息码元数量为k，总码元数量为n，则比值k/n 就是码率。,冗余度：监督码元数(n-k)和信息码元数 k 之比。,理论上，差错控制以降低信息传输速率为代价换取提高传输可靠性。,监督码元：在4种差错控制技术中除第3种外，都是在接收端识别有无错码。所以在发送端需要在信息码元序列中增加一些差错控制码元，它们称为监督码元。,2023年1月22日,8,11.2 纠错编码的基本原理,1、分组码基本原理,将信息码分组，为每组信息码附加若干监督码的编码称为分组码。在分组码中，监督码元仅监督本码组中的信息码元。,卷积码又称连环码。卷积码编码器把k比特信息段编成n比特的码组，但所编的n长码组不仅同当前的k比特信息段有关，而且还同前面的(N-1)个(N1,整数)信息段有关联。,2023年1月22日,9,11.2 纠错编码的基本原理,1、分组码基本原理,规则：使码组中“1”的个数为偶数,情形1：没有冗余 不能发现错误,情形2：加入冗余 可以发现错误,冗余,另外4个码组,许用码组,禁用码组,2023年1月22日,10,11.2 纠错编码的基本原理,1、分组码基本原理,规则：使码组中“1”的个数为偶数,情形1：没有冗余 不能发现错误,情形2：加入冗余 可以发现错误,冗余,另外4个码组,许用码组,禁用码组,只能检出一个码组中1个和3个(奇数)错码的情况，不能发现2个(偶数)错码的情况，也不能纠正错误。,2023年1月22日,11,11.2 纠错编码的基本原理,1、分组码基本原理,情形1：没有冗余 不能发现错误,情形2：加入冗余 可以发现错误,2023年1月22日,12,11.2 纠错编码的基本原理,1、分组码基本原理,这时，能够发现 2个以下错码，或者纠正 1位 错码。,2023年1月22日,13,11.2 纠错编码的基本原理,1、分组码基本原理,综上所述,不同的编码方法，检错 或 纠错 能力也不同。,2023年1月22日,14,11.2 纠错编码的基本原理,1、分组码基本原理,分组码的一般结构：,分组码的符号：(n,k),n 码组的总位数，又称为码组的长度(码长);,k 码组中信息码元的数目;,n k r 码组中的监督码元数目，或称监督位数目。,2023年1月22日,15,11.2 纠错编码的基本原理,2、码重和码组,码重(w)：,码距(d)：,把码组中“1”的个数目，简称码重。,把两个码组中对应位上数字不同的位数，即两个码组对应位模2和的重量，称为码组的距离，简称码距。码距又称汉明距离。,码长(n)：,码组(码字)中的码元个数。,“0 1 1 0 1 1”的距离为 3,码重为 3,2023年1月22日,16,11.2 纠错编码的基本原理,2、码重和码组,码重(w)：,码距(d)：,最小码距(d0)：,把码组中“1”的个数目，简称码重。,把两个码组中对应位上数字不同的位数，即两个码组对应位模2和的重量，称为码组的距离，简称码距。码距又称汉明距离。,把某种编码中各个码组之间距离的最小值称为最小码距(d0)。若是线性码，d0就等于(非全零)码组的最小重量。一种编码的检错和纠错能力决定于最小码距d0。,码长(n)：,码组(码字)中的码元个数。,2023年1月22日,17,11.2 纠错编码的基本原理,3、最小码距与纠检错能力,(n,k)分组码，纠(检)错能力为：,(1)为检测e个错码，要求最小码距 d0 e+1,(2)为了纠正t个错码，要求最小码距d0 2t+1,(3)为纠正t个错码，同时检测e个错码，要求最小码距,2023年1月22日,18,11.2 纠错编码的基本原理,3、最小码距与纠检错能力,(n,k)分组码，纠(检)错能力为：,(1)为检测e个错码，要求最小码距 d0 e+1,(2)为了纠正t个错码，要求最小码距d0 2t+1,(3)为纠正t个错码，同时检测e个错码，要求最小码距,2023年1月22日,19,11.2 纠错编码的基本原理,4、编码效率和编码增益,编码效率简称码率：,冗余度：,编码增益：,监督码元数(n-k)和信息码元数k的比值，即(n-k)/k。,信息码元数k与编码组的总码元数(即码长)n的比值。,在保持误码率恒定条件下，采用纠错编码所节省的信噪比称为编码增益。,2023年1月22日,20,11.4 简单的实用编码,11.4.1 奇偶监督码,奇偶监督码是最简单的检错码，监督位只有1位，因此码率Rc=(n-1)/n很高。设编码组为，其中前n-1位为信息码，第n位为监督码a0。,这种编码能够检测奇数个错码。但对突发差错的漏检率接近于1/2。,监督关系式,校正子,2023年1月22日,21,11.4 简单的实用编码,11.4.1 奇偶监督码,奇偶监督码是最简单的检错码，监督位只有1位，因此码率Rc=(n-1)/n很高。设编码组为，其中前n-1位为信息码，第n位为监督码a0。,适用：检测随机出现的零星差错。,很高（因为只有一位监督位）。,码率：,2023年1月22日,22,11.4 简单的实用编码,11.4.2 二维奇偶监督码（方阵码）,先把上述奇偶监督码的若干码组排成矩阵，每一码组写成一行，然后再按列的方向增加第二维监督位。,纠检能力：有较强的检错能力，并有一定的纠错能力。,适用：适于检测长度不大于行数(或列数)的突发错误。,2023年1月22日,23,11.4 简单的实用编码,11.4.3 恒比码,检测方法：计算接收码组中“1”的数目，就可知是否有错。,适用：用于电报传输系统或其他键盘设备产生的字母和符号。,编码规则：,个许用码组，可分别用来代表26个英文字母 及 其他符号。,2023年1月22日,24,11.5 线性分组码,代数码：建立在代数学基础上的编码。,具有封闭性，即任意两个许用码组之和(逐位模2加)仍为一许用码组。它的最小码距等于非全零码组的最小重量。,线性码：按照一组线性方程构成的代数码。在线性码中信息位和监督位是由一些线性代数方程联系着的。,线性分组码：按照一组线性方程构成的分组码。,线性分组码的性质：,2023年1月22日,25,11.5 线性分组码,1、汉明码,若要构造具有纠错能力的（n，k）码，则需增加督元的数目。,当“=”成立时，构造的线性分组码 称为汉明码,汉明码是一种能够纠正1位错码，且编码效率较高的一种线性分组码。,其特点是d0=3(能够纠正一个错码或检两个错码)，码长n与监督位数rnk满足关系式n=2r-1。,2023年1月22日,26,11.5 线性分组码,1、汉明码,(7,4)汉明码,在(7,4)码中，n=7，k=4，rnk=3。设码组为a6 a5 a0，其中信息码元为a6 a5 a4 a3，监督码元为a2 a1 a0。用S1、S2和S3表示3个监督关系式中的校正子(又称校验子、伴随式)。若S=0就认为无错码；若S=1就认为有错码。,2023年1月22日,27,11.5 线性分组码,1、汉明码,(7,4)汉明码,仅当一位错码的位置在a2、a4、a5 或a6 时，校正子S1为1；否则S1为 0。,同理：,2023年1月22日,28,11.5 线性分组码,1、汉明码,(7,4)汉明码,(A),2023年1月22日,29,11.5 线性分组码,1、汉明码,(7,4)汉明码,(A),2023年1月22日,30,11.5 线性分组码,1、汉明码,(7,4)汉明码,接收端译码检错纠错过程,2023年1月22日,31,11.5 线性分组码,1、汉明码,一般来说，若码长为n，信息位数为k，则监督位数rnk。如果希望用r个监督位构造出r个监督关系式来指示1位错码的n种可能位置，则要求：,对于汉明码，上式取等号。这表明用来纠正单个错误时，汉明码所用的监督位最少。与码长相同的其他纠正单个错误的码相比，其码率最高。,表中所列的(7,4)汉明码的最小码距d0=3。因此，这种码能够纠正1个错码或检测2个错码。由于码率k/n=(n-r)/n=1 r/n，故当n很大和r很小时，码率接近1。可见，汉明码是一种高效码。,2023年1月22日,32,11.5 线性分组码,2、监督矩阵（H矩阵）,监督码元和信息码元之间的关系称为监督方程。,将它改写为：,可以表示成矩阵形式：,简记为：,HAT=0T 或 A HT=0,2023年1月22日,33,11.5 线性分组码,2、监督矩阵（H矩阵）,讨论：,(1)监督矩阵H是一个rn阶(r行n列)矩阵。,(2)任一发送码组A都满足式HAT=0T的关系。也就是说只要监督矩阵H给定，编码时监督位和信息位的关系就完全确定了。H的每行中的“1”的位置表示相应 码元之间存在的监督关系。例如，H的第一行1110100表示监督位a2是由a6 a5 a4 之和决定的。(n,k)码的H矩阵必须有r=n-k行，且各行必须是线性无关的。,2023年1月22日,34,11.5 线性分组码,2、监督矩阵（H矩阵）,讨论：,(3)H矩阵可以分成两部分：,(4)典型H矩阵的各行一定是线性无关的。非典型形式的监督矩阵可以经过初等行运算化为典型阵。,式中，P 为r k阶矩阵，Ir 为r r阶单位方阵。具有P Ir形式的H矩阵称为典型监督矩阵。由典型监督矩阵及信息码元很容易算出各监督码元。,2023年1月22日,35,11.5 线性分组码,3、生成矩阵（G矩阵）,汉明码例子中的监督位公式为：,也可以改写成矩阵形式：,或者写成：,式中，Q为一个k r阶矩阵，它为P的转置，即：,上式表示，在信息位给定后，用信息位的行矩阵乘矩阵Q就产生出监督位。,P 阵,Q 阵,Q=PT,2023年1月22日,36,11.5 线性分组码,3、生成矩阵（G矩阵）,将Q的左边加上1个k k阶 单位方阵，就构成1个矩阵G。,G称为生成矩阵，因为由它可以产生整个码组，即有：,或者,2023年1月22日,37,11.5 线性分组码,3、生成矩阵（G矩阵）,讨论：,(1)生成矩阵G是一个kn阶矩阵。,(2)具有Ik Q形式的生成矩阵称为典型生成矩阵，由它产生的分组码称为系统码。,(3)典型生成矩阵G和典型监督矩阵 H之间由Q=PT或P=QT相联系。即：若知H=P Ir，则由Q=PT，可得G=IkQ 若知G=Ik Q，则由P=QT，可得H=PIr,2023年1月22日,38,11.5 线性分组码,3、生成矩阵（G矩阵）,讨论：,(4)任一码组A都是G的各行的线性组合。G的各行本身就是一个许用码组。,(5)非典型形式的生成矩阵经过初等行运算也一定可以化为典型阵。,(6)注意：H矩阵、G矩阵的各行应该线性无关的。,2023年1月22日,39,11.5 线性分组码,4、校正子S与译码,错误图样,若ei=0，表示该接收码元无错；若ei=1，则表示该接收码元有错。,设发送码组A=a6 a5 a4 a3 a2 a1 a0，接收码组，则错误图样(收发码组之差)为：,B A=E(模2),式中,2023年1月22日,40,11.5 线性分组码,4、校正子S与译码,S 和 E 的关系,接收端计算校正子为：,可以改写成 B=A+E(模2),S=B H T=(A+E)H T=A H T+E H T=E H T,由于A HT=0，所以校正子S只E与有关，即S和错码E之间有确定的线性变换关系。,2023年1月22日,41,11.5 线性分组码,4、校正子S与译码,译码,对接收码组B计算校正子：S=B H T；,译码过程即纠错和检错的过程。其步骤如下：,若S=0(全0阵)，表示接收码组B无错；若S0，则由 S=E H T解得错误图样E；,由B=A+E(模2)可得到纠错后的码组为A=B+E。,2023年1月22日,42,11.6 循环码,循环码是(n,k)线性分组码的一个重要子类。其编解码设备简单，检(纠)错能力较强。有RS、BCH等高效子类码，实际应用广泛。,循环码除了具有线性分组码的一般性质外，还具有循环性。,2023年1月22日,43,11.6 循环码,循环性：是指任一码组循环一位(即将最右端的一个码元移至左端，或反之)以后，仍为该码中的一个码组。,表中的第 2 码组向 右移一位即得到第 5 码组；,(7,3)循环码,表中的第 6 码组向 右移一位即得到第 3码组。,2023年1月22日,44,11.6 循环码,1、码多项式,在代数编码理论中为了便于运算，常以多项式来表示码组。,码字（1100101）的多项式可表示为：,多项式的系数就是码组中的各码元，x 仅是码元位置标记。,n=7 时,一个长度为n的码组A=an-1 an-2 a0可以表示成多项式形式：,2023年1月22日,45,11.6 循环码,1、码多项式,码多项式的按模运算,若一个整数m 可以表示为,（Q 为整数）,m p(模n),则在模n 运算下，有,2023年1月22日,46,11.6 循环码,1、码多项式,码多项式的按模运算,或,则,式中，码多项式系数之间的加法和乘法仍按模2 运算。,2023年1月22日,47,11.6 循环码,1、码多项式,码多项式的按模运算,解 运算过程：,即有,则有,2023年1月22日,48,11.6 循环码,在循环码中，若A(x)是一个长为n的许用码组，则xiA(x)在按模xn+1运算下，也是该编码中的一个许用码组，即若：,则A(x)也是该编码中的一个许用码组。,1、码多项式,2023年1月22日,49,11.6 循环码,2、生成多项式g(x),1)存在性,在一个(n,k)循环码中，有一个且仅有一个次数为(n k)的多项式：,这唯一的(n k)次多项式g(x)为码的生成多项式。g(x)表示该循环码的前(k-1)位皆为“0”的码组。,2023年1月22日,50,11.6 循环码,(2)所有码多项式A(x)都可被g(x)整除，而且任意一个次数不大于(k-1)的多项式乘g(x)都是码多项式。该条性质可用于编码，还可用于验证接收码组是否出错。,2、生成多项式g(x),2)性质,(1)g(x)是一个：常数项为1；最高次数为(n-k)次；是xn+1的一个因式。该条性质给我们提供了一种对于给定的(n,k)循环码，寻找或确定其生成多项式的方法。,2023年1月22日,51,11.6 循环码,3、生成矩阵G,在循环码中，一个(n,k)码有2k个不同的码组。若用g(x)表示其中前(k-1)位皆为“0”的码组，则g(x)，xg(x)，x2g(x)，xk-1g(x)都是码组，而且这k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵G。,由于此式不符合G=IkQ的形式，所以它不是典型阵。将其作线性变换，可化成典型阵。,一旦确定g(x)，整个(n,k)循环码就被确定了。,g(x)是循环码的核心。对于给定的k位信息码，由g(x)构造出G(x)，从而产生(n,k)循环码。,2023年1月22日,52,11.6 循环码,4、循环码的编码,方法一：对于给定的信息码m(x)，相应的码多项式A(x)=m(x)g(x)，它是非系统码。,方法二：m(x)与G(x)相乘。此法得到的是非系统码；若先将生成矩阵G(x)化为典型阵，则可得到系统码。,2023年1月22日,53,11.6 循环码,4、循环码的编码,方法三：A(x)=xn-km(x)+r(x)，属系统码。编码步骤如下：,(1)用xn-k乘m(x)。这一运算实际上是在信息码后附加上(n k)个“0”。,(2)用g(x)除xn-k m(x)，得到商Q(x)和余式r(x)，即：,(3)编出的码组T(x)为：A(x)=xn-k m(x)+r(x),由以上编码步骤可见，编码的核心是如何确定余式r(x)，找到后r(x)，可直接将所代表的编码位附加到信息位之后，完成编码。,2023年1月22日,54,11.6 循环码,5、循环码的译码,解码要求：检错和纠错。,(1)检错,接收码组与发送码组相同，即B(x)=A(x)，故接收码组B(x)必定能被g(x)整除；若码组在传输中发生错误，则B(x)A(x)，B(x)被g(x)除时可能除不尽而有余项。因此，就以余项是否为零来判别接收码组中有无错码。,2023年1月22日,55,11.6 循环码,5、循环码的译码,解码要求：检错和纠错。,(2)纠错,纠错可按下述步骤进行：,用生成多项式g(x)除接收码组B(x)，得出余式s(x)。,按余式s(x)，用查表的方法或通过某种计算得到错误图样E(x)；例如，通过计算校正子S和查表，就可以确定错码的位置。,从B(x)中减去E(x)，便得到已经纠正错码的原发送码组A(x)。,2023年1月22日,56,11.6 循环码,5、循环码的译码,上述编、解码运算，都可以用硬件电路(如除法电路)事项。由于数字信号处理器的应用日益广泛，目前多采用软件运算实现上述编解码运算。,2023年1月22日,57,11.11 小结,11.1 概述11.2 纠错编码的基本原理 分组码基本原理 码重和码距 最小码距与纠检错能力 编码效率和编码增益11.4 简单的实用编码 奇偶监督码 二维奇偶监督码（方阵码）恒比码11.5 线性分组码 汉明码 监督矩阵（H矩阵）生成矩阵（G矩阵）校正子S与译码11.6 循环码 码多项式 生成多项式g(x)生成矩阵G 循环码的编码 循环码的译码,2023年1月22日,58,11.11 小结,本章知识点:1、了解差错控制技术种类 2、掌握纠错编码原理、最小码距和检错、纠错之间关系；了解奇偶监督码、恒比码编码方法。3、掌握线性分组码编码和译码方法 4、掌握循环码编码和译码方法,作业：376-377页 11-3、11-6、11-8、11-13,