信息论基础信源编码PPT讲稿.ppt

《信息论基础信源编码PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《信息论基础信源编码PPT讲稿.ppt（86页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息论基础信源编码1第1页，共86页，编辑于2022年，星期四0.概述是第一个能够找到的好的变长码.原则：按照符号出现的概率从大到小排序，然后将其分成两个出现概率相同或几乎相同的子集一个子集的编码均以0打头，另一个子集的编码均以1打头；然后把每个子集再分成两个更小的子集，同样确定所有码字的第二位，依次循环.算术码算术码Shannon-Fano-Elias码码第2页，共86页，编辑于2022年，星期四算术码算术码Shannon-Fano-Elias码码例例1 1第3页，共86页，编辑于2022年，星期四0.概述平均码长：0.252+0.202+0.153+0.153+0.103+0.104+0.

2、054=2.7bits/symbol.熵：-（0.25log0.25+0.20log0.20+0.15log0.15+0.15log0.15+0.10log0.10+0.10log0.10+0.05log0.052.67.这是一个较好的结果！算术码算术码Shannon-Fano-Elias码码第4页，共86页，编辑于2022年，星期四算术码算术码Shannon-Fano-Elias码码例例2 2第5页，共86页，编辑于2022年，星期四算术码算术码Shannon-Fano-Elias码码例例3 3第6页，共86页，编辑于2022年，星期四1.基本思路用二进制小数表示信源的概率分布，如果概率分布

3、取值大，则它的二进制位数就低；另外，为了使算术码具有前缀性（无尾随后缀），对概率分布采用累计求和计算.算术码算术码Shannon-Fano-Elias码码第7页，共86页，编辑于2022年，星期四2.编码方法1）将信源符号X=a1,a2,aq依次排列（不要求以概率大小排序）；2）计算各符号的修正累积分函数值3）确定各信源符号所对应码字的码长4）将F(ak)表示为二进制小数，并用小数点后的l(ak)位作为ak的码字.算术码算术码Shannon-Fano-Elias码码x代表不小于x的整数若若二进制小数后二进制小数后面有尾数，则面有尾数，则截断截断第8页，共86页，编辑于2022年，星期四例例1

4、1：若信源的概率分布为若信源的概率分布为 ，取信，取信 号字母表为号字母表为 ，求信源的算术码，求信源的算术码.算术码算术码Shannon-Fano-Elias码码第9页，共86页，编辑于2022年，星期四例例1 1：若信源的概率分布为若信源的概率分布为 ，取信，取信 号字母表为号字母表为 ，求信源的算术码，求信源的算术码.算术码算术码Shannon-Fano-Elias码码第10页，共86页，编辑于2022年，星期四例例1 1：若信源的概率分布为若信源的概率分布为 ，取信，取信 号字母表为号字母表为 ，求信源的算术码，求信源的算术码.算术码算术码Shannon-Fano-Elias码码10第

5、11页，共86页，编辑于2022年，星期四例例2 2有一单符号离散无记忆信源对该信源编二进制香农-费诺码.其编码过程如下表所示：算术码算术码Shannon-Fano-Elias码码第12页，共86页，编辑于2022年，星期四算术码算术码Shannon-Fano-Elias码码第13页，共86页，编辑于2022年，星期四n计算出给定信源香农码的平均码长n若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用3个比特表示。相比较，香农编码对信源进行了压缩。n由离散无记忆信源熵定义，可计算出：n对上述信源采用香农编码的信息率为n编码效率为信源熵和信息率之比。则n可以看出，编码效率并不是很高。算

6、术码算术码Shannon-Fano-Elias码码第14页，共86页，编辑于2022年，星期四思考（一）：思考（一）：用Shannon-Fano-Elias码方法将信源编成二元变长唯一可译码，并计算其码率.算术码算术码Shannon-Fano-Elias码码第15页，共86页，编辑于2022年，星期四算术码算术码Shannon-Fano-Elias码码思考（二）：思考（二）：有两个信源X和Y如下：1)分别用霍夫曼码编成二元变长惟一可译码，并计算其编码效率。*)用Shannon-Fano码编成二元变长惟一可译码第16页，共86页，编辑于2022年，星期四思考（二）：思考（二）：有两个信源X和Y如

