计算机与信息工程学院综合性实验报告一、实验目的根据霍夫曼编码的原理，用MATLAB设计进行霍夫曼编码的程序，并得出正确的结果。
二、实验仪器或设备1、一台计算机。
2、MATLAB r2013a。
三、二元霍夫曼编码原理1、将信源消息符号按其出现的概率大小依次排列，p1>p2>…>p q2、取两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的概率，从而得到只包含q-1个符号的新信源S1。
3、对重排后的缩减信源S1重新以递减次序排序，两个概率最小符号重复步骤(2)的过程。
4、不断继续上述过程，直到最后两个符号配以0和1为止。
5、从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。
四、霍夫曼编码实现程序function [outnum]=lml_huffman(a)%主程序，输入一组概率，输出此组概率的霍夫曼编码%a：一组概率值，如a=[0.2 0.3 0.1 0.4]等%outnum：输出的霍夫曼码，以cell中的字符数组表示if sum(a)~=1warning('输入概率之和不为“1”，但程序仍将继续运行')end[cho,sequ,i,l]=probality(a);global lmlcode %用于输出霍夫曼码，定义为cell型global cellnum %用于编码的累加计算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：此函数为编码第一步if j==(l-i)output=[input '0'];else if j==(l-i+1)output=[input '1'];elseoutput=input;endendfunction [ecode]=comset(code,pro)%将概率和编码进行关联%code：已编成的霍夫曼码%pro：输入的一组概率%ecode：最终完成的码l=length(code);ecode=cell(l,2);for i=1:llang(i)=length(code{i});end[a,b]=sort(lang);for i=1:lecode{i,1}=code{b(i)};ecode{i,2}=pro(i);endfunction [final,a]=dealnum(imput,m)%整理并在全局变量中输出已完成的霍夫曼码%输入： imput：程序运算后的生成cell型矩阵% m：标识数%输出： final：整理后的霍夫曼码% a：标识数global lmlcodeglobal cellnumif m==1lmlcode{cellnum}=imput;cellnum=cellnum+1;final='';a='';else if m==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=[final3 final4];a=[a3 a4];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：此函数为编码第二步if i~=1if sequ(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;else if sequ(i,j)~=1[output1,p]=findsumother(sequ,i,j,l,add_num);output=output1;m=p;endendelseoutput=add_num;m=1;end五、实验程序实现方法演示若在command window中输入的概率数组为p=[0.1 0.15 0.20 0.25 0.30]使用子函数[output,sequ,i,j]=probality(p)对此组概率进行预处理，处理结果如下图所示：图5.1 概率数据处理过程简图图5.2 对图1中数据的转移方式标示图图2标明了对图1中各数据的位置转移过程。
