信息论与编码3.ppt

【例3.18】 对给定的信源，用两种方法进行D = 2进制霍夫曼编码。 计算 M+r = D+m(D-1) 5+ r =2+ m（2-1） → r = 0 方法一：若概率之和与原信源中的某概率相等，将概率之和往上排，如图3-8所示。 方法二：若概率之和与原信源中的某概率相等，将概率之和往下排，如图3-9所示。 分别计算两种编码法的平均码长 和 ，均方差 和 ： 通过上面的例子可以看出，霍夫曼编码法的指导思想是：概率小的消息赋予较大的码长（重复赋予单码元），概率大的消息赋予较小的码长（重复的次数少）。 【例3.19】对给定的信源 ，进行D =3进制霍夫曼编码，编码结果如图3-10所示。 M+r = D+m(D-1) 6+ r =3+ m（3-1） r = 1，所以增加r =1个概率为0的信源消息。 [定理3.3]说明，只有满足 否则惟一可译码不存在。但平均码长 应该小于 ，这是按 应尽可能短的要求，这时得到的码是最佳码，其实 ，也能找到惟一可译码。 ，才能构成惟一可译码， 【例3.10】 信源 对信源进行二进制变长编码，D = 2，信源各消息概率恰好表示成D = 2的整数次幂，取码长等于其幂次，即取n1=1 n2=2 n3=3 n4=3对信源各消息编码，得到的码就是紧致码，下面计算RD。 （码元/符号） 因为信息传输率RD的值小于等于1，所以上述RD =1达到最大值， 得到的码集为紧致码。 （比特/码元时间） 【例3.11】 对下述信源进行二进制变长编码， 根据式(3-20)，即码长nm 应满足tm ? nm tm +1 ，tm是消息xm（m =1，2，3，4，5）的2次幂概率所对应的幂次，取{x1, x2 , x3 , x4 , x5 } 所对应的码字的码长分别为n1=3 n2 = 4 n3 = 2 n4=3 n5=2 ，计算出平均码长 熵 =2.228（比特/符号） 满足式(3-19) 则有 定理3.4 变长编码定理 (Shannon第一定理) 给定熵为H（X）的离散无记忆信源 ， 其L次扩展信源 的熵记为H（X）， 给定有D个元素的码符号集，对扩展信源进行编码，总可以找到一种惟一可译码，使码长 满足 (3-23) 记 为信源每个符号所对应的平均码字数，则式(3-23)为 （3-24） Shannon第一定理的物理意义在于：对信源进行编码，使编码后的码集中各码字尽可能等概分布，如果将这码集看成为一个新的信源，这时新信源所含信息量最大。 定义编码效率 (3-26) η是一个无量纲的数，一般情况下η1，在极限情况下η=1。 对于同一种信源，三种编码法中以香农编码法的编码效率最低，费诺编码法也不是一种最佳编码法，但用这种方法有时候也能找到紧致码。 一般情况下，霍夫曼编码法得到的平均码长 最短，即编码效率 最高。 3.4 变长码的编码方法 香农（Shannon）编码法 费诺(Fano)编码法 霍夫曼(Huffman)编码法 变长编码法： 3.4.1 香农编码法 二进制香农编码法其码长的取值范围: -log q (xm) ? nm -log q (xm) +1 （3-30） 记离散信源 ，给定有D个 元素的码符号集，对信源进行变长编码，将各消息概率q(xm) (m = 1, 2, …, M) 写成如下的形式： 取码长nm (m = 1, 2, …, M) 满足： tm ? nm tm +1