进制哈夫曼编码.PPT

5.4 哈夫曼（Huffman）编码 二进制哈夫曼码的编码方法： (1)将信源消息符号按其出现的概率大小依次排列： 。 (2)取两个概率最小的符号分别配以0和1两个码元，并将这两个概率相加作为一个新符号的概率，与未分配二进制码元的符号重新排队。 * * 5.4 哈夫曼（Huffman）编码 (3)对重排后的两个概率最小符号重复步骤(2)的过程。 (4)不断继续上述过程，直到最后两个符号配以0和1为止。 (5)从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。 * * 5.4 哈夫曼（Huffman）编码（例１） 例：对以下信源进行哈夫曼编码。 P166习题5.3 信源符号ai 概率p(ai) 码字Wi 码长Ki a1 0.20 10 2 a2 0.19 11 2 a3 0.18 000 3 a4 0.17 001 3 a5 0.15 010 3 a6 0.10 0110 4 a7 0.01 0111 4 * * 5.4 哈夫曼（Huffman）编码（例１续） 0.20 0.20 0.26 0.35 0.39 0.61 1.0 0.19 0.19 0.20 0.26 0.35 0.39 0.18 0.18 0.19 0.20 0.26 0.17 0.17 0.18 0.19 0.15 0.15 0.17 0.10 0.11 0.01 0 1 0 1 0 1 0 1 0 1 0 1 * * 5.4 哈夫曼（Huffman）编码（例１续） * * 5.4 哈夫曼（Huffman）编码 哈夫曼编码方法得到的码并非唯一的。 每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。 对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。 需要大量的存储设备来缓冲码字长度的差异，这是码方差小的码质量好的原因。 * * 5.4 哈夫曼（Huffman）编码（例2） 例：对以下离散无记忆信源进行两种哈夫曼编码。(例5.1.6) 信源 符号ai 概率p(ai) 码字Wi1 码长Ki1 码字Wi2 码长Ki2 a1 0.4 1 1 00 2 a2 0.2 01 2 10 2 a3 0.2 000 3 11 2 a4 0.1 0010 4 010 3 a5 0.1 0011 4 011 3 * * 5.4 哈夫曼（Huffman）编码（例2续） 第一种方法　　　　　第二种方法 0.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.4 0.2 0.2 0.2 0.1 0.2 0.1 0.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.4 0.2 0.2 0.2 0.1 0.2 0.1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 码字 １ 01 000 0010 0011 00 10 11 010 011 * * 5.4 哈夫曼（Huffman）编码（例2续） 第一种方法码树图　　　　　　　　　　　　　　第二种方法码树图　　 * * 5.4 哈夫曼（Huffman）编码（例2续） * * 5.4 哈夫曼（Huffman）编码 进行哈夫曼编码时，为得到码方差最小的码，应使合并的信源符号位于缩减信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码。 哈夫曼码是用概率匹配方法进行信源编码。它有两个明显特点：一是哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；二是缩减信源的最后两个码字总是最后一位不同，保证了哈