20104632汤云雪new

1、青 岛 农 业 大 学本 科 生 课 程 论 文论 文 题 目 信息率失真函数的研究与设计 学生专业班级 信息与计算科学2010级1班 学生姓名（学号） 汤云雪（20104632） 指 导 教 师 吴慧 完 成 时 间 2013/06/26 2013 年 06 月 26 日目录中文摘要1Abstract11信息论与编码技术的发展与简介22信息率失真函数及其性质 32.1失真测度 32.1.1单符号失真度42.1.2序列失真度42.1.3平均失真度42.2常见的失真函数52.2.1汉明失真52.2.2平方误差失真52.2.3绝对失真函数与相对失真函数52.2.4N次扩展信道62.3信息率失真函数

2、的定义及其性质6 2.3.1信息率失真函数的定义6 2.3.2信息率失真函数的性质6 3离散无记忆信源的信息率失真函数7 3.1等概率、对称失真信源的计算7 3.1.1二元等概率、对称失真信源7 3.1.2三元等概率、对称失真信源8 3.2离散无记忆信源的信息率失真函数的迭代算法8 3.2.1迭代算法的步骤9 3.2.2四元离散信源的迭代计算10 4总结10参考文献11附录 12 信息率失真函数的研究与设计信息与计算科学专业 汤云雪指导教师 吴慧摘要: 本文对信息率失真函数的计算方法展开分析讨论，并通过MATLAB数学软件实现。信息论是运用概率论与数理统计的方法进行研究的应用数学学科。随着人们

3、不断加深对信息的认识与利用，信息科学被应用在各个方面。然而，在实际的通信中，无失真的通信是不可能的，而且也无必要，因此，本文从离散信源着手，讨论平稳无记忆信源的信息传输过程及其特性，分析在限定失真为最大允许失真D时信源的最小信息速率。本文采用带参量的迭代法求解，通过MATLAB编写程序实现信源的信息率失真函数的计算。关键词： 率失真函数 MATLAB 迭代法 离散信源 The discussion and project of rate-distortion functionStudent majoring in Informationand Computing Sciences TangYu

4、nxueTutor WuhuiAbstract： This paper mainly discusses and analysises the calculation method of rate-distortion, and to solve by using mathematics software MATLAB(Matrix Laboratory).Information Theory is an Applied Mathematics which uses probability theory and mathematical statistics methods to do stu

5、dy.As people continue to deepen the understanding and use of information,information science is applied in many aspects.However,in actual communication,distortion-free communication is impossible,and not necessary,therefore,this paper proceed from the discrete source and source to discuss the inform

6、ation transfer process and feature of the stationary memoryless source, and analysis the Minimum information rate of information Source when limit distortion is the maximum allowable distortion D.In this paper,the iterative algorithm with parameters is used to calculate the R(D),the calculation of i

7、nformation rate distortion function of discrete source and continuous source is realized by programming.Key words: rate-distortion function MATLAB Iterative algorithm discrete source 1. 信息论与编码技术的发展与简介 随着现代科学技术的飞速发展，我们对周围世界的认识和理解不断加深。特别是20世纪60年代以来，计算机技术的迅猛发展、计算机及相关设备的迅速更新换代和个人微型计算机的普及，极大地提高了人们处理信息、存储

8、信息、控制和管理信息的能力，人类社会进入了信息时代。作为现代科学技术基础理论之一的信息论在各个领域的应用和推广使许多经典的概念有了全新的解释，使过去不确切的描述有了精确的定量分析方法。信息论与编码理论是在长期的通信工程实践和理论研究的基础上发展起来的。信息论从诞生至今已经历半个多世纪，目前已成为一门独立的学科。而编码理论与技术研究也有半个世纪的历史，并从刚开始时作为信息论的一个组成部分逐步发展成为比较完善的独立体系。最早对信息进行科学定义的是哈特莱，他在1928年发表的信息传输一文中，首先提出“信息”这一概念。但是哈特莱的理解没有考虑各种可能选择方法的统计特性的局限，限制了其适用范围。1948

