进制哈夫曼编码PPT学习教案

1、会计学1 进制哈夫曼编码进制哈夫曼编码 2上午7时34分 第1页/共22页 信源符号信源符号ai概率概率p(ai)码字码字Wi码长码长Ki a10.20102 a20.19112 a30.180003 a40.170013 a50.150103 a60.1001104 a70.0101114 3上午7时34分 第2页/共22页 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

2、.01 0 1 0 1 0 1 0 1 0 1 0 1 4上午7时34分 第3页/共22页 % K )X(H R )X(H Kmlog L K R ,mL .)p(alog)p(a)X(H K)a(pK i ii i ii 96 2.72 2.61 /2.72 21 /612 /2.72 7 1 7 1 编编码码效效率率： 码码元元比比特特 所所需需的的信信息息率率： 码码，则则信信源源采采用用哈哈夫夫曼曼编编码码，对对单单符符号号信信源源编编二二进进制制 符符号号比比特特信信源源熵熵： 符符号号码码元元平平均均码码长长： 5上午7时34分 第4页/共22页 哈夫曼编码方法得到的码并非唯一的。

3、 n每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是 可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长 度。 n对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源 符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放 置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字 的长度，一般将合并的概率放在上面，这样可获得较小的码方差。 n需要大量的存储设备来缓冲码字长度的差异，这是码方差小的码质 量好的原因。 n i iii )K)(Kp(xKKE 1 2 2 2 码字长度的方差：码字长度的方差： 6上午7时34分 第5页/共22页 信源信源 符号符号ai

4、概率概率 p(ai) 码字码字Wi1码长码长Ki1码字码字Wi2码长码长Ki2 a10.411002 a20.2012102 a30.20003112 a40.1001040103 a50.1001140113 7上午7时34分 第6页/共22页 第第一一种方法第种方法第二二种方法种方法 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 码字码

5、字 01 000 0010 0011 00 10 11 010 011 8上午7时34分 第7页/共22页 第一种方法码树图第二种方法码树图第一种方法码树图第二种方法码树图 9上午7时34分 第8页/共22页 量好。量好。故第二种哈夫曼码的质故第二种哈夫曼码的质 第二种方法：第二种方法： 第一种方法：第一种方法： 码字长度的方差：码字长度的方差： 率相等：率相等：两种编码方法的编码效两种编码方法的编码效 符号符号码元码元等：等：两种方法的平均码长相两种方法的平均码长相 1602.2)-0.1)(3(0.12.2)-0.2)(20.2(0.4 3612.2)-0.1)(4(0.12.2)-0.2

6、(32.2)-0.2(22.2)-0.4(1 596 /22 222 2 22222 1 1 2 2 2 7 1 . . )K)(Kp(xKKE %. K )X(H .)Kp(xK n i iii i ii 10上午7时34分 第9页/共22页 n进行哈夫曼编码时，为得到码方差最小的码，应使合并 的信源符号位于缩减信源序列尽可能高的位置上，以减 少再次合并的次数，充分利用短码。 n哈夫曼码是用概率匹配方法进行信源编码。它有两个明 显特点：一是哈夫曼码的编码方法保证了概率大的符号 对应于短码，概率小的符号对应于长码，充分利用了短 码；二是缩减信源的最后两个码字总是最后一位不同， 保证了哈夫曼码是

7、即时码。 n哈夫曼码是最佳码。 11上午7时34分 第10页/共22页 5.4 哈夫曼（Huffman）编码 12上午7时34分 第11页/共22页 m进制哈夫曼编码 5.4 哈夫曼（Huffman）编码 13上午7时34分 第12页/共22页 14上午7时34分 第13页/共22页 符符号号进进行行编编码码。 个个次次只只需需取取不不用用的的码码字字，所所以以第第一一 个个则则须须增增加加则则令令 。其其中中， 21-3s-m 1n-9s9,1)-k(mm3, 83, 05005050050010102040 87654321 k nm . xxxxxxxx )p(x X i 15上午7时3

8、4分 第14页/共22页 16上午7时34分 第15页/共22页 % . . . . 91 772 352 /7723log L K R /751)Kp(xK 2 8 1i ii 编码效率编码效率 符号符号比特比特相应的信息率相应的信息率 符号符号码元码元其平均码长其平均码长 三进制哈夫曼码树图三进制哈夫曼码树图 17上午7时34分 第16页/共22页 05.005.02.03.04.0 54321 xxxxx )p(x X i 18上午7时34分 第17页/共22页 19上午7时34分 第18页/共22页 20上午7时34分 第19页/共22页 缩缩可可言言。于于没没有有编编码码，当当然然无

9、无压压 数数，等等个个信信源源符符号号赋赋予予一一个个码码若若编编五五元元码码，只只能能对对每每大大于于码码元元数数。上上例例中中， 数数应应远远下下，信信源源符符号号集集的的元元素素编编码码的的优优势势，一一般般情情况况可可见见，要要发发挥挥哈哈夫夫曼曼 编编码码效效率率分分别别为为： 别别为为：两两种种编编码码的的平平均均码码长长分分 信信源源熵熵： %. . . LlogK H(X) )( %. . . LlogK H(X) R H(X) )( l)(bit/symbo.).().()Kp(xK l)(bit/symbo.).().()Kp(xK l)(bit/symbo.)p(xlog)p(