信息论与编码第2

《信息论与编码第2》由会员分享，可在线阅读，更多相关《信息论与编码第2（126页珍藏版）》请在金锄头文库上搜索。

1、第2章无失真信源编码原理 第2章无失真信源编码原理 2.1离散信源及其信息测度离散信源及其信息测度 2.2信源编码的基本概念信源编码的基本概念 2.3惟一可译码惟一可译码 2.4信源变长编码信源变长编码 2.5统计匹配码统计匹配码 轻珠临组愚肖肇赦舀救睹铃孟橇慌奈想醋咏珍徊蕉淳矫准展杏碌苟葫稗畔信息论与编码第2信息论与编码第2第2章无失真信源编码原理 2.12.1离散信源及其信息测度离散信源及其信息测度 2.1.12.1.1信源概述信源概述 1 1消息、信号和信息消息、信号和信息信源的输出被称做消息(message)，消息一般不能被直接传输，需要经过发送器的变换才能转换成适于信道传输的信号(s

2、ignal)。消息和信号的这种区别对信息传输系统来讲是有一定意义的。 道汞忙阎盾谍暗炔洞君鹿烁紧捷饼誊绅酬膊峪媚幢劳罚醛响徽斌漱胸瘫虐信息论与编码第2信息论与编码第2第2章无失真信源编码原理 在一般情况下，消息和信号既是相互区别的，又是相互联系的。一方面，消息和信号的定义与含义不同。当信源的输出连同语义学上的意义一并加以理解时则称为消息。例如，播音员播送的一段新闻，记者拍摄的一段录像，歌手演唱的一首歌曲等，都应该说是消息。而当信源的输出只被看做是随时间变化的某一物理量f（t）或随时间、空间位置变化的某一物理量f（x，y，t）时，则称为信号。另一方面，信源的输出在收到、看到、听到之前都是随机的、

3、不确定的，属于随机现象。因此，从信息论的观点来看，信源的输出无论是被看做消息，还是被看做信号，它均含有信息。 障奖达袋既抹断疡司兵孵僵械揣窘附样滚担躁组皿阐贪尔忧第证斗决胎娶信息论与编码第2信息论与编码第2第2章无失真信源编码原理 消息、信号和信息这三者都可以说是信源的输出，或者说它们是信源输出的三个方面。由于信息论关心的是信源输出的信息，因此可将信源称为信息源。通常，统计信息论是不研究消息、信号和信息三个方面在语义学上的意义的，它只考虑信源输出的后两个方面，即信号和信息。应该说，信号是信息的载体和具体表达形式，信息必须借助信号才能得以表现，信息不能离开信号而单独存在。所以，研究信源就是要研究

4、信号和信息的关系，特别是信号如何才能有效地携带信息。 复勾锅踢栏帜捞别铭云漓抖执昔漱谗竿署绦远苟尊守赦敢黎党绕保工凤叭信息论与编码第2信息论与编码第2第2章无失真信源编码原理 2 2信源的分类信源的分类按信号取值的集合和信号取值时刻的集合是离散的或连续的进行分类，信源可分为数字信源(DigitalSource)或离散信源(DiscreteSource)、模拟信源(AnalogSource)或波形信源(WaveformSource)、连续信源(ContinuousSource)。 筏儿铣叠编恫泄颇钎爽墙息液镶后睬缸僳菱浴咳屯比请硫颅掉阳函惨渴童信息论与编码第2信息论与编码第2第2章无失真信源编码

5、原理 信源输出的信息从数学角度来看就是一种随机过程。有些信源输出的是单个符号(或代码)的消息，它们符号集的取值是有限的或可数的，即可用一维离散型随机变量来描述这些信源的输出，这样的信源称为离散信源。在实际情况中，存在着很多这样的信源。例如投硬币、书信文字、计算机的代码、电报符号、阿拉伯数字码等等。当我们掷一个六面质地均匀的骰子时，每次出现朝上一面的点数都是随机的，如把出现朝上一面的点数作为这个随机试验的结果，并把试验的结果看做信源的输出消息，无可置疑，这个随机试验可看做是一个信源。这个信源输出有限种离散数字，其组成的集合为A=1，2，3，4，5，6，而且每一个数字代表一个完整的消息，辱锥弃蒸滇

6、瘫平炙刷蛊厉壕晚净扰塞酥鸦谅瓜灾资掇贱粉涯房豌眠苗沁虹信息论与编码第2信息论与编码第2第2章无失真信源编码原理 所以，这个信源是单符号离散信源。有的信源输出的虽是单个符号(或代码)的消息，但其可能出现的消息数是不可数的或无限的，即输出消息的符号集的取值是连续的，或取值范围是实数集(-，+)。例如，语音信号、热噪声信号等某时间的连续取值数据，以及遥控系统中有关电压、温度、压力等测得的连续数据。这些数据取值虽是连续的，但又是随机的，可用一维的连续型随机变量来描述这些消息，所以这种信源可称为连续信源。 茶谩骡翱乡吗侦旦们场哦蚊旬祥彝愿挤壳方梦纫撬阴吴那翰乒革撰肪苑戮信息论与编码第2信息论与编码第2第

7、2章无失真信源编码原理 若信源只输出一个消息(符号)，则用一维随机变量来描述。然而，很多实际信源输出的消息往往是由一系列符号序列所组成的。例如，将中文自然语言文字作为信源，这时中文信源的样本空间是所有汉字与标点符号的集合。由这些汉字和标点符号组成的序列即构成中文句子和文章。因此，从时间上看，中文信源输出的消息是时间上离散的符号序列，其中每个符号的出现是不确定的、随机的，由此构成了不同的中文消息。又例如，对离散化的平面灰度图像信源来说，从XY平面空间上来看每幅画面是一系列空间离散的灰度值符号，而空间每一点的符号（灰度值）又都是随机的，由此形成了不同的图像消息。 训赔梨圆在馈煽镍京核镐衰罢捆挡坡不

8、溶鲸魂莽胡掖高雀疹住超盼蜀金插信息论与编码第2信息论与编码第2第2章无失真信源编码原理 这类信源输出的消息是按一定概率选取的符号序列,所以可以把这种信源输出的消息看做时间上或空间上离散的一系列随机变量，即随机矢量。这样，信源的输出可用N维随机矢量来描述，这N维随机矢量有时也称为随机序列，其中，N可为有限正整数或可数的无限值。若在信源输出的随机序列XX1X2XN中，每个随机变量Xi(i=1,2,N)都是取值离散的离散型随机变量，即每个随机变量Xi的可能取值是有限的或可数的,而且随机变量X的各维概率分布都与时间起点无关，也就是在任意两个不同时刻，随机变量的各维概率分布都相同，这样的信源称为离散平稳

9、信源。前面所述的中文自然语言文字与离散化平面灰度图像都是这种离散型平稳信源。 饱章腆羌型之铃讽剧麦圭晶吠打郎罗霸造吼斟兽把丙熟获米坎媒梭斗香幽信息论与编码第2信息论与编码第2第2章无失真信源编码原理 若信源输出的消息可用N维随机序列XX1X2XN来描述，其中每个随机分量Xi(i=1,2,N)都是取值为连续的连续型随机变量(即Xi的可能取值是不可数或无限的)，并且满足随机变量X的各维概率密度函数与时间起点无关，也就是在任意两个不同时刻随机变量X的各维概率密度函数都相同，这样的信源称为连续平稳信源。例如，语音信号与热噪声信号，它们在时间上取样离散化后的信源输出矢量在时间上是离散的，但输出矢量中的随

10、机变量的取值都是连续的，所以它们是连续型平稳信源。 苯钓雅菩箱肛宛暗薪普镇猴糙蹬算蛀宪面验瞩箕线尊祁淫镣稻怜奔训罕雪信息论与编码第2信息论与编码第2第2章无失真信源编码原理 某些简单的离散平稳信源先后发出的一个个符号是统计独立的。也就是说，在信源输出的随机序列XX1X2XN中，各随机变量Xi(i=1,2,N)之间是无依赖的、统计独立的，这样的信源称为离散无记忆信源。该信源在不同时刻发出的各符号之间也是无依赖的、统计独立的。离散无记忆信源输出的随机变量X所描述的信源称为离散无记忆信源的N次扩展信源。可见，N次扩展信源是由离散无记忆信源输出N长的随机序列构成的信源。一般情况下，信源在不同时刻发出的

11、各符号之间是相互依赖的，也就是在信源输出的平稳随机序列XX1X2XN中,各随机变量Xi之间是相互依赖的。 畏蝎净郡竭葫池冶奔腻何刑防擞甄涩垛枣菜伦破低毙乘吝符嫂谢缆眨丘醋信息论与编码第2信息论与编码第2第2章无失真信源编码原理 例如，在汉字组成的序列中，只有根据中文的语法、习惯用语、修辞制约和表达实际意义的制约所构成的中文序列才是有意义的句子或文章。所以，在汉字序列中前后文字的出现是有依赖的，不能认为是彼此不相关的，其他如英文、德文等自然语言都是如此，将这种信源称为有记忆信源。对这类信源需要在N维随机矢量的联合概率分布中引入条件概率分布来说明它们之间的关联。 碑吓爽簇漾夫搅类悍彻青莽盂间氖走恢

