信息论与编码 教学课件 ppt 作者 张莲 周登义 余成波 5

《信息论与编码 教学课件 ppt 作者 张莲 周登义 余成波 5》由会员分享，可在线阅读，更多相关《信息论与编码 教学课件 ppt 作者 张莲 周登义 余成波 5（63页珍藏版）》请在金锄头文库上搜索。

1、第五章 无失真信源编码,主要内容,一、信源编码与信道编码 二、信源编码的分类 三、无失真信源编码 四、等长码及等长编码定理 五、变长码及变长编码定理 六、变长编码的方法,一、信源编码与信道编码,1、通过前面几章的学习，我们应该知道： 各种通信系统，尽管它们的形式和用途各不相同，但都可以归结为第一章的一般模型。其中信源、信宿和信道是事先给定的，信源是产生消息的源泉，信宿用于接收信息，而信道则用于传输信息。 为了实现高质量、高效率的通信，引入了信源编码的信道编码，这些都是由人来设计完成的，通信质量的优劣，很大程度上取决于编码、译码过程设计的优劣。,2、信源编码和信道编码各自解决的问题： （1）提高

2、传输率： 一般用尽可能少的信道传输符号来传递信源消息，目的是提高传输率，这是信源编码主要解决的问题。这就是本章第一小节要讨论的内容。 （2）增强通信的可靠性： 信号在信道的传播过程中总不可避免地受到各种干扰，在这种情况下，如何增加信号的抗干扰能力，提高传输的可靠性，是信道编码主要考虑的问题。解决这一问题，一般采用冗余编码法，即按照一定的编码规则事先给信码加上一定的冗余度（检测位），赋予信码自身一定的纠错和检错能力，只要采取适当的信道编码和译码措施，就可使信道传输的错误概率降到允许的范围之内，这是后面第六章信道编码中要讨论的问题。,综上所述，提高抗干扰能力往往是以降低信息传输率为代价的，而为了提

3、高传输率又往往削弱了其抗干扰能力。这样，设计者在取舍之间就要进行均衡考虑，当然，香龙已经在理论上证明，至少存在某种最佳编码方法，可以有效地解决上述矛盾。,二、信源编码的分类,信源编码可分两种情况讨论，即允许接收信号有一定的失真或不允许失真。 无失真信源编码 此方法不考虑信道的干扰，仅考虑的是将信源输出的全部信息在接收端精确地重现出来，它只是对信源的冗余度进行压缩，并不改变信源的熵。 （1）此时，将信道编码和译码看成是信道的一个部分。是本章讨论的主要内容。 （2）适用范围：主要针对离散信源。而连续信源在量化编码的过程中必然会有量化失真，所以，对连续信源只能近似地再现信源的消息。,限失真信源编码

4、在许多实际情况中，信宿并不要求完全精确地复现信源输出的原信号，例如，在电话通信系统中，只要将通话内容送达对方就可以了，对音质并没有太高的要求。在这种情况下，允许接收信号有一定的失真，为提高传输率，我们可以事先对信源进行压缩编码，能压缩到什么程度由允许失真的程度来确定。这是本章第2小节至第8小节需要讨论的问题。 适用范围：主要针对连续信源； 共同点：均以提高信息率为主要最终目的。,三、无失真信源编码（5.1节）,主要内容： 一般用尽可能少的符号来传输信源消息，以便提高传输效率，这是信源编码应考虑的问题，本小节讨论在不允许失真的情况下的信源编码。等长编码定理给出了等长编码条件下，其码长的下限值，变

5、长编码定理（香龙第一定理）给出了信源无失真变长编码时其码长的上、下限值。本章还介绍了三种通用信源编码方法、费诺编码法和霍夫曼编码法。 知识要点： 信息传输率、克拉夫特不等式、等长编码定理、变长编码定理、编码效率、无失真编码方法。,信源编码的定义和两个功能： 实际上是对信源的原始符号按一定的数学规则进行变换的一种代码。 信源编码的两个功能（或目的）： （1）将信源符号变换成适合信道传输的符号； （2）压缩信源冗余度，提高传输率；,1、信源编码的相关概念： 1）编码： 对信源输出的原始符号按照一定的数学规则进行的一种 变换。 2）编码器： 完成编码功能的具体器件。 3）译码器： 在接收端完成与编码