7、下：2)分别用Shannon-Fano-Elias编码法编成二元变长惟一可泽码并计算编码效率.3)从X，Y两种不同信源来比较这三种编码方法的优缺点算术码算术码Shannon-Fano-Elias码码第17页，共86页，编辑于2022年，星期四思考（二）：思考（二）：信源X的二元霍夫曼编码：算术码算术码Shannon-Fano-Elias码码第18页，共86页，编辑于2022年，星期四算术码算术码Shannon-Fano-Elias码码第19页，共86页，编辑于2022年，星期四思考（二）：思考（二）：信源X的二元霍夫曼编码：其平均码长编码效率算术码算术码Shannon-Fano-Elias码码

8、第20页，共86页，编辑于2022年，星期四思考（二）：思考（二）：信源Y的二元霍夫曼编码：算术码算术码Shannon-Fano-Elias码码第21页，共86页，编辑于2022年，星期四算术码算术码Shannon-Fano-Elias码码第22页，共86页，编辑于2022年，星期四思考（二）：思考（二）：信源Y的二元霍夫曼编码：其平均码长编码效率算术码算术码Shannon-Fano-Elias码码第23页，共86页，编辑于2022年，星期四思考（二）：思考（二）：信源X的Shannon-Fano编码：算术码算术码Shannon-Fano-Elias码码第24页，共86页，编辑于2022年，星

9、期四算术码算术码Shannon-Fano-Elias码码第25页，共86页，编辑于2022年，星期四思考（二）：思考（二）：信源X的Shannon-Fano编码：其平均码长编码效率算术码算术码Shannon-Fano-Elias码码第26页，共86页，编辑于2022年，星期四思考（二）：思考（二）：信源Y的Shannon-Fano码：算术码算术码Shannon-Fano-Elias码码第27页，共86页，编辑于2022年，星期四算术码算术码Shannon-Fano-Elias码码第28页，共86页，编辑于2022年，星期四思考（二）：思考（二）：信源Y的Shannon-Fano码：其平均码长编

10、码效率算术码算术码Shannon-Fano-Elias码码第29页，共86页，编辑于2022年，星期四思考（二）：思考（二）：信源X的Shannon-Fano-Elias编码：其平均码长编码效率算术码算术码Shannon-Fano-Elias码码第30页，共86页，编辑于2022年，星期四思考（二）：思考（二）：信源Y的Shannon-Fano-Elias码：其平均码长编码效率算术码算术码Shannon-Fano-Elias码码第31页，共86页，编辑于2022年，星期四思考（二）：思考（二）：从信源X和Y的三种不同编码方法可以看出：Huffman编码所得平均码长最短，编码效率最高；Shann

11、on-Fano-Elias编码所得平均码长最长，其编码效率最差；而Shannon-Fano码居中。算术码算术码Shannon-Fano-Elias码码第32页，共86页，编辑于2022年，星期四 Huffman码其编码时短码得到充分利用，而且一定是概率大的信源符号对应于短码，概率小的信源符号对应于长码：所以，其平均码长最短。Shannon-Fano-Elias编码方法虽然概率大的符号其码长短，概率小的符号其码长长，但它短 码 没 有 被 充 分 利 用。所 以，其 平 均码长增大。算术码算术码Shannon-Fano-Elias码码第33页，共86页，编辑于2022年，星期四 Shannon-

12、Fano码也是一种较好的编码方法如信源Y的Shannon-Fano码与Huffman码的编码效率一样好。而信源X的Shannon-Fano码的编码效率比其Huffman码的编码效率降低极少。这是因为信源Y在Shannon-Fano码编程过程中分两大组时“概率和”相差不多(为0.49与0.51)：而信源X在编码过程中每次分两组时，其“概率和”相差较远(第一次为0.57和0.43；第二次上面分组为0.2和0.37，下面分组为0.17和0.26)。算术码算术码Shannon-Fano-Elias码码第34页，共86页，编辑于2022年，星期四数据压缩和信源编码数据压缩和信源编码3.1 等长码等长码

