《Matlab函数实现哈夫曼编码算法讲解.pdf》由会员分享，可在线阅读，更多相关《Matlab函数实现哈夫曼编码算法讲解.pdf（9页珍藏版）》请在三一文库上搜索。
1、编写 Matlab 函数实现哈夫曼编码的算法 一、设计目的和意义 在当今信息化时代， 数字信号充斥着各个角落。 在数字信号的处理和传 输中，信源编码是首先遇到的问题， 一个信源编码的好坏优劣直接影响到了 后面的处理和传输。 如何无失真地编码， 如何使编码的效率最高， 成为了大 家研究的对象。 哈夫曼编码就是其中的一种， 哈夫曼编码是一种变长的编码方案。它由 最优二叉树既哈夫曼树得到编码， 码元内容为到根结点的路径中与父结点的 左右子树的标识。 所以哈夫曼在编码在数字通信中有着重要的意义。可以根 据信源符号的使用概率的高低来确定码元的长度。既实现了信源的无失真地 编码，又使得编码的效率最高。 二
2、、设计原理 哈夫曼编码 (Huffman Coding)是一种编码方式，哈夫曼编码是可变字长 编码(VLC)的一种。 uffman 于 1952 年提出一种编码方法，该方法完全依据 字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码， 一般就叫作 Huffman 编码。 而哈夫曼编码的第一步工作就是构造哈夫曼树。哈夫曼二叉树的构造方 法原则如下，假设有n 个权值，则构造出的哈夫曼树有n 个叶子结点。n 个权值分别设为w1、w2、wn，则哈夫曼树的构造规则为： (1) 将 w1、w2、，wn 看成是有 n 棵树的森林 (每棵树仅有一个结点 )； (2) 在森林中选出两个根结点的权值
3、最小的树合并，作为一棵新树的 左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； (3)从森林中删除选取的两棵树，并将新树加入森林； (4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈 夫曼树。 具体过程如下图 1 产所示：（例） 图 1 哈夫曼树构建过程 哈夫曼树构造成功后，就可以根据哈夫曼树对信源符号进行哈夫曼编 码。具体过程为先找到要编码符号在哈夫曼树中的位置，然后求该叶子节点 到根节点的路径，其中节点的左孩子路径标识为0，右孩子路径标识为1， 最后的表示路径的01 编码既为该符号的哈夫曼编码。可以知道，一个符号 在哈夫曼树中的不同位置就有不同的编码。而且
4、，不同符号的编码长度也可 能不一样，它由该结点到父结点的路径长度决定，路径越长编码也就越长， 这正是哈夫曼编码的优势和特点所在。 它以各符号出现的概率大小将各符号 的编码区分开。 例如对上例图中“ 1”的编码为“ 100”，“3”的编码为“ 101”，“5” 的编码为“ 11” 。 对于一个信源消息的熵可以以下公式(1)求得： (1) 其中 H(x)表示信源的总信息量， 既为信源的熵。 p()为信源中一特定符 号出现的概率。 三、详细设计步骤 1)首先对设计题目进行系统理论分析。由给定的 8 种可能符号的信源， 各种符号发生的概率分别为：0.30、0.16、0.14、0.12、0.10、0.0
5、9、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。 15 1.01 13 0.41 14 0.6 10 0.19 11 0.22 1 0.3 12 0.3
6、 5 0.1 6 0.09 4 0.12 9 0.1 2 0.16 3 0.14 7 0.06 8 0.04 0 0 0 0 0 0 0 1 11 1 1 1 1 3)由熵的计算公式可知： H(X)=-(0.30.3+0.160.16+0.140.14+0.0.12+0.10.1+0.09 0.09+0.060.06+0.040.04)=2.7824 4)哈夫曼树在 matlab中的构造，在 matlab中用 tree(MN,s1,s2,s3 ) 这个系统函数来构造哈夫曼二叉树。声明一个tree(5,x)结构的树型结点，一 个结点包括有 5 个变量存储单元。 其中 tree(1,x)记录该结点
7、的编号； tree(2,x) 记录该结点的概率值； tree(3,x)记录该结点的父结点编号； tree(4,x)记录该结 点是左结点还是右结点 (其中左结点为“ 0”，右结点为“ 1”)；tree(5,x)记录 该结点是否为根结点标志 (该结点为根结点记为“ 1”，否则决为“ 0”)。由 哈夫曼树构造原则， 先选出所有结点中概率值最小的两个结点，把这两个结 点组合在一起形成一个新的二叉树。 新二叉树的根结点为两个子结点的概率 这和，同时根据实际情况标记结点的相关属性(如左右子结点，是否为根结 点)，之后再将新的二叉树跟剩下的结点集合在一起，再选出概率值最小的 两个结点，并重复以上的过程， 直
8、到把所有的结点都加到二叉树中，开成一 根哈夫曼二叉树。在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); end end l=min(first,second)
9、;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;%设置结点是否在集合
10、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;%设置不在集合中 end HuffmanTree=tree; 6)调用循环计算信源的熵，代码如下： Entropy=0
11、;%初始化为 0 for j=1:n;%循环累加求信源的熵 Entropy=Entropy-pro(j)*log2(pro(j); end 7)由哈夫曼树生成哈夫曼编码，既哈夫曼树的遍历，同时统计编码的 长度，此处采用由下往上的遍历方式，获得路径编码后再将编码倒一次序， 得到的编码既为信源称号的哈夫曼编码，最后再将所有符号的编码组合在一 起，代码如下： %由下至上完成哈夫曼编码 HuffmanCode=;%初始化定义 Code=; SumCode=0; LastPoint=1; int z; for k=1:n;%循环完成 n 个符号的编码 CodeNumber=1; m=k; while(t
12、ree(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 个符号的编码组合到一
13、起 HuffmanCode(z)=Code(CodeNumber); CodeNumber=CodeNumber-1; z=z+1; end LastPoint=z; end 8)最后将以上的代码整合到一个子函数中，并设置函数的传入参数为 信源符号的概率向量， 同时使函数返回哈夫曼树， 哈夫曼编码， 编码长度以 及信源的熵，函数头如下： function HuffmanTree,HuffmanCode,SumCode,Entropy = Huffman(pro) 四、设计结果及分析 完成编写设计后，在matlab 中运行并验证结果，首先输入概率向量： pro=0.30,0.16,0.14,0.
14、12,0.10,0.09,0.06,0.04; 再调用编写的 Huffman 函数： HuffmanTree,HuffmanCode,SumCode,Entropy = Huffman(pro) 回车即可得到执行的结果：（见附图3） 所得的结果与实际预测的理论结果一致无误。 五、体会 通过本次数字通信课程的设计，深刻体会了数字编码的全过程。认识到了无 失真和高效率编码在数字通信中的重要性。清楚了哈夫曼编码的整体过程和细 节，首先构建哈夫曼二叉树， 再通过该二叉树遍历得到哈夫曼编码值。对二叉树 的构建过程的判断方式和构建原则有了更深的认识。同时，进一步使用了 matlab 这个软件工具，进一步熟悉了在matlab 中的编程的语法和结构。认识到了软件 工具在通信科研仿真方面的重要作用和方便性。同时在专业方面丰富了知识面， 增长了见闻。 了解到了更多的通信方面的专业名词和术语。对以后的更深入的学 习的工作打下了基础。