五章数据压缩课件

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