进制哈夫曼编码课件.ppt

1、5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码）编码二进制哈夫曼码的编码方法：二进制哈夫曼码的编码方法：(1)将信源消息符号按其出现的概率大小依次排将信源消息符号按其出现的概率大小依次排列：列：。(2)取两个概率最小取两个概率最小的符号分别配以的符号分别配以0和和1两个码元，两个码元，并将这两个概率相加作为一个新符号的概率，与并将这两个概率相加作为一个新符号的概率，与未分配二进制码元的符号重新排队。未分配二进制码元的符号重新排队。)x(p)x(p)x(pn211上午8时8分5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码）编码(3)对重排后的两个概率最小符号重

2、复步骤对重排后的两个概率最小符号重复步骤(2)的过的过程。程。(4)不断继续上述过程，直到最后两个符号配以不断继续上述过程，直到最后两个符号配以0和和1为止。为止。(5)从最后一级开始，向前返回得到各个信源符号从最后一级开始，向前返回得到各个信源符号所对应的码元序列所对应的码元序列，即相应的码字。，即相应的码字。2上午8时8分5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码）编码（例）（例）例：例：对以下信源进行哈夫曼编码。对以下信源进行哈夫曼编码。P166习题习题5.3 信源符号信源符号ai概率概率p(ai)码字码字Wi码长码长Kia10.20102a20.19112a30.

3、180003a40.170013a50.150103a60.1001104a70.01011143上午8时8分5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码（例续）编码（例续）0.20 0.20 0.26 0.35 0.39 0.61 1.00.19 0.19 0.20 0.26 0.35 0.390.18 0.18 0.19 0.20 0.260.17 0.17 0.18 0.190.15 0.15 0.170.10 0.110.010101010101014上午8时8分5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码（例续）编码（例续）%K)X(HR)X(

4、HKmlogLKR,mL.)p(alog)p(a)X(HK)a(pKiiiiii962.722.61/2.7221/612/2.727171 编编码码效效率率：码码元元比比特特所所需需的的信信息息率率：码码，则则信信源源采采用用哈哈夫夫曼曼编编码码，对对单单符符号号信信源源编编二二进进制制符符号号比比特特信信源源熵熵：符符号号码码元元平平均均码码长长：5上午8时8分5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码）编码哈夫曼编码方法得到的码哈夫曼编码方法得到的码并非唯一并非唯一的。的。n每次对信源缩减时，赋予信源最后两个概率最小的符号，用每次对信源缩减时，赋予信源最后两个概率最

5、小的符号，用0和和1是可是可以任意的，所以可以得到不同的哈夫曼码，但以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度不会影响码字的长度。n对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将一般将合并的概率放在上面合并的概率放在上面，这样可获得，这样可获得较小的码方差较小

6、的码方差。n需要大量的存储设备来缓冲码字长度的差异，这是码方差小的码质量需要大量的存储设备来缓冲码字长度的差异，这是码方差小的码质量好的原因。好的原因。niiii)K)(Kp(xKKE1222 码字长度的方差：码字长度的方差：6上午8时8分5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码（例）编码（例2 2）例：例：对以下离散无记忆信源进行两种哈夫曼编码。对以下离散无记忆信源进行两种哈夫曼编码。(例例5.1.6)信源信源符号符号ai概率概率p(ai)码字码字Wi1码长码长Ki1码字码字Wi2码长码长Ki2a10.411002a20.2012102a30.20003112a40.

7、1001040103a50.10011401137上午8时8分5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码（例）编码（例2 2续）续）第第一一种方法第种方法第二二种方法种方法0.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.2 0.20.1 0.2 0.10.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.2 0.20.1 0.20.10101010101010101码字码字01000001000110010110100118上午8时8分5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码（例）编码（

8、例2 2续）续）第一种方法码树图第二种方法码树图第一种方法码树图第二种方法码树图9上午8时8分5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码（例）编码（例2 2续）续）量好。量好。故第二种哈夫曼码的质故第二种哈夫曼码的质第二种方法：第二种方法：第一种方法：第一种方法：码字长度的方差：码字长度的方差：率相等：率相等：两种编码方法的编码效两种编码方法的编码效符号符号码元码元等：等：两种方法的平均码长相两种方法的平均码长相1602.2)-0.1)(3(0.12.2)-0.2)(20.2(0.43612.2)-0.1)(4(0.12.2)-0.2(32.2)-0.2(22.2)-0.

9、4(1596/22 2222222221122271.)K)(Kp(xKKE%.K)X(H.)Kp(xKniiiiiii 10上午8时8分5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码）编码n进行哈夫曼编码时，为得到进行哈夫曼编码时，为得到码方差码方差最小的码，应使合并的最小的码，应使合并的信源符号位于缩减信源序列信源符号位于缩减信源序列尽可能高的位置尽可能高的位置上，以减少再上，以减少再次合并的次数，充分利用短码。次合并的次数，充分利用短码。n哈夫曼码是用概率匹配方法进行信源编码。它有两个明显哈夫曼码是用概率匹配方法进行信源编码。它有两个明显特点：一是哈夫曼码的编码方法保证

10、了概率大的符号对应特点：一是哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；二于短码，概率小的符号对应于长码，充分利用了短码；二是缩减信源的最后两个码字总是最后一位不同，保证了哈是缩减信源的最后两个码字总是最后一位不同，保证了哈夫曼码是即时码。夫曼码是即时码。n哈夫曼码是最佳码。哈夫曼码是最佳码。11上午8时8分m进制哈夫曼编码哈夫曼编码n二进制哈夫曼的编码方法可以很容易推广到m进制的情况。只是编码过程中构成缩减信源时，每次都是将m个概率最小的符号合并，并分别用0,1,m-1码符号表示。n为使平均码长最短，必须使最后一步缩减信源有m个信源符号。如果第一步

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

12、（sm-1）个不用的码字来形成全树。）个不用的码字来形成全树。m进制哈夫曼编码哈夫曼编码5.4 5.4 哈夫曼哈夫曼（HuffmanHuffman）编码）编码13上午8时8分m进制哈夫曼编码步骤哈夫曼编码步骤(1)验证所给验证所给n是否满足是否满足n=(m-1)k+m，若不满足该式，可以人为地增加一，若不满足该式，可以人为地增加一些概率为零的符号，以使最后一步有些概率为零的符号，以使最后一步有m个信源符号；个信源符号；(2)取概率最小的取概率最小的m个符号合并成一个新结点，并分别用个符号合并成一个新结点，并分别用0,1,(m-1)给各给各分支赋值，把这些符号的概率相加作为该新结点的概率；分支赋

13、值，把这些符号的概率相加作为该新结点的概率；(3)将新结点和剩下结点重新排队，重复将新结点和剩下结点重新排队，重复(2),如此下去直至树根；如此下去直至树根；(4)取树根到叶子取树根到叶子(信源符号对应结点信源符号对应结点)的各树枝上的赋值，则得到各符号的各树枝上的赋值，则得到各符号码字。码字。n后来新加的概率为零的符号，虽也赋予码字，实际上这是冗余码字，后来新加的概率为零的符号，虽也赋予码字，实际上这是冗余码字，并未用上，但这样编成的码，仍是最佳的，也就是平均码长最短，如并未用上，但这样编成的码，仍是最佳的，也就是平均码长最短，如果等概率符号排队时注意到顺序，则码长的方差也是最小的。果等概率

14、符号排队时注意到顺序，则码长的方差也是最小的。14上午8时8分m进制哈夫曼编码例哈夫曼编码例n设单符号离散无记忆信源如下，对信源编三进制设单符号离散无记忆信源如下，对信源编三进制哈夫曼码。哈夫曼码。符符号号进进行行编编码码。个个次次只只需需取取不不用用的的码码字字，所所以以第第一一个个则则须须增增加加则则令令。其其中中，21-3s-m1n-9s9,1)-k(mm3,83,0500505005001010204087654321 knm.xxxxxxxx)p(xXi15上午8时8分m进制哈夫曼编码例（续）哈夫曼编码例（续）16上午8时8分m进制哈夫曼编码例（续）哈夫曼编码例（续）%.917723

15、52/7723logLKR/751)Kp(xK281iii 编码效率编码效率符号符号比特比特相应的信息率相应的信息率符号符号码元码元其平均码长其平均码长三进制哈夫曼码树图三进制哈夫曼码树图17上午8时8分m进制哈夫曼编码例哈夫曼编码例n设单符号离散无记忆信源如下其三进制哈夫曼编码如图(a)所示，四进制哈夫曼编码如图(b)所示。05.005.02.03.04.054321xxxxx)p(xXi18上午8时8分m进制哈夫曼编码例（续）哈夫曼编码例（续）图(a)三进制哈夫曼编码19上午8时8分m进制哈夫曼编码例（续）哈夫曼编码例（续）图(b)四进制哈夫曼编码20上午8时8分m进制哈夫曼编码例（续）哈

16、夫曼编码例（续）缩缩可可言言。于于没没有有编编码码，当当然然无无压压数数，等等个个信信源源符符号号赋赋予予一一个个码码若若编编五五元元码码，只只能能对对每每大大于于码码元元数数。上上例例中中，数数应应远远下下，信信源源符符号号集集的的元元素素编编码码的的优优势势，一一般般情情况况可可见见，要要发发挥挥哈哈夫夫曼曼编编码码效效率率分分别别为为：别别为为：两两种种编编码码的的平平均均码码长长分分信信源源熵熵：%.LlogKH(X)(%.LlogKH(X)RH(X)(l)(bit/symbo.).().()Kp(xKl)(bit/symbo.).().()Kp(xKl)(bit/symbo.)p(x

17、log)p(x-H(X)iiiiiiiii68821195144994581319513311205005013020403120500502013040951 4343 21上午8时8分三种最佳变长编码方法比较三种最佳变长编码方法比较n香农码香农码：有系统的、惟一的编码方法，但多数情况下编码：有系统的、惟一的编码方法，但多数情况下编码效率不是很高。效率不是很高。n费诺码费诺码：编码方法不惟一，比较适合于对分组概率相等或：编码方法不惟一，比较适合于对分组概率相等或接近的信源编码。接近的信源编码。n哈夫曼码哈夫曼码：编码方法不惟一，对信源的统计特性没有特殊：编码方法不惟一，对信源的统计特性没有特殊要求，编码效率比较高，综合性能优于香农码和费诺码。要求，编码效率比较高，综合性能优于香农码和费诺码。22上午8时8分