基于MATLAB的霍夫曼程序设计

《基于MATLAB的霍夫曼程序设计》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、本科课程设计基于MATLAB的霍夫曼编码设计院（系）名称专业名称学生姓名学号指导教师完成时间2016.12.31基于MATLAB的霍夫曼编码设计霍夫曼编码是一种无损的统计编码方法，利用信息符号概率分布特性改变字长进行编码。霍夫曼编码适用于多元独立信源，对于多元独立信源来说它是最佳码。1基本原理霍夫曼编码是一种利用信息符号概率分布特征的变字长的编码方法，即对于出现概率大的信息符号编以短字长的码，对于出现概率小的信息符号编以长字长的码。如果码字长度严格按照所对应符号出现概率大小逆序排列，则编码结果的平均码字长度一定小于任何其他排列形式。霍夫曼编码则是严格按照信源符号出现的概率大小来构造码字,因此

2、这种编码方式形成的平均码字长度最短。霍夫曼编码系统主要分为压缩对彖输入、概率统计、构造Huffman树、生成Huffman树、压缩编码环节组成，如图所示霍夫曼解码系统构成。编程依据霍夫曼的编程步骤进行，实现对数据的压缩及其压缩参数的计算。霍夫曼编码图像输入概按照率概率统大小计倒序51排列构生生造成成霍霍霍夫夫夫曼曼曼树树n码压缩图像输出2霍夫曼编码的步骤：2.1将信源符号按岀现概率从大到小排成一列，然后把最末两个符号的概率相加，合成一个概率。2.2把这个符号的概率与其余符号的概率按从大到小排列，然后再把最末两个符号的概率加起来，合成一个概率。2.3重复上述做法，直到最后剩下两个概率为止。2.

3、4从最后一步剩下的两个概率开始逐步反向进行编码。没步只需对两个分支各赋予•个二进制码，如对概率大的赋予码0,对概率小的赋予码1。•20.26严.o0.19C.P0200•“八M•0.18e.is•.it0.2(>¥026•.17•47o.ir.awJ•.ISo.isri•.mJ0・叩0.0lLJe.iiu«Kk<020102*0.19112al「0.180003]•470013*0.1S01030.10•IM41■?Ml01114倂对以卜信激退疗哈夫曼第码3实例分析设输入信源L1,L2,L3,L4的概率分别为：0.5,0.19,0.19,0.12借源缩減年俞入输入概率111^14O.5O.1

4、9O.19O.505»O・31一严o*5O.19O・12原始信源信源缩减綸入输入概率码字12110.500.50.50】20.19110.310^-T—0.51130.19100◄—0.191」1A1O1ni亠编码结果为：Ll=0,L2=ll,L3=100,L4=10,根据所给参数求得信息源嫡为:4//(X)=-^/>log2pk=-(0.51og20.5+0.191og20.19+0.191og20.19+0.121og20.12)=1.78k=平均码字长度为:4R=》BR=0.5x1+0.19x2+0.19x3+0.12x3=1.81k=]编码效率为:=983%冗余度为:y=1-7；=

5、1-0.983=0.017压缩比为：r=-=—=AR1.814程序%霍夫曼编码李晓东130524050closeall;clearall;clc;A=[0.5,0.19,0.19,0.12];A=fliplr(sort(A));T二A;[m,n]=sizo(A);B二zeros(n,n-1);fori=l:nB(i,l)=T(i);endr=B(i,l)+B(i-l,1)；T(n-l)=r;T(n)=0;T=fliplr(sort(T));t=n-l;for%关闭所有图形窗口，清楚工作空间所有变量，清除命令行%信源消息的概率序列%按降序排列%空的编码表（矩阵）%生成编码表的第一列%最后两

6、个元素相加j=2:n-lfori二l:tB(i,j)=T(i);endK=find(T==r);B(n,j)=K(end);r=(B(t-l,j)+B(t,j));T(t-l)=r;T(t)=O;T=fliplr(sort(T));t二t—1;%生成编码表的其他各列%从第二列开始，每列的最后一个元素记录特征元素在盖烈的位置%最后两个元素相加endB;END1二sym('[0,1]');EMD二EMD1;t二3;d二1;forj二n-2:T:1fori=l:t-2ifi>l&B(i,j)==B(i-l,j)%输出编码表%给最后一列的元素编码elsed=l;endB(B(n,j+1),j+1)二

7、-1;temp=B(:,j+1);x二find(temp==B(i,j));END(i)=ENDl(x(d));endy=B(n,j+1);END(t-l)=[char(END1(y)),'O'];END(t)=[char(END1(y)),*T];t二t+1;E7D1二END;enddispf排序后的原概率序列P:');disp(A)dispC编码结果END')disp(END);fori=l:n[a,b]