信息论与编码实验报告-Huffman信源编码.docVIP

实验报告 课程名称： 信息论与编码 姓 名： 系： 专 业： 年 级： 学 号： 指导教师： 职 称： 年 月 日  实验二 Huffman信源编码 一、实验目的 1．理解信源的最优变长编码的基本思想。 2．熟练掌握Huffman信源编码方法。 二、设计原理 设信源S={s1,s2,…..,sq}，其对应的概率分布为P(si)={p1,p2,p3,….,pq}，则其编码步骤如下： (1)将q个信源符号按递减方式排列。 (2)用0、1码符分别表示概率最小的两个信源符号，并将这两个符号合并成一个新的符号，从而得到q-1个符号的新信源成为S信源的缩减信源S1。 (3)将缩减信源S1中的符号仍按递减顺序排列，再将最小两个概率相加，合并成一个符号，并分别用0、1码表示，这样有形成了q-2个缩减信源S2。 (4)依次继续下去，直到缩减信源只剩下两个符号为止，将最后两个符号用0、1分别表示。 (5)从最后一次缩减信源开始，向前返回，沿信源缩减过程的反方向取出所编的马元。 三、实验内容 计算定信源和输入信号字母表的Huffman编码，并计算Huffman编码的平均码长。实验具体要求如下： 信源字母表的概率分布为： P={ 0.15,0.12,0.2,0.08,0.04,0.18,0.02,0.09,0.04,0.02,0.06} 输入信号字母表： U={0,1,2}； 1. 独立设计信源和输入信号字母表进行Huffman编码,其中信源字母表元素个数要求是8以上，信号字母表元素个数是2以上； 2. 输出Huffman编码的平均码长。 四、实验环境 Microsoft Windows 7 Matlab 6.5 五、编码程序 MATLAB编码： function[h,L]=huffman(p,r) %变量p为符号出现概率所组成的概率向量 %返回值h为利用Huffman编码算法编码后最后得到编码结果 %返回值L为进行Huffman编码后所得编码的码字长度 if length(find(p0))~=0 error(Not a prob.vector,negative component(s)); end %判断概率向量中是否有0元素，有0元素程序显示出错，终止运行 if (sum(p,2)1) error(Not a prob.vector,components do not add up to 1); end %判断所有符号出现概率之和是否大于1，如果大于1程序显示出错，终止运行 a=length(p); %测定概率向量长度，将长度值赋给变量n k=fix((a-1)/(r-1)); l1=a-k*r+k; q=zeros(1,a); m=zeros(k+1,a); mp=m; q=p; [m(1,:),mp(1,:)]=sort(q); if (l11) s=sum(m(1,1:l1),2); q=[s,m(1,(l1+1):a),ones(1,l1-1)]; [m(2,:),mp(2,:)]=sort(q); else m(2,:)=m(1,:); mp(2,:)=1:1:a; end for i=3:k+1 s=sum(m(i-1,1:r),2); q=[s,m(i-1,r+1:a),ones(1,r-1)]; [m(i,:),mp(i,:)]=sort(q); end n1=m; n2=mp; for i=1:k+1 n1(i,:)=m(k+2-i,:); n2(i,:)=mp(k+2-i,:); end m=n1; mp=n2; c=cell(k+1,a); for j=1:r c{1,j}=num2str(j-1); end for i=2:k p1=find(mp(i-1,:)==1); for j=1:r c{i,j}=strcat(c{i-1,p1},int2str(j-1)); end for j=(r+1):(p1+r-1) c{i,j}=c{i-1,j-r}; end for j=(p1+r):a c{i,j}=c{i-1,j-r+1}; end end if l1==1 for j=1:a c{k+1,j}=c{k,j}; end else p1=find(mp