《第五章数据压缩.ppt》由会员分享，可在线阅读，更多相关《第五章数据压缩.ppt（30页珍藏版）》请在三一文库上搜索。
1、第五章 数据压缩,关于随机变量X的信源编码C是从X的取值空间 到 的一个映射，其中 表示D元字母表 上有限长度的字符串所构成的集合。用C(x)表示x的码字，l(x)表示C(x)的长度。 设随机变量X的概率密度函数为p(x)，定义信源编码C(x)的期望长度L(C)为,中国科学技术大学 刘斌,1,信息论基础,定义,定义,信源编码的例子,中国科学技术大学 刘斌,2,信息论基础,例,信源编码的例子,中文电报的编码方式 中文电报的基本编码方法是将每一个汉字或字符用4位十进制数来表示，每一个十进制数再用5位二进制数来表示。 例如，“信息论”三个字的电码分别是(0207)，(1873)，(6158)。以“信
2、”为例，首先将它编成4位十进制的码0207，再将它们变换成20位二进制的码:01101 11001 01101 11100， 220=1048576,中国科学技术大学 刘斌,3,信息论基础,例,常用汉字表+次常用汉字表：大约是2500到7000之间 毛泽东所有的著作仅含3136个汉字。孙中山三民主义用了2134个汉字。骆驼祥子用了2413个汉字。,信源编码的例子,摩尔斯电码：使用四个字符的字母表（点，划，字母间隔和单词间隔）,中国科学技术大学 刘斌,4,信息论基础,例,编码的类型,非奇异（nonsingular）编码： 扩展（extension）编码： 唯一可译（uniquely decoda
3、ble）编码：扩展编码是非奇异的 前缀码（prefix code）或即时码（instantaneous code）：码中无任何码字是其他码字的前缀。,中国科学技术大学 刘斌,5,信息论基础,编码的类型,中国科学技术大学 刘斌,6,信息论基础,Kraft不等式,信源编码的目标：构造期望长度最小的即时码 Kraft不等式：对于D元字母表上的即时码，码字长度 必须满足不等式 反之，若给定满足以上不等式的一组码字长度，则存在一个相应的即时码，其码字长度就是给定的长度。 推广的Kraft不等式：,中国科学技术大学 刘斌,7,信息论基础,码树,对于给定码字的全体集合，可以用码树来描述。 对于r进制的码树，
4、如下页图所示，其中图(a)为二元码树，图(b)为三元码树。在码树中R点是树根，从树根伸出个树枝，构成 r元码树。树枝的尽头是节点，一般中间节点会伸出树枝，不伸出树枝的节点为终端节点，编码时应尽量在终端节点安排码字。,码树,Kraft不等式的证明,中国科学技术大学 刘斌,10,信息论基础,Kraft不等式是即时码存在的充要条件，其必要性表现在如果码是即时码，则必定满足Kraft不等式；充分性表现在如果满足Kraft不等式，则这种码长的即时码一定存在，但并不表示所有满足Kraft不等式的码一定是即时码。 因此， Kraft不等式是即时码存在的充要条件，而不是即时码的充要条件。,Kraft不等式的充
5、分必要性,最优码,最优化问题：在所有满足 整数 中，最小化 取消 必须是整数的限制 约束条件中的等号成立 拉格朗日乘子法（Lagrange Multiplier） 随机变量X的任一D元即时码的期望长度 当且仅当 ，等号成立,中国科学技术大学 刘斌,12,信息论基础,定理,寻找最优码,D进制的（D-adic）概率分布：每一个概率值均等于 寻找最优码的方法 找到与X的分布最接近的D进制分布（在相对熵意义下） 该D进制概率分布可提供一组码字长度 构造码字,中国科学技术大学 刘斌,13,信息论基础,定义,最优码长的界,设 是关于信源分布p和一个D元字母表的一组最优码长， 为最优码的相应期望长度，则 多
6、字符分组编码：,中国科学技术大学 刘斌,14,信息论基础,定理,香农第一定理,香农第一定理（可变长无失真信源编码定理） 设 为离散无记忆信源X的n次扩展，对n次扩展信源进行编码，平均每字符期望码长为Ln，则对任意给定的0，当n足够大时，总可以找到一种无失真惟一可译编码，满足 HD(X)LnHD(X)+ 反之，若LnHD(X)，则信源编码不可能无失真。,中国科学技术大学 刘斌,15,信息论基础,定理,不正确分布引起的误差,码字长度分配 关于p(x)的期望码长满足,中国科学技术大学 刘斌,16,信息论基础,定理,例,构造最优即时码,中国科学技术大学 刘斌,17,信息论基础,赫夫曼码,中国科学技术大
7、学 刘斌,18,信息论基础,例,赫夫曼码,中国科学技术大学 刘斌,19,信息论基础,例,赫夫曼码,中国科学技术大学 刘斌,20,信息论基础,例,赫夫曼码,中国科学技术大学 刘斌,21,信息论基础,例,赫夫曼码的讨论,加权码字的赫夫曼编码：赫夫曼算法最小化的是码长加权和,中国科学技术大学 刘斌,22,信息论基础,赫夫曼码的讨论,赫夫曼编码和香农码（码字长度 ） 从平均意义上讲，赫夫曼编码具有更短的期望长度，但两者的差别不超过1比特 对于单个字符来说，香农码可能具有比赫夫曼码更短的码字长度,中国科学技术大学 刘斌,23,信息论基础,赫夫曼码的最优性,对任意一个分布，必然存在满足如下性质的一个最优即
8、时码： 其长度序列与按概率分布排列的次序相反 最长的两个码字具有相同长度 最长的两个码字仅在最后一位上有所差别，且对应与两个最小可能发生的字符 满足以上定理得最优码称为典则码 赫夫曼码是最优的，它提供了最短的期望码长,中国科学技术大学 刘斌,24,信息论基础,定理,定理,赫夫曼码的最优性,中国科学技术大学 刘斌,25,信息论基础,赫夫曼码的最优性,中国科学技术大学 刘斌,26,信息论基础,Shannon-Fano-Elias编码,累计分布函数：假定取 ，并对所有x，有p(x)0。定义累计分布函数 修正的累计分布函数,中国科学技术大学 刘斌,27,信息论基础,Shannon-Fano-Elias编码,中国科学技术大学 刘斌,28,信息论基础,Shannon-Fano-Elias编码,唯一确定x，可作为x的编码 一般情况下， 需用无限多比特表示 取 的前l(x)位作为x的编码： 此编码是前缀码 编码的期望长度：,中国科学技术大学 刘斌,29,信息论基础,Shannon-Fano-Elias编码的例子,中国科学技术大学 刘斌,30,信息论基础,