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

里面有完整的实验报告及代码

Xx大学yy学院 综合性设计性实验报告

专 业 班 级：

学 号 ：

姓 名：实验所属课程：实验室(中心)：

指 导 教 师 ：

实验完成时间： 信息论与编码技术 信息科学与工程学院软件中心 2012 年 12 月 9 日

里面有完整的实验报告及代码

一、 设计题目：

Huffman编码及译码

二、 实验内容及要求：

<一>实验内容：对所给的字符串进行huffman的编译码；译码对应原始序列，在将编码

进行移位操作时，再进行译码输出，得出误码率。 <二>实验要求：自己设计一段信源序列，利用Huffman编码对其进行编码，然后利用相

应的译方法进行译码，同时考察译码错误对后续序列带来的影响。

三、 实验过程(详细设计)：

<一> huffman编码原理：

Huffman编码是一种紧致编码，但编码序列的码并非是唯一的。它是根据源数据各信号发生的概率进行编码，在源数据中出现的概率越大的信号，分配的码字越短；出现概率越小的信号，其码字越长，从而达到用尽可能少的码字表示源数据的目的。 Huffman编码的步骤如下：设信源X有m个符号（消息），信源概率分布如下： X x1, x2 ,..., xm p1 2 ,..., pm

（ ）把信源 X 中的消息按概率从大到小的顺序排列；

（2）把最后两个出现概率最小的消息合并成一个消息，从而使信源的消息数减少，并同时再按信源符号（消息）出现的概率从大到小排列；

（3）重复上述 2 个步骤，直到信源最后为一个序列只有一个1； （4）将被整合的消息分别赋予 1 和 0，并对最后的两个消息也相应地赋予 1 和 0. （5）通过以上步骤即可完成编码操作。 <二> huffman译码原理：

通过在刚开始生成的随机编码序列，得到列出的0 1 序列与源字符串一一对应，就完成了译码。而对错位后的编码序列，我只是只错位了前两个进行译码，效果不是很明显。

<三>算法设计：

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); %调用函数，使编码序列中的0 1错位

Codenumber1=yiweicodenumber(Codenumber); %调用译码函数，对错位后的编码

序列进行译码

decodenumber=huffmandecode(Codenumber1,huffmantable,Code2,pro2,s);

（2）通过编写函数pro=getpro(s)函数来完成对字符串中的各字符的统计，并列出其概

率分布矩阵，返回pro矩阵，其主要代码如下： for i=1:b %进行概率计算； for j=1:a

if S(i)==s(j) c(i)=c(i)+1; else continue; end; end; end;

pro=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,:)); for i=2:n

s1(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,:)

中概率分布，方便对其操作；

for i=(n+1):(2*n-1);

min1=find(s2==s1(i-n,1)); %从tree（2，：）中找对应于s1矩阵中每一行的

最小的两个概率值的下标;

%为避免tree(2,:)中出现两个相同的最小值，将进行如下判断并操作; if length(min1)==1 m1=min1;

min2=find(tree(2,:)==s1(i-n,2)); m2=min2(1); else

m1=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;

for i=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); %指向父节点； end

lc=length(Code);

huffmantable(i,1:lc)=fliplr(Code); %将Code矩阵中的编码左右翻

转，完成倒序排列；

Code2=[Code2,lc]; %将各个码元的编码长度赋予矩阵Code2; end

disp('码表如下：'); %显示码表，即只输出矩阵huffmantable中非-1的部分； Code4=[];

for i=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=[]; for i=1:len2 for j=1:len1

if a1(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) for i=1:lx

k=Code2(i);

while(ZF(1:k)==huffmantable(i,1:k)) decodenumber=[decodenumber,mm(i)]; ZF=ZF(k+1:end); end end

flag=ZF(1); end

3、错位后重新译码 ：

通过函数调用，改变编码序列中的前两个值，即是0的变为1，是1的变为0，然后再进行重新译码输出，观察其变化。其主要代码如下：

for i=1:2

if Codenumber(i)==0 Codenm=1;

else Codenumber(i)=0; end; end;

Codenumber1=Codenumber; disp('错位后的编码序列：'); Codenumber1

四、测试及设计分析：

<一>实验测试结果：实验的测试结果如下图所示，在 Command Window 中输入调用后主函数huffmanmain()，在提示说明下输入字符串：

