二元霍夫曼编码 - 信息论与编码实验报告

《二元霍夫曼编码 - 信息论与编码实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

计算机与信息工程学院综合性实验报告专业：通信工程年级/班级：2011级2013—2014学年第一学期课程名称信息论与编码指导教师刘艳芳本组成员学号姓名实验地点计科楼111实验时间周五5-6节项目名称二元霍夫曼编码实验类型综合性一、实验目的根据霍夫曼编码的原理，用MATLAB设计进行霍夫曼编码的程序，并得出正确的结果。二、实验仪器或设备1、一台计算机。2、MATLABr2013a。三、二元霍夫曼编码原理1、将信源消息符号按其出现的概率大小依次排列，p1>p2>…>pq2、取两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的概率，从而得到只包含q-1个符号的新信源S1。3、对重排后的缩减信源S1重新以递减次序排序，两个概率最小符号重复步骤(2)的过程。4、不断继续上述过程，直到最后两个符号配以0和1为止。5、从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。四、霍夫曼编码实现程序function[outnum]=lml_huffman(a)%主程序，输入一组概率，输出此组概率的霍夫曼编码%a：一组概率值，如a=[0.20.30.10.4]等%outnum：输出的霍夫曼码，以cell中的字符数组表示ifsum(a)~=1warning('输入概率之和不为“1”，但程序仍将继续运行')end[cho,sequ,i,l]=probality(a);globallmlcode%用于输出霍夫曼码，定义为cell型globalcellnum%用于编码的累加计算cellnum=1;lmlcode=cell(l,1);j=1;%第一部分add_num=char;[l_add]=addnum(add_num,i,j,l);[output,m]=disgress(sequ,i,j,l,l_add); dealnum(output,m);%在全局变量中输出霍夫曼码j=2;%第二部分[l_add]=addnum(add_num,i,j,l);[output,n]=disgress(sequ,i,j,l,l_add);dealnum(output,n);[outnum]=comset(lmlcode,cho(1,:));%将概率和编码进行关联function[output]=addnum(input,i,j,l)%对概率矩阵中每一行最后两个不为0的数进行编码，即在某个编码后添加0,1或空%输出：%input：输入的某个未完成的编码%(i,j):当前检索目标在sequ矩阵中的位置%l:sequ矩阵的列数%PS:sequ矩阵在此函数中未用到%PS：此函数为编码第一步ifj==(l-i)output=[input'0'];elseifj==(l-i+1)output=[input'1'];elseoutput=input;endendfunction[ecode]=comset(code,pro)%将概率和编码进行关联%code：已编成的霍夫曼码%pro：输入的一组概率%ecode：最终完成的码l=length(code);ecode=cell(l,2);fori=1:llang(i)=length(code{i});end[a,b]=sort(lang);fori=1:lecode{i,1}=code{b(i)};ecode{i,2}=pro(i);endfunction[final,a]=dealnum(imput,m)%整理并在全局变量中输出已完成的霍夫曼码%输入：imput：程序运算后的生成cell型矩阵%m：标识数 %输出：final：整理后的霍夫曼码%a：标识数globallmlcodeglobalcellnumifm==1lmlcode{cellnum}=imput;cellnum=cellnum+1;final='';a='';elseifm==2[final1,a1]=dealnum(imput{1,1},imput{1,2});[final2,a2]=dealnum(imput{2,1},imput{2,2});[final3,a3]=dealnum(final1,a1);[final4,a4]=dealnum(final2,a2);final=[final3final4];a=[a3a4];elsefinal=imput;a=m;endendfunction[outnum,p]=findsumother(sequ,i,j,l,add_num)%当前检索目标在sequ(i,j)处为非1时的处理程序，即跳转到下一级进行整理%输入：sequ:概率转移矩阵%(i,j):当前检索目标在sequ矩阵中的位置%l:sequ矩阵的列数%add_num：当前进行的编码%输出：（与disgress类同）%outnum：进行霍夫曼编码，用cell型表示%p：标识数j=l-i+2-sequ(i,j);i=i-1;[add_num1]=addnum(add_num,i,j,l);[outnum,p]=disgress(sequ,i,j,l,add_num1);function[outnum1,outnum2,p,q]=findsumis1(sequ,i,j,l,add_num)%当前检索目标在sequ(i,j)处为1时的处理程序，%即对下一级的最小两概率进行求和移位编码整理%输入：sequ:概率转移%(i,j):当前检索目标在sequ矩阵中的位置%l:sequ矩阵的列数%add_num：当前进行的编码%输出：（与disgress类同） %outnum1&[outnum2：进行霍夫曼编码，用cell型表示%p&q：标识数i=i-1;j1=l-i;j2=l-i+1;[add_num1]=addnum(add_num,i,j1,l);[outnum1,p]=disgress(sequ,i,j1,l,add_num1);[add_num2]=addnum(add_num,i,j2,l);[outnum2,q]=disgress(sequ,i,j2,l,add_num2);function[output,m]=disgress(sequ,i,j,l,add_num)%当前检索目标，累加数，输出下一级霍夫曼码及其个数，此函数被调用次数最多%输入：sequ：概率转移矩阵%(i,j)：当前检索目标在sequ矩阵中的位置%l：sequ矩阵的列数%add_num：当前进行的编码%输出：output：进行霍夫曼编码，用cell型表示%m：标识数%PS：此函数为编码第二步ifi~=1ifsequ(i,j)==1[output1,output2,p,q]=findsumis1(sequ,i,j,l,add_num);output=cell(2);output{1,1}=output1;output{1,2}=p;output{2,1}=output2;output{2,2}=q;m=2;elseifsequ(i,j)~=1[output1,p]=findsumother(sequ,i,j,l,add_num);output=output1;m=p;endendelseoutput=add_num;m=1;end一、实验程序实现方法演示若在commandwindow中输入的概率数组为p=[0.10.150.200.250.30]使用子函数[output,sequ,i,j]=probality(p)对此组概率进行预处理，处理结果如下图所示： 0.30000.30000.45000.55000.25000.25000.30000.45000.20000.25000.25000.15000.20000.1000output图5.1概率数据处理过程简图54114332312221sequ图5.2对图1中数据的转移方式标示图图2标明了对图1中各数据的位置转移过程。图1中每一列最后两个数据标为1，其他数据从下到上依次标为2、3、4...如第一列最后两个数据标为1，则其上依次为2、3、4。故在第二列中sequ(2,3)=1的含义是：output(2,3)=0.25为第一列中标为1的数据转移而来；sequ(2,2)=3的含义是：output(2,2)=0.25为第一列中标为3的数据转移而来；在第三列中sequ(2,3)=3的含义是：output(2,3)=0.3为第二列中标为3的数据转移而来，等等。依据矩阵output及sequ可以得到霍夫曼编码的码树图如下：1111010100010000.550.30.250.30.250.30.250.450.450.10.20.250.20.15010010110011图5.3特定概率数组的编码码树 一、结果分析与总结（1）实验结果分析1、在commandwindow中输入:p=[0.10.150.200.250.30],生成数组p2、之后在commandwindow中输入:[a]=lml_huffman(p),输出结果为：a='00'[0.3000]'01'[0.2500]'11'[0.2000]'100'[0.1500]'101'[0.1000]其中outnum为cell型，第一列为字符型，输出的是霍夫曼码，第二列为输入的概率数组，与第一列中的霍夫曼码相对应。将以上输出结果在下表中统计。表6.1编码分析表信源消息符号ai符号概率p(ai)累加概率Pi=-logp(ai)码字长度li码字a10.301.74200a20.250.32.00201a30.20.552.32211a40.150.752.743100a50.10.93.323101则（2）实验小结1、从实验结果可以看出，霍夫曼编码的效率很高，但是并未达到可以达到100%2、从实验程序可以看出，每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的霍夫曼码，但不会影响码字的平均长度。教师签名：年月日