《费诺编码的程序实现过程与设计毕业论文.doc》由会员分享，可在线阅读，更多相关《费诺编码的程序实现过程与设计毕业论文.doc（24页珍藏版）》请在三一办公上搜索。
1、西藏大学本科生毕业论文题目:费诺编码的程序实现过程与设计院（部） 工学院 专业年级 09级电子信息工程 姓 名 高云飞 学 号 31010950101 指导教师 王龙业 职 称 副教授 二一三年 月 日西藏大学本科生毕业论文(设计)原创性及知识产权声明 本人郑重声明：所呈交的毕业论文（设计）是本人在导师的指导下取得的成果。对本毕业论文（设计）的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。因本毕业论文（设计）引起的法律结果完全由本人承担。本毕业论文（设计）成果归西藏大学所有。 特此声明 毕业论文（设计）作者签名：作者专业：作者学号： 年 月 日费诺编码的程序实现过程与设计摘要21世纪
2、随着现代科技的发展，人们逐渐跨入了信息化高速发展的时代。无论在政治、经济、军事等各个领域，还是在生活中的各个方面，通信系统起着至关重要的作用。关于通信系统的研究必将受到人们的重视。而且在早期香农已经发现通信系统的传递对象就是信息，通信系统的中心问题是在噪声下如何有效可靠地传输信息，而实现这一目标的主要途径是编码。编码的方式分为三种即：信源编码、信道编码和密码编码。本文主要研究信源编码中的一种最佳变长编码费诺编码来进行通信系统的分析，费诺编码的目的就是使信源冗余减少，使信息更加经济、有效地传输，它是比香农编码更优的一种编码方式，通过程序来实现该编码更加有效的提高了编码的效率，缩短了计算编码所用的
3、时间，从而使得信息的可靠性大大的提高了。关键词：通信系统 编码 费诺编码 程序实现Fano-coding program realization of the process and designAbstractThe 21st century with the development of modern technology, people gradually entered the era of rapid development of information technology.In terms of the political, economic,military and other
4、 fields,and in all aspects of life,communication system plays a vital role.On the communication system is bound to be peoples attention.Passing objects has been found in the early Shannon communication system is the central issue of the information,communication system noise how effective and reliab
5、le transmission of information,and to achieve this goal is coding.The coding method is divided into three:source coding,channel coding and password encoding.This paper studies the source coding in an optimal variable-length coding Fano-coding for the analysis of the communication system,the purpose
6、of Fano-coding is the source for reduced redundancy,to make the information more cost-effective transmission,it is better than shannon-coding encoding,the code more effective to improve the coding efficiency,shorten the calculation used to encode the time,so that the information achieved through the
7、 process greatly improve the reliability.Keywords: communication system coding fano-coding procedures to achieve目录1 绪论12 编码与信源编码52.1首先要了解什么是信源编码52.2费诺编码方法62.3哈夫曼编码方法73 费诺编码83.1费诺编码描述83.2费诺编码算法83.3费诺编码特点93.4费诺编码的实例94 费诺编码的程序设计94.1费诺编码算法设计114.2编码如下164.3程序中要解决的关键问题174.4总结17致谢词18参考文献191 绪论1.1信息论的定义早期的数据
8、压缩来自于人们对概率的了解。当对文字信息进行编码时，如果为出现概率较高的字母赋予较短的编码，为出现概率较低的字母赋予较长的编码，平均编码长度就能缩短不少。印象中的著名的Morse电码就是一个范例。信息论之父C.E.Shannon曾指出，任何信息都存在冗余，冗余大小与信息中每个符号的出现概率（不确定性）有关。他所提出的无失真信源编码定理奠定了数据压缩的理论基础1。数据压缩的目的就是要消除信息中的冗余，而信息熵及相关的定理恰恰用数学手段精确地描述了信息冗余的程度9。信息论是运用概率论与数理统计的方法研究信息、信息熵、通信系统、数据传输、密码学、数据压缩等问题的应用数学学科8。从DVD到个人电脑，从
9、卫星通信到文件，在我们今天的生活中，信息几乎在每个领域都扮演着重要角色。工程师克劳德香农于1948年奠定了信息论的基础，他指出了通信的极限。基于这一理论产生了数据压缩技术、纠错技术等各种应用技术，这些技术提高了数据传输和存储的效率。信息论将信息的传递作为一种统计现象来考虑，给出了估算通信信道容量的方法。信息传输和信息压缩是信息论研究中的两大领域。这两个方面又由信息传输定理、信源信道隔离定理相互联系。当然，信息论的重大应用远不止于此。DNA是一种信息存储物质，正是信息论帮助人们解开了生物基因组密码之谜。简单地说信息论包含了生命、宇宙乃至一切7。1.2 信息论对现代社会的影响信息论对现代社会的影响
10、是多方面的。首先,在理论研究方面,信息论所处的地位已远远超出了香农当年所界定的“通信的数学理论”的范畴,得到了不断的扩充和发展,出现了语义信息、语法信息与语用信息等研究与信息的意义有关的学科,以及面向智能研究的全信息理论6 。如今,信息已成为与物质、能量并列的宇宙中的三个基本要素, 世间万物的发展变化可归结为物质、能量和信息的传递和转化过程。另一方面,在科学和技术高度发展的今天,信息的概念也被渗透到许多不同的学科和领域,深入到了社会生活的各个方面,成为可与相对论和量子力学并驾齐驱的新一代边缘交叉学科的重要组成部分。特别是以信息论、控制论和系统论为代表的“老三论”以及以普里高津(I.Prigog
11、ine)的耗散结构理论,哈肯(H.Haken)的协同学和托姆(R.Thom) 的突变论或艾根(M.Eigen)的超循环理论为代表的“新三论”的出现,标志着一代新的边缘交叉学科的兴起。它们的形成和发展对现代科学的研究具有重要的方法论上的指导意义。第二,在技术应用方面, 信息论为现代通信理论和技术的发展做出了不可磨灭的贡献,信息科学与材料科学、能源科学一起已成为现代高新技术领域的三大关键技术, 信息产业已是当今社会中发展最快、效益最高、潜力最大、影响最广的最重要的支柱产业之一。科学技术的进步使得计算机从一种单纯的快速计算机器发展成为能智能化、高速度地处理一切数字、符号、文字、语音、图像以至进行知识
12、发现和逻辑推理等的强大工具,其应用领域已覆盖了社会生活的方方面面,成为推动人类社会进步的强大动力。计算机与通信技术的结合更深刻地影响和改善了人们的生产与生活方式,促进了人类文明的进步。没有信息论的指导,就不会有现代的无线电技术,电视接收系统, 不会有现代的移动通信和卫星导航、定位系统,更不会有“英特网”和“信息高速公路”的出现, 而所有这些领域业已成为现代技术进步的重要标志。第三, 在社会经济领域, 21世纪人类社会将全面进入信息时代,智能、技术和信息已成为现代社会经济生活中不可缺少的重要资源。信息科学的迅速发展和信息高速公路的出现,使先进的技术和信息能够为不同国家和民族所使用,有利于国际性的
13、合作和交往的发展,同时也为市场经济中资源的有效配置和利用提供了良好的社会环境, 避免了项目的重复建设和产品的盲目生产。企业充分利用互联网上的有用信息和在互联网上做广告也为其利润的增加和经济的发展开辟了新的天地。信息科学的发展还促进了各种信息产业如光纤制造业、信息传输、交换设备生产企业、计算机软、硬件生产以及电信等行业的繁荣,同时也带动了各种高科技企业及其它行业的发展,知识和技术密集型产业将代替劳动密集型产业而成为当今社会的“朝阳产业”。信息时代的信息将成为社会运作的核心,成为世界经济从工业化阶段进入信息化阶段的标志。电子商务的迅速崛起,适应了21世纪全球经济一体化的发展趋势,构成了这个时代的新
14、特征,并在促进经济增长,方便人们生活方面发挥出了巨大的作用。第四,在个人生活方面,互联网将打破国界和地域的限制,使整个世界联为一体, 人们似乎生活在一个地球村中。不同民族、肤色、文化和语言背景的人们通过信息高速公路互相沟通,地区间的差异和空间上的距离变得越来越不重要了。互联网的发展还导致了一些新的服务行业的出现,如电子教育、电子科研、电子医疗、电子购物、电子信箱、电子查阅、电子钱包及交互式电视等全新的行业,使人们足不出户就能享受着信息科学的进步所事来的巨大方便,做完想做的事。信息的利用已不再是知识阶层的特权,互联网的普及将深刻地改变人们生活方式,给人们的学习和生活带来极大的便利,“居家购物”、
15、“居家上班”、“居家上学”和“居家就医”等已不再是遥远的未来。通过网络快捷方便地获取信息和知识，使得那些一时还无法进入高校大门的人能方便地通过因特网免费享受重点高校甚至国外高校提供的一流的课程和教育。同时,在未来的信息社会中,随着信息产业在国民经济中所占比重的日益增多,就业结构的变化对劳动者素质提出了更高的要求,新兴产业的工人,已不再是原来意义上从事大量体力劳动的人,而是能够掌握现代科学技术及技能的新型工人,这将使社会成员普遍地意识到知识和信息的重要性,主动要求接受再教育,从而有利于迅速提高个人乃至人类整体的文化水平，所有这些,都将使个人生活方式发生着深刻的变化。第五, 在思维方式方面,信息高
16、速公路的开通和信息的快速传递将导致思维方式上的不断更新。互联网的开通大大加快了人们接受新思想、新信息的速度,促进了不同生活方式和思维模式的融合,使得那些原来遥不可及的事情变得唾手可得,原来不可思议的新事物变得司空见惯,原来不可接受的生活方式、思维模式和文化传统变得争相仿效。人们每天都能从网络上接受到大量的不同种类、具有不同文化特质和民族风格的信息,通过对不同民族的优良文化传统和独特的思维方式的学习和消化,分析和综合,加快了人们思维方式的变革和更新,促进了新的思维模式的形成,将人们从静态思维转向动态思维,从局域性思维转向全局性思维,从封闭性思维转向开放性思维,从单向性思维转向多向性思维。有利于全
17、方位、多层次、多渠道地展开思维活动,促进跳跃性、联想性、创造性的思维网络的形成。所有这些对人类的文明和社会的进步都将起到积极的促进作用。然而,技术是一把双刃剑。在信息理论和信息网络给人类带来福音的同时,也带来了一些问题和困惑。首先,信息网络的建立和信息的快速传递为西方大国霸权主义和强权政治的发展、腐朽观念的传播以及利用本国信息优势进行“信息侵略”和文化渗透提供了有利条件,这将在某种程度上左右他国民众的政治观念和政治信仰,损害不同国和民族的文化传统, 损坏丰富多彩的文化个性,在世界范围内产生“文化同质”现象,对世界文化的多元性造成了威胁。随之而来的将是外国的价值观念和思维方式及其政治、经济、法律
18、制度对中国千百年来所形成的文化传统造成冲击和震荡,将会在一定程度上改变国人特别是青年一代的价值取向和思维方式,从而对现行的政治构架产生负面影响。东西方文化在这些方面的磨合和碰撞将是长期的,在这个过程中将会出现一些新的矛盾,其直接结果就是涉外案件增多,意识形态领域上渗透与反渗透、颠覆与反颠覆的交锋将会更加激烈。其次,由于发达国家有充分的技术和财政力量进行信息资源的开发和利用并从中受益,而第三世界国家却无力支付它的建设所需要的巨额开支,从而将越来越远地落在后面,这在客观上加大了发展中国家与发达国家的贫富差距。贫富差距的拉大,使一些人的心理失衡,造成的结果是,这些人会铤而走险,进行抢劫、盗窃、诈骗等
19、各种违法犯罪活动。再次,信息的滥开发将导致严重的信息污染现象,而信息的滥用将导致对个人隐私权、名誉权和知识产权侵犯,这些都直接影响着社会的稳定和发展。最后,毫无节制地上网和某些过剩的信息垃圾不仅浪费人们的时间和精力,而且也影响了人们的身体健康,导致了各种“网络病”的出现,并已成为不可忽视的社会问题。另外,各种计算机病毒感染的加剧及网络黑客的猖獗使得信息的安全保密问题成为全社会乃至政府首脑关心的焦点并在这方面耗费了大量的时间、人力和物力,在一定程度上阻碍了经济的快速发展。总之,信息论的创立,信息科学的基础和应用研究的开展有力地推动了信息技术的进步和信息全球化的进程,对人类社会的发展和人们生活水平
20、的提高起到了不可磨灭的积极作用与此同时,以信息技术为代表的高科技将更多地被犯罪分子所利用,实施技术型、智能型犯罪,特别是利用计算机技术、现代通信技术、现代信息技术、现代仿真技术等方面的现代化犯罪,将增大社会危害性和侦查破案难10。2 编码与信源编码在学过信息论与编码以后，对这方面内容已有了基础的了解。为了进行更深入的了解，我查阅了很多资料，我认为通信的根本问题是如何将信源输出的信息在接收端的信宿精确地或近似地复制出来，而这最重要的一步就是信源的编码，一个好的开端才能为以后的传输及接受、解码提供有利得条件。而我也对各种信源编码方式产生了浓厚的兴趣。2.1首先要了解什么是信源编码为了减少信源输出符
21、号序列中的剩余度、提高符号的平均信息量，对信源输出的符号序列所施行的变换。具体说，就是针对信源输出符号序列的统计特性来寻找某种方法，把信源输出符号序列变换为最短的码字序列，使后者的各码元所载荷的平均信息量最大，同时又能保证无失真地恢复原来的符号序列8。既然信源编码的基本目的是提高码字序列中码元的平均信息量，那么，一切旨在减少剩余度而对信源输出符号序列所施行的变换或处理，都可以在这种意义下归入信源编码的范畴，例如过滤、预测、域变换和数据压缩等。一般来说，减少信源输出符号序列中的剩余度、提高符号平均信息量的基本途径有两个：使序列中的各个符号尽可能地互相独立；使序列中各个符号的出现概率尽可能地相等。
22、前者称为解除相关性，后者称为概率均匀化。在通信过程中，如何在不失真或允许一定失真条件下，用尽可能少的符号来传送信源信息，提高信息传输率；在信道受干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大。这就产生了多种信源编码方式2。为了有效传播信息，最理想状态即为无失真传输。在无失真信源编码中又分为定长编码、变长编码机最佳变长编码。2.1.1定长编码在定长编码中，K是定值，编码的目的即为找到最小的K值。要实现无失真的信源编码，不但要求信源符号与码字是一一对应的，而且还要求有码字组成的码符号序列的逆变换也是唯一的。由定长编码定理可知，当编码器容许的输出信息率，也就是当每个信源符号必须输出
23、的码长是K=Kl/logm。由定理表明，只要码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无失真，但是条件是L足够大。这就为传输带来了很大的麻烦，并且实现起来很困难，并且编码效率也不高。而要达到编码效率接近1的理想编码器虽有存在性，但在实际上时不可能的，因为L非常大，无法实现。由此而产生了变长编码。2.1.2变长编码在变长编码中，码长K是变化的，可根据信源各个符号的统计特性，对概率大的符号用短码，而对概率小的符号用长码。这样大量信源符号编成码后，平均每个信源符号所需的输出符号数就可以降低，从而提高编码效率。用变长编码来达到相当高的编码效率，一般所要求的符号长度L可以比定长编码小
24、得多的多。很明显，定长码需要的信源序列长，这使得码表很大，且总存在译码差错。而变长码要求编码效率达到96%时，只需L=2.因此用变长码编码时，L不需要很大就可达到相当高的编码效率，而且可实现无失真编码。并且随着信源序列长度的增加，编码效率越来越接近于1，编码后的信息传输率R也越来越接近于无噪无损二元对称信道的信道容量C=1bit/二元码符号，达到信源与信道匹配，使信道得到充分利用。但变长编码方式也有优劣的区分，下面就讨论几种不同的变长编码方式1。1、 香农编码方法香农第一定理指出了平均码长与信源之间的关系，同时也指出了可疑通过编码使平均码长达到极限值，这是一个很重要的极限定理。香农第一定理指出
25、，选择每个码字的长度Ki满足下式：I（xi）Ki=P2=Pn。2依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并对各组赋予一个二进制码元“0”和“1”。3使划分后的两个组的概率之和近似相同，并对各组赋予一个二进制符号“0”和“1”。4如此重复，直至每个组只剩下一个信源符号为止。5信源符号所对应的码字即为费诺码。3.3费诺编码特点费诺编码，它编码后的费诺码要比香农码的平均码长小，消息传输速率大，编码效率高，但它属于概率匹配编码它不是最佳的编码方法1。费诺编码方法属于概率匹配编码，具有如下特点：1、概率大，则分解次数小；概率小则分解次数多。这符合最佳码原则。2、码字集合是唯一的
26、。3、分解完了，码字出来了，码长也有了,即先有码字后有码长。因此，费诺编码方法又称为子集分解法。3.4费诺编码的实例例题：信源符号及其概率仍如香农码中的例题所示。编码过程及编码结果如下表所示：消息符Xi符号概率P(Xi)第一次第二次第三次第四次二元码码长X10.200002X20.19100103X30.1810113X40.1710102X50.15101103X60.101011104X70.01111114该费诺码的平均码长为信息传输率为L = 1,m = 2很显然，费诺编码方法的效率要高于香农码。4 费诺编码的程序设计4.1费诺编码算法设计费诺编码也是一种常见的信源编码方法。信源符号以
27、概率递减的次序排列进来,将排列好的信源符号划分为两大组,使第组的概率和近于相同,并各赋于一个二元码符号”0”和”1”.然后,将每一大组的信源符号再分成两组,使同一组的两个小组的概率和近于相同,并又分别赋予一个二元码符号.依次下去,直至每一个小组只剩下一个信源符号为止.这样,信源符号所对应的码符号序列则为编得的码字3。4.2编码如下clc;clear;A=0.4,0.3,0.1,0.09,0.07,0.04;A=fliplr(sort(A);%降序排列m,n=size(A);for i=1:nB(i,1)=A(i);%生成B的第1列end%生成B第2列的元素a=sum(B(:,1)/2;for
28、k=1:n-1if abs(sum(B(1:k,1)-a)=abs(sum(B(1:k+1,1)-a)break;endendfor i=1:n %生成B第2列的元素if i=kB(i,2)=0;elseB(i,2)=1;endend%生成第一次编码的结果END=B(:,2);END=sym(END);%生成第3列及以后几列的各元素5j=3;while (j=0)p=1;while(p=n)x=B(p,j-1);for q=p:nif x=-1break;elseif B(q,j-1)=xy=1;continue;elsey=0;break;endendendif y=1q=q+1;endif
29、 q=p|q-p=1B(p,j)=-1;elseif q-p=2B(p,j)=0;END(p)=char(END(p),0;B(q-1,j)=1;END(q-1)=char(END(q-1),1;elsea=sum(B(p:q-1,1)/2;for k=p:q-2if abs(sum(B(p:k,1)-a)=abs(sum(B(p:k+1,1)-a);break; endendfor i=p:q-1if i=kB(i,j)=0;END(i)=char(END(i),0;elseB(i,j)=1;END(i)=char(END(i),1;endendendendp=q;endC=B(:,j);D
30、=find(C=-1);e,f=size(D);if e=nj=0;elsej=j+1;endendBAENDfor i=1:n u,v=size(char(END(i); L(i)=v;endavlen=sum(L.*A)图1 费诺编码程序设计图2 费诺编码程序设计4.3程序中要解决的关键问题 如何能够将编码与程序链接起来、程序中函数的调用、程序的调试方法等4.4总结本文将通过采用递归的思想进行费诺编码，求得了每个字符的二进制码字。并且对编码后的平均码长，以及编码的传输效率进行了求解。符合费诺编码的要求，得到了预期的编码结果。致谢词风景依稀去年时，人生喜乐皆不知。纵叹时光如斯水，两年脉脉送流
31、景。临近毕业了，让人感到很多不舍。两年的大学生生活，忙碌而充实，收获着师生情、同窗情，也收获着思想、智慧，收获着感动。能够顺利完成研究生学业，与我的家人、老师、同学和亲朋支持与帮助密不可分。首先，我衷心地感谢西藏大学为我提供了优异的学习生活环境，尤其感谢我的恩师王龙业老师。恩师为人坦诚，治学严谨，勤奋好学，是我院极具责任心的好老师。这些给了我做人与工作的标尺，我自知不能达到老师的高度，不过，在以后的工作与学习中定当以此为目标去从严要求自己。恩师学识渊博，见解深刻，思想睿智，在学术上常给予我具有针对性的指导，时常让我茅塞顿开，受益匪浅。在生活上恩师也时常能给予关注与关心，对生活中困惑，老师常常给
32、出良好的建议。在此再次对恩师表示衷心的感谢!同时，我要感谢全体同学，共同的学习让我倍受启发，因为大家的共同努力与相互帮助，才使得我们学业不断的向前发展，取得了不错的成果，也使得我们的友情日益深厚，时间虽不长，却视彼此为良师益友。另外，我要特别地感谢我的家人。感谢你们陪伴我成长，感谢你们培养了我良好的生活习惯，感谢你们对我一直在外求学的宽容与理解，感谢你们对我学习上一如既往的默默支持。千言万语也难以表达我对你们的感激之情与深深的敬意，祝福你们身体健康，万事如意！同时，感谢百忙中抽出宝贵时间审阅我论文的各位老师。谢谢您们对我论文所提出的宝贵意见！由于才疏学浅，论文之中难免有不足之处，恳请批评指正。
33、最后，感谢所有关心、支持和帮助过我的人们!参考文献1曹雪虹,张宗橙.信息论与编码.北京：清华大学出版社，2009.2.2樊昌信,曹丽娜.通信原理.北京：国防工业出版社,2006.9.3严蔚敏.吴伟民.数据结构.北京：清华大学出版社,2007.4谭浩强.c程序设计.北京：清华大学出版社,2005.5徐利民,舒君,谢优忠.基于MATLAB的信号与系统实验教程.北京：清华大学出版社,2010.2.6周炯磐.信息论基础.北京:人民邮电出版社，1983.7周炯磐,丁晓明.信源编码原理.北京:人民邮电出版社,1999.8周荫清.信息理论基础.北京:北京航空航天大学出版社,1993.9吴伯修,祝宗泰,钱霖君.信息论与编码.南京:东南大学出版社,1991.10阙喜戎.信息安全原理及应用.北京:清华大学出版社,2003.
