《信息论基础-数据压缩.ppt》由会员分享，可在线阅读，更多相关《信息论基础-数据压缩.ppt（99页珍藏版）》请在三一办公上搜索。
1、1,第3章 数据压缩和信源编码,最优码的实际构造！,2,数据压缩,“数据压缩”在汉英词典中的解释：data compression(A method of reducing the amount of memory required to store data by encoding it and minimizing redundancy.Compressed data takes less time to transmit,but more computation time to restore it to its original form when needed for process
2、ing.),3,数据压缩-作用,通俗地说，就是用最少的数码来表示信号。其作用是：能较快地传输各种信号，如传真、Modem通信等；在现有的通信干线并行开通更多的多媒体业务，如各种增值业务；紧缩数据存储容量，如CDROM、VCD和DVD等；降低发信机功率，这对于多媒体移动通信系统尤为重要。由此看来，通信时间、传输带宽、存储空间甚至发射能量，都可能成为数据压缩的对象。,4,数据压缩-目的,一、可以节省空间。二、可以减少对带宽的占用。JPEG压缩编码技术的基本原理：JPEG专家组开发了两种基本的压缩算法，一种是采用以离散余弦变换（DCT-DiscreteCosine Transform）为基础的有损压
3、缩算法，另一种是以空间线性预测技术（DPCM）为基础的无损压缩算法。现在应用得较多的是有损压缩算法。JPEG标准只处理单帧图像，而不必顾及到前后左右帧，将每帧图像作为基础进行处理，利用了空间压缩编码原理。,5,数据压缩-目的,一、可以节省空间。二、可以减少对带宽的占用。MPEG编码技术的基本原理：MPEG数字视频编码技术实质上是一种统计方法。在时间和空间方向上，视频列通常包含统计冗余度。MPEG压缩技术所依赖的 基本统计特性为像素之间(interpel)的相关性，这里包含这样一个设想：即在各连续帧之间存在简单的相关性平移运动。,6,数据压缩-类型,有损压缩和无损压缩（图片格式）有损压缩 有损压
4、缩可以减少图像在内存和磁盘中占用的空间，在屏幕上观看图像时，不会发现它对图像的外观产生太大的不利影响。因为人的眼睛对光线比较敏感，光线对景物的作用比颜色的作用更为重要，这就是有损压缩技术的基本依据。有损压缩的特点是保持颜色的逐渐变化，删除图像中颜色的突然变化。生物学中的大量实验证明，人类大脑会利用与附近最接近的颜色来填补所丢失的颜色。,7,数据压缩-类型,有损压缩和无损压缩（图片格式）有损压缩 例如，对于蓝色天空背景上的一朵白云，有损压缩的方法就是删除图像中景物边缘的某些颜色部分。当在屏幕上看这幅图时，大脑会利用在景物上看到的颜色填补所丢失的颜色部分。利用有损压缩技术，某些数据被有意地删除了，
5、而被取消的数据也不再恢复。无可否认，利用有损压缩技术可以大大地压缩文件的数据，但是会影响图像质量。如果使用了有损压缩的图像仅在屏幕上显示，可能对图像质量影响不太大，至少对于人类眼睛的识别程度来说区别不大。可是，如果要把一幅经过有损压缩技术处理的图像用高分辨率打印机打印出来，那么图像质量就会有明显的受损痕迹。,8,数据压缩-类型,有损压缩和无损压缩（图片格式）无损压缩 无损压缩的基本原理是相同的颜色信息只需保存一次。压缩图像的软件首先会确定图像中哪些区域是相同的，哪些是不同的。包括了重复数据的图像(如蓝天)就可以被压缩，只有蓝天的起始点和终结点需要被记录下来。但是蓝色可能还会有不同的深浅，天空有
6、时也可能被树木、山峰或其他的对象掩盖，这些就需要另外记录。从本质上看，无损压缩的方法可以删除一些重复数据，大大减少要在磁盘上保存的图像尺寸。,9,数据压缩-类型,有损压缩和无损压缩（图片格式）无损压缩 但是，无损压缩的方法并不能减少图像的内存占用量，这是因为，当从磁盘上读取图像时，软件又会把丢失的像素用适当的颜色信息填充进来。如果要减少图像占用内存的容量，就必须使用有损压缩方法。无损压缩方法的优点是能够比较好地保存图像的质量，但是相对来说这种方法的压缩率比较低。但是，如果需要把图像用高分辨率的打印机打印出来，最好还是使用无损压缩几乎所有的图像文件都采用各自简化的格式名作为文件扩展名。从扩展名就
7、可知道这幅图像是按什么格式存储的，应该用什么样的软件去读写等等。,10,数据压缩-概要,在计算机科学和信息论中，数据压缩或者信源编码是按照特定的编码机制用比未经编码少的数据位元（或者其它信息相关的单位）表示信息的过程。例如，如果我们将“compression”编码为“comp”那么这篇文章可以用较少的数据位表示。一种流行的压缩实例是许多计算机都在使用的ZIP 文件格式，它不仅仅提供了压缩的功能，而且还作为归档工具Archiver）使用，能够将许多文件存储到同一个文件中。,11,数据压缩-概要,对于任何形式的通信来说，只有当信息的发送方和接受方都能够理解编码机制的时候压缩数据通信才能够工作。例如
8、，只有当接受方知道这篇文章需要用英语字符解释的时候这篇文章才有意义。同样，只有当接受方知道编码方法的时候他才能够理解压缩数据。一些压缩算法利用了这个特性，在压缩过程中对数据进行加密，例如利用密码加密，以保证只有得到授权的一方才能正确地得到数据。,12,数据压缩-概要,数据压缩能够实现是因为多数现实世界的数据都有统计冗余。例如，字母“e”在英语中比字母“z”更加常用，字母“q”后面是“z”的可能性非常小。无损压缩算法通常利用利用了统计冗余，这样就能更加简练地、但仍然是完整地表示发送方的数据。如果允许一定程度的保真度损失，那么还可以实现进一步的压缩。例如，人们看图画或者电视画面的时候可能并不会注意
9、到一些细节并不完善。同样，两个音频录音采样序列可能听起来一样，但实际上并不完全一样。有损压缩算法在带来微小差别的情况下使用较少的位数表示图像、视频或者音频。,13,数据压缩-概要,由于可以帮助减少如硬盘空间与连接带宽这样的昂贵资源的消耗，所以压缩非常重要，然而压缩需要消耗信息处理资源，这也可能是费用昂贵的。所以数据压缩机制的设计需要在压缩能力、失真度、所需计算资源以及其它需要考虑的不同因素之间进行折衷。一些机制是可逆的，这样就可以恢复原始的数据，这种机制称为无损数据压缩；另外一些机制为了实现更高的压缩率允许一定程度的数据损失，这种机制称为有损数据压缩。,14,数据压缩-概要,然而，经常有一些文
10、件不能被无损数据压缩算法压缩，实际上对于不含可以辨别样式的数据任何压缩算法都不能压缩。试图压缩已经经过压缩的数据通常得到的结果实际上是扩展数据，试图压缩经过加密的数据通常也会得到这种结果。实际上，有损数据压缩也会最终达到不能工作的地步。我们来举一个极端的例子，压缩算法每次去掉文件最后一个字节，那么经过这个算法不断的压缩直至文件变空，压缩算法将不能继续工作。,15,数据压缩-应用,一种非常简单的压缩方法是行程长度编码，这种方法使用数据及数据长度这样简单的编码代替同样的连续数据，这是无损数据压缩的一个实例。这种方法经常用于办公计算机以更好地利用磁盘空间、或者更好地利用计算机网络中的带宽。对于电子表
11、格、文本、可执行文件等这样的符号数据来说，无损是一个非常关键的要求，因为除了一些有限的情况，大多数情况下即使是一个数据位的变化都是无法接受的。,16,数据压缩-应用,对于视频和音频数据，只要不损失数据的重要部分一定程度的质量下降是可以接受的。通过利用人类感知系统的局限，能够大幅度得节约存储空间并且得到的结果质量与原始数据质量相比并没有明显的差别。这些有损数据压缩方法通常需要在压缩速度、压缩数据大小以及质量损失这三者之间进行折衷。有损图像压缩用于数码相机中，大幅度地提高了存储能力，同时图像质量几乎没有降低。用于DVD的有损MPEG-2编解码视频压缩也实现了类似的功能。,17,数据压缩-应用,在有
12、损音频压缩中，心理声学的方法用来去除信号中听不见或者很难听见的成分。人类语音的压缩经常使用更加专业的技术，因此人们有时也将“语音压缩”或者“语音编码”作为一个独立的研究领域与“音频压缩”区分开来。不同的音频和语音压缩标准都属于音频编解码范畴。例如语音压缩用于因特网电话，而音频压缩被用于CD翻录并且使用 MP3 播放器解码。,18,数据压缩-理论,压缩的理论基础是信息论（它与算法信息论密切相关）以及率失真理论，这个领域的研究工作主要是由 Claude Shannon 奠定的，他在二十世纪四十年代末期及五十年代早期发表了这方面的基础性的论文。Doyle 和 Carlson 在2000年写道数据压缩
13、“是所有的工程领域最简单、最优美的设计理论之一”。密码学与编码理论也是密切相关的学科，数据压缩的思想与统计推断也有很深的渊源。,19,数据压缩-理论,许多无损数据压缩系统都可以看作是四步模型，有损数据压缩系统通常包含更多的步骤，例如它包括预测、频率变换以及量化。Lempel-Ziv（LZ）压缩方法是最流行的无损存储算法之一。DEFLATE是 LZ 的一个变体，它针对解压速度与压缩率进行了优化，虽然它的压缩速度可能非常缓慢，PKZIP、gzip 以及 PNG 都在使用EFLATE。LZW（Lempel-Ziv-Welch）是 Unisys 的专利，直到2003年6月专利到期限，这种方法用于 GI
14、F 图像。,20,数据压缩-理论,另外值得一提的是 LZR(LZ-Renau)方法，它是 Zip 方法的基础。LZ R方法使用基于表格的压缩模型，其中表格中的条目用重复的数据串替换。对于大多数的 LZ 方法来说，这个表格是从最初的输入数据动态生成的。这个表格经常采用霍夫曼编码维护（例如，SHRI、LZX）。目前一个性能良好基于 LZ 的编码机制是 LZX，它用于微软公司的 CAB 格式。,21,数据压缩-理论,最好的压缩工具将概率模型预测结果用于算术编码。算术编码由 Jorma Rissanen 发明，并且由 Witten、Neal 以及 Cleary 将它转变成一个实用的方法。这种方法能够实
15、现比众人皆知的哈夫曼算法更好的压缩，并且它本身非常适合于自适应数据压缩，自适应数据压缩的预测与上下文密切相关。算术编码已经用于二值图像压缩标准 JBIG、文档压缩标准 DejaVu。文本 输入系统 Dasher 是一个逆算术编码器。,有效输入信息文本的界面,22,数据压缩和信源编码,3.1 等长码 3.2 变长编码 3.3 哈夫曼码 3.4 算术码 香农-费诺码3.5 通用信源编码 LZW算法习题三,23,数据压缩和信源编码,信源编码定理（定理）设X1，X2为无记忆信源，服从共同分布p(x)，则 当码率 时，存在码率为R的编码，使得当n时，误差码率Pe0.,最优码的存在性,24,数据压缩和信源
16、编码,将信道编码和译码看成是信道的一部分，而突出信源编码；,25,数据压缩和信源编码,通过信源编码，用尽可能少的信道符号来表达信源，即对信源数据用最有效的表达方式表达，尽可能减少编码后的数据的剩余度；,26,数据压缩和信源编码,3.1 等长码 3.2 变长编码 3.3 哈夫曼码 3.4 算术码 香农-费诺码3.5 通用信源编码 LZW算法习题三,27,等长码,定义：设为信源字母表，=0,1,D-1为D进码元（码符号）集.映射f:nk(x1,xn)(u1,uk)等长编码；若k不唯一，则为变长编码.映射：k n称为相应的译码；称上述编码为D元码.,分组码,28,等长码,定义（续）：f(xn)=uk
17、称为码字，k为码长；R=k/nlogD称为f的编码速率，即码率；由f编出的所有码字的集合称为码字集：C=f(xn),xn n 若任一码字只能被唯一译成所对应的信源符号序列，称这类编码为唯一可译码.,又称信源的信息率-信源编码后平均每个码元载荷的最大信息量,29,等长码,1.若进行二元等长编码，则码字长至少为2；从而：熵H(X)=1.75;码率R=k/nlogD=2H(X).,30,等长码,2.若进行二元不等长编码.变长编码的平均码长：L=p(i)l(i)=1.75;熵H(X)=1.75;码率R=L/nlogD=H(X).,31,数据压缩和信源编码,3.1 等长码 3.2 变长编码 3.3 哈夫
18、曼码 3.4 算术码 香农-费诺码3.5 通用信源编码 LZW算法习题三,32,变长编码,该编码的平均码长L=1.5=R H(X);是否说明该码更加实用呢？考查：对收到的码字序列001001译码？,33,变长编码,必须要求编码是唯一可译的；这是变长码编码要满足的第一个要求！对于所编出的变长码，怎样才能说明它是否是唯一可译的？,34,变长编码,定义：前缀若一个码字与另一个码字的前面部分相同，则称其为另一码字的前缀；0，01；01，011,35,变长编码,定义：前缀若一个码字与另一个码字的前面部分相同，则称其为另一码字的前缀；0，01；01，011,36,变长编码,定义：前缀若一个码字与另一个码字
19、的前面部分相同，则称其为另一码字的前缀；0，01；01，011 其中，较长码的剩余部分称为较短码的 尾随后缀.,37,变长编码,如何确定一个变长编码的所有尾随后缀？步骤：考查码C中最短码字是否是其它码字的前缀若是，列出所有的尾随后缀，再考查这 些尾随后缀是否是其它码字的前缀；若不是，考查次长的码字.,38,变长编码,哪些码是否为唯一可译码？若是请说明；否则，请构造一个有二义的码字序列.,判定：尾随后缀集中没有码字！,39,变长编码,定义:若f 编出的码字集中，没有一个码字是其它码字的前缀，则称f 编出的码为即时码.即时码一定是唯一可译码，反之不然！,40,作业,P75 3)以及课堂练习.,41
20、,变长编码,码树图,即时码的树图构造法：给每个节点伸出的树枝从上向下标上码符号 0，1，而只对终结点安排码字：从根出发到终结点走过的路径所对应的码符号组成；中间节点不安排码字.,42,变长编码,0,0,0,0,0,0,1,1,1,1,1,1,1,码树图,43,用树的概念可导出即时码存在的条件，即各码字的长度li应符合克莱夫特不等式：定理 克莱夫特（Kraft，1949）不等式含m个码字，码长为 l1,l2,lm的D进码是一个即时码，则它满足Kraft不等式 反之，存在给定码长的即时码；,变长编码,该不等式对唯一可译码成立！,44,变长编码的平均码长：若信源，编码后的码子为，码长分别为，则平均码
21、长为：,变长编码,它是传输信源符号平均需用的码元数！,编码效率-衡量各种编码的优劣,45,变长信源编码问题就是 求使得给定信源平均码长最小的唯一可译的变长码.注意：Kraft不等式是一个存在定理，不是唯一可译码的判定定理.存在长度满足Kraft不等式的码不是即时码：,变长编码,最优码！,46,例1：考虑二元码C=0,11,100,110，|D|=2.可以验证其码字长度1，2，3，3满足Kraft不等式；但不是即时码，因为它不是唯一可译码.,变长编码,47,如何用Kraft不等式的证明过程构造即时码.例2.令U=0,1,2,且 l1=l2=1，l3=2，l4=l5=4，l6=5.可以证明他们满足
22、Kraft不等式；能够构造U上具有对应码字长度的即时 码：,变长编码,48,由li的取值得到：(a1,a2,a3,a4,a5)=(2,1,0,2,1);任取a1个长度为1的码元：0，1；任取a2个长度为2，并且不以已经出现的码字为 前缀的码元：20；任取a4个长度为4，的码元：2100，2101；任取a5个长度为5，的码元：21020.,变长编码,是即时码,49,在有些编码选择中，我们会面临一些最优选择的问题。比如下面这样的问题：我们要编码字符串“7F-0505-12345678-1234567AB”，使得编码结果序列最短。可使用的编码方案已给定，有两种选择：每个数字或字符对应一个定长码，比如
23、1-1001100，F-1010100 每两个连续数字可以对应一个定长码。比如12-1001100，23-1101100 注意，给定的编码方案里，上面两种情况下定长码均等长(例子中为长度为7)。这里，我们看到，如果要编码结果序列最短。就需要尽量多的使用第二个方案。,变长编码,50,这里有两种极限情况：比如ABECDDDEFG.FHE这样的字串只能按第一种方案进行,因为它没有连续数字出现.比如1234235345.32这样的字串,如果有偶数个数字的话,我们完全可以按第二种方案进行.那么既有字符,又有数字的情况,就有一个选择的问题,所以这里的问题就是我们如何识别可以使用第二个方案的字串。,变长编码
24、,51,作者 fineamy,变长编码,52,变长信源编码问题就是 求使得给定信源平均码长最小的唯一可译的变长码.但是满足Kraft不等式的码长集未必是最优的，即其平均码长未必是最小的！,变长编码,53,定理（最优码码长的下界估计）：随机变量X的任何D进即时码的平均码长L应满足，,变长编码,等号成立的充要条件,54,证明：记如果C是即时码，则根据Kraft不等式，有,变长编码,55,定义3.2.3 相对冗余度作业：P75 1),变长编码,56,定理（最优码码长的下界估计）：随机变量X的任何D进即时码的平均码长L应满足，,变长编码,等号成立的充要条件,对于出现概率大的信息符号，编以短字长的码,对
25、于出现概率小的信息符号编以长字长的码，如果码字长度严格按照符号概率的大小的相反顺序排列，则平均码字长一定小于按任何其他符号顺序排列方式得到的码字长度。,57,某地的 A 同学 要给另外一方 B 同学 传递信息,信息必须以二进制编码(即01编码)的方式传递.假设 A 传递给 B 的所有字符只有 a,b,c,d 四个,且不包含空格.一种显而易见的编码方法是:a-00;b-01;c-10;d-11;这样保证不会产生翻译错误的情况发生,而平均每个字符需要 2 个 Bit 的带宽.然而这种方法不是最优的;借助统计规律,就可以构造出保证不会产生错误,然而却能更省带宽的编码方式:,变长编码,58,给出一个例
26、子:假设 P(x=a)=1/2;P(x=b)=1/4;P(x=c)=1/8;P(x=d)=1/8;即对大量的信息作出统计后,发现 a 出现的频率最高,平均每两个字符中就出现一个 a;b 其次;c,d再次之.如此对a的编码进行 缩水 处理:a-1;b-01;c-001;d-000;这样仍然能保证不会译错,而且,平均每个字符需要 1*1/2+2*1/4+3*1/8+3*1/8=7/4=1.75 Bit这样就节省了宝贵的 0.25 Bit上述的编码方式称为 Huffman 编码,变长编码,59,数据压缩和信源编码,3.1 等长码 3.2 变长编码 3.3 哈夫曼码 3.4 算术码 香农-费诺码3.5
27、 通用信源编码 LZW算法习题三,60,数据压缩和信源编码,哈夫曼编码/译码器。设计一个哈夫曼编码/译码器程序，对一个文本文件中的字符进行哈夫曼编码，生成编码文件（压缩文件，后缀.cod）；反过来，可将一个压缩文件译码还原为一个文本文件(.txt)。http,61,数据压缩和信源编码,步骤：（1）输入一个待压缩的文本文件名，统计文本文件中各字符的个数作为权值，生成哈夫曼树；（2）将文本文件利用哈夫曼树进行编码，生成压缩文件（后缀名cod）（3）输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码；（4）显示指定的压缩文件和文本文件的内容。,62,数据压缩和信源编码,哈夫曼编码(Hu
28、ffman Coding)是可变长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称熵编码法），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。,63,数据压缩和信源编码,例如，在英
29、文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。,64,数据压缩和信源编码,哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用
30、短的位序列，而那些很少出现的符号，则用较长的位序列。作者：著述的鸭子非了 压缩1M数据少于100ms（P3处理器，主频1G）。,65,一、二进制哈夫曼编码1.步骤(1)信源符号按概率分布大小，以递减次序排列；(2)取两个最小的概率，分别赋以“0”,“1”;然后把这两个概率值相加，作为新概率值与其他概率重新排序(3)按重排概率值，重复(2),直到概率和达到1为止(4)由后向前排列码序，即得哈夫曼编码,哈夫曼（Huffman）码,66,2.例题 x1 0.4 x2 0.2 x3 0.2 x4 0.1 x5 0.1平均码长码方差12=E(li-L)2=p(xi)(li-L)2=1.36,X:p(x)
31、(0.4,0.2,0.2,0.1,0.1),（合并后概率下放）,哈夫曼（Huffman）码,01,1,000,0010,0011,67,方法一：合并后的新符号排在其它相同概率符号的后面；,哈夫曼（Huffman）码,68,3.上例00 x1 0.4 10 x2 0.211 x3 0.2010 x4 0.1011 x5 0.1,（合并后概率上放）,哈夫曼（Huffman）码,69,3.上例00 x1 0.4 10 x2 0.211 x3 0.2010 x4 0.1011 x5 0.1 平均码长 结论 码方差22=0.16 两法平均码长相同，故信息率R、冗余度相同；但码方差不同，码方差小要好.,（
32、合并后概率上放）,哈夫曼（Huffman）码,70,方法二：合并后的新符号排在其它相同概率符号的前面.,哈夫曼（Huffman）码,71,两种编码的平均码长是一样的，都是2.2，那一种更好呢，我们可以计算一下平均码长的方差。,定义码字长度的方差2：,哈夫曼（Huffman）码,72,可见：第二种编码方法的码长方差要小许多。意味着第二种编码方法的码长变化较小，比较接近于平均码长。第一种方法编出的5个码字有4种不同的码长；第二种方法编出的码长只有两种不同的码长；显然，第二种编码方法更简单、更容易实现，所以更好。结论：在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符
33、号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。,哈夫曼（Huffman）码,73,3.上例00 x1 0.4 10 x2 0.211 x3 0.2010 x4 0.1011 x5 0.1 平均码长 结论 码方差22=0.16 两法平均码长相同，故信息率R、冗余度相同；但码方差不同，码方差小要好.,（合并后概率上放）,哈夫曼（Huffman）码,74,定理：在变长编码中，若各码字长度严格按照所对应符号出现概率的大小逆序排列，则其平均长度为最小。结论：霍夫曼编码方法，它完全依据字符出现概率来构造平均长度最短的异字头码字，有时称之为最佳编码。,哈夫曼（Huffm
34、an）码,75,应该指出的是，由霍夫曼编码过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。此外，由于码长不等，还存在一个输入与输出的速率匹配问题。解决的办法是设置一定容量的缓冲寄存器。而随着微电子与计算技术的发展，霍夫曼编码已可做成单片IC，并成为许多国际标准中的主要技术内核之一。能够用较低的处理代价，来换取昂贵的通信开销，是完全值得的。,哈夫曼（Huffman）码,方差最小者最佳,76,应该指出的是，由霍夫曼编码过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。此外，由于码长不等，还存在一个输入与输出的速率匹配问题。解决的办法
35、是设置一定容量的缓冲寄存器。而随着微电子与计算技术的发展，霍夫曼编码已可做成单片IC，并成为许多国际标准中的主要技术内核之一。能够用较低的处理代价，来换取昂贵的通信开销，是完全值得的。,哈夫曼（Huffman）码,方差最小者最佳,77,哈夫曼（Huffman）码,4.例题X:p(x)(0.4,0.18,0.1,0.1,0.07,0.06,0.05,0.04),78,二、D进制哈夫曼编码1.编码步骤同二进制，但需注意两点：每次取最小的D个概率,分别赋以0,1,D-1；信源符号个数r必须满足：r=(D-1)+D.当r不满足时，在信源符号集中补充一些对应概率为0的符号.,哈夫曼（Huffman）码,
36、79,2.例题,某离散无记忆信源符号集a1,a2,a3,a4,a5,a6,a7,a8，已知所对应的概率，试对其进行四元编码！,哈夫曼（Huffman）码,有误！,80,解：其中D=4.若取=2可得大于9但与9最接近的正整数10，因此在编码是加入一个零概率符号.对其进行四元编码：,哈夫曼（Huffman）码,81,哈夫曼（Huffman）码,82,哈夫曼码考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩；哈夫曼码的编码方法都不惟一；哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，因此综合性较优.,哈夫曼（Huffman）码,83,Huf
37、fman码在具体实用时，设备较复杂.在编码器中需要增加缓冲寄存器，因为每个信源符号所对应的码符号长度不一，负责会造成输入和输出不能保持平衡.优点：提高编码效率；缺点：需要大量缓冲设备来存储这些变长码，然后再以恒定的码率进行传送；在传输的过程中如果出现了误码，容易引起错误扩散，所以要求有优质的信道。,哈夫曼（Huffman）码,84,作业：P 76 8),哈夫曼（Huffman）码,85,哈夫曼码为设计最优的唯一可译变长码提供了一种有效的方法！对单义代码有：定理不是说单义代码的平均码长L不能大于上限，只是说小于上限的单义代码总是存在的。现在考虑信息论中的一个更好的上限：,哈夫曼（Huffman）
38、码,86,定理(信源编码的基本定理).设:A一a1,a1,.,am;XKX=x1,x2,.,xn的延长;WKW=W1,W2,.,Wn的延长，其平均长度为l;P(wi)一P(xi)，P(W)一IIP(Wi)，i=1，,n;如果要求WK为单义代码，则，也叫做无失真编码的基本定理。它说明:如果我们把X延长后再对K元组(K为延长长度)进行编码，那么不必利用数据前后的关联，只要K足够大，则代表每消息单元X的平均符号个数l/K可以任意趋于下限。,哈夫曼（Huffman）码,87,它说明:如果我们把X延长后再对K元组(K为延长长度)进行编码，那么不必利用数据前后的关联，只要K足够大，则代表每消息单元X的平均
39、符号个数l/K可以任意趋于下限。有了最佳编码方法，我们就可以举一个简单例子来说明L/K趋于下限的情况：,哈夫曼（Huffman）码,88,【例】只有两种灰度的传真机，其输出信号非“白”即“黑”，故可令 X=x1.x2=白，黑至于它们的概率P(x1),P(x2)则视所传内容而定。假设对于某页文件，有P(x1)=0.9，P(x2)=0.3则当不考虑信号间的关联时，可求出该信源的一阶熵即编码下限为H(x)=一0.9 log 0.9一0.1 log0.1=0.469(bit/pel),哈夫曼（Huffman）码,89,此时W=0,1，无论采用定长编码还是最佳编码，平均码长L1=1 bit/pel，效率
40、只有 H(X)/L1=46.9%现在把X延长到X2，不利用信号前后的关联(或假定是离散无记忆信源)，则由图所示X2的最佳编码，知W2=0，10，110，1lW2的平均长度L2=0.81+0.09*2+0.09*3+0.01*3=1.29 bit/pel,哈夫曼（Huffman）码,90,哈夫曼（Huffman）码,91,W2的每一个元素代表两个消息单元，所以平均每一消息单元的符号(码元)个数是 L2/2=0.645 bit/pel显然已经比较靠近下限(0.469)，编码效率则提高到H(X)/(L2/2)=0.469/0.645=72.7%,哈夫曼（Huffman）码,92,现在把X延长到X3，
41、不利用信号前后的关联(或假定是离散无记忆信源)，则由图所示X3的最佳编码的平均长度L3=1.598 bit/pelL3/3=0.533 bit/pelH(X)/(L3/3)=88.0%,哈夫曼（Huffman）码,93,哈夫曼（Huffman）码,94,毫无疑问，如果信号继续有关联可供利用的话，继续延长，会使下限变得更小。至此，信源编码在理论上已经相当完满地解决了。现在简单归纳如下：如果给定消息单元集合X、符号集合A和X的概率分布P(X)，我们可以采用最佳编码，使代码W的平均长度L落在半区间 H(X)/logM,H(X)/logM+1 之内.如果把X延长至X，那么不必利用信号前后的关联意味着P
42、(X)能直接从P(X)得到，就可以使代表一个消息单元的符号个数Lk/K任意接近下限H(X)/logM;,哈夫曼（Huffman）码,95,如果把X延长至X，那么不必利用信号前后的关联意味着P(X)能直接从P(X)得到，就可以使代表一个消息单元的符号个数Lk/K任意接近下限H(X)/logM;如果利用延长信号X 的前后关联必须给出X 的概率分布P(X)，更可使下限减小.当然在具体实现时，还必须考虑到:如果将信号延长得过长，会使实际设备复杂到不合理的程度.,哈夫曼（Huffman）码,96,哈夫曼码也是译码的工具：,哈夫曼（Huffman）码,97,哈夫曼（Huffman）码,4.例题X:p(x)(0.4,0.18,0.1,0.1,0.07,0.06,0.05,0.04),98,哈夫曼（Huffman）码,4.例题 X:p(x)(0.4,0.18,0.1,0.1,0.07,0.06,0.05,0.04),若接收的字符串是：,0001,00010100101100011,00010100101100011,99,数据压缩和信源编码,3.1 等长码 3.2 变长编码 3.3 哈夫曼码 3.4 算术码 香农-费诺码3.5 通用信源编码 LZW算法习题三,
