哈夫曼编码的分析与实现课程设计.doc

吉林建筑大学 电气与电子信息工程学院 信息理论与编码课程设计报告 设计题目： 哈夫曼编码的分析与实现 专业班级： 电子信息工程 111 学生姓名： 学 号： 指导教师： 设计时间： 2014.11.24－2014.12.5  摘要 哈夫曼编码(Huffman Coding)是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称熵编码法），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。 本课题通过编写适当的函数，对一个随机信源进行哈夫曼编码，得出码字，平均码长和编码效率。从而理解信源编码的基本思想与目的以及哈夫曼编码方法的基本过程与特点，并且提高综合运用所学理论知识独立分析和解决问题的能力。 关键字：哈夫曼，信源编码，2.2设计原理 2.3哈夫曼编码步骤 2.4哈夫曼编码特点2.5设计步骤 2.5.1 以框图形式画出哈夫曼编码过程2.5.2 哈弗曼树的介绍 …………………………………………………………5 2.5.3 计算平均码长、编码效率、冗余度 ……………………………………5 第3章 哈夫曼编码C语言实现 3.1 C语言编程 3.1.1编程环境介绍 3.1.2程序介绍3.1.3程序测试 …………………………………………………………………8 3.2 运行结果及分析……………………………………………………………10 3.3 程序流程图以及说明………………………………………………………11 第4章 总结 ………………………………………………………………………12 参考文献 …………………………………………………………………………14 附录一 哈夫曼编码分析与实现C语言源程序 …………………………………15 第1章 概述 1.1设计的作用、目的 从信息论角度看，信源编码的一个最主要的目的，就是要解决数据的压缩问题。数据压缩是指以最少的代码表示信源所发出的信号，减少容纳给定信息集合或数据采样集合的信号空间。图像编码与压缩的目的就是对图像数据按一定的规则进行变换和组合，从而达到以尽可能少的代码表示尽可能多的图像信息。图像数字化之后，其数据量非常庞大，例如，一副640×480?的彩色图像（24bit/像素），其数据量约为921.6KB。如果以30?帧/s?的速度播放，则每秒的数据量为640×480×24×30bit=221.12Mbit，需要221?Mbit/s?的通信回路。在多媒体中，海量图像数据的存储和处理是一个难题。如不进行编码压缩处理，一张存650MB字节的光盘仅能存放24s左右的640像素×480像素的图像画面[1][5]。总之，大数据量的图像信息会给存储器的存储容量、通信干线通道的带宽以及计算机的处理速度增加极大的压力。另一方面，图像本身包含着大量的冗余成分。统计测量表明图像信号在相邻像素间、相邻行间、相邻帧之间存在着很强的相关性。一般情况下，画面中亮度变化相对平坦的地方，相邻像素就有相同的值，而且对相邻帧的图像来说，画面中的大部分区域信号变化缓慢，尤其是背景部分几乎不变。如果能对这些冗余成分加以有效削减，就能够大大节减图像的存储空间，减少图像传输时所占信道容量，使得现有的PC和网络在指标和性能方面能够达到处理图像信息的要求。没有压缩技术的发展，大容量图像信息的存储与传输难以适应应用的要求，多媒体通信技术也难以推广。因此，图像数据在传输和存储中，数据的压缩是必不可少的 1.2设计任务及要求 1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法； 2. 掌握哈夫曼编码/费诺编码方法的基本步骤及优缺点； 3. 深刻理解信道编码的基本思想与目的，理解线性分组码的基本原理与编码过程； 4. 能够使用语言进行编程夫曼编码(Huffman Coding)是一种编码方式，夫曼编码是可变字长编码(VLC)的一种。夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。(参与求概率之和的这两个序列不再出现在新的排列之中)。然后,对参