里面有完整的实验报告及代码

里面有完整的实验报告及代码

里面有完整的实验报告及代码

<二>实验分析：通过上述图示可以得出其码表，各码元的码长，平均码长，信息熵，编码效率，译码，以及错位后的编码和再一次的译码输出结果。而且，在设计编码算法的时候，参考了其二叉树的建立，遍历算法；编写函数模块，译码的时候，参考了同学的算法，完成了编码。

五、思路及附码：

<一>实验思路：在设计算法的时候，运用二叉树的构建、遍历，再结合所学的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：所含的码元序列 function pro=getpro221(s) pro=[];

a=length(s); S=unique(s); b=length(S);

c=zeros(1,b); %用以存放个序列中各个码元的个数； %进行概率计算； for i=1:b for j=1:a

if S(i)==s(j) c(i)=c(i)+1; else continue; end; end; end; pro=c./a; disp(S); disp(pro); 构建huffmantree function

[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,:)); for i=2:n

s1(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,:)中概率分布，方便对其操作； for i=(n+1):(2*n-1);

min1=find(s2==s1(i-n,1)); %从

tree（2，：）中找对应于s1矩阵中每一行的最小的两个概率值的下标;

%为避免tree(2,:)中出现两个相同的最小值，将进行如下判断并操作; if length(min1)==1 m1=min1;

min2=find(tree(2,:)==s1(i-n,2)); m2=min2(1); else

m1=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; end

HuffmanTree=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;

for i=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); %指向父节点； end

lc=length(Code);

huffmantable(i,1:lc)=fliplr(Code); %将Code矩阵中的编码左右翻转，完成倒序排列；

Code2=[Code2,lc]; %将各个码元的编码长度赋予矩阵Code2; end

%显示码表，即只输出矩阵huffmantable中非-1的部分；

disp('码表如下：'); Code4=[];

for i=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)

%%通过码元与待编码的序列一一比较，输出huffmantable中对应的编码； Codenumber=[]; for i=1:len2 for j=1:len1 if a1(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;

for i=1:len1

HX=HX-pro(1,i)*log2(pro(1,i)); end;

%计算其编码效率； N=HX/PJ_Code; disp('平均码长：'); PJ_Code

disp('信息熵：'); HX

disp('编码效率：'); N End 译码

%完成对已知编码序列的译码，以及在改变码表中的某一位值得情况下，再一次译码，计算其误码率； %Codenumber:已编码序列； huffmantable:码表；Code2:各码元的码长；pro2：各码元的概率分

里面有完整的实验报告及代码

%s:原始序列；decodenumber： 译码序列； function

decodenumber=huffmandecode221(Codenumber,huffmantable,Code2,pro2,bit) mm=unique(bit); %码元序列 mm=mm(pro2(2,:)); LL=size(Codenumber,2); decodenumber=[];

ZF=[Codenumber,-ones(1,max(Code2))]; for j=1:length(bit) for i=1:lx

while(ZF(1:k)==huffmantable(i,1:k))

decodenumber=[decodenumber,mm(i)]; ZF=ZF(k+1:end); end end

[lx,ly]=size(huffmantable); end

disp('译码序列如下：'); disp(decodenumber); disp('原始序列如下：'); disp(bit); end

六、实验心得体会：

首先，感谢老师这九个周的教学，我学到了很多东西，而且也意识到Matlab所发挥

的作用，尤其是在我们所学的专业---通信工程中随起到的作用，所以一定要严格要求自己，学好这门课程。

其次，在完成这个实验的过程中，遇到了很多问题，虽然最后都逐一的解决了，比如说，在进行编码的时候，参考了其中的一个程序，但不明白其原理，所以只能一点点的通过网上自己查找，熟悉并会运用二叉树的建立，遍历的算法，所以说，在编码的过程中，也是一次深刻的学习过程。再者，在译码的时候，有几次一直出现译码不完整，仔细检查了好几遍，始终发现不了其错误所在，最后，跟同学一起查找，在存码表的矩阵中，每一行所对应的字符出现错误，经过改正，得出了正确结果。

最后，我想说的是，通过学习这门课程，深刻意识到自己要学的东西还有很多，自己已经掌握的就是冰山一角，微乎其微，所以在以后的学习中，我会更进一步的加深对此课程的理解，练习，掌握好这样一种技能，增加自己在未来的求职路上的筹码。