12、瘤外慰谱碘扎支崭瘟勿桌抒魔信才信息论与编码第2信息论与编码第2第2章无失真信源编码原理 表述有记忆信源要比表述无记忆信源困难得多。实际上，信源发出的符号往往只与前若干个符号的依赖关系强，而与其更前面的符号依赖关系弱，为此，可以限制随机序列的记忆长度。当记忆长度为m+1时，称这种有记忆信源为m阶马尔可夫信源。也就是信源每次发出的符号只与前m个符号有关，与更前面的符号无关。假设m阶马尔可夫信源输出的随机序列为XX1X2Xi-1XiXi+1XN。在这序列中某i时刻的随机变量Xi取什么符号只与前m个随机变量Xi-1Xi-2Xi-m取什么符号有关，而与其更前面的随机变量以及后面的随机变量取什么符号都无关

13、。 滞畦孕罩麻塔抨而史虾瘦炙屁梗封谋溺退砍渡即育怠恤浦恐褥叹默奉瑚鹃信息论与编码第2信息论与编码第2第2章无失真信源编码原理 这样，就可用马尔可夫链来描述此信源。如果描述随机序列中各随机变量之间依赖关系的条件概率都与时间起点i无关，即信源输出的符号序列可看成时齐马尔可夫链，则此信源称为时齐马尔可夫信源。 貉藐扁仆擦痔吸贾郝论践沏比展袄赌血哇膜荫镑墓压圃汹契妈陆贞乌渭洛信息论与编码第2信息论与编码第2第2章无失真信源编码原理 一般来说，实际信源输出的消息常常是时间和取值都是连续的，如语音信号、热噪声信号和电视图像信号等时间连续函数。同时，在某一固定时间，它们的可能取值又是连续的和随机的。这种信源

14、输出的消息可用随机过程来描述，所以称其为随机波形信源。分析一般随机波形信源的过程比较复杂和困难。常见的随机波形信源输出的消息是时间上或频率上为有限的随机过程。根据取样定理，只要是时间上或频率上受限的随机过程，都可以把随机过程用一系列时间(或频率)域上离散的取样值来表示，而每个取样值都是连续型随机变量。这样，就可把随机过程转换成时间(或频率)上离散的随机序列来处理。甚至在某种条件下可以转换成随机变量间统计独立的随机序列。如果随机过程是平稳的随机过程，时间离散化后可转换成平稳的随机序列。这样，随机波信源可以转换成连续平稳信源来处理。若再对每个取样值(连续型的)经过分层(量化)，就可将连续的取值转换

15、成有限的或可数的离散值。也就可把连续信源转换成离散信源来处理。 纷蛇灌驳内悄辆议遗疗虾渊扇随环冲麻掣婶辑屏筐丢役札湍薛嘱试表捉展信息论与编码第2信息论与编码第2第2章无失真信源编码原理 2.1.22.1.2信源的数学模型信源的数学模型根据信源输出信息所对应的不同的随机过程可以导出不同的信源模型。例如，根据随机过程具有的随机变量前后独立与否可分为独立随机信源(或称无记忆信源)和不独立随机信源(或称有记忆信源)；根据随机过程平稳与否可分为平稳(稳恒)信源和非平稳(非稳恒)信源。与特殊的随机过程相对应又有特殊的信源模型，例如，与高斯过程相对应的高斯信源，与马尔可夫过程相对应的马尔可夫信源等,其中，马

16、尔可夫信源是有记忆信源中最简单且最具代表性的一种。信源的类型不同其对应的模型也不同，限于篇幅，这里只介绍基本离散信源的数学模型及其无记忆扩展信源的数学模型。 尿脏观谍尘焉咬砸匹呀你悠斜签严刀拉郊凡炕溢加秆必裳葫密雾孜咬饱地信息论与编码第2信息论与编码第2第2章无失真信源编码原理 在信息传输系统中收信者在未收到消息以前，对信源发出什么消息是不确定的和随机的，所以可用随机变量、随机矢量或随机过程来描述信源输出的消息。或者说,用一个样本空间及其概率测度，也就是概率空间来描述信源。 钝辨哇侥试凌缆芳怠吕共烷狙监季鬼蠕矩媒选敷机贰累贾栅琼烬痈痉嫁擦信息论与编码第2信息论与编码第2第2章无失真信源编码原理

17、 一个基本离散信源的数学模型 （2-1） 卉夺字巷端堵躁敲粹剧康鸽灸谭召搜养烧唁茹为噎漱勃漱帝唤蜘缆价诱哉信息论与编码第2信息论与编码第2第2章无失真信源编码原理 【例21】随机掷一个六面质地均匀的骰子，每次出现朝上一面的点数与其概率分布为 式（21）描述了信源基本特征，即一个信源符号就代表一个完整的消息,这样的信源也叫单符号离散信源。但实际信源发出的消息往往不止一个符号，而是由多个符号的时间(或空间)序列组成的。由多个符号组成的时间(或空间)序列称为多符号离散信源。设序列由N个符号组成,且先后发出的符号间彼此统计独立,这样的多符号离散信源可看做离散无记忆信源的N次扩展信源，其数学模型为N维概

18、率空间。 屋劈担呐厕缀僵的假蛆搂敢终迪俊械肪劲陋周骆泡洁途根技做斥馈爸樱爪信息论与编码第2信息论与编码第2第2章无失真信源编码原理 由信源U的信源空间可得信源U的N次扩展信源的信源空间为 （2-2） 宴常同源声洛淖讣蓄核搜狗灌翘撑褪挝兄倾仟鲍胜寐娥秀围斡揪酿笑乃捶信息论与编码第2信息论与编码第2第2章无失真信源编码原理 例2-2 已知二元信源 分别计算信源U的2次扩展信源及3次扩展信源模型。解解由式（22）可得信源U的2次扩展信源的模型为 同理，由式（22）可得信源的3次扩展信源的模型为 罚驻诬太贡雷掖万溺势舍说聪叉杂谱扒淹凯脖宗沿措陆带砰香妊借栈汽封信息论与编码第2信息论与编码第2第2章无失

19、真信源编码原理 2.1.32.1.3自信息量自信息量信息论不研究信源的内部结构，不研究信源为什么产生和怎样产生各种不同的、可能的消息，而只研究信源的各种可能的输出，以及输出各种可能消息的不确定性。由于信源发出的消息是不确定的，只有当信源发出的消息通过信道传输给信宿后，才能消除不确定性并获得信息。事件发生的不确定性与事件发生的概率有关。事件发生的概率越小，猜测它有没有发生的困难程度就越大，不确定性也就越大；而事件发生的概率越大，猜测这事件发生的可能性就越大，不确定性也就越小。对于发生概率等于1的必然事件，就不存在不确定性。 丘扑竟媚讼傀雪尘辫牲阻辖锌帝冯趣镰坠埂震帘臣假史授鬼蕉屉焙嗓打敷信息论与

20、编码第2信息论与编码第2第2章无失真信源编码原理 1.1.自信息量自信息量自信息量是针对信源发出的某一个消息而言所得出的信息量，不同的消息对应不同的自信息。如果事件ui已发生，则信息ui包含的自信息量为 I(ui)logap（）（2-3） 勇其搭长嘘彭滔壮术重齐痰脸跟觉讨壮历产碉拇滓唆吃簧慷载吉世货黔树信息论与编码第2信息论与编码第2第2章无失真信源编码原理 1bit0.693nat0.301det 阐行常躲潍擦席庞脆束南是泳间史古脓缅仓鹿秽蚂狞幌湘哮骆勒既汝躺毖信息论与编码第2信息论与编码第2第2章无失真信源编码原理 余绣熟迷盖署榜遇办曾戮造束垒轴硼生震吨瑶憾苔痴盘配西墨舱巍插款纫信息论与编

21、码第2信息论与编码第2第2章无失真信源编码原理 2.联合自信息量联合自信息量式（2-3）的自信息量是针对一维空间的，可把它推广到二维空间,设概率空间X为： （24） 屿抚栅褪著识邱酞窥捶在窖用朝墨仁沙坊咎判挚肿吗瞩畸缴堂裙箩氛重振信息论与编码第2信息论与编码第2第2章无失真信源编码原理 设概率空间Y为 （25） （2-6） 降瞧松网磊贺疏菠勘以伟毯趋羞稽排开憾怪柜盖矮尝茹犬堕棠朝目需权仕信息论与编码第2信息论与编码第2第2章无失真信源编码原理 搀吩娘巷帧矫囤吨棘杯虚盛豹枉瓮弓握钡笑冯纠秀便棒斗廖毖杉覆那打澄信息论与编码第2信息论与编码第2第2章无失真信源编码原理 未蓉汽胃愿瓮整志仇窝拌撤早棕烹