9、年，控制论创始人之一维纳出版了控制论动物和机器中通信与控制问题一书，将“信息”上升到“最基本概念”的位置。意大利学者朗格提出用差异量来测度信息，认为“信息就是差异”，这是不全面、不确切的。香农在1948年发表了著名的论文通信的数学理论，从研究通信系统传输的实质出发，对信息作了科学的定义，并进行了定性和定量的描述。他用概率测度和数理统计的方法系统地讨论了通信的基本问题，得出了无失真信源编码定理和有噪环境下的信道编码定理，由此奠定了现代信息论的基础。1959年香农又发表了论文“保真度准则下的离散信源编码定理”，发展成为信息率失真理论，这一理论是信源编码的核心。1961年香农的论文双路通信信道开拓了

10、多用户信息论的研究。20世纪50年代初期，汉明提出了一种重要的线性分组码汉明码。1957年普兰奇提出了循环码。1959年霍昆格姆、1960年博斯和查德胡里各自分别提出了BCH码，可纠正多个随机错误的码。1955年埃利斯提出了不同于分组码的卷积码，接着伍成克拉夫提出了卷积码的序列译码。1967年维特比提出了卷积码的最大似然译码法，该方法效率高、速度快、译码较简单。1966年福尼提出级联码概念。信源编码的研究由维纳于1942年进行了开创性的工作。1952年霍夫曼提出了无失真信源编码方法Huffman码。20世纪60年代到70年代，开始将正交变换用于信源压缩编码，先后提出DFT、DCT、WHT、ST

11、、KLT等多种变换。从20世纪90年代初开始，主要针对图像类信源的特点提出了多种新的压缩原理和方法，包括小波变换编码、分形编码、模型编码等。目前，对信息论的研究主要包括三种理解：狭义信息论、一般信息论和广义信息论。信息论不仅在方法论的层面上解决通信的有效性和可靠性问题，而且在认识论的层面上帮助人们认识事物的本质。信息论的创立，信息编码的基础和应用研究的开展有力地推动了信息技术的进步和信息全球化的进程，对人类社会的发展和人们生活水平的提高起到了不可磨灭的积极作用。随着社会信息化的不断深入，我们对信息的要求也越来越高。无失真信源编码定理和有噪信道编码定理告诉我们：只要信道的信息传输速率R小于信道容

12、量C，总能找到一种编码方法，使得在该信道上的信息传输的差错概率任意小；反之，若信道的信息传输速率R大于信道容量C，则不可能使信息传输差错概率任意小。但是，无失真的编码并非总是可能的，在实际应用中，信宿的灵敏度和分辨力都是有限的，无需要求在信息传输过程中绝对无失真。由于信道噪声的影响，即使信源消息的编码是无失真的，信息在传输过程也会产生差错或失真。因此，在实际信息传输系统中，失真是不可避免的，有时甚至是必要的。在允许一定程度失真的条件下，能够多大程度地压缩信息，即最少需要多少比特数才能描述信源，由此对率失真函数的研究是很有必要的。2. 信息率失真函数及其性质2.1失真测度限失真信源编码的系统模型

13、如图1所示。信源发出的信息X通过有失真的信源编码，编码后的输出通过理想无噪信道传输，接收信息经信源译码后的输出为Y，由于信源编码是有失真的编码，因此输出的Y不是信源发出的消息X的精确重现。为了定量描述信源传输速率与失真之间的关系，已经假定传输信道为理想无噪信道。另外，可以将信源编码器引起的失真视为由于信道不理想所造成的，即将有失真信源编码器和接收译码器之间的过程一并看作有噪声的信道，这个假想的信道称为试验信道。这样就把有失真信源编码的问题转化为无失真的信源通过有噪信道传输的问题，进而通过研究试验信道输入与输出之间的互信息来研究限失真信源编码。信宿信源译码器无噪信道信源X信源编码器XY 试验信道

14、（假想信道）图1 限失真信源编码的系统模型2.1.1单符号失真度设离散无记忆信源 ，信源符号通过试验信道传送到输出端 ，试验信道矩阵 ，对一对指定函数，表示输入在输出端再现的错误或失真程度，称为单符号失真度，或单符号失真函数。通常规定越小表示引起的失真越小，显然表示没有失真。信源符号集的大小为n，译码器输出符号集的大小为m，因此有个单符号失真度，将其写成矩阵形式，即 称为失真矩阵。2.1.2序列失真度设，。则序列失真度定义为 2.1.3平均失真度失真函数在随机变量X和Y的联合概率空间中的统计平均值，即上式称为单符号平均失真，表示有信源X和试验信道组成的通信系统的平均失真度。序列平均失真为 。“

