信息率失真函数.ppt

《信息率失真函数.ppt》由会员分享，可在线阅读，更多相关《信息率失真函数.ppt（60页珍藏版）》请在三一办公上搜索。

1、第四章 信息率失真函数,目录,4.1 失真测度4.2 信息率失真函数及其性质4.3 离散无记忆信源的信息率失真函数4.4 连续无记忆信源的信息率失真函数4.5 保真度准则下的信源编码定理,无失真信源编码和有噪信道编码告诉我们：只要信道的信息传输速率小于信道容量，总能找到一种编码方法，使得在该信道上的信息传输的差错概率任意小；反之，若信道的信息传输速率大于信道容量，则不可能使信息传输差错概率任意小。但是，无失真的编码并非总是必要的。,香农首先定义了信息率失真函数R(D)，并论述了关于这个函数的基本定理。定理指出：在允许一定失真度D的情况下，信源输出的信息传输率可压缩到R(D)值，这从理论上给出信

2、息传输率与允许失真的关系，奠定了信息率失真理论基础。信息率失真理论是进行量化、数模转换、频带压缩和数据压缩的理论基础。,本章主要介绍信息率失真理论的基本内容，侧重讨论离散无记忆信源。首先给出信源的失真度和信息率失真函数的定义与性质；然后讨论离散信源和连续信源的信息率失真函数计算；在此基础上论述保真度准则下的信源编码定理。,41 失真测度,4.1.1 系统模型 信源发出的消息X通过有失真信源编码，再通过理想无噪信道传输，接收信息经信源译码后的输出为Y，由于信源编码是有失真的编码，则输出的Y不是X的精确重现。为定量描述信息传输速率与失真的关系，假定传输信道为理想无噪信道。,另外，可将信源编码引起的

3、失真视为由于信道不理想造成，即将有失真信源编码器和接收译码器之间过程看做有噪声的信道，这个假想的信道称为试验信道。则将有失真信源编码问题转化为无失真信源通过有噪信道传输的问题，进而通过研究试验信道输入输出间的互信息来研究限失真信源编码。,4.1.2 失真度和平均失真度从直观感觉可知，若允许失真越大，信息传输率可 越小；若允许失真越小，信息传输率需越大。所以信息传输率与信源编码所引起的失真(或误差)是有关的。,首先讨论失真的测度。试验信道的输入X，取值于符号集A=a1,a2,an，信道输出为Y，取值于符号集Bb1,b2,bm。对应于每一对(x,y)，定义非负函数：,称为单符号失真度（或失真函数）

4、。通常较小的d值代表较小的失真，而d(ai,bj)0表示没有失真。,若信源变量X有n个符号，接收变量Y有m个符号，则d(xi,yj)就有nm个，可排列成矩阵形式，即：,失真矩阵d,例1 离散对称信源(n=m)。信源变量Xa1,a2,an，接收变量Y b1,b2,bm。单符号失真度：,称为汉明失真。汉明失真矩阵是一方阵，对角线上的元素为零，即：,对二元对称信源(nm2)，信源X0,1，接收变量Y0,1。在汉明失真定义下，失真矩阵为：,例2 删除信源。信源变量Xa1,a2,an，接收变量Y b1,b2,bm(m=n+1)。定义其单符号失真度为：,其中接收符号bs作为一个删除符号。意味着若把信源符号

5、再现为删除符号vs时，其失真程度要比再现为其他接收符号的失真程度少一半。若二元删除信源n2,m3,X0,1,Y0,2,1,失真度为：,则,d(0,0)=d(1,1)=0 d(0,1)=d(1,0)=1d(0,2)=d(1,2)=1/2,例3 对称信源(n=m)。信源变量Xa1,a2,an，接收变量Y b1,b2,bm。失真度定义为：,若信源符号代表信号的幅度值，这就是以方差表示的失真度。表示幅度差值大要比差值小引起的失真更严重，严重程度用平方来表示，称为平方误差失真度。当 n3时，X0,1,2，Y0,1,2，则失真矩阵为：,上述三个例子说明了具体失真度的定义。一般情况下根据实际信源的失真，可以