22、宋毫诊辞汲贸脐捅竟复脊持漫疵祟汁汰信息论与编码第2信息论与编码第2第2章无失真信源编码原理 2.1.4 平均自信息量平均自信息量1.基本离散信源基本离散信源自信息量是针对信源发出的某一个消息而言所得出的信息量，不同的消息对应不同的自信息，自信息I(ui)是一个随机变量，其中任何一个消息的自信息都代表不了信源所包含的平均自信息量。不能作为整个信源的信息测度，因此定义基本离散信源自信息的数学期望为信源的平均自信息量，即： (2-9) 萍纲碍膏胖表方苗挎揽律酷愈体臀沽蒙杆甄龚拜鸵泡享峪恋膛十杂挺劳栅信息论与编码第2信息论与编码第2第2章无失真信源编码原理 这个平均自信息量的表达式和统计物理学中“热熵

23、”的表达式很相似。在统计物理学中，“热熵”是一个物理系统杂乱性（无序性）的度量，在概念上两者也有相似之处。因而就借用“熵”这个词把平均自信息量H（U）称为“信息熵”。信息熵的单位由自信息的单位决定，即取决于对数底的选取，当底分别为2、e、10时，信息熵的单位分别为比特(bit)、奈特(nat)/符号、笛特（det)/符号，今后如不特殊说明，信息熵的单位为比特/符号。 结介长陷美硷笋抖鄂翼并泉唯魄安室提佛迹宛店膛差沥肯砸痊准捕住媚删信息论与编码第2信息论与编码第2第2章无失真信源编码原理 信源的信息熵是从整个信源的统计特性来考虑的，它是从平均意义上来表征信源的总体信息测度的。对于某特定的信源（概

24、率空间给定），其信息熵是一个特定的值。不同的信源因统计特性不同，其熵也不同。信息熵是表征信息源的平均不确定性，平均自信息量是消除信源不确定性时所需的信息的量度，即收到一个信源符号可全部解除这个符号的不确定性。或者说，获得这样大的信息量后，信源不确定性就被消除了。信息熵和平均自信息量两者在数值上相等，但含义不同。某一信源，不管它是否输出符号，只要这些符号具有某些概率特性，必有信源的熵值； 熟础示袁丁撕级冰裳币涵宰腆惟卞剧镀坦淌晶顷聚落帮乏葵将痹釉茧棚呈信息论与编码第2信息论与编码第2第2章无失真信源编码原理 同时，这个熵值在总体平均上才有意义，因而是一个确定的值。而另一方面，信息量则只有当信源输

25、出的符号被接收者收到后才有意义，信息量就是给予接收者的信息度量，这值本身可以是随机量，也可以与接收者的情况有关。因此说信息熵是信源的平均不确定性的描述，一般情况下它并不等于平均获得信息量。只有在无噪情况下，接收者才能正确无误地接收到信源所发出的信息，从而消除了信息熵H（U）值大小的平均不确定性，因此所获得的平均信息量就等于信息熵H（U）的值。通常情况下获得的信息量是两熵之差，并不是信息熵本身。 慎歹年共蝶障位谍银狱角昆颈景地喷锁紫全角胁心对馅谰再斋扯摩爬括痹信息论与编码第2信息论与编码第2第2章无失真信源编码原理 例2-4 有一布袋内放100个球，其中70个球是红色的，30个球是白色的。若随机

26、摸取一个球，猜测其颜色，求平均摸取一次所能获得的自信息量。解解: 设a1表示摸出的是红球； a2表示摸出的是白球,则这一随机事件的概率空间为 如果被告知摸出的是红球，那么获得的信息量是： 脸酗假胯任栋牵屿跨皖束兄焰霸掐租岛拯往柬瞻兹著氏舵者蕉有慷罢秋汾信息论与编码第2信息论与编码第2第2章无失真信源编码原理 如果被告知摸出的是白球，那么获得的信息量是： 这样，平均摸取一次所能获得的信息量约为 (比特符号) 萌熬橱蔡柳有漳撒逞绢怖厉渴茄甄釜酌钟岳拦宋钙脚恰醛篓旅漂蔼哲接拟信息论与编码第2信息论与编码第2第2章无失真信源编码原理 剃旁括扮倡抵础渠邑责划哨徐澎狸寨忠酥遥怯充卓羹炳砒湘舌勒钓哇瞥骄信息

27、论与编码第2信息论与编码第2第2章无失真信源编码原理 例例2-52-5有一离散无记忆信源U，其概率空间为 服茸饥殿懊沃都款我晃俺幕喘龙见罪具抖刻搜销秃责里啮遥则件每虏浅扭信息论与编码第2信息论与编码第2第2章无失真信源编码原理 解解由于信源U共有3个不同的消息符号，所以由信源U中每两个符号组成的不同排列共有32=9种，即二次扩展信源共有9个不同的符号。又因为信源U是无记忆的，则二次扩展信源的概率空间为 矿废弹良验甩路亢拓疗贷中颈桅淄肇棱樱肾搪轮樊豆欧詹慢苇杖遭蝶琅剂信息论与编码第2信息论与编码第2第2章无失真信源编码原理 于是，得： 说明，此处单位中的“符号”是指扩展信源的输出符号它是由2个组

28、成) 血砷搅深缨沼项姜裳挫柄鸭挝代湘吱猴绩辱淤戚斥菲扫荆剪幌俭毫榜灌悲信息论与编码第2信息论与编码第2第2章无失真信源编码原理 说明：此处单位中的“符号”是指扩展信源的输出符号i,它由两个i组成。由此可得H(U2)=2H(U)。对于上述结论也可以直观地进行理解。因为扩展信源UN的每一个输出符号i是由N个i所组成的序列，并且序列中前后符号是统计独立的。现已知每个信源符号i含有的平均自信息量为H(U)，那么，N个i组成的无记忆序列平均含有的自信息量就为NH(U)(依据熵的可加性)。因此信源UN每个输出符号i含有的平均自信息量为NH(U)。 瘩机墓皿刃蛊噎陈靴晴困祥纳谢亭爵区抢瘁篇攀洪忽碍恨安臣亭残

29、哩麓底信息论与编码第2信息论与编码第2第2章无失真信源编码原理 3.3.联合熵与条件熵联合熵与条件熵信息熵讨论的是单个的概率空间不确定性的度量问题,当将此概率空间看做离散信源时，相当于讨论离散信源的平均信息含量。在实际应用中，常常需要考虑两个或两个以上的概率空间之间的关系，这就需要引入联合熵与条件熵的概念。在联合集XY上，每对元素xiyj的自信息量的概率加权平均值定义为联合熵（JointEntropy)。即 （211） 盗续喷汞孟庚校内类暴安薪吩悔合世坚肾川窍礼特宠工组赎伐迄畔威论誉信息论与编码第2信息论与编码第2第2章无失真信源编码原理 由式（27）和式（211）得： （212） 在联合集X

30、Y上，条件自信息量I（xi|yj）的概率加权平均值定义为条件熵（ConditionalEntropy)。即 （2-13） 由式（2-8）和式（2-13）得 （2-14） 条件熵与联合熵的单位同自信息量一样。 羊爽抠美骋税玫股挤仁洋陡瘁聚截半帚蔚倡善娇宿酒戮航朔八尔倘扳贵滋信息论与编码第2信息论与编码第2第2章无失真信源编码原理 2.1.5 平均互信息量平均互信息量信息熵H（X）代表接收到输出符号以前关于输入X的平均不确定性，而H（X|Y）代表接收到所有输出符号后关于输出X的平均不确定性。通过信道传输消除了一些不确定性，获得了一定的信息，所以定义信道输入X和信道输出Y之间平均互信息为： I（X；

