2.8无失真信源编码.ppt

(2) 采用两次扩展的范诺编码 每对消息的平均码长 单个消息的平均码长 码字 0 0 0 1 1 1 1 0 1 1 0 1 1 1 0 1 0 1 1 0 1 码长 2 3 3 2 3 4 4 AB BA BC CB BB AC CA 消息 3 3 3 3 2 1 1 概率 解 编码效率 * 第二章 基本信息论 §2.8 无失真信源编码(二) §2.8 无失真信源编码(二) 五、编码的一般原则 六、范诺(Fano)编码 七、霍夫曼(Huffman)编码 八、N 次扩展编码 五、编码的一般原则 1. 等概化 使编码后各个码元出现的概率尽可能地相等。 2. 减少平均码长 将概率大的消息编成短码，概率小的消息编成长码。 3. 消息合并 将两个或者两个以上的消息编成一个码字。 目的 去相关性； 减少平均码长。 六、范诺(Fano)编码 1. 方法及步骤 (1) 将消息符号按其概率从大到小排列。 (2) 将排列好消息符号分为概率尽可能相等的两组， (3) 将每次所分的两组中前一组编为0，前一组编为1。 (4) 按顺序写出码字。 每个组只剩下一个消息符号为止。 对每组 直至 的消息符号再分为概率尽可能相等的两组， …… ， 码字 0 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 0 1 0 0 1 1 0 1 0 1 码长 2 2 3 3 4 4 4 4 A B C D E F G H X 4 4 2 2 1 1 1 1 p(x) 解 1/4 B 1/8 C 1/8 D 1/4 A 1/16 E 1/16 p(x) F X 求其范诺编码及编码效率。 例 设消息的概率分布如下， 1/16 G 1/16 H 编码效率 平均码长 熵 ( bi t ), 解 码树图生成过程 G H A B C D E F 0 1 0 1 0 1 0 1 0 1 0 1 0 1 从 上 到 下 生 成 1/4 B 1/8 C 1/8 D 1/4 A 1/16 E 1/16 p(x) F X 求其范诺编码及编码效率。 例 设消息的概率分布如下， 1/16 G 1/16 H 码字 0 0 1 1 1 1 0 1 0 1 1 1 0 1 1 0 1 码长 2 2 2 3 4 4 A B C D E F X 32 22 18 16 8 4 p(x) 解 0.22 B 0.18 C 0.16 D 0.32 A 0.08 E 0.04 p(x) F X 求其范诺编码及编码效率。 例 设消息的概率分布如下， 编码效率 平均码长 熵 ( bi t ), 解 码树图生成过程 E F A B 0 1 0 1 0 1 0 1 0 1 从 上 到 下 生 成 0.22 B 0.18 C 0.16 D 0.32 A 0.08 E 0.04 p(x) F X 求其范诺编码及编码效率。 例 设消息的概率分布如下， C D 码字 0 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 0 1 1 1 0 1 1 码长 2 3 3 2 3 4 5 5 A B C D E F G H X 熵 解 编码效率 平均码长 范诺编码有时会出现 0.20 B 0.16 C 0.15 D 0.21 A 0.14 E 0.08 p(x) F X 求其范诺编码及编码效率。 例 设消息的概率分布如下， 0.03 G 0.03 H 概率相对较小的消息 其码长反而较短。 21 20 16 15 14 8 3 3 p(x) 0 1 2. 分组问题的探讨 六、范诺(Fano)编码 通常情况下，不能保证使所分的两组的概率完全相等， 此时就会出现两种不同的分组方案。 比如： A B C D E F G H 下面通过几个例子来探讨一下范诺编码分组问题， 从而能发现范诺编码的主要不足之处。 码字 0 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 0 1 0 1 1 1 0 1 1 码长 2 2 3 3 3 4 5 5 A B C D E F G H X 28 16 12 11 11 11 5.5 5.5 p(x) 熵 解一 0.055 H 0.16 B 0.12 C 0.11 D 0.28 A 0.11 E 0.11 p(x) F X 求其范诺编码及编码效率。 例 设消息的概率分布如下， 0.055 G 编码效率 平均码长 0.44 0.56 0 1 0.56 0.44 解一 0.055 H A B C D E F G H 28 16 12 11 11 11 5.5 5.5 p(x) 码字 0 0 0 1 1 1 1 1 0 1 1 0 0