信息论与编码实验报告讲解(共19页)

1、精选优质文档-倾情为你奉上信息论与编码实验报告实验课程名称 ： 赫夫曼编码 （二进制与三进制编码） 专 业 信息与计算科学班 级 信息与计算科学1班 学生姓名 李林钟 学 号 49 指导老师 王老师 一、实验目的利用赫夫曼编码进行通信可以大大提高通信利用率，缩短信息传输时间，降低传输成本。赫夫曼编码是信源编码中最基本的编码方法。l 理解赫夫曼编码，无论是二进制赫夫曼编码，还是m进制赫夫曼编码，都要理解其编码原理和编码步骤。l 回顾无失真信源编码定理，理解无失真编码的基本原理和常用编码方法。l 掌握二进制赫夫曼编码和m进制赫夫曼编码的基本步骤，能计算其平均码长，编码效率等。l 应用二进制赫夫曼编

2、码或m进制赫夫曼编码处理简单的实际信源编码问题。二、实验环境与设备1、操作系统与编程软件：windows操作系统，cfree5.0， Visual C+ 6.0。2、编程语言：C语言以及C+语言 三、实验内容1. 二进制赫夫曼编码原理及步骤：（1）信源编码的计算设有N个码元组成的离散、无记忆符号集，其中每个符号由一个二进制码字表示，信源符号个数n、信源的概率分布P=p(si),i=1,.,n。且各符号xi的以li个码元编码，在变长字编码时每个符号的平均码长为 ；信源熵为： ；唯一可译码的充要条件： ； 其中m为码符号个数，n为信源符号个数，Ki为各码字长度。（2）二元霍夫曼编码规则 （1）将信

3、源符号依出现概率递减顺序排序。 （2）给两个概率最小的信源符号各分配一个码位“0”和“1”，将两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含（n-1）个信源符号的新信源。称为信源的第一次缩减信源，用s1 表示。（3）将缩减信源 s1 的符号仍按概率从大到小顺序排列，重复步骤(2)，得到只含（n-2）个符号的缩减信源s2。（4）重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号 的概率之和必为 1，然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。专心-专注-专业(3).算法基本步骤描述得到信源序列 输出得出信源序