15、人们允许的失真”通常采用规定系统的平均失真D不能超过某一限定值（规定）的形式来体现，即通常所说的保真度准则。2.2常见的失真函数2.2.1 汉明失真 假设失真函数 ，则失真矩阵为 。 当时，为汉明失真，称为汉明失真矩阵。2.2.2 平方误差失真 离散无记忆信源，接收符号，这该信源的平方误差失真为 。2.2.3 绝对失真函数与相对失真函数设信源，接收符号集，则失真函数称为该信源的绝对失真函数，失真函数称为该信源的相对失真函数。2.2.4 次扩展信道对于离散无记忆信源，其次扩展信源为，次扩展信道为。其输入符号为，输出符号为。该次扩展信源的失真函数为 该次扩展信源的平均失真度为2.3信息率失真函数的

16、定义及其性质2.3.1 信息率失真函数的定义在信源X给定、失真度被确定的条件下，就可以通过选择适当的信道，使系统平均失真度满足保真度准则。凡是满足保真度准则的信道，都称为许可试验信道。所有许可试验信道的集合用表示，即 。在许可试验信道集合中，总可以找到某一试验信道，使信道信息传输速率达到最小值。记此最小值为，即 。则函数被称为信源的信息速率失真函数，简称率失真函数。其逆函数称为失真率函数，表示一定信息速率下可能达到的最小的平均失真。2.3.2信息率失真函数的性质 1.的定义域为，且 ， 2.设,为任意两个平均失真，则有即是关于平均失真度的下凸函数。3.由信息率失真函数的下凸性可知，在上连续。又

17、由函数的非增性且不为常数知，是区间上的严格单调递减函数。3. 离散无记忆信源的信息率失真函数已知信源的概率分布和失真函数，就可求得信源的信息率失真函数。即求其约束条件为3.1等概率、对称失真信源的计算对于等概率、对称失真的信源，存在一个试验信道，其转移概率矩阵与失真矩阵具有相同的对称性，且该试验信道达到信息率失真函数。3.1.1 二元等概率、对称失真信源有一个二元、等概、平稳、无记忆信源，接受符号集，且失真矩阵为汉明矩阵，求率失真函数。由于信源概率为等概分布，失真函数具有对称性，因此，存在着与失真矩阵具有同样对称性的转移概率分布达到率失真。将该转移概率矩阵写为，对应此转移概率矩阵的平均失真。由

18、MATLAB编程得到对应的率失真函数结果（源程序见附录1）：当D=0时，即无失真。当有失真时，取 D=0.2，得RD =0.2781, D=0.4，得RD =0.0290， D=0.6，得RD =0.0290， D=0.8，得RD =0.2781。3.1.2 三元等概率、对称失真信源有一个三元、等概、平稳、无记忆信源，接收符号集，且规定失真矩阵为汉明矩阵，求其率失真函数。对于该信源，其转移概率矩阵可写为 。对应此转移概率矩阵的平均失真。因此，。由此求出互信息为：由MATLAB编程得到信息率失真函数结果如下（源程序见附录2）：当D=0时，即无失真。当有失真时，取 D=0.2，得RD =0.663

19、0, D=0.4，得RD =0.2140， D=0.6，得RD =0.0140， D=0.8，得RD =0.0630。3.2 离散无记忆信源的信息率失真函数的迭代算法达到率失真函数的条件概率和输出符号的概率分布都不一定是唯一的。3.2.1 迭代算法的步骤离散无记忆信源的信息率失真函数的迭代算法可按以下步骤进行：（1） 先假设一个负数作为，选定初始转移概率组成阶初始矩阵。（2） 把选定的初始转移概率代入表达式中，得到相应的，然后将代入表达式 中，得到相应的。（3）在将代入表达式中，得到相应的，然后将代入表达式中，得到相应的。（4）以此类推，直到与非常接近，其差别在允许的精度范围之内，且与非常接近

