实验报告-2 Huffman编码

PAGE1学生姓名:及学号学院理学院班级课程名称：信息与编码实验题目:Huffman编码指导教师姓名及职称：副教授讲师实验师2014年3月14日目录TOC\o"1-1"\h\z\u一、实验目的 1二、实验内容 1三、实验要点及说明 1四、实现方法 1五、实验结果 2六、源程序清单 2七、思考及总结 5-PAGE1-一、实验目的1．掌握变长编码及即时码的特点；2．理解Huffman编码的特性及编码方法；二、实验内容对给定信源，统计信源分布，在信源概率分布确定情况下，进行Huffman编码，并给出编码结果，并计算平均码长。三、实验要点及说明通过matlab编程，计算相应结果并绘制图形，理解相关性质。四、实现方法以matlab软件为基础，通过编程，对给出或计算出的概率分布计算相应Huffman编码，并计算平均码长。通过matlab编程计算，步骤如下：1.生成表示信源的概率分布p和表示信号字母表的元包数组u；2.根据公式计算霍夫曼压缩表的列数k和各列的行数，为后面的计算做准备；3.根据霍夫曼压缩表的构建方法，循环计算各概率列的数值，同时对各概率列排序并获取插入元素的位置（黑框标记位置）；4.根据霍夫曼编码表的构建方法，从后往前计算出各列的霍夫曼编码；5.将霍夫曼编码表中的第一列霍夫曼编码重新排序，得到最终霍夫曼编码。五、实验结果霍夫曼编码表概率码概率码概率码概率码0.2121281520.2121281520.27751831510.38535353500.12530.12530.2121281520.27751831510.111111111000.111111111000.12530.2121281520.1010.1010.111111111000.12530.090909091020.090909091020.1010.083333333030.083333333030.090909091020.076923077100.076923077100.083333333030.071428571110.071428571110.066666667120.066666667120.06251300.062513平均码长：1.72537185037185最终霍夫曼编码序列表P编码0.12530.111111111000.1010.090909091020.083333333030.076923077100.071428571110.066666667120.06251300.212128152六、源程序清单运行命令：>>p=1./(8:16);>>p(10)=1-sum(p);>>fori=0:3u(i+1)={num2str(i)};end;>>[huff,summ,huffbiao]=huffman(p,u);源程序：function[huff,summ,huffbiao]=huffman(p,u)a=size(p,2);%获取第一列长度r=size(u,2);%获取信号字母个数huff=cell(1,a);%存储霍夫曼编码k=round((a-1)/(r-1)+0.5);%求列数huffbiao=cell(a,2*k);%存储霍夫曼压缩表t=zeros(1,k);%存储各列长度list=zeros(1,k-1);%存储标记位置pp=1:a;%标记排序后的位置t(1)=a;summ=0;forj=2:kt(j)=(k-j+1)*r-k+j;%求各列长度end;forj=a-1:-1:1%首次排序forh=1:jifp(h)<p(h+1)temp=p(h);p(h)=p(h+1);p(h+1)=temp;temp=pp(h);pp(h)=pp(h+1);pp(h+1)=temp;end;end;end;fori=1:ahuffbiao(i,1)={p(i)};end;fori=1:k-1temp=sum(p(t(i+1):t(i)));%求和num=0;forj=1:t(i+1)%插入，重排序iftemp>=p(j)iftemp>p(j)||j==t(i+1)num=num+1;end;temp1=p(j);p(j)=temp;temp=temp1;ifnum==1list(i)=j;%获取标记位置end;end;end;p(t(i+1)+1:t(i))=0;%将无用的部分置为0forh=1:t(i+1)huffbiao(h,2*i+1)={p(h)};%生成霍夫曼压缩表end;end;fori=k:-1:1ifi==kforj=1:t(i)huff(j)=u(j);%给霍夫曼压缩表最后概率列赋值end;elsetemp=huff(list(i));%缓存编码forh=list(i)+1:t(i+1)huff(h-1)=huff(h);%给该列的前段赋值，即将后一列的标记位后面的编码提前一位end;forj=t(i+1):t(i)huff(j)=strcat(temp,u(j-t(i+1)+1));%给该列的后段赋值，即将后一列的标记位编码与信号字母表对应编码连接后赋值end;end;forh=1:t(i)huffbiao(h,2*i)=huff(h);%生成霍夫曼压缩表end;end;forj=a-1:-1:1%霍夫曼编码排序forh=1:jifpp(h)>pp(h+1)temp=pp(h);pp(h)=pp(h+1);pp(h+1)=temp;temp=huff{h};huff{h}=huff{h+1};huff{h+1}=temp;end;end;end;fori=1:asumm=summ+huffbiao{i,1}*length(huffbiao{i,2});%求平均码长end;huff=huff';end七、思考及总结本次课内实验我理解了信源的最优变长编码的基本思想，明白了霍夫曼编码是一种用于无损数据压缩的熵编码（权编码）算法，通过编程演算熟练地掌握了Huffman信源编码方法，同时了解了变长编码及即时码的特点。霍夫曼编码的特点主要有：编出来的码都是异字头码，保证了码的唯一可译性。由于编码长度可变。因此译码时间较长，使得霍夫曼编码的压缩与还原相当费时。编码长度不统一，硬件实现有难度。对不同信号源的编码效率不同，当信号源的符号概率为2的负幂次方时，