信息论与编码课程设计哈夫曼编码的分析与实现.doc

信息论与编码课程设计哈夫曼编码的分析与实现

27
2020年4月19日
文档仅供参考，不当之处，请联系改正。

吉林建筑大学
电气与电子信息工程学院
信息理论与编码课程设计报告

设计题目： 哈夫曼编码的分析与实现
专业班级： 电子信息工程 101
学生姓名：
学 号：
指导教师： 吕卅 王超
设计时间： .11.18－ .11.29

教师评语：

成绩 评阅教师 日期

一、设计的作用、目的
《信息论与编码》是一门理论与实践密切结合的课程,课程设计是其实践性教学环节之一，同时也是对课堂所学理论知识的巩固和补充。其主要目的是加深对理论知识的理解，掌握查阅有关资料的技能，提高实践技能，培养独立分析问题、解决问题及实际应用的能力。
经过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法
二、设计任务及要求
经过课程设计各环节的实践，应使学生达到如下要求：
1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；
2. 掌握哈夫曼编码/费诺编码方法的基本步骤及优缺点；
3. 深刻理解信道编码的基本思想与目的，理解线性分组码的基本原理与编码过程；
4. 能够使用MATLAB或其它语言进行编程，编写的函数要有通用性。
三、设计内容
一个有8个符号的信源X，各个符号出现的概率为：

编码方法：先将信源符号按其出现的概率大小依次排列，并取概率最小的字母分别配以0和1两个码元（先0后1或者先1后0，以后赋值固定），再将这两个概率相加作为一个新字母的概率，与未分配的二进制符号的字母重新排队。并不断重复这一过程，直到最后两个符号配以0和1为止。最后从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即为对应的码字。
哈夫曼编码方式得到的码并非唯一的。在对信源缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减中的排序将会导致不同码字，但不同的排序将会影响码字的长度，一般讲合并的概率放在上面，这样可获得较小的码方差。
四、设计原理
4.1哈夫曼编码步骤
（1）将信源消息符号按照其出现的概率大小依次排列为

（2）取两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新的概率，与未分配的二进制符号的字母重新排队。
（3）对重新排列后的两个最小符号重复步骤（2）的过程。
（4）不断重复上述过程，知道最后两个符号配以0和1为止。
（5）从最后一级开始，向前返回得到的各个信源符号所对应的码元序列，即为相应的码字。

4.2哈夫曼编码特点
哈夫曼编码是用概率匹配的方法进行信源匹配方法进行信源。它的特点是：
（1）哈夫曼的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分应用了短码。
（2）缩减信源的最后两个码字总是最后一位不同，从而保证了哈夫曼编码是即时码。
（3）哈夫曼编码所形成的码字不是唯一的，但编码效率是唯一的，在对最小的两个速率符号赋值时能够规定大的为“1”，小得为“0”，如果两个符号的出现概率相等时，排列时无论哪个在前都能够，因此哈夫曼所构造的码字不是唯一的，对于同一个信息源，无论上述的顺序如何排列，她的平均码长是不会改变的，因此编码效率是唯一的。
（4）只有当信息源各符号出现的概率很不平均的时候，哈夫曼编码的效果才明显。
（5）哈夫曼编码必须精确的统计出原始文件中每个符号出现频率，如果没有这些精确的统计将达不到预期效果。哈夫曼编码一般要经过两遍操作 ，第一遍进行统计，第二遍产生编码，因此编码速度相对慢。另外实现电路复杂，各种长度的编码的编译过程也是比较复杂的，因此解压缩的过程也比较慢。
（6）哈夫曼编码只能用整数来表示单个符号，而不能用小数，这很大程度上限制了压缩效果。哈夫曼所有位都是合在一起的，如果改动其中一位就能够使其数据变得面目全非。
五、设计步骤
5.1以框图形式画出哈夫曼编码过程（哈夫曼编码要求构建哈夫曼树）。
表1 哈夫曼编码
信源
编码
概率
编码过程
码字
码长
X1
0.4
0.4 0.4 0.4 0.4 0.4 0.6 0 1.0
0.18 0.18 0.19 0.23 0.37 0 0.4 1
0.1 0.13 0.18 0.19 0 0.23 1
0.1 0.1 0.13 0 0.18 1
0.09 0.1 0 0.1 1
0.07 0 0.09 1
0.06 1

