本_信息论与编码A_第4章无失真信源编码.ppt

* 4.3 变长编码 符号序列 概率分布 码字 a0 a0 9/16 0 a0 a1 3/16 10 a1 a0 3/16 110 a1 a2 1/16 111 例4-5 设二元离散无记忆信源X的符号集为{a0, a1}, 概率分布为：p0=0.75, p1=0.25, 则 H(X)= ?0.75log0.75 ?0.25log0.25=0.811. 如对信源符号X直接进行编码: a0?0, a1?1, 则 如对两个信源符号X2进行编码, 则有 * 第4章 无失真信源编码 4.1 无失真信源编码的概念 4.2 等长编码 4.3 变长编码 4.4 常用的变长编码算法 * 4.4 常用的变长编码算法 最佳不等长编码(最佳码) 对于给定的信源和码元符号集，在其所有的唯一可译码中，平均长度最小的码称为最佳码，或紧致码。 字母集: S＝{s1, s2,…,sq}. 信源X的概率分布：p(si) (i=1,2,…,q ). 码元集A＝{a1, a2,…,am}. 信源符号si的码字: wi=f(si) 码字wi的长度为li (i=1,2,…,q ) * 4.4 常用的变长编码算法 费诺(Fano)编码 (1) 将信源符号按其出现概率从大到小排列: p1? p2…?pq. (2) 依次将信源符号分成两组，使其每组中符号的概率和尽量相等，分别对给各组赋予码元“0”和“1” . (3) 对各分组重复(2), 直至每个分组只剩一个符号 (5) 从左向右依次写出每个符号的码元序列，即得相应的码字. 所得的码称为费诺码. * 4.4 常用的变长编码算法 例4.6 已知离散无记忆信源X为： 求费诺码. 符号序列 概率分布 第1次分组 第2次分组 第3次分组 第4次分组 码字 码长 a1 0.20 0 (0.57) 0 (0.2) 00 2 a2 0.19 1 (0.37) 0 010 3 a3 0.18 1 011 3 a4 0.17 1 (0.43) 0 (0.17) 10 2 a5 0.15 1 (0.26) 0 110 3 a6 0.10 1 0(0.10) 1110 4 a7 0.01 1(0.01) 1111 4 * 4.4 常用的变长编码算法 例4.6 信源X的熵: H(X)=2.61 * 4.4 常用的变长编码算法 霍夫曼(Huffman)编码 (1) 将信源符号按其出现概率从大到小排列: p1? p2…?pq. (2) 对概率最小的两个信源符号赋予码元“0”和“1”，并将二个概率相加作为一个新字母的概率，与未编码的符号重新排序. (3) 对重新排序的符号执行(2). (4) 重复(2), (3), 直至每个符号均已赋予码元. (5) 从最后一级开始，依次向前写出每个符号码元序列，即得相应符号的码字. 所得的码称为霍夫曼码. * 4.4 常用的变长编码算法 例4.7 求以下信源X的霍夫曼码 解：赋予码元 * 4.4 常用的变长编码算法 解：写出码字 * 4.4 常用的变长编码算法 例4.8 求以下信源X的三元霍夫曼码 * 4.4 常用的变长编码算法 霍夫曼码是最佳、即时码 霍夫曼码不唯一 例4.9 已知离散无记忆信源X如下，求其霍夫曼码 解：霍夫曼码1 * 4.4 常用的变长编码算法 解：霍夫曼码2 霍夫曼码2方差较小，质量更好！ 应使用霍夫曼码2！ * 4.4 常用的变长编码算法 符号序列 概率分布 1 2 3 码字 码长 a0 a0 9/16 9/16 9/16 0 1 0 1 a0 a1 3/16 4/16 0 1 7/16 11 2 a1 a0 3/16 0 1 3/16 100 3 a1 a1 1/16 101 3 例4.10 设二元离散无记忆信源X的符号集为{a0, a1}, 概率分布为：p0=0.75, p1=0.25, 则 H(X)= ?0.75log0.75 ?0.25log0.25=0.811. 对两个信源符号X2进行编码, 则有 * 4.4 常用的变长编码算法 例4.10 对三个信源符号X3进行编码 * 4.4 常用的变长编码算法 课堂练习 已知离散信源X如下，求其二元费诺码。并求其平均码长与编码效率。 已知离散无记忆信源X如下，求其三元霍夫曼码。并求其平均码长与编码效率。 * 4.4 常用的变长编码算法 LZ码 1977年，齐费(J. Ziv