6、器相反功能的具体器件。 4）码序列： 将信源输出的符号序列（或称消息），变换成适合信道传 输的符号序列，称为码序列。,2、无失真信源编码器的数学模型：,两个输入： （1）信源符号集 S = s1 , s2 , ,sq ,共有q个信源符号。 （2）码符号集（或称基本符号集）= x1 ,x2 , ,xr ，共有r个符号组成。该集中的元素称为码元或码符号。 一个输出： 码字集合（或称代码组） C = W1, W2, ,Wq 。,编码器完成的任务： 将信源符号集S中的符号 Si ，i=1，2， ， q 变换成由Li个码符号组成的一一对应的码符号序列，即码字，并用Wi,i=1,2, ,q来表示。 码字与

7、信源符号Si之间是一一对应的关系，如图5.1.1所示 码长： 信源符号 Si 对应的码字 Wi 包含 Li 个码符号，称为码长。 总之，信源编码就是把信源符号序列变换到码符号序列的一种映射。若要实现无失真编码，那么这种映射必须是一一对应、可逆的。一般所来，人们总是希望把信源所有的信息毫无保留地传递到接收端，即实现无失传递，所以首先要对信源实现无失真编码。,3、举例说明用编码器实现对信源符号的编码 天气预报：信源有4个消息 晴、阴、雨、雪 待发. 方法一： 如果码符号集为 1 , 2 , 3 , 4 ，此时，因为消息个数与码符号集个数相等，可以用单符号来表示这4个消息。 方法二： 如果码符号集为

8、 0，1 ，则可将这4个消息变换成4个二位的二进制代码： 晴:00 阴:01 雨:10 雪:11 00,01,10,11 就是分别代表 晴、阴、雨、雪 这4个消息的码字，码长为2。 在此例中， 晴、阴、雨、雪 是信源消息，码符号集仅含 0，1 两个数字， 00,01,10,11 是信源编码器的输出符号，即信道的输入符号，相应得到的码字。,4、码的分类： 1）二元码 若码符号集为 0，1 ，所编出码字就是二元序列，称为 二元码，二元码通过二进制信道传输，这是数字通信和计算机 通信中最常见的一种码，表5-1中列出的4种码都是二元码。 2）等长码 在一组码字集合 C 中的所有码字 Wi ，其码长都相

9、同，则 称这组码为等长码表5-1中的码1、码2是码长等于2的等长码； 3）变长码 若码字集合 C 中的所有码字 Wi ，其码长不都相同，则称 这组码为变长码表5-1中的码3、码4；,4）奇异码 指从信源消息到码字的映射不是一一对应，即在一组码 中，存在着不同的信源消息用同一码字来表示的情况。如表5- 1中的码1；奇异码不具备唯一可译性。 5）非奇异码 指从信源消息到码字的映射是一一对应的，每一个的信源 消息都用不同的码字对其编码，如表5-1中的码2、码3、码4 .,6）原码 C 的 N 次扩展码 原码C的N次扩展码中，其每一个元素是N次扩展信源中的序 列所对应的N个码字组成的序列。,唯一可译码

10、（单义码）,如果一个信源符号的原编码是非奇异码，而且它的任意N 次扩展码也是非奇异码，则称该码为唯一可译码。 结论： 1）对于定长码，若原码是唯一可译码，则它的N次扩展编码也是唯一可译码； 2）而对于变长码则不尽然。见表5-2,（表 5-2）同一信源的几种不同变长码,即时码与延长码 同是唯一可译码，其译码方法仍有所不同。 对于唯一可译的变长码而言，若码组中的任一码字都不 是另一码字的字头（前缀），称该码是即时码。 例如：表5-2中， 对于码3，收到“1”后就知道一个码字已经完结，马上就能 判断出是什么码字，无需等待下一个符号抵达，所以称之为 即时可译玛，简称即时码。 而对于码2，收到“1”后，

11、并不能立即做出判决，就是收到 “10”也不能立即做出判决，因为若下一次收到“1”，则可判决 前面发出的是S2 ，若下一个是“0” ，则还要再收到下面的码 元才能做出最后的判决。,由以上分析可知： 1）即时码是唯一可译码，而唯一可译码不一定是即时码。 2）即时码是一种实时的唯一可译码。在信源编码和数据压缩中这类编码无论在理论还是在实际上都有很大意义。 即时码的树图构造法 1）最上端为树根 A ，从树根出发向下伸出树枝，树枝的总数等于 r ,树枝的尽头称为节点。 2）从每个节点再伸出 r 枝树枝，当某节点被安排为码子以后，就不能再伸枝，这个节点称为终端节点。一直继续进行，直到都不能伸枝为止。 3）