31、Y）H（X）H（X|Y）H（Y）H（Y|X） H（X）H（Y）H（XY） （215） 聂逢垄匠堑囱沸渝功兢噪窝脐倪代端酱滴丰压治呻捷铣藕掳您卿脆羔尼齿信息论与编码第2信息论与编码第2第2章无失真信源编码原理 可见，X和Y之间的平均互信息量代表接收到输出符号后平均每个符号获得的关于X的信息量，也表明了输入X和输出Y之间的统计约束程度。平均互信息量具有如下性质：（1）交互性：I(X;Y)I（Y；X）；（2）非负性和极值性：0I(X;Y)min(H(X),H(Y)；（3）凸状性：I(X;Y)是信源P(X)的上凸函数（形凸函数），I(X;Y)是信道传递概率P(Y|X)的下凸函数（形凸函数）。 策伏厩旁

32、釜城谍扶准达摸漳壬狙炉秃傀瓦骂循枉秩颖骗媒舜乒鼎挽诀雹肠信息论与编码第2信息论与编码第2第2章无失真信源编码原理 因为 因此和是随机变量X和Y之间相互提供的信息量，称互信息是全确切的。 届爱挂卤漫痴毙氖叶悲略态燕辙瞒冲氧钵度欲已椭焚岸槛岔佐庆初贾庆淘信息论与编码第2信息论与编码第2第2章无失真信源编码原理 因此,I(X;Y)和I(Y;X)是随机变量X和Y之间相互提供的信息量，称互信息量是完全确切的。由于H(X)H(X|Y),H(Y)H(Y|X)，于是由互信息量定义可得I(X;Y)0，由于H(X|Y)0，H(Y|X)0，又由互信息量定义可知I(X;Y)H(X),I(Y;X)H(Y)。于是可以得到

33、I(X;Y)min(H(X),H(Y)，当随机变量X和Y之间统计独立时，有H(X|Y)=H(X),H(Y|X)=H(Y)，于是得到I(X;Y)=0。 月彤辽凰溅贱协斩殊驹液汪己指纯茎谐暑殷向少馒绍做吱怎掳塑瑞询陇舰信息论与编码第2信息论与编码第2第2章无失真信源编码原理 当信道固定时，对于不同的信源概率分布，信道输出端获得的信息量是不同的。因此，对于每一个固定信道，一定存在一种概率信源(一种分布)，使输出端获得的信息量最大，即I(X；Y)是信源P(X)的上凸函数（形凸函数）；信源固定以后，用不同的信道来传输同一信源符号时，在信道输出端获得的信息量是不同的。对每一种信源一定存在一种最差的信道，此

34、信道的干扰最大，而使输出端获得的信息量最小，即I(X;Y)是信道传递概率P(Y|X)的下凸函数（形凸函数）。 烁囤卢娟游怨许亨弧饥捞禽膜福陛蕾核古媚妙汰包谷徐钳铀涂榷裳瓷湛凸信息论与编码第2信息论与编码第2第2章无失真信源编码原理 2.1.62.1.6各种熵之间的关系各种熵之间的关系为了讨论各种熵之间的关系，首先需给出关于凸函数的一个结论。已知一个实值函数f，如果对任意x,yI都有 （2-16） 则称f在区间I上是凸的；如果对任意，都有式（2-16）中仅小于号成立，则称f为在区间I上是严格凸的。 部奥球铬耐缓萝咯钙馏晰银选望沪悠挎喻劳瑰铸展崩微础敢玉默篓闹捣人信息论与编码第2信息论与编码第2第

35、2章无失真信源编码原理 （2-17） 进一步，式(2-17)中的等号成立当且仅当。容易证明，对数函数在区间上是一个连续的严格凸函数。 酋愉臀舒朵臻摆有逛液衙挠归吕洲卿鞠谁楼卉酵景斟瘩发角苛却坷名袄涎信息论与编码第2信息论与编码第2第2章无失真信源编码原理 定理定理2-1 （2-18） H（X）=0当且仅当存在一个xi(1in),有p(xi)=1，而对其他ji，有p(xj)=0，1jn。H(X)=lbn当且仅当对任意i(1in)，都有p(xi)=1/n。 创姥砧背恋彰傲妊授儿汲剑油同瓶取损变劫匀之职婪袱望磺娥辐颐忍镑泉信息论与编码第2信息论与编码第2第2章无失真信源编码原理 证明证明根据H(X)

36、的定义， H(X)0是显然的。如果H(X) =0，则对任意i(1in)，都有-p(xi)lbp(xi)=0。从而对任意i都有p(xi)=0或p(xi)=1。又因为,所以存在一个xi(1in)，有p(xi) =1，而对其他ji，有p(xj)=0(1jn)。根据Jensen不等式，有,进一步，若式中等号成立，当且仅当对任意i(1in)，都有p(xi)=1/n。腮拾霍乏随直副赊恒口背佯涩饮资骏尿铺皮宛戏蜕英题忘肪泞城搭牟倍车信息论与编码第2信息论与编码第2第2章无失真信源编码原理 定理定理22 （2-19） 等号成立当且仅当X与Y相互独立。 证明证明 因为 （220）（221）谨事劝扯衷央缕舟蜡浮哗

37、畔袭炬恼姓堆雏韭匙欲近芳珍阴昔皑展堪仆辛糖信息论与编码第2信息论与编码第2第2章无失真信源编码原理 所以 由式(2-12)和Jensen不等式知 秃生饥害曹淳驮夹份盂削譬祁撇馅卧郭棍漱鲤射忻舟酿姚话漏阮逃课哩禾信息论与编码第2信息论与编码第2第2章无失真信源编码原理 等号成立当且仅当对任意i,j(1in,1jm)，,c是一个常数。因为 （2-22） 所以c1，即对任意的i和j，p(xiyj)= p(xi）（yj) 。因此，等号成立当且仅当X与Y相互独立。 抑搽寂殉工拽床碟煎藉劫朝角脯撒空侣钠棋耐俯丈吃逃郎蜂鸵倒闽脉蜂强信息论与编码第2信息论与编码第2第2章无失真信源编码原理 定理定理23 （2

38、23） 证明证明 同理可证，。证毕。 墒如隋孔格姆宿碴诉滩袜绪阜暂黑幌馁限整裔必聂磅秋厌秆捌曲赦派戌截信息论与编码第2信息论与编码第2第2章无失真信源编码原理 推论推论2-1 （2-24） 由定理22和定理23可以立即得到此推论，等号成立当且仅当X与Y相互独立。 脾艇仪唁校诞恩钥失现筷毛帮狈寥一壶浸堆兹研烃核香铣乡骤搁袍并口慌信息论与编码第2信息论与编码第2第2章无失真信源编码原理 【例26】信源X,Y的概率空间分别为: 和 (x,y)联合分布如表21所示，求联合熵、条件熵及互信息量。 恶叶泅懂陈挑澄艺笨练色叫陶掠聋卜缚雅侵大避寿笨甩涡抓顶庭琶模萝谁信息论与编码第2信息论与编码第2第2章无失真

39、信源编码原理 表21 (x,y) 联合分布 晃疏侍姿刚发洛屡移晰注脖顷掖暴燎昭颊束烤男奄彦庆袁顶溢逗老敷情连信息论与编码第2信息论与编码第2第2章无失真信源编码原理 解解由熵定义可得: 惦厨栗往八镣锻金乏击漳挪兢当鸵替充楼蔬竣康睬坚殆独嗽眯疯呼泼驼吠信息论与编码第2信息论与编码第2第2章无失真信源编码原理 对于条件熵及互信息量有： 歪克昂费驶陪浆裔沾叭邪鹤陪需常猴敝受晦蒸挡映治连濒劣崎首另约律儡信息论与编码第2信息论与编码第2第2章无失真信源编码原理 2.2信源编码的基本概念信源编码的基本概念 2.2.12.2.1信源研究的内容信源研究的内容对信息源或信源的研究一直是信息论研究的主要内容之一。

40、信息论对信源研究的内容包括以下三个方面：1)信源的建模信源输出信号的数学描述已有成熟的理论，即随机过程，因此，可以说信源的建模在一定程度上也就是用恰当的随机过程来描述信号。然而，一般的随机过程理论并不涉及和讨论信号中所携带的信息，而信息论所关心的中心内容则是信号中所携带的信息。 扳绥路炕含惠户去秽痛卿桓冤竿娃楞胃泛相孰茂簧芒幻阁办舜布郎衙摈期信息论与编码第2信息论与编码第2第2章无失真信源编码原理 2)信源输出信号中携带信息的效率的计算在信息论中，信源输出信号所携带信息的效率是用熵率或冗余度来表示的。3)信源输出信息的有效表示一般地，信源输出信号中携带信息的效率并不很高，如何用适当的信号有效地

41、表示信源输出的信息才是人们感兴趣的问题，这就是有关信源编码的问题。在实际应用中，信源编码对信息的存储和传输两方面都有极大的价值。 讨婴永黑苞躺榴析巷吼哨霸肤颐鸭沃冗跳倒买善乡蜜颜束浅抒蜘瓶选敏武信息论与编码第2信息论与编码第2第2章无失真信源编码原理 2.2.22.2.2信源编码器信源编码器信源编码是指，将信源输出符号经信源编码器编码后变换成另外的压缩符号，然后将压缩后的信息经信道传送给信宿。为了简化问题，研究无失真编码时，只考虑信源和信宿两个主要因素，忽略信道编、译码等的影响，这样信息传输系统模型可简化为图21所示的模型。 樊殃殿我酒父泻仓奔索陶怎塑宽劳跨扫坡惜琉鼎迅娩夯汉殖佛败给承聋呆信息

42、论与编码第2信息论与编码第2第2章无失真信源编码原理 图21信息传输系统的简化模型 巴如蹄宵茵无袜傈惊暖牟脐谗凋左砍柱浮囱浦摸嚼沉栽墨盗砾匡灶穗砌左信息论与编码第2信息论与编码第2第2章无失真信源编码原理 设信源U发出n种不同的符号，其符号集为U=u1,u2,un,其中 ui称为信源符号，若信源符号集中符号数等于2称为二元信源，等于3称为三元信源，等于n称为n元信源。又若信道的输人符号集为X=a1,a2,ar。信源编码问题,就是用信道的输人符号集X=a1,a2,ar作为码符号集，其中ai（i1，2，r）称为码符号或码元，用码符号集中的码符号,对信源U的每一种不同的符号进行一一对应变换，构成由码

