《差错控制编码电信课件》由会员分享，可在线阅读，更多相关《差错控制编码电信课件（58页珍藏版）》请在金锄头文库上搜索。
1、,第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章 差错控制编码,2019年4月20日,3,为保证运送途中不出现打碎灯泡的情况,有效性,可靠性,11.1 概述,2019年4月
2、20日,4,通信中的情况：,针对乘性干扰,针对加性干扰,合理选择调制/解调方法，增大发射功率, 采用均衡等措施,11.1 概述,2019年4月20日,5,11.1 概述,差错控制编码,2019年4月20日,6,11.1 概述,信道分类(从差错控制角度看)：,随机信道：错码的出现是随机的。,突发信道：错码是成串集中出现的。,混合信道：既存在随机错码又存在突发错码。,差错控制技术的种类：,检错重发,前向纠错,反馈校验,检错删除,信道编码分类：,线性码和非线性码,分组码和卷积码,系统码和非系统码,2019年4月20日,7,11.1 概述,不同的编码方法，有不同的检错或纠错能力。,多余度：就是指增加的
3、监督码元多少。例如，若编码序列中平均每两个信息码元就添加一个监督码元，则这种编码的多余度为1/3。,编码效率(简称码率) ：设编码序列中信息码元数量为k，总码元数量为n，则比值k/n 就是码率。,冗余度：监督码元数(n-k) 和信息码元数 k 之比。,理论上，差错控制以降低信息传输速率为代价换取提高传输可靠性。, 监督码元：在4种差错控制技术中除第3种外，都是在接收端识别有无错码。所以在发送端需要在信息码元序列中增加一些差错控制码元，它们称为监督码元。,2019年4月20日,8,11.2 纠错编码的基本原理,1、分组码基本原理,将信息码分组，为每组信息码附加若干监督码的编码称为分组码 。在分组
4、码中，监督码元仅监督本码组中的信息码元。,卷积码又称连环码。卷积码编码器把k比特信息段编成n比特的码组，但所编的n长码组不仅同当前的k比特信息段有关，而且还同前面的(N-1)个(N1,整数)信息段有关联。,2019年4月20日,9,11.2 纠错编码的基本原理,1、分组码基本原理,规则：使码组中 “1”的个数为偶数,情形1：没有冗余 不能发现错误,情形2：加入冗余 可以发现错误,冗余, 另外4个码组,2019年4月20日,10,11.2 纠错编码的基本原理,1、分组码基本原理,规则：使码组中 “1”的个数为偶数,情形1：没有冗余 不能发现错误,情形2：加入冗余 可以发现错误,冗余, 另外4个码
5、组,只能检出一个码组中1个和3个(奇数)错码的情况，不能发现2个(偶数)错码的情况，也不能纠正错误。,2019年4月20日,11,11.2 纠错编码的基本原理,1、分组码基本原理,情形1：没有冗余 不能发现错误,情形2：加入冗余 可以发现错误,2019年4月20日,12,11.2 纠错编码的基本原理,1、分组码基本原理,这时，能够发现 2个以下错码，或者纠正 1位 错码 。,2019年4月20日,13,11.2 纠错编码的基本原理,1、分组码基本原理,综上所述,不同的编码方法，检错 或 纠错 能力也不同 。,2019年4月20日,14,11.2 纠错编码的基本原理,1、分组码基本原理,分组码的
6、一般结构：,分组码的符号：(n, k),n 码组的总位数，又称为码组的长度(码长);,k 码组中信息码元的数目;,n k r 码组中的监督码元数目，或称监督位数目。,2019年4月20日,15,11.2 纠错编码的基本原理,2、码重和码组,码重(w)：,码距(d)：,把码组中“1”的个数目，简称码重。,把两个码组中对应位上数字不同的位数，即两个码组对应位模2和的重量，称为码组的距离，简称码距。码距又称汉明距离。,码长(n)：,码组(码字)中的码元个数。,“ 0 1 1 0 1 1” 的距离为 3,码重为 3,2019年4月20日,16,11.2 纠错编码的基本原理,2、码重和码组,码重(w)：
7、,码距(d)：,最小码距(d0) ：,把码组中“1”的个数目，简称码重。,把两个码组中对应位上数字不同的位数，即两个码组对应位模2和的重量，称为码组的距离，简称码距。码距又称汉明距离。,把某种编码中各个码组之间距离的最小值称为最小码距(d0)。若是线性码， d0就等于(非全零)码组的最小重量。一种编码的检错和纠错能力决定于最小码距d0 。,码长(n)：,码组(码字)中的码元个数。,2019年4月20日,17,11.2 纠错编码的基本原理,3、最小码距与纠检错能力,(n,k)分组码，纠(检)错能力为：,(1)为检测e个错码，要求最小码距 d0 e + 1,(2)为了纠正t个错码，要求最小码距d0
8、 2t + 1,(3)为纠正t个错码，同时检测e个错码，要求最小码距,2019年4月20日,18,11.2 纠错编码的基本原理,3、最小码距与纠检错能力,(n,k)分组码，纠(检)错能力为：,(1)为检测e个错码，要求最小码距 d0 e + 1,(2)为了纠正t个错码，要求最小码距d0 2t + 1,(3)为纠正t个错码，同时检测e个错码，要求最小码距,2019年4月20日,19,11.2 纠错编码的基本原理,4、编码效率和编码增益,编码效率简称码率：,冗余度：,编码增益：,监督码元数(n-k)和信息码元数k的比值，即(n-k)/k。,信息码元数k与编码组的总码元数(即码长)n的比值。,在保持
9、误码率恒定条件下，采用纠错编码所节省的信噪比称为编码增益。,2019年4月20日,20,11.4 简单的实用编码,11.4.1 奇偶监督码,奇偶监督码是最简单的检错码，监督位只有1位，因此码率Rc=(n-1)/n很高。设编码组为 ，其中前n-1位为信息码，第n位为监督码a0。,这种编码能够检测奇数个错码。但对突发差错的漏检率接近于1/2。,监督关系式,校正子,2019年4月20日,21,11.4 简单的实用编码,11.4.1 奇偶监督码,奇偶监督码是最简单的检错码，监督位只有1位，因此码率Rc=(n-1)/n很高。设编码组为 ，其中前n-1位为信息码，第n位为监督码a0。,适用： 检测随机出现
10、的零星差错。,很高 （因为只有一位监督位）。,码率：,2019年4月20日,22,11.4 简单的实用编码,11.4.2 二维奇偶监督码（方阵码）,先把上述奇偶监督码的若干码组排成矩阵，每一码组写成一行，然后再按列的方向增加第二维监督位。, 纠检能力：有较强的检错能力，并有一定的纠错能力。, 适用：适于检测长度不大于行数(或列数)的突发错误。,2019年4月20日,23,11.4 简单的实用编码,11.4.3 恒比码, 检测方法：计算接收码组中“1”的数目，就可知是否有错。, 适用：用于电报传输系统或其他键盘设备产生的字母和符号。, 编码规则：,个许用码组，可分别用来代表26个英文字母 及 其
11、他符号。,2019年4月20日,24,11.5 线性分组码,代数码：建立在代数学基础上的编码。, 具有封闭性，即任意两个许用码组之和(逐位模2加)仍为一许用码组。 它的最小码距等于非全零码组的最小重量。,线性码：按照一组线性方程构成的代数码。在线性码中信息位和监督位是由一些线性代数方程联系着的。,线性分组码：按照一组线性方程构成的分组码 。,线性分组码的性质：,2019年4月20日,25,11.5 线性分组码,1、汉明码,若要构造具有纠错能力的（n，k）码，则需增加督元的数目。,当“ = ”成立时，构造的线性分组码 称为汉明码,汉明码是一种能够纠正1位错码，且编码效率较高的一种线性分组码。,其
12、特点是d0=3(能够纠正一个错码或检两个错码)，码长n与监督位数rnk满足关系式n=2r-1。,2019年4月20日,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就认为有错码。,2019年4月20日,27,11.5 线性分组码,1、汉明码,(7, 4)汉明码,仅当一位错码的位置在a2 、a4、a5 或a6 时， 校正子S1为1；否则S1
13、为 0。,同理：,2019年4月20日,28,11.5 线性分组码,1、汉明码,(7, 4)汉明码,(A),2019年4月20日,29,11.5 线性分组码,1、汉明码,(7, 4)汉明码,(A),2019年4月20日,30,11.5 线性分组码,1、汉明码,(7, 4)汉明码,接收端译码检错纠错过程,2019年4月20日,31,11.5 线性分组码,1、汉明码,一般来说，若码长为n，信息位数为k，则监督位数rnk。如果希望用r个监督位构造出r个监督关系式来指示1位错码的n种可能位置，则要求：,对于汉明码，上式取等号。这表明用来纠正单个错误时，汉明码所用的监督位最少。与码长相同的其他纠正单个错
14、误的码相比，其码率最高。,表中所列的(7, 4)汉明码的最小码距d0 = 3。因此，这种码能够纠正1个错码或检测2个错码。由于码率k/n =(n - r)/n=1 r/n，故当n很大和r很小时，码率接近1。可见，汉明码是一种高效码。,2019年4月20日,32,11.5 线性分组码,2、监督矩阵（ H矩阵）,监督码元和信息码元之间的关系称为监督方程。,将它改写为：,可以表示成矩阵形式：,简记为：,HAT = 0T 或 A HT = 0,2019年4月20日,33,11.5 线性分组码,2、监督矩阵（ H矩阵）,讨论：,(1) 监督矩阵H是一个rn阶(r行n列)矩阵。,(2) 任一发送码组A都满
15、足式HAT = 0T的关系。 也就是说只要监督矩阵H给定，编码时监督位和信息位的关系就完全确定了。 H的每行中的“1”的位置表示相应 码元之间存在的监督关系。例如， H的第一行1110100表示监督位a2是由a6 a5 a4 之和决定的。 (n,k)码的H矩阵必须有r=n-k行，且各行必须是线性无关的。,2019年4月20日,34,11.5 线性分组码,2、监督矩阵（ H矩阵）,讨论：,(3) H矩阵可以分成两部分：,(4)典型H矩阵的各行一定是线性无关的。非典型形式的监督矩阵可以经过初等行运算化为典型阵。,式中，P 为r k阶矩阵，Ir 为r r阶单位方阵。具有P Ir形式的H矩阵称为典型监
16、督矩阵。由典型监督矩阵及信息码元很容易算出各监督码元。,2019年4月20日,35,11.5 线性分组码,3、生成矩阵（ G矩阵）,汉明码例子中的监督位公式为：,也可以改写成矩阵形式：,或者写成：,式中，Q为一个k r阶矩阵，它为P的转置，即：,上式表示，在信息位给定后，用信息位的行矩阵乘矩阵Q就产生出监督位。,P 阵,Q 阵,Q = PT,2019年4月20日,36,11.5 线性分组码,3、生成矩阵（ G矩阵）,将Q的左边加上1个k k阶 单位方阵，就构成1个矩阵G。,G称为生成矩阵，因为由它可以产生整个码组，即有 ：,或者,2019年4月20日,37,11.5 线性分组码,3、生成矩阵（ G矩阵）,讨论：,(1) 生成矩阵G是一个kn阶矩阵。,(2)具有Ik Q形式的生成矩阵称为典型生成矩阵，由它产生的分组码称为系统码。,(3)
