第5章 有失真信源编码

第章 有失真信源编码（信息率失真函数）离散信源有失真编码连续信源有失真编码5.1 信息率失真函数的概念在第章我们证明了当输入随机变量的概率分布确定时，互信道是条件转移概率的下凸函数，即互信息必存在一个最小值。然而，在没有其它约束条件的情况下，这个最小值就是零。因为一方面互信息总是非负的，另一方面，当输入和输出随机变量相互独立时互信息等于零。所以研究一般情况下互信息的极小值问题没有什么意义。无失真信源编码时，信源的熵是信息率所能达到的下限。在很多实际情况下，要做到完全没有失真是没有必要的，特别是对连续信源编码，由于信源的绝对熵无穷大，要达到无失真编码是不可能的。为此，我们有必要研究在满足某种失真准则下互信息的极小值问题，即信息率失真函数。首先看离散信源的情况。设和是定义在相同取值域 上的离散型随机变量。失真函数 d(x,y) ,21naBA是定义在 上的非负函数BA ByAxYXdyx,),(),(例如，可定义 jiadjiji,0),(),(（.）其物理意义是当输入和输出相等时没有失真，当输入和输出不相等时失真是相同的。显然失真函数d(x,y)是对代表所引起失真的量度。失真函数的定义由所研究的客观问题决定。 （.）式的失真函数称为汉明失真准则。失真函数只定义了若干具体失真的数值，为了反映随机变量之间的总体失真情况，我们定义平均失真 ),(yxdE（.）对离散型变量 ij jidjp),(|（.）如果和都是维随机矢量，可定义矢量间的失真为 LllLyxYXd1),(),(（.）平均失真 Ll LllL dyxdEE11),(),(（.）其中 是第 个分量的平均失真。ld如果我们要求平均失真不大于某个定值。令 表示所有满足平均失真不DdijpPD|)(大于的条件概率矩阵的集合，我们定义 ),(min)(YXIDRDP（.）为信息率失真函数，或简称率失真函数。它表示在给定失真限度条件下互信息的极小值。在率失真函数的定义中涉及条件转移概率矩阵，似乎它也是表征率失真函数的参量，然而，率失真函数是表征信源的量，它只与信源和失真有关，而与转移概率矩阵无关。如果把转移概率矩阵看成信道，我们把这些不同的信道称为试验信道，对不同的试验信道，失真和互信息是不同的，只有当试验信道使互信息达到最小时，这个最小值就是率失真函数的值。为了理解率失真函数的实际意义，我们看如下有失真信源编码问题。设有一个有 2n 个符号 的等概率信源，失真函数是na21, jijid,10),(当（。）式的汉明失真准则。可允许的平均失真。在无失真情况下，传送每个符号的信息率至少 log2n。在有失真条件下我们采用下述编码方案： niaXYni 2,1, 当当这时平均失真不大于。编码后信息率 )1log(2log2,1, nnHRn 个显然，小于原来的 log2n。信息率压缩了 ，所付出的代价是容忍了的平均失)1l(真。现在的问题是， （）在失真为时，信息率能否更小，最小值是多少；（）采用何种编码方式使信息率尽可能小。第一个问题是率失真函数的计算问题，实际上是有失真信源编码问题；第二个问题是怎样进行信源编码问题，即信源编码方法问题。实际上，信息率可以更小些，但编码方法要复杂得多。5.2 率失真函数的性质5.2.1 （）函数的定义域（） 失真函数的下限失真函数 d(i,j)组成一个 失真矩阵mnij jidjpD),(|)(iijp|n)(只要令对应于 d(i,j)最小的 p(j|i)=1，其它所有的都为零，可得ijidpD),(n)min（.）当且仅当失真矩阵中每行中至少有一个零时 。通常情况下这是能够做到的。如果 ，0minD0minD只要改变单个符号的失真度，令 就可以保证失真矩阵每行至少有一)|()|()|( ijdjdijj个零，使 。对率失真函数来说，它只是起了坐标平衡的作用。所以假设 并不失一0minD min般性。对应于无失真情况，这时应该有 )()(0ipHXR但是上式成立是有条件的，它与失真矩阵的形式有关。只有当失真矩阵中每行至少有一个零，并且每列最多只有一个零时， 。)(0XHR否则（）小于（） ，这表示对信源符号集中有些符号进行压缩、合并，但没有引入失真（在具体的失真准则之下） 。（） 失真函数的上限 maxD定义域的上界定义为 0)(|min)|(axRDjp（.）必有 。由于a )(|(,0),(0)( jqijpYXID相 互 独 立所以 jiqijjq jidjidqp,)min),(mn)()(ax令 ，只要令对应于 最小的 q(j)等于 1，那么ijidpj,)()( )(jijD,nmax（.）5.2.2 （）函数的下凸性定理. 率失真函数是定义域 上的下凸函数maxin,D证明 （）（）函数的定义域是凸域。令 maxin2121 ,0,)( DD由率失真函数的定义 )|()|(in)( 1)|(11 ijpIijIRDPjp其中 是使互信息达到极小值的信道转移概率，对应的平均失真 。)|(1ijp 11)|(ijd)|()|(min)( 2)|(22 ijpIijIDRDPjp其中 是使互信息达到极小值的信道转移概率，对应的平均失真 。)|(2ijp 22)|(Dijd作 ，对应的平均失真)|(1()| 21ijijij jijppd),(|)(|Dijpdijpd jidjpiidiji jiij21 2212)()|()(| ),(|)(1,|) ,|(因此 ，即定义域是凸的。DPijp)|(（） （）函数的下凸性。由率函数的定义和互信息的下凸性 )(1)()|()1()|)|()( 221 DRijpIijpIijpIR 证毕。5.2.3 （）函数的单调递减性和连续性。（） （）函数的单调递减性R(D)函数的递减性由定义直接得到，其单调递减性可以通过（）函数的下凸性来证明。（） （）函数的连续性由互信息的连续性可以得到（）函数的连续性。R(D)H（X）DDmax（）函数示意图5.3 离散信源 R(D)函数的计算5.3.1 (D)函数的参量表达式（）函数的计算是目标函数ij jqipijpYXI )(|log)|(),(（.）在约束条件 ij Djidj),(|)(（.）mj nip1,21,|（.）下的极小值问题，其中 。iijpjq)|()(用拉格朗日乘子法，引入 n+1 常数个 s 和 ，求如下目标函数的极值。ni,21, （.）ij jidjpjpIijf ),(|)()|()|( ijip)|(令 0)|(ijpf得 0),()(|ln1)(ln1 ijidspijijq 整理得 )(,()(|lnipjisdjqip（.）也就是 mjnijsjiji ,21;,),(ex)()|( （.）其中 )(lnipi（.）（）式是一个由 nm 个方程组成的方程组。两边对 j 求和得（.）nijisdjqji ,21,),(exp)(（.）ijji ,)()(1（）式两边乘以 并对 求和得ipi jsdjq),(ex)()(（.）即0)(,2,1),(exp)( jqmjisdii （.）由把(5.3.9)式代入上式得 jlislqji ,),(e)(（.）(5.3.12)式是一个关于参量 s 的由 m 个方程组成的方程组, 可解得 ，代入mjq,21),(（5.3.9）式可解得 。ni2,1将所求得的 代入（5.3.6）式得到解决 nm 个 ，再代入（5.3.1）和（5.3.2）式即ijq)( )|(ijp得率失真函数和平均失真关于 s 的参量表达式。只要改变 s 的值（注意使 q(j)非负）即右得到 D(s)和 R(s)的值，从而得到 R（D）函数的曲线。ijiij jisdjiqpsD),(exp),()|)(（.）ij iijij iij i jpjdjpssjqisdjRln)|(),(|)(,ln| )(,exp)|()(（.）iiijipsDln)()(|下面研究 s 取值范围。事实上，参量 s 就是（）函数的一阶导数。因为 dDRRdii（.）dDsipsiDiii)(再求 ，对（.）式求关于 s 导数得dsi 0),(exp),(),(exp)( i ii jisdjjidsd两边乘以 q(j)，并对 j 求和得0),(exp),(),(exp)( ijiiji jisdjiqpjisdjqds 由（.）和（.）式 0)(Ddsiii代入（.）式即得 sdDR（.）由