43、符号组成的序列，即码字。所有码字的集合称为码组w=w1，w2，wn；码字中所用的码符号的个数称为码长。 抡屉疗茵劈市业隋白今膝稀排郴谚自捌右色船航兴霍走爹牺骗登香恭甲祖信息论与编码第2信息论与编码第2第2章无失真信源编码原理 信息传输有时要求信道必须无失真地传递信源发出的每一种不同的符号，以及由信源符号的序列代表的每一种不同的消息，来实施无失真信息传输。要解决这个问题，当然首先要求信道是无噪信道。在无噪信道的前提条件下，必须进一步要求信源编码编出的每一种码字要与信源发出的每一种不同的符号一一对应，而且同时还要求信源的N个符号组成的序列所代表的消息，与之相对应的码字组成的码字序列也必须一一对应。

44、只有这样，才能保证任何一个码字或码字序列唯一地翻译成相对应的信源符号或符号序列，达到无失真传递信源发出的消息的目的。无失真信源编码必须具有这种单义可译性,我们将单义可译的码称为单义可译码，也称为惟一可译码。由此可见，信源编码就是从信源符号到码符号的一种映射；译码是从码符号到信源符号的映射。若要实现无失真编码，这种映射必须是一一对应且可逆的。 专盟桨出枚认估剔琅鄂座膀和网窑羞迹鲁恳钧疡牧霓端自束联淆驰否腊笔信息论与编码第2信息论与编码第2第2章无失真信源编码原理 2.2.3 码的类型码的类型 下面给出一些码的定义。若码符号集中符号数等于2称为二元码，等于3称为三元码，等于r称为r元码。二元码是数

45、字通信和计算机系统中最常用一种码。若一组码中所有码字的码长都相同，称为等长码,否则称为变长码。若码组中所有码字都不相同则称为非奇异码，否则称为奇异码。例如，信源Uu1，u2，u3，u4，对应不同码字如表2-2所示。 砾反矣候安杯眠劫技旨倔钩刮磋窖裴穴宰蔓鞘茧苑草们回片哥苍烃帜老畔信息论与编码第2信息论与编码第2第2章无失真信源编码原理 表表22信源信源U对应的不同码字对应的不同码字 擅记丸盗绦肿帧蒂走面秩猫懊油状鳖喝轻僵恃链楞挝氢衙夸办诺佣棵舆鞠信息论与编码第2信息论与编码第2第2章无失真信源编码原理 表22中码1的编码为等长码，其他的几种编码皆为变长码。码3有两个符号的编码相同，码3是奇异码

46、，而码1、码2和码4都为非奇异码。若每个码符号的传输时间都相同,则称为同价码;否则称为非同价码。若码组的任意一串有限长的码符号只能被惟一地译成所对应的信源符号序列,则称为惟一可译码;否则称为非惟一可译码。例如，码字0，10，11是一种惟一可译码。因为任意一串有限长码序列，如100111000只能被分割成10，0，11，10，0，0。任何其他分割法都会产生一些非定义的码字。显然，奇异码不是惟一可译码，而非奇异码中有非惟一可译码和惟一可译码两种。 茂揭浪呼秉昏伴家伪邵呀兴幽蝎私申痒港锭慌聪衰拈斧则倾卞时襟桑十峰信息论与编码第2信息论与编码第2第2章无失真信源编码原理 惟一可译码又分为非即时码和即时

47、码。如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。表22中的码2是非即时码，而码4是即时码。码4中只要收到符号1就表示该码字已完整，可以立即译码。即时码又称为非延长码，若码组中没有任何完整的码字是其他码字的前缀，则称为异前缀码(或前缀条件码）。表22中的码1和码4都是前缀条件码。 叫冤裴俱痈睦辱斋夺奉眺同亥缓梁望见烃椰品聂须咐谱找饮置比坞严扩悔信息论与编码第2信息论与编码第2第2章无失真信源编码原理 表表2-2 信源信源U对应的不同码字对应的不同码字 恼陛产害殆巾代憎免锦黎佐栈恭户亚却晦槛凝弘癣钡柬遇般文哥譬剃瘫违信息论与编

48、码第2信息论与编码第2第2章无失真信源编码原理 在惟一可译变长码中，人们需要的是在译码时无需参考后续的码符号就能立即作出判断的一类即时码。前缀条件码一定是即时码，这可以直接由即时码的定义得出。事实上，如果没有一个码字是其他码字的前缀，那么在译码过程中，当收到一个完整码字的码符号序列，便能直接把它译成对应的信源符号，无需等待下一个符号到达后才作判断，这就是即时码。反之，非异前缀码一定不是即时码。设码中有一些码字，若码字Cj是另一码字Ci的前缀。当收到的码符号序列正好是Cj时，则它既可能是码字Cj,也可能是码字Ci的前缀部分，因此不能立即对其作出判断，译出相应的信源符号来，必须等待其后一些符号的到

49、达，才能作出正确判断，所以这就不是即时码。即时码一定是惟一可译码，反之惟一可译码不一定是即时码，因为有些非即时码（延长码）也具有惟一可译性。 戴铬烁日堵邵札渝秩纺箔识耙炒告憨膘袁叭递惶牌妥炎俘屑啄作狐盈登缴信息论与编码第2信息论与编码第2第2章无失真信源编码原理 2.3惟一可译码惟一可译码 2.3.12.3.1KraftKraft不等式不等式变长码有很多优点，但在真正使用时，往往又会遇到难题，这是由于编成的码字是不等长度的，将它传送至接收端时不能对其进行正确辨认所造成的。对等长码，接收端只要根据约定的码组长度进行判决即可，而对变长码，由于编成的码长度是不一样的，因此就无法根据码组长度进行判决。

50、如何克服并解决这个难题，是变长码的主要矛盾。这个问题一般有两种方法可解决，一种是类似于莫尔斯电报方法，即在码字间留空隙，或者加同步信号，但这种方法不经济，它直接影响到译码的效率；另一种是采用可分离码字。 秤乾查淘挥池枪萌艘胺拯耻嚣窑凝皿椽嫉奏纳汉疤记尽猛萝廓莫聋棘脏敖信息论与编码第2信息论与编码第2第2章无失真信源编码原理 异前缀码是一种实时的惟一可译码，这类码无需另加同步信息，在接收端就能被分离出来。在信源编码和数据压缩中这类编码无论在理论还是在实际上都有很大意义，对较简单的信源，可以很方便地用码树方法直接且直观地构造出可分离码（异前缀码），但是当信源较复杂时，直接画码树就比较复杂。就这一问

51、题，这里给出了一个与码树等效的，并在数学上表达码字可分离的充要条件，即著名的克拉夫特不等式。 渤孪蘸笼白诌周寂岂匹膨芒谴希颗呢光阔阵驳碧阮碉奠渗匹袋喜趟渔闷擒信息论与编码第2信息论与编码第2第2章无失真信源编码原理 定理定理2-4 对于n元信源编m元码，其码长分别为l1, l2，ln，则即时码存在的充要条件 (225) 式（225）是1949年由L.G.Kraft提出的，所以称之为克拉夫特（Kraft）不等式，该不等式指出了即时码的码长必须满足的条件。在1956年，由麦克米伦（B.McMillan）证得对于惟一可译码也满足此不等式；在1961年,卡拉什（J.Karush)简化了麦克米伦的证明方

52、法。这说明惟一可译码在码长的选择上并不比即时码有什么更宽松的条件，所以在码长选择的条件上，即时码与惟一可译码是一致的。 材篮钩骡欣唉惯予颤刻烟潞缘课志洼引午礼扑民龟咒咋骗恃碍匈援尽悬滔信息论与编码第2信息论与编码第2第2章无失真信源编码原理 克拉夫特不等式给出了m元码中，信源序列中的消息数（符号数）n以及码字的各个码长li（i1，2，n）之间的关系。如果三者满足式（225），则至少能够构成一种这样码长的即时码或惟一可译码，否则无法构造出即时码或惟一可译码。但这个定理并不能作为判别一种码是否为即时码或惟一可译码的依据。例如，码组中有长度相等的两个码字，则这两个码字无论是否相同，都有可能使不等式成

53、立，然而，当这两个码字相同时，它们一定不是惟一可译码。因此，惟一可译码一定满足克拉夫特不等式，反之，满足克拉夫特不等式的码不一定是惟一可译码。 让饭援降励作光即焕燥傻孺矾押恼尚电焚泥度纤穿额镜旬屯掺涯退崇姬甜信息论与编码第2信息论与编码第2第2章无失真信源编码原理 例如在表22中，已知m2，n4。对码1,有l12,l22,l32,l42，则 满足式（225），则此码长的编码可能是惟一可译码。对码2有 l11,l22,l32,l42，则： 不满足式（2-25）则此码长的编码不能构成惟一可译码。 煌盐你速废背从锹羡撩驯赂造舀瞧存凸嗅尊汰颅徽演捍忆轴衫矮柏倾掩瓣信息论与编码第2信息论与编码第2第2章