13、3.2 变长编码变长编码 3.3 哈夫曼码哈夫曼码 3.4 算术码算术码3.5 通用信源编码通用信源编码习题三习题三 香农香农-费诺码费诺码;香农香农-费诺费诺-埃里斯码埃里斯码第35页，共86页，编辑于2022年，星期四编码理论（实例）编码理论（实例）以数字电视这一热门话题为例以数字电视这一热门话题为例.第36页，共86页，编辑于2022年，星期四数字电视的主要核心技术包括信源编码、数字电视的主要核心技术包括信源编码、信道编码和显示技术信道编码和显示技术，它们分别解决数字电视节目在初始制作、中间传播和终端呈现三个主要环节上的问题。通俗地说就是满足了我们拍片子、播节目、看电视的需要。编码理论（

14、实例）编码理论（实例）第37页，共86页，编辑于2022年，星期四信源编码技术解决的重点问题是数字音视频信源编码技术解决的重点问题是数字音视频海量数据的编码压缩问题。海量数据的编码压缩问题。n众所周知，数字化视频的原始数据量是十分庞大的，例如，标准清晰度的数字视频每秒的数据量超过200Mbit，高清晰度数字电视每秒的数据量超过1Gbit。编码理论（实例）编码理论（实例）第38页，共86页，编辑于2022年，星期四信源编码技术解决的重点问题是数字音视频信源编码技术解决的重点问题是数字音视频海量数据的编码压缩问题。海量数据的编码压缩问题。n高清晰度数字电视高清晰度数字电视简称高清电视（HDTV）简

15、单的说，是指图像水平清晰度大于720线、采用的是16:9显示方式的数字电视系统。从世界范围来看，目前高清电视主要包括1080i和720p这两种格式，两者图像的长宽比都是16：9，因此这符合人眼视觉的“黄金分割法则”。作为隔行扫描的1080i的分辨率则是19201080；720p是逐行扫描，分辨率为1280720。编码理论（实例）编码理论（实例）第39页，共86页，编辑于2022年，星期四数字音视频要在消费电子产品中得到应用，必须采用先进的压缩编码算法进行大幅度压缩。而反映压缩效率的压缩比也就成为数字电视乃至数字音视频产业的“基本指数”。编码理论（实例）编码理论（实例）第40页，共86页，编辑于

16、2022年，星期四打个形象的比方，信源编码就好像制作压缩饼干的技术，如何将普通面粉制作成压缩饼干就是“编码”过程挤掉冗余成分，只保留有效成分且体积（或所占用资源）尽可能小；而“译码”就是一个还原过程，将压缩饼干恢复到常态供给食用，并保证营养（或信息）损失尽可能少。编码理论（实例）编码理论（实例）第41页，共86页，编辑于2022年，星期四MP3（MPEGAudioLayer）是是一种以高保真为前提下实现的高效压缩技术。它采用了特殊的数据压缩算法对原先的音频信号进行处理，使数码音频文件的大小仅为原来的十几分之一，而音乐的质量却没有什么什么变化，几乎接近于CD唱盘的质量。一分钟的WAVE格式的文件

17、有十几兆，而一分钟MP3格式的音频文件仅有一兆左右。编码理论（实例）编码理论（实例）第42页，共86页，编辑于2022年，星期四MP3技术使在较小的存储空间内，存储大量的音频数据成为可能：一张CD唱盘存储的音乐与一盒卡带差不多，若用MP3格式来存储，则可存上百首。播放MP3流行的软件有很多，最流行的播放器要算是是WINAMP。我们自己也可以制作MP3。在超级解霸中提供了一个CD压缩工具，用它可以将CD音轨直接转换成MP3音乐。此外比如：WinPlay等。编码理论（实例）编码理论（实例）第43页，共86页，编辑于2022年，星期四而信道就是信源的通路，信道编码就相当于压缩饼干的运输方式，用飞机、

