霍夫曼编码及其应用

毕业设计（论文）题目：霍夫曼编码及其应用学院：数理学院专业名称：信息与计算科学学号：0741210246学生姓名：张浩指导教师：韩海清2011年4月20日毕业设计（论文）1摘要本文首先对二元霍夫曼编码进行了细致研究，并对其算法进行扩展，得到了适用于多元霍夫曼编码的算法。然后，对霍夫曼编码的前缀性，最优性进行了证明。最后实现了霍夫曼编码在决策论中应用。关键词码；熵；霍夫曼编码；决策树毕业设计（论文）2ABSTRACTThispaperfirststudiedbinaryHuffmancoding,andconductedadetailedstudyonitsalgorithmsuitableforexpansion,getmultipleHuffmancodingalgorithm.Meanwhile,Huffmancodingprefixsex,optimalityproved.FinallyrealizedHuffmancodingappliedinrigorous.KEYWORDSTheCoding；TheEntropy；HuffmanCoding；Decisiontree毕业设计（论文）3目录第一章引言..................................................................................................4第二章主要概念..........................................................................................52.1香农三大定理......................................................................................52.1.1香农第一定理(可变长无失真信源编码定理)....................52.1.2香农第二定理（有噪信道编码定理）.................................52.1.3香农第三定理（保失真度准则下的有失真信源编码定理）............................................................................................................52.2霍夫曼编码..........................................................................................6第三章二元霍夫曼编码及其算法.............................................................6第四章一般霍夫曼编码及其算法.............................................................8第五章霍夫曼编码的性能分析...............................................................125.1霍夫曼编码的前缀性........................................................................125.2霍夫曼编码的最优性定理...............................................................13第六章霍夫曼编码的应用........................................................................13第七章总结与展望....................................................................................16参考文献......................................................................................................17附录1...........................................................................................................18致谢..............................................................................................................30毕业设计（论文）4第一章引言1948年，美国数学家香农（C.E.Shannon）在《贝尔系统电话杂志》发表了题为“通信的数学理论”的长篇论文。这篇论文以概率论为工具，深刻阐述了通信工程的一系列基本理论问题，给出了计算信源信息量和信道容量的方法和一般公式，得到了一组表征信息传递重要关系的编码定理，从而创立了信息论。1959年，香农在发表的“保真度准则下的离散信源编码定理”（Codingtheoremsforadiscretesourceatthefidelitycriterion）一文中系统的提出了信息率失真理论（rate-distortiontheory）,为信源压缩编码的研究奠定了理论基础。在信息传输过程中，信源序列通过信源编码器实现对信源冗余度的压缩，变成编码序列，编码序列通过信源译码器恢复成信源序列。根据恢复序列的效果，可把信源编译器分为两类，即无失真信源编码和限失真信源编码。在无失真信源编码的过程中，编、译码过程是可逆的，即信源符号可以通过编码序列无差错地恢复。为提高传输有效性，我们总是希望在保证无失真的条件下尽量压缩码率（编码后传输每信源符号所需的二元码符号数），但这种压缩是否有限度是一个必须要解决的理论问题。香农第一定理也就是无失真信源编码定理对这个问题做了明确回答。定理指出，只要信源编码码率不小于信源的熵就存在无失真信源编码，同时还指出如果信源编码的码率大于信源编码的熵就不存在无失真信源编码。同时，定理还给出了进行无失真信源编码的理论极值，论证与指出了理想最佳信源编码是存在的。但是并没有给出信源编码的实际构造方法和实用码的结构。编码的目的就是为了优化通信系统。一般来说，通信系统的性能指标是有效性、可靠性、安全性和经济性。随着科学技术的发展和需求，人们广泛致力于对各种文本、图片、图形、语言、声音、活动图像和影视信号等实际信源进行了实用压缩方法和技术研究，使信源的数据压缩技术得以蓬勃发展和逐渐走向成熟。霍夫曼在1952年提出了一种构造最佳码得方法，我们称之为霍夫曼编码。霍夫曼编码适用于多远独立信源，对于多元独立信源来说它是最佳码。它充分利用了信源概率分布的特性进行编码，是一种最佳的逐个符号的编码方法。毕业设计（论文）5第二章主要概念香农定理作为信息论的基础理论，我们有必要对进行简要介绍。下面我们给出香农三大定理：2.1香农三大定理香农三大定理是信息论的基础理论。香农三大定理是存在性定理，虽然并没有提供具体的编码实现方法，但为通信信息的研究指明了方向。[4]香农第一定理是可变长无失真信源编码定理。香农第二定理是有噪信道编码定理。香农第三定理是保失真度准则下的有失真信源编码定理。具体如下:2.1.1香农第一定理(可变长无失真信源编码定理)[1]设信源S的熵H(S),无噪离散信道的信道容量为C,于是,信源的输出可以进行这样的编码,使得信道上传输的平均速率为每秒aSHC)(/个信源符号.其中a可以是任意小的正数,要使传输的平均速率大于)(/SHC是不可能的。2.1.2香农第二定理（有噪信道编码定理）[1]设某信道有r个输入符号,s个输出符号,信道容量为C,当信道的信息传输率R码长N足够长,总可以在输入的集合中(含有r^N个长度为N的码符号序列),找到M（())((^2aCNM,a为任意小的正数)个码字,分别代表M个等可能性的消息,组成一个码以及相应的译码规则,使信道输出端的最小平均错误译码概率Pmin达到任意小。2.1.3香农第三定理（保失真度准则下的有失真信源编码定理）[1]设R(D)为一离散无记忆信源的信息率失真函数,并且选定有限的失真函数,对于任意允许平均失真度0D,和任意小的0a,以及任意足够长的码长N,则一定存在一种信源编码W,其码字个数为aDRNEXPM)(，而编码后码的平均失真度adWD)(,。毕业设计（论文）62.2霍夫曼编码1952年David.A.Huffman提出了一种构造最佳码的方法称之为霍夫曼码。霍夫曼码适用于多元独立信源，对于多元独立信源来说它是最佳码。它充分利用了信源概率分布的特性进行编码，是一种最佳的逐个符号的编码方法。[2]第三章二元霍夫曼编码及其算法二元霍夫曼编码方法的编码步骤如下：1）将q个信源符号按概率分布)(isp的大小，以递减次序排列起来，设qpppp3212）用0和1码分别分配给概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新符号，并用这两个最小概率之和作为新符号的概率，从而得到只包含q-1个符号的新信源，称为S信源的缩减信源1S。3）把缩减信源1S的符号仍按概率大小以递减次序排列，再将最后两个概率最小的符号合并成一个新符号，并分别用0和1码表示，这样又形成q-2个符号的缩减信源2S。4）依次继续下去，直至缩减信源最后只剩两个符号为止。再将最后两个新符号分别用0和1码符号表示。最后这两个符号的概率之和比为1.然后从最后一级缩减信源开始，一编码路径右后向前返回，就得出各信源符号所对应的码符号序列，即得对应的码字。现在，给出一个具体的例子来说明这种编码方法。【例1】设单符号离散无记忆信源如下，要求对其进行二元霍夫曼编码。)(ixpX=01.002.003.006.012.030.046.07654321xxxxxxx可以计算出该信源的熵为：H（X）=-712logiiipp=1.978b从而可以计算出每个符号的平均二元字符数为毕业设计（论文）7K=71)()(iiixPxk=10.46+20.30+30.12+40.06+50.03+60.02+60.01=1.9900b该编码的效率为=（1.9781/1.9900）=99.4%其编码过程如表3.1所示表3.1二元霍夫曼编码（1）概率码概率码概率码概率码概率码概率码0.4610.30000.120100.0601100.03011100.020111100.010111110.4610.30000.120100.0601100.03011100.03011110.4610.30000.120100.0601100.0601110.4610.30000.120100.120110.4610.30000.24010.5400.461现在将看到霍夫曼编码不是唯一的。考了最小两个概率的组合（符号6x和7x），它们的和为0.03，等于与符号5x对应的下一个较高的概率。那么第二步，可以选择使这个组合搞了（比如说等于符号6x）高于或低于符号5x。假定把组合搞了放在下面，继续进行又将发现6x和5x组合后的概率为0.06，等于符号4x的概率。我们又一次可以选择是组合概率高于或低于4x。每次做出一种选择时，最后导致符号的码子改变。每次在有两个相同概率的情况下要做出一种选择时，我们把组合符号的概率放在上面。该信源的熵为H（X）=-712logiiipp=1.9781b而平均每个符号的比特数为K=71)()(iiixPxk=10.46+20.30+30.12+40.06+50.03+60.02+60