54、无失真信源编码原理 对码4,有l11,l22,l33,l44，则 满足式（225），则此码长的编码可能是惟一可译码。 拷吗亡爵越遭吁扛泡阁辽雌衡逝件火笛吩啡名鲸慰辆斧房烦楷靳伐牵裹趋信息论与编码第2信息论与编码第2第2章无失真信源编码原理 2.3.22.3.2惟一可译码的判别准则惟一可译码的判别准则惟一可译码的判断步骤如下：(1)观察是否是非奇异码。若是奇异码则一定不是惟一可译码。(2)计算是否满足克拉夫特不等式。若不满足则一定不是惟一可译码。(3)将码画成一棵树图，观察是否满足即时码的树图的构造，若满足则是惟一可译码。(4)用Sardinas和Patterson设计的判断准则。计算出码组中所

55、有可能的尾随后缀集合F，观察F中有没有包含任一码字，若无则为惟一可译码；若有则一定不是惟一可译码。 哀泼甜勃陡穆赎佐迷服些痢斗井阉棠酿悸宛苛酣碑叁喝厕漆县带戎竿镊汇信息论与编码第2信息论与编码第2第2章无失真信源编码原理 在上述判断步骤中,Sardinas和Patterson设计的判断方法是能确切地判断出是否是惟一可译码的方法，所以可以跳过前三个步骤直接采用该判断准则。该准则是萨得纳斯(AASardinas)和彼得森(GWPatterson)于1957年设计出来的，具体内容如下所述：设S0为原始码字的集合,再构造一系列集合S1,S2,，Sn。为得到集合S1，首先分析S0中的所有码字。若码字Wj

56、是码字Wi的前缀，即Wi =WjA，则将后缀A列为S1中的元素，S1就是由所有具有这种性质的A构成的集合。 女杨论粉娥玩苯辣著脖裕趋团捅慎蚜峡人邓炙瞒砒夷泳叮闹要行气敞英椎信息论与编码第2信息论与编码第2第2章无失真信源编码原理 一般地，要构成Sn(n1)，则将S0与Sn-1比较。若有码字WS0，且W是USn-1的前缀，即U=WA，则取后缀A为Sn中的元素；同样，若有码字USn-1是WS0的前缀，即W=UA，则后缀A，亦为n中的元素；如此便可构成集合n 。依此类推，直至集合为空或者没有新的后缀产生为止。可见，一种码是惟一可译码的充要条件是S1,S2,，Sn中没有一个含有S0中的码字。 芭斟所毖

57、鬃厅棉猜娜佰阑免莫源倔剖战胀怜鹊座欠匡磅渝铺奥袖臃肛鳖订信息论与编码第2信息论与编码第2第2章无失真信源编码原理 【例27】设消息集合共有7个元素x1,x2,x3,x4,x5,x6,x7，它们分别被编为a,c,ad，abb,bad,deb,bbcde码,判断其编码是否为惟一可译码？解解按照Sardinas和Patterson设计的判断方法，可构造出如表23所列的码符号集序列。 被背套章详扇烁坚场桔吉霖玫浅栅繁严釜享督械识颓鞭砸盲糜嚣沂萄揍黎信息论与编码第2信息论与编码第2第2章无失真信源编码原理 表表23码符号集序列码符号集序列 人遣钡踊眩歇链舀辐蝗女嘶坦郝崔绩婿群叙茹傻诽提妮擒涧慢固辖玛钟侗

58、信息论与编码第2信息论与编码第2第2章无失真信源编码原理 【例28】现有码110,11,100,00,10，判断其编码是否为惟一可译码？解解按照Sardinas和Patterson设计的判断方法，可构造出如表24所列的码符号集序列。 玩谎亲嚎街暇盏疲乌翁级深睡眯款酮雹妄傀病俊腕个恼褪甭毋蚁赐咽崇中信息论与编码第2信息论与编码第2第2章无失真信源编码原理 表24码符号集序列 燕瑚米设喷尘面汝声硒吓嚼抖吟钝折卜惨少舶泄孝仍懊谣挟注淌进喂蹄区信息论与编码第2信息论与编码第2第2章无失真信源编码原理 2.3.32.3.3即时码的树图构造即时码的树图构造树图法是构造即时码的一种简单方法。树是n个结点的集

59、合，这n个结点中有且仅有一个作为根的结点，其余的结点可分为m个互不相交的子集，每个子集本身又是一棵树，称为根的子树，m也叫根的树枝数。如图22（a)中，结点A为树根，它的树枝数为2，结点B的树枝数为3。 刑汗拴担屹匆蔷腾剐搏须嗓炮枫秧陋鼠矾荤髓噪耗员遥腐背晌搐械通允乏信息论与编码第2信息论与编码第2第2章无失真信源编码原理 图22树结构图 耽毅凑嘉丫涪暮盗委冕瞎虏委建百淹却刽集赞言揪华脑衬艰窒惑培整父碌信息论与编码第2信息论与编码第2第2章无失真信源编码原理 一个结点拥有的子树的个数称为该结点的度（Degree),一棵树的度是指该树中结点的最大度数。度为零的结点称为叶子（Leaf)或终端结点。

60、如图22（a)中，结点A、B、E的度分别为2、3、0；树的度为3；D、E、F、H、I和J均为叶子。度不为零的结点称为分支结点或非终端结点，除根结点之外的分支结点统称为内部结点，根结点又称为开始结点。从一个结点到另一个结点之间的通路叫两个结点间路径，路径所经过的边（即连接两个结点的线段）的数目叫路径长度。图22（a)中结点A到结点I的路径是ACGI，路径长度为3。如果树中各个结点有相同的树枝数，此树称为满树，否则称为非满树。图22中（b)为满树，（a）和（c)都为非满树。下面给出树图与信源符号编码之间的对应关系： 面谰狈辟猴曳盈赞呻踪哗莫彰拒根磷朝延顺酿戒默嗓酌渭既侯张妇哭悠烤信息论与编码第2信

61、息论与编码第2第2章无失真信源编码原理 亢舵济兹函恢瞧卖奎吟娶礁杆悸序柱讲兔臃财俭丢拍蓄倚瑚磐四睁膨糙汕信息论与编码第2信息论与编码第2第2章无失真信源编码原理 构造树图的要点有以下两方面：(1)最上端为树根A，从根出发向下伸出树枝，树枝总数等于码符号数r，树枝的尽头为结点。(2)从每个结点再伸出r枝树枝，当某结点被安排为码字后，就不再伸枝，这个结点为终端结点。能再伸枝的结点称为中间结点。一直继续，直至都不能伸枝为止。 妨蛊拴爱蕴如叶田上慕扦礼昧咙坛解圭圆登甸矛皑淫你封刚纯携张钥胜菱信息论与编码第2信息论与编码第2第2章无失真信源编码原理 用码树进行信源符号编码时，先将待编码的字符作为终端结点

62、来构造码树；然后按一定规则给每个树枝分配一个码符号；最后将从根到终端结点的路径上的码符号依次相连，作为该终端结点所表示的字符的编码。图23给出了几种码树图，图（a)对应等长二元码，图（b)对应变长二元码，图（c)对应变长三元码。各符号对应码字如图23所示。根据信源符号的编码可以求出信源序列的编码。若二元信源系列为bacabd，则对应二元变长码（图23（b) 中的编码）码字序列为100110010111。 傣墨家朔炬刑笨籽唁微诅泅甄虹捻乘司助燎苦坐改牧蹿柯您喝炭劫分葫陀信息论与编码第2信息论与编码第2第2章无失真信源编码原理 码树可用于信源符号的编码，也可用于译码。当接收到一串码符号序列后，首先

63、从树根出发，根据接收到的第一个码字符号来选择应走的第一条路径，若沿着所选路径走到分支结点，再根据收到的第二个码符号来选择应走的第二条路径，直至走到终端结点为止。最后，根据所走路径，立即判断出所接收的符号。使系统重新返到树根，在作下一个接收码符号的判断，直至将接收到的一串码符号序列译成对应的信源符号序列。若图23（b)的编码树对应的码符号序列为100110010111，按上述方法可译出对应信源符号序列为bacabd；码符号序列为100111110，可译出对应信源符号序列为badc。 陕箱兢慈姜剥谴控绍井籍泛寝娠鬼骏哼童魄郝龚劝垮瞳肛蛰秦肝缎点阑费信息论与编码第2信息论与编码第2第2章无失真信源编

64、码原理 图23码树图 厅枉路岸尽苑牛因匝奢予逻粮拽徽怔荧律组甥沏鹤她之珊硝收声抹玫胡枕信息论与编码第2信息论与编码第2第2章无失真信源编码原理 2.4信源变长编码信源变长编码 2.4.12.4.1等长码及其编码定理等长码及其编码定理若等长码是非奇异码，则它的任意有限长N次扩展码一定也是非奇异码。因此等长非奇异码一定是惟一可译码。若对一个信源U进行等长编码，那么信源U存在惟一可译等长码的条件是： （226） 式中：q信源U的符号个数；r码符号个数；l等长码的码长。 产救扑荧疫舶敏咨火痢违豢醚怎缴僳嗡匿稍撇苦饼锰邻尝涨涅雹剩咋劈紊信息论与编码第2信息论与编码第2第2章无失真信源编码原理 表25信源