12、每个节点所伸出的树枝上标上码符号，从树根出发到终端节点所走过的路径所对应的码符号序列则为该终端节点的码字。,举例： 利用树图法构成一个即时码 例1： 用二进制树图来构成一个即时码 w = w1, w2 , w3, w4 ，要求其码长分别为：1，2，3，3。 1）从树根开始，画出两条分枝，选中一节点代表 w1. 2）从没有被选用的节点，再画出两条分枝。又选中一节点代表 w2。 3）继续下去，直到四个码字都有节点来代表为止。 4）将由树根到某一个码字wi经过的枝（码符号），依次写出来，即得到该码字。,例2： 用树图法表示下表中的码字：,数根,0,1,0,1,1,1,1,s1,0,0,0,s5,s3

13、,s6,s4,s2,唯一可译码存在的充要条件,1）对含有q个信源符号的信源，用r个符号的码符号集进行编码，各码字的码长为 L1 , L2 , , Lq 的唯一可译码存在的充要条件是满足Kraft不等式：,2）若存在一组码长为 L1 , L2 , , Lq 的唯一可译码，则一定存在具有相同码长的即时码。,注意： Kraft不等式只涉及唯一可译码的存在问题而并不涉及具体的码的构造问题。因此，它可用来判定某一组码不是唯一可译码，但不能判定是唯一可译码。也就是说，不满足Kraft不等式的码肯定不是唯一可译码，而满足的也不一定就是唯一可译码。,唯一可译码存在的判断方法,判断步骤： 一、首先，观察是否是非

14、奇异码。若是奇异码则一定不是唯一 可译码。 二、其次，计算是否满足Kraft 不等式。若不满足一定不是唯 一可译码。,码的分类结构图,码,奇异码,非奇异码,唯一可译码,非唯一可译码,变长码,等长码,即时码,延长码,作业与练习 5-1：有一信源，它有四个可能的输出，其概率分布如下表所示，表中给出了对应五种码。 （1）问这些码中，哪些是唯一可译码。 （2）问在变长码中，哪些又是即时码。,平均码长： 1、对于变长码，码字集合 C 的平均码长，等于其每个码字码长的概率加权平均值。 计算公式为：,式中， 是码字 所对应的码字长度； 是码字 出现的概率。 2、对于等长码，码字集合 C 的每个码字的码长都相

15、同，平均码长就等于每个码字的码长。,例：试计算下表中四组码的平均码长。,码3的平均码长为 码4的平均码长为,四、等长码和等长编码定理,1、基本概念： 1）不论设计者所编出的码是等长或变长码，一般来说，若想要实现无失真，都应该是唯一可译的，否则会因译码带来错误与失真。 2）对与定长码来说，若该定长码是非奇异码，则它的任意有限长N次扩展码一定也是非奇异码，因此，定长非奇异码一定是唯一可译码。 2、本节重点讨论三个方面的问题： 1）已知一个信源，对其进行定长编码时，获得唯一可译码的条件。（信源符号数、编码长以及信源熵之间的关系） 2）定长编码定理：讨论定长编码所需码长的理论极限值。 3）讨论定长编码

16、的效率、实现的难易程度。,3、唯一可译定长码获得的条件：,1）如某个信源S（假定有q个符号），要对其进行等长编码，那么，该信源S存在唯一可译定长码的条件是： 如左表所示： 当r = 2时 ,该编码可称为二元等 长编码。,2）同理，如果对信源S的N次扩展信源进行等长编码，那么该信源SN存在唯一可译定长码的条件是： 将上式两边去对数后，可得： 那么，就有： ：表示在信源SN 中，平均每个信源符号所需要多少个 码符号来表示。,特别地，当 r = 2 时， ，表示对于二元定长唯一可译码，平均每个原始信源符号至少需要 个二元码符号来表示。 当 N = 1 时，则有：,4、唯一可译定长码的传输效率问题： 1）效率较低 例如： 英文电报有32个符号（其中26个英文字母加6个标点符 号）。若对其进行定长二元编码，则 L = log32 = 5 ，也就 是说，每个英文电报符号至少要用5位码才能得到唯一可译码。 从前面已知