进制哈夫曼编码课件

5.4哈夫曼（Huffman）编码二进制哈夫曼码的编码方法：(1)将信源消息符号按其出现的概率大小依次排列：。(2)取两个概率最小的符号分别配以0和1两个码元，并将这两个概率相加作为一个新符号的概率，与未分配二进制码元的符号重新排队。1*5.4哈夫曼（Huffman）编码二进制哈夫曼码的编码方法5.4哈夫曼（Huffman）编码(3)对重排后的两个概率最小符号重复步骤(2)的过程。(4)不断继续上述过程，直到最后两个符号配以0和1为止。(5)从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。2*5.4哈夫曼（Huffman）编码(3)对重排后的两个概率5.4哈夫曼（Huffman）编码（例１）例：对以下信源进行哈夫曼编码。P166习题5.3

信源符号ai概率p(ai)码字Wi码长Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.01011143*5.4哈夫曼（Huffman）编码（例１）例：对以下信源进5.4哈夫曼（Huffman）编码（例１续）0.20 0.200.260.350.390.611.00.190.190.200.260.350.390.180.180.190.200.260.170.170.180.190.150.150.170.100.110.010101010101014*5.4哈夫曼（Huffman）编码（例１续）0.20 5.4哈夫曼（Huffman）编码（例１续）5*5.4哈夫曼（Huffman）编码（例１续）5*5.4哈夫曼（Huffman）编码哈夫曼编码方法得到的码并非唯一的。每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。需要大量的存储设备来缓冲码字长度的差异，这是码方差小的码质量好的原因。6*5.4哈夫曼（Huffman）编码哈夫曼编码方法得到的码并5.4哈夫曼（Huffman）编码（例2）例：对以下离散无记忆信源进行两种哈夫曼编码。(例5.1.6)

信源符号ai概率p(ai)码字Wi1码长Ki1码字Wi2码长Ki2a10.411002a20.2012102a30.20003112a40.1001040103a50.10011401137*5.4哈夫曼（Huffman）编码（例2）例：对以下离散无5.4哈夫曼（Huffman）编码（例2续）第一种方法第二种方法0.40.40.40.61.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码字１01000001000110010110100118*5.4哈夫曼（Huffman）编码（例2续）第一种方法5.4哈夫曼（Huffman）编码（例2续）第一种方法码树图第二种方法码树图

9*5.4哈夫曼（Huffman）编码（例2续）第一种方法码树5.4哈夫曼（Huffman）编码（例2续）10*5.4哈夫曼（Huffman）编码（例2续）10*5.4哈夫曼（Huffman）编码进行哈夫曼编码时，为得到码方差最小的码，应使合并的信源符号位于缩减信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码。哈夫曼码是用概率匹配方法进行信源编码。它有两个明显特点：一是哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；二是缩减信源的最后两个码字总是最后一位不同，保证了哈夫曼码是即时码。哈夫曼码是最佳码。11*5.4哈夫曼（Huffman）编码进行哈夫曼编码时，为得到m进制哈夫曼编码二进制哈夫曼的编码方法可以很容易推广到m进制的情况。只是编码过程中构成缩减信源时，每次都是将m个概率最小的符号合并，并分别用0,1,…,m-1码符号表示。为使平均码长最短，必须使最后一步缩减信源有m个信源符号。如果第一步给概率最小的符号分配码元时，所取的符号数就不一定是m个。5.4哈夫曼（Huffman）编码12*m进制哈夫曼编码二进制哈夫曼的编码方法可以很容易推广到m进制全树：码树图中每个中间节点后续的枝数必为m。若有些节点的后续枝数不足m，则称为非全树。对于m进制编码，若所有码字构成全树，可分离的码字数必为m+k(m-1)，式中k为非负整数，即缩减次数。若信源所含的符号数n不能构成m进制的全树，就必须增加s（s<m-1）个不用的码字来形成全树。m进制哈夫曼编码5.4哈夫曼（Huffman）编码13*全树：码树图中每个中间节点后续的枝数必为m。若有些节点的后续m进制哈夫曼编码步骤(1)验证所给n是否满足n=(m-1)k+m，若不满足该式，可以人为地增加一些概率为零的符号，以使最后一步有m个信源符号；(2)取概率最小的m个符号合并成一个新结点，并分别用0,1,…,(m-1)给各分支赋值，把这些符号的概率相加作为该新结点的概率；(3)将新结点和剩下结点重新排队，重复(2),如此下去直至树根；(4)取树根到叶子(信源符号对应结点)的各树枝上的赋值，则得到各符号码字。后来新加的概率为零的符号，虽也赋予码字，实际上这是冗余码字，并未用上，但这样编成的码，仍是最佳的，也就是平均码长最短，如果等概率符号排队时注意到顺序，则码长的方差也是最小的。14*m进制哈夫曼编码步骤(1)验证所给n是否满足n=(m-1)km进制哈夫曼编码－例１设单符号离散无记忆信源如下，对信源编三进制哈夫曼码。15*m进制哈夫曼编码－例１设单符号离散无记忆信源如下，对信源编三m进制哈夫曼编码－例１（续）16*m进制哈夫曼编码－例１（续）16*m进制哈夫曼编码－例１（续）三进制哈夫曼码树图17*m进制哈夫曼编码－例１（续）三进制哈夫曼码树图17*m进制哈夫曼编码－例２设单符号离散无记忆信源如下其三进制哈夫曼编码如图(a)所示，四进制哈夫曼编码如图(b)所示。18*m进制哈夫曼编码－例２设单符号离散无记忆信源如下18*m进制哈夫曼编码－例２（续）图(a)三进制哈夫曼编码19*m进制哈夫曼编码－例２（续）图(a)三进制哈夫曼编码19*m进制哈夫曼编码－例２（续）图(b)四进制哈夫曼编码20*m进制哈夫曼编码－例２（续）图(b)四进制哈夫曼编码20*m进制哈夫曼编码－例２（续）21*m进制哈夫曼编码－例２（续）21*三种最佳变长编码方法比较香农码：有系统的、惟一的编码方法，但多数情况下编码效率不是很高。费诺码：编码方法不惟一，比较适合于对分组概率相等或接近的信源编码。哈夫曼码：编码方法不惟一，对信源的统计特性没有特殊要求，编码效率比较高，综合性能优于香农码和费诺码。22*三种最佳变长编码方法比较香农码：有系统的、惟一的编码方法，但5.4哈夫曼（Huffman）编码二进制哈夫曼码的编码方法：(1)将信源消息符号按其出现的概率大小依次排列：。(2)取两个概率最小的符号分别配以0和1两个码元，并将这两个概率相加作为一个新符号的概率，与未分配二进制码元的符号重新排队。23*5.4哈夫曼（Huffman）编码二进制哈夫曼码的编码方法5.4哈夫曼（Huffman）编码(3)对重排后的两个概率最小符号重复步骤(2)的过程。(4)不断继续上述过程，直到最后两个符号配以0和1为止。(5)从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。24*5.4哈夫曼（Huffman）编码(3)对重排后的两个概率5.4哈夫曼（Huffman）编码（例１）例：对以下信源进行哈夫曼编码。P166习题5.3

