信息论与编码课程设计

建筑大学信息理论与编码课程设计报告设计题目：哈夫曼编码的分析与实现专业班级：电子信息工程101学生：《信息论与编码》是一门理论与实践密切结合的课程，课程设计是其实践性教学环节之一，同时也是对课堂所学理论知识的巩固和补充。其主要目的是加深对理论知识的理解，掌握查阅有关资料的技能，提高实践技能，培养独立分析问题、解决问题及实际应用的能力。通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法二、设计任务及要求通过课程设计各环节的实践，应使学生达到如下要求：1.理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；2.掌握哈夫曼编码/费诺编码方法的基本步骤及优缺点；3.深刻理解信道编码的基本思想与目的，理解线性分组码的基本原理与编码过程；4.能够使用MATLA或其他语言进行编程，编写的函数要有通用性。一个有8个符号的信源X,各个符号出现的概率为：编码方法：先将信源符号按其出现的概率大小依次排列，并取概率最小的字母分别配以0和1两个码元(先0后1或者先1后0,以后赋值固定),再将这两个概率相加作为一个新字母的概率，与未分配的二进制符号的字母重新排队。并不断重复这一过程，直到最后两个符号配以0和1为止。最后从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即为对应的码字。哈夫曼编码方式得到的码并非唯一的。在对信源缩减时，两个概率最小的符号合并后的概率与其他信源符号的概率相同时，这两者在缩减中的排序将会导致不同码字，但不同的排序将会影响码字的长度，一般讲合并的概率放在上面，这样可获得较小的码方差。四、设计原理(1)将信源消息符号按照其出现的概率大小依次排列为(2)取两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新的概率，与未分配的二进制符号的字母重新排队。(3)对重新排列后的两个最小符号重复步骤(2)的过程。(4)不断重复上述过程，知道最后两个符号配以0和1为止。(5)从最后一级开始，向前返回得到的各个信源符号所对应的码元序列，即为相应的码字。哈夫曼编码是用概率匹配的方法进行信源匹配方法进行信源。它的特点是：(1)哈夫曼的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分应(2)缩减信源的最后两个码字总是最后一位不同，从而保证了哈夫曼编码是即时码。(3)哈夫曼编码所形成的码字不是唯一的，但编码效率是唯一的，在对最小的两个速率符号赋值时可以规定大的为“1”,小得为“0”,如果两个符号的出现概率相等时，排列时无论哪个在前都可以，所以哈夫曼所构造的码字不是唯一的，对于同一个信息源，无论上述的顺序如何排列，他的平均码长是不会改变的，所以编码效率是唯一的。(4)只有当信息源各符号出现的概率很不平均的时候，哈夫曼编码的效果才明显。(5)哈夫曼编码必须精确的统计出原始文件中每个符号出现频率，如果没有这些精确的统计将达不到预期效果。哈夫曼编码通常要经过两遍操作，第一遍进行统计，第二遍产生编码，所以编码速度相对慢。另外实现电路复杂，各种长度的编码的编译过程也是比较复杂的，因此解压缩的过程也比较慢。果。哈夫曼所有位都是合在一起的，如果改动其中一位就可以使其数据变得面目全非。5.1以框图形式画出哈夫曼编码过程(哈夫曼编码要求构建哈夫111f0.1/0.23呻00.41/0.190匕231101WPL=(W1*L1+W2*L2+W3*L3+…(4)重复第(2)和第(3)步，直到F中只含有一棵为止，此树便为Huffman树。0000工i15.2计算平均码长、编码效率、冗余度。0.05X5+0.04X5=2.61(码元/符号)0.1log0.1+0.07+log0.07+0.06log0.06+0.05log0.0=0.977bit/码兀=1-=1-0.977=0.六、哈夫曼编码的实现6.1软件介绍VisualC++6.0,简称VC或者VC6.0,是微软推出的一款C++编译器，将“高级语言”翻译为“机器语言(低级语言)”的程序。VisualC++是一个功能强大的可视化软件开发工具。自1993年Microsoft公司推出VisualC++1.0后，随着其新版本的不断问世，VisualC++已成为专业程序员进行软件开发的首选工具。VisualC++6.0由Microsoft开发，它不仅是一个C++编译器，而且是一个基于Windows操作系统的可视化集成开发环境(integrateddevelopmentenvironment,IDE)。VisualC++6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导ClassWizard等开发工具。这些组件通过一个名为DeveloperStudio的组件集成为和谐的开发环境。Microsoft的主力软件产品。VisualC++是一个功能强大的可视化软件开发工具。VisualC++6.0以拥有“语法高亮”,自动编译功能以及高级除错功能而著称。比如，它允许用户进行远程调试，单步执行等。还有允许用户在调试期间重新编译被修改的代码，而不必重新启动正在调试的程序。其编译及创建预编译头文件(stdafx.h)、最小重建功能及累加连结(link)著称。这些特征明显缩短程序编辑、编译及连结的时间花费，在大型软件计划上尤其显著。(1)DeveloperStudio这是一个集成开发环境，我们日常工作的99%都是在它上面完成的，再加上它的标题赫然写着“MicrosoftVisualC++,所以很多人理所当然的认为，那就是VisualC++了。其实不然，虽然DeveloperStudio提供了一个很好的编辑器和很多Wizard,但实际上它没有任何编译和程序的功能，真正完成这些工作的幕后英雄后面会介绍。我们也知道，DeveloperStudio并不是专门用于VC的，它也同样用于VB,VJ,VID等VisualStudio家族的其他同胞兄弟。所以不要把DeveloperStudio当成VisualC++,它充其量只是VisualC++的一个壳子而这一点请切记!从理论上来讲，MFC也不是专用于VisualC++,BorlandC++,C++Builder和SymantecC++同样可以处理MFC同时，用VisualC++编写代码也并不意味着一定要用MFC只要愿意，用VisualC++来编写SDK程序，或者使用STL,ATL,一样没有限制。不过，VisualC++本来就是为MFC丁造的，VisualC++中的许多特征和语言扩展也是为MFC而设计的，所以用VisualC++而不用MFC就等于抛弃了VisualC++中很大的一部分功能。但是，VisualC++也不等于MFC。致说来，PlatformSDK是以MicrosoftC/C++编译器为核心(不是VisualC++,看清楚了),配合HuffNode*LeftSubtree,*middleSubtree,*RightSu{}voidDestroyBTree(HuffNode*TreePointer);private:vector<Huffman_InformationSource>ISarray;inttemp1={"x1",0.40,"",0};ISarray.push_batemp2={"x2",0.18,"",0}ISarray.push_bacyoidCHuffman_2::Huffman_Tree()HuffNode*ptr1,*ptr2,*ptr3,*ptr4,*temp1,*testrcpy(ptr1->InformationSign,ISarray[0].Infoptr1->Probability=ISarstrcpy(ptr1->Code,ISarrastrcpy(ptr2->InformationSign,ISarray[i].Infoptr2->Probability=ISarrstrcpy(ptr2->Code,ISarray[i].Code);ptr2->Leftstrcpy(ptr4->Informatioptr4->Probability=ptr1->Probabilitwhile(temp1&&(ptr4->Probability>temp1->Probabi}Jstrcpy(ptr4->Informatioptr4->Probability=ptr1->Probabiliwhile(temp1&&(ptr4->Probability>temp1->Probabil}}//释放：voidCHuffman_2::Huffman_Code(HuffNode*Trchartempstr[10]="";if(!TreePointer->LeftSubtree&&!TreePointer->middleSubtreefor(inti=0;i<ISNumbif(strcmp(ISarray[i].InformationSign,TreePointer-ISarray[i].CodeLength=TreePstrcpy(tempstr,TreePointstrcat(tempstr,"2");strcpy(TreePointer->LeftSubtree->CTreePointer->LeftSubtree->CodeLength=TreePointer->Co}f(TreePointer->middleSubstrcpy(tempstr,TreePointstrcat(tempstr,"1");strcpy(TreePointer->middleSubtree->CTreePointer->middleSubtree->CodeLength=TreePointer->CoHuffman_Code(TreePostrcpy(tempstr,TreePointer->Code);strcat(tstrcpy(TreePointer->RightSubtree->CoTreePointer->RightSubtree->CodeLength=TreePointer->Co//编码结果voidCHuffman_2::Huffmfor(inti=0;i<ISNumbAvageCodeLength+=ISarray[i].Probability*ISarray[i].CodeLInformationRate=AvageCodefor(intj=0;j<ISNumber;j++)Hx+=-ISarray[j].Probability*log(ISarrayCodeEfficiency=Hx/IyoidCHuffman_2::Huffman_Dcout<<"\'"<<ISarray[i].Informaticout<<"平均码长："<<AvageCodeLength<<endl<<endl;cout<<"编码效率："<<CodeEfficiency<<endl<<endl;JvoidCHuffman_2::DestroyBTree(HuffNode*TreePointer)DestroyBTree(TreePoiDestroyBTree(TreePoCHuffman_3YYY;YYY.Huffman」nput();YYY.Huffman_Coding(码免平均码扶：2*61图2运行结果从运行结果上可以看出，该结果与理论计算一致，并且可以看出哈夫曼编码的特点：(1)哈夫曼的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分(2)缩减信源的最后两个码字总是最后一位不同，从而保证了哈夫曼编码是即时码。这三个特点保证了所得的哈夫曼码一定是最佳码。因此哈夫曼是一种应用广泛而有效的数据压缩技术。利用哈夫曼编码进行通信可以大大提高信道利用率，加快信息传输速度，降低传输成本。数据压缩的过程称为编码，解压的过程称为译码。进行信息传递时，发送端通过一个编码系统对待传数据(明文)预先编码，而接受端将传来的数据(密文)进行译码。要求数据这样一个简单的哈夫曼编码译码器。在进行哈夫曼编码时，为了得到码方差最小的码，应使合并的信源符号位于缩减信源序列尽可七、体会及建议在这次课程设计中，通过对程序的编写，调试和运行，使我更好的掌握了哈夫曼树等数据结构方面的基本知识和各类基本程序问题的解决方法，熟悉了各种调用的数据类型，在调试和运行过程中，加深我对程序运行的环境了解和熟悉的程度，同时也提高这次信息论与编码的程序设计，对于我来说是一个挑战。我对数据结构的学习在程序的设计中也有所体现。课程设计是培养学生综合运用所学知识，发现问题、提出问题、分析问题和解决问题的过程，锻炼学生的逻辑思维能力和实践能力，是对学生实际工作能力的具体训练和考察过程。在整个课程程序中，我们充分应用和调用各个程序模块，从而部分实现了此次程序设计的所应该有的功能。就是我在课程设计是比较成功的方面，而在这个过程中，让我感觉收获最大的就是我们都能利用这次课程设计学到很多我们在课本上没有的知识，充分的发挥了我们的主动性，使我们学会了自主学习，和独立解决问题的能力。很多程序在结构上是独立的，但是本此设计的程序功能不是零散的，它有一个连接是的程序是一个整体，达到这种统一体十分重要，因为这个输出连接是贯穿始终的。通过翻阅相关书籍，在网上查询资料学习有关哈夫曼编码的实现过程，我实在是获益匪浅，更加深刻的感觉到哈夫曼编码能够大大提高通信的效率，对于我们通信工程专业来说，学好这门科学是非常重要的，在以后的图像处理和压缩方面这门学科能给我们很大的帮助。同时，学习这门科学也是艰辛的，因为它比较难懂，这不仅需要我们发挥我们的聪明才智，还需要我们在不断的实践中领悟。这次的课程设计，让我体会到了作为一个编程人员的艰辛，一个算法到具体实现，再到应用层面的开发是需要有一个较长的路要走的，不是一朝一夕就可以实现的，而且在编好程序后，编程人员还要花很多时间去完善，过程是心酸的，外人很难能够真正明白。今后我要更加努力的学习专业知识，提高自我的能力!这次的程序软件基本上运行成功，可以运用简单的数字告诉程序的操作者下一步该如何进行，使得程序规模相对较小，即功能还不