18、汽车、火车都可以将饼干从厂家运送到消费者手中，但选择何种运输方式就相当于采用哪种信道编码标准，目的地一致，但在成本和效率上会有各种差别。编码理论（实例）编码理论（实例）第44页，共86页，编辑于2022年，星期四由此可见，信源编码是由此可见，信源编码是数字电视数字电视的基础，离开的基础，离开了信源编码去谈信道编码就是无源之水、无本了信源编码去谈信道编码就是无源之水、无本之木。之木。编码理论（实例）编码理论（实例）第45页，共86页，编辑于2022年，星期四编码理论（实例）编码理论（实例）数字电视数字电视就是指从演播室到发射、传输、接收的所有环节都是使用数字电视数字电视信号或对该系统所有的信号传

19、播都是通过由0、1数字串所构成的数字流来传播的，数字信号的传播速率是每秒19.39兆字节，如此大的数据流的传递保证了数字电视数字电视的高清晰度，克服了模拟电视的先天不足。同时还由于数字电视数字电视可以允许几种制式信号的同时存在，每个数字频道下又可分为几个子频道，从而既可以用一个大数据流-每秒19.39兆字节，也可将其分为几个分流：第46页，共86页，编辑于2022年，星期四编码理论（实例）编码理论（实例）例如4个，每个的速度就是每秒4.85兆字节，这样虽然图像的清晰度要大打折扣，却可大大增加信息的种类，满足不同的需求。例如在转播一场体育比赛时，观众需要高清晰度的图像，电视台就应采用每秒19.3

20、9兆字节的传播；而在进行新闻广播时，观众注意的是新闻内容而不是播音员的形象，所以没必要采用那么高的清晰度，这时只需每秒3兆字节的速度就可以了，剩下16.39兆字节可用来传输别的内容。第47页，共86页，编辑于2022年，星期四以视频为例：以视频为例：视频能够压缩的根本原因在于视频数据具有较高的冗余度，压缩就是指冗余的消除，主要基于两种技术：统计学和心理视觉。编码理论（实例）编码理论（实例）第48页，共86页，编辑于2022年，星期四消除统计冗余的基本依据是视频数字化过程在时间和空间上采用了规则的采样过程。视频画面数字化为规则的像素阵列，其密集程度适于表征每点最高的空间频率，而绝大多数画面帧包含

21、非常少甚至不含这种最高频率的细节。同样，所选的帧频能够表征场景中最快的运动，而理想的压缩系统只要描述场景所必需的瞬时运动即可。编码理论（实例）编码理论（实例）第49页，共86页，编辑于2022年，星期四简言之，理想的压缩系统能够动态适应视频在时间和空间上的变化，所需要的数据量远低于数字化采样所产生的原始数据。编码理论（实例）编码理论（实例）第50页，共86页，编辑于2022年，星期四 压缩效果的评价标准有主观评价和客观评价两压缩效果的评价标准有主观评价和客观评价两种种，各有优缺点。n主观评判是聘请专门的评价人员来比较压缩之后再恢复的视听效果和原始效果的差异，通常是在专门的视听环境中按照一定的规

22、则进行主观评分。客观评判则是通过一种具体的算法来统计多媒体数据压缩结果的损失，例如信噪比SNR（即信号与噪声之比的对数）。编码理论（实例）编码理论（实例）第51页，共86页，编辑于2022年，星期四 主观评判和客观评判有时相差很大，因此衡量一个算法的好坏就需要在这二者之间找到一个平衡点。对一套标准的评价，通常开发过程中采用客观评价的方法，但最终要得到主观评价的确认。编码理论（实例）编码理论（实例）第52页，共86页，编辑于2022年，星期四数据压缩和信源编码数据压缩和信源编码3.1 等长码等长码 3.2 变长编码变长编码 3.3 哈夫曼码哈夫曼码 3.4 算术码算术码 香农香农-费诺码费诺码3