4、列个数得出信源序列的概率输出计算信源符号熵输出信源符号的赫弗曼编码平均码长输出输出编码效率输出码方差(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”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概

5、率，或者在新添加一个信源符号，令其概率为0，则个分配一个码位“0”、“1”和“2”，将其合并，结果得到一个只包含(n1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。3将缩减信源S1的符号仍按概率从大到小顺序排列，此后每次合并3个信源符号，得到只含(n3)个符号的缩减信源S2。4重复上述步骤，直至最后，此时所剩符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。(2).编码及注解（见附页2）(3).例题：对如下单符号离散无记忆信源编三进制赫夫曼码。这里：m=3，n=8令k=3，m+k(m1)=9，则 s=9n=98=1所以第一次取ms

6、=2个符号进行编码。由计算可得：平均码长为： （3.1）信息率为：（3.2）编码效率为：（3.3）(4).验证结果截图： 四.实验总结：用C语言实现二进制赫夫曼编码对信源无失真编码。由于课本知识点的不太理解，一点都不知道编码的过程，后来通过阅读<<信息论与编码>>课本、网上查阅资料，最后才对本次设计有了一定的理解，详细理解了赫夫曼的具体编码过程。经过理解，发现这种编码其实挺简单的，最重要的是怎样用程序把他实现，这对我们的编程能力也是一次考验。设计要求中要求计算信源熵，这又考察了现代通信原理的知识。以C+语言实现三进制赫夫曼编码来诠释多进制赫夫曼编码，其实不论是几进制的赫

7、夫曼编码，只要掌握了编码的原理，是非常简单的。通过这次课程设计，我又重新的将信息论编码与设计的教材翻看了一遍，在网上也搜到了不少相关的知识，知识有提升不少。在这次课程设计中，最让人难懂的就是C+的编程，让我找了不少相关的书籍，上网查阅了不少的程序，对以前学过的编程又进一步巩固和提高了。在编程中，要涉及到编制赫夫曼树，平均码长，编码效率，信息率，信源熵。通过同学，网上查阅资料，终于得到解决，虽然仍有一些问题，但是大体上自己能编程出来，是对自己的考验。而且由网上得知：赫夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码。赫夫曼编码在具体实

8、用时，设备较复杂。在编码器中需要增加缓冲寄存器，因为每个信源符号所对应的码符号长度不一，负责会造成输入和输出不能保持平衡。对于自己来说，编程能力尚有欠缺，自主编程能力较差，希望以后多加学习，掌握基础语言的编程基础。附页1：#include<stdio.h>#include<string.h>#include<math.h>#define MAX 100/定义全局变量h存放信息熵double h=0;/定义结构体用于存放信源符号，数目及概率typedef struct/不同的字符char SOURCECODE;/不同字符出现的次数int NUM;/不同字符出现

9、的概率double PROBABILITY; /赫夫曼编码符号int CodeMAX;int start;/赫夫曼树的父结点int parent;/赫夫曼树的左右子结点int lchild;int rchild;/赫夫曼编码的长度int lengthofhuffmancode;Hcode;Hcode INFORMATIONMAX;/该函数用来求信源所包含的符号，以及不同符号出现的次数和概率int Pofeachsource(char informationsourceMAX,int a)int i,j=1,m,flag=0;char temp;/预先存入第一个字符，便于与后面的字符进行比较/统

10、计不同的字符存入结构体数组中/利用flag标签来标记每个字符是否出现过，若出现过标记为1，否则置为零INFORMATION0.SOURCECODE=informationsource0;for(i=1;i<a;i+) for(m=0;m<i;m+)flag=0;if(informationsourcem=informationsourcei)flag=1;break;if(flag=1)continue;else INFORMATIONj+.SOURCECODE=informationsourcei;INFORMATIONj.SOURCECODE='0'printf

11、("信源符号数为:%dn",j);/统计相同的字符出现的次数/每做一个字符出现次数的统计都将结构体数组里的NUM置为零for(i=0;i<j;i+) INFORMATIONi.NUM=0;for(m=0;m<a;m+)if(informationsourcem=INFORMATIONi.SOURCECODE)INFORMATIONi.NUM+;/统计每个字符出现的概率for(i=0;i<j;i+) INFORMATIONi.PROBABILITY=(float)INFORMATIONi.NUM/a;/将每个不同字符出现的次数概率都显示出来for(i=0;i

12、<j;i+)printf("The NUM and PROBABILITY of Code'%c'is %d and %.3fn",INFORMATIONi.SOURCECODE,INFORMATIONi.NUM,INFORMATIONi.PROBABILITY);return j;/求信源符号的熵void H(int a)int i;for(i=0;i<a;i+)h+=(-1)*(INFORMATIONi.PROBABILITY)*(log(INFORMATIONi.PROBABILITY)/log(2);/赫夫曼编码函数void Huffma

13、n(int a)Hcode cd;int i,j,m=0,lm=0,p,c;double min,lmin;/顺序初始化每个信源父子结点为-1 for(i=0;i<a;i+) INFORMATIONi.parent=-1; INFORMATIONi.lchild=-1; INFORMATIONi.lchild=-1; /循环构造Huffman树 for(i=0;i<a-1;i+) /min,lmin中存放两个无父结点且结点权值最小的两个结点 min=lmin=MAX; /找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树 for (j=0;j<a+i;j+) i

14、f(INFORMATIONj.PROBABILITY<min)&&(INFORMATIONj.parent=-1) lmin=min; lm=m; min=INFORMATIONj.PROBABILITY; m=j; else if (INFORMATIONj.PROBABILITY<lmin)&&(INFORMATIONj.parent=-1) lmin=INFORMATIONj.PROBABILITY; lm=j; /设置找到的两个子结点 m、lm 的父结点信息 INFORMATIONm.parent=a+i; INFORMATIONlm.par

15、ent=a+i; INFORMATIONa+i.PROBABILITY=INFORMATIONm.PROBABILITY+INFORMATIONlm.PROBABILITY;INFORMATIONa+i.parent=-1; INFORMATIONa+i.lchild=m; INFORMATIONa+i.rchild=lm; for (i=0;i<a;i+) cd.start=a-1; c=i; p=INFORMATIONc.parent; while(p!=-1) /* 父结点存在 */ if(INFORMATIONp.lchild=c) cd.Codecd.start=1; else

16、 cd.Codecd.start=0; cd.start-; /* 求编码的低一位 */ c=p; p=INFORMATIONc.parent; /* 设置下一循环条件 */ /保存求出的每个叶结点的赫夫曼编码和编码的起始位 for(j=cd.start+1;j<m;j+) INFORMATIONi.Codej=cd.Codej; INFORMATIONi.start=cd.start; main()/定义存放信源符号的数组char informationsourceMAX;int i,j,m;double averageofhuffmancode=0.0,Eita,cV=0.0;pri

17、ntf("please input the source of information:");for(i=0;i+)scanf("%c",&informationsourcei);if(informationsourcei='n')break;informationsourcei='0'printf("信源序列为:");/显示已输入的一串信源符号puts(informationsource);/返回不同信源符号的数目m=Pofeachsource(informationsource,i);/求信

18、源的符号熵H(m);printf("信源的符号熵:H(X)=%.3f(比特/符号)n",h);Huffman(m);/输出已保存好的所有存在编码的赫夫曼编码 for(i=0;i<m;i+) printf("%c's Huffman code is: ",INFORMATIONi.SOURCECODE); for(j=INFORMATIONi.start+1;j<m;j+) printf("%d",INFORMATIONi.Codej);INFORMATIONi.lengthofhuffmancode=m-INFOR

19、MATIONi.start-1; printf("n"); /求赫夫曼编码的平均码长和编码效率for(i=0;i<m;i+)averageofhuffmancode+=INFORMATIONi.PROBABILITY*INFORMATIONi.lengthofhuffmancode;printf("赫夫曼编码的平均码长为:%lf(码元/信源符号)n",averageofhuffmancode);Eita=h/averageofhuffmancode;printf("赫夫曼编码的编码效率为:%lfn",Eita);/求赫弗曼编码的

20、码方差for(i=0;i<m;i+)cV+=INFORMATIONi.PROBABILITY*INFORMATIONi.lengthofhuffmancode*INFORMATIONi.lengthofhuffmancode;cV-=averageofhuffmancode*averageofhuffmancode;printf("赫弗曼编码的码方差为：%lfn",cV);附页2#include <iostream.h>#include <math.h>#include <string.h>#include <stdio.h&

21、gt;#include <stdlib.h>#include <vector> /为了使用vector容器using namespace std; /vector属于std命名域，因此使用全局命名域方式struct Huffman_InformationSource /信源类型 char InformationSign10; /信源符号double Probability; /概率char Code10; /编码结果 int CodeLength; /码长;struct HuffNode /赫夫曼树的节点类型char InformationSign10;double P

22、robability;HuffNode *LeftSubtree,*middleSubtree,*RightSubtree,*Next;char Code10;int CodeLength;class CHuffman_3 /三进制赫夫曼编码public:CHuffman_3() /初始化ISNumber=0;AvageCodeLength=0.0;InformationRate=0.0;CodeEfficiency=0.0;CHuffman_3()DestroyBTree(HuffTree);void Huffman_Input(); /输入信息void Huffman_Sort(); /排

23、序void Huffman_Tree(); /构造赫夫曼树void Huffman_Coding(); /生成赫夫曼编码void Huffman_CodeAnalyzing(); /结果分析void Huffman_Display(); /显示结果信息void DestroyBTree(HuffNode *TreePointer); /释放资源private:vector<Huffman_InformationSource>ISarray; /声明ISarray数组，初始时为空int ISNumber; /符号个数double AvageCodeLength; /平均码长doubl

24、e InformationRate; /信息率double CodeEfficiency; /编码效率HuffNode * HuffTree; /赫夫曼树private:void Huffman_Code(HuffNode *TreePointer);/输入信源信息如果需要添加信源信息在这里修改即可void CHuffman_3:Huffman_Input()Huffman_InformationSource temp1="A",0.40,"",0;ISarray.push_back(temp1);Huffman_InformationSource te

25、mp2="B",0.18,"",0;ISarray.push_back(temp2);Huffman_InformationSource temp3="C",0.10,"",0;ISarray.push_back(temp3);Huffman_InformationSource temp4="D",0.10,"",0;ISarray.push_back(temp4);Huffman_InformationSource temp5="E",0.07,&quo

26、t;",0;ISarray.push_back(temp5);Huffman_InformationSource temp6="F",0.06,"",0;ISarray.push_back(temp6);Huffman_InformationSource temp7="G",0.05,"",0;ISarray.push_back(temp7);Huffman_InformationSource temp8="H",0.04,"",0;ISarray.push_bac

27、k(temp8);ISNumber=ISarray.size();/按概率“从大到小”排序：void CHuffman_3:Huffman_Sort()Huffman_InformationSource temp;int i,j;for(i=0;i<ISNumber-1;i+)for(j=i+1;j<ISNumber;j+)if(ISarrayi.Probability<ISarrayj.Probability)temp=ISarrayi;ISarrayi=ISarrayj;ISarrayj=temp;/基于ISarray数组构造赫夫曼树void CHuffman_3:Huf

28、fman_Tree()int i;HuffNode *ptr1,*ptr2,*ptr3,*ptr4,*temp1,*temp2;/（1）：基于数组，创建单向链表ptr1=new HuffNode;strcpy(ptr1->InformationSign,ISarray0.InformationSign);ptr1->Probability=ISarray0.Probability;strcpy(ptr1->Code,ISarray0.Code); ptr1->LeftSubtree=NULL;ptr1->middleSubtree =NULL;ptr1->R

29、ightSubtree=NULL;ptr1->Next=NULL; HuffTree=ptr1; /赋给数据成员HuffTreefor(i=1;i<ISNumber;i+)ptr2=new HuffNode;strcpy(ptr2->InformationSign,ISarrayi.InformationSign);ptr2->Probability=ISarrayi.Probability;strcpy(ptr2->Code,ISarrayi.Code); ptr2->LeftSubtree=NULL;ptr2->middleSubtree =NUL

30、L;ptr2->RightSubtree=NULL;ptr2->Next=ptr1;ptr1=ptr2;/结果：链表的表头为数组的最小元素。HuffTree=ptr1; /使HuffTree指向链表头/（2）：基于链表，构造赫夫曼树int k; /树的层次int s; /需要添加的无用符号的数目。k=ceil(double)(ISNumber-3)/(3-1); /“3”：表示三进制 /ceil函数：向上取整； /floor函数：向下取整s=3+k*(3-1)-ISNumber;if(s=1) /第一次取m-s=3-1=2个符号/合并概率最小的二个节点ptr1、ptr2，生成一个新

31、节点ptr4：ptr2=ptr1->Next;ptr4=new HuffNode;strcpy(ptr4->InformationSign,"*");/新节点的符号为“*”ptr4->Probability=ptr1->Probability+ptr2->Probability; /新节点的概率为二者之和strcpy(ptr4->Code,""); ptr4->LeftSubtree =NULL;ptr4->middleSubtree=ptr1; /最小的节点ptr1成为ptr4的“中”子树，将来赋予码元“

32、1”ptr4->RightSubtree=ptr2;/次小的节点ptr2成为ptr4的“右”子树，将来赋予码元“0”HuffTree=ptr2->Next; /指向下一个节点/重新排序：temp1=HuffTree;while(temp1&&(ptr4->Probability>temp1->Probability)temp2=temp1;temp1=temp1->Next;ptr4->Next=temp1; /插在当前节点temp1之前if(temp1=HuffTree)HuffTree=ptr4;else temp2->Nex

33、t=ptr4; /插在temp2节点之后ptr1=HuffTree;while(ptr1->Next)/合并概率最小的三个节点ptr1、ptr2，生成一个新节点ptr4：ptr2=ptr1->Next;ptr3=ptr2->Next;ptr4=new HuffNode;strcpy(ptr4->InformationSign,"*");/新节点的符号为“*”ptr4->Probability=ptr1->Probability+ptr2->Probability+ptr3->Probability; /新节点的概率为三者之和s

34、trcpy(ptr4->Code,""); ptr4->LeftSubtree=ptr1;/最小的节点ptr1成为ptr4的“左”子树，将来赋予码元“2”ptr4->middleSubtree=ptr2/次小的节点ptr2成为ptr4的“中”子树，将来赋予 “1”ptr4->RightSubtree=ptr3;/次次小的节点ptr3成为ptr4的“右”子树，将来赋予 “0”HuffTree=ptr3->Next;temp1=HuffTree;while(temp1&&(ptr4->Probability>temp1-

35、>Probability)temp2=temp1;temp1=temp1->Next;ptr4->Next=temp1; /插在当前节点temp1之前if(temp1=HuffTree)HuffTree=ptr4;else temp2->Next=ptr4; /插在temp2节点之后ptr1=HuffTree;/释放：ptr1=NULL;ptr2=NULL;ptr3=NULL;ptr4=NULL;temp1=NULL;temp2=NULL;/设置根节点：strcpy(HuffTree->Code,"");HuffTree->CodeLen

36、gth=0;/生成赫夫曼码：void CHuffman_3:Huffman_Code(HuffNode *TreePointer)if (TreePointer = NULL)return;char tempstr10=""if(!TreePointer->LeftSubtree&&!TreePointer->middleSubtree&&!TreePointer->RightSubtree)for(int i=0;i<ISNumber;i+)if(strcmp(ISarrayi.InformationSign,Tre

37、ePointer->InformationSign)=0)strcpy(ISarrayi.Code,TreePointer->Code);ISarrayi.CodeLength=TreePointer->CodeLength;return;return;if(TreePointer->LeftSubtree)/生成左子树编码：strcpy(tempstr,TreePointer->Code);strcat(tempstr,"2");strcpy(TreePointer->LeftSubtree->Code,tempstr);Tree

38、Pointer->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->middleSubt

39、ree->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_3:Huffman_Coding()H