信源熵统计与哈夫曼编码

1、信息论与编码课程设计报告设计题目：统计信源嫡与哈夫曼编码专业班级学号学生姓名指导教师教师评分2014年1月26日 目录TOC o 1-5 h z HYPERLINK l bookmark6一、设计任务与要求2 HYPERLINK l bookmark8二、设计思路3 HYPERLINK l bookmark10三、设计流程图4 HYPERLINK l bookmark12四、程序运行及结果5 HYPERLINK l bookmark14五、心得体会6 HYPERLINK l bookmark16参考文献7 HYPERLINK l bookmark18附录：源程序8 一、设计任务与要求要求完成两

2、个题目，1和2选做一题，3、4和5选做一题。1、统计信源爛要求：统计任意文本文件中各字符（不区分大小写）数量，计算字符概率，并计算信源爛。2、判断唯一可译码要求：利用尾随后缀法判断任意输入的码是否为唯一可译码。3、香农编码要求：任意输入消息概率，利用香农编码方法进行编码，并计算信源爛和编码效率。4、费诺编码要求：任意输入消息概率，利用费诺编码方法进行编码，并计算信源爛和编码效率。5、哈夫曼编码要求：任意输入消息概率，利用哈夫曼编码方法进行编码，并计算信源爛和编码效率。 二、设计思路此设计是将统计信源爛与哈夫曼编码结合在一起。程序中采用模块化思想将实现某个功能的程序独立成一个模块，然后在主程序中

3、加以调用。H（X丿表示信源输出后，每个消息（或符号）所提供的平均信息量。统计信源爛模块是程序从键盘中读取用户输入的字母（不区分大小写）或空格，并分别统计出总数N和每个字母、空格出现的次数“以及概率Pg）,然后由公式nt=i可计算出信源爛。哈夫曼是将信源消息符号按其出现的概率大小依次排列，然后取两个概率最小的符号分别配以o和1,并将这两个概率相加作为一个新符号的概率，与未分配码元的符号重新排队。对重排后的两个概率最小符号重复以上的过程。继续上述过程，直到最后两个符号配以o和1为止。从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。哈夫曼编码模块是将各个字符的概率进行排序并写

4、出每一个的码字存放于一个相应的结构体中。哈夫曼编码是可变字长编码的一种，这种编码方法完全依据字符出现的概率來构造平均长度最短的码字，有时称之为最佳编码。它可以充分利用短码，使出现概率高的符号使用短的位序列，而那些很少出现的符号则用较长的位序列。在此次课程设计中先通过所输入的字母和空格进行相应的统计，计算各自的概率，然后选用哈夫曼编码，通过编程运行來进一步感受哈夫曼编码的便利之处。三、设计流程图图1设计流程图 四、程序运行及结果在程序中可以输入字母及空格，对于输入的其他字符程序会给出错误提示。设在程序中输入了字符“ABCDabcd”，则程序输出的结果如下图所示：图2实验结果图 五、心得体会这次的

5、课程设计让我巩固了一个学期的所学，前半部分是求信源爛，后半年部分是考察编码。我们所选取的的实验样本很简单，只有四个字符而且都是等概率出现的，计算信源爛时很简单，使用哈弗曼编码时编码效率达到了100%。真正到我们工作时不会遇到如此简单的项目。这次的课程设计，我们的主要目的是为了巩固所学，复习信源爛的求法和三种编码方法。这次课程设计，我们对香农编码，费诺编码以及哈弗曼编码有了一个更全面的认识。信息论与编码是一门实用性很强的学科，同时也很有针对性。这次我们选用的样本这么简单，我在编程上还不能顺利写出，到后来程序还是同组同学写的，我深深地认识到自己在编程上的不足。学习本就是一个从不会到会的过程，同学之

6、间的合作，我们才顺利完成课程设计。理论是为实践服务的，学好理论才能去接触实践，因为学时所限制，我们在课堂上学习的东西仅仅是皮毛。信息论与编码，需要大量地概率论与数理统计的只是作为依托，所以数学是基础。任何一门课程都不会独立与其他课程之外。作为一个工科的学生一定要把所学用于实践，相信我下次能做的更好。 参考文献1曹雪虹，张宗橙.信息论与编码北京.清华大学出版社.2009.2StanleyB.LippmanJoseeLajoie,BarbaraE.Moo著，李师贤，蒋爱军，梅晓勇,林瑛译.C+Primer中文版.北京.人民邮电出版社.2006.3傅祖芸.信息论基础北京.电子工业出版社，1989谭浩

