第四章 信息率失真函数精选文档.ppt
第四章 信息率失真函数本讲稿第一页,共八十一页为什么要讨论为什么要讨论信息率失真函数信息率失真函数R(D)?失真在传输中是不可避免的。失真在传输中是不可避免的。连续信源输出的信息量为无穷大连续信源输出的信息量为无穷大,不可能实现无失真信源编码不可能实现无失真信源编码.接收者接收者(信宿信宿)无论是人还是机器设备,都有一定的分辨能力与无论是人还是机器设备,都有一定的分辨能力与 灵敏灵敏度,超过分辨能力与灵敏度的信息传送过程是毫无意义的。即使信宿度,超过分辨能力与灵敏度的信息传送过程是毫无意义的。即使信宿能分辨、能判别,但对通信质量的影响不大,也可以称它为能分辨、能判别,但对通信质量的影响不大,也可以称它为允许范围允许范围内的失真内的失真。如果如果RC,就必须对信源压缩,使得压缩后的,就必须对信源压缩,使得压缩后的R*C,但同时要求引,但同时要求引入的失真不能超过规定的限度。入的失真不能超过规定的限度。对于给定的信源,在允许失真的条件下信源熵所能压缩的理论极限值就对于给定的信源,在允许失真的条件下信源熵所能压缩的理论极限值就是率失真函数是率失真函数R(D)。本讲稿第二页,共八十一页综上所述,一般可以对信源输出的信息进行综上所述,一般可以对信源输出的信息进行限失真限失真处理,处理,降低信息率,提高传输效率。降低信息率,提高传输效率。在允许一定程度的失真条件下,能够把信息压缩到什么程在允许一定程度的失真条件下,能够把信息压缩到什么程度?需要多少比特的信息率才能描述信源?度?需要多少比特的信息率才能描述信源?本章主要讨论一定程度的失真情况下所需的最少的信息率,本章主要讨论一定程度的失真情况下所需的最少的信息率,即信息率失真函数即信息率失真函数R(D)。思路:思路:从分析从分析失真函数、平均失真失真函数、平均失真出发求出信息率失真出发求出信息率失真函数函数R(D)。本讲稿第三页,共八十一页l控制信息失真的原因控制信息失真的原因?在实际问题中,信号有一定的失真是在实际问题中,信号有一定的失真是可以容忍的。但是当失真大于某一限度后,可以容忍的。但是当失真大于某一限度后,信息质量将被严重损伤,甚至丧失其实际信息质量将被严重损伤,甚至丧失其实际价值。要规定失真限度,必须先有一个定价值。要规定失真限度,必须先有一个定量的失真测度。量的失真测度。4.1 基本概念本讲稿第四页,共八十一页4.1.1 失真函数和平均失真度失真函数和平均失真度 一、失真函数一、失真函数1.失真函数的定义失真函数的定义假如某一信源假如某一信源X,输出样值为,输出样值为ai ,经过失真编码器,输出,经过失真编码器,输出Y,样值为,样值为bj 。对于每一对。对于每一对(ai,bj),指定一个,指定一个非负函数非负函数 为单个符号的失真度或失真为单个符号的失真度或失真函数函数说明:说明:如果如果 ai=bj,i=1,2,n,j=1,2,则没有失真。则没有失真。(4-1-1)如果如果ajbj,就产生了失真。,就产生了失真。失真的大小,用一个量来表示,即失真函数失真的大小,用一个量来表示,即失真函数d(ai,bi),以衡量用,以衡量用bj代替代替ai所引起的所引起的失真程度失真程度。本讲稿第五页,共八十一页失真函数:失真函数:是人们根据实际需要和失真引起的损失、风险、是人们根据实际需要和失真引起的损失、风险、主观感觉上的差别大小等因素主观感觉上的差别大小等因素人为规定人为规定的。的。2.常用的失真函数常用的失真函数 均方失真函数:均方失真函数:d(ai,bj)=(ai bj)2 (平方误差失真函数平方误差失真函数)绝对失真函数:绝对失真函数:d(ai,bj)=ai bj 相对失真函数:相对失真函数:d(ai,bj)=ai b/ai 误码失真函数:误码失真函数:d(aj,bj)=(汉明失真函数)(汉明失真函数)本讲稿第六页,共八十一页均均方方失失真真函函数数、绝绝对对失失真真函函数数和和相相对对失失真真函函数数适适用用于于连连续续信信源源;误码失真适用于误码失真适用于离散信源离散信源。(2)(2)失真函数比较失真函数比较均均方方失失真真和和绝绝对对失失真真只只与与(aibj)有有关关,而而不不是是分分别别与与ai及及bj有有关关,在在数学处理上比较方便数学处理上比较方便.相相对对失失真真与与主主观观特特性性比比较较匹匹配配,因因为为主主观观感感觉觉往往往往与与客客观观量量的的对对数成正比,但在数学处理中就要困难得多。数成正比,但在数学处理中就要困难得多。其其实实选选择择一一个个合合适适的的、完完全全与与主主观观特特性性匹匹配配的的失失真真函函数数是是非非常常困困难难的的,更更不不用用说说还还要要易易于于数数学学处处理理。当当然然不不同同的的信信源源应应有有较较好好的的失失真函数,所以在实际问题中还可以提出许多其他形式的失真函数。真函数,所以在实际问题中还可以提出许多其他形式的失真函数。说明:说明:(1)1)常用失真函数及其适用性常用失真函数及其适用性本讲稿第七页,共八十一页3.3.失真矩阵失真矩阵将所有的失真函数将所有的失真函数 d(ai,bj),i=1,2,n;j1,2,m排列起来,用矩阵表示为排列起来,用矩阵表示为 本讲稿第八页,共八十一页【例例4.1.1】设设信信源源符符号号序序列列为为X0,1,接接收收端端收收到到符符号号序序列列为为Y0,1,2,规定失真函数为规定失真函数为 d(0,0)d(1,1)=0;d(0,1)=d(1,0)=1 d(0,2)=d(1,2)=0.5求:失真矩阵求:失真矩阵d?解:解:失真矩阵为失真矩阵为 l失真函数的数值是依据实际应用情况,用失真函数的数值是依据实际应用情况,用bj代替代替ai所导致的失真大小是人所导致的失真大小是人为决定的。上例中用为决定的。上例中用b=2代替代替a=0和和a=1所导致的失真程度相同,均为所导致的失真程度相同,均为0.5;而用而用b=0代替代替a=1所导致的失真程度要大些,为所导致的失真程度要大些,为1 1。本讲稿第九页,共八十一页二、平均失真度二、平均失真度1.离散随机变量平均失真度定义离散随机变量平均失真度定义 失真函数的数学期望称为平均失真度。失真函数的数学期望称为平均失真度。说明说明:(1)由于由于ai和和bj都是随机变量,所以失真函数都是随机变量,所以失真函数d(ai,bj)也是也是随机变量,要分析整个信源的失真大小,只能用它的数学期望随机变量,要分析整个信源的失真大小,只能用它的数学期望或统计平均值来表示。或统计平均值来表示。本讲稿第十页,共八十一页(2)式中式中p(aibj)i=1,2,n,j=1,2,m是联合分布概率;是联合分布概率;p(ai)是是信源符号概率分布;信源符号概率分布;p(bj/ai):i=l,2,n,j l,2,m是转移概率分布;是转移概率分布;d(ai,bj):i=1,2,n,j=1,2,m是离散随机变量的失真函数。是离散随机变量的失真函数。(3)平均失真度是对给定信源平均失真度是对给定信源p(xi)经过某一种转移概率分布经过某一种转移概率分布p(yj/xi)的有失真的有失真信源编码器后产生失真的总体量度。信源编码器后产生失真的总体量度。(4)平均失真度已对信源和信道进行了统计平均,所以此值描述了某一信平均失真度已对信源和信道进行了统计平均,所以此值描述了某一信源在某一信道下的失真程度。源在某一信道下的失真程度。本讲稿第十一页,共八十一页因此因此 取决于以下几个因素:取决于以下几个因素:上式称为上式称为保真度准则保真度准则。(4.1.8)1 1)信源的统计特性,即信源的统计特性,即2 2)信道的统计特性,即信道的统计特性,即3 3)失真函数,即失真函数,即一般情况下,人们所允许的失真指的都是平均意义一般情况下,人们所允许的失真指的都是平均意义上的失真。如果规定其平均失真度上的失真。如果规定其平均失真度 不能超过某一限不能超过某一限定的值定的值D,即,即D就是允许失真的上界。就是允许失真的上界。本讲稿第十二页,共八十一页说明离散无记忆信道说明离散无记忆信道N次扩展信源通过离散无记忆次扩展信源通过离散无记忆N次次扩展信道的是单符号信道的平均失真度的扩展信道的是单符号信道的平均失真度的N倍。相应的倍。相应的保真度准则为保真度准则为 2.N次扩展信源的平均失真度次扩展信源的平均失真度单符号离散无记忆信源的单符号离散无记忆信源的N次扩展信源,在信道中的次扩展信源,在信道中的传递作用相当于单符号离散无记忆信道的传递作用相当于单符号离散无记忆信道的N次扩展信道,次扩展信道,输出也是一个随机变量序列。则输出也是一个随机变量序列。则N次离散次离散无记忆信源和信无记忆信源和信道道的平均失真度为的平均失真度为本讲稿第十三页,共八十一页4.1.2 信息率失真函数的定义信息率失真函数的定义一、保真度准则一、保真度准则对对于于信信道道容容量量为为C的的信信道道,在在传传输输信信息息率率为为R的的信信源源时时,如如果果RC,就就必必须须对对信信源源压压缩缩,使使其其压压缩缩后后的的信信息息传传输输率率R C,但但同同时时要要保保证证压压缩缩后所引入的失真不超过预先规定的限度。后所引入的失真不超过预先规定的限度。信信息息压压缩缩问问题题就就是是对对于于给给定定的的信信源源,在在满满足足平平均均失失真真度度 的的前提下,使信息率尽可能小。前提下,使信息率尽可能小。D 是允许失真的上界。是允许失真的上界。本讲稿第十四页,共八十一页二、二、D允许试验信道允许试验信道 将满足保真度准则的所有试验信道称为将满足保真度准则的所有试验信道称为D允许试验信道,用允许试验信道,用PD来表示来表示,即即三、分析方法三、分析方法 信源信源X经过有失真的信源编码器输出经过有失真的信源编码器输出Y,将这样的编码器看作存,将这样的编码器看作存在有干扰的在有干扰的假想信道假想信道,Y当作接收端的符号。这样就可用分析信道传输当作接收端的符号。这样就可用分析信道传输的方法来研究限失真信源编码的问题。的方法来研究限失真信源编码的问题。选择信源编码的方法:选择信源编码的方法:就变成了选择就变成了选择假想信道假想信道的问题,符号的问题,符号转移概率转移概率p(bj/ai)对应信道转移概率。信源编码器对应信道转移概率。信源编码器使信源编码后使信源编码后所需的信息传输率所需的信息传输率R尽量小。但尽量小。但R越小,引起的平均失真越小,引起的平均失真 就就越大。越大。本讲稿第十五页,共八十一页 给出一个失真的限定值给出一个失真的限定值D ,在满足平均失真,在满足平均失真 的条件下,选择一种编码方法,使得信息传输率的条件下,选择一种编码方法,使得信息传输率 R 尽可能小,尽可能小,即在即在PD中寻找一个信道使中寻找一个信道使 R 最小。最小。本讲稿第十六页,共八十一页信息率失真理论信息率失真理论研究了信源熵的压缩问题,但采用了研研究了信源熵的压缩问题,但采用了研究信道的方法,其中的究信道的方法,其中的P(bj/ai)并没有实际信道的意义,并没有实际信道的意义,它仅仅是在数学上将信源的压缩看作了通过一个信道。它仅仅是在数学上将信源的压缩看作了通过一个信道。四、信息率失真函数四、信息率失真函数R(D)的定义的定义 在在PD中寻找一个中寻找一个信道信道P(bj/ai),使给定的信源经过此信道传,使给定的信源经过此信道传输时,让其信道的传输率输时,让其信道的传输率R 达到最小,即达到最小,即R(D)的物理意义:的物理意义:对于给定的信源,在满足保真度准则下,信息率对于给定的信源,在满足保真度准则下,信息率R是是允允许压缩的最小值。许压缩的最小值。本讲稿第十七页,共八十一页说明说明:对于离散无记忆信源,对于离散无记忆信源,R(D)函数可写成函数可写成 理论基础:理论基础:I(X;Y)的下凸性的下凸性 对于固定的信源分布,平均互信息量对于固定的信源分布,平均互信息量I(X;Y)是信道是信道转移概率转移概率P(bj/ai)的下凸函数。也就是说存在一个信道,使的下凸函数。也就是说存在一个信道,使某一特定信源经过此信道传输时,信道的平均互信息量某一特定信源经过此信道传输时,信道的平均互信息量I(X;Y)达到最小值。达到最小值。本讲稿第十八页,共八十一页【例例4.1.2】已知信源编码器的输入概率分布为已知信源编码器的输入概率分布为:p(x)0.5,0.5,信道转移矩阵分别为,信道转移矩阵分别为:求求:平均互信息平均互信息I(X;Y),并比较其大小。,并比较其大小。本讲稿第十九页,共八十一页解:解:因为因为 p(ai bj)p(ai)p(bj/ai)(1)p(a1b1)=0.3,p(a1b2)=0.2,p(a2b1)=0.1,p(a2b2)=0.4因为因为所以所以 p(b1)=0.4,p(b2)=0.6 根据平均互信息公式可得根据平均互信息公式可得(2)同理可得)同理可得 I(X;Y)=0.397 比特符号比特符号 本讲稿第二十页,共八十一页五、五、R(D)与信道容量与信道容量C的比较的比较信道容量表示信道的最大传输能力,反映的是信道容量表示信道的最大传输能力,反映的是信道信道本身本身的特性,与信源无关。但由于平均互信息量与信源特性有关的特性,与信源无关。但由于平均互信息量与信源特性有关,为了排除信源特性对信道容量的影响,采用的做法是在所,为了排除信源特性对信道容量的影响,采用的做法是在所有的信源中以那个能够使平均互信息量达到最大的有的信源中以那个能够使平均互信息量达到最大的信源为参信源为参考考,从而使信道容量仅仅与信道特性有关。信道不同,从而使信道容量仅仅与信道特性有关。信道不同,C也不同。也不同。R(D)函数是在保真度准则条件下信源信息率函数是在保真度准则条件下信源信息率R可被压缩的可被压缩的最低限度,反映的是最低限度,反映的是信源信源本身的特性,与信道无关。同样地,本身的特性,与信道无关。同样地,由于平均互信息量与信道的特性有关,由于平均互信息量与信道的特性有关,本讲稿第二十一页,共八十一页为了排除信道特性对信息率失真函数的影响,采用的做法是在所为了排除信道特性对信息率失真函数的影响,采用的做法是在所有的信道中以那个能够使平均互信息量达到最小的有的信道中以那个能够使平均互信息量达到最小的信道为参考信道为参考,从而使信息率失真函数从而使信息率失真函数R(D)仅仅与信源特性有关。信源不同,仅仅与信源特性有关。信源不同,R(D)也不同。也不同。l 引入引入C是为了解决在所有是为了解决在所有信道信道中传送的最大信息量到底有中传送的最大信息量到底有多大的问题,它给出了信道可能传输的最大信息量,是无多大的问题,它给出了信道可能传输的最大信息量,是无差错传输的上限。它是为差错传输的上限。它是为信道编码信道编码服务,也是为了提高通信的服务,也是为了提高通信的可靠性可靠性服务。服务。l 引入引入R(D)是为了解决在允许失真度是为了解决在允许失真度D的条件下,的条件下,信源编码信源编码到到底能压缩到什么程度的问题,它给出了保真度准则条件下信底能压缩到什么程度的问题,它给出了保真度准则条件下信源信息率可被压缩的最低限度。可见引入它能够为源信息率可被压缩的最低限度。可见引入它能够为信源的压信源的压缩编码缩编码服务,或者是为了提高通信的服务,或者是为了提高通信的有效性有效性服务。服务。本讲稿第二十二页,共八十一页信息传输理论信息率失真理论附注信道p(y/x)失真函数d(ai,bj),信源p(x)固定信源p(x)信道p(y/x)(假想的)可变的错误概率Pe平均失真度信道容量率失真函数R 0。(2)R(D)R(0)H(X)对应于对应于无失真无失真(D=0)情况,相当于无噪声信道,)情况,相当于无噪声信道,此时信道传输此时信道传输的信息量等于信源熵。的信息量等于信源熵。1.Dmin和和R(Dmin)(1)由于由于D是非负实数是非负实数d(xi,yj)的数学期望,因此的数学期望,因此D也是非负的实数。也是非负的实数。而非负实数的下界是零,而非负实数的下界是零,所以所以D的下界是零。的下界是零。本讲稿第二十八页,共八十一页(3)一般情况下一般情况下选择试验信道,也就是选择转移概率选择试验信道,也就是选择转移概率,方法是:,方法是:对每一个对每一个xi,找出一个使,找出一个使d(ai,bj)最小的最小的yj,令,令p(bj/ai)=1,而其他的,而其他的转移概率为转移概率为0。这样可以得到。这样可以得到即在失真函数矩阵中寻找即在失真函数矩阵中寻找每行每行的最小值的最小值与与P(ai)相乘。相乘。本讲稿第二十九页,共八十一页【例【例4.1.4】删除信道删除信道X=0,1,Y=0,1,2,求求 Dmin。解:解:最小允许失真度为最小允许失真度为此时信道矩阵为此时信道矩阵为本讲稿第三十页,共八十一页【例【例4.1.5】设信源设信源 ,失真矩阵为,失真矩阵为 信宿信宿 Y0,1,求求 Dmin。此信道矩阵有无穷多个,且它们的最小此信道矩阵有无穷多个,且它们的最小平均失真度都是平均失真度都是1/6,即,即 PD 集合中的信道有无数多个。集合中的信道有无数多个。解:解:使平均失真度达到最小值(使平均失真度达到最小值(D=1/6)的信道必须满足)的信道必须满足信道矩阵为信道矩阵为本讲稿第三十一页,共八十一页R(D)=0意味着不需传输任何信息。显然意味着不需传输任何信息。显然D越大,直至无限大都能满越大,直至无限大都能满足这样的情况。这里选择所有满足足这样的情况。这里选择所有满足R(D)0中的所有平均失真度中的所有平均失真度D中的中的最小值,定义为最小值,定义为R(D)的上限的上限Dmax。R(D)的定义域为的定义域为D0,Dmax。R(D)允许存在失真时(信源可压缩编码时允许存在失真时(信源可压缩编码时),压缩越大,失真就越严重,传输的信,压缩越大,失真就越严重,传输的信息率就越小;当压缩至息率就越小;当压缩至0时,信息率达到时,信息率达到最小值最小值0,对应的平均失真度就达到最大,对应的平均失真度就达到最大值值Dmax,此即为,此即为R(D)函数定义域的上界函数定义域的上界值。值。2.Dmax和和R(Dmax)DDmaxR(D)0本讲稿第三十二页,共八十一页 3.如何计算如何计算Dmax?R(D)0就是就是I(X;Y)=0,这时试验信道的,这时试验信道的输入与输出是互相独立的输入与输出是互相独立的,所以条件概率所以条件概率p(bj/ai)与与ai无关无关,即即 P(bj/ai)=P(bj)这时平均失真度为这时平均失真度为令令 则则(4.1.26)本讲稿第三十三页,共八十一页式式(4.1.26)是用不同的概率分布是用不同的概率分布p(bj)对对Dj求数学期望,取数学期望当中最求数学期望,取数学期望当中最小的一个,作为小的一个,作为Dmax。实际上是用。实际上是用p(bj)对对Dj进行线性分配,使线性分进行线性分配,使线性分配的结果最小。配的结果最小。当当p(ai)和和d(ai,bj)已给定时,则可计算出已给定时,则可计算出Dj,Dj 随随j 的变化而变化。的变化而变化。p(bj)是任选的,只需满足非负性和归一性。若是任选的,只需满足非负性和归一性。若Ds是所有是所有Dj当中当中最小最小的的一个,可取一个,可取p(bs)=1,其他的,其他的p(bj)=0,此时,此时Dj的线性分配值(或数学的线性分配值(或数学期望)必然期望)必然最小最小,即有,即有则则Dmax由信源的概率分布和规定的失真函数所确定。由信源的概率分布和规定的失真函数所确定。和和(4.1.27)本讲稿第三十四页,共八十一页允许的失真为最大值允许的失真为最大值Dmax时是全失真,这时试验信道的噪声熵等于信宿时是全失真,这时试验信道的噪声熵等于信宿熵,有熵,有因此通过试验信道的平均互信息量为因此通过试验信道的平均互信息量为即无论信源输出什么,信宿端将会得到最大失真,这时信源即无论信源输出什么,信宿端将会得到最大失真,这时信源X的信息率失真函数为的信息率失真函数为本讲稿第三十五页,共八十一页【例例4.1.6】设输入输出符号为设输入输出符号为XY=0,1,输入概,输入概率分布率分布p(X)=1/3,2/3,失真矩阵为,失真矩阵为 求求Dmax。本讲稿第三十六页,共八十一页解法一解法一:由概率的完备性由概率的完备性 p(b1)+p(b2)=1,有,有当当p(b1)=0时(则时(则p(b2)=1),得),得此时输出符号概率:此时输出符号概率:p(b1)=0,p(b2)=1相应试验信道的信道矩阵相应试验信道的信道矩阵 p(X)=1/3,2/3本讲稿第三十七页,共八十一页解法二解法二:此时输出符号概率:此时输出符号概率:p(b1)=0,p(b2)=1因为因为相应试验信道的信道矩阵相应试验信道的信道矩阵 p(X)=1/3,2/3本讲稿第三十八页,共八十一页【例例4.1.7】设输入输出符号表为设输入输出符号表为XY=0,1,输入概,输入概率分布率分布p(X)=1/3,2/3,失真矩阵为,失真矩阵为试求试求Dmax。解解:相应试验信道的信道矩阵相应试验信道的信道矩阵 本讲稿第三十九页,共八十一页 定理定理4.1.1:R(D)在定义域内是下凸的。在定义域内是下凸的。若若R(D)在在D上是下凸函数,那么对任一上是下凸函数,那么对任一01和任意平和任意平均失真值均失真值D、DDmax,有,有二、二、R(D)函数的下凸性函数的下凸性本讲稿第四十页,共八十一页三、三、R(D)函数的单调递减性和连续性函数的单调递减性和连续性定理定理 4.1.2:R(D)在定义域内是单调递减的。在定义域内是单调递减的。定理定理4.1.3:R(D)在定义域内是连续的。在定义域内是连续的。R(D)H(Y)=R(0)Dmax DDmaxR(D)0本讲稿第四十一页,共八十一页总结:总结:(1)它们都有一最大失真值它们都有一最大失真值Dmax,对应,对应R(D)=0。当允许的平均失真。当允许的平均失真D大大于这最大值时,于这最大值时,R(D)当然也是零,也就是不用传送信息已能达到当然也是零,也就是不用传送信息已能达到要求。要求。(3)当当D=0,R(D)趋于无限,也就是说,对于信息量无限大的连续信源符趋于无限,也就是说,对于信息量无限大的连续信源符号,号,无法进行无损编码无法进行无损编码,除非信息率,除非信息率R趋向无限大。对于离散信源就不趋向无限大。对于离散信源就不同,当同,当D=0时,时,R(0)=H(X),这就是,这就是无损编码情况无损编码情况,此时所需的信息,此时所需的信息率率R不能小于信源熵不能小于信源熵H(X)。(2)当当DDmax时,时,R(D)不为零,随着不为零,随着D的增加的增加,R(D)单调地减少。单调地减少。本讲稿第四十二页,共八十一页 问题问题:假设已给定信源概率假设已给定信源概率p(ai)和失真函数和失真函数d(ai,bj),就可以确,就可以确定信源的定信源的R(D)。它是在约束条件下即保真度准则下求。它是在约束条件下即保真度准则下求I(X;Y)的极小值问题的极小值问题。应用。应用拉格朗日乘子法拉格朗日乘子法,原则上可以,原则上可以求出解来,但是如果要得到明显的解析表达式是比较困求出解来,但是如果要得到明显的解析表达式是比较困难的,通常只能用难的,通常只能用参量形式参量形式来表示,或采用来表示,或采用迭代算法迭代算法用计算用计算机求解信源的机求解信源的R(D)函数函数。4.2 离散信源离散信源R(D)的计算的计算本讲稿第四十三页,共八十一页一、计算条件一、计算条件要计算信源信息率失真函数要计算信源信息率失真函数R(D),即在,即在l已知信源的概率分布已知信源的概率分布l已知失真函数为已知失真函数为d(xi,yj),选取合适的试验信道,选取合适的试验信道p(bj/ai)条件下,计条件下,计算平均互信息的极小值。算平均互信息的极小值。平均互信息的表达式为平均互信息的表达式为并满足约束条件:并满足约束条件:其中其中 本讲稿第四十四页,共八十一页二、计算方法二、计算方法 (4.2.6)将将对对p(yj/xi)求偏导数,并令导数为零,即求偏导数,并令导数为零,即 (4.2.7)应用拉格朗日乘子法,引入拉格朗日乘数应用拉格朗日乘子法,引入拉格朗日乘数S和和 构造构造一个新的函数,可将求条件极值问题化为无条件极值问题。一个新的函数,可将求条件极值问题化为无条件极值问题。下面介绍用下面介绍用拉格朗日乘子法拉格朗日乘子法求解求解R(D)函数,并用参量函数,并用参量S来表示来表示.本讲稿第四十五页,共八十一页下面分别计算以上三部分的偏导数:下面分别计算以上三部分的偏导数:第一部分:第一部分:式中式中本讲稿第四十六页,共八十一页第二部分:第二部分:第三部分:第三部分:将这三部分偏导数结果代入到式(将这三部分偏导数结果代入到式(4.2.7)得)得(4.2.8)本讲稿第四十七页,共八十一页三、计算三、计算 p(bj)、i和和 p(bj/ai)式式(4.2.10)两边对两边对j求和得:求和得:(4.2.11a)解得解得(4.2.11b)利用关系利用关系上式两边同除以上式两边同除以p(ai),并令,并令 ,解得,解得mn个关于个关于p(bj/ai)的方程的方程(4.2.10)本讲稿第四十八页,共八十一页将式(将式(4.2.10)两边乘以)两边乘以p(ai)再对再对i求和有求和有将将i代入代入(4.2.12)式得到式得到m个关于个关于p(bj)的联立方程式的联立方程式 (4.2.13)(4.2.12)本讲稿第四十九页,共八十一页解之可得到以解之可得到以S为参量的为参量的m个的个的p(bj)值。将得到的值。将得到的p(bj)代入代入式式(4.2.11b),得到,得到m个个i值。再将值。再将m个个p(bj)和和m个个i值代入值代入(4.2.10),得到,得到mn个以个以S为参量的为参量的p(bj/ai)。四、计算信息率失真函数四、计算信息率失真函数R(D)因为平均失真度因为平均失真度将式将式(4.2.10)代入上式得代入上式得 (4.2.14)本讲稿第五十页,共八十一页这里这里p(yj)和和i均以均以S为参量,因此为参量,因此D也是以也是以S为参量为参量将式将式(4.2.10)代入上式,得到以代入上式,得到以S为参量为参量的信息率失真函数的表达式的信息率失真函数的表达式(4.2.15)本讲稿第五十一页,共八十一页 五、参量五、参量S的物理意义的物理意义 (4.2.16)除某些特定的情况外,参量除某些特定的情况外,参量S一般难以消除,因此很难得到一般难以消除,因此很难得到R(D)的显的显式表达式。现在通过计算式表达式。现在通过计算R(D)的微分,分析参量的微分,分析参量S的物理意义。的物理意义。根据式(根据式(4.2.15)的结论,)的结论,R(S)是是D(S)、S和和i的隐函数,因此利用的隐函数,因此利用全微分公式计算导数如下:全微分公式计算导数如下:本讲稿第五十二页,共八十一页将式(将式(4.2.12)对)对S求导得求导得 将式(将式(4.2.17)乘以)乘以p(yj),并对,并对 j 求和得求和得(4.2.17)本讲稿第五十三页,共八十一页对照式对照式(4.2.11b)和式和式(4.2.14)有有将上式的结果代入式(将上式的结果代入式(4.2.16)中得)中得(4.2.18)式式(4.2.18)表明,参量表明,参量S是信息率失真函数是信息率失真函数R(D)的斜率。由于的斜率。由于信息率失真函数信息率失真函数R(D)是是D的单调递减函数,且是的单调递减函数,且是U型下凸函数。型下凸函数。所以所以R(D)的斜率的斜率S0,且斜率,且斜率S 必然随着必然随着D的增加而增加的增加而增加 ,即,即 。1/iD(S)本讲稿第五十四页,共八十一页斜率斜率S与失真度与失真度D、信息率失真函数、信息率失真函数R(D)与与D的关系曲线见图的关系曲线见图4.2.1。当当D=Dmin=0时,由式时,由式(4.2.14)知,由于失真度知,由于失真度D是是mn项的和,其中项的和,其中d(ai,bj)、p(ai)、p(bj)和和i均为非负值,因此指数项的幂必为负无穷大,均为非负值,因此指数项的幂必为负无穷大,即即Smin。由于参量由于参量S是是D的递增函数,所以当的递增函数,所以当S由由Dmin=0逐渐增大时,逐渐增大时,S将随将随D的增大而逐渐增大。当允许失真度的增大而逐渐增大。当允许失真度D=Dmax时,参量时,参量S将达到最大值,将达到最大值,并且并且Smax0。当当DDmax时时 R(D)0。因此一般情况下,在。因此一般情况下,在D=Dmax处,参量处,参量S将从一将从一个很小的负值跳跃到零,个很小的负值跳跃到零,S在这一点不连续,而在开区间在这一点不连续,而在开区间(0,Dmax)内,内,S是失真度是失真度D的连续函数。的连续函数。本讲稿第五十五页,共八十一页由上可知,当规定了允许失真度由上可知,当规定了允许失真度D,又找到了适当的失真,又找到了适当的失真函数函数d(ai,bj),就可以找到在该失真条件下的最小信息,就可以找到在该失真条件下的最小信息率失真函数率失真函数R(D),这个最小信息率失真函数,这个最小信息率失真函数R(D)是一个是一个极限数值。用不同的方法进行数据压缩时(前提是都不极限数值。用不同的方法进行数据压缩时(前提是都不能超过失真度能超过失真度D),其压缩的程度如何,函数),其压缩的程度如何,函数R(D)是一是一把尺子。由它可知是否还有压缩的潜力,潜力有多大。因此把尺子。由它可知是否还有压缩的潜力,潜力有多大。因此近年来引起很多学者对它的兴趣。近年来引起很多学者对它的兴趣。本讲稿第五十六页,共八十一页例例4.2.1 设输入输出符号表为设输入输出符号表为XY=0,1,输入概率分布,输入概率分布P(x)P,1-p,0p,失真矩阵为,失真矩阵为 求信息率失真函数求信息率失真函数R(D)。六、六、R(D)参量计算举例参量计算举例本讲稿第五十七页,共八十一页解解:(1)求求 1 和和 2简记简记 按下式解方程按下式解方程(4.2.12)本讲稿第五十八页,共八十一页(2)求求p(yj)由此解得由此解得 解得解得(4.2.11)解方程解方程 本讲稿第五十九页,共八十一页(3)由下式求出转移概率分布由下式求出转移概率分布 P(b/ai)(4.2.10)本讲稿第六十页,共八十一页(4)求求 所以所以(4.1.7)本讲稿第六十一页,共八十一页(5)计算计算R(D),将上面各式代入,则有,将上面各式代入,则有 本讲稿第六十二页,共八十一页取取 作曲线有:作曲线有:本讲稿第六十三页,共八十一页结论:结论:1)信源概率分布越不均匀,压缩比越大;信源概率分布越不均匀,压缩比越大;2)D越大,压缩比也越大。越大,压缩比也越大。由图可见:由图可见:无失真:无失真:限失真时,比如限失真时,比如D=0.1时时结果得到如图结果得到如图4-2-2所示的曲线:所示的曲线:本讲稿第六十四页,共八十一页4.3.3 信息率失真函数与信息价值信息率失真函数与信息价值信息价值是比信息量更难定义的量,它与信息的接收有信息价值是比信息量更难定义的量,它与信息的接收有关。信息率失真理论不仅被应用于信息传输来解决信源关。信息率失真理论不仅被应用于信息传输来解决信源的压缩编码问题,也被应用于质量检测和科学管理中。的压缩编码问题,也被应用于质量检测和科学管理中。【例【例4.3-1】某印刷电路板加工厂的产品合格率约为某印刷电路板加工厂的产品合格率约为98%。一块好的一块好的PCB板出厂价约为板出厂价约为100元,但如果客户发现一块不元,但如果客户发现一块不合格的板子可向厂方索赔合格的板子可向厂方索赔10000元。已知厂方检验员检验的元。已知厂方检验员检验的正确率约为正确率约为95%,试用信息率失真理论来分析检验的作用,试用信息率失真理论来分析检验的作用并作比较。假设合格品出厂、废品报废都不造成损失。并作比较。假设合格品出厂、废品报废都不造成损失。本讲稿第六十五页,共八十一页选择失真函数为选择失真函数为 d(好,好)(好,好)=0 d(废,废)(废,废)=0 d(好,废)(好,废)=100 d(废,好)(废,好)=10000解:解:根据题意,可将根据题意,可将 PCB板作为一信源,且有板作为一信源,且有信源空间:信源空间:好(合格)好(合格)废(废品)废(废品)P(好)(好)=0.98 P(废)(废)=0.02l情况情况1 全部产品不经检验而出厂全部产品不经检验而出厂全部是合格品全部是合格品把这一过程看作是一个把这一过程看作是一个“信道信道”,其,其“传递概率传递概率”为为p(好(好/好)好)=1 p(废(废/好)好)=0 p(好(好/废)废)=1 p(废(废/废)废)=0可将产品检验分成可将产品检验分成4种情况:全部产品都当合格品,全部产品都当废品,种情况:全部产品都当合格品,全部产品都当废品,完美的检验和允许出错的检验。完美的检验和允许出错的检验。本讲稿第六十六页,共八十一页信道矩阵为信道矩阵为好好废废好好 废废这种情况的平均损失,即平均失真度为这种情况的平均损失,即平均失真度为这种情况每销售出去一块这种情况每销售出去一块PCB板,加工厂将要另外承担可板,加工厂将要另外承担可能损失能损失200元的风险,考虑到每块销售元的风险,考虑到每块销售100元,实际上每卖出元,实际上每卖出一块可能要实际损失一块可能要实际损失100元。元。本讲稿第六十七页,共八十一页l情况情况2 全部产品不经检验全部报废全部产品不经检验全部报废都当废品都当废品这时的信道传递概率为这时的信道传递概率为 p(好(好/好)好)=0 p(废(废/好)好)=1 p(好(好/废)废)=0 p(废(废/废)废)=1信道矩阵为信道矩阵为好好废废好好 废废这种情况的平均失真度为这种情况的平均失真度为本讲稿第六十八页,共八十一页比较比较1、2两种情况,做出全部报废决定造成的损失要小于做出全两种情况,做出全部报废决定造成的损失要小于做出全部出厂决定所造成的损失。不做任何检验,在全部出厂和全部报废部出厂决定所造成的损失。不做任何检验,在全部出厂和全部报废两者之间抉择,选择第两者之间抉择,选择第2种情况的损失反而小些。因此有种情况的损失反而小些。因此有即这种情况每销售出去一块即这种情况每销售出去一块PCB板,加工厂将有损失板,加工厂将有损失98元的风险。这元的风险。这是因为把是因为把98%本来可以卖本来可以卖100元一块的板子也报废的缘故。元一块的板子也报废的缘故。由于此时产品没有进行质量管理,相当于信源没有输出任何信息量。由于此时产品没有进行质量管理,相当于信源没有输出任何信息量。本讲稿第六十九页,共八十一页l情况情况3 经过检验能正确地判断合格品和废品经过检验能正确地判断合格品和废品完美检验完美检验这相当于无噪信道的情况,信道矩阵为这相当于无噪信道的情况,信道矩阵为好好废废好好 废废这种情况的平均失真度为这种情况的平均失真度为H(X)=R(0)=0.98log20.980.02log20.02=0.142(比特比特/块)块)即这种情况不会另外造成损失。即这种情况不会另外造成损失。下面探讨每一比特信息量的价值。为此先来求该信源的熵,有下面探讨每一比特信息量的价值。为此先来求该信源的熵,有因为可能造成的最大损失为因为可能造成的最大损失为98元元/块,所以说块,所以说0.142比特信息量的最大价值为比特信息量的最大价值为98元,则每一比特信息的最大价值为元,则每一比特信息的最大价值为98/0.142=690.14(元(元/比特)比特)该式说明,如果从每块该式说明,如果从每块PCB板上获取板上获取0.142比特的信息量,就可以避免一切比特的信息量,就可以避免一切细小的损失。细小的损失。本讲稿第七十页,共八十一页l情况情况4 检验时允许有一定的错误检验时允许有一定的错误非完美检验非完美检验这时的信道传递概率为这时的信道传递概率为 p(好(好/好)好)=0.95 p(废(废/好)好)=0.05 p(好(好/废)废)=0.05 p(废(废/废)废)=0.95信