五章数据压缩.pptVIP

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