信息论综合性实验报告 Huffman编码及译码 代码

Xx大学yy学院

综合性设计性实验报告专业班级：学号：姓名：实验所属课程：信息论与编码技术实验室（中心）:信息科学与工程学院软件中心指导教师：实验完成时间：2012年12月9日一、设计题目：Huffman编码及译码二、实验内容及要求：＜一＞实验内容：对所给的字符串进行huffman的编译码；译码对应原始序列，在将编码进行移位操作时，再进行译码输出，得出误码率。＜二＞实验要求：自己设计一段信源序列，利用Huffman编码对其进行编码，然后利用相应的译方法进行译码，同时考察译码错误对后续序列带来的影响。三、实验过程（详细设计）：＜一＞huffman编码原理：Huffman编码是一种紧致编码，但编码序列的码并非是唯一的。它是根据源数据各信号发生的概率进行编码，在源数据中出现的概率越大的信号，分配的码字越短；出现概率越小的信号，其码字越长，从而达到用尽可能少的码字表示源数据的目的。Huffman编码的步骤如下：设信源X有m个符号（消息），信源概率分布如下：X』气,七，…,门〔P12，…,P〕（1）把信源X中的消息按概率从大到小的”顺序排列；（2）把最后两个出现概率最小的消息合并成一个消息，从而使信源的消息数减少，并同时再按信源符号（消息）出现的概率从大到小排列；（3）重复上述2个步骤，直到信源最后为一个序列只有一个1；（4）将被整合的消息分别赋予1和0,并对最后的两个消息也相应地赋予1和0._（5）通过以上步骤即可完成编码操作。＜一＞huffman译码原理：通过在刚开始生成的随机编码序列，得到列出的01序列与源字符串一一对应，就完成了译码。而对错位后的编码序列，我只是只错位了前两个进行译码，效果不是很明虹＜三＞算法设计：1、编码部分：(1)主函数主要用于调用前面所编写的各个函数模块，按照主函数(主函数代码如下)所列出来的调用顺序，进行一一叙述。function[]=huffmanmain()disp('请输入待编码序列');s=input('','s');%调用概率统计函数，输出各码元的概率分布矩阵；pro=getpro(s);%调用生成huffmantree函数，输出基本树，及完整huffmantree；[HuffmanTree,pro2]=huffmantree(pro);%调用编码函数，输出码表，编码序歹。平均码长，信息熵，编码效率；[Codenumber,huffmantable,Code2]=huffmanencode221(HuffmanTree,pro2,s);%调用译码函数，输出译码序列以及误码率；decodenumber=huffmandecode221(Codenumber,huffmantable,Code2,pro2,s);%调用函数，使编码序列中的01错位Codenumber1=yiweicodenumber(Codenumber);%调用译码函数，对错位后的编码序列进行译码decodenumber=huffmandecode(Codenumber1,huffmantable,Code2,pro2,s);(2)通过编写函数pro=getpro(s)函数来完成对字符串中的各字符的统计，并列出其概率分布矩阵，返回pro矩阵，其主要代码如下：foi=1:b%进行概率计算；forj=1:aifS(i)==s(j)c(i)=c(i)+1;elsecontinue;end;end;en;dpro=c./a;(3)由Huffman编码要求，得到的概率分布矩阵要按照从大到小得顺序来排列，所以需要编写函数来得到顺序排列的概率分布矩阵。我们需要从pro(1,:)中找到两个最小的概率值，所以需要编写找出两个最小值的函数[min1,min2]=getmin(tree),其中tree是在进行Huffman编码过程中产生的Huffman树(包含pro信息，具体下面介绍)，并且在min1与min2中若两者值相等，则在pro中概率序号在前的概率值赋予min1，概率序号在后的概率值赋予min2,详细说明见其下面的代码注释；此部分函数代码主要如下：LL=length(pro1);构建基础二叉树[p1,p2]=sort(pro1,'descend');pro2=zeros(2,LL);pro2(1,:)=p1;pro2(2,:)=p2;n0=size(pro2,2);n1=ceil(log2(n0));%二叉树的深度；n=LL;tree=ones(6,2*n-1);%建立其6*2*n-1的单位1矩阵，用以存储二叉树中各个结点，父节点，以及各个结点的编号；tree(1,:)=1:(2*n-1);%用以编号并存储二叉树中的结点；tree(5,(n+1):end)=0;%用以存放其根结点；tree(2,1:n)=pro2(1,:);%用以存放概率分布;tree(6,1:n)=pro2(2,:);%用以存放每个概率对应的符号的下标；tree(6,n+1:end)=0;disp('基本树形式：')；disp(tree);%显示构建其的基本树形式；%对概率分布矩阵进行运算，每次进行最小两个值相加，其和赋予其中一个，另外一个置1，重复操作，%将其每一次输出的结果存于s1矩阵中，至最后两个概率和为1结束；s1=ones(n-1,2*n-1);s1(1,:)=sort(tree(2,:));fori=2:ns1(i,:)=[s1(i-1,1)+s1(i-1,2),1,s1(iT,3:2*nT)];s1(i,:)=sort(s1(i,:));end;%对基础二叉树进行操作，完整构造；m1=0;m2=0;s2=tree(2,:);%将tree(2,:)中的概率分布赋予s2矩阵中，在不改变tree(2,:)中概率分布，方便对其操作；fori=(n+1):(2*n-1);min1=find(s2==s1(i-n,1));%从tree(2，：)中找对应于$1矩阵中每一行的最小的两个概率值的下标;%为避免tree(2,:)中出现两个相同的最小值，将进行如下判断并操作；iflength(min1)==1m1=min1;min2=find(tree(2,:)==s1(i-n,2));m2=min2(1);elsem1=min1(1,1);m2=min1(1,2);end;(4)在以上的代码中，主要用到了二叉树的构建，其详细说明如下：通过tree=ones(6,2*n-1)语句来构造二叉树。声明一个tree(6,x)结构的树型结点，一个结点包括有6个变量存储单元。其中tree(1,x)记录该结点的编号；tree(2,x)记录该结点的概率值；tree(3,x)记录该结点的父结点编号；tree(4,x)记录该结点是左结点还是右结点(其中左结点为“0”，右结点为“1”)；tree(5,x)记录该结点是否为根结点标志(该结点为根结点记为“1”，否则决为“0”)；tree(6,x)记录该结点的字符，x为pro中源字符经过筛选后的下标数，其余值赋为零。如上代码所示，基本树的构建以及另建立一个与之大小相同的矩阵，存储每一次运算后的所找出的最小的两个概率值。然后对建立好的huffman树进行遍历，遍历的时候从tree(6，：)中第一值开始，逐一的把tree(2,:)中的概率值所对应的编码一一找出来，赋予huffmantable矩阵中然后逐一输出；以下是主要代码部分：%遍历二叉树，生成码表huffmantable;fori=1:len1;%循环完成len1个符号的编码；k=pro(2,i);key=1;m=find(HuffmanTree(6,1:len1)==k);while(HuffmanTree(5,m)~=1)%判断是否遍历至U根结点；Code(key)=HuffmanTree(4,m);key=key+1;m=HuffmanTree(3,m);%指向父节点；endlc=length(Code);huffmantable(i,1:lc)=fliplr(Code);%将Code矩阵中的编码左右翻转，完成倒序排列；Code2=[Code2,lc];%将各个码元的编码长度赋予矩阵Code2;enddisp('码表如下：');%显示码表，即只输出矩阵huffmantable中非-1的部分；Code4=[];fori=1:len1%显示其码表；disp(a1(pro(2,i)));flag=1;while(huffmantable(i,flag)~=-1)Code4(flag)=huffmantable(i,flag);flag=flag+1;end;Code4,disp'码长='),Code2(i)end;(5)通过以上生成的码表，然后遍历源字符串与unique之后的字符串，找出其下标并对应输出码表中对应的编码序列，这样源字符串的编码就完成了，以下是编码部分的主要代码：%%通过码元与待编码的序列一一比较，输出huffmantable中对应的编码；Codenumber=[];fori=1:len2forj=1:len1ifa1(j)==a2(i)v=find(HuffmanTree(6,:)==j);flag=1;while(huffmantable(v,flag)~=-1)Code1(flag)=huffmantable(v,flag);flag=flag+1;Sumnumber=Sumnumber+1;end;Codenumber(Sumnumber-flag+2:Sumnumber)=[Code1(1:flag-1)];end;2、译码部分：对于译码部分所用到的部分主要是编码时生成的码表以及huffmantree，在进行编码的时候，通过筛选后的源字符串的字符序列的下标，与码表中的每