23、.5 通用信源编码通用信源编码 LZW算法算法习题三习题三 第53页，共86页，编辑于2022年，星期四对于统计特性已知的平稳信源，有Huffman码和算术码等高效编码方法.但是，它们存在以下共同问题：但是，它们存在以下共同问题：但是，它们存在以下共同问题：但是，它们存在以下共同问题：在编码时必须知道信源的概率分布，这在许多情况下在编码时必须知道信源的概率分布，这在许多情况下是不可能的；是不可能的；它们对无记忆信源较为合适，而实际应用中的信源一它们对无记忆信源较为合适，而实际应用中的信源一般都具有记忆性；因此如何利用信源的记忆性提高它的般都具有记忆性；因此如何利用信源的记忆性提高它的压缩率是信

24、源编码所必需考虑的问题压缩率是信源编码所必需考虑的问题.通用信源编码通用信源编码第54页，共86页，编辑于2022年，星期四1通用码的一般理论通用编码通用编码通用编码通用编码是指在信源概率分布不知时，对其编码并使编码效率很高的一种码.基本原理基本原理：利用出现数据序列前后的相关性进行压缩.通用信源编码通用信源编码第55页，共86页，编辑于2022年，星期四常用的通用码：LZ码及其改进算法LZW码.LZ码是1977-1978年以色列研究人员J.Ziv&A.Lempel提出的，是一种基于字典的编码方法.1984年，T.A.Welch给出了LZ算法的实用修正形式，成为LZW算法.通用信源编码通用信源

25、编码第56页，共86页，编辑于2022年，星期四LZ码的基本算法：码的基本算法：将长度不同的符号串编成一个个新的短语(单词)，形成短语词典的索引表；它是一种分段编码，其短语词典是由前面已见到的文本分段来定义的.通用信源编码通用信源编码第57页，共86页，编辑于2022年，星期四LZ码的编码步骤：码的编码步骤：取第一个符号x作为第一段（单词），记为（0 0，x）；从第二个符号y起，分段时先查看是否与前面的短语相同（匹配）：若没有匹配的，记为（0 0，y）；若有匹配的符号，就找从该符号开始与之匹配的若有匹配的符号，就找从该符号开始与之匹配的最大长度最大长度L L，并使得匹配开始的距离，并使得匹配开

26、始的距离最近，记为最近，记为（1 1，L,）；通用信源编码通用信源编码匹配时长度优先考虑，距离次之！第58页，共86页，编辑于2022年，星期四例例1设x11=a0a0a2a3a1a1a0a0a0a3a2，求它的LZ码.解：对x1的LZ码为（0，a0）；对x2的LZ码为（1，1，1）;对x3的LZ码为（0，a2）；对x4的LZ码为（0，a3）;对x5的LZ码为（0，a1）；对x6的LZ码为（1，1，1）;对x7的LZ码为（1,2,6）；对x8不编码；对x9的LZ码为（1，1，1）;对x10的LZ码为（1，1，6）;对x11的LZ码为（1，1，8）;通用信源编码通用信源编码因此，它的因此，它的L

27、Z码为码为C=(0,a0),(1,1,1),第59页，共86页，编辑于2022年，星期四例例1设x11=a0a0a2a3a1a1a0a0a0a3a2，求它的LZ码.译码：由（0，a0）得到x1=a0,xn=a0；由（1，1，1）得到x2=a0,xn=a0a0 通用信源编码通用信源编码因为，它的因为，它的LZ码为码为C=(0,a0),(1,1,1),第60页，共86页，编辑于2022年，星期四常用的通用码：LZ码及其改进算法LZW码.LZ码是1977-1978年以色列研究人员J.Ziv&A.Lempel提出的，是一种基于字典的编码方法.1984年，T.A.Welch给出了LZ算法的实用修正形式，

