进制哈夫曼编码复习过程.ppt

《进制哈夫曼编码复习过程.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、进制哈夫曼编码5.4哈夫曼（Huffman）编码（例１）例：对以下信源进行哈夫曼编码。P166习题5.3信源符号ai概率p(ai)码字Wi码长Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.01011142021/10/525.4哈夫曼（Huffman）编码（例１续）0.200.200.260.350.390.611.00.190.190.200.260.350.390.180.180.190.200.260.170.170.180.190.150

2、.150.170.100.110.010101010101012021/10/535.4哈夫曼（Huffman）编码（例１续）2021/10/545.4哈夫曼（Huffman）编码哈夫曼编码方法得到的码并非唯一的。每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率

3、放在上面，这样可获得较小的码方差。需要大量的存储设备来缓冲码字长度的差异，这是码方差小的码质量好的原因。2021/10/555.4哈夫曼（Huffman）编码（例2）例：对以下离散无记忆信源进行两种哈夫曼编码。(例5.1.6)信源符号ai概率p(ai)码字Wi1码长Ki1码字Wi2码长Ki2a10.411002a20.2012102a30.20003112a40.1001040103a50.10011401132021/10/565.4哈夫曼（Huffman）编码（例2续）第一种方法　　　　　第二种方法0.40.40.40.61

4、.00.20.20.40.40.20.20.20.10.20.10.40.40.40.61.00.20.20.40.40.20.20.20.10.20.10101010101010101码字１01000001000110010110100112021/10/575.4哈夫曼（Huffman）编码（例2续）第一种方法码树图　　　　　　　　　　　　　　第二种方法码树图2021/10/585.4哈夫曼（Huffman）编码（例2续）2021/10/595.4哈夫曼（Huffman）编码进行哈夫曼编码时，为得到码方差最小的码，应使合并的

5、信源符号位于缩减信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码。哈夫曼码是用概率匹配方法进行信源编码。它有两个明显特点：一是哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；二是缩减信源的最后两个码字总是最后一位不同，保证了哈夫曼码是即时码。哈夫曼码是最佳码。2021/10/510m进制哈夫曼编码二进制哈夫曼的编码方法可以很容易推广到m进制的情况。只是编码过程中构成缩减信源时，每次都是将m个概率最小的符号合并，并分别用0,1,…,m-1码符号表示。为使平均码长最短，必须使最后一

6、步缩减信源有m个信源符号。如果第一步给概率最小的符号分配码元时，所取的符号数就不一定是m个。5.4哈夫曼（Huffman）编码2021/10/511全树：码树图中每个中间节点后续的枝数必为m。若有些节点的后续枝数不足m，则称为非全树。对于m进制编码，若所有码字构成全树，可分离的码字数必为m+k(m-1)，式中k为非负整数，即缩减次数。若信源所含的符号数n不能构成m进制的全树，就必须增加s（s

7、n是否满足n=(m-1)k+m，若不满足该式，可以人为地增加一些概率为零的符号，以使最后一步有m个信源符号；(2)取概率最小的m个符号合并成一个新结点，并分别用0,1,…,(m-1)给各分支赋值，把这些符号的概率相加作为该新结点的概率；(3)将新结点和剩下结点重新排队，重复(2),如此下去直至树根；(4)取树根到叶子(信源符号对应结点)的各树枝上的赋值，则得到各符号码字。后来新加的概率为零的符号，虽也赋予码字，实际上这是冗余码字，并未用上，但这样编成的码，仍是最佳的，也就是平均码长最短，如果等概率符号排队时注意到顺序，则码长的方

8、差也是最小的。2021/10/513m进制哈夫曼编码－例１设单符号离散无记忆信源如下，对信源编三进制哈夫曼码。2021/10/514m进制哈夫曼编码－例１（续）2021/10/515m进制哈夫曼编码－例１（续）三进制哈夫曼码树图2021/10/516m进制哈夫曼