编写Matlab函数实现哈夫曼编码的算法.doc

西南科技大学课 程 设 计 报 告课程名称： 数字通信课程设计 设计名称：编写Matlab函数实现哈夫曼编码的算法姓 名： 张亮 学 号: 20084905 班 级： 通信0802班 指导教师： 胥磊 起止日期： 2011.6.21-2011.7.3 西南科技大学信息工程学院制课 程 设 计 任 务 书学生班级： 通信0802班 学生姓名： 张亮 学号： 20084905 设计名称：编写Matlab函数实现哈夫曼编码的算法 起止日期：2011.6.21-2011.7.3 指导教师： 胥磊 设计要求：1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；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.216.21查阅资料，确定方案，了解哈夫曼编码的规则6.226.22设计总体方案6.236.26功能和要求的具体设计6.276.27完成设计报告7.57.5答辩课 程 设 计 考 勤 表周星期一星期二星期三星期四星期五课 程 设 计 评 语 表指导教师评语： 成绩： 指导教师： 年 月 日编写Matlab函数实现哈夫曼编码的算法一、 设计目的和意义在当今信息化时代，数字信号充斥着各个角落。在数字信号的处理和传输中，信源编码是首先遇到的问题，一个信源编码的好坏优劣直接影响到了后面的处理和传输。如何无失真地编码，如何使编码的效率最高，成为了大家研究的对象。哈夫曼编码就是其中的一种，哈夫曼编码是一种变长的编码方案。它由最优二叉树既哈夫曼树得到编码，码元内容为到根结点的路径中与父结点的左右子树的标识。所以哈夫曼在编码在数字通信中有着重要的意义。可以根据信源符号的使用概率的高低来确定码元的长度。既实现了信源的无失真地编码，又使得编码的效率最高。二、 设计原理哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。而哈夫曼编码的第一步工作就是构造哈夫曼树。哈夫曼二叉树的构造方法原则如下，假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、wn，则哈夫曼树的构造规则为： (1) 将w1、w2、，wn看成是有n 棵树的森林(每棵树仅有一个结点)； (2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； (3)从森林中删除选取的两棵树，并将新树加入森林； (4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。具体过程如下图1产所示：（例）图1 哈夫曼树构建过程哈夫曼树构造成功后，就可以根据哈夫曼树对信源符号进行哈夫曼编码。具体过程为先找到要编码符号在哈夫曼树中的位置，然后求该叶子节点到根节点的路径，其中节点的左孩子路径标识为0，右孩子路径标识为1，最后的表示路径的01编码既为该符号的哈夫曼编码。可以知道，一个符号在哈夫曼树中的不同位置就有不同的编码。而且，不同符号的编码长度也可能不一样，它由该结点到父结点的路径长度决定，路径越长编码也就越长，这正是哈夫曼编码的优势和特点所在。它以各符号出现的概率大小将各符号的编码区分开。例如对上例图中“1”的编码为“100”，“3”的编码为“101”，“5”的编码为“11”。对于一个信源消息的熵可以以下公式(1)求得：HX=-i=0nnp(xi)log2p(xi) (1)其中H(x)表示信源的总信息量，既为信源的熵。p(xi)为信源中一特定符号出现的概率。三、 详细设计步骤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,0.06,0.04对应编码输出应该为：1 0 1 1 0 1 1 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 1 1，编码长度为25。3) 由熵的计算公式可知：H(X)=-(0.3log20.3+0.16log20.16+0.14log20.14+0.12log20.12+0.1log20.1+0.09log20.09+0.06log20.06+0.04log20.04)=2.78244) 哈夫曼树在matlab中的构造，在matlab中用tree(MN,s1,s2,s3)这个系统函数来构造哈夫曼二叉树。声明一个tree(5,x)结构的树型结点，一个结点包括有5个变量存储单元。其中tree(1,x)记录该结点的编号；tree(2,x)记录该结点的概率值；tree(3,x)记录该结点的父结点编号；tree(4,x)记录该结点是左结点还是右结点(其中左结点为“0”，右结点为“1”)；tree(5,x)记录该结点是否为根结点标志(该结点为根结点记为“1”，否则决为“0”)。由哈夫曼树构造原则，先选出所有结点中概率值最小的两个结点，把这两个结点组合在一起形成一个新的二叉树。新二叉树的根结点为两个子结点的概率这和，同时根据实际情况标记结点的相关属性(如左右子结点，是否为根结点)，之后再将新的二叉树跟剩下的结点集合在一起，再选出概率值最小的两个结点，并重复以上的过程，直到把所有的结点都加到二叉树中，开成一根哈夫曼二叉树。在matlab编程实现中先编写一个子函数用于找出所有结点中概率值最小的两个结点，子函数如下：function l,r=findminval(tree)s=find(tree(5,:)=1);if size(s,2)tree(2,i) if secvalfirval second=first;secval=firval; end first=i;firval=tree(2,i); elseif secvaltree(2,i) second=i;secval=tree(2,i); endendl=min(first,second);r=max(first,second);5) 然后再编写代码实现哈夫曼树的构建，通过循环调用tree()函数，并加以判断完成哈夫曼树的构造，代码如下：%哈夫曼树结点数据结构%pro为一概率向量%tree(1,*)结点序号%tree(2,*)概率%tree(3,*)父结点序号%tree(4,*)左右标志%tree(5,*)结点是否是根结点标志%生成的哈夫曼树n=size(pro,2);%得到字符个数tree=ones(5,2*n-1);%构造树数据结构tree(1,:)=1:(2*n-1);%填充结点序号tree(5,(n+1):end)=0;%设置结点是否在集合tree(2,1:n)=pro;%设置概率for i=(n+1):(2*n-1);%循环控制 l,r=findminval(tree);%找到集合中两个最小的值的序号 tree(2,i)=tree(2,l)+tree(2,r);%得到父结点概率值 tree(5,i)=1;%设置新构造结点在集合中 tree(3,l)=i;tree(3,r)=i;%设置父结点序号 tree(4,l)=0;tree(4,r)=1;%设置左右标志 tree(5,l)=0;tree(5,r)=0;%设置不在集合中endHuffmanTree=tree;6) 调用循环计算信源的熵，代码如下：Entropy=0;%初始化为0for j=1:n;%循环累加求信源的熵 Entropy=Entropy-pro(j)*log2(pro(j);end7) 由哈夫曼树生成哈夫曼编码，既哈夫曼树的遍历，同时统计编码的长度，此处采用由下往上的遍历方式，获得路径编码后再将编码倒一次序，得到的编码既为信源称号的哈夫曼编码，最后再将所有符号的编码组合在一起，代码如下：%由下至上完成哈夫曼编码HuffmanCode=;%初始化定义Code=;SumCode=0;LastPoint=1;int z;for k=1:n;%循环完成n个符号的编码 CodeNumber=1; m=k; while(tree(5,m)=1)%判断是否已遍历到根结点 if tree(4,m)=0%判断为左结点编码为0 Code(CodeNumber)=0; CodeNumber=CodeNumber+1; elseif tree(4,m)=1%判断为右结点编码为1 Code(CodeNumber)=1; CodeNumber=CodeNumber+1; end m=tree(3,m);%指向父结点 end CodeNumber=CodeNumber-1; SumCode=SumCode+CodeNumber;%累加计算编码长度 for z=LastPoint:SumCode;%将n个符号的编码组合到一起 HuffmanCode(z)=Code(CodeNumber); CodeNumber=CodeNumber-1; z=z+1; end LastPoint=z;end8) 最后将以上的代码整合到一个子函数中，并设置函数的传入参数为信源符号的概率向量，同时使函数返回哈夫曼树，哈夫曼编码，编码长度以及信源的熵，函数头如下：function HuffmanTree,HuffmanCode,SumCode,Entropy = Huffman(pro)四、 设计结果及分析完成编写设计后，在matlab中运行并验证结果，首先输入概率向量： pro=0.30,0.16,0.14,0.12,0.10,0.09,0.06,0.04;再调用编写的Huffman函数： HuffmanTree,HuffmanCode,SumCode,Entropy = Huffman(pro)回车即可得到执行的结果：（见附图3）所得的结果与实际预测的理论结果一致无误。五、 体会通过本次数字通信课程的设计，深刻体会了数字编码的全过程。认识到了无失真和高效率编码在数字通信中的重要性。清楚了哈夫曼编码的整体过程和细节，首先构建哈夫曼二叉树，再通过该二叉树遍历得到哈夫曼编码值。对二叉树的构建过程的判断方式和构建原则有了更深的认识。同时，进一步使用了matlab这个软件工具，进一步熟悉了在matlab中的编程的语法和结构。认识到了软件工具在通信科研仿真方面的重要作用和方便性。同时在专业方面丰