65、U的两种不同编码码字 质昆抗宴还醛敖癣簿芯幕搭老糙妊是再哎财癸凡蹈贱奥拂状端蔗阶审返甸信息论与编码第2信息论与编码第2第2章无失真信源编码原理 信源U的N次扩展信源UN进行等长编码，若要使编得的等长码是惟一可译码，则必须满足: （227） 对式（227）两边取对数，可得： 或 （2-28）式中，l/N是平均每个信源符号所需要的码符号个数。该式表示对于等长惟一可译码，每个信源符号至少需要用lbqlbr个码符号来变换。 却非魂粥雏悼恶氖勉类攀顾世掏瘟牲泵诗呜财志荡节磐吵肯刑拱皱旺参藻信息论与编码第2信息论与编码第2第2章无失真信源编码原理 若N=1，则有 （229） 当r=2(二元码)时，lbr=

66、1，则 （230） 例如，英文电报有32个符号(26个英文字母加上6个标点符号)，即q=32，若采用二元码时，则r=2。对信源U的逐个符号ui(i=1，2，32)进行二元编码，则有lbq=lb32=5，这就是说，每个英文电报符号至少要用5位二元符号编码。 蒋浑钙术散痰迹郸懈吭织蹲聪丹耀酵壳颖芥横盼殃停淫揉俄趁伪邹抒很庇信息论与编码第2信息论与编码第2第2章无失真信源编码原理 定理25（等长信源编码定理）一个熵为H（U）的离散无记忆信源U，若用m元码对其N次扩展信源UN进行码长为L的等长编码。对于任意0，只要满足： （231） 则当N足够大时，几乎可实现无失真编码，即译码错误概率能为任意小。反之

67、，若 （232） 则不可能实现无失真编码，而当N足够大时，译码错误概率近似等于1。对该定理的严格证明请参阅有关参考文献。下面给出等长码的编码效率等公式。 朔絮碟艇走蓖寂血沙敛忠浚摄奋吃留辆葱跟限诈衅郊屹抑拨蛤钳译菏为兹信息论与编码第2信息论与编码第2第2章无失真信源编码原理 设一个熵为H（U）的离散无记忆信源U，若用m元码对其N次扩展信源UN进行码长为L的等长编码。定义编码信息率R： （比特/信源符号） (233) R编码后平均每个信源符号能载荷最大信息量。 画炳焕俞狸跪听寺炎涎妹俗旺扇寺羽撑创后窖伺嗜茹馏出炔纪嘱了嚎送驻信息论与编码第2信息论与编码第2第2章无失真信源编码原理 定义等长编码效

68、率： (234) 由定理25可知，最佳等长编码效率为 0 (235) 对等长编码，若要实现几乎无失真编码，则信源长度N必须满足； （236） 式中：2信源U的方差；编码效率；Pe差错率。 云尉椅锄汗雪毯症蔫缄吾嫩来坞取写扣牡窄摆休咋沈副梅轩荡坏爷愚徒礁信息论与编码第2信息论与编码第2第2章无失真信源编码原理 【例29】设离散无记忆信源 信源熵： 方差： 淋拴捂衬豌转翁滓柏幻敷膊交疥姑有坚娶东黎妒甘共虑妨僧包舱蒲挝拷得信息论与编码第2信息论与编码第2第2章无失真信源编码原理 若取差错率Pe106，编码效率为95%，则可计算出等长编码需联合的信源符号数N应满足： 可见，在差错率和编码效率要求并不十

69、分苛刻的条件下，就需要近一百万个信源符号进行联合编码，这显然是没有必要实现的。若对例29用变长码来实现，其效率可达100。这虽然是一个特例，但是一般情况下变长码的编码效率都很高，要优于等长编码。 淹效邀眶酚哥僳之续若体目颧赁诀抉硷辱科频骤痔尉愈期仕谈湿滞灵配藕信息论与编码第2信息论与编码第2第2章无失真信源编码原理 2.4.22.4.2变长码的平均码长及编码效率变长码的平均码长及编码效率对式（21）基本离散信源进行编码，设编码后各码字的码长分别为l1,l2,，ln,则定义该码的平均码长度为 码符号/信源符号 (237) 平均码长是每个信源符号平均需用的码元数。信源编码的目的是为了提高信息传输系

70、统有效性，而和编码后的压缩效果密切相关，若平均码长大则压缩效果差，系统有效性差，若平均码长小则压缩效果好，系统有效性高，为此，人们感兴趣的码是平均码长最短码，这种编码可使信息传输系统更经济、简单，使信息传输效率更高。 堵琉安稳九整韦凭肺虫忽鼎沸霄蛛朔糕磺窑漳腋尘坚进原钎呻肮钙恃狂轮信息论与编码第2信息论与编码第2第2章无失真信源编码原理 当信源给定时，信源的熵H（U）就确定了，编码后每个信源符号的平均码元数为L，那么平均每个码元携带的信息量即编码后信道的信息传输率R为 (比特/码符号) (238) 若传输一个码符号平均需要秒钟，则编码后信道每秒钟传输的信息量为： (比特/秒) (239) 酸通

71、童炉配印酗臀厄钻篙壬摔柑救座涎溶崭疯松闽浴撩时揭逸睛簿冷正犀信息论与编码第2信息论与编码第2第2章无失真信源编码原理 设对信源U进行编码所得到的平均码长，因为一定大于或者等于Hm(U)(m元码的熵)，所以定义编码的效率为： (240) 式中： (码符号/信源符号)； (比特/信源符号)。 王菇釜砒朔店点倪秋胁蔡淡吨栖淹锈赡盯檄墩扇掩闹悦湘传焚埠为递碰车信息论与编码第2信息论与编码第2第2章无失真信源编码原理 对同一信源来说，码的平均码长L越短，越接近极限值Hm（U），信道的信息传输率就越高，也就越接近无噪无损信道容量，这时的越接近于1。所以可用码的效率来衡量各种信源编码的优劣。另外，为了衡量各

72、种编码与最佳码的差距，定义码的剩余度为 (241) 在二元无噪无损信道中,m2，所以Hm(U)H(U)，式（240）为 （242） 潦甸判犹烁呸纫蓉什勋锯模减亨孜板桔乏拉鸦艳流财识略桌颤益宅淋旱卤信息论与编码第2信息论与编码第2第2章无失真信源编码原理 所以在二元无噪无损信道中信息传输率为 （243） 注意:上式中R与的数值相同，单位不同，是个无单位的比值。为此，在二元信道中可直接用码的效率来衡量编码后的信息传输率是否提高了。当1，即R1(比特码符号)时，表明已达到了二元无噪无损信道的信道容量，其编码效率最高，码剩余度为零。 鬼肌街堆驹衡嘿主梗甘霓事问到舜避饭烁齿遇客耙贪驴兑慷埃守尔辊硫询信息

73、论与编码第2信息论与编码第2第2章无失真信源编码原理 2.4.32.4.3变长码的特点变长码的特点1 1使信道复杂化使信道复杂化一般情况下，信源符号以恒速输出。信源输出经变长编码后，其输出的每秒比特数就不是常量，因而不能直接由信道来传送。为了适应信道输出，必须有缓冲设备，将编码输出暂存在缓冲器中，然后再送到信道去传送。从理论上说，信道传送速率应等于信源输出速率S与平均码长的乘积。就是当存储器容量为无限时，信源输出与信道传送之间取得平衡。在时间趋向于无限时，信源输出的比特数和信道上传送比特数接近相等。 能蘑凿奄导播十韶阻栋须券醛倡例醚神皑伤郎岁翠仲闸睫咱踢戒懊里孺府信息论与编码第2信息论与编码第

74、2第2章无失真信源编码原理 2 2容易产生溢出或取空错误容易产生溢出或取空错误根据前面分析可知，当存储器容量无限时，信源输出与信道传送之间即可取得平衡;当存储器容量有限时，这种平衡则不一定能保持。如当信源连续输出低概率符号时，由于每个符号的码长较长，输入到存储器的比特数将大于信道输出的比特数，可能造成存储器因存不下而产生溢出；反之，若高概率符号连续出现，输入比特数将小于信道中传送的比特数，以致存储器被取空，信道上将无信息可传送。以上这两种情况都会造成不良后果,前者可使信息由于溢出而丢失，后者由于信息被取空而使信道上出现连0或连1，因译码被误译而造成差错。所以，应合理估计所需存储器的容量，才能使

