信息论与编码实验报告讲解.doc
《信息论与编码实验报告讲解.doc》由会员分享，可在线阅读，更多相关《信息论与编码实验报告讲解.doc（19页珍藏版）》请在冰点文库上搜索。
信息论与编码实验报告
实验课程名称：
赫夫曼编码（二进制与三进制编码）
专业信息与计算科学
班级信息与计算科学1班
学生姓名李林钟
学号 2013326601049
指导老师王老师
一、实验目的
利用赫夫曼编码进行通信可以大大提高通信利用率，缩短信息传输时间，降低传输成本。
赫夫曼编码是信源编码中最基本的编码方法。
l理解赫夫曼编码，无论是二进制赫夫曼编码，还是m进制赫夫曼编码，都要理解其编码原理和编码步骤。
l回顾无失真信源编码定理，理解无失真编码的基本原理和常用编码方法。
。
l掌握二进制赫夫曼编码和m进制赫夫曼编码的基本步骤，能计算其平均码长，编码效率等。
l应用二进制赫夫曼编码或m进制赫夫曼编码处理简单的实际信源编码问题。
二、实验环境与设备
1、操作系统与编程软件：
windows操作系统，cfree5.0，VisualC++6.0。
2、编程语言：
C语言以及C++语言
三、实验内容
1.二进制赫夫曼编码原理及步骤：
（1）信源编码的计算
设有N个码元组成的离散、无记忆符号集，其中每个符号由一个二进制码字表示，信源符号个数n、信源的概率分布P={p（si）},i=1,…..,n。
且各符号xi的以li个码元编码，在变长字编码时每个符号的平均码长为；
信源熵为：
；
唯一可译码的充要条件：
；
其中m为码符号个数，n为信源符号个数，Ki为各码字长度。
（2）二元霍夫曼编码规则
（1）将信源符号依出现概率递减顺序排序。
（2）给两个概率最小的信源符号各分配一个码位“0”和“1”，将两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含（n-1）个信源符号的新信源。
称为信源的第一次缩减信源，用s1表示。
（3）将缩减信源s1的符号仍按概率从大到小顺序排列，重复步骤
（2），得到只含（n-2）个符号的缩减信源s2。
（4）重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1，然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。
18
（3）.算法基本步骤描述
得到信源序列
输出
得出信源序列个数
得出信源序列的概率
输出
计算信源符号熵
输出
信源符号的赫弗曼编码
平均码长
输出
输出
编码效率
输出
码方差
（4）.编码及注解（见附页1）
（5）.验证截图:
2.三进制编码：
（1）.三进制赫弗曼编码原理：
对于多进制赫夫曼编码，为了提高编码效率，就要是长码的符号数量尽量少、概率尽量小，所以信源符号数量最好满足n=（m-1）*k+r,其中m为进制数，k为缩减的次数。
设计步骤如下：
[1]将信源符号按概率从大到小的顺序排列，令
p（x1）≥p（x2）≥…≥p（xn）
[2]给两个概率最小的信源符号p（xn-1）和p（xn）各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，或者在新添加一个信源符号，令其概率为0，则个分配一个码位“0”、“1”和“2”，将其合并，结果得到一个只包含（n－1）个信源符号的新信源。
称为信源的第一次缩减信源，用S1表示。
[3]将缩减信源S1的符号仍按概率从大到小顺序排列，此后每次合并3个信源符号，得到只含（n－3）个符号的缩减信源S2。
[4]重复上述步骤，直至最后，此时所剩符号的概率之和必为1。
然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。
（2）.编码及注解（见附页2）
（3）.例题：
对如下单符号离散无记忆信源编三进制赫夫曼码。
这里：
m=3，n=8
令k=3，m+k（m－1）=9，则s=9－n=9－8=1
所以第一次取m－s=2个符号进行编码。
由计算可得：
平均码长为：
（3.1）
信息率为：
（3.2）
编码效率为：
（3.3）
（4）.验证结果截图：
四.实验总结：
用C语言实现二进制赫夫曼编码对信源无失真编码。
由于课本知识点的不太理解，一点都不知道编码的过程，后来通过阅读<<信息论与编码>>课本、网上查阅资料，最后才对本次设计有了一定的理解，详细理解了赫夫曼的具体编码过程。
经过理解，发现这种编码其实挺简单的，最重要的是怎样用程序把他实现，这对我们的编程能力也是一次考验。
设计要求中要求计算信源熵，这又考察了现代通信原理的知识。
以C++语言实现三进制赫夫曼编码来诠释多进制赫夫曼编码，其实不论是几进制的赫夫曼编码，只要掌握了编码的原理，是非常简单的。
通过这次课程设计，我又重新的将信息论编码与设计的教材翻看了一遍，在网上也搜到了不少相关的知识，知识有提升不少。
在这次课程设计中，最让人难懂的就是C++的编程，让我找了不少相关的书籍，上网查阅了不少的程序，对以前学过的编程又进一步巩固和提高了。
在编程中，要涉及到编制赫夫曼树，平均码长，编码效率，信息率，信源熵。
通过同学，网上查阅资料，终于得到解决，虽然仍有一些问题，但是大体上自己能编程出来，是对自己的考验。
而且由网上得知：
赫夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码。
赫夫曼编码在具体实用时，设备较复杂。
在编码器中需要增加缓冲寄存器，因为每个信源符号所对应的码符号长度不一，负责会造成输入和输出不能保持平衡。
对于自己来说，编程能力尚有欠缺，自主编程能力较差，希望以后多加学习，掌握基础语言的编程基础。
附页1：
#include
#include
#include
#defineMAX100
//定义全局变量h存放信息熵
doubleh=0;
//定义结构体用于存放信源符号，数目及概率
typedefstruct{
//不同的字符
charSOURCECODE;
//不同字符出现的次数
intNUM;
//不同字符出现的概率
doublePROBABILITY;
//赫夫曼编码符号
intCode[MAX];
intstart;
//赫夫曼树的父结点
intparent;
//赫夫曼树的左右子结点
intlchild;
intrchild;
//赫夫曼编码的长度
intlengthofhuffmancode;
}Hcode;
HcodeINFORMATION[MAX];
//该函数用来求信源所包含的符号，以及不同符号出现的次数和概率
intPofeachsource（charinformationsource[MAX],inta）
{
inti,j=1,m,flag=0;
chartemp;
//预先存入第一个字符，便于与后面的字符进行比较
//统计不同的字符存入结构体数组中
//利用flag标签来标记每个字符是否出现过，若出现过标记为1，否则置为零
INFORMATION[0].SOURCECODE=informationsource[0];
for（i=1;i for（m=0;m flag=0;
if（informationsource[m]==informationsource[i]）{
flag=1;
break;
}
}
if（flag==1）
continue;
else
INFORMATION[j++].SOURCECODE=informationsource[i];
}
INFORMATION[j].SOURCECODE='\0';
printf（"信源符号数为:
%d\n",j）;
//统计相同的字符出现的次数
//每做一个字符出现次数的统计都将结构体数组里的NUM置为零
for（i=0;i INFORMATION[i].NUM=0;
for（m=0;m if（informationsource[m]==INFORMATION[i].SOURCECODE）
INFORMATION[i].NUM++;
}
//统计每个字符出现的概率
for（i=0;i INFORMATION[i].PROBABILITY=（float）INFORMATION[i].NUM/a;
//将每个不同字符出现的次数概率都显示出来
for（i=0;i printf（"TheNUMandPROBABILITYofCode'%c'is%dand%.3f\n",INFORMATION[i].SOURCECODE,INFORMATION[i].NUM,INFORMATION[i].PROBABILITY）;
returnj;
}
//求信源符号的熵
voidH（inta）{
inti;
for（i=0;i h+=（（-1）*（INFORMATION[i].PROBABILITY）*（log（INFORMATION[i].PROBABILITY）/log
（2）））;
}
}
//赫夫曼编码函数
voidHuffman（inta）
{
Hcodecd;
inti,j,m=0,lm=0,p,c;
doublemin,lmin;
//顺序初始化每个信源父子结点为-1
for（i=0;i{
INFORMATION[i].parent=-1;
INFORMATION[i].lchild=-1;
INFORMATION[i].lchild=-1;
}
//循环构造Huffman树
for（i=0;i{
//min,lmin中存放两个无父结点且结点权值最小的两个结点
min=lmin=MAX;
//找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树
for（j=0;j{
if（（INFORMATION[j].PROBABILITY{
lmin=min;
lm=m;
min=INFORMATION[j].PROBABILITY;
m=j;
}
elseif（（INFORMATION[j].PROBABILITY{
lmin=INFORMATION[j].PROBABILITY;
lm=j;
}
}
//设置找到的两个子结点m、lm的父结点信息
INFORMATION[m].parent=a+i;
INFORMATION[lm].parent=a+i;
INFORMATION[a+i].PROBABILITY=INFORMATION[m].PROBABILITY+INFORMATION[lm].PROBABILITY;
INFORMATION[a+i].parent=-1;
INFORMATION[a+i].lchild=m;
INFORMATION[a+i].rchild=lm;
}
for（i=0;i{
cd.start=a-1;
c=i;
p=INFORMATION[c].parent;
while（p!
=-1）/*父结点存在*/
{
if（INFORMATION[p].lchild==c）
cd.Code[cd.start]=1;
else
cd.Code[cd.start]=0;
cd.start--;/*求编码的低一位*/
c=p;
p=INFORMATION[c].parent;/*设置下一循环条件*/
}
//保存求出的每个叶结点的赫夫曼编码和编码的起始位
for（j=cd.start+1;j{INFORMATION[i].Code[j]=cd.Code[j];}
INFORMATION[i].start=cd.start;
}
}
main（）
{
//定义存放信源符号的数组
charinformationsource[MAX];
inti,j,m;
doubleaverageofhuffmancode=0.0,Eita,cV=0.0;
printf（"pleaseinputthesourceofinformation:
"）;
for（i=0;;i++）{
scanf（"%c",&informationsource[i]）;
if（informationsource[i]=='\n'）
break;
}
informationsource[i]='\0';
printf（"信源序列为:
"）;
//显示已输入的一串信源符号
puts（informationsource）;
//返回不同信源符号的数目
m=Pofeachsource（informationsource,i）;
//求信源的符号熵
H（m）;
printf（"信源的符号熵:
H（X）=%.3f（比特/符号）\n",h）;
Huffman（m）;
//输出已保存好的所有存在编码的赫夫曼编码
for（i=0;i{
printf（"%c'sHuffmancodeis:
",INFORMATION[i].SOURCECODE）;
for（j=INFORMATION[i].start+1;jprintf（"%d",INFORMATION[i].Code[j]）;
INFORMATION[i].lengthofhuffmancode=m-INFORMATION[i].start-1;
printf（"\n"）;
}
//求赫夫曼编码的平均码长和编码效率
for（i=0;i averageofhuffmancode+=INFORMATION[i].PROBABILITY*INFORMATION[i].lengthofhuffmancode;
printf（"赫夫曼编码的平均码长为:
%lf（码元/信源符号）\n",averageofhuffmancode）;
Eita=h/averageofhuffmancode;
printf（"赫夫曼编码的编码效率为:
%lf\n",Eita）;
//求赫弗曼编码的码方差
for（i=0;i cV+=INFORMATION[i].PROBABILITY*INFORMATION[i].lengthofhuffmancode*INFORMATION[i].lengthofhuffmancode;
cV-=averageofhuffmancode*averageofhuffmancode;
printf（"赫弗曼编码的码方差为：
%lf\n",cV）;
}
附页2
#include
#include
#include
#include
#include
#include //为了使用vector容器
usingnamespacestd; ///vector属于std命名域，因此使用全局命名域方式
structHuffman_InformationSource//信源类型
{
charInformationSign[10]; //信源符号
doubleProbability; //概率
charCode[10]; //编码结果
intCodeLength; //码长
};
structHuffNode //赫夫曼树的节点类型
{
charInformationSign[10];
doubleProbability;
HuffNode*LeftSubtree,*middleSubtree,*RightSubtree,*Next;
charCode[10];
intCodeLength;
};
classCHuffman_3 //三进制赫夫曼编码
{
public:
CHuffman_3（） //初始化
{
ISNumber=0;
AvageCodeLength=0.0;
InformationRate=0.0;
CodeEfficiency=0.0;
}
~CHuffman_3（）
{
DestroyBTree（HuffTree）;
}
voidHuffman_Input（）; //输入信息
voidHuffman_Sort（）; //排序
voidHuffman_Tree（）; //构造赫夫曼树
voidHuffman_Coding（）; //生成赫夫曼编码
voidHuffman_CodeAnalyzing（）; //结果分析
voidHuffman_Display（）; //显示结果信息
voidDestroyBTree（HuffNode*TreePointer）; //释放资源
private:
vectorISarray; //声明ISarray数组，初始时为空
intISNumber; //符号个数
doubleAvageCodeLength; //平均码长
doubleInformationRate; //信息率
doubleCodeEfficiency; //编码效率
HuffNode*HuffTree; //赫夫曼树
private:
voidHuffman_Code（HuffNode*TreePointer）;
};
//输入信源信息如果需要添加信源信息在这里修改即可
voidCHuffman_3:
:
Huffman_Input（）
{
Huffman_InformationSourcetemp1={"A",0.40,"",0};
ISarray.push_back（temp1）;
Huffman_InformationSourcetemp2={"B",0.18,"",0};
ISarray.push_back（temp2）;
Huffman_InformationSourcetemp3={"C",0.10,"",0};
ISarray.push_back（temp3）;
Huffman_InformationSourcetemp4={"D",0.10,"",0};
ISarray.push_back（temp4）;
Huffman_InformationSourcetemp5={"E",0.07,"",0};
ISarray.push_back（temp5）;
Huffman_InformationSourcetemp6={"F",0.06,"",0};
ISarray.push_back（temp6）;
Huffman_InformationSourcetemp7={"G",0.05,"",0};
ISarray.push_back（temp7）;
Huffman_InformationSourcetemp8={"H",0.04,"",0};
ISarray.push_back（temp8）;
ISNumber=ISarray.size（）;
}
//按概率“从大到小”排序：
voidCHuffman_3:
:
Huffman_Sort（）
{
Huffman_InformationSourcetemp;
inti,j;
for（i=0;i for（j=i+1;j if（ISarray[i].Probability {
升级会员 