28、成为LZW算法.LZW就是通过建立一个字符串表,用较短的代码来表示较长的字符串来实现压缩.LZW压缩算法是Unisys的专利,有效期到2003年.通用信源编码通用信源编码第61页，共86页，编辑于2022年，星期四LZW算法保留了LZ的自适应性能，压缩效率大致相同；成为计算机文件压缩的标准算法，已经实现成为Unix操作系统中的标准文件压缩程序和arc文件压缩程序.可将典型的ASCII文本文件压缩成原文件的一半，得到广泛的应用.通用信源编码通用信源编码手机存储备份,是ARC文件第62页，共86页，编辑于2022年，星期四LZW压缩有三个重要的对象：数据流(CharStream)、编码流(Code

29、Stream)和编译表(StringTable)。在编码时，数据流是输入对象（文本文件的数据序列），编码流就是输出对象（经过压缩运算的编码数据）；在解码时，编码流则是输入对象，数据流是输出对象；而编译表是在编码和解码时都须要用借助的对象。.通用信源编码通用信源编码第63页，共86页，编辑于2022年，星期四LZW压缩算法的基本原理：提取原始文本文件数据中的不同字符，基于这些字符创建一个编译表，然后用编译表中的字符的索引来替代原始文本文件数据中的相应字符，减少原始数据大小。看起来和调色板图象的实现原理差不多，但是应该注意到的是，我们这里的编译表不是事先创建好的，而是根据原始文件数据动态创建的，解

30、码时 还 要 从 已 编 码 的 数 据 中 还 原出原来的编译表.通用信源编码通用信源编码第64页，共86页，编辑于2022年，星期四LZW算法流程：1)初始化：将所有的单字符串放入串表；2)读第一个输入字符给前缀串3)Step:读下一个输入字符K;if没有这样的K(输入已穷尽)：码字()输出；结束。通用信源编码通用信源编码IfK已存在于串表中：K:=；repeatStep；elseK不在于串表中:码字()输出；K加进串表；K:=；repeatStep.第65页，共86页，编辑于2022年，星期四例子：ababcbababaaaaaaaLZW编码：a,b,c,ab,ba,abc,cb,bab

31、,baba,aa,aaa,aaaa通用信源编码通用信源编码第66页，共86页，编辑于2022年，星期四LZW码的编码步骤：码的编码步骤：取第一个符号x作为第一段（单词），记为（0 0，x）；从第二个符号y起，分段时先查看是否与前面的短语相同（匹配）：若没有匹配的，记为（0 0，y）；若有匹配的符号，并与若有匹配的符号，并与第第l个码字相同个码字相同，就再取紧，就再取紧跟后面的一个符号跟后面的一个符号z一起组成一个短语，以便与一起组成一个短语，以便与前面的短语不同，记为前面的短语不同，记为（l ，z）；通用信源编码通用信源编码第67页，共86页，编辑于2022年，星期四例例2设x11=a0a0a

32、2a3a1a1a0a0a0a3a2，求它的LZW码.解：对x1的LZW码为（0，a0）；对x2的LZW码为（1，a2）;对x3不编码；对x4的LZW码为（0，a3）;对x5的LZW码为（0，a1）；对x6的LZW码为（4，a0）;对x7不编码；对x8的LZW码为（1，a0）；对x9不编码;对x10的LZ码为（3，a2）;对x11不编码;通用信源编码通用信源编码因此，它的因此，它的LZ码为码为C=(0,a0),(1,a2),第68页，共86页，编辑于2022年，星期四LZW压缩的特点 LZW码能有效利用字符出现频率冗余度进行压缩，且字典是自适应生成的，但通常不能有效地利用位置冗余度。具体特点如下

33、：l)LZW压缩技术对于可预测性不大的数据具有较好的处理效果，常用于GIF格式的图像压缩，其平均压缩比在2:1以上，最高压缩比可达到3:1。通用信源编码通用信源编码第69页，共86页，编辑于2022年，星期四2)对于数据流中连续重复出现的字节和字串，LZW压缩技术具有很高的压缩比。3)除了用于图像数据处理以外，LZW压缩技术还被用于文本程序等数据压缩领域。4)LZW压缩技术有很多变体，例如常见的ARC、PKZIP高效压缩程序。5)对于任意宽度和像素位长度的图像，都具有稳定的压缩过程。压缩和解压缩速度较快。6)对机器硬件条件要求不高。通用信源编码通用信源编码第70页，共86页，编辑于2022年，

