信息论与编码课程设计

1信息论与编码课程设计报告设计题目：统计信源熵与香农编码专业班级：学号：学生姓名：指导老师：教师评分：2015年3月24日2目录一、设计任务与要求…………………………………………3二、设计思路…………………………………………………3三、设计流程图………………………………………………4四、程序运行及结果…………………………………………5五、心得体会…………………………………………………6参考文献………………………………………………………7附录：源程序…………………………………………………73一、设计任务与要求1、统计信源熵要求：统计任意文本文件中各字符（不区分大小写）数量，计算字符概率，并计算信源熵。2、香农编码要求：任意输入消息概率，利用香农编码方法进行编码，并计算信源熵和编码效率。二、设计思路1、统计信源熵在VC++环境中进行编程：（1）打开一篇文章，将26个英文字母作为信源。（2）计算每个字母出现的次数（不区分大小写），再通过计算信源总大小来计算在本篇文章中每个字母出现的频率。（3）通过信源熵计算公式来计算信源熵。2、香农编码设计思路香农编码主要是通过一系列步骤支出平均码长与信源之间的关系，同时是平均码长达到极限值，即选择的每个码字的长度k满足下式：I（x）≤k＜I(x)+1具体步骤如下：a、将信源消息符号按其出现的概率大小依次排列为：p1≥p2≥…≥pnb、确定满足下列不等式的整数码长k为：-lb(pi)≤k≤-lb(pi)+1c、为了编成唯一可译码，计算第i个消息的累加概率：pi=∑𝑝(𝑎𝑘)𝑖−1𝑘=1d、将累加概率Pi变换成二进制。e、取Pi二进制数的小数点后Ki位即为该消息符号的二进制码字。在香农编码中对于求解编码效率主要是依靠这个公式：R=H(X)/K,其中k=∑𝑝(𝑎𝑖)𝑘𝑖𝑛𝑖=1对于求解信源熵主要依靠公式：H（X）=−∑𝑝(𝑥𝑖)𝑙𝑜𝑔𝑝(𝑥𝑖)𝑛𝑖=14三、设计流程图1、统计信源熵：开始↓先输入一段英文文章↓统计各个字符的概率大小↓通过信源熵计算公式计算信源熵↓输出结果程序结束2、香农编码：开始↓先输入一组概率分布数组↓先对符号概率进行从大到小排列↓计算累加概率Pi↓5确定码字长度Ki↓由上组的累加概率Pi计算出码长↓计算编码效率：信源熵与平均码长的比值↓输出结果程序结束四、程序运行及结果1、统计信源熵：2、香农编码：6五、心得体会通过本次课程设计的练习，进一步巩固了信源熵、信源编码的基本原理，基本上掌握了编码方法，对编程软件的使用得到了很大的熟悉，有效增强了自主设计、编程调试的开发能力，同时也大大提高了本身的实践创新能力。课程设计是培养学生综合运用所学知识，发现、提出、分析和解决实际问题，锻炼实践能力的重要环节，是对学生实际工作能力的具体训练和考察过程。在这个过程中不仅锻炼了我们坚持不懈的毅力，更磨练了一个队伍的团结互助的精神，只有大家一起努力才能将课程设计圆满的完成，设计中遇到和解决问题的过程对我们的探索解决问题能力有了一个提高，对我们以后的学习有很大的好处。这次我们主要做了统计信源熵和香农编码的题目，这不仅需要对年前学的信息论与编码有一个很好的回顾与掌握，还要对一年前学的C语言程序设计有一个基本的了解，这让我们又对C语言编程有了一个重新的复习，知识也得到了较好的巩固。在此过程中我们我们充分认识到了团队协作的重要性，也体验到了问题得到解决的喜悦感，成就感。在以后的学习中要坚持不懈，善于创新和发现，提高自己的思维和动手能力，成为一个高素质人才。7参考文献[1]曹雪虹、张宗橙编著《信息论与编码》.清华大学出版社，2009年第二版[2]贾宗璞、许合利编著《C语言程序设计》.人民邮电出版社，2010年第一版[3]严蔚敏、吴伟民编著《数据结构（C语言版）》.清华大学出版社，1997年第一版附录：源程序：(1)统计信源熵#includestdio.h#includemath.hvoidmain(){inti,sum=0,n=0,ch[50]={0};doublep[50]={0},H=0;charc,zm;printf(输入文字:\n);while((c=getchar())!='\n'){sum++;for(i=97;i=122;i++){if(c==i){ch[i-97]++;//sum++;}}for(i=65;i=90;i++){if(i==c){ch[i-65]++;//sum++;}}}printf(各字符个数:\n);for(i=0,zm='A';i26;i++,zm++){8printf(%c:%-5d\t,zm,ch[i]);}printf(\n);printf(符号概率为:\n);for(i=0;i50;i++){p[i]=(double)ch[i]/(double)sum;if(p[i]!=0){printf(p(%c)=%f,i+65,p[i]);printf();n++;}if(n==4){printf(\n);n=0;}}for(i=0;i=25;i++){if(p[i]!=0)H=H-p[i]*((log(p[i]))/(log(2)));}printf(\n);printf(信源熵=%f\n,H);printf(字符长度:%d\n,sum);//printf(\n);//getchar();}(2)香农编码#includestdio.h#includemath.hvoidmain(){inti,n,j,k;floatsum=0;floatp[100]={0};floatm,H1=0,H2=0;floatPi[100]={0};intl[100];9charc[100][100];printf(请输入x的个数\n);scanf(%d,&n);printf(\n);printf(请输入p[i]的概率分布\n);for(i=0;in;i++)scanf(%f,&p[i]);for(i=0;i=n;i++)sum=sum+p[i];while(sum!=1){printf(错误输入，请重输\n);printf(请输入x的个数\n);scanf(%d,&n);printf(\n);printf(请输入p[i]的概率分布\n);for(i=0;in;i++)scanf(%f,&p[i]);for(i=0;in;i++)sum=sum+p[i];}for(j=0;jn-1;j++)for(i=0;in-1-j;i++)if(p[i]p[i+1]){m=p[i];p[i]=p[i+1];p[i+1]=m;}Pi[0]=0;for(j=1;jn+1;j++){Pi[j]=Pi[j-1]+p[j-1];}for(i=0;in;i++){m=log(1/p[i])/log(2);if(m==(int)m)l[i]=(int)m;elsel[i]=(int)(m+1);}printf(p[i]序列为累加概率Pi码长Ki\n);for(i=0;in;i++)printf(%5.2f\t%5.2f\t\t%d\n,p[i],Pi[i],l[i]);for(i=0;in;i++)10{for(k=0;kl[i];k++){m=Pi[i]*2;if(m=1){Pi[i]=m-1;c[i][k]='1';}elsec[i][k]='0';Pi[i]=m;}}printf(码字\n);for(i=0;in;i++){for(k=0;kl[i];k++)printf(%c,c[i][k]);printf(\n);}for(i=0;in;i++){H1=H1-p[i]*log10(p[i])/log10(2);H2=H2+p[i]*l[i];}printf(信源熵=%f\n,H1);printf(编码效率为:%0.3f\n,H1/H2);}