0
1
1
1
X2
0.18
001
3
X3
0.1
011
3
X4
0.1
0000
4
X5
0.07
0100
4
X6
0.06
0101
4
X7

0.05

00010

5

X8

0.04
00011

5

哈夫曼树：
给定n个实数w1，w2，．．．．．．，wn（n2），求一个具有n个结点的二叉数，使其带权路径长度最小。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。能够证明哈夫曼树的WPL是最小的。
（1） 根据与n个权值{w1,w2…wn}对应的n个结点构成具有n棵二叉树的森林F={T1,T2…Tn},其中第i棵二叉树Ti(1 i n)都只有一个权值为wi的根结点，其左、右子树均为空。
（2） 在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、右子树，且置新树的根结点的权值为其左、右子树上根结点权值之和。
（3）从F中删除构成新树的那两棵，同时把新树加入F中。
（4）重复第（2）和第（3）步，直到F中只含有一棵为止，此树便为Huffman树。

图1哈夫曼树
5.2计算平均码长、编码效率、冗余度。
平均码长为：
==0.4×1+0.18×3+0.1×3+0.1×4+0.07×4+0.06×4+
0.05×5+0.04×5=2.61（码元/符号）
信源熵为：
-(0.4log0.4+0.18log0.18+0.1log0.1+
0.1log0.1+0.07+log0.07+0.06log0.06+0.05log0.05+0.04log0.04)
=2.55bit/符号
信息传输速率为：
R===0.977bit/码元
编码效率为：
===0.977
冗余度为：
=1-=1-0.977=0.023
六、哈夫曼编码的实现
6.1软件介绍
Visual C++ 6.0，简称VC或者VC6.0，是微软推出的一款C++编译器，将“高级语言”翻译为“机器语言（低级语言）”的程序。Visual C++是一个功能强大的可视化软件开发工具。自1993年Microsoft公司推出Visual C++1.0后，随着其新版本的不断问世，Visual C++已成为专业程序员进行软件开发的首选工具。Visual C++6.0由Microsoft开发, 它不但是一个C++ 编译器，而且是一个基于Windows操作系统的可视化集成开发环境（integrated development environment，IDE）。Visual C++6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导Class Wizard等开发工具。 这些组件经过一个名为Developer Studio的组件集成为和谐的开发环境。Microsoft的主力软件产品。Visual C++是一个功能强大的可视化软件开发工具。
Visual C++6.0以拥有“语法高亮”，自动编译功能以及高级除错功能而著称。比如，它允许用户进行远程调试，单步执行等。还有允许用户在调试期间重新编译被修改的代码，而不必重新启动正在调试的程序。其编译及创立预编译头文件(stdafx.h)、最小重建功能及累加连结(link)著称。这些特征明显缩短程序编辑、编译及连结的时间花费，在大型软件计划上特别显著。
（1）Developer Studio这是一个集成开发环境，我们日常工作的99%都是在它上面完成的，再加上它的标题赫然写着“Microsoft Visual C++”，因此很多人理所当然的认为，那就是Visual C++了。其实不然，虽然Developer Studio提供了一个很好的编辑器和很多Wizard，但实际上它没有任何编译和链接程序的功能，真正完成这些工作的幕后英雄后面会介绍。我们也知道，Developer Studio并不是专门用于VC的，它也同样用于VB，VJ，VID等Visual Studio家族的其它同胞兄弟。因此不要把Developer Studio当成Visual C++， 它充其量只是Visual C++的一个壳子而已。这一点请切记！
（2）MFC
从理论上来讲，MFC也不是专用于Visual C++，Borland C++，C++Builder和Symantec C++同样能够处理MFC。同时，用Visual C++编写代码也并不意味着一定要用MFC，只要愿意，用Visual C++来编写SDK程序，或者使用STL，ATL，一样没有限制。不过，Visual C++原来就是为MFC打造的，Visual C++中的许多特征和语言扩展也是为MFC而设计的，因此用Visual C++而不用MFC就等于抛弃了Visual C++中很大的一部分功能。可是，Visual C++也不等于MFC。
（3）Platform SDK
这才是Visual C++和整个Visual Studio的精华和灵魂，虽然我们很少能直接接触到它。大致说来，Platform SDK是以Microsoft C/C++编译器为核心（不是Visual C++，看清楚了），配合MASM，辅以其它一些工具和文档资料。上面说到Developer Studio没有编译程序的功能，那么这项工作是由谁来完成的呢？是CL，是NMAKE，和其它许许多多命令行程序，这些我们看不到的程序才是构成Visual Studio的基石。
6.2 编程
//**哈夫曼编码**
#include <iostream.h>
#include <math.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;
struct Huffman_InformationSource
{
char InformationSign[10]；
double Probability；
char Code[10]；
int CodeLength;；
};
struct HuffNode
{
char InformationSign[10]；
double Probability；
HuffNode *LeftSubtree,*middleSubtree,*RightSubtree,*Next；
char Code[10]；
int CodeLength；
}；
class CHuffman_2
{
public:
CHuffman_2()
{
ISNumber=0；
AvageCodeLength=0.0；
InformationRate=0.0；
CodeEfficiency=0.0；
Redundancy=0.0；
}
CHuffman_2()
{
DestroyBTree(HuffTree)；
}
void Huffman_Input()；
void Huffman_Sort()；
void Huffman_Tree()；
void Huffman_Coding()；
void Huffman_CodeAnalyzing()；
void Huffman_Display()；
void DestroyBTree(HuffNode *TreePointer)；
private:
vector<Huffman_InformationSource>ISarray；
int ISNumber；
double AvageCodeLength；
double InformationRate；
double CodeEfficiency；

HuffNode * HuffTree；
private：
void Huffman_Code(HuffNode *TreePointer);
}；
//输入信源信息
void CHuffman_2::Huffman_Input()
{
Huffman_InformationSource temp1={"x1",0.40,"",0};
ISarray.push_back(temp1);
Huffman_InformationSource temp2={"x2",0.18,"",0}；
ISarray.push_back(temp2);
Huffman_InformationSource temp3={"x3",0.10,"",0};
ISarray.push_back(temp3);
Huffman_InformationSource temp4={"x4",0.10,"",0};
ISarray.push_back(temp4);
Huffman_InformationSource temp5={"x5",0.07,"",0};
ISarray.push_back(temp5);
Huffman_InformationSource temp6={"x6",0.06,"",0};
ISarray.push_back(temp6);
Huffman_InformationSource temp7={"x7",0.05,"",0};
ISarray.push_back(temp7);
Huffman_InformationSource temp8={"x8",0.04,"",0};
ISarray.push_back(temp8);
ISNumber=ISarray.size();
}
//按概率“从大到小”排序
void CHuffman_2::Huffman_Sort()
{
Huffman_InformationSource temp;
int I,j;
for(i=0;i<ISNumber-1;i++)
for(j=i+1;j<ISNumber;j++)
if(ISarray[i].Probability<ISarray[j].Probability)
{
temp=ISarray[i]；
ISarray[i]=ISarray[j];
ISarray[j]=temp;
}
}
void CHuffman_2::Huffman_Tree()
{
int I;
HuffNode *ptr1,*ptr2,*ptr3,*ptr4,*temp1,*temp2;
ptr1=new HuffNode;
strcpy(ptr1->InformationSign,ISarray[0].InformationSign);
ptr1->Probability=ISarray[0].Probability;
strcpy(ptr1->Code,ISarray[0].Code);
ptr1->LeftSubtree=NULL;
ptr1->middleSubtree =NULL;
ptr1->RightSubtree=NULL;
ptr1->Next=NULL;
HuffTree=ptr1;
for(i=1;i<ISNumber;i++)
{
ptr2=new HuffNode;
strcpy(ptr2->InformationSign,ISarray[i].InformationSign);
ptr2->Probability=ISarray[i].Probability;
strcpy(ptr2->Code,ISarray[i].Code);
ptr2->LeftSubtree=NULL;
ptr2->middleSubtree =NULL;
ptr2->RightSubtree=NULL;
ptr2->Next=ptr1;
ptr1=ptr2;
}
HuffTree=ptr1;
int k;
int s;
k=ceil((double)(ISNumber-3)/(3-1));
s=3+k*(3-1)-ISNumber;
if(s==1)
{
ptr2=ptr1->Next;
ptr4=new HuffNode;
strcpy(ptr4->InformationSign,"*");
ptr4->Probability=ptr1->Probability+ptr2->Probability;
strcpy(ptr4->Code,"");
ptr4->LeftSubtree =NULL;
ptr4->middleSubtree=ptr1;
ptr4->RightSubtree=ptr2;
HuffTree=ptr2->Next;
temp1=HuffTree;
while(temp1&&(ptr4->Probability>temp1->Probability))
{
temp2=temp1;
temp1=temp1->Next;
}
ptr4->Next=temp1;
if(temp1==HuffTree)
HuffTree=ptr4;
else
temp2->Next=ptr4;
ptr1=HuffTree;
}
while(ptr1->Next)
{
//合并概率最小的结点
ptr2=ptr1->Next;
ptr3=ptr2->Next;
ptr4=new HuffNode;
strcpy(ptr4->InformationSign,"*");
ptr4->Probability=ptr1->Probability+ptr2->Probability
+ptr3->Probability;
strcpy(ptr4->Code,"");
ptr4->LeftSubtree=ptr1;
ptr4->middleSubtree=ptr2;
ptr4->RightSubtree=ptr3;
HuffTree=ptr3->Next;
temp1=HuffTree;
while(temp1&&(ptr4->Probability>temp1->Probability))
{
temp2=temp1;
temp1=temp1->Next;
}
ptr4->Next=temp1;
if(temp1==HuffTree)
HuffTree=ptr4;
else
temp2->Next=ptr4;
ptr1=HuffTree;
}
//释放：
ptr1=NULL;
ptr2=NULL;
ptr3=NULL;
ptr4=NULL;
temp1=NULL;
temp2=NULL;
strcpy(HuffTree->Code,"");
HuffTree->CodeLength=0;
}
//生成哈夫曼码
void CHuffman_2::Huffman_Code(HuffNode *TreePointer)
{
if (TreePointer == NULL)
return;
char tempstr[10]="";
if(!TreePointer->LeftSubtree&&!TreePointer->middleSubtree
&&!TreePointer->RightSubtree)
{
for(int i=0;i<ISNumber;i++)
if(strcmp(ISarray[i].InformationSign,TreePointer->InformationSign)==0)
{
strcpy(ISarray[i].Code,TreePointer->Code);
ISarray[i].CodeLength=TreePointer->CodeLength;
return;
}
return;
}
if(TreePointer->LeftSubtree)
{
strcpy(tempstr,TreePointer->Code);
strcat(tempstr,"2");
strcpy(TreePointer->LeftSubtree->Code,tempstr);
TreePointer->LeftSubtree->CodeLength=TreePointer->CodeLength+1;

Huffman_Code(TreePointer->LeftSubtree);
}
if(TreePointer->middleSubtree)
{
strcpy(tempstr,TreePointer->Code);
strcat(tempstr,"1");
strcpy(TreePointer->middleSubtree->Code,tempstr);
TreePointer->middleSubtree->CodeLength=TreePointer->CodeLength+1;

Huffman_Code(TreePointer->middleSubtree);
}
if(TreePointer->RightSubtree)
{
strcpy(tempstr,TreePointer->Code);
strcat(tempstr,"0");
strcpy(TreePointer->RightSubtree->Code,tempstr);
TreePointer->RightSubtree->CodeLength=TreePointer->CodeLength+1;

Huffman_Code(TreePointer->RightSubtree);
}
}
void CHuffman_2::Huffman_Coding()
{
Huffman_Code(HuffTree);
}
//编码结果
void CHuffman_2::Huffman_CodeAnalyzing()
{
for(int i=0;i<ISNumber;i++)
AvageCodeLength+=ISarray[i].Probability*ISarray[i].CodeLength;
int L=1;
int m=2; /
InformationRate=AvageCodeLength/L*(log(m)/log(2));
double Hx=0;
for(int j=0;j<ISNumber;j++)
Hx+=-ISarray[j].Probability*log(ISarray[j].Probability)/log(2);
CodeEfficiency=Hx/InformationRate;
Redundancy=1- CodeEfficiency;
}
void CHuffman_2::Huffman_Display()
{
cout<<"码字："<<endl;
for(int i=0;i<ISNumber;i++)
{
cout<<"\'"<<ISarray[i].InformationSign<<"\'"<<": "<<ISarray[i].Code<<endl;
}
cout<<endl;
cout<<"平均码长："<<AvageCodeLength<<endl<<endl;
cout<<"编码效率："<<CodeEfficiency<<endl<<endl;
cout<<"冗余度："<< Redundancy <<endl<<endl;
}
void CHuffman_2::DestroyBTree(HuffNode *TreePointer)
{
if (TreePointer!= NULL)
{
DestroyBTree(TreePointer->LeftSubtree);
DestroyBTree(TreePointer->middleSubtree);
DestroyBTree(TreePointer->RightSubtree);
delete TreePointer;
TreePointer = NULL;
}
}
void main()
{
CHuffman_3 YYY;
YYY.Huffman_Input();
YYY.Huffman_Sort();
YYY.Huffman_Tree();
YYY.Huffman_Coding();
YYY.Huffman_CodeAnalyzing();
YYY.Huffman_Display();
}
6.3 运行结果及分析

