无失真信源编码

无失真信源编码包括香农编码、费诺编码、哈夫曼编码,常用的算法是变长编码算法。
展开查看详情

1.信息论与编码技术 第 5 章 无失真信源编码 苗付友 mfy@ustc.edu.cn 2016 年 9 月

2.5.1 香农编码 5.2 费诺编码 5.3 哈夫曼编码 5.4 常用的变长编码算法

3.3 5.1 香农编码 设有离散无记忆信源

4.4 1 2 3 4 香农编码方法的步骤 按信源符号的概率从大到小的顺序排队 不妨设

5.5 例 设有一单符号离散无记忆信源 试对该信源编二进制香农码。

6.6 编码过程 ( 1 )

7.7

8.5.2 费 诺编码 对概率按 m( 码符号数 ) 进行 分组,使每组 概率 尽可能相等 给每个分组分配一个码元 对每个分组重复 2 、 3 步,直到不可分为止 按信源符号的概率从大到小的顺序排队 不妨设 1 2 3 4

9.设有一单符号离散无记忆信源 试对该信源编二进制费诺码。 例

10.编码过程

11.11 可以看出本例中费诺码有较高的编码效率。 费诺码比较适合于每次分组概率都很接近的信源。

12.12 将信源符号按概率由大到小顺序排队 给两个概率最小的符号各分配一个码位,将其概率相加后合并作为一个新的符号,与剩下的符号一起,再重新排队 给缩减信源中概率最小的符号各分配一个码元 重复步骤 2 、 3 直至概率和为 1 5.3 哈夫曼编码 1 2 3 4

13.设有一单符号离散无记忆信源 试对该信源编二进制哈夫曼码。 例 定理: 哈夫曼编码一定是最佳即时码(紧致码), 即平均码长最小。

14.14 编码过程

15.15  

16.16

17.17 说明: Huffman 码的编码方法不是唯一的。首先,每 次对缩减信源两个最小的符号分配 “ 0 ” 和 “ 1 ” 码 元是任意 的,所以可得到不同的码字。只要在 各次缩减信源中保持码元分配的一致性,即能 得到唯一可译码。 不同的码元分配,得到的具体 码字不同,但码长,平均码长都不变,所以没有 本质区别。其次,若合并后的新符号的概率与其 他符号的概率相等,从编码的方法上来说,这几 个符号的次序可任意排列,编出的码都是正确的,但得到的码字不同。不同的编法得到的码字长度也不尽相同。

18.18 对信源进行缩减时,两个概率最小的符号合并后的概率与其它信源符号的概率相同时,这两者在缩减信源中进行概率排序,其位置放置次序是可以任意的,故会得到不同的哈夫曼码。此时将影响码字的长度,一般将 合并的概率放在上面 ,这样可获得 较小的码方差 。 如下面的例子

19.19 例 设有离散无记忆信源 用两种不同的方法对其编二进制 huffman 码

20.20 方法一 方法二

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 两种不同的编码方法得到的码字和码长的对比

22.22 平均码长和编码效率

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 的霍夫曼码 解:赋予码元