20、，其差别也在允许的精度范围之内，则或就是所对应的信息率失真函数的近似值。（5）再选定一略大些的负数作为，重复以上的迭代步骤，可得到所对应的信息率失真函数的近似值。（6）反复迭代，直到信息率失真函数接近于零为止，就可得到信息率失真函数的曲线。3.2.2 四元离散信源的迭代计算设一个四元信源，接收符号，失真矩阵为汉明矩阵，求信源的函数。对于此四元对称信源在汉明失真矩阵下，其平均失真度根据最小、最大允许失真度的定义可得：，由r元离散对称信源得：MATLAB运行结果如下（源程序见附录3）：输入的数据为：d=0.25 0.25 0.25 0.25;r=4;s=4;S=-99.5;times=100;输出

21、的结果为：ans= 0.164746936130 0.281840602558 0.278737326470 0.274675134840 0.272718322130 0.171635075922 0.279862596375 0.275784005571 0.272384386123 0.282631901283 0.169537396872 0.275446315720 0.271948497445 0.282179613809 0.279072604953 0.166799283792对应的信息率失真函数曲线如图2： 图2 信息率失真函数曲线4.总结本文是以信息率失真函数为主题展开的研

22、究。其中讨论了信息率失真函数的具体定义，研究背景和现实意义，信息率失真函数是在假定信源给定的情况下，在满足保真度准则下再现信源消息所必须获得的最小的平均信息量，它反映了信源可以压缩的程度。实际上，计算一般离散信源的信息率失真函数是相当复杂和困难的，必须借助计算机。本文在求解信息率失真函数时采用了迭代法，其中待定常数S就是的斜率，根据的S参量表述，得到的函数曲线。在求解信息率失真函数时，达到信息率失真函数的转移概率不一定是唯一的。参考文献：1 冯桂，林其伟，陈东华.信息论与编码技术.清华大学出版社.2011,6（2）2 曹雪虹，张宗橙.信息论与编码.清华大学出版社.20043 唐向宏，岳恒立，郑

23、雪峰.MATLAB及在电子信息类课程中的应用.电子工业出版社.20064 周品，赵新芬.MATLAB数理统计分析.国防工业出版社.2009.45 曲炜，朱诗兵.信息论基础及应用.清华大学出版社.2005.46 Cover Thomas M,Thomas Joy A. Elements of Information Theory. New York:Wiley,1991附录1：clear all;D=0.8;px=1/2 1/2;Hx=-px*log2(px);pyx=1-D D;Hyx=-pyx*log2(pyx);RD=Hx-Hyx附录2：clear all;D=0.8;px=1/3 1/3

24、 1/3;Hx=-px*log2(px);pyx=1-D D/2 D/2;Hyx=-pyx*log2(pyx);RD=Hx-Hyx附录3：clear all;function=RateDF(Pa,d,S)format longd=input(失真矩阵d=);Pa=input(输入概率分布Pa=);n=input(输入信源数n=);m=input(输出信源数m=);S=input(拉式乘子S=);times=input(迭代次数times=);n,m=size(d);if(length(find(Pa=0)=0)error(Not a prob.vector,shoud be positive

25、component!);endif(r=length(Pa)error(The parameters do not match!);endPba=;RS=;DS=;r=1;for z=1:timesPba(1:n,1:m,1)=1/s*ones(r,s);for j=1:m Pb(j.1)=0; for i=1:n Pb(j,1)=Pb(j,i)+Pa(i)*Pba(i,j,1); endendfor i=1:n temp(i)=0; for j=1:m temp(i)=temp(i)+Pb(j,1)*exp(S(r)*d(i,j); endendfor i=1:n for j=1:m Pba(i,j,2)=(Pb(j,1)*exp(S(m)*d(i,j)/temp(i); end D(1)=0; for i=1:n for j=1:m D(1)=D(1)+Pa(i)*Pba(i,j,1)*d(i,j); end end R(1)=0; for i=1:n for j=1:s if（Pba(i,j,1)=0) R(1)=R(1)+Pa(i)*Pba(i,j,1)*log2(Pba(i,j,1)/Pb(j,1); end end end s=2; while(1) for j=1:m Pb(j