图2 运行结果

运行结果分析：
从运行结果上能够看出，该结果与理论计算一致，而且能够看出哈夫曼编码的特点：
（1）哈夫曼的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分应用了短码。
（2）缩减信源的最后两个码字总是最后一位不同，从而保证了哈夫曼编码是即时码。
（3）每次缩减信源的最长两个码字有相同的码长。
这三个特点保证了所得的哈夫曼码一定是最佳码。因此哈夫曼是一种应用广泛而有效的数据压缩技术。利用哈夫曼编码进行通信能够大大提高信道利用率，加快信息传输速度，降低传输成本。数据压缩的过程称为编码，解压的过程称为译码。进行信息传递时，发送端经过一个编码系统对待传数据（明文）预先编码，而接受端将传来的数据（密文）进行译码。要求数据这样一个简单的哈夫曼编码译码器。
在进行哈夫曼编码时，为了得到码方差最小的码，应使合并的信源符号位于缩减信源序列尽可能高的。
七、体会及建议
在这次课程设计中，经过对程序的编写，调试和运行，使我更好的掌握了哈夫曼树等数据结构方面的基本知识和各类基本程序问题的解决方法，熟悉了各种调用的数据类型，在调试和运行过程中，加深我对程序运行的环境了解和熟悉的程度，同时也提高了我对程序调试分析的能力和对错误纠正的能力。
这次信息论与编码的程序设计，对于我来说是一个挑战。我对数据结构的学习在程序的设计中也有所体现。课程设计是培养学生综合运用所学知识，发现问题、提出问题、分析问题和解决问题的过程，锻炼学生的逻辑思维能力和实践能力，是对学生实际工作能力的具体训练和考察过程。在整个课程程序中，我们充分应用和调用各个程序模块，从而部分实现了此次程序设计的所应该有的功能。就是我在课程设计是比较成功的方面，而在这个过程中，让我感觉收获最大的就是我们都能利用这次课程设计学到很多我们在课本上没有的知识，充分的发挥了我们的主动性，使我们学会了自主学习，和独立解决问题的能力。
很多程序在结构上是独立的，可是本此设计的程序功能不是零散的，它有一个连接是的程序是一个整体，达到这种统一体十分重要，因为这个输出连接是贯穿始终的。
经过翻阅相关书籍，在网上查询资料学习有关哈夫曼编码的实现过程，我实
在是获益匪浅，更加深刻的感觉到哈夫曼编码能够大大提高通信的效率，对于我们通信工程专业来说，学好这门科学是非常重要的，在以后的图像处理和压缩方面这门学科能给我们很大的帮助。同时，学习这门科学也是艰辛的，因为它比较难懂，这不但需要我们发挥我们的聪明才智，还需要我们在不断的实践中领悟。    这次的课程设计，让我体会到了作为一个编程人员的艰辛，一个算法到具体实现，再到应用层面的开发是需要有一个较长的路要走的，不是一朝一夕就能够实现的，而且在编好程序后，编程人员还要花很多时间去完善，过程是心酸的，外人很难能够真正明白。 今后我要更加努力的学习专业知识，提高自我的能力！
这次的程序软件基本上运行成功，能够运用简单的数字告诉程序的操作者下一步该如何进行，使得程序规模相对较小，即功能还不很全面，应用也不很普遍。原来数据结构能够涉及很多知识，而不是枯燥无聊的简单的代码部分而已，利用数据结构方面的知识，我们能够设计出更完善的软件。
总而言之，这次数据结构课程设计让我们感触很深，使我们每个人都了解到学习不应该只局限于课本，因为课本上告诉我们的只是很有限的一部分，只是理论上的死知识，所涉及的范围也是狭窄的。我们若想在有限的范围内学习到无限的知识，就要我们自己懂得争取，懂得自学，懂得充分利用身边的任何资源。
在我们的程序中有一部分查找许多该方面的资料，我竭力将所获得的信息变成自己的资源。我动手上机操作的同时，在了解和看懂的基础上对新学的知识进行改进和创新，可是在我们的程序软件中还有很多的不足，需要加以更新。经过这次课程设计，我们都意识到了自己动手实践的弱势，特别是在编程方面，于是我们知道了计算机的实践操作是很重要的，只有经过上机编程才能充分的了解自己的不足。
经过这次的课程设计，我们深刻意识到自己在学习中的弱点，同时也找到了克服这些弱点的方法，这是在此活动中得到的一笔很大的财富。在以后的时间中，我们应该利用更多的时间去上机实验，多编写程序，相信不久后我们的编程能力都会有很大的提高，能设计出更多的更有创新的软件。同时也感谢老师给我们这次机会，发现自身存在的缺点与不足，从而在以后的大学生活中更好的提升和完善自我。
八、参考文献
[1] 曹雪虹，张宗橙.信息论与编码（第二版）.北京：清华大学出版社.
[2] 吕锋，王虹，刘皓春，苏扬.信息论与编码.北京：人民邮电出版社.
[3] 樊昌信，曹丽娜.通信原理（第六版）.北京：国防工业出版社.
[4] 王慧琴.数字图像处理.北京：北京邮电大学出版社.
[5] 孙丽华. 信息论与纠错编码.电子工业出版社.
[6] 刘宏.C++程序设计教程.武汉：武汉大学出版社，
[7] 杨永国，张冬明.Visual C++6.0实用教程.北京：清华大学出版社，
[8] 严蔚敏，吴伟民.数据结构.北京：清华大学出版社，1997