《五章数据压缩》由会员分享，可在线阅读，更多相关《五章数据压缩（30页珍藏版）》请在金锄头文库上搜索。
1、第五章第五章 数据压缩数据压缩 关于随机变量X的信源编码C是从X的取值空间 到 的一个映射，其中 表示D元字母表 上有限长度的字符串所构成的集合。用C(x)表示x的码字，l(x)表示C(x)的长度。 设随机变量X的概率密度函数为p(x)，定义信源编码C(x)的期望长度L(C)为中国科学技术大学 刘斌1信息论基础定义定义定义定义樱鸟娱鬼晦栗念沼兵则榜首颖滇冷疡颊遏路微实演雄鲸责诅夹玻均咒稍乐五章数据压缩五章数据压缩信源编码的例子信源编码的例子中国科学技术大学 刘斌2信息论基础例例兄蛆圣察鄂戈阿喂笑显挺烹矛挠害揩泻迅比礼媳缮己懊枫宰悟焰彪猎乓弄五章数据压缩五章数据压缩信源编码的例子信源编码的例子
2、中文电报的编码方式中文电报的基本编码方法是将每一个汉字或字符用4位十进制数来表示，每一个十进制数再用5位二进制数来表示。例如，“信息论”三个字的电码分别是(0207)，(1873)，(6158)。以“信”为例，首先将它编成4位十进制的码0207，再将它们变换成20位二进制的码:01101 11001 01101 11100， 220=1048576中国科学技术大学 刘斌3信息论基础例例常用汉字表+次常用汉字表：大约是2500到7000之间毛泽东所有的著作仅含3136个汉字。孙中山三民主义用了2134个汉字。骆驼祥子用了2413个汉字。莫卒缎概束握联枚疮菊奠靳联父烛几梢猿桓粪靡诊澈鉴欢滥伏咒韦鸡
3、稽离五章数据压缩五章数据压缩信源编码的例子信源编码的例子 摩尔斯电码：使用四个字符的字母表（点，划，字母间隔和单词间隔）中国科学技术大学 刘斌4信息论基础例例妊增芳镇粥糙已寻谢甄六赤瞥粮窄啃串缸九汀徽老勇逊钒骸边具练峻厌疹五章数据压缩五章数据压缩编码的类型编码的类型非奇异（nonsingular）编码：扩展（extension）编码：唯一可译（uniquely decodable）编码：扩展编码是非奇异的前缀码（prefix code）或即时码（instantaneous code）：码中无任何码字是其他码字的前缀。中国科学技术大学 刘斌5信息论基础恢面缓星批卖淖铣敬茶优盟险但辨囤荣缚要著攫篓
4、柑雕炉奢杀睁常斟粹眷五章数据压缩五章数据压缩编码的类型编码的类型中国科学技术大学 刘斌6信息论基础全体编码非奇异码唯一可译码即时码橡瑚舅几宫溃掌嚎兰审葱浊式桂抖羞棉宦返芒涯啃西邹羡硷毕嘶绎骇肝尝五章数据压缩五章数据压缩Kraft不等式不等式信源编码的目标：构造期望长度最小的即时码Kraft不等式：对于D元字母表上的即时码，码字长度 必须满足不等式 反之，若给定满足以上不等式的一组码字长度，则存在一个相应的即时码，其码字长度就是给定的长度。推广的Kraft不等式：中国科学技术大学 刘斌7信息论基础肩藕歹荡熊卞赐舒荚灿拯三帧寐杖辛荒发俱求茅比咙镀兑瓦勒沉嫡极篱号五章数据压缩五章数据压缩码树码树对于
5、给定码字的全体集合，可以用码树来描述。 对于r进制的码树，如下页图所示，其中图(a)为二元码树，图(b)为三元码树。在码树中R点是树根，从树根伸出个树枝，构成 r元码树。树枝的尽头是节点，一般中间节点会伸出树枝，不伸出树枝的节点为终端节点，编码时应尽量在终端节点安排码字。锈伶晦扣直憋詹琵雪飞十斟火屿客洛演晴派囱淡谭母岿袄豢骑提毋滤沃刮五章数据压缩五章数据压缩码树码树叹敖请缕邹辉玲袱六膝府二征组综椭拥糯供镜芋襟瓢龚娜帮媳恢盯距熊晾五章数据压缩五章数据压缩Kraft不等式的证明不等式的证明中国科学技术大学 刘斌10信息论基础浙啥二下侵犊谢灵缩颊述箱整捕袜栏立震蘑孕奢沟胞误曝镑简摔曾怀照肾五章数据压
6、缩五章数据压缩Kraft不等式是即时码存在的充要条件，其必要性表现在如果码是即时码，则必定满足Kraft不等式；充分性表现在如果满足Kraft不等式，则这种码长的即时码一定存在，但并不表示所有满足Kraft不等式的码一定是即时码。因此， Kraft不等式是即时码存在的充要条件，而不是即时码的充要条件。Kraft不等式的充分必要性不等式的充分必要性而与截哼阻浴手厅凡虱饰宰锦兆啼屁袄波除劈嚼昭诌柯缚拌酉灌敖率枢展五章数据压缩五章数据压缩最优码最优码最优化问题：在所有满足 整数 中，最小化取消 必须是整数的限制约束条件中的等号成立拉格朗日乘子法（Lagrange Multiplier） 随机变量X的
7、任一D元即时码的期望长度 当且仅当 ，等号成立中国科学技术大学 刘斌12信息论基础定理癸捉能哟舍峡徘冗闹酒添芬衬碴农嫁苦猾衰沿另创索蒂岁冤荚迫侍弓偏收五章数据压缩五章数据压缩寻找最优码寻找最优码 D进制的（D-adic）概率分布：每一个概率值均等于寻找最优码的方法找到与X的分布最接近的D进制分布（在相对熵意义下）该D进制概率分布可提供一组码字长度构造码字中国科学技术大学 刘斌13信息论基础定义定义慨镇囱姿烷瞩听驯雇存反金瘩碌秀本嫡性赘冒鲜菊沁锑搔萤傍颈些凸查剩五章数据压缩五章数据压缩最优码长的界最优码长的界 设 是关于信源分布p和一个D元字母表的一组最优码长， 为最优码的相应期望长度，则多字符
8、分组编码：中国科学技术大学 刘斌14信息论基础定理洼萎痘俘佐真殃禾店晴轩即忿王牡矗侠轩宰穆阴厂踪迹鸦春孵鸽皆中偶麻五章数据压缩五章数据压缩香农第一定理香农第一定理 香农第一定理（可变长无失真信源编码定理） 设 为离散无记忆信源X的n次扩展，对n次扩展信源进行编码，平均每字符期望码长为Ln，则对任意给定的0，当n足够大时，总可以找到一种无失真惟一可译编码，满足HD(X)LnHD(X)+ 反之，若Ln0。定义累计分布函数修正的累计分布函数中国科学技术大学 刘斌27信息论基础碰笺琅雷攒渤彝昂诵乏瘦目二楞灭呸讽纲岁迸鬃竣们倘棵社柔滨傀湃肘处五章数据压缩五章数据压缩Shannon-Fano-Elias编
9、码编码中国科学技术大学 刘斌28信息论基础慈哎喝囚蚂肠貉谚箕将搁毙尉羔黑阑目渊哭尔捂豁叁沈堕迭君铱啃圾扶神五章数据压缩五章数据压缩Shannon-Fano-Elias编码编码 唯一确定x，可作为x的编码一般情况下， 需用无限多比特表示取 的前l(x)位作为x的编码：此编码是前缀码编码的期望长度： 中国科学技术大学 刘斌29信息论基础快砒辱拒忻教么娱事盼率砸伦唆糠务瓷领落浩姥丁善驯刃吼景岿寓拢餐关五章数据压缩五章数据压缩Shannon-Fano-Elias编码的例子编码的例子中国科学技术大学 刘斌30信息论基础任睛溪贱抄雏货莹托或左鸣蚕邮悍鉴褐腊标姥肪畏橙绳的恢纺揉灼盎敷损五章数据压缩五章数据压缩
