信息导论-第10讲-率失真函数1.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章,信息率,失真函数,4.1,基本概念,4.2,离散信源的信息率失真函数,4.3,连续信源的信息率失真函数,4.4,信息率失真函数与信息价值,4.5,信道容量与信息率失真函数的比较,4.6,保真度准则下的信源编码定理,4.7,信息论“三大定理”总结,第四章 信息率失真函数,1,4.1.1,引言,4.1.2,失真度与平均失真度,4.1.3,信息率失真函数的定义,4.1.4,信息率失真函数的性质,4.1,基本概念,2,(1)“,消息完全无失真传送”的可实现性,信道编码定理,：,无论何种信道，只要信息率,R小于信道容量,C,，总能找到一种编码，使在信道上能以任意小的错误概率和任意接近于,C,的传输率来传送信息。反之，若,R,C,，则传输总要失真。,完全无失真传送不可实现：,实际的信源常常是连续的，信息率无限大，要无失真传送要求信息率,R,为无穷大；,实际信道带宽是有限的，所以信道容量受限制。要想无失真传输，所需的信息率大大超过信道容量,R,C,。,4.1.1,引 言,4.1,基本概念,3,(2),实际中允许一定程度的失真,技术发展的需要,随着科学技术的发展，数字系统应用得越来越广泛，这就需要传送、存储和处理大量的数据。为了提高传输和处理效率，往往需要对,数据压缩,，这样也会带来一定的信息损失。人类社会已进入信息时代，信息爆炸的结果要求人们解决如何对浩如烟海的数据有效的压缩，减少数据的,存储容量,(,如各种数据库、电子出版物、多媒体娱乐,),、,传输时间,(,如数据通信和遥测,),、或,占有带宽,(,如多媒体通信、数字音频广播、高清晰度电视,),，要想方设法压缩给定消息 集合占用的,空间域、时间域和频率域资源,。,如海洋地球物理勘探遥测数据，用,60,路传感器，每路信号,1,KHz,，,16,位,A,/,D,量化，每航测,1,Km,就需记录,1,盘,0.5,英寸的磁带，一条测量船每年就可勘测,15000,Km,，数据流之大可见一斑。,4.1.1,引 言,4.1,基本概念,4,实际生活中的需要,实际生活中，人们一般并不要求获得完全无失真的消息，通常只要求近似地再现原始消息，即允许一定的失真存在。,例如,打电话：即使语音信号有一些失真，接电话的人也能听懂。人耳接收信号的带宽和分辨率是有限的。,放电影,：理论上需要无穷多幅静态画面，由于人眼的“视觉暂留性”，实际上只要每秒放映,24,幅静态画面。,有些失真没有必要完全消除。,4.1.1,引 言,4.1,基本概念,5,(3),信息率失真理论,信息率失真函数,香农定义了信息率失真函数,R,(,D,),。,定理指出,：,在允许一定失真度,D,的情况下，信源输出的信息率可压缩到,R,(,D,),。,信息率失真理论是,量化,（模数转换）数模转换,、,频带压缩,和,数据压缩,的理论基础。,4.1.1,引 言,4.1,基本概念,6,信息率失真函数极小值问题,I,(,X,;,Y,),是,P,(,X,),和,P,(,Y,/,X,),的二元函数；,在讨论信道容量时：,规定了,P,(,Y,/,X,),，,I,(,X,;,Y,),变成了,P,(,X,),的函数。在离散情况下，因为,I,(,X,;,Y,),对,p,(,x,i,),是上凸函数，所以变更,p,(,x,i,),所求极值一定是,I,(,X,;,Y,),的极大值；在连续情况下，变更信源,P,(,X,),求出的也是极大值，但求极值时还要一些其它的限制条件。,在讨论信息率时：,可规定,p,(,x,i,),，变更,p,(,y,j,/,x,i,),来求平均互信息的极值，称为,信道容量对偶问题,。,由于,I,(,X,;,Y,),是,p,(,y,j,/,x,i,),的下凸函数，所求的极值一定是极小值,。但若,X,和,Y,相互统计独立,(,p,(,y,j,/,x,i,)=,p,(,y,j,),，这个极小值就是,0,，因为,I,(,X,;,Y,),是非负的，,0,必为极小值，这样求极小值就没意义了。,引入一个失真函数，计算在失真度一定的情况下信息率的极小值就变的有意义了。,4.1.1,引 言,4.1,基本概念,7,4.1.2,失真度与平均失真度,(1),信息率与失真的关系,(2),失真度,(3),常用的失真函数,(4),平均失真度,(5),N,次扩展信道的平均失真度,4.1,基本概念,8,(1),信息率与失真的关系,信道中固有的噪声和不可避免的干扰，使信源的消息通过信道传输后造成误差和失真,误差或失真越大，接收者收到消息后对信源存在的不确定性就越大，获得的信息量就越小，信道传输消息所需的信息率也越小。,4.1.2,失真度与平均失真度,4.1,基本概念,9,4.1.2,失真度与平均失真度,(2),失真度,失真度,设离散无记忆信源为,4.1,基本概念,10,4.1.2,失真度与平均失真度,对每一对,(,x,i,y,j,),，指定一个非负函数,d,(,x,i,y,j,)0,i1,2,n,j,=1,2,m,称,d,(,x,i,y,j,),为,单个符号的失真度,/,失真函数。表示信源发出一个符号,x,i,，在接收端再现,y,j,所引起的误差或失真。,4.1,基本概念,11,4.1.2,失真度与平均失真度,失真矩阵,失真度还可表示成矩阵的形式,称,D,为失真矩阵。它是,n,m,阶矩阵。,连续信源和连续信道的失真函数,在连续信源和连续信道情况下，失真度定义为,d,(,x,y,)0,4.1,基本概念,12,4.1.2,失真度与平均失真度,(3),常用的失真函数,第一种,当,i,=,j,时，,X,与,Y,的取值一样，用,Y,来代表,X,就没有误差，所以定义失真度为,0,；当,i,j,时，用,Y,代表,X,就有误差。,这种定义认为对所有不同的,i,和,j,引起的误差都一样，所以定义,失真度常数,a,。,失真矩阵的,特点是对角线上的元素均为,0,，对角线以外的其它元素都为常数,a,。,4.1,基本概念,13,4.1.2,失真度与平均失真度,当,a,=1,时的失真函数称为汉明失真函数,。,第二种：,d,(,x,i,y,j,)=(,y,j,x,i,),2,这种函数称为,平方误差失真函数,，失真矩阵称为,平方误差失真矩阵,。,若信源符号代表输出信号的幅度值，则较大的幅度失真比较小的幅度失真引起的错误更为严重，严重程度用平方表示。,失真函数是根据人们的实际需要和失真引起的损失、风险、主观感觉上的差别大小等因素,人为规定的,。,4.1,基本概念,14,4.1.2,失真度与平均失真度,(4),平均失真度,平均失真度定义,d,(,x,i,y,j,),只能表示两个特定的具体符号,x,i,和,y,j,之间的失真。,平均失真度,：平均失真度为失真度的数学期望，,4.1,基本概念,15,4.1.2,失真度与平均失真度,平均失真度意义,是在平均意义上，从总体上对整个系统失真情况的描述。它是信源统计特性,p,(,x,i,),、信道统计特性,p,(,y,j,/,x,i,),和失真度,d,(,x,i,y,j,),的函数。当,p,(,x,i,),，,p,(,y,j,/,x,i,),和,d,(,x,i,y,j,),给定后，平均失真度就不是一个随机变量了，而是一个确定的量。,如果信源和失真度一定，就只是信道统计特性的函数。信道传递概率不同，平均失真度随之改变。,保真度准则,人们所允许的失真指的都是平均意义上的失真。,保真度准则,：规定平均失真度 不能超过某一限定的值,D,，即 ，则,D,就是允许失真的上界。该式称为保真度准则。,4.1,基本概念,16,4.1.2,失真度与平均失真度,(5),N,次扩展信道的平均失真度,N,次扩展,单符号离散无记忆信源,X,x,1,x,2,x,n,的,N,次扩展信源,X,N,=,X,1,X,2,X,N,，在信道中的传递作用相当于单符号离散无记忆信道的,N,次扩展信道，输出也是一个随机变量序列,Y,N,=,Y,1,Y,2,Y,N,。,此时输入共有,n,N,个不同的符号,信道的输出共有,m,N,个不同的符号,4.1,基本概念,17,4.1.2,失真度与平均失真度,定义离散无记忆信道,X,P,(,Y,/,X,),Y,的,N,次扩展信道的,输入序列,a,i,和,输出序列,b,j,之间的失真函数为,上式说明：离散无记忆信道的,N,次扩展信道输入输出之间的失真，等于输入序列,a,i,中,N,个信源符号,x,i,1,x,i,2,x,iN,各自通过信道,X,P,(,Y,/,X,),Y,，分别输出对应的,N,个信宿符号,y,j,1,y,j,2,y,jN,后所引起的,N,个单符号失真,d,(,x,ik,y,jk,)(,k,=1,2,N,),之和。,4.1,基本概念,18,N,次扩展的失真度,定义,N,次离散无记忆扩展信源和信道的平均失真度为 ，则,4.1.2,失真度与平均失真度,4.1,基本概念,19,“,N,次扩展”与“单符号”平均失真度的关系,由扩展信源和扩展信道的无记忆性有,4.1.2,失真度与平均失真度,4.1,基本概念,20,实际上，,(,k,=1,2,N,),是同一信源,X,在,N,个不同时刻通过同一信道,X,P,(,Y,/,X,),Y,所造成的平均失真度，因此都等于单符号信源,X,通过信道,X,P,(,Y,/,X,),Y,所造成的平均失真度，即,上式说明：,离散无记忆,N,次扩展信源通过离散无记忆,N,次扩展信道的平均失真度是单符号信源通过单符号信道的平均失真度的,N,倍,。,4.1.2,失真度与平均失真度,4.1,基本概念,21,N,次扩展的保真度准则,离散无记忆,N,次扩展信源通过离散无记忆,N,次扩展信道的保真度准则为,4.1.2,失真度与平均失真度,4.1,基本概念,22,4.1.3,信息率失真函数的定义,(1),试验信道,(2),信息率失真函数,(3),求信息率失真函数的方法,(4),研究信道编码和率失真函数的意义,4.1,基本概念,23,4.1.3,信息率失真函数的定义,(1),试验信道,单符号信源和单符号信道的试验信道,当固定信源（,P,(,X,),已知），单个符号失真度也给定时，选择信道使 。凡满足要求的信道称为,D,失真许可的试验信道,，简称试验信道。,所有试验信道构成的集合用,P,D,来表示，即,N,次扩展的试验信道,对于离散无记忆信源的,N,次扩展信源,和离散无记忆信道的,N,次扩展信道,，其试验信道集合,P,D,(,N,),为,4.1,基本概念,24,(2),信息率失真函数,单符号信源和单符号信道的信息率失真函数,在信源和失真度给定以后，,P,D,是满足保真度准则 的试验信道集合，平均互信息,I,(,X,;,Y,),是信道传递概率,p,(,y,j,/,x,i,),的下凸函数，所以在,P,D,中一定可以找到某个试验信道，使,I,(,X,;,Y,),达到最小，即,这个最小值,R,(,D,),称为信息率失真函数,，简称,率失真函数,。,在信源给定以后，总希望在允许一定失真的情况下，传送信源所必须的信息率越小越好。,从接收端来看，就是在满足保真度准则 的条件下，寻找再现信源消息必须的最低平均信息量，即平均互信息的最小值,。,4.1.3,信息率失真函数的定义,4.1,基本概念,25,“,N,次扩展”的信息率失真函数,对于离散无记忆信源的,N,次扩展信源和离散无记忆信道的,N,次扩展信道，在所有满足保真度准则 的,N,维试验信道集合中，一定可以寻找到某个信道使平均互信息取最小值R,N,(,D,),，这个最小值称为它的信息率失真函数。,由信源和信道的无记忆性，可以证明,R,N,(,D,)=,NR,(,D,),。,4.1.3,信息率失真函数的定义,4.1,基本概念,26,(3),求信息率失真函数的方法,对偶问题,平均互信息,I,(,X,;,Y,),既是信源概率分布,p,(,x,i,),的上凸函数，又是信道传递概率,p,(,y,j,/,x,i,),的下凸函数。率失真函数,R,(,D,),是在允许失真,D,和信源概率分布,p,(,x,i,),已给的条件下，求平均互信息的极小值（最小）问题，而信道容量,C,是在信道特性,p,(,y,j,/,x,i,),已知的条件下求平均互信息的极大值（最大）问题。这两个问题是对偶问题。,4.1.3,信息率失真函数的定义,4.1,基本概念,27,求信道容量的方法,信道容量是假定信道固定的前提下，选择一种试验信源，使信息率最大。一旦找到了这个信道容量，它就与信源不再有关，而是信道特性的参量，随信道特性的变化而变化。,4.1.3,信息率失真函数的定义,4.1,基本概念,28,求信息率失真函数的方法,信息率失真函数,R,(,D,),是假定信源给定的情况下，在用户可以容忍的失真度内再现信源消息所必须获得的最小平均信息量。它反映的是信源可压缩程度。率失真函数一旦找到，就与求极值过程中选择的试验信道不再有关，而只是信源特性的参量。不同的信源，其,R,(,D,),是不同的。,4.1.3,信息率失真函数的定义,4.1,基本概念,29,(4),研究信道编码和率失真函数的意义,研究信道容量的意义：,在实际应用中，研究信道容量是为了解决在已知信道中传送最大信息率问题。目的是充分利用已给信道，使传输的信息量最大而发生错误的概率任意小，以,提高通信的可靠性,。这就是,信道编码,问题。,研究信息率失真函数的意义：,研究信息率失真函数是为了解决在已知信源和允许失真度,D,的条件下，使信源必须传送给信宿的信息率最小。即用尽可能少的码符号尽快地传送尽可能多的信源消息，以,提高通信的有效性,。这是,信源编码,问题。,4.1.3,信息率失真函数的定义,4.1,基本概念,30,4.1.4,信息率失真函数的性质,(1),率失真函数的定义域,什么是率失真函数的定义域,允许平均失真度,：,率失真函数中的自变量,D,，也就是人们规定的平均失真度 的上限值。,率失真函数的定义域,问题就是在信源和失真函数已知的情况下，讨论,允许平均失真度,D,的最小和最大值问题,。,D,的选取必须根据固定信源,X,的统计特性,P,(,X,),和选定的失真函数,d,(,x,i,y,j,),，在平均失真度 的可能取值范围内。,4.1,基本概念,31,4.1.4,信息率失真函数的性质,信源最小平均失真度,D,min,是非负函数,d,(,x,i,y,j,),的数学期望，也是一个非负函数，显然其下限为,0,。因此,允许平均失真度,D,的下限也必然是,0,，这就是不允许有任何失真的情况。,允许平均失真度,D,能否达到其下限值,0,，与单个符号的失真函数有关。,信源最小平均失真度,D,min,：对于每一个,x,i,，找出一个,y,j,与之对应，使,d,(,x,i,y,j,),最小，不同的,x,i,对应的最小,d,(,x,i,y,j,),也不同。这相当于在失真矩阵的每一行找出一个最小的,d,(,x,i,y,j,),，各行的最小,d,(,x,i,y,j,),值都不同。对所有这些不同的最小值求数学期望，就是信源的最小平均失真度。,4.1,基本概念,32,4.1.4,信息率失真函数的性质,只有当失真矩阵的每一行至少有一个,0,元素时，信源的平均失真度才能达到下限值,0,。,当,D,min,=0,时（信源不允许任何失真存在）,，信息率至少应等于信源输出的平均信息量（信源熵），即,R,(0)=,H,(,X,),。,连续信源有 。这时虽然信源熵是有限的，但信息量是无穷大。实际信道容量总是有限的，无失真传送这种连续信息是不可能的。只有当允许失真（,R,(,D,),为有限值），传送才是可能的。,4.1,基本概念,33,4.1.4,信息率失真函数的性质,信源最大平均失真度,D,max,信源最大平均失真度,D,max,：必须的信息率越小，容忍的失真就越大。当,R,(,D,),等于,0,时，对应的平均失真最大，也就是,函数,R,(,D,),定义域的上界值,D,max,。,信息率失真函数是平均互信息的极小值：,当,R,(,D,)=0,时，即平均互信息的极小值等于,0,；,当,D,D,max,时，从数学意义上讲，因为,R,(,D,),是非负函数，所以它仍只能等于,0,。这相当于输入,X,和输出,Y,统计独立。意味着,在接收端收不到信源发送的任何信息,，与,信源不发送任何信息,等效。或者说,传送信源符号的信息率可以压缩至,0,。,4.1,基本概念,34,4.1.4,信息率失真函数的性质,计算,D,max,的值,令试验信道特性,p,(,y,j,/,x,i,)=,p,(,y,j,)(,i,=1,2,n,),这时,X,和,Y,相互独立，等效于通信中断，因此,I,(,X,;,Y,)=0,，即,R,(,D,)=0,。,满足上式的试验信道有许多，相应地可求出许多平均失真值，从中选取最小的一个，就是这类平均失真值的上界,D,max,。,上式是用不同的概率分布,p,(,y,j,),对,D,j,求数学期望，取数学期望当中最小的一个作为,D,max,。,4.1,基本概念,35,4.1.4,信息率失真函数的性质,实际是用,p,(,y,j,),对,D,j,进行线性分配，使线性分配的结果最小。当,p,(,x,i,),和,d,(,x,i,y,j,),给定时，必可计算出,D,j,，,D,j,随,j,的变化而变化，,p,(,y,j,),是任选的，只需满足非负性和归一性。若,D,s,是所有,D,j,当中最小的一个，可取,p,(,y,s,)=1,，其它,p,(,y,j,),为,0,，这时,D,j,的线性分配（数学期望）必然最小，即,4.1,基本概念,36,4.1.4,信息率失真函数的性质,4.1,基本概念,37,4.1.4,信息率失真函数的性质,例,4.1.1,二元信源 ，相应的失真矩阵 ，,计算,D,max,。,先计算,D,j,：,D,1,0.4,D,2,=0.6,所以,D,max,=min(,D,1,D,2,)=0.4,4.1,基本概念,38,4.1.4,信息率失真函数的性质,结 论,R,D,),的定义域为,(,D,min,D,max,),；,一般情况下,D,min,=0,，,R,(,D,min,)=,H,(,X,),；,当,D,D,max,时，,R,(,D,)=0,；,当,D,min,D,D,max,时，,0,R,(,D,),H,(,X,),。,4.1,基本概念,39,4.1.4,信息率失真函数的性质,(2),率失真函数对允许平均失真度的下凸性,对任一,0,1,和任意平均失真度,D,，,D,D,max,，有,R,D,+(1,),D,R,(,D,)+(1,),R,(,D,),(3),率失真函数的单调递减和连续型,由于函数,R,(,D,),具有凸状性，保证了它在定义域内是连续的。,在,D,min,D,D,max,范围内,R,(,D,),单调递减。,4.1,基本概念,40,4.1.4,信息率失真函数的性质,图说明：,R,(0),=,H,(,X,),，,R,(,D,max,),=0,，,决定了曲线边缘上的两个点；,在,0,和,D,max,之间，,R,(,D,),是单,调递减的下凸函数；,在连续信源时，当,D,0,时，,R,(,D,),，曲线将不与,R,(,D,),轴相交。,4.1,基本概念,41,