展开查看详情
1 .信息论与编码技术 第 5 章 无失真信源编码 苗付友 mfy@ustc.edu.cn 2016 年 9 月
2 .5.1 香农编码 5.2 费诺编码 5.3 哈夫曼编码 5.4 常用的变长编码算法
4 .4 1 2 3 4 香农编码方法的步骤 按信源符号的概率从大到小的顺序排队 不妨设
5 .5 例 设有一单符号离散无记忆信源 试对该信源编二进制香农码。
8 .5.2 费 诺编码 对概率按 m( 码符号数 ) 进行 分组，使每组 概率 尽可能相等 给每个分组分配一个码元 对每个分组重复 2 、 3 步，直到不可分为止 按信源符号的概率从大到小的顺序排队 不妨设 1 2 3 4
9 .设有一单符号离散无记忆信源 试对该信源编二进制费诺码。 例
11 .11 可以看出本例中费诺码有较高的编码效率。 费诺码比较适合于每次分组概率都很接近的信源。
12 .12 将信源符号按概率由大到小顺序排队 给两个概率最小的符号各分配一个码位，将其概率相加后合并作为一个新的符号，与剩下的符号一起，再重新排队 给缩减信源中概率最小的符号各分配一个码元 重复步骤 2 、 3 直至概率和为 1 5.3 哈夫曼编码 1 2 3 4
13 .设有一单符号离散无记忆信源 试对该信源编二进制哈夫曼码。 例 定理： 哈夫曼编码一定是最佳即时码（紧致码）， 即平均码长最小。
17 .17 说明： Huffman 码的编码方法不是唯一的。首先，每 次对缩减信源两个最小的符号分配 “ 0 ” 和 “ 1 ” 码 元是任意 的，所以可得到不同的码字。只要在 各次缩减信源中保持码元分配的一致性，即能 得到唯一可译码。 不同的码元分配，得到的具体 码字不同，但码长，平均码长都不变，所以没有 本质区别。其次，若合并后的新符号的概率与其 他符号的概率相等，从编码的方法上来说，这几 个符号的次序可任意排列，编出的码都是正确的，但得到的码字不同。不同的编法得到的码字长度也不尽相同。
18 .18 对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将 合并的概率放在上面 ，这样可获得 较小的码方差 。 如下面的例子
19 .19 例 设有离散无记忆信源 用两种不同的方法对其编二进制 huffman 码
21 .21 信源符号 x i 概率 p (x i ) 码字 W i1 码长 K i1 码字 W i2 码长 K’ i2 x 1 0.4 1 1 00 2 x 2 0.2 01 2 10 2 x 3 0.2 000 3 11 2 x 4 0.1 0010 4 010 3 x 5 0.1 0011 4 011 3 两种不同的编码方法得到的码字和码长的对比
23 .23 两种编码方法编出的码字的码长方差比较
24 .24 可以看出第二种编码方法的码长方差要小 许多。这意味着第二种编码方法的码长变 化较小，比较接近平均码长。由此可以得 到一个结论 ( 怎样得到码方差较小的 huffman 编码 ) 。
25 .25 结论： 进行哈夫曼 编码时，为得到 码方差 最小的码，应使合并的信源符号位于缩减信源序列 尽可能高的位置 上，以减少再次合并的次数，充分利用短码。
26 .26 5.4 常用的变长编码算法 最佳不等长编码 ( 最佳码 ) 对于给定的信源和码元符号集，在其所有的唯一可译码中，平均长度最小的码称为 最佳码 ，或 紧致码 。 字母集 : S ＝ { s 1 , s 2 ,…, s q }. 信源 X 的概率分布： p ( s i ) ( i =1,2,…, q ). 码元集 A ＝ { a 1 , a 2 ,…, a m }. 信源符号 s i 的码字 : w i = f ( s i ) 码字 w i 的长度为 l i ( i =1,2,…, q )
27 .27 5.4 常用的变长编码算法 习题 已知离散无记忆信源 X 为： 求二进制 费诺码，二进制霍夫曼码，三进制霍夫曼码。
28 .28 5.4 常用的变长编码算法 符号序列 概率分布 第 1 次分组 第 2 次分组 第 3 次分组 第 4 次分组 码字 码长 a 1 0.20 0 (0.57) 0 (0.2) 00 2 a 2 0.19 1 (0.37) 0 010 3 a 3 0.18 1 011 3 a 4 0.17 1 (0.43) 0 (0.17) 10 2 a 5 0.15 1 (0.26) 0 110 3 a 6 0.10 1 0(0.10) 1110 4 a 7 0.01 1(0.01) 1111 4
29 .29 5.4 常用的变长编码算法 习题 求以下信源 X 的霍夫曼码 解：赋予码元
热门城市
