m进制哈夫曼编码尚世伟.doc

课程设计任务书 2011—2012学年第一学期 专业： 通信工程 学号： 080110004 姓名： 尚世伟 课程设计名称： 信息论与编码课程设计 设计题目： M进制哈夫曼编码的分析与实现 完成期限：自 2011 年 11 月 19 日至 2011 年 11 月 25 日共 1 周 一．设计目的 1、深刻理解信源编码的基本思想与目的； 2、理解哈夫曼编码方法的基本过程与特点； 3、提高综合运用所学理论知识独立分析和解决问题的能力； 4、使用MATLAB或其他语言进行编程。 二．设计内容 假设已知一个信源的各符号概率，编写适当函数，对其进行哈夫曼编码，得出M进制码字，平均码长和编码效率，总结此编码方法的特点和应用。 三．设计要求 1、编写的函数要有通用性； 2、信源可以自由选择，符号信源与图像信源均可。 四．设计条件 计算机、MATLAB或其他语言环境 五．参考资料 [1]曹雪虹，张宗橙.信息论与编码.北京：清华大学出版社，2007. [2]王慧琴.数字图像处理.北京：北京邮电大学出版社，2007. 指导教师（签字）： 教研室主任（签字）： 批准日期： 年 月 日 摘要 通信的数字化是它能与计算机技术和数字信号处理技术相结合的基础，而实现通信数字化的前提是信源能提供的各种用于传递的消息，例如语音、图像、数据、文字等都必须以数字化形式表示。而信源编码是数字通信系统中的重要组成部分，它是保证信号有效传输的一种重要方式。霍夫曼编码依据字符出现的概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，其优越的性能被广泛使用在数字通信系统中。霍夫曼编码已经成为数据压缩的灵魂算法。本文介绍了无失真编码算法的构造，霍夫曼编码的规则和特点，同时分析了对信源进行优化的方法，最后通过C++编程来实现霍夫曼码的优化构造。 关键词：信源；C++；M进制；哈夫曼编码 目录 1 课题描述 1 2 信源编码的基本概念 1 2.1 通信系统的模块 1 2.2 信息的度量与编码 2 2.3 无失真编码算法 3 3 信源最佳化 5 4 霍夫曼编码特点及应用 6 5 编码 7 5.1 二元霍夫曼编码规则 7 5.2 M进制哈夫曼编码 8 5.3 C++程序 9 总结 15 参考资料 16 1 课题描述 在通信的数字化过程中，对于时间连续和取值连续的原始语音和图像等模拟信号来说，如果要以数字方式进行传输，在发送端必须首先进行模/数(A/D)变换，将原始信号转换为时间离散和取值离散的数字信号。 模拟信号数字化之后一般会导致传输信号的带宽明显增加，这样就会占用更多的信道资源，使得传输效率降低，或者无法实现实时传输。为了提高传输效率，一方面需要采用压缩编码技术，在保证一定信号质量的前提下，尽可能地去除信号中的冗余信息，从而减少信号速率和传输所用带宽。另一方面，即使是原本就以数字形式存在的数据和文字信息，也同样存在一个需要通过压缩编码降低信息冗余提高传输效率的问题。由于这些处理都是针对信源发送信息所进行的，因此一般将其称为信源编码。 信源编码的基本目的是提高码字序列中码元的平均信息量，那么，一切旨在减少剩余度而对信源输出符号序列所施行的变换或处理，都可以在这种意义下归入信源编码的范畴，例如过滤、预测、域变换和数据压缩等。作为现代数据无损压缩的灵魂算法，霍夫曼编码正广泛应用于各种图像、音频、视频及各种多媒体信息的压缩环境中。 2 信源编码的基本概念 2.1 通信系统的模块 2.2 信息的度量与编码 信息是指消息中包含的有效内容，度量信息量的原则首先是能度量任何消息并与消息的种类无关，其次度量方法应该与消息的重要程度无关，最后消息中所含信息量和消息内容的不确定性有关。 信息熵的输出可以用随机过程来描述。对于一个离散无记忆平稳随机过程，其信息量（熵）定义为： 其中X表示信源取值集合，p(x)是信源取值x的概率。 信源编码是数字通信中的重要环节，它的主要目的是减少冗余，提高编码效率。信源编码可分为两类：无失真编码和有失真编码。无失真编码只对信源冗余度进行压缩，不会改变信源的熵，又称冗余度压缩编码，它能保证码元序列经译码后能无失真的恢复成信源符号序列，如霍夫曼编码，香农编码。有失真编码在允许的失真范围内把编码后的信息率压缩到最小，有失真信源编码的失真范围受限，所以又称为限失真信源编码。 信源编码就是把信源符