信源符号ai概率p(ai)码字Wi码长Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.010111425*5.4哈夫曼（Huffman）编码（例１）例：对以下信源进5.4哈夫曼（Huffman）编码（例１续）0.20 0.200.260.350.390.611.00.190.190.200.260.350.390.180.180.190.200.260.170.170.180.190.150.150.170.100.110.0101010101010126*5.4哈夫曼（Huffman）编码（例１续）0.20 5.4哈夫曼（Huffman）编码（例１续）27*5.4哈夫曼（Huffman）编码（例１续）5*5.4哈夫曼（Huffman）编码哈夫曼编码方法得到的码并非唯一的。每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。需要大量的存储设备来缓冲码字长度的差异，这是码方差小的码质量好的原因。28*5.4哈夫曼（Huffman）编码哈夫曼编码方法得到的码并5.4哈夫曼（Huffman）编码（例2）例：对以下离散无记忆信源进行两种哈夫曼编码。(例5.1.6)

信源符号ai概率p(ai)码字Wi1码长Ki1码字Wi2码长Ki2a10.411002a20.2012102a30.20003112a40.1001040103a50.100114011329*5.4哈夫曼（Huffman）编码（例2）例：对以下离散无5.4哈夫曼（Huffman）编码（例2续）第一种方法第二种方法0.40.40.40.61.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码字１010000010001100101101001130*5.4哈夫曼（Huffman）编码（例2续）第一种方法5.4哈夫曼（Huffman）编码（例2续）第一种方法码树图第二种方法码树图

31*5.4哈夫曼（Huffman）编码（例2续）第一种方法码树5.4哈夫曼（Huffman）编码（例2续）32*5.4哈夫曼（Huffman）编码（例2续）10*5.4哈夫曼（Huffman）编码进行哈夫曼编码时，为得到码方差最小的码，应使合并的信源符号位于缩减信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码。哈夫曼码是用概率匹配方法进行信源编码。它有两个明显特点：一是哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；二是缩减信源的最后两个码字总是最后一位不同，保证了哈夫曼码是即时码。哈夫曼码是最佳码。33*5.4哈夫曼（Huffman）编码进行哈夫曼编码时，为得到m进制哈夫曼编码二进制哈夫曼的编码方法可以很容易推广到m进制的情况。只是编码过程中构成缩减信源时，每次都是将m个概率最小的符号合并，并分别用0,1,…,m-1码符号表示。为使平均码长最短，必须使最后一步缩减信源有m个信源符号。如果第一步给概率最小的符号分配码元时，所取的符号数就不一定是m个。5.4哈夫曼（Huffman）编码34*m进制哈夫曼编码二进制哈夫曼的编码方法可以很容易推广到m进制全树：码树图中每个中间节点后续的枝数必为m。若有些节点的后续枝数不足m，则称为非全树。对于m进制编码，若所有码字构成全树，可分离的码字数必为m+k(m-1)，式中k为非负整数，即缩减次数。若信源所含的符号数n不能构成m进制的全树，就必须增加s（s<m-1）个不用的码字来形成全树。m进制哈夫曼编码5.4哈夫曼（Huffman）编码35*全树：码树图中每个中间节点后续的枝数必为m。若有些节点的后续m进制哈夫曼编码步骤(1)验证所给n是否满足n=(m-1)k+m，若不满足该式，可以人为地增加一些概率为零的符号，以使最后一步有m个信源符号；(2)取概率最小的m个符号合并成一个新结点，并分别用0,1,…,(m-1)给各分支赋值，把这些符号的概率相加作为该新结点的概率；(3)将新结点和剩下结点重新排队，重复(2),如此下去直至树根；(4)取树根到叶