毕业论文《霍夫曼编码及其应用》.doc

《毕业论文《霍夫曼编码及其应用》.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、毕业设计（论文）题目：霍夫曼编码及其应用学院：数理学院专业名称：信息与计算科学学号：学生姓名：指导教师：2012年4月20日椿品摘要本文首先对二元霍夫曼编码进行了细致研究，并对其算法进行扩展，得到了适用于多元霍夫曼编码的算法。然后，对霍夫曼编码的前缀性，最优性进行了证明。最后实现了霍夫曼编码在决策论中应用。关键词码；®;霍夫曼编码；决策树ABSTRACTThispaperfirststudiedbinaryHuffmancoding,andconductedadetailedstudyonitsalgorithmsuitableforexpansion,getmulti

2、pieHuffmancodingalgorithm.Meanwhile,Huffmancodingprefixsex,optimalityproved.FinallyrealizedHuffmancodingappliedinrigorous.KEYWORDSTheCoding；TheEntropy；HuffmanCoding；Decisiontree第一章引言4第二章主要概念52.1香农三大定理52.1.1香农第一定理（可变长无失真信源编码定理）52.1.2香农第二定理（有噪信道编码定理）52.1.3香农第三定理（保失真度准则下的有失真信源编码定理）2.2霍夫曼编码第

3、三章二元霍夫曼编码及其算法第四章般霍夫曼编码及其算法12第五章霍夫曼编码的性能分析5.1霍夫曼编码的前缀性125.2霍夫曼编码的最优性定理13第六章霍夫曼编码的应用13第七章总结与展望16参考文献17附录118致谢30第一章引言1948年，美国数学家香农(C.E.Shannon)在《贝尔系统电话杂志》发表了题为“通信的数学理论”的长篇论文。这篇论文以概率论为工具，深刻阐述了通信工程的一系列基本理论问题，给出了计算信源信息量和信道容量的方法和一般公式，得到了一组表征信息传递重要关系的编码定理，从而创立了信息论。1959年，香农在发表的“保真度准则下的离散信源编码定理”(C

4、odingtheoremsforadiscretesourceatthefidelitycriterion)一文中系统的提出了信息率失真理论(rate-distortiontheory)，为信源压缩编码的研究奠定了理论基础。在信息传输过程中，信源序列通过信源编码器实现对信源冗余度的压缩，变成编码序列，编码序列通过信源译码器恢复成信源序列。根据恢复序列的效果，可把信源编译器分为两类，即无失真信源编码和限失真信源编码。在无失真信源编码的过程中，编、译码过程是可逆的，即信源符号可以通过编码序列无差错地恢复。为提高传输有效性，我们总是希望在保证无失真的条件下尽量压缩码率(编码后

5、传输每信源符号所需的二元码符号数)，但这种压缩是否有限度是一个必须要解决的理论问题。香农第一定理也就是无失真信源编码定理对这个问题做了明确回答。定理指出，只要信源编码码率不小于信源的嫡就存在无失真信源编码，同时还指出如果信源编码的码率大于信源编码的炳就不存在无失真信源编码。同时，定理还给出了进行无失真信源编码的理论极值，论证耳指出了理想最佳信源编码是存在的。但是并没有给出信源编码的实际构造方法和实用码的结构。编码的目的就是为了优化通信系统。一般来说，通信系统的性能指标是有效性、可靠性、安全性和经济性。随着科学技术的发展和需求，人们广泛致力于对各种文本、图片、图形、语言、

6、声音、活动图像和影视信号等实际信源进行了实用压缩方法和技术研究，使信源的数据压缩技术得以蓬勃发展和逐渐走向成熟。霍夫曼在1952年提岀了一种构造最佳码得方法，我们称之为霍夫曼编码。霍夫曼编码适用于多远独立信源，对于多元独立信源来说它是最佳码。它充分利用了信源概率分布的特性进行编码，是一种最佳的逐个符号的编码方法。第二章主要概念香农定理作为信息论的基础理论，我们有必要对进行简要介绍。下面我们给出香农三大定理：2.1香农三大定理香农三大定理是信息论的基础理论。香农三大定理是存在性定理，虽然并没有提供具体的编码实现方法，但为通信信息的研究指明了方向。⑷香农第一定理是可变长无失

7、真信源编码定理。香农第二定理是有噪信道编码定理。香农第三定理是保失真度准则下的有失真信源编码定理。具体如下:2.1.1香农第一定理(可变长无失真信源编码定理)设信源S的燔H(S),无噪离散信道的信道容量为C,于是,信源的输出可以进行这样的编码,使得信道上传输的平均速率为每秒C/H(S)-a个信源符号.其中a可以是任意小的正数，要使传输的平均速率大于C/H(S)是不可能的。2.1.2香农第二定理(有噪信道编码定理)tn设某信道有r个输入符号,s个输出符号，信道容量为C,当信道的信息传输率R码长N足够长，总可以在输入的集合中(含有r^N个长度