行相对应的原则，遍历编码序列；在遍历的时候，通过码表中各行的码长，控制遍历的长度，与每行中的码表进行比较，输出相对应的字符，即完成了译码。以下是主要代码部分：while(flag~=-1)fori=1:lxk=Code2(i);while(ZF(1:k)==huffmantable(i,1:k))decodenumber=[decodenumber,mm(i)];ZF=ZF(k+1:end);endendflag=ZF(1);end3、错位后重新译码：通过函数调用，改变编码序列中的前两个值，即是0的变为1，是1的变为0，然后再进行重新译码输出，观察其变化。其主要代码如下：fori=1:2ifCodenumber(i)==0Codenm=1;elseCodenumber(i)=0;end;end;Codenumber1=Codenumber;disp('错位后的编码序列：')；Codenumber1四、测试及设计分析：＜一＞实验测试结果：实验的测试结果如下图所示，在CommandWindow中输入调用后王函数huffmanmain()，在提示说明下输入字符串：CommandWindow-+■□*「NewtoMATLAB?WatchthisWideesee口号mo%orreadGetting请输入待编码序列skdshsfhsdjdsjksdfhjks0.18750.06250.12500.12500.12500.3750基本树形式：Columns1through71.00002.GOOD3.00004.00005.00006.00007.00000.37500.18750.12500.12500.12500.06251.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00000

