信息编码课程设计 19 胡仲科.doc

课 程 设 计 报 告课程名称 信息论与编码 课题名称 香农编码的分析与实现 专 业 信息与计算科学 班 级 1103 学 号 19 姓 名 胡仲科 指导教师 李安平 李荣军 2014年 06 月 27 日湖 南 工 程 学 院课 程 设 计 任 务 书课程名称 信息论与编码 课 题 香农编码的分析与实现 专业班级 信息与计算科学1103班学生姓名 胡仲科 学 号 19 指导老师 李安平 李荣军 审 批 李安平 李荣军 任务下达日期 2014年6月16日 任务完成日期 2014年6月27日信息论与编码课程设计任务书 一、 设计目的通过课程设计使学生更进一步掌握信息论与编码课程的有关知识，提高编程的能力，并将所学的内容加以综合。通过查阅资料，了解所学知识的应用情况。同时也使学生通过动手进行程序设计从而提高解决实际问题的能力。二、课程设计要求1、认真查阅资料、遵守课程设计时间安排、按时上机，认真调试程序、认真书写报告三、报告书写格式1、课程设计封面、课程设计任务书、正文、参考文献、课程设计成绩报告单四、设计题目、 符号信源熵的求解给定信源各个符号发生概率，条件概率，编程求解各个符号的自信息量和信源的熵,条件熵，联合熵。、 图像信源熵的求解读入一幅图像，编程实现求解图像信源的熵。、 互信息的求解已知信源发出x的概率，及接收到y后的x的后验概率，编程实现互信息、平均互信息的求解。、 唯一可译码的判断总结唯一可译码的概念与判断方法，编程实现：给定码字，判断是否为唯一可译码。、 即时码的构造与判断总结即时码的概念与判断方法，编程实现：构造给定码长的即时码；给定码字，判断是否为即时码。、 Kraft不等式的分析与判断编写程序，给定信源符号个数，码元进制数和码长，判断唯一可译码是否存在。、 香农编码的分析与实现给定信源各个符号及其发生概率，编程求解其香农编码的码字，平均码长，及编码效率。、 费诺编码的分析与实现给定信源各个符号及其发生概率，编程求解其费诺编码的码字，平均码长，及编码效率。、 用香农-费诺-埃利斯编码的分析与实现给定信源各个符号及其发生概率，编程求解其香农-费诺-埃利斯编码码字，平均码长，及编码效率。、 哈夫曼编码的分析与实现给定信源各个符号及其发生概率，编程求解其哈夫曼编码码字，平均码长，及编码效率。、 LZW编码的分析与实现、 算术编码的分析与实现、 线性分组码的编译码的分析与实现、 对称信道容量的求解给定信道的概率矩阵，编程判断其是否为对称信道，并求解其信道容量、 准对称信道容量的求解给定信道的概率矩阵，编程判断其是否为准对称信道，并求解其信道容量、 信道容量迭代算法的分析与实现、 率失真函数R(D)的计算说明：（1） 课程设计的题目共17个，一个班一个题目最多供4人选。（2） 课程设计说明书一般应包括理论分析与仿真，编程语言可自行选择，说明书字数在3000字左右；（3） 参考文献可更改，设计的内容细节和具体要求可以和指导老师协商后，有所更改。（4） 多人做一个题目时要有不同的分工或侧重点，写出的课程设计说明书不能雷同，如重复率超过50%，同组人均不能通过。五、时间安排、查阅资料及程序设计（2天）、上机调试程序（2天）3、书写报告（1天）六、成绩评定、未完成设计任务，没达到设计要求则成绩为“不及格”。、基本完成设计任务，并撰写出课程设计报告则成绩为“及格”。、学生能够认真查阅资料，独立完成设计任务，程序调试通过，并且撰写出课程设计报告则成绩为“中”。、学生能够认真查阅资料，独立完成设计任务，程序调试通过，功能完善，操作灵活，界面美观，并且撰写出课程设计报告则成绩为“良好”。、学生根据自身的实际能力，在实现设计题目基本要求的基础上增加一些功能，评定成绩时根据其难度和完成情况给与适当加分，如界面效果，系统操作的方便性、灵活性、创新性等，如果设计非常完善则成绩为“优秀”。七、参考文献1 傅祖芸 . 信息论 基础理论与应用 .北京:电子工业出版社,20012 周荫清 . 信息理论基础 .北京:北京航空航天大学出版社,20023 T M Cover & J A Thomas . Elements of Informat ion Theory .New York: John Wiley& Sons . Inc ., 19914 美 R W 汉明著,朱雪龙译 . 编码和信息理论 .北京:科学出版社,19845 朱雪龙 . 应用信息论基础 .北京:清华大学出版社,20016 姜丹 . 信息论与编码 .合肥:中国科技大学出版社,20017 陈运 . 信息论与编码 .北京:电子工业出版社,20028 曹雪虹 . 信息论与编码 .北京:北京邮电大学出版社,20019 吴伟陵 . 信息处理与编码 .北京:人民邮电出版社,20036.19（星期四）上午8:00-11:00 1班及2班前15下午14:30-17:30 3班及2班15后6.20（星期五）上午8:00-11:00 3班及2班15后 下午14:30-17:30 1班及2班前15 目 录1.摘要12.问题提出33.问题分析 34.程序流程图 45.程序代码 66.程序界面 77.程序结果78.课程设计心得79.课程设计评分表81.摘要：Shannon编码的特点1.由于累加概率总是进一取整,香农编码方法不一定是最佳的；2.由于第一个消息符号的累加概率总是为0,故它对应码字总是0、00、000、 00的式样；3.码字集合是唯一的,且为即时码;4.先有码长再有码字；5.对于一些信源,编码效率不高,冗余度稍大,因此其实用性受到较大限制 Shannon编码的优缺点1.香农码考虑了信源的统计特性,使经常出现的信源符号对应较短的码字,使信源的平均码长缩短，从而实现了对信源的压缩；2.香农码有系统的、惟一的编码方法,但在很多情况下编码效率不是很高。Shannon编码的步骤1.将信源发出的N个消息符号按其概率的递减次序依次排列。2.按下式计算第i个消息的二进制代码组的码长,并取整。3.为了编成唯一可译码，首先计算第i个消息的累加概率4.将累加概率Pi （为小数）变成二进制数5.去除小数点，并根据码长li ，取小数点后li 位数作为第i个消息的码字。我们知道，离散无记忆信源的冗余度是由于信源字母的概率分布不平均引起的，当用等概率的码字母组对源字母组进行定长编码时，为使编码有效，源字母组的长度必须很大才行，这在实际应用中很难实现。为了解决这一难题，可以采用可变长度的码字母组去适应不同概率的源字母组和源字母。变长编码将等长消息变换成不等长的符号序列。通常在编码时，为使平均码长最短，我们可将最常出现的消息用短码表示，不常出现的消息用长码表示。设第个消息用长度为的进制符号表示，则平均每个消息的码长为显然，变长编码比等长编码要复杂得多。比如在不等长码字组成的序列中，要正确识别每个长度不同的码字的起点就比等长码要复杂。另外，接收到一个变长码字序列后，往往不能正确译出，要等到后面的符号收到后才能正确译出，这就是所谓同步译码和译码延时问题。在一般情况下对系统地构造前缀码的问题Shannon曾经提出过一种方法，被称为Shannon码。一个离散信源是一个有序对(S.P),其中是一个有限符号集（或称为字母集），P为S上的一个概率分布，一般记的概率为，或记为.设(S,P)为一个信源，事件的自信息记为，并定义为在这个定义中，对数的底没有说明，选择什么样的底对我们来说是无关紧要的，因为底的改变仅仅变动了计量的尺度单位。最常见的底为2,e和10.当底为2时，I是以比特(bit)作为度量单位(bit为binary digit的缩写，即二进制数的缩写)；当底为10时I是以哈特(Hart)度量(Hart是Hartly unit的缩写，即十进制数的缩写)；当底选为e时，I是以奈特(nat)度量(nat是nature unit的缩写)。信源(S,P)的熵，记为H(S)，是自信息的统计平均值，即对任一编码规则，其平均码长并不受信源符号的影响，仅与概率分布有关，因而为了确定平均码长，我们可以直接将码字与概率分布联系起来。一个编码规则的平均码长是指一般定义为编码速率或称码率。如果对于给定的离散无记忆信源及编码速率,以及，存在正整数，以及相应的编码与解码器，使得当时，则称为可达的，否则称为不可达的。表明当时可达，当时，不可达。称为编码效率，通常。C语言是一种优秀的面向对象程序设计语言，它在C，语言的基础上发展而来，但它比C语言更容易为人们学习和掌握。C以其独特的语言机制在计算机科学的各个领域中得到了广泛的应用。面向对象的设计思想是在原来结构化程序设计方法基础上的一个质的飞跃，C完美地体现了面向对象的各种特性。2.问题的提出：香农编码的分析与实现给定信源各个符号及其发生概率，编程求解其香农编码的码字，平均码长，及编码效率。3.问题的分析：Shannon编码法：设信源为令，若，表示大于或等于的最小整数，则记，用个bit来表示按二进制小数展开到位截断。于是平均码长为例如：设离散无记忆信源为求各字母的码字、平均码长、编码效率。开始4.流程图：输入信源字符的个数Ni=0输入信源的概率分布pi,i+是iN? 否i=0l1i=-log(pi)/log(2);li=l1i;lil1i? 是li=li+1，i+是iN? i=0j=0qi=qi*2是qi1?qi=qi-1;aij=1;aij=0k=0输出aik是 kli? 否 是 jli? 是iN? i=0 n=n+li*pi;m=m-pi*log(pi)/log(2);是iN? 否m=m/n输出平均码长为n输出编码效率为m结束5.程序代码：#include#includeint main()float p99=0,l199=0,q99=0;int l99;int a9999=0;int i,j,k,N;float n=0,m=0;printf(请输入你要输入信源字符的个数Nn);scanf(%d,&N);printf(请输入你要输入信源的概率分布n);for(i=0;iN;i+)scanf(%f,&pi);for(i=0;iN;i+)l1i=-log(pi)/log(2);for(i=0;iN;i+)li=l1i;if(lil1i) li=li+1;for(i=1;iN;i+)for(j=0;ji;j+)qi=qi+pj;for(i=0;iN;i+)for(j=0;jli;j+)qi=qi*2;if(qi1) aij=0;else qi=qi-1;aij=1; printf(a%d的码字为:,i+1); for(k=0;kli;k+)printf(%d,aik); printf(n);for(i=0;iN;i+)n=n+li*pi;printf(平均码长为:%fn,n);for(i=0;iN;i+)m=m-pi*log(pi)/log(2);m=m/n;printf(编码效率为:%fn,