6、定义不同的失真和误差的度量。另外还可以按其他标准，如引起的损失、风险、主观感觉上的差别大小等来定义失真度d(x,y)。,这里假设X是信源，Y是信宿，则X和Y间必有信道。实际这里X指的是原始的未失真信源，而Y是指失真以后的信源。则从X到Y之间实际上是失真算法，所以转移概率p(bj/ai)是指一种失真算法，有时又把p(bj/ai)称为试验信道的转移概率，如图所示。,平均失真度,信源X和信宿Y都是随机变量，故单符号失真度d(ai,bj)也是随机变量，设其概率为p(aibj)，规定单符号失真度d(ai,bj)后，传输一个符号引起平均失真，即单符号平均失真，信源平均失真度：,若平均失真度D不大于允许的失

7、真限定值D0，即：D D0，称为保真度准则。,信源固定(给定P(u)，单个符号失真度固定时(给定d(ai,bj)，选择不同试验信道，相当于不同的编码方法，所得的平均失真度是不同的。有些试验信道满足D D0，而有些不满足。凡满足保真度准则-平均失真度D D0的试验信通称为-D失真许可的试验信道。把所有D失真许可的试验信道组成一个集合，用符号PD表示，即：PD=P(y/x)：D D0,4.2 信息率失真函数及其性质,4.2.1 信息率失真函数的定义,信源给定，又定义了失真函数后，希望在满足一定失真情况下，使信源传输给收信者的信息传输率R尽可能小。即在满足保真度准则下，寻找信源必须传输给收信者的信息

8、率R下限值-与D有关。从接收端来看，就是在满足保真度准则下，寻找再现信源消息所必须获得的最低平均信息量。而接收端获得的平均信息量可用平均互信息I(X;Y)表示，就变成在满足保真度准则的条件下，寻找平均互信息I(X;Y)最小值。,当失真度d确定，信源X给定，平均失真度D是试验信道传递概率的函数，即D可表示为 D=fp(y|x)凡是满足保真度准则的信道，称为许可试验信道，所有许可试验信道的集合用PD表示，即：PD：P(y/x)；D D0,寻找平均互信息I(X;Y)的最小值,而PD是所有满足保真度准则的试验信道集合，可在D失真许可的试验信道集合PD中寻找信道P(bj/ai)，使I(X;Y)取极小值。

9、由于平均互信息I(X;Y)是P(bj/ai)的U型凸函数，所以在PD集合中，极小值存在。就是在D D0的条件下，信源必须传输的最小平均信息量。即：,R(D)-信息率失真函数或简称率失真函数。单位是奈特信源符号 或 比特信源符号,率失真函数给出了熵压缩编码可能达到的最小熵率与失真的关系，其逆函数D(R)称为失真率函数，表示一定信息速率下所可能达到的最小的平均失真。,4.2.2 信息率失真函数的性质,允许失真度D的下限可以是零，即不允许任何失真的情况。,1.R(D)的定义域,R(D)的定义域为 且：,解：,例 设试验信道输入符号集，各符号对应概率分别为1/3,1/3,1/3，失真矩阵如下所示，求

10、和 及相应的试验信道的转移概率矩阵。,令对应最小失真度 的，其它为“0”，可得对应 的试验信道转移概率矩阵为,上式中第二项最小，所以令，可得对应 的试验信道转移概率矩阵为,2、R(D)是关于平均失真度D的下凸函数,设 为任意两个平均失真，则有：,3、R(D)是 区间上的连续和严格单调递减函数。由信息率失真函数的下凸性可知，R(D)在 上连续。又由R(D)函数的非增性且不为常数知，R(D)是区间 上的严格单调递减函数。,信息率失真函数的一般形状,4.3 离散无记忆信源的信息率失真函数,已知信源的概率分布P(u)和失真函数d(u,v)，就可求得信源的R(D)函数。原则上与信道容量一样，即在有约束条

11、件下求极小值的问题。也就是适当选取试验信道P(v/u)使平均互信息最小化：,其约束条件为:,4.3.1 等概率、对称失真信源的率失真R(D)计算,对于等概、对称失真的信源，存在一个与失真矩阵具有同样对称性的转移概率分布达到率失真R(D)。,例5 有一个二元等概平稳无记忆信源，接收符号集为 且失真矩阵为：,求率失真函数R(D)。,解：由,由于信源等概分布，失真函数具有对称，因此，存在着与失真矩阵具有同样对称性的转移概率分布达到率失真R(D)，该转移概率矩阵可写为：,由于，因此对于任何有限平均失真，必须。于是转移概率矩阵变为：,对应此转移概率矩阵的平均失真：因此 可求出此时的互信息为：,相应的率失

12、真函数R(D)如图所示。,例：有一个n元等概率平稳无记忆信源，接收符号集为，且规定失真矩阵为求率失真函数R(D)。解：由于信源等概率分布，失真函数具有对称性，则存在着与失真矩阵具有同样对称性的转移概率分布达到率失真R(D)。该转移概率矩阵为,4.3.2 离散无记忆信源的信息率失真函数的参量表述,求信源的R(D)函数，原则上与求信道容量一样，是在有约束条件下求极小值的问题。也就是适当选取试验信道P(v/u)使平均互信息最小化，,应用拉格朗日乘子法，原则上可以求出解来。,但是，如果要求得到明显的解析表达式，则比较困难，通常只能用参量形式来表达。即便如此，除简单情况外，实际计算仍然是相当困难的。尤其

13、是约束条件式(7.32)，它是求解R(D)函数最主要的障碍。因为应用拉格朗日乘子法解得的一个或某几个P(vj/ui)很可能是负的。在这情况下，必须假设某些P(vj/ui)=0，然后重新计算，这就使得计算复杂化了。目前，可采用收敛的迭代算法在电子计算机上求解R(D)函数。下面介绍用拉格朗日乘子法求解R(D)函数，并用S作为参量来表述率失真函数R(D)和失真函数D(S)。,由式(1)知，当信源的概率分布P(u)固定，平均互信息仅仅是试验信道P(vj/ui)的函数。若先不考虑式(2)的约束，约束条件式(3)包含r个等式，取拉格朗日乘子 i(i12，r)分别与之对应；并取拉氏乘子S与式(4)对应。由此

14、构成辅助函数：,(1),求极值，就是求辅助函数一阶导数等于零的方程组的解。因为已知平均互信息I(U;V)是信道P的U型凸函数，所以若极值存在，它一定是极小值。即求：,该式共有r*s个方程，加上式(3)r 个方程和式(4)1 个方程，共有(r+1+r*s)个方程。而未知数i(i=1,2,r)、S和P(vj/ui)(i=1,2,r，j=1,2,s)也正好对应(r+1+r*s)个，所以原则上只需求解式(6)、(3)和(4)的方程组，即可求出I(U;V)在约束条件下的极小值。,注：这时所得的结果是以S为参量的表达式，而不是显式表达式，因而所得到的R(D)的表达式也是以S为参量的表达式。参量S对应的限制

15、条件为式(4)，它与允许的失真度D有关，所以以S为参量就相当于以D为参量。,例6 设离散信源,和接收变量：并设失真矩阵为:,求该信源的信息率失真函数R(D)。,解：根据(4.2.4)式计算可得，由题设，根据参量表达式按如下步骤进行求解。第一步：由式(4.3.14)求,第二步：由式(4.3.13)求,第三步：由式(4.3.16)求D(s)，将上述结果代入式(4.3.16)有,第四步：由式(4.3.17)求R(s)，将上述结果代入式(4.3.17)有,应用式(4.3.11)，还可求得此时的试验信道转移概率：,4.4 连续无记忆信源的信息率失真函数,在讨论完离散无记忆信源以后，我们现在转向连续无记忆

16、信源的信息率失真函数及其求解。研究连续信源的信息率失真函数比离散信源更有实际意义，因为连续随机变量不可能用有限比特加以精确描述，即连续信源信息量为无限大，传送无限大信息量既无必要，也不可能。所以连续信源都属于限失真范畴。,一、连续无记忆信源的信息率失真函数的定义 连续信源的平均失真度定义为：,通过试验信道获得的平均互信息为：,同样，确定一允许失真度D，凡满足平均失真小于D的所有试验信道的集合记为PD，则连续信源的信息率失真函数定义为：,二、高斯信源的信息率失真函数 对高斯信源，在一般失真函数下，其率失真函数是很难求得的，但在平方误差失真度量下，其率失真函数有简单的封闭表达式。对平方误差失真，试

17、验信道输入符号和输出符号之间失真为：,对应的平均失真度为：,在平方误差失真下，设允许失真为D，则高斯信源 的率失真函数为：,三、连续无记忆信源信息率失真函数的参量表述 同离散信源类似，率失真函数的计算也归结为求有约束极值的问题，不过在连续信源情况下试验信道的条件概率也是函数，所以，率失真函数的计算就变成求泛函的极值，即求：,的极小值，满足约束条件为：,约束条件下的泛函求极值问题和约束条件下的函数求极值问题类似，即利用拉格朗日乘子将问题转化为无约束极值问题，并用变分代替微分，对本节讨论的问题，等价于使下式的一阶变分为零：,其中 为待定函数，s为待定常数，其求解顺序完全类似于离散情况。,在此我们仅

18、给出最终结论：在连续无记忆信源下，达到信息率失真函数的试验信道的转移概率密度函数必需满足：,其中,需要说明的是，连续情况下的信息率失真函数与离散情况下信息率失真函数的一个主要差别在于当,从此意义上讲，连续信源的熵压缩编码是必不可少的。,四、差值失真度量下连续无记忆信源的信息率失真函数 一般情况下，连续无记忆信源下信息率失真函数的计算相当困难，绝大多数情况下无解析解。但当连续信源的失真函数D(x,y)为x和y的差值形式如：|x-y|，(x-y)2时，可以较容易地采用参量表述式来求得其上、下限。,(1)差值失真度量下率失真函数的Shannon下限,上式是香农首先得到的，因此称其右端为差值失真度量时

19、连续信源的香农下限。,(2)平方误差(差方)失真度量下率失真函数的上限 对均值为零，方差为的任意连续无记忆信源，在差方失真度量下的率失真函数满足如下结论：,4.5 保真度准则下的信源编码定理,定理4.1(保真度准则下的信源编码定理，香农第三定理)设R(D)为一离散无记忆信源的信息率失真函数，并且有有限的失真测度D。对于任意D，以及任意长的码长k，一定存在一种信源编码C，其码字个数为 使编码后码的平均失真度。,定理的含义是：只要码长k足够长，总可以找到一种信源编码，使编码后的信息传输率略大于(直至无限逼近)率失真函数R(D)，而码的平均失真度不大于给定的允许失真度，即：或是：在允许失真D的条件下

20、，信源最小的，可达的信息传输率是信源的R(D)。,由于R(D)为给定D前提下信源编码可能达到的下限，所以香农第三定理即说明了：达到此下限的最佳信源编码是存在的。,实际的信源编码(无失真编码或先限失真编码后无失真编码)的最终目标是尽量接近最佳编码，使编码信息传输率接近最大值log r，而同时又保证译码后能无失真地恢复信源的全部信息量H(S)或限失真条件下的必要信息量R(D)。编码后信息传输率的提高使每个编码符号能携带尽可能多的信息量，-使得传输同样多的信源总信息量所需的码符号数大大减少-使所需的单位时间传输信道单位时间信道容量Ct大大减少，或在Ct不变的前提下使传输时间大大缩短，从而提高了通信的

21、效率。,香农第三定理仍然只是个存在性定理，至于最佳编码方法如何寻找，定理中并没有给出。如何计算符合实际信源的信息率失真函数R(D)?如何寻找最佳编码方法才能达到信息压缩的极限值R(D)?这是该定理在实际应用中存在的两大问题，它们的彻底解决还有赖于继续的努力。尽管如此，香农第三定理毕竞对最佳限失真信源编码方法的存在给出了肯定的回答，它为今后人们在该领域的不断深入探索提供了坚定的信心。,联合有失真信源信道编码定理,Shannon第二定理：只要信道容量大于信源的极限熵，就能在信道中做到有效的、无错误地传输信息，不满足时，则不可能在信道中以任意小的错误概率传输信息。有了第三定理，当不满足上述条件时，只要在允许一定的失真时，仍能做到有效地、可靠地传输信息。若通过信道来传输信源，如果信道容量CR(D),则总能以保真度D+再现信源的信息。反之则不能。,