资源描述
第4章信息率失真函数本章主要讨论在信源允许一定失真情况下所需的最少信息率，从分析失真函数、平均失真出发，求出信息率失真函数R（D）。n4.1平均失真和信息率失真函数n4.2离散信源和连续信源的R（D）计算1第4章信息率失真函数1(1)“消息完全无失真传送消息完全无失真传送”的可实现性的可实现性n信道编码定理信道编码定理：无论何种信道，只要信息率无论何种信道，只要信息率R小于信小于信道容量道容量C，总能找到一种编码，使在信道上能以任意小，总能找到一种编码，使在信道上能以任意小的错误概率和任意接近于的错误概率和任意接近于C的传输率来传送信息。反之，的传输率来传送信息。反之，若若RC，则传输总要失真。，则传输总要失真。n完全无失真传送不可实现：完全无失真传送不可实现：q实际的信源常常是连续的，信息率无限大，要无失实际的信源常常是连续的，信息率无限大，要无失真传送要求信息率真传送要求信息率R为无穷大；为无穷大；q实际信道带宽是有限的，所以信道容量受限制。要实际信道带宽是有限的，所以信道容量受限制。要想无失真传输，所需的信息率大大超过信道容量想无失真传输，所需的信息率大大超过信道容量RC。4.1.1引引言言4.1基本概念有失真信源编码的意义有失真信源编码的意义2(1)“消息完全无失真传送”的可实现性4.1.1引(2)实际中允许一定程度的失真实际中允许一定程度的失真n技术发展的需要技术发展的需要q随着科学技术的发展，数字系统应用得越来越广泛，随着科学技术的发展，数字系统应用得越来越广泛，这就需要传送、存储和处理大量的数据。为了提高传这就需要传送、存储和处理大量的数据。为了提高传输和处理效率，往往需要对数据压缩，这样也会带来输和处理效率，往往需要对数据压缩，这样也会带来一定的信息损失。一定的信息损失。q人类社会已进入信息时代，信息爆炸的结果要求人们人类社会已进入信息时代，信息爆炸的结果要求人们解决如何对浩如烟海的数据有效的压缩，减少数据的解决如何对浩如烟海的数据有效的压缩，减少数据的存储容量存储容量(如各种数据库、电子出版物、多媒体娱乐如各种数据库、电子出版物、多媒体娱乐)、传输时间传输时间(如数据通信和遥测如数据通信和遥测)、或、或占有带宽占有带宽(如多如多媒体通信、数字音频广播、高清晰度电视媒体通信、数字音频广播、高清晰度电视)，要想方，要想方设法压缩给定消息设法压缩给定消息集合占用的空间域、时间域和频率集合占用的空间域、时间域和频率域资源。域资源。4.1.1引引言言4.1基本概念3(2)实际中允许一定程度的失真4.1.1引言4.n实际生活中的需要实际生活中的需要q实际生活中，人们一般并不要求获得完全无失真的消息，实际生活中，人们一般并不要求获得完全无失真的消息，通常只要求近似地再现原始消息，即允许一定的失真存通常只要求近似地再现原始消息，即允许一定的失真存在。在。q例如打电话：即使语音信号有一些失真，接电话的人也例如打电话：即使语音信号有一些失真，接电话的人也能听懂。人耳接收信号的带宽和分辨率是有限的。能听懂。人耳接收信号的带宽和分辨率是有限的。q放电影：理论上需要无穷多幅静态画面，由于人眼的放电影：理论上需要无穷多幅静态画面，由于人眼的“视觉暂留性视觉暂留性”，实际上只要每秒放映，实际上只要每秒放映24幅静态画面。幅静态画面。q有些失真没有必要完全消除。有些失真没有必要完全消除。4.1.1引引言言4.1基本概念4实际生活中的需要4.1.1引言4.1基本概念4n限失真编码：信源编码经过译码后能保留应用要求的信息，允许信源有一定的失真。n那么在允许一定程度失真的条件下，能够把信那么在允许一定程度失真的条件下，能够把信源信息压缩到什么程度，也就是，允许一定程源信息压缩到什么程度，也就是，允许一定程度失真的条件下，如何能快速的传输信息，这度失真的条件下，如何能快速的传输信息，这就是本章所要讨论的问题。就是本章所要讨论的问题。5限失真编码：信源编码经过译码后能保留应用要求的信息，允许信源4.1平均失真和信息率失真函数n4.1.1失真函数n4.1.2平均失真n4.1.3信息率失真函数R(D)n4.1.4信息率失真函数的性质64.1平均失真和信息率失真函数4.1.1失真函数64.1平均失真和信息率失真函数 在实际问题中，信号有一定的失真是可以容忍的。但在实际问题中，信号有一定的失真是可以容忍的。但是当失真大于某一限度后，信息质量将被严重损伤，是当失真大于某一限度后，信息质量将被严重损伤，甚至丧失其实用价值。要规定失真限度，必须先有一甚至丧失其实用价值。要规定失真限度，必须先有一个定量的失真测度。为此可引入失真函数。个定量的失真测度。为此可引入失真函数。74.1平均失真和信息率失真函数7 1、失真函数信源信源编码信道编码信道信道译码信源译码信宿干扰 根据信道编码定理，我们可以把信道编码、信道和信道解码等价成是一个没有任何干扰的广义信道，这样收信者收到消息后，所产生的失真只是由信源编码带来的。我们也可以把信源编码和信源译码等价成一个信道。4.1.1失真函数81、失真函数信源信源编码信道编码信道信道译码信源译我们称此信道为我们称此信道为试验信道试验信道。现在我们要研究在给定允许失真的条件下，是否可以设现在我们要研究在给定允许失真的条件下，是否可以设计一种信源编码使信息传输率为最低。为此，我们首先计一种信源编码使信息传输率为最低。为此，我们首先讨论失真的测度。讨论失真的测度。4.1.1失真函数9我们称此信道为试验信道。现在我们要研究在给定允许失真的条件下失真函数定义信源经过信源编码后输出对于每一对(xi,yj),指定一个非负函数d(xi,yj)0i=1,2,n j=1,2,m 称 d(xi,yj)为单个符号的失真函数.表示信源发出符号xi ,接收端再现yj所引起的误差或失真.d越小表示失真越小：d(xi,yj)=0无失真,d(xi,yj)0有失真.10失真函数定义10常用的失真函数 1平方误差失真函数d(xi,yj)=(xi-yj)22绝对误差失真函数d(xi,yj)=|xi-yj|3相对误差失真函数d(xi,yj)=|xi-yj|/|xi|4误码失真函数失真函数1,2,3用于连续信源,失真函数4用于离散信源,失真函数4也称Hanmming失真函数失真矩阵d n m 矩阵11常用的失真函数11例例1：失真矩阵为：这种失真成为汉明失真在二元情况下：12例1：失真矩阵为：这种失真成为汉明失真在二元情况下：12例例2：删除信源：删除信源对于二元删除信源n=2,m=313例2：删除信源对于二元删除信源n=2,m=313失真函数的定义可以推广到序列编码情况，如果假定离散信源输出符号序列X=(X1X2XlXL)，其中L长符号序列样值xi(xi1xi2xilxiL)，经信源编码后，输出符号序列Y=(Y 1Y 2Y lY L)，其中L长符号序列样值yj(yj1yj2yjlyjL)，则失真函数定义为：其中其中d(xil，yjl)是信源输出是信源输出L长符号样值长符号样值xi中的第中的第l个符号个符号xil时，编时，编码输出码输出L长符号样值长符号样值yj中的第中的第l个符号个符号yjl的失真函数。的失真函数。14失真函数的定义可以推广到序列编码情况，如果假定离散信源输出4.1.2 平均失真平均失真由于xi和yj都是随机变量，所以失真函数d(xi，yj)也是随机变量，限失真时的失真值，只能用它的数学期望或统计平均值，因此将失真函数的数学期望称为平均失真平均失真，记为信源编码器信源编码器154.1.2平均失真由于xi和yj都是随机变量，所以失真对于连续随机变量同样可以定义平均失真对于对于L长序列编码情况，平均失真为长序列编码情况，平均失真为16对于连续随机变量同样可以定义平均失真对于L长序列编码情况受信道容量的限制,实际应用中必须对信源进行压缩,应 1使其压缩后的信息传输率小于信道容量;2保证压缩所引入的平均失真不超过预先给定的允许失真度D;3在满足D的前提下,使编码后的信息率尽可能小.不等式D 称为保真度准则17受信道容量的限制,实际应用中必须对信源进行压缩,应14.1.3信息率失真函数R(D)信源编码器信源编码器XY假想信道假想信道将信源编码器看作信道将信源编码器看作信道184.1.3信息率失真函数R(D)信源编码器XY假想信道4.1.3信息率失真函数R(D)给出一个失真的限制值D，在满足平均失真 D的条件下，选择一种编码方法使信息率R尽可能小。信息率R就是所需输出的有关信源X的信息量。194.1.3信息率失真函数R(D)给出一个失真的限制值D，试验信道 1有失真的信源编码器视作有干扰的信道(假想信道)2当信源已知(即P(X)已知)时,单个符号的失真度给定,选择一类假想信道,使得D,这类假想信道称为D 失真允许信道,或D 失真允许试验信道.记为PD=p(yi|xj):D;i=1,2,n;j=1,2,m p(yi|xj)为信道的传递概率。凡满足保真度准则的这些试验信道称为D失真许可的试验信道。把所有D失真许可的试验信道组成一个集合PD。（1）D允许试验信道20试验信道（1）D允许试验信道20（2）信息率失真函数R(D)由于互信息取决于信源分布和信道转移概率分布，当p(xi)一定时，互信息I是关于p(yj/xi)的U型凸函数，存在极小值。因而在上述允许信道PD中，可以寻找一种信道pij，使给定的信源p(xi)经过此信道传输后，互信息I(X；Y)达到最小。该最小的互信息就称为信息率失真函数R(D)，即21（2）信息率失真函数R(D)由于互信息取决于信源分布和信道对于离散无记忆信源，R(D)函数可写成 p(ai)，i1，2，n是信源符号概率分布；p(bj/ai)，i1，2，n，j1，2，m是转移概率分布 p(bj)，j1，2，m是接收端收到符号概率分布。22对于离散无记忆信源，R(D)函数可写成p(ai)，i1例4-1-3设信源的符号表为Aa1，a2，a2n，概率分布为p(ai)1/2n，i1，2，2n，失真函数规定为即符号不发生差错时失真为0，一旦出错，失真为1，试研究在一定编码条件下信息压缩的程度。23例4-1-3234.1.4信息率失真函数的性质1.R(D)函数的定义域2.Dmin和R(Dmin)3.Dmin04.对于连续信源 5.244.1.4信息率失真函数的性质R(D)函数的定义域(2)Dmax和R(Dmax)选择所有满足选择所有满足R(D)0中中D的最小值，定义为的最小值，定义为R(D)定义域定义域的上限的上限Dmax，即，即因此可以得到因此可以得到R(D)的定义域为的定义域为25(2)Dmax和R(Dmax)选择所有满足R(D)Dmax是这样来计算的。R(D)0就是I(X;Y)0，这时试验信道输入与输出是互相独立的，所以条件概率p(yj/xi)与xi无关。即26Dmax是这样来计算的。R(D)0就是I(X;Y)0，这求出满足条件的D中的最小值，即，即此时平均失真为此时平均失真为27求出满足条件的D中的最小值从从上上式式观观察察可可得得：在在j=1，m中中，可可找找到到值值最最小小的的j，当当该该j对对应应的的pj1，而而其其余余pj为为零零时时，上上式式右右边边达达到到最最小小，这这时时上式可简化成上式可简化成28从上式观察可得：在j=1，m中，可找到 （4.3）且且 （4.4）（4.5）证：证：1）定义域下界：定义域下界：对对x的每一取值的每一取值 ，令对应最小的，令对应最小的 条件概率条件概率p(bj|ai)为为1,其余条件概率为零，就得到其余条件概率为零，就得到Dmin。1R(D)的定义域为的定义域为291R(D)的定义域为29 2）定义域上界：定义域上界：R(D)为平均互信息，所以为平均互信息，所以R(D)0。在较大范围内。在较大范围内 求极小值一定不大于在所含小范围内求的极小值，所求极小值一定不大于在所含小范围内求的极小值，所 以以D1D2=R(D1)R(D2)，即，即R(D)是是D的非增函数。的非增函数。当当XY独立时，独立时，R(D)I(X;Y)=0，当，当D继续增加，继续增加，R(D)仍然为仍然为0。所以，。所以，Dmax是使是使R(D)=0的最小平均失真。当的最小平均失真。当 x,y独立时，独立时，p(x,y)=p(x)p(y)，有，有 由于由于 已给定，而且对不同已给定，而且对不同y，也可能有不同的值。所以，求也可能有不同的值。所以，求 ，并使对，并使对应的应的p(y)=1，其余为，其余为0。这样就可使平均失真最小。所。这样就可使平均失真最小。所以得到（以得到（4.5）式。）式。证毕。证毕。302）定义域上界：30例4.3 设设试试验验信信道道输输入入符符号号 ，概概率率分分别别为为1/3，1/3，1/3，失失真真矩矩阵阵如如下下所所示示，求求Dmin和和Dmax和相应的试验信道的转移和相应的试验信道的转移概率矩阵。概率矩阵。解解 =1令对应最小令对应最小 的的 ,其其它它为为0。可得对应。可得对应Dmin 的转移概率矩阵为：的转移概率矩阵为：31例4.3设试验信道输入符号 =5/3上上式中第式中第2项最小，所以令项最小，所以令 ，。可得对应。可得对应Dmax 的转移概率矩阵为：的转移概率矩阵为：3232例4-1-4设输入输出符号表为XY0，1，输入概率分布p(x)=1/3，2/3，失真矩阵为33例4-1-4设输入输出符号表为XY0，1，输入概解：解：当当Dmin0时时，R(Dmin)H(X)H(1/3，2/3)0.91比比特特/符符号号，这这时时信信源源编编码码器器无无失失真真，所所以以该该编编码码器的转移概率为器的转移概率为 34解：34当当R(Dmax)0时时 此此时时输输出出符符号号概概率率p(b1)0，p(b2)1，所以这时的编码器的转移概率为所以这时的编码器的转移概率为 35当R(Dmax)0时此时输出符号概率p(b1)0，p(2R(D)是关于是关于D的下凸函数的下凸函数 设设D1,D2为任意两个平均失真，为任意两个平均失真，那么，那么 （4.6）证证 当信源分布给定后，当信源分布给定后，可以看成试验信道转移概率可以看成试验信道转移概率 的函数，的函数，即即 ，且有，且有 362R(D)是关于D的下凸函数36令令 ，那么，那么 ，=证毕。证毕。37令，n3、R(D)函数的单调递减性函数的单调递减性n 容许的失真度越大，所要求的信息率越小。容许的失真度越大，所要求的信息率越小。反之亦然。反之亦然。383、R(D)函数的单调递减性38综上所述，可以得出如下结论：综上所述，可以得出如下结论：R(D)是是非非负负的的实实数数，即即R(D)0。其其定定义义域域为为0Dmax，其其 值值 为为 0 H(X)。当当 DDmax时时，R(D)0。R(D)是是关关于于D的的下下凸凸函函数数，因因而而也也是是关关于于D的的连连续续函数。函数。R(D)是关于是关于D的严格递减函数。的严格递减函数。39综上所述，可以得出如下结论：39由以上三点结论，对一般R(D)曲线的形态可以画出来 R(D)H(X)R(D)0DDmaxDR(D)0DmaxD 信息率失真曲线信息率失真曲线40由以上三点结论，对一般R(D)曲线的形态可以画出来R(D)由以上分析可见，当规定了允许的失真D，又找到了适当的失真函数di j，就可以找到该失真条件下的最小信息率R(D)，这个最小信息率是一个极限值。在满足保真度准则的前提下，用不同方法进行数据压缩时，R(D)函数就是压缩程度的衡量，由R(D)可知是否还有压缩的潜力，潜力有多大，因此对它的研究很有实际意义。41由以上分析可见，当规定了允许的失真D，又找到了适当的失真函数例：二元信源和离散对称信源的R(D)函数1、二元对称信源的二元对称信源的R(D)函数函数 设二元信源设二元信源U=0,1，其分布概率，其分布概率 ，而接收变量而接收变量v=0,1，设汉明失真矩阵为，设汉明失真矩阵为：因而最小失真度因而最小失真度 。并能找到满足该最小失真的试。并能找到满足该最小失真的试验信道，且是一个无噪无损信道，其信道矩阵为：验信道，且是一个无噪无损信道，其信道矩阵为：42例：二元信源和离散对称信源的R(D)函数1、二元对称信源的R 要达到最大允许失真，唯一确定要达到最大允许失真，唯一确定 此时，可计算得信息传输率此时，可计算得信息传输率 一般情况下，当一般情况下，当 时，时，43要达到最大允许失真，唯一确定此时，可计算得信息传输可以计算得：二元信源得信息率失真函数为可以计算得：二元信源得信息率失真函数为例：例：在汉明失真条件下，在汉明失真条件下，44可以计算得：二元信源得信息率失真函数为例：在汉明失真条件下，对于离散对称信源，在汉明失真条件下：对于离散对称信源，在汉明失真条件下：45对于离散对称信源，在汉明失真条件下：45R(D)与与C的比较的比较信道容量定义为。它表示信道的最大传信道容量定义为。它表示信道的最大传输能力，反映的是信道本身的特性，应该与信源无关。输能力，反映的是信道本身的特性，应该与信源无关。但平均互信息量与信源的特性有关，为排除信源特性但平均互信息量与信源的特性有关，为排除信源特性对信道容量的影响，在所有的信源中以那个能够使平对信道容量的影响，在所有的信源中以那个能够使平均互信息量达到最大的信源为参考，从而使信道容量均互信息量达到最大的信源为参考，从而使信道容量仅与信道特性有关，信道不同，仅与信道特性有关，信道不同，C亦不同。亦不同。信息率失真函数。它也应该与信信息率失真函数。它也应该与信道无关。为此在所有信道中以能够使平均互信息量达道无关。为此在所有信道中以能够使平均互信息量达到最小的信道为参考，从而使信息率失真函数仅与信到最小的信道为参考，从而使信息率失真函数仅与信源特性有关，信源不同，源特性有关，信源不同，R(D)亦不同。亦不同。46R(D)与C的比较46引入引入C和和R(D)的目的的目的引入引入C,是为了解决在所用信道中传送的最大信息量到是为了解决在所用信道中传送的最大信息量到底有多大的问题，它给出了信道可能传输的最大信息底有多大的问题，它给出了信道可能传输的最大信息量，是无差错传输的上限。引入量，是无差错传输的上限。引入C能够为信道编码服务，能够为信道编码服务，或者说为提高通信的可靠性服务。或者说为提高通信的可靠性服务。引入引入R(D)，是为了解决在允许失真度，是为了解决在允许失真度D条件下，信源编条件下，信源编码到底能压缩到什么程度的问题，它给出了保真度条码到底能压缩到什么程度的问题，它给出了保真度条件下信源信息率可被压缩的最低限度，可见引入它能件下信源信息率可被压缩的最低限度，可见引入它能够为信源的压缩编码服务，或者说是为提高通信的有够为信源的压缩编码服务，或者说是为提高通信的有效性服务效性服务47引入C和R(D)的目的474.2离散信源和连续信源的R（D）计算某些特殊情况下R（D）的表示式为：（1）当d(x,y)=(x-y)2，时，484.2离散信源和连续信源的R（D）计算某些特(2)当d(x,y)=|x-y|，时，(3)当当d(x,y)=(x,y)，p(x=0)=p，p(x=1)=1-p时，时，R(D)=H(p)H(D)49(2)当d(x,y)=|x-y|，这些R（D）可画成图4-5的三条曲线0DmaxDR(D)H(3)(1)(2)图图4-5信息率失真函数信息率失真函数R(D)50这些R（D）可画成图4-5的三条曲线0信息率失真函数R(D)的计算已给定信源概率P(X)和失真函数d(xi,yj),求信息率失真函数R(D)的问题,可以归结为在约束条件保真度准则D 下,求极小值的问题.离散信源信息率失真函数的计算离散信源信息率失真函数的计算51信息率失真函数R(D)的计算离散信源信息率失真函数的计算51设试验信道的输入X，符号集A=a1,an，对应的概率分布为p1,pn；信道的输出Y，符号集B=b1,bm，对应的概率分布为q1,qm，失真矩阵为试验信道转移概率矩阵为 。并且，。52设试验信道的输入X，符号集A=a1,an，对应的概求解R(D)，实际上是求有约束极值 （4.2.1）由于，使R最小的pij总是在PD的边界上，所以在求极值时，平均失真约束条件的不等式取等号，即 （4.2.2）从（4.2.1）式可知，约束条件有n+1个，未知数pij有mn个。下面用拉格朗日乘子法求有约束极值。53求解R(D)，实际上是求有约束极值53设设s,i (i=1,n)为常数，求下式极值（以为常数，求下式极值（以e为底）：为底）：（）令令 ，得，得 （4.2.3）其中其中 ，54设s,i(i=1,n)为常数，求下式极值（所以所以 （4.2.4）当当 时，有时，有 （4.2.5）结合（结合（4.2.4）与（）与（4.2.5）式，得）式，得 ，j=1,m （4.2.6）（4.2.6）式含）式含m个方程，个方程，m个未知数个未知数qj(j=1,m)，而，而s为参为参量，一般能解。量，一般能解。55所以 将（将（4.2.3）代入（）代入（4.2.2）（）（4.2.1），分别得），分别得 （4.2.7）（4.2.8）56将（4.2.3）代入（4.2.2）（4.2.1），分别方程的解法现将现将R(D)R(D)求解的过程归纳如下求解的过程归纳如下：i）根据（根据（4.2.5）式求）式求 ，；ii）根据（根据（4.2.4）式求）式求 ，j=1,m；iii）根据（）根据（4.2.7）式求）式求D(s)；iv）根据（）根据（4.2.8）式求）式求R(s)。57方程的解法现将R(D)求解的过程归纳如下：57 设为矩阵，；，为列矢量。由（4.2.5）得写成矩阵形式为 （4.2.9）58设由（4.2.4），得写成矩阵形式为 （4.2.10）其中，。59由（4.2.4），得59当m=n且A-1存在时，求解过程为：由解得 ；由解得；设矩阵为，有 （4.2.11）（4.2.12）其中，H(p)为信源的熵。6060参量s的意义现求R(D)对D的导数，由（4.2.8）得 （4.2.13）在（4.2.5）式的两边，对s求导，得 两边都乘以，得 61参量s的意义现求R(D)对D的导数，由（4.2.8）得61根据（4.2.4），得 （4.2.14）将（4.2.14）结果代入（4.2.12），得 （4.2.15）结论：i）s是R(D)的斜率；ii）因为R(D)在0DDmax严格单调递减，所以s0。62根据（4.2.4），得例4.2.2 一个二进信源，符号集A=0,1，概率为p(0)=p1=p，p(1)=p2=1-p，其中p1/2；试验信道输出符号集B=0,1，失真函数为汉明失真，求R(D)函数。解i）求，ii）由，得，63例4.2.2一个二进信源，符号集A=0,1，概率为iii）iv）（4.2.16）（4.2.17）64iii）64由（4.2.16）得，和，将这些结果代入（4.2.17），得（4.2.18）65由（4.2.16）得，和0.10.20.30.40.5D1.00.80.60.40.20.0R(D)/bitp=0.5p=0.3p=0.2p=0.1图图46R(D)=H(p)H(D)，p为参数为参数660.1
展开阅读全文