信息论编码课程设计.doc

课程设计20122013学年第一学期专业： 计算机科学与技术 学号： 姓名： 陈玉剑 课程设计名称： 信息论与编码课程设计 设计题目： 哈夫曼编码的分析与实现 完成期限：自 2012 年 10 月 19 日至 2012 年 10 月 24 日一设计目的1、深刻理解信源编码的基本思想与目的；2、理解哈夫曼编码方法的基本过程与特点；3、提高综合运用所学理论知识独立分析和解决问题的能力；4、使用MATLAB或其他语言进行编程。二设计内容 假设已知一个信源的各符号概率，编写适当函数，对其进行哈夫曼编码，得出M进制码字，平均码长和编码效率，总结此编码方法的特点和应用。三设计要求1、编写的函数要有通用性；2、信源可以自由选择，符号信源与图像信源均可。四设计条件计算机、MATLAB或其他语言环境五参考资料1曹雪虹，张宗橙.信息论与编码.北京：清华大学出版社，2007.2王慧琴.数字图像处理.北京：北京邮电大学出版社，2007.摘 要哈夫曼编码(Huffman Coding)是一种编码方式，也是可变字长编码(VLC)的一种。这种方法完全依据字符出现的概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作哈夫曼编码。对于M进制哈弗曼编码，为了提高编码效率，就要使长码的符号数量尽量少、概率尽量小，所以应使合并的信源符号位于缩减信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码。本文将采用三进制哈夫曼编码作为例子来诠释M进制哈夫曼编码。在三进制哈夫曼编码中，得出码字、平均码长和编码效率，构造哈夫曼树，沿着根节点到叶节点从左到右依次为0、1、2，保证平均码长最小。在本文中采用Visual C+6.0进行编程，此程序中具有输入字符集大小和权值大小，构造哈夫曼树，并对用户输入的字符串进行编码等功能。关键词：哈弗曼编码；信源；哈夫曼树；Visual C+6.0；目 录1课题描述12设计原理13 设计过程23.1软件介绍23.1.1 Visual C+ 6.0简介23.1.2主要部分33.2设计内容44编码程序分析及其结果6总 结14参考文献151课题描述在这个信息量爆炸的时代，凡是能载荷一定信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码。为此，必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字最短。能获得最佳码的编码方法主要有：香农（Shannon）、费诺（Fano）、哈夫曼（Huffman）编码等。哈夫曼(Huffman)编码是一种常用的压缩编码方法，是Huffman于1952年为压缩文本文件建立的。它的基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。哈夫曼编码是哈夫曼树的一个应用，是一种最优的前缀技术，然而其存在的不足却制约了它的直接应用。首先，其解码时间为O(lavg)，其中lavg为码字的平均长度；其次，更为重要的是，解码器需要知道哈夫曼编码树的结构，因而编码器必须为解码器保存或传输哈夫曼编码树。对于小量数据的压缩而言，这是很大的开销。因而，应用哈夫曼编码的关键是如何降低哈夫曼编码树的存储空间。目前流行的很多压缩方法都是用了该技术，如GZIB、ZLIB、PNC等。2设计原理对于多进制哈夫曼编码，为了提高编码效率，就要是长码的符号数量尽量少、概率尽量小，所以信源符号数量最好满足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”，将其合并，结果得到一个只包含(n1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。3将缩减信源S1的符号仍按概率从大到小顺序排列，此后每次合并3个信源符号，得到只含(n3)个符号的缩减信源S2。4重复上述步骤，直至最后，此时所剩符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。3 设计过程3.1软件介绍3.1.1 Visual C+ 6.0简介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)著称。这些特征明显缩短程序编辑、编译及连结的时间花费，在大型软件计划上尤其显著。3.1.2主要部分1Developer Studio 图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+的一个壳子而已。这一点请切记！ 2MFC从理论上来讲，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。 3Platform SDK这才是Visual C+和整个Visual Studio的精华和灵魂，虽然我们很少能直接接触到它。大致说来，Platform SDK是以Microsoft C/C+编译器为核心（不是Visual C+，看清楚了），配合MASM，辅以其他一些工具和文档资料。上面说到Developer Studio没有编译程序的功能，那么这项工作是由谁来完成的呢？是CL，是NMAKE，和其他许许多多命令行程序，这些我们看不到的程序才是构成Visual Studio的基石。3.2设计内容例：对如下单符号离散无记忆信源编三进制哈夫曼码。这里：m=3，n=8令k=3，m+k(m1)=9，则 s=9n=98=1所以第一次取ms=2个符号进行编码。由计算可得：平均码长为： （3.1）信息率为：（3.2）编码效率为：（3.3）可见：哈夫曼的编码效率相当高，对编码器的要求也简单得多。编码过程如下：表1 哈夫曼编码信源符号概率缩减信源码字码长0.40.090100.22201210 1.012010.181020.11120.11220.072120.062220.0520030.042013001212102图2 哈夫曼树 4编码程序及其分析/*哈夫曼编码*#include <iostream.h>#include <math.h>#include <string.h>#include <stdio.h>#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 Probability;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(); /排序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; /平均码长double 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 temp2="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,"",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_back(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:Huffman_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->RightSubtree=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 =NULL;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，生成一个新节点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的“中”子树，将来赋予码元“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->Next=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; /新节点的概率为三者之和strcpy(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->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->CodeLength=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,TreePointer->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);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_3:Huffman_Coding()Huffman_Code(HuffTree);/编码结果分析void CHuffman_3:Huffman_CodeAnalyzing()/(1):平均码长for(int i=0;i<ISNumber;i+)AvageCodeLength+=ISarrayi.Probability*ISarrayi.CodeLength;/(2):信息率int L=1; /单符号时，L=1int m=3; /三进制编码，m=3InformationRate=AvageCodeLength/L*(log(m)/log(2);/(3):编码效率double Hx=0;for(int j=0;j<ISNumber;j+) /求信源熵Hx+=-ISarrayj.Probability*log(ISarrayj.Probability)/log(2);CodeEfficiency=Hx/InformationRate;/显示结果void CHuffman_3:Huffman_Display()cout<<"编码结果："<<endl;for(int i=0;i<ISNumber;i+)cout<<"'"<<ISarrayi.InformationSign<<"'"<<": "<<ISarrayi.Code<<endl;cout<<endl;cout<<"平均码长："<<AvageCodeLength<<endl<<endl;cout<<"信息率 ："<<InformationRate<<endl<<endl;cout<<"编码效率："<<CodeEfficiency<<endl<<endl;/释放资源void CHuffman_3: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();图3 程序运行结果总 结本次课程设计是以三进制哈夫曼编码来诠释多进制哈夫曼编码，其实不论是几进制的哈夫曼编码，只要掌握了编码的原理，是非常简单的。通过这次课程设计，我又重新的将信息论编码与设计的教材翻看了一遍，在网上也搜到了不少相关的知识，知识有提升不少。在这次课程设计中，最让人难懂的就是C+的编程，让我找了不少相关的书籍，上网查阅了不少的程序，对以前学过的编程又进一步巩固和提高了。在编程中，要涉及到编制哈夫曼树，平均码长，编码效率，信息率，信源熵。而且在程序中还要使用到一些函数，例如“for”、“ceil”函数等。哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码。哈夫曼编码在具体实用时，设备较复杂。在编码器中需要增加缓冲寄存器，因为每个信源符号所对应的码符号长度不一，负责会造成输入和输出不能保持平衡。参考文献1曹雪虹，张宗橙.信息论与编码.北京：清华大学出版社，2007.2王慧琴.数字图像处理.北京：北京邮电大学出版社，2007.3刘宏.C+程序设计教程.武汉：武汉大学出版社，2005.4杨永国，张冬明.Visual C+6.0实用教程.北京：清华大学出版社，2007.