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

摘 要 在当今信息化时代，数字信号充斥着各个角落。在数字信号的处理和传输中，信源编码是首先遇到的问题，一个信源编码的好坏优劣直接影响到了后面的处理和传输。如何无失真地编码，如何使编码的效率最高，成为了大家研究的对象。 哈夫曼编码就是其中的一种，哈夫曼编码是一种变长的编码方案matlab编程实现8进制数的哈夫曼编码。 关键字：matlab，哈夫曼编码 目 录 1 课题描述 1 2 设计原理 1 3 设计过程 3 3.1软件介绍 3 3.2设计内容 3 3.3设计步骤 3 4设计程序 5 5程序运行结果及分析 10 总 结 11 参考文献 12 1 课题描述 本课题主要研究对因果稳定线性时不变系统的差分方程的单位冲激响应和单位阶跃响应的求解及绘图观察。该实验以常用工具matlab求解绘图。　MATLAB的基本数据单位是矩阵，它的指令表达式与数学、工程中常用的形式十分相似，故用MATLAB来解算问题要比用C，FORTRAN等语言完成相同的事情简捷得多，并且mathwork也吸收了像Maple等软件的优点,使MATLAB成为一个强大的数学软件。可以直接调用,用户也可以将自己编写的实用程序导入到MATLAB函数库中方便自己以后调用，此外许多的MATLAB爱好者都编写了一些经典的程序，用户可以直接进行下载就可以用。MATLAB以矩阵作为基本编程单元，它提供了各种矩阵的运算与操作，并有较强的绘图功能。 本课题主要利用matlab根据根据信源符号出现概率编程实现8进制数的哈夫曼编码。 2 设计原理 哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。 假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为： (1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)； (2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； (3)从森林中删除选取的两棵树，并将新树加入森林； (4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。 图1 哈夫曼树构建过程 哈夫曼树构造成功后，就可以根据哈夫曼树对信源符号进行哈夫曼编码。具体过程为先找到要编码符号在哈夫曼树中的位置，然后求叶子节点到根节点的路径，其中节点的左孩子路径标识为0，右孩子路径标识为1 例如对上例图中“1”的编码为“100”，“3”的编码为“101”，“5”的编码为“11”。 对于一个信源消息的熵可以以下公式(1)求得： (1) 其中H(x)表示信源的总信息量，既为信源的熵。p()为信源中一特定符号出现的概率。 3 设计过程 3.1软件介绍 MATLAB是矩阵实验室（Matrix Laboratory）的简称，是美国MathWorks公司出品的商业，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，主要包括MATLAB和Simulink两大部分。　MATLAB和Mathematica、Maple并称为三大数学软件。它在数学类科技应用软件中在数值方面首屈一指。MATLAB可以进行矩阵运算、绘制函数和数据、实现算法、创建用户界面、连接其他编程语言的程序等，主要应用于工程计算、控制设计、信号处理与通讯、、、金融建模设计与分析等领域。 MATLAB的基本数据单位是矩阵，它的指令表达式与数学、工程中常用的形式十分相似，故用MATLAB来解算问题要比用C，FORTRAN等语言完成相同的事情简捷得多，并且mathwork也吸收了像Maple等软件的优点,使MATLAB成为一个强大的数学软件。在新的版本中也加入了对CORTRAN，C++，JAVA的支持。可以直接调用,用户也可以将自己编写的实用程序导入到MATLAB函数库中方便自己以后调用，此外许多的MATLAB爱好者都编写了一些经典的程序，用户可以直接进行下载就可以用。1.首先对设计题目进行系统理论分析。由给定的8种可能符号的信源，各种符号发生的概率分别为：0.30、0.16、0.14、0.12、0.10、0.09、0.06、0.04。可以根据哈夫曼树的构造原理得出如下哈夫曼树型结构（图2）: 图2 哈夫曼树 其中每个结点中的上面的整数为结点有编号，下面的小数为该结点的权值，在这里指的各结点的概率。 2.由以是的哈夫曼树图，根据哈夫曼的编码规则可求该8个输出符号的顺序为：0.30,0.16,0.14,0.12,0.10,0.09