信道率失真函数.ppt

1,4.1平均失真和信息率失真函数4.2离散信源和连续信源的R(D)计算,内容,2,重点与难点,重点：失真函数、平均失真、信息率失真函数R(D)、信息率失真函数的计算。难点：信息率失真函数R(D)、信息率失真函数的计算。,3,第2章所讲的信源熵，是针对不失真的情况。而在实际信息处理过程中，往往允许有一定的失真，例如连续信源发出的消息，由于其可能取值有无限多种，信源熵无穷大，要想传输这样的信息，必须经过A/D转换，这就引起量化失真。,引言,4,人们的视觉和听觉都允许有一定的失真，电影和电视就是利用了人的视觉残留，使人没有发觉影片是由一张张画面快速连接起来的。耳朵的频率响应也是有限的，在某些实际场合中只需保留信息的主要特征就够了。所以，一般可以对信源输出的信息进行失真处理，降低信息率，提高传输率。那么在允许一定程度的失真条件下，能够把信源信息压缩到什么程度，至少需要多少比特的信息率才能描述信源呢？本章主要讨论在一定程度的失真情况下所需的最少信息率，从分析失真函数、平均失真出发，求出信息率的失真函数。,5,4.1平均失真和信息率失真函数,6,在实际问题中，信号有一定的失真是可以容忍的。但是当失真大于某一限度后，信息质量将被严重损伤，甚至丧失其实用价值。要规定失真限度，必须先有一个定量的失真测度。为此引入失真函数。,7,4.1.1失真函数,假如某一信源X,输出样值xi,xia1,a2,an,经信道传输后变成yj,yjb1,b2,bm,如果:xiyj没有失真xiyj产生失真失真的大小,用一个量来表示,即失真函数d(xi,yj),以衡量用yj代替xi所引起的失真程度。失真函数定义为：,8,失真函数,将所有的d(xi,yj)排列起来,用矩阵表示为:,失真矩阵,例：设信源符号序列为X=0,1,编码器输出符号序列为Y=0,1,2,规定失真函数为d(0,0)d(1,1)=0d(0,1)d(1,0)=1d(0,2)d(1,2)=0.5,失真矩阵,m=n或mn,9,失真函数,注意：失真函数d(xi,yj)的数值是依据实际情况，用yj代替xi所导致的失真大小是人为决定的。比如上例中，用y=2代替x=0和x=1所导致的失真程度相同，用0.5表示；而用y=0代替x=1所导致的失真程度要大，用1表示。,10,失真函数形式可以根据需要任意选取,最常用的有:,均方失真:,绝对失真:,相对失真:,误码失真:,适于连续信源,适于离散信源,失真函数,11,失真函数,均方失真和绝对失真只与xi-yj有关，而不是分别与xi和yj有关，在数学上处理比较方便；相对失真与主观特性比较匹配，因为主观感觉往往与客观量的对数成正比，但在数学处理中就要困难得多。实际选择一个合适的、完全与主观特性匹配的失真函数是非常困难的，更不用说还要易于数学处理。当然不同的信源应有较好的失真函数，所以在实际问题中还可提出许多其他形式的失真函数。,12,失真函数,汉明失真矩阵,对于二元对称信源(m=n),X=0,1,Y=0,1,汉明失真矩阵:,13,序列编码情况的失真函数,14,补充知识数学期望,15,补充知识数学期望,16,4.1.2平均失真,xi和yj都是随机变量,所以失真函数d(xi,yj)也是随机变量,限失真时的失真值只能用数学期望表示将失真函数的数学期望称为平均失真：,平均失真对给定信源分布p(ai)经过某一种转移概率分布为p(bj|ai)的有失真信源编码器后产生失真的总体量度。,17,失真函数d(xi,yj)：描述了某个信源符号通过传输后失真的大小平均失真：描述某个信源在某一试验信道传输下的失真大小,它对信源和信道进行了统计平均,是从总体上描述整个系统的失真。,4.1.2平均失真,转移概率分布为p(yj|xi)的信源编码器,18,L长序列编码情况的平均失真,如果假定离散信源输出符号序列XX1X2XlXL,其中L长符号序列xi=xi1xi2xiL,经信源编码后,输出符号序列Y=Y1Y2YlYL,其中L长符号序列yj=yj1yj2yjL,则失真函数定义为,平均失真,19,4.1.3信息率失真函数R(D),如图所示，信源X经过有失真的信源编码器输出Y，将这样的编码器看作存在干扰的假想信道，Y当作接收端的符号。这样就可用分析信道传输的方法来研究限失真信源问题。,将信源编码器看作信道,20,4.1.3信息率失真函数R(D),信源编码器的目的是使编码后所需的信息传输率R尽量小，然而R越小，引起的平均失真就越大。给出一个失真的限制值D，在满足平均失真的条件下，选择一种编码方法使信息率R尽可能小。信息率R就是所需输出的有关信源X的信息量。将此问题对应到信道，即为接收端Y需要获得的有关X的信息量，也就是互信息I(X;Y)。这样，选择信源编码方法的问题就变成了选择假想信道的问题，符号转移概率p(yj|xi)对应信道转移概率。,21,4.1.3信息率失真函数R(D),无论是无噪信道还是有噪信道:RC总能找到一种编码使在信道上能以任意小的错误概率,以任意接近C的传输率来传送信息RC就必须对信源压缩,使其压缩后信息传输率R小于信道容量C,但同时要保证压缩所引入的失真不超过预先规定的限度。信息压缩问题就是对于给定的信源,在满足平均失真的前提下,使信息率尽可能小。,22,信息率失真函数R(D),若平均失真度不大于我们所允许的失真,即,则称此为保真度准则,当信源p(xi)给定,单个符号失真度d(xi,yj)给定时,选择不同的试验信道p(yj|xi),相当于不同的编码方法,其所得的平均失真度不同。试验信道,23,信息率失真函数R(D),满足条件的所有转移概率分布pij,构成了一个信道集合,D失真允许的试验信道：满足保真度准则的试验信道。PD：所有D失真允许的试验信道组成的一个集合。,24,信息率失真函数R(D),由于互信息取决于信源分布和信道转移概率分布，根据2.2节所述，当p(xi)一定时,互信息I是关于p(yj|xi)的U型函数,存在极小值。因而在上述允许信道PD中可以寻找一种信道pij，使给定的信源p(xi)经过此信道传输后，互信息I(X;Y)达到最小。该最小的互信息就称为信息率失真函数R(D)，即,25,信息率失真函数R(D),R(D)：在限定失真为D的条件下信源输出的最小信息速率。,在信源给定后,我们希望在满足一定失真的情况下,使信源必须传输给收信者的信息传输率R尽可能地小。若从接收端来看,就是在满足保真度准则下,寻找再现信源消息所必须获得的最低平均信息量。即在满足保真度准则的条件下寻找平均互信息I(X;Y)的最小值。,26,信息率失真函数,PD是所有满足保真度准则的试验信道集合,因而可以在集合PD中寻找某一个信道pij,使I(X;Y)取极小值。离散无记忆信源,27,由互信息的关系式I(X;Y)=H(Y)-H(Y|X)=H(X)-H(X|Y)可理解为互信息是信源发出的信息量H(X)与噪声干扰条件下消失的信息量H(Y|X)之差。应当注意，这里讨论的是有关信源的问题，一般不考虑噪声的影响。信息在存储和传输时需要去掉冗余，或者从某些需要出发认为可将一些次要成分去掉，也就是说，对信源的原始信息在允许的失真限度内可以进行压缩。由于这种压缩损失了一定的信息，造成一定的失真，把这种失真等效成由噪声而造成的信息损失，看成一个等效噪声信道(又称为试验信道)，因此信息率失真函数的物理意义是：对于给定信源，在平均失真不超过失真限度D的条件下，信息率允许压缩的最小值为R(D)。,信息率失真函数,28,例已知编码器输入的概率分布为p(x)=0.5,0.5信道矩阵,求互信息,29,编码器输入的概率分布为p(x)=0.5,0.5信道矩阵,求互信息,可见当p(x)一定时,I(X;Y)随p(yj|xi)而变。因为p(x)分布一定时,信道受干扰不同所能传递的信息量是不同的。当p(x)一定时,I(X;Y)是关于p(yj|xi)的下凸函数。因此当改变p(yj|xi)时,I(X;Y)有一极小值。,30,平均互信息,平均互信息I(X;Y)：p(yj|xi)一定，信源的概率分布p(xi)的上凸函数。p(xi)一定，信道传递概率p(yj|xi)的下凸函数。,信道容量：,信息率失真函数：,31,信道容量,信道容量：假定信道固定的前提下,选择一种试验信源使信息传输率最大。它所反映的是信道传输信息的能力,是信道可靠传送的最大信息传输率。一旦找到了信道容量,它就与信源不再有关,而是信道特性的参量,随信道特性的变化而变化不同的信道其信道容量不同。,32,信息率失真函数,信息率失真函数：假定信源给定的情况下,用户可以容忍的失真度内再现信源消息所必须获得的最小平均信息量。它反映的是信源可以压缩的程度,是在满足一定失真度要求下信源可压缩的最低值。率失真函数一旦找到,就与求极值过程中选择的试验信道不再有关,而只是信源特性的参量。不同的信源其R(D)不同。,33,信道容量与信息率失真函数,研究信道容量：充分利用已给信道,使传输的信息量最大,而发生错误的概率任意小,为提高通信的可靠性服务。研究信息率失真函数：解决在已知信源和允许失真度D的条件下,使信源必须传送给信宿的信息率最小。即用尽可能少的码符号尽快地传送尽可能多的信源消息,以提高通信的有效性。,34,例4-2：设信源的符号表为A=al,a2,a2n,概率分布为p(ai)=1/2n,i=1,22n,失真函数规定为,信源熵,即不发生差错时失真为0,出错失真为1。试研究在一定编码条件下信息压缩的程度。,35,例4-2：,图4-3等效试验信道,如果对信源进行不失真编码,平均每个符号至少需要log2n个二进制码元。现在假定允许有一定失真,假设失真限度为D=1/2，设想采用下面的编码方案：a1a1，a2a2，ananan+1an,an+2an,a2nan,36,由该信道模型图4-3看出,它是一个确定信道(每个输入都对应一个输出)，pij=1(或0)，噪声熵H(Y|X)=0，无噪有损信道。,平均失真,信道输出概率分布为,由于从an起，以后所有符号都编成an，所以概率分布为,37,则输出熵H(Y),压缩,n-1个,1个,38,由以上结果可知，经压缩编码以后，信源需要传输的信息率由原来的log2n，压缩到log2n-(n+1)/2n)log(n+1)。也就是说，信息率压缩了(n+1)/2n)log(n+1)。这是采用上述压缩编码方法的结果，所付出的代价是容忍了1/2的平均失真。如果选取对压缩更为有利的编码方案，则压缩的效果可能更好。但一旦达到最小互信息这个极限值，就是R(D)的数值(此处D=1/2)，或超过这个极限值，那么失真就要超过失真限度。如果需要压缩的信息率更大，则可容忍的平均失真就要更大。,39,4.1.4信息率失真函数的性质,1、R(D)的定义域率失真的定义域问题就是在信源和失真函数已知的情况下,讨论允许平均失真度D的最小和最大取值问题。由于平均失真度是非负实数d(xi,yj)的数学期望,因此也是非负的实数,即的下界是0。,允许平均失真度能否达到其下限值0,与单个符号的失真函数有关。,40,R(D)的定义域,（1）Dmin和R(Dmin)信源的最小平均失真度：,只有当失真矩阵的每一行至少有一个0元素时,信源的平均失真度才能达到下限值0。当Dmin=0,即信源不允许任何失真时,信息率至少应等于信源输出的平均信息量信息熵。即R(Dmin)=R(0)=H(X),遍历j,p(yj|xi)=1(或0)无失真,41,R(D)的定义域,因为实际信道总是有干扰的,其容量有限,要无失真地传送连续信息是不可能的。当允许有一定失真时,R(D)将为有限值,传送才是可能的。,对于连续信源，由于其信源只有相对意义，而真正的熵为，当Dmin=0时相当于严格无噪声信道，通过无噪声信道的熵是不变的，所以,42,R(D)的定义域,（2）Dmax和R(Dmax)由于I(X;Y)是非负函数，而R(D)是在约束条件下的I(X;Y)的最小值，所以R(D)是也是一个非负函数，它的下限值是零。当R(D)为0，意味着不需要传输任何信息。显然D越大，直至无限大都能满足这样的情况，这里选择所有满足R(D)=0中D的最小值，定义为R(D)定义域的上限Dmax，即因此可以得到R(D)的定义域为。,43,R(D)的定义域,R(D)的定义域为Dmin，Dmax。通常Dmin=0，R(Dmin)=H(X)当DDmax时,R(D)=0不需传输任何信息当0DDmax时,0R(D)H(X)由此，得到R(D)的定义域为0，Dmax,44,R(D)的定义域,Dmax：定义域的上限。Dmax是满足R(D)=0时所有的平均失真度中的最小值。,由于I(X;Y)是非负函数,而R(D)是在约束条件下的I(X;Y)的最小值,所以R(D)也是一个非负函数,它的下限值是零。R(D)0,45,R(D)的定义域,R(D)=0，就是I(X;Y)=0，其充要条件是X与Y统计独立,即：,这时平均失真为,现在需要求出满足条件的D的最小值，即,46,R(D)的定义域,分析上式可知，在j=1,m中，可以找到值最小的j，当该j对应的pj=1，而其余pj为零时，上式右边达到最小，这时上式可化简成,47,例4-3:设输入输出符号表示为X=Y=0,1,输入概率分布p(x)=1/3,2/3,失真矩阵,求：Dmin、R(Dmin)和Dmax、R(Dmax)，以及两种情况下对应的转移概率。,失真矩阵的每一行至少有一个0元素时,Dmin=0此时，R(Dmin)=H(X)=H(1/3,2/3)=0.91bit/符号，这时信源编码器无失真，a1b1，a2b2，所以这时的编码器的转移概率为,48,此时输出符号概率p(b1)=0，p(b2)=1，a1b2，a2b2，所以这时的编码器的转移概率为,当R(Dmax)=0时，由书中式(4-1-13)得,49,例4-4:设输入输出符号表示为X=Y=0,1,输入概率分布p(x)=1/3,2/3,失真矩阵,求：Dmin和Dmax,失真矩阵的行元素无0，故平均失真度达不到下限值0,50,信息率失真函数的性质,1、R(D)是非负的实数,R(D)0。其定义域为0Dmax,其值为0H(X)。当DDmax时,R(D)02、R(D)是关于D的下凸函数也是关于D的连续函数。3、R(D)的单调递减性及连续性容许的失真度越大，所要求的信息率越小。反之亦然。,51,信息率失真函数的性质,信息率失真曲线,52,4.2离散信源和连续信源R(D)计算,给定信源概率pi和失真函数dij,就可以求得该信源的R(D)函数。它是在保真度准则下求极小值的问题。但要得到它的显式表达式,一般比较困难通常用参量表达式。即使如此,除简单的情况外实际计算还是困难的,只能用迭代逐级逼近的方法。,53,某些特殊情况下R(D),连续信源,离散信源,54,某些特殊情况下R(D),这些R(D)可画成如右图所示的3条曲线。他们都有一最大失真值Dmax，对应R(D)=0。当允许的平均失真D大于最大值时，R(D)当然也是零，也就是不用传