信息论编码课程设计

《信息论编码课程设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计任务书2011—2012学年第一学期专业：通信工程学号：080110005姓名：刘胜英课程设计名称：信息论与编码课程设计设计题目：M进制哈夫曼编码的分析与实现完成期限：自2011年12月19日至2011年12月25日共1周一．设计目的1、深刻理解信源编码的基本思想与目的；2、理解哈夫曼编码方法的基本过程与特点；3、提高综合运用所学理论知识独立分析和解决问题的能力；4、使用MATLAB或其他语言进行编程。二．设计内容假设已知一个信源的各符号概率，编写适当函数，对其进行哈夫曼编码，得出M进制码字，平均码长和编码效率，总结此编码方法的特点和应用

2、。三．设计要求1、编写的函数要有通用性；2、信源可以自由选择，符号信源与图像信源均可。四．设计条件计算机、MATLAB或其他语言环境五．参考资料[1]曹雪虹，张宗橙.信息论与编码.北京：清华大学出版社，2007.[2]王慧琴.数字图像处理.北京：北京邮电大学出版社，2007.指导教师（签字）：教研室主任（签字）：批准日期：年月日摘要哈夫曼编码(HuffmanCoding)是一种编码方式，也是可变字长编码(VLC)的一种。这种方法完全依据字符出现的概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作哈夫曼编码。对于M进制哈弗曼编码，

3、为了提高编码效率，就要使长码的符号数量尽量少、概率尽量小，所以应使合并的信源符号位于缩减信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码。本文将采用三进制哈夫曼编码作为例子来诠释M进制哈夫曼编码。在三进制哈夫曼编码中，得出码字、平均码长和编码效率，构造哈夫曼树，沿着根节点到叶节点从左到右依次为0、1、2，保证平均码长最小。在本文中采用VisualC++6.0进行编程，此程序中具有输入字符集大小和权值大小，构造哈夫曼树，并对用户输入的字符串进行编码等功能。关键词：哈弗曼编码；信源；哈夫曼树；VisualC++6.0；目录1课题描述12设

4、计原理13设计过程23.1软件介绍23.1.1VisualC++6.0简介23.1.2主要部分33.2设计内容44编码程序分析及其结果6总结14参考文献15课程设计说明书（论文）1课题描述在这个信息量爆炸的时代，凡是能载荷一定信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码。为此，必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字最短。能获得最佳码的编码方法主要有：香农（Shannon）、费诺（Fano）、哈夫曼（Huffman）编码等。哈夫曼(Huffman)编码是一种常用的压缩编码方法，是Huffm

5、an于1952年为压缩文本文件建立的。它的基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。哈夫曼编码是哈夫曼树的一个应用，是一种最优的前缀技术，然而其存在的不足却制约了它的直接应用。首先，其解码时间为O(lavg)，其中lavg为码字的平均长度；其次，更为重要的是，解码器需要知

6、道哈夫曼编码树的结构，因而编码器必须为解码器保存或传输哈夫曼编码树。对于小量数据的压缩而言，这是很大的开销。因而，应用哈夫曼编码的关键是如何降低哈夫曼编码树的存储空间。目前流行的很多压缩方法都是用了该技术，如GZIB、ZLIB、PNC等。2设计原理对于多进制哈夫曼编码，为了提高编码效率，就要是长码的符号数量尽量少、概率尽量小，所以信源符号数量最好满足n=(m-1)*k+r,其中m为进制数，k为缩减的次数。设计步骤如下：[1]将信源符号按概率从大到小的顺序排列，令第15页共15页课程设计说明书（论文）p(x1)≥p(x2)≥…≥p(xn)[2]给两

7、个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，或者在新添加一个信源符号，令其概率为0，则个分配一个码位“0”、“1”和“2”，将其合并，结果得到一个只包含(n－1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。[3]将缩减信源S1的符号仍按概率从大到小顺序排列，此后每次合并3个信源符号，得到只含(n－3)个符号的缩减信源S2。[4]重复上述步骤，直至最后，此时所剩符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回

8、，就得到各信源符号所对应的码字。3设计过程3.1软件介绍3.1.1VisualC++6.0简介VisualC++6.0，简称VC或者VC