CommandWindow-+■,'.i'1NewtoMATLAB?WatchthisWidgseeE）辑mcis,orreadGettingStarted,哈夫曼树如下：Columns1through71.00002.00003.00004.00005.00006.00007.00000.37500.18750.12500.12500.12500.06250.187510.00009.00007.00008.00008.00007.00009.000001.0000Q1.000001.0000000000006.00001.00003.00004.00005.00002.00000Colijjnns8through11码长二ans=2Code4二g1ans=Coded=01L码长二ans=码长二3113=Code4二101Coluimts12through22000101Columiis23through33110111Columiis34through39101000编码效率：N二0.9676译码序列如下：skdshsfhsdjdsjks原始序列如下：skdshsfhsdjdsjks错位后的编码序列WCodeniimber1=Columns1through11000101Columns12through2200010110000100011001010000ColiJjms34through39101000译码序列如下；1skdshsfhsdjdsjks原始序列如下；skdshsfhsdjdsjks＜二＞实验分析：通过上述图示可以得出其码表，各码元的码长，平均码长，信息熵，编码效率，译码，以及错位后的编码和再一次的译码输出结果。而且，在设计编码算法的时候，参考了其二叉树的建立，遍历算法；编写函数模块，译码的时候，参考了同学的算法，完成了编码。五、思路及附码：＜一＞实验思路：在设计算法的时候，运用二叉树的构建、遍历，再结合所学的MATLAB编程知识来进行编码。在整个编写的过程中，首先要清楚其流程，然后通过对其逐一的编写函数模块，逐一的调试，最后整合到一个主函数调用中，而在整个编码过程中，最大的困难就是对其进行遍历的时候，清楚其原理是关键。＜二＞实验的附代码：主函数调用function[]=huffman221()disp('请输入待编码序列');s=input('','s');%调用概率统计函数，输出各码元的概率分布矩阵；pro=getpro221(s);%调用生成huffmantree函数，输出基本树，及完整huffmantree；[HuffmanTree,pro2]=huffmantree221(pro);%调用编码函数，输出码表，编码序列，平均码长，信息熵，编码效率；[Codenumber,huffmantable,Code2]=huffmanencode221(HuffmanTree,pro2,s);%调用译码函数，输出译码序列以及误码率；decodenumber=huffmandecode221(Codenumber,huffmantable,Code2,pro2,s);%通过构建二叉树，遍历huffman树，从而得到其对应的码表；%pro1：各码元概率分布矩阵，pro2:各码元按倒序排列后的顺序以及对应之前的位置；编码生成概率分布矩阵%完成对输入的序列进行各个码元的概率统计；%s:待编码序列，S：所含的码元序列functionpro=getpro221(s)pro=[];a=length(s);S=unique(s);b=length(S);c=zeros(1,b);%用以存放个序列中各个码元的个数；%进行概率计算；fori=1:bforj=1:aifS(i)==s(j)c(i)=c(i)+1;elsecontinue;end;end;end;pro=c./a;disp(S);disp(pro);构建huffmantreefunction[HuffmanTree,pro2]=huffmantree221(pro1%构建基础二叉树LL=length(pro1);[p1,p2]=sort(pro1,'descend');pro2=zeros(2,LL);pro2(1,:)=p1;pro2(2,:)=p2;n0=size(pro2,2);n1=ceil(log2(n0));%二叉树的深度；n=LL;tree=ones(6,2*n-1);%建立其6*2*n-1的单位1矩阵，用以存储二叉树中各个结点，父节点，以及各个结点的编号；tree(1,:)=1:(2*n-1);%用以编号并存储二叉树中的结点；tree(5,(n+1):end)=0;%用以存放其根结点；tree(2,1:n)=pro2(1,:);%用以存放概率分布；tree(6,1:n)=pro2(2,:);%用以存放每个概率对应的符号的下标；tree(6,n+1:end)=0;disp('基本树形式：')；disp(tree);%显示构建其的基本树形式；%对概率分布矩阵进行运算，每次进行最小两个值相加，其和赋予其中一个，另外一个置1，重复操作，%将其每一次输出的结果存于s1矩阵中，至最后两个概率和为1结束；s1=ones(n-1,2*n-1);s1(1,:)=sort(tree(2,:));fori=2:ns1(i,:)=[s1(i-1,1)+s1(i-1,2),1,s1(i-1,3:2*n-1)];s1(i,:)=sort(s1(i,:));end;%对基础二叉树进行操作，完整构造；m1=0;m2=0;s2=tree(2,:);%将tree(2,:)中的概率分布赋予s2矩阵中，在不改变tree(2,:)中概率分布，方便对其操作；fori=(n+1):(2*n-1);min1=find(s2==s1(i-n,1));%从tree(2，：)中找对应于s1矩阵中每一行的最小的两个概率值的下标;%为避免tree(2,:)中出现两个相同的最小值，将进行如下判断并操作；iflength(min1)==1m1=min1;min2=find(tree(2,:)==s1(i-n,2));m2=min2(1);elsem1=min1(1,1);m2=min1(1,2);end;tree(2,i)=tree(2,m1)+tree(2,m2);s2(i)=tree(2,m1)+tree(2,m2);s2(m1)=-1;s2(m2)=-1;tree(5,i)=1;tree(3,m1)=i;tree(3,m2)=i;tree(4,m1)=1;tree(4,m2)=0;tree(5,m1)=0;tree(5,m2)=0;endHuffmanTree=tree;disp('哈夫曼树如下：');disp(HuffmanTree);end%完成构成完整的基本树，形成huffmantree，并对其遍历，得到码表，通过码表对序列进行编码，并求其平均码长，信息熵，编码效率；%HuffmanTree哈夫曼树，pro码元概率分布矩阵，S，待编码序列；编码序列function[Codenumber,huffmantable,Code2]=huffmanencode221(HuffmanTree,pro,bit)p=pro;a1=unique(bit);a2=bit;len1=length(a1);%码元序列的长度；len2=length(a2);%所要编码序列的长度；a3=zeros(1,len2);%生成与编码序列长度一样的零矩阵，用以存放编码对应的下标；Code=[];%存放其遍历一个码元所对应的编码；Code2=[];%记录各个码元的码长；Lastnumber=1;Sumnumber=0;%累积计算编码总长度；huffmantable=-ones(len1,len1);%建立len1*len1的单位负矩阵，用以存放其码表；%遍历二叉树，生成码表huffmantable;fori=1:len1;%循环完成len1个符号的编码；k=pro(2,i);key=1;m=find(HuffmanTree(6,1:len1)==k);while(HuffmanTree(5,m)~=1)%判断是否遍历到根结点；Code(key)=HuffmanTree(4,m);key=key+1;m=HuffmanTree(3,m);%指向父节点；endlc=length(Code);huffmantable(i,1:lc)=fliplr(Code);%将Code矩阵中的编码左右翻转，完成倒序排列；Code2=[Code2,lc];%将各个码元的编码长度赋予矩阵Code2;end%显示码表，即只输出矩阵huffmantable中非-1的部分；disp('码表如下：');Code4=[];fori=1:len1%显示其码表；disp(a1(pro(2,i)));flag=1;while(huffmantable(i,flag)~=-1)Code4(flag)=huffmantable(i,flag);flag=flag+1;end;Code4,disp('码长='),Code2(i)end;%%通过码元与待编码的序列一一比较，输出huffmantable中对应的编码；Codenumber=[];fori=1:len2forj=1:len1ifa1(j)==a2(i)v=find(HuffmanTree(6,:)==j);flag=1;while(huffmantable(v,flag)~=-1)Code1(flag)=huffmantable(v,flag);flag=flag+1;Sumnumber=Sumnumber+1;end;Codenumber(Sumnumber-flag+2:Sumnumber)=[Code1(1:flag-1)];end;end;end;disp('编码如下：');disp(Codenumber);%计算其平均码长；PJ_Code=pro(1,:)*Code2';%计算其信息熵；HX=0;fori=1:len1HX=HX-pro(1,i)*log2(pro(1,i));end;%计算其编码效率；N=HX/PJ_Code;disp('平均码长：