第4章-信息率失真函数

第四章信息率失真函数无失真信源编码和有噪信道编码（香农第一定理和香农第二定理）告诉我们：只要信道的信息传输速率小于信道容量，总能找到一种编码方法，使得在该信道上的信息传输的差错概率任意小；反之，若信道的信息传输速率大于信道容量，则不可能使信息传输差错概率任意小。但是，无失真的编码并非总是必要的。原始图像红色图像绿色图像蓝色图像原始图像和限失真图像香农首先定义了信息率失真函数R(D)，并论述了关于这个函数的基本定理。定理指出：在允许一定失真度D的情况下，信源输出的信息传输率可压缩到R(D)值，这就从理论上给出了信息传输率与允许失真之间的关系，奠定了信息率失真理论的基础。信息率失真理论是进行量化、数模转换、频带压缩和数据压缩的理论基础。本章主要介绍信息率失真理论的基本内容，重点讨论离散无记忆信源。给出信源的失真度和信息率失真函数的定义与性质；讨论离散信源和连续信源的信息率失真函数计算；在此基础上论述保真度准则下的信源编码定理。4.1失真测度一、失真度•从直观感觉可知，若允许失真越大，信息传输率就可越小；若允许失真越小，信息传输率需越大。•所以信息传输率与（信源）编码所引起的失真(或误差)是有关的。首先讨论失真的测度。离散无记忆信源X，信源符号集X＝{a1,a2,…,ar}，概率分布为p(x)＝[p(a1),p(a2),…p(ar)]。信源符号通过信道传输到接收端，接收端的接收符号集Y＝{b1,b2,…bs}。对应于每一对(ai,bj)，我们指定一个非负的函数：称为单个符号的失真度(或失真函数)。通常较小的d值代表较小的失真，而d(ai,bj)＝0表示没有失真。0(,)(0)ijijdabij若信源变量X有r个符号，接收变量Y有s个符号，则d(ai,bj)就有r×s个,它可以排列成矩阵形式，即：该失真矩阵D，是r×s阶矩阵。111212122212(,)(,)...(,)(,)(,)...(,)::...:(,)(,)...(,)ssrrrsdabdabdabdabdabdabDdabdabdab实际这里X指的是原始的未失真信源，而Y是指失真以后的信源。如果假设X是信源，Y是信宿，那么X和Y之间必有信道。从X到Y之间实际上是失真算法，所以这里的转移概率p(bj/ai)是指一种失真算法，有时又把p(bj/ai)称为试验信道的转移概率，如图所示。原始信源失真信源试验信道信道XYp(bj/ai)[例1]离散对称信源(r=s)，“0-1”失真。信源X＝{a1,a2,…ar}，接收Y＝{b1,b2,…bs}。定义单个符号失真度：这种失真称为汉明失真。汉明失真矩阵是一方阵，对角线上的元素为零，即：0(,)1ijijijabdababrrD0...11:...::1...011...10对二元对称信源(s＝r＝2)，信源X＝{0,1}，接收变量Y＝{0,1}。在汉明失真定义下，失真矩阵为：0110D[例2]删除信源。信源X＝{a1,a2,…ar}，接收Y＝{b1,b2,…bs}(s=r+1)。定义其单个符号失真度为：•其中接收符号bs作为一个删除符号。•此时，意味着若把信源符号再现为删除符号bs时，其失真程度要比再现为其他接收符号的失真程度少一半。•二元删除信源r＝2，s＝3，X＝{0,1}，Y＝{0,1,2}。失真度为：则10121102Dd(0,0)=d(1,1)=0d(0,1)=d(1,0)=1d(0,2)=d(1,2)=1/20(,)11/2ijijdabijjs除j=s以外所有的j和i所有i[例３]对称信源(s=r)。信源X＝{a1,a2,…ar}，接收Y＝{b1,b2,…bs}。若失真度定义为：如果信源符号代表信源输出信号的幅度值，这就是一种平方误差失真度。它意味着幅度差值大的要比幅度差值小的所引起的失真更为严重，其严重的程度用平方来表示。当r＝3时，Ｘ＝{0,1,2}，Ｙ＝{0,1,2}，则失真矩阵为：2(,)()ijjidabba014101410D上述例子说明了失真度的具体定义。一般情况下根据实际信源的失真，可以定义不同的失真和误差的度量。另外还可以按其他标准，如引起的损失、风险、主观感觉上的差别大小等来定义失真度d(a,b)。二、序列失真度设，其中12,,,Nxxxxix取自信源符号集A；12,,,Nyyyy其中iy取自信宿符号集B。则序列失真度定义为：11(,)(,)NNiiidxydxyN三、平均失真度信源X和信宿Y都是随机变量，故单个符号失真度d(ai,bj)也是随机变量。规定了单个符号失真度d(ai,bj)后，传输一个符号引起的平均失真，即信源平均失真度：在离散情况下，信源X＝{a1,a2,…ar}，其概率分布p(x)＝[p(a1),p(a2),…,p(ar)]，信宿Y＝{b1,b2,…bs}。若已知试验信道的传递概率为p(bj/ai)时，则平均失其度为：[(,)][(,)]ijDEdabEdab11()(,)()(/)(,)rsijiijXYijDpabdabpapbadab•若平均失真度D不大于我们所允许的失真D0，即：DD0称此为保真度准则。信源固定（即给定了p(x)），单个符号失真度固定时（即给定了d(ai,bj)），选择不同试验信道，相当于不同的编码方法，所得的平均失真度是不同的。有些试验信道满足DD0，而有些试验信道D＞D0。凡满足保真度准则-----平均失真度DD0的试验信通称为----D失真许可的试验信道。把所有D失真许可的试验信道组成一个集合，用符号PD表示，则：PD={p(bj/ai)：DD0}4.2信息率失真函数及其性质一、信息率失真函数的定义信源给定，且又具体定义了失真函数以后，总希望在满足一定失真的情况下，使信源传输给收信者的信息传输率R尽可能地小。-------即在满足保真度准则下，寻找信源必须传输给信宿的信息率R的下限值------这个下限值与D有关。从接收端来看，就是在满足保真度准则下，寻找再现信源消息所必须获得的最低平均信息量。而接收端获得的平均信息量可用平均互信息I(X;Y)来表示，这就变成了在满足保真度准则的条件下，寻找平均互信息I(X;Y)的最小值。寻找平均互信息I(X;Y)的最小值。而PD是所有满足保真度准则的试验信道集合，因而可以在D失真许可的试验信道集合PD中寻找一个信道p(bj/ai)，使I(X;Y)取极小值。由于平均互信息I(X;Y)是p(bj/ai)的U型凸函数，所以在PD集合中，极小值存在。这个最小值就是在DD0的条件下，信源进行传输的最小平均信息量。即：(/)()(;)minjiDpbaPRDIXYR(D)-------信息率失真函数或简称率失真函数单位是：比特／信源符号•率失真函数给出了熵压缩编码可能达到的最小熵率与失真的关系;•其逆函数D(R)称为失真率函数,D(R)表示一定信息速率下所可能达到的最小的平均失真。二、信息率失真函数的性质•允许失真度D的下限可以是零，这是不允许任何失真的情况。1、R(D)的定义域R(D)的定义域为且：minmax0DDDmin()min(,)yxDpxdxymaxmin()(,)yxDpxdxy解：[例4]设试验信道输入符号集，各符号等概分布，失真矩阵如下所示，求和以及相应的试验信道的转移概率矩阵。123,,aaaminDmaxD123213321d123()min(1,2,3)()min(2,1,3)()min(3,2,1)papapamin()min(,)yxDpxdxy令对应最小失真度的，其它为“0”，可得对应的试验信道转移概率矩阵为：(,)ijdab(|)1jipbaminD100(|)010001pyxmax123123123min()(,)min()1()2()3,()2()1()2,()3()3()1yxDpxdxypapapapapapapapapa上式中第二项最小，所以令，，可得对应的试验信道转移概率矩阵为:2()1pb13()()0pbpbmaxD010(|)010010pyx2、R(D)是关于平均失真度D的下凸函数设为任意两个平均失真，，则有：12,DD01a1212[(1)]()(1)()RaDaDaRDaRD3、R(D)是区间上的连续和严格单调递减函数。minmax(,)DD信息率失真函数的一般形状)0()(RUH连续离散0D()RDＨ(Ｘ)0D()RDmaxDminDmax()RD4.3离散无记忆信源的信息率失真函数已知信源的概率分布p(x)和失真函数d(x,y)，就可求得信源的R(D)函数。原则上它与信道容量一样，即在有约束条件下求极小值的问题。也即选取适当的试验信道p(x/y)使平均互信息最小化：其约束条件为:(/)0jipba1(/)1sjijpba11()(/)(,)rsijiijijpapbadabD111(/)(,)()(/)log()(/)rsjiijirijijiipbaIXYpapbapapba一般取等号一、等概率、对称失真信源的R(D)计算对于等概、对称失真的信源，存在一个与失真矩阵具有同样对称性的转移概率分布达到率失真R(D)。解：[例5]有一个二元等概平稳无记忆信源，接收符号集为且失真矩阵为：0,1X0,1,2Y01[]01d求率失真函数R(D)。min()min(,)0yxDpxdxymaxmin()(,)1yxDpxdxy由于信源等概分布，失真函数具有对称性，因此，存在着与失真矩阵具有同样对称性的转移概率分布达到率失真R(D)，该转移概率矩阵可写为：(),1pyx由于，因此对于任何有限平均失真，必须,于是转移概率矩阵为：(0,1)(1,0)dd001()01pyxa对应此转移概率矩阵的平均失真：因此:可求得此时的互信息为：,()()(,)1xyDpxpyxdxy1D()(;)[()(/)]11(,,(1,)22112loglog(1)log(1)log22RDIXYHYHYXDDHDHDDDDDDDDDD）－－(1)(1)log(1)(1)log(1)(1)1DDDDDDD)(DR10D1D二、信息率失真函数的参量表述求信源的R(D)函数，原则上与求信道容量一样，是在有约束条件下求极小值的问题。也就是适当选取试验信道p(y/x)使平均互信息最小化，111(/)(,)()(/)log()(/)nmjiijirijijiipbaIXYpapbapapba应用拉格朗日乘子法，原则上可以求出解来。困难在于：•要得到显式的解析表达式，则比较困难，通常只能用参量形式来表达。•要保证约束条件式p(bj/ai)0，应用拉格朗日乘子法解得的某些p(bj/ai)很可能是负的。在这情况下，必须假设其p(bj/ai)=0，然后重新计算，这就使得计算复杂化了。•下面介绍用拉格朗日乘子法求解R(D)函数，并用s作为参量来表述率失真函数R(s)和失真函数D(s)。•由(1)式知，当信源的概率分布p(x)固定，平均互信息仅仅是试验信道p(bj/ai)的函数。•若先不考虑(2)式的约束，约束条件(3)式包含n个等式，取拉格朗