34、星期四习题习题若试构造它的LZW数据压缩编码.通用信源编码通用信源编码第71页，共86页，编辑于2022年，星期四通用信源编码通用信源编码第72页，共86页，编辑于2022年，星期四数据压缩和信源编码数据压缩和信源编码3.1 等长码等长码 3.2 变长编码变长编码 3.3 哈夫曼码哈夫曼码 3.4 算术码算术码 香农香农-费诺码费诺码3.5 通用信源编码通用信源编码 LZW算法算法习题三习题三 第73页，共86页，编辑于2022年，星期四1）(a)解：由长度满足Kraft不等式，可知利用该数集可以构造二进即时码.编码方法：任意选取长为1的码字：0；第74页，共86页，编辑于2022年，星期四3

35、）证明：最短码字“101”不是其他码的前缀；依次考查，码C3是C6的前缀，有可得，尾随后缀集合为0，011，0001，10100；由于该集合中没有码字，所以是唯一可译码.第75页，共86页，编辑于2022年，星期四5）提示：（a）进行哈夫曼编码；所得码：（b）平均码长：2.45bit;第76页，共86页，编辑于2022年，星期四6）提示：（a）进行哈夫曼编码；所得码：第77页，共86页，编辑于2022年，星期四7）注：编码效率R是衡量各种(D进)编码优劣的主要依据；在码率相同时，可以借助于码长的方差；第78页，共86页，编辑于2022年，星期四9）解：（a）对于三元Huffman码，要使短码得

36、到充分利用，必须信源符号个数q，满足q=（D-1）+D现在D=3，若=3时，q=9，所以需要加两个符号其概率为0.信源X的三元Huffman编码：第79页，共86页，编辑于2022年，星期四10）提示：n次扩展信源，即长为n的信源字母序列由于信源是离散无记忆的，所以第80页，共86页，编辑于2022年，星期四17）(a)(0,0),(1,1,1),(1,2,2),(0,1),(1,1,2),(1,2,3),(1,2,4),(1,4,5),(1,13,13),(1,4,6),(1,1,1)(b)第81页，共86页，编辑于2022年，星期四d)压缩率：码字个数码字个数信源字符集每个码字的最坏长度对

37、给定信源，是定值第82页，共86页，编辑于2022年，星期四采用霍夫曼码逼近信源的熵，必须知道全部信源符号的出现概率。但随着信源编码理论的发展，人们发现：即使没有任何信源统计特性的知识，也有可能设计出最佳的编码，即当码组长度趋干无穷时其性能收敛于依赖信源统计特性而设计的编码器性能。1973年L.D.Davisson把这种不需要知道信源统计特性的最佳信源编码理论，称之为通用编码(UniversalCoding)理论。通用信源编码通用信源编码第83页，共86页，编辑于2022年，星期四更广义地理解，一般认为除了确知概率特性的编码方法以外的其他编码方法，都可作为通用编码的一种。不依赖信源统计特性而得到的最佳码称为普适码或泛码(UniversalCode)。作为语法解析码的LZ码就是一类泛码。寻找更好更简便的泛码，仍是目前信源编码中很活跃的一个课题。通用信源编码通用信源编码第84页，共86页，编辑于2022年，星期四通用信源编码通用信源编码第85页，共86页，编辑于2022年，星期四LZW算法并未涉及字串表中串的优化选择，或输人数据的最佳解析，而是追求简单、有效、快速的实现，此时一个主要问题是串表的存储。在消息长度为1万字符的数量级时可得到令人满意的压缩效果。通用信源编码通用信源编码第86页，共86页，编辑于2022年，星期四