编写matlab函数实现哈夫曼编码的算法

《编写matlab函数实现哈夫曼编码的算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、西南科技大学课程设计报告课程名称：数字通信课程设计设计名称：编写Matlab函数实现哈夫曼编码的算法姓名：张亮学号:20084905班级：通信0802班指导教师：胥磊起止日期：2011.6.21-2011.7.3西南科技大学信息工程学院制课程设计任务书学生班级：通信0802班学生姓名：张亮学号：20084905设计名称：编写Matlab函数实现哈夫曼编码的算法起止日期：2011.6.21-2011.7.3指导教师：胥磊设计要求：1.理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；2.

2、考虑一个有8种可能符号的信源，各种符号发生的概率分别为：0.30、0.16、0.14、0.12、0.10、0.09、0.06、0.04；3.根据Huffman编码算法，得到码树和Huffman码；4.编写M函数，以8个信源产生的概率向量为变量，返回Huffman编码算法的编码结果，返回信源熵和编码的码字长度。课程设计学生日志时间设计内容6.21—6.21查阅资料，确定方案，了解哈夫曼编码的规则6.22—6.22设计总体方案6.23—6.26功能和要求的具体设计6.27—6.27完成设计报告7.5

3、—7.5答辩课程设计考勤表周星期一星期二星期三星期四星期五课程设计评语表指导教师评语：成绩：指导教师：年月日编写Matlab函数实现哈夫曼编码的算法一、设计目的和意义在当今信息化时代，数字信号充斥着各个角落。在数字信号的处理和传输中，信源编码是首先遇到的问题，一个信源编码的好坏优劣直接影响到了后面的处理和传输。如何无失真地编码，如何使编码的效率最高，成为了大家研究的对象。哈夫曼编码就是其中的一种，哈夫曼编码是一种变长的编码方案。它由最优二叉树既哈夫曼树得到编码，码元内容为到根结点的路径中与父结点

4、的左右子树的标识。所以哈夫曼在编码在数字通信中有着重要的意义。可以根据信源符号的使用概率的高低来确定码元的长度。既实现了信源的无失真地编码，又使得编码的效率最高。二、设计原理哈夫曼编码(HuffmanCoding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。而哈夫曼编码的第一步工作就是构造哈夫曼树。哈夫曼二叉树的构造方法原则如下，假

5、设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1、w2、…、wn，则哈夫曼树的构造规则为：(1)将w1、w2、…，wn看成是有n棵树的森林(每棵树仅有一个结点)；(2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)从森林中删除选取的两棵树，并将新树加入森林；(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。具体过程如下图1产所示：（例）图1哈夫曼树构建过程哈夫曼树构造成功

6、后，就可以根据哈夫曼树对信源符号进行哈夫曼编码。具体过程为先找到要编码符号在哈夫曼树中的位置，然后求该叶子节点到根节点的路径，其中节点的左孩子路径标识为0，右孩子路径标识为1，最后的表示路径的01编码既为该符号的哈夫曼编码。可以知道，一个符号在哈夫曼树中的不同位置就有不同的编码。而且，不同符号的编码长度也可能不一样，它由该结点到父结点的路径长度决定，路径越长编码也就越长，这正是哈夫曼编码的优势和特点所在。它以各符号出现的概率大小将各符号的编码区分开。例如对上例图中“1”的编码为“100”，“3”

7、的编码为“101”，“5”的编码为“11”。对于一个信源消息的熵可以以下公式(1)求得：(1)其中H(x)表示信源的总信息量，既为信源的熵。p()为信源中一特定符号出现的概率。一、详细设计步骤1)首先对设计题目进行系统理论分析。由给定的8种可能符号的信源，各种符号发生的概率分别为：0.30、0.16、0.14、0.12、0.10、0.09、0.06、0.04。可以根据哈夫曼树的构造原理得出如下哈夫曼树型结构（图2）:图2哈夫曼树其中每个结点中的上面的整数为结点有编号，下面的小数为该结点的权值，在

8、这里指的各结点的概率。2)由以是的哈夫曼树图，根据哈夫曼的编码规则可求该8个输出符号的顺序为：0.30,0.16,0.14,0.12,0.10,0.09,0.06,0.04对应编码输出应该为：1011011101000000101100111，编码长度为25。1)由熵的计算公式可知：H(X)=-(0.30.3+0.160.16+0.140.14+0.0.12+0.10.1+0.090.09+0.060.06+0.040.04)=2.78242)哈夫曼树在matlab中的构造，在matlab中用t