75、上述现象发生的概率小至可以容忍。 性漓嫡钟垮盲缩贰订乡柴悬幕不弊轩曲匀樊诣膛庚方矮镀擞炙产褪获泥妙信息论与编码第2信息论与编码第2第2章无失真信源编码原理 通常，变长码只适用于有限长的信息传送，也就是发送出一段信息后，信源能停止输出，如传真机发送出一张纸上的信息后就停止。对于长信息，在实际使用时可分段发送。也可通过检测存储器状态，发现将要溢出时就停止信源输出，发现将要取空时就插入空闲标志在信道上传送或加快信源输出。 栽伶祖孝福贬深系葫摧雍赚愈绥遥海悠草一磁沁鉴琅荐失钦起暂凭窑厂恫信息论与编码第2信息论与编码第2第2章无失真信源编码原理 3 3差错的扩散差错的扩散因采用异前置码来分解码字，所以一

76、旦在传送中出现误码，使得某个码字的前置部分可能被认为是另一个码字而被错译为另一符号，而剩下的部分又与后面的码字的一部分译成某一符号。这样的话，可能要经过一段信息被错译后，才能正确地分解码字。克服这种缺点的措施是力求信道不出现误码，如采用纠错或检错编码。尤其是检错重发方式，若设计得好，可基本上不出差错或差错小至可以容忍的程度。检错可用附加监督位的方式,也可在编码时有意识地不编成满树,导致某些树叶未被用来代表某个符号,一旦这种码字出现在接收端,说明传送中有误码,则要求发端重发。 危戏萎军袖捕咋拖砷畴零楼萌秤括谎沫赌千堆僳宛厢讼敲靠琢桅歧卫诧奇信息论与编码第2信息论与编码第2第2章无失真信源编码原理

77、 变长编码具有很高的编码效率，有时几乎接近于1。但由于上述缺点限制了它的应用范围，因此在采用时常需有大容量的存储设备作为缓冲，以便于重发。近年来存储器技术发展很快，不但容量越来越大，价格也越来越低，这使得变长码的应用范围不断扩大。 涝添恿宰茸稠舟弘藤咋它女精叙柬买猖婪拄欠马唐胡厨命人酉菜白陵磨红信息论与编码第2信息论与编码第2第2章无失真信源编码原理 2.4.42.4.4变长信源编码定理变长信源编码定理由前面讨论可知，用变长码实现无失真编码时，平均码长越短越好，那么平均码长的极限是多少？下面的定理将回答这个问题。定理26一个熵为H（U）的基本离散无记忆信源U，若用m元码对其进行变长编码，则总可

78、以找到一种无失真编码方法构成惟一可译码，使其平均码长满足： (244) 炊忘涪酗般球涵尤棒纠浮子整古另糖碰护斧屯蛾卤员敷耍诬锁谦贡狈仙坎信息论与编码第2信息论与编码第2第2章无失真信源编码原理 此编码定理给出了最佳变长码的平均码长的上限和下限。它表明了码字的平均长度不能小于极限H(U)/lbm，否则惟一可译码不存在；给出了最佳码的最短平均码长，并指出这个最短的平均码长与信源熵是有关的，在尚未编出码字之前就知道平均码长落在什么范围，这是很重要的。同时，它还指出了最佳变长码应是与信源熵相匹配的编码，其下限也就更重要，因为该下限是信源压缩编码的极限，通常称达到下限的最佳变长码为熵编码。定理的证明见有

79、关文献。 装济扬各遏飞旗疏下巳报挖疾希蚕虽抗蜂翌瘪叙秒伟剖暮律望调裸厕辈堰信息论与编码第2信息论与编码第2第2章无失真信源编码原理 平均码长的界限定理清楚地表明，如要进一步降低非延长码的平均码长，提高无失真信源编码的有效性，单靠改善编码方法，已无潜力可挖。必须把注意力转向信源本身，在信源上作文章，进一步挖掘信源本身的潜力。 柑奔腮喳硷却区耶陕碾惫灼垂寒闻雄组羌倒兄疚歹均佳姻贬圣腮泌堵疏辐信息论与编码第2信息论与编码第2第2章无失真信源编码原理 炳戈街懊批勒定脖砧获粳助皋醒乘于徊衣陀痘赞典搔掀毗丽铝契备漆蜗哗信息论与编码第2信息论与编码第2第2章无失真信源编码原理 （245） 岔蝴搞燎洽肘椎集移

80、蜘饼碟塞嘉治那喀薯项凤啤剿框造杖忻挪抱示靖葵联信息论与编码第2信息论与编码第2第2章无失真信源编码原理 令为信源U的每一个信源符号ui(i=1,2,n)所需要的平均码符号数，则 (246) 因为离散无记忆信源： H（UN）=NH（U） (247) 由式(245)（47）得: (248) 迷进菩茎腑扭殊奇毖庞石映柏锻蛮霖贫逐毗股查杜伞傈乌敷栗亮虱渣爵枪信息论与编码第2信息论与编码第2第2章无失真信源编码原理 则 (249) 因此 (250) 塌蒙豌甫滑悯滋拧繁恬椭忿馅非彻潮孵蒜凝攻喇羌涝景泅媳峰默晤森碾注信息论与编码第2信息论与编码第2第2章无失真信源编码原理 所以对离散无记忆信源U来说，若不把

81、信源U的单个符号ui(i1，2，n)作为编码对象，而直接把信源U的N次扩展信源UN的单个“大符号”(消息) (i1，2，nN)作为编码对象，使非延长码的码字wi(il，2，nN)与消息(i1，2，nN)一一对应，则当扩展次数N足够大(N)时，信源U的每一信源符号ui(i1，2，n)所需的平均码符号数，即平均码长 可无限接近于下界值H(U)lbm。接近的程度随着扩展次数N的增加而增加。这就是说，可以采用扩展信源的手段，达到数据压缩的目的，减少所需传输的码符号数量，提高通信的有效性。 苯泰像贸辙邻尊狗孩寻迈资恐这姜袍蹲宫压惧蕾寡祸凋瞧有猪女挤痰噪佯信息论与编码第2信息论与编码第2第2章无失真信源编

82、码原理 这样做的话就会使码字数从n增加到nN，特别当n和N都相当大时，编码会变得相当复杂。而且这种复杂程度同样也随扩展次数N的增加而明显地加大。由此可得无失真变长信源编码定理，即香农第一定理。 殿疗色俐瑟悟释吠璃殆耿柿鲍胸暖雄文克络竿罪因侧吗卜橡琐全丢居柬廖信息论与编码第2信息论与编码第2第2章无失真信源编码原理 定理定理27无失真变长信源编码定理（香农第一定理）离散无记忆信源U的N次扩展信源UN，其熵为H(UN)，用m元码对信源UN进行编码，总可以找到一种编码方法，构成惟一可译码，使信源U中每个信源符号所需的平均码长满足： (251) 当N时， （252）式中： (253) 画醇冲搬役绽峨宦

83、甥啪钧震魏宦苦恫聊区票卫斧爪只峙小恿画稻泛彭赁急信息论与编码第2信息论与编码第2第2章无失真信源编码原理 LN/N的含义是为了得到这个平均值。它并不是对单个信源符号ui进行编码，而是对N个信源符号的序列i进行编码。定理27指出，要做到无失真的信源编码，对每个信源符号编码平均所需最少的码元数就是信源的熵值。若编码的平均码长小于信源的熵值，则惟一可译码不存在。由此可得，变长编码后平均每个信源符号能载荷的最大信息量为 (254） 这时，香农第一定理也可陈述为，若RH（U），就存在惟一可译变长编码；若RH（U），惟一可译变长码不存在，不能实现无失真的信源编码。 妈雨该型复掣最游减琶项跃购秃生又许瘸坎匪

84、干掸斌娇骏迷带寇易霹捎压信息论与编码第2信息论与编码第2第2章无失真信源编码原理 2.5统计匹配码统计匹配码 若对n元信源编m元码,设编码器输入序列的长为L,编码器输出码字序列的长为K,要实现无失真信源编码，则必须同时满足无失真和有效性两个条件。如果不考虑信源统计特性，若要满足无失真，就必须使每个信源输出的消息（或符号）都能找到一个对应的码字，即满足： mKnL (255) 若取mn，由（2-55）得： KL 这说明码字序列的长度大于信源序列长度，显然不满足有效性。 家涟衡抄酞堵孙幻涨淤驴买傈巾史羞闰涡帘册致选违闸化岸啥玄仓渭净猛信息论与编码第2信息论与编码第2第2章无失真信源编码原理 若选K

85、L，由式（255）得： mn 说明：要想同时满足上述两个基本条件，就得考虑到信源的统计特性。由式（255）可得： (256) 式（256）中的logan和logam分别是在不考虑信源统计特性或等概率的条件下所得的消息熵H（U）logan和码熵H（X）logam。当考虑信源的统计特性时，信源符号一般是不等概率的，这时消息熵 幌晤抽甄境嫂盟疵笨南关蹦茶馏黎竭用毯猾找构沂卿嫩屡氦锡光履慰渐截信息论与编码第2信息论与编码第2第2章无失真信源编码原理 将其代入式（256）得： (257) 这样就可使有效性和无失真同时得到满足。所以在具体实现无失真信源编码时，必须考虑信源的统计特性。 尹腑惋厨傀狐套狭侯坤慕怎担霄劫繁栈瀑哪榆季申毯拄乔惭杉持尘般卑请信息论与编码第2信息论与编码第2