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