资源描述：
《第二章 信息熵与Huffman编码.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、多媒体技术信息熵与Huffman编码徐家臻本章内容Huffman编码算法信息论的一些基础知识编码(Code)定长编码ASCII–每个字母8位‘A’:01000001变长编码a:0b:1c:00d:11平均编码长度其中，x表示各种符号p(x)表示该符号出现的概率(频率)L(x)表示该符号对应码字的长度(位数)唯一可解码编码是唯一可解的吗？a:0b:1c:00d:11接收到00011唯一可译码接收到11000000010110-00-00-00-10前缀码定义如果没有一个码字是另一个码字的前缀，则该码称为前缀码特点唯一可译即时可译，译码不需要等待后续码字为什么唯一即时可译？xabcdC(x
2、)010110111最优编码最优编码的定义最小的唯一可解码两个问题最优的前缀码设计方法是什么？最优的前缀码是不是最优编码？Huffman编码给定m个权值{w1,w2,…,wm}构造由m棵二叉树组成的树林F={T1,T2,…,Tm}，其中每棵树Ti只有一个根结点，且根结点的权值为wi；在树林中选取两棵根结点权值最小的和次小的二叉树作为左右子树构造一棵新的二叉树，其根结点的权值为左右子树根结点权值之和。将新的二叉树加入到树林F中，去除原两棵权值最小的树；重复2、3步骤，直至F中只剩一棵树为止。Huffman编码举例a2字母abcde频率24211b4c2d1e1Huffman编码举例字母a
3、bcde频率24211d1e12Huffman编码举例字母abcd+e频率2422d1e12a2c24Huffman编码举例字母a+cbd+e频率442d1e12a2c24Huffman编码举例字母a+c+d+eb频率64d1e12a2c246Huffman编码举例字母all频率10d1e12a2c246b410Huffman编码举例d1e12a2c246b41001001011字母编码a100b0c101d110e111Huffman编码步骤给定m个权值{w1,w2,…,wm}构造由m棵二叉树组成的树林F={T1,T2,…,Tm}，其中每棵树Ti只有一个根结点，且根结点的权值为wi；
4、在树林中选取两棵根结点权值最小的和次小的二叉树作为左右子树构造一棵新的二叉树，其根结点的权值为左右子树根结点权值之和。将新的二叉树加入到树林F中，去除原两棵权值最小的树；重复2、3步骤，直至F中只剩一棵树为止。最优前缀码必要条件与Huffman树的构造方式最优前缀码应具有的性质出现频率高的符号的码字长度比出现频率低的符号的码字长度短出现频率最低的两个符号，码字长度相等最优编码对应的树的中间节点必有左右两个分支如果把中间节点的所有叶子节点对应的符号看成一个符号组合，把中间节点改成组合对应的叶子结点，那么若原来的树是最优的，修改后的树也是最优的。最优编码最优编码的定义最小的唯一可解码两个问
5、题最优的前缀码设计方法是什么？最优的前缀码是不是最优编码？√？Kraft-McMillan不等式McMillan定理假定C是由N个长度为l1,l2,…,lN码字组成的编码表，如果C是唯一可解码的，那么必有Kraft定理假定N个整数l1,l2,…,lN满足不等式那么必定可以找到一种N个码字组成的前缀码，其码字长度分别为l1,l2,…,lNMcMillan定理证明看K(C)的n次方McMillan定理证明Ak表示n个C中的码字可以组合成长度k的串数目对于2进制串，只可能有2k种取值，由于C是唯一可解码的，所以每个取值对应唯一的C中码字的组合因此，Ak<2k如果K(C)>1，当n充分大时，左
6、边>右边。所以K(C)≤1从Kraft-McMillan定理得到的结论假定C是由N个长度为l1,l2,…,lN码字组成的编码表，如果C是唯一可解码的，那么必有假定N个整数l1,l2,…,lN满足不等式那么必定可以找到一种N个码字组成的前缀码，其码字长度分别为l1,l2,…,lN结论：对于任意唯一可解码，都可以找到对应的前缀码，其码字长度完全相同。最优的前缀码是最优编码。统计编码压缩的上限Huffman编码可以产生最优编码最优编码的平均长度是多少？或者说，统计编码压缩的上限是多少？信息量与信息熵用什么作为信息的量度?信息的不确定程度信息带来的“惊奇”程度信息量与信息描述的事件产生的概率密
7、切相关Shannon认为x事件的信息量I(x)应该具有的性质（用p(x)代表x事件发生的概率）I(x)>0p(x)越小，I(x)越大如果事件x，y独立同分布，即p(x,y)=p(x)p(y)时，I(x,y)=I(x)+I(y)I(x)=-logp(x)对于二进制编码：I(x)=-log2p(x)，单位是bit信息熵信息熵是所有可能事件的信息量的期望（平均）H与p的关系假设有N个事件，当每个事件发生的概率相等，即p(x1)=p(x2)=…=p(x