7、强.C语言程序设计（第三版）北京.清华大学出版社，2009.10 附录：源程序#includeviosteamA包含头文件#include#include#include#include#includeusingnamespacestd;stmctList_num定义一个stmct类型用于存放概率和对应的字符标识floatprobability=0;bitsetkey;structBinary.alphabet用于存放码字vectorbitset=A&wordi=h&woidi=N)numwordi-8+;elsecout11ERROE!ii您输入的其他字符，请重新输入字符(字母或空格)!”e

8、ndlendl;gotorepet;不是人写字符和空格的情况if(word.size()=0)没有输入字符的情况coutnERROR!ii您没有输入字符，请重新输入字符！”endlendl;gotorepet;for(inti=0;i=l;j+)for(inti=0;i27;i+)if(Alphabet_probabilitynj.keyi=1)CharToBinaryi.key.push_back(1);/概率最小的码值为1if(Alphabet_probabilityn-j-l.keyi=1)CharToBinaryi.key.push_back(O);/概率次最小的码值为0Alphabe

9、t_probabilitynJ-1.piobability=Alphabet_bability+Alphabet_bability;for(mtk=0;k27;k+)将最小的二个概率相加，将相应的字符标识也置1if(Alphabet_probabilityn-j.keyk=1)Alphabet_probabilityn-j-l.keyk=1;Insert_Sort(n-j);进行一遍后，再进行排序cout”统计结果及由哈夫曼编码可得的各个字符的码字如卞所示：”endl;cout”你输入的总数为:word.sizeQen

10、dl;cout“字符次数概率码字2字符次数概率码字-endl;CharToBuiaiy_output();调用输出码字的函数cout”信源爛为：nInforniation_S_EQntM/信源爛”平均码长为：HAveiage_Code_Lengtli()ntH平均码长编码效率为：MIiifdrniation_S_EQ/Average_Code_Length()*100亡iidl;/编码效率cout转换后的编码为：endl;Binary_Output();调用输出编码后的序列coutendl;repet:后面的goto语句要用的标号for(inti=0;i27;i+)将相应的变量初始化，以便下一

11、次再使用numi=0;Alphabet_probabilityi.key.reset();Alphabet_bability=0;CharToBmaiyfi.key.clearQ;couthji请按Enter清除屏幕iiH;while(1)if(getcharQ=W)break; Isystem(cls);cout”请按”Ctrl+Z”然后再按Enter结束该程序!n”请输入一串字符：n”；return0;unsignedmtPiobability_NotzeroQ将概率中不是0概率的个数返回unsignedmtn=0,i=0;for(;i27;i+)if(Al

12、phabet_probabilityi.piobabilitv!=0)n+;returnn;voidInseit_Soil(unsignedmtn)采用插入排序法unsignedmti;mtj;List_numtemp;for(i=l;iAlphabet_piobabilityj.piobability&j=0)Alphabet_probabilityj+1=AlphabeCprobabilitylj；j-;AlphabeCprobabilityj+1=temp;voidCharToBinary_outputQ各个码字的输出函数mtk=0;for(mti=0;i0)if(i=26)cout”空

13、格，；coutnumi;if(k%2=0)gotoxv(lO);if(k%2=1)gotoxv(50);float(numi)/woid.sizeO)/出其他字符概率for(intj=ChaiToBmaiyi.key.size()1;j=0;j)coutCliarToBinaryi.keyj;coutendl;elsek+；coutchar(65+i),7Hchar(97+i)coutnumi;if(k%2=1)gotoxv(lO);if(k%2=0)gotoxv(50);float(numi)/woid.sizeO)/出其他字符概率for(intj=ChaiToBmaiyi.key.size

14、()1;j=0;j)coutCliarToBinaryi.keyj;if(k%20)输出2组数后，进行换行coutendl;elsegotoxv(40);if(ChaiToBmary26.key.size()=0&k%2=1)coutendl;voidBiiiaiy_Output()整体编码的输出 for(unsignediiiti=0;i=A&woidi=0;j)coutChaiToBiiiaiywordi-WJ.keylj；elsefor(intj=ChaiToBiiiaiywordi-hkeysize()-1;j=0;j-)coutChaiToBinarywordi-.keyjj;els

15、efor(intj=ChaiToBiiiaiy26.key.sizeQ-1;j=0;j)coutChaiToBiiiary26.keyj；floatAvreiage_Code_Length()/计算平均码长floatsum=0;for(unsignediiiti=0;i27;i+)if(CharToBiiiaiyi.key.sizeO!=0)sum+=(float(numi)/float(word.sizeQ)*ChaiToBiiiaiy1.key.size();returnsum;floatIiifbnnation_S_E()计算平均信源爛floatsum=0;for(mti=0;i27;i+)log2(float(numi)if(CharToBiiiaryi.key.sizeQ!=0)sum+=(float(numi)/float(word.size()*float(word.size();return(-sum);voidgotoxy(iiitx)在屏幕的具体位置