第5章 CHAPTER 5 限失真信源编码 第4章讨论了无失真信源编码，给出了无失真信源编码定理即香农第一定理。 现在一个自然而然的问题是： 在信道传输信息时是否必须完全无失真？回答是： 通常不需要。例如，人类主要通过视觉和听觉获取信息，人的视觉大多数情况下对于每秒25帧以上的图像认为是连续的，通常只需传送每秒25帧的图像就能满足人类通过视觉感知信息的要求，而不必占用更大的信息传输率。而对于人类的听觉，大多数人只能听到几千赫兹到十几千赫兹的声音，即使经过专业训练的音乐家，一般也不过听到二十千赫兹的声音。所以，为了提高信息传输效率，在实际中通常总是要求在保证一定质量的前提下在信宿近似地再现信源输出的信息，或者说在保真度准则下允许信源输出存在一定的失真。 本章将讨论在允许一定失真情况下的信源编码问题，从分析失真函数、信息率失真函数出发，给出限失真编码定理，即香农第三定理。 5.1失真函数 从本质上看，限失真信源编码就是对数据进行压缩。在实际问题中，被压缩的数据有一定的失真是可以容忍的。但是，当失真大于某一限度后，信息质量将被严重损伤，甚至会丧失其实用价值。要规定失真限度，必须要有一个定量的失真测度，为此需要引入失真函数的概念。 5.1.1失真度 图5.1限失真信源编码模型 在数学模型上，可将有失真的信源编码过程看作数据通过一种有干扰的信道。这种干扰信道常被称作试验信道。如图5.1所示，信源输出原始数据x1,x2,…给试验信道，而信道输出有失真的数据y1,y2,…给信宿，这就完成了数据压缩。先考虑简单的单符号信源的情况，然后再考虑多符号信源的情况。 设有一个单符号离散无记忆信源X，其概率空间为 X P=x1x2…xn P(x1)P(x2)…P(xn) 让试验信道输出符号集表示为{y1,y2,…,ym}，用一个非负函数d(xi,yj)表示发出xi收到yj的失真度。那么整体失真情况就可用如下矩阵来刻画，称为失真矩阵。 D=d(x1,y1)d(x1,y2)…d(x1,ym)  d(xn,y1)d(xn,y2)…d(xn,ym)=［dij］ 失真度d(xi,yj)的函数形式可以根据需要任意选取，例如平方代价函数、绝对代价函数、均匀代价函数等。常用的失真函数如下： 均方失真d(xi,yj)=(xi-yj)2 绝对失真d(xi,yj)=|xi-yj| 相对失真d(xi,yj)=|xi-yj||xi| 误码失真d(xi,yj)=δ(xi,yj)=0,xi=yj 1,其他 例5.1假定试验信道就是二进制纯删除信道。设输入符号集为A={0,1}，输出符号集为B={0,?,1}，定义失真矩阵为 D=00.51 10.50 该失真矩阵表明，发出0收到0或者发出1收到1是没有失真，发出0收到1或者发出1收到0是完全失真，发出0或1收到删除符号“？”表示有部分失真。 考虑将失真函数概念推广到矢量传输的情况。为此，需要考虑单符号信源X的K次扩展信源XK。设试验信道输入的是长度为K的信源符号序列 xi=［xi1,xi2,…,xiK］，xik∈{x1,x2,…,xn} 经信道传输后，信宿接收到的长度为K的符号序列可表示为 yj=［yj1,yj2,…,yjK］，yjk∈{y1,y2,…,ym} 则发出xi收到yj的失真度可定义为 dK(xi,yj)=1K∑Kk=1d(xik,yjk)(5.1) 所有这些不同的dK(xi,yj)可形成一个nK×mK阶失真矩阵DK。 例5.2在例5.1的条件下，求出K=2时的失真矩阵。 解按定义可以计算出 d2(00,00)=12［d(0,0)+d(0,0)］=0 d2(00,0?)=12［d(0,0)+d(0,?)］=14 d2(00,01)=12［d(0,0)+d(0,1)］=12  d2(00,11)=12［d(0,1)+d(0,1)］=1 于是有 D2=0141214123412341 1214034121413412 1234114123401412 1341234121412140■ 5.1.2平均失真度 在单符号情况中，xi、yj均是随机变量，因此失真函数d(xi,yj)也是随机变量,称失真度的数学期望为平均失真度，并记为。可表示为 =Ε［d］=∑ni=1∑mj=1P(xi,yj)d(xi,yj) =∑ni=1∑mj=1P(xi)P(yj|xi)d(xi,yj) 平均失真度是对给定信源分布{P(xi)}在给定转移概率分布为{P(yj|xi)}的试验信道中传输时失真的总体量度。 在多符号情况中，由式(5.1)，平均失真度可表示为 K=E［dK］=1K∑Kk=1E［d(xik,yjk)］=1K∑Kk=1k 其中，k是第k个位置上符号的平均失真度。显然，由第3章讨论可知，如果多符号信源是离散无记忆K次扩展信源，而试验信道是离散无记忆K次扩展信道，则每个位置上符号的平均失真度k相等，为，此时有K=。 例5.3设信源X有2n个符号，其概率空间为 X P=x1x2…x2n 12n12n…12n 与输入符号集一样，试验信道输出符号集也为{x1,x2,…,x2n}，而失真函数为 d(xi,xj)=1,i≠j 0,i=j 假定可允许平均失真度≤12，试分析信息传输率可压缩程度。 解信源X所有2n个符号是等概率分布的，因此按照熵的性质，信息熵达到最大值为H(X)=log(2n)。如果对信源X进行无失真编码，即要求=0，则相应的试验信道应是无干扰信道，此时信息传输率就等于log(2n)。 当可允许平均失真度≤12时，一个容易实现的信源编码方案是： 编码器输入为x∈{x1,x2,…,xn}，输出为x； 输入为x∈{xn+1,xn+2,…,x2n}，输出为xn。这样其等效试验信道的信道转移概率为 P(y=xj|x=xi)=1，i=j,1≤i≤n 1，j=n,n+1≤i≤2n 0，其他 由此可以计算出该编码方案的平均失真度为 =∑2ni=1∑2nj=1P(xi)P(xj|xi)d(xi,xj)=12 因此，该编码方案满足对平均失真度的要求。由上述信道转移概率表达式可知，该试验信道实际上是一个确定信道，因此有 H(Y|X)=0 I(X;Y)=H(Y)-H(Y|X)=H(Y) 容易计算出输出符号概率分布为 P(y=xj)=12n，1≤j≤n-1 1+n2n，j=n 0，其他 这样 I(X;Y)=H(Y)=log2n-n+12nlog(n+1) 此时信息传输率变为log2n-n+12nlog(n+1)，或者说信息传输率压缩了 n+12nlog(n+1) 还能进一步压缩吗？信息传输率最大可压缩到什么程度？这是5.2节要讨论的话题。 ■ 5.2信息率失真函数 我们将有失真的信源编码器视作有干扰的信道，那么就可以用分析信道信息传输的方法来研究限失真编码问题。一个自然而然的问题是，对于给定的信源，在允许一定失真条件下，试验信道中最低信息传输速率(接收端为再现信源消息所应得的最小平均互信息量)是多少呢？ 5.2.1信息率失真函数的定义 对于上述的一定失真条件，通常用平均失真度来表示。如果预先规定平均失真度为D，则称信源编码后的平均失真度不大于D的准则为保真度准则。因此，数据压缩问题就是，对于给定的信源，在满足保真度准则(≤D)的前提下，使信息传输率尽可能小。将满足保真度准则的这些试验信道称为D失真许可的试验信道。信道用信道转移概率P(y|x)刻画，因此D失真许可的试验信道集合可表示为 CD={P（y|x）： ≤D}(5.2) 对于单符号离散无记忆信道，D失真许可的试验信道集合可表示为 CD={P(yj|xi)： ≤D,1≤j≤m,1≤i≤n}(5.3) 考虑对一个单符号离散无记忆信源X进行数据压缩，且允许平均失真度不超过D，那么对其最低的压缩率会是多少呢？这个问题实际上可以变换为这样的问题： 在D失真许可的试验信道集合CD中，寻找一个信道P(yj|xi)使信源X经过此信道传输时，其信道传输率I(X;Y)达到最小。这个最小的信道传输率I(X;Y)就是最低的数据压缩率，将之定义为信息率失真函数，并简称率失真函数，记为R(D)，即有 R(D)=minP(yj|xi)∈CDI(X;Y)(5.4) 率失真函数可再写为 R(D)=minP(yj|xi)∈CD∑ni=1∑mj=1P(xi)P(yj|xi)logP(yj|xi)P(yj)(5.5) 其中，P(xi)是信源发出符号概率分布，i=1,2,…,n； P(yj|xi)是信道转移概率分布，i=1,2,…,n，j=1,2,…,m； P(yj)是接收端收到符号概率分布，j=1,2,…,m。 至于多符号情况，率失真函数可延伸表示为 RK(D)=minP(yj|xi)∈CDI(X;Y)(5.6) 5.2.2信息率失真函数的性质 信息率失真函数R(D)有如下三个基本性质。 (1) R(D)是非负函数，其定义域为［0，Dmax］，其值域为［0，H(X)］。 (2) R(D)是关于失真度D的下凸函数。 (3) R(D)是关于失真度D的严格递减函数。 下面分别论证这三个性质。 1. R(D)的定义域性质 R(D)的定义域表示为［Dmin,Dmax］。一般情况下，由失真度的非负性和平移性，可以假设Dmin=0，这对应于无失真情况，此时必有R(0)≤H(X)。关于Dmax，显然应该满足R(Dmax)=0。定义Dmax是满足R(D)=0的所有平均失真度D中的最小值，即 Dmax=minP(y|x)∈C(0)DE［d(x,y)］ 其中，C(0)D={P(y|x):I(X;Y)=0}。 下一个问题是如何能求出Dmax。由于I(X;Y)=0的充分必要条件是X与Y统计独立，即对于任意的x,y有P(y|x)=P(y)成立。这样 Dmax=min∑yP(y)∑xP(x)d(x,y)(5.7) 式中，P(x)和d(x,y)是已知的，该最小化问题归结为选择分布P(y)使式(5.7)右端达到最小。如果对最小的∑xP(x)d(x,y)选取P(y)=1，而对其他的∑xP(x)d(x,y)选取P(y)=0，则必有 Dmax=miny∑xP（x）d（x，y）(5.8) 例5.4设输入符号集为A={0,1}，输出符号集为B={0,1}，输入概率分布为P(x=0)=13,P(x=1)=23，而失真矩阵为 D=［d(x,y)］=01 10 试求率失真函数R(D)的定义域。 解如果选择信道转移概率等于 P(y=0|x=0)=1 P(y=1|x=0)=0 P(y=0|x=1)=0 P(y=1|x=1)=1 可以计算出此时的平均失真度为 =∑x,yP(x)P(y|x)d(x,y)=0 因此，有Dmin=0。此外，由式(5.8)可知 Dmax=miny∑xP(x)d(x,y) =min13×0+23×1,13×1+23×0 =13 故R(D)的定义域为0,13。■ 2. R(D)的下凸函数性质 假定D1和D2是两个平均失真度，而P1(y|x)和P2(y|x)是在满足保真度准则D1和D2的前提下使I(X;Y)达到极小的信道转移概率，则有 R(D1)=minP(y|x)∈CD1I［P(y|x)］=I［P1(y|x)］ R(D2)=minP(y|x)∈CD2I［P(y|x)］=I［P2(y|x)］ 且 ∑x∑yP(x)P1(y|x)d(x,y)≤D1 ∑x∑yP(x)P2(y|x)d(x,y)≤D2 令0<α<1，且使 D0=αD1+(1-α)D2 P0(y|x)=αP1(y|x)+(1-α)P2(y|x) 记D是P0(y|x)所对应的失真度，则 D=∑x∑yP(x)P0(y|x)d(x,y) =α∑x∑yP(x)P1(y|x)d(x,y)+(1-α)∑x∑yP(x)P2(y|x)d(x,y) =αD1+(1-α)D2 =D0 所以，P0(y|x)∈CD0，即P0(y|x)是D0失真许可的试验信道。再由信息率失真函数定义式(5.4)，可得 R(D0)=minP(y|x)∈CD0I［P(y|x)］≤I［P0(y|x)］ =I［αP1(y|x)+(1-α)P2(y|x)］≤αI［P1(y|x)］+(1-α)I［P2(y|x)］ =αR(D1)+(1-α)R(D2)(5.9) 这符合下凸函数的定义。因此R(D)是关于失真度D的下凸函数。 此外，值得一提的是，R(D)显然是连续函数，因为I［P(y|x)］是P(y|x)的连续函数，由R(D)的定义可知R(D)是连续函数。 3. R(D)的严格递减函数性质 R(D)是非增函数。因为若D1>D2，则满足保真度D1与D2的试验信道集合CD1和CD2满足CD1CD2，进而由R(D)的定义有 R(D1)=minP(y|x)∈CD1I［P(y|x)］≤minP(y|x)∈CD2I［P(y|x)］=R(D2)(5.10) 要证明R(D)是严格递减函数，只需证明式(5.10)中等号不成立即可。下面采用反证法来证明。 在［0，Dmax］中任取两点D1和D2满足0ω(5.12) R(D)的曲线如图5.4所示。 图5.5给出在不同ω值下的R(D)曲线。从图5.5可以看出，对于同一D,ω越大，R（D）越大，信源压缩的可能性越小。 图5.4二进制信源X的R(D)曲线 图5.5不同ω值下的R（D）函数 值得一提的是，在前面的计算中，我们是从反向试验信道来计算I（X； Y）的。实际上，这个反向试验信道就是正向试验信道，它们只是一个信道从两个不同角度考虑的两种不同表示方法。反向试验信道的转移概率为P（x|y），而正向试验信道的转移概率为P（y|x）。当P（x）给定时，就可从P（y|x）唯一地确定出对应的P（x|y），反之亦然。所以，反向试验信道和正向试验信道指的是同一试验信道。依据平均互信息量的互易性，从反向试验信道进行计算就方便了。 图5.6正向试验信道 对于信源X，从寻找所得的反向试验信道可求得正向试验信道为 P(y=0|x=0)=1-D P(y=1|x=0)=D P(y=0|x=1)=D P(y=1|x=1)=1-D 如图5.6所示。 5.3信息率失真函数的计算 如果信源概率分布和失真函数已知，求信息率失真函数问题就变成了在保真度准则的约束下求平均互信息量的极小值问题。在一般情况下，这个问题很难求得如5.2.3节给出的闭式解，通常要采用参量表述方法或者迭代计算方法来进行求解。 5.3.1率失真函数的参量表述方法 试验信道的输入概率分布为 X P=x1x2…xn P(x1)P(x2)…P(xn) 输出概率分布为 Y P=y1y2…ym P(y1)P(y2)…P(ym) 字符传输的失真函数为 d(xi,yj),1≤i≤n,1≤j≤m 为了表达简洁，记 dij=d(xi,yj)，pij=P(yj|xi) pi=P(xi)，qj=P(yj) 其中 P(yj)=∑ni=1P(xi)P(yj|xi)=∑ni=1pipij 则信息率失真函数R(D)的计算问题变为在约束条件 ∑ni=1∑mj=1pipijdij=D ∑mj=1pij=1，i=1,2,…,n(5.13) 下求平均互信息量 I(X;Y)=∑ni=1∑mj=1pipijlogpijqj(5.14) 的极小值问题。 在数学上应用著名的拉格朗日乘子法就可将上述条件极值问题转换为无条件极值问题。为此，引入乘子s和μi,i=1,2,…,n，作辅助函数 Ω({pij})=I(X;Y)+sD-∑ni=1∑mj=1pipijdij+∑ni=1μi1-∑mj=1pij 由辅助函数对各个信道转移概率pij分别求偏导并置之为零，可得n×m个方程 δΩδpij=0,i=1,2,…,n;j=1,2,…,m(5.15) 如果由式(5.15)能解出n×m个pij，代入式(5.14)就会得到在式(5.13)约束条件下的I(X;Y)极小值，即为所求的R(D)。 对式(5.15)中的辅助函数展开并逐项求偏导后可得 pilogpijqj-spidij-μi=0,1≤i≤n,1≤j≤m(5.16) 这样 pij=qj·esdij+μi/pi,1≤i≤n,1≤j≤m(5.17) 式(5.17)可简写为 pij=qj·λi·esdij,1≤i≤n,1≤j≤m(5.18) 其中， λi=eμi/pi，1≤i≤n(5.19) 式(5.18)给出的pij表达式仍涉及待定常数s和λi,i=1,2,…,n，因此需要结合约束条件式(5.13)进行联合求解。 考虑保留待定常数s作为参量，求出仅含s的所有pij与λi参量表达式。由于∑mj=1pij=1，故对式(5.18)求和得 λi=1∑mj=1qj·esdij，1≤i≤n(5.20) 另外，由于qj=∑ni=1pipij，因此对式(5.18)两边同乘pi，并求和得 ∑ni=1λi·pi·esdij=1,1≤j≤m(5.21) 将式(5.20)代入式(5.21)可得关于qj的m个方程 ∑ni=1pi·esdij∑mj=1qj·esdij=1,1≤j≤m(5.22) 由式(5.22)可解出含有s的m个qj，再将这些qj代入式(5.20)可解出含有s的n个λi，最后将这些解出的m个qj和n个λi代入式(5.18)就可解出仅含有s的n×m个pij。 将这些解出的pij代入约束条件式(5.13)可得 D=∑ni=1∑mj=1λipiqjdijesdij(5.23) 式(5.23)给出的允许失真度表达式仅含参量s，故记为D(s)。将极值解式(5.18)代入平均互信息量表达式(5.14)并利用式(5.23)进行化简，最后可得仅含参量s的率失真函数表达式为 R（D）=R（s）=∑ni=1Pilogλi+sD（s）(5.24) 一般情况下，参量s无法消去，因此得不到R(D)的闭式解，只有在一些比较简单的情况下才可以消去参量s，得到R(D)的闭式解。若无法消去参量s，就需要进行逐点计算。 与待定常数μi(i=1,2,…,n)相比，待定常数s在率失真函数问题的求解中发挥着十分重要的作用。为此，下面深入分析其特性。 允许失真度D(s)是参量s的函数，反过来，s也可看作D的函数，进而λi也可看作D的函数。这样可以对式(5.24)表示的R(D)关于D进行求导以获得率失真函数的斜率： dRdD=RD+Rs·sD+∑ni=1Rλi·λiD =RD+Rs·dsdD+∑ni=1Rλi·dλidD =s+D·dsdD+∑ni=1piλi·dλidD =s+D+∑ni=1piλi·dλids·dsdD(5.25) 为求出dλids，在式(5.21)中对s求导得 ∑ni=1pi·esdijdλids+λipidijesdij=0(5.26) 对式(5.26)两边同乘以qj，并对j求和得 ∑ni=1pi∑mj=1qj·esdijdλids+∑ni=1∑mj=1qjpiλidijesdij=0(5.27) 将式(5.20)和式(5.23)代入式(5.27)得 ∑ni=1pi1λidλids+D=0(5.28) 将式(5.28)代入式(5.25)最后可得 dRdD=s(5.29) 图5.7率失真函数R(D)与 其斜率s之间的关系 式(5.29)表明，保留的待定常数s参量，正好就是允许失真度D作为变量的率失真函数R(D)的斜率。由于R(D)是关于失真度D的下凸函数和严格递减函数，这意味着R(D)的斜率s=dRdD＜0，且dsdD＞0，斜率s会随失真度D的增加而增加。一般而言，R(D)的斜率s在开区间(0，Dmax)是失真度D的连续函数，但当D=0时，s=-∞； 当D>Dmax时，R(D)=0，s=dRdD=0。在D=Dmax时，除一些特殊情况外，s将从负值跳到零，因而在这一点上，s是不连续的。率失真函数R(D)与其斜率s之间关系如图5.7所示。 例5.5设信源X有n个符号，其概率空间为 X P=x1x2…xn 1n1n…1n 试验信道输出符号也有n个，其集合为{y1,y2,…,yn}，失真函数定义为 d(xi,yj)=1,i≠j 0,i=j 求信息率失真函数R(D)。 解简记 dij=d(xi,yj)，pi=P(xi)，qj=P(yj) 为了求解信息率失真函数R(D)，先求出带参量s的n个qj和n个λi表达式。为此，将已知条件代入式(5.22)得 q1+q2es+…+qnes=1+(n-1)esn q1es+q2+…+qnes=1+(n-1)esn  q1es+q2es+…+qn=1+(n-1)esn 解上述方程组可得 qj=1n,1≤j≤n(5.30) 将式(5.30)代入式(5.20)得 λi=n1+(n-1)es,1≤i≤n(5.31) 然后再将式(5.30)和式(5.31)代入式(5.23)得 D(s)=(n-1)es1(n-1)es(5.32) 利用式(5.32)解出s得 s=logD(n-1)(1-D)(5.33) 将式(5.31)代入式(5.24)得到关于仅含参量s的R(D)表达式，然后再代入式(5.33)，从而有 R（D）=∑ni=1pilogλi+sD =logn-Dlog(n-1)-H(D)(5.34) 其中，H(D)=-DlogD-(1-D)log(1-D)。 继续考虑例5.3。应用例5.5的最后结果式(5.34)，可知 R12=log(2n)-12log(2n-1)-1 因此，在可允许平均失真度≤12情况下，信息传输率最大可压缩量是 12log(2n-1)+1 5.3.2率失真函数的迭代计算方法 5.3.1节给出了信息率失真函数R(D)的参量表达式R(s)，但是要进行具体计算仍然是相当困难的，一般需要借助计算机进行迭代运算。众所周知，要形成迭代算法的关键是有描述优化函数的具有互为因果关系的两个自变量组。依据率失真函数R(D)的定义表达式，选择输出概率分布{qj}和信道转移概率{pij}作为可产生迭代运算的两个自变量组。下面推导形成迭代运算所需的公式。 依据率失真函数R(D)定义表达式，求解R(D)的问题就是求在式(5.13)的约束条件下平均互信息量I(X;Y)极小值的问题，而这个问题通过拉格朗日乘子法可转换为求引入待定常数s和{μi,1≤i≤n}的辅助函数 Ω(s,{pij})=I(X;Y)+sD-∑ni=1∑mj=1pipijdij+∑ni=1μi1-∑mj=1pij 的极小值问题，这已变成了无约束条件下的极值问题。在已知输入概率分布{pi}的情况下，{qj}与{pij}是相互关联的。为了导出迭代运算公式，先假定{qj}固定不变，与{pij}无关。在这种情况下，对辅助函数计算关于各个pij的偏导，并置之为零，可得如下n×m个方程 Ωpij=0,i=1,2,…,n;j=1,2,…,m(5.35) 完全类似于5.3.1节中的推导，有 p*ij=qj·λi·esdij,1≤i≤n,1≤j≤m(5.36) 其中， λi=eμi/pi=1∑mj=1qj·esdij，1≤i≤n(5.37) 因此 p*ij=qj·esdij∑mj=1qj·esdij,1≤i≤n,1≤j≤m(5.38) 这就是在{qj}固定不变假定下{pij}的优化解。 现在假定{pij}固定不变，与{qj}无关。可以证明，平均互信息量I(X;Y)是关于{qj}的下凸函数。因此，在式(5.39)的约束条件下存在关于I(X;Y)极小值求解问题 ∑ni=1∑mj=1pipijdij=D ∑mj=1qj=1(5.39) 这个问题可通过拉格朗日乘子法转换为引入待定常数s和μ下关于辅助函数 Ψ(s,{qj})=I(X;Y)+sD-∑ni=1∑mj=1pipijdij+μ1-∑mj=1qj 的极小值求解问题。在这种情况下，对辅助函数计算关于各个qj的偏导，并置之为0，可得如下m个方程 Ψqj=0,j=1,2,…,m(5.40) 解上述方程组得 q*j=1μ∑ni=1pipij(5.41) 利用约束条件式(5.39)可进一步解出 μ=∑mj=1∑ni=1pipij=1(5.42) 因此有 q*j=∑ni=1pipij,1≤j≤m(5.43) 这就是在{pij}固定不变假定下{qj}的优化解。 式(5.43)和式(5.38)形成求解率失真函数R(D)迭代算法所需的公式，即 q(t)j=∑ni=1pip(t)ij,1≤j≤m p(t+1)ij=q(t)jesdij∑mj=1q(t)jesdij,1≤i≤n 1≤j≤m(5.44) 求R(D)迭代算法具体步骤描述如下。 （1） 设定标志算法收敛的误差精度ε，给定参量s值。 （2） 对{p(1)ij}赋初始值，一般可取p(1)ij=1m，1≤i≤n,1≤j≤m。计算 q(1)j=∑ni=1pip(1)ij,1≤j≤m （3） 利用计算出的结果{q(1)j,1≤j≤m}，再计算 p(2)ij=q(1)jesdij∑mj=1q(1)jesdij,1≤i≤n,1≤j≤m （4） 计算 q(2)j=∑ni=1pip(2)ij,1≤j≤m 并检验由{q(1)j}、{q(2)j}、{p(1)ij}和{p(2)ij}产生的计算结果是否满足如下收敛性要求 |R(2)(s)-R(1)(s)|≤ε，|D(2)(s)-D(1)(s)|≤ε （5） 如没有满足收敛性要求，则继续重复第(3)步和第(4)步，直至第t次迭代达到要求。此时由{q(t)j}和{p(t)ij}产生的R(t)(s)和D(t)(s)即为所求。这实际上给出了R(D)-D坐标图上的一个点。 （6） 再给定参量s新的值，重复第(2)步到第(5)步获得新的R(s)和D(s)值。这实际上给出了R(D)-D坐标图上的另一个点。不断重复上述过程，就能画出R(D)完整曲线。 参量s是率失真函数R(D)的斜率，其取值范围是(-∞，0)。所以，要得到整个R(D)曲线，可先选取一个绝对值充分大的负值s开始上述迭代过程，计算出相应的R(s)和D(s)值； 再逐渐增加s值，并计算R(s)和D(s)值； 当R(s)接近零时，计算过程结束，从而获得整个曲线。 理论上可以进一步证明上述迭代运算的收敛性，此处不再赘述。 以上侧重讨论了单符号离散无记忆信源率失真函数的性质、参量表述和迭代运算。尽管比较复杂，但这些方法和结果可以向多符号离散信源延伸。若多符号信源是平稳无记忆的，则可以证明当各维允许失真度一致时，即所有Dk=D时，RK(D)才会达到最小。 5.4限失真信源编码定理 设有一个离散无记忆信源X，其概率空间为 X P=x1x2…xn P(x1)P(x2)…P(xn) 记试验信道输出符号集为{y1,y2,…,ym}，用d(xi,yj)表示发出xi收到yj的失真度。设试验信道每次输入的是长度为K的信源符号序列 xi=［xi1,xi2,…,xiK］，xik∈{x1,x2,…,xn} 经信道传输后，信宿会接收到的长度为K的符号序列可表示为 yj=［yj1,yj2,…,yjK］，yjk∈{y1,y2,…,ym} 则发出xi收到yj的失真度可表示为 dK(xi,yj)=1K∑Kk=1d(xik,yjk) 从所有上述接收序列yj选取M个序列构成一个码，并称为码字数目为M、码长为K的分组码，记为C(M,K)。采用这样的分组码进行如下信源编码： 输入xi，输出使失真达到最小的码字yj。记 dK(xi|C)=minyj∈C dK(xi,yj) 则该分组码C(M,K)的平均失真度为 dK(C)=∑nKi=1P(xi)dK(xi|C) 由于信源是无记忆性的，因此有 P(xi)=∏Kk=1P(xik) 设D是预先给定的失真度。如果dK(C)≤D，则称分组码C(M,K)是满足保真度准则D的许可码。对于分组码C(M,K)，其信息率表示为R=1KlogM。 定理5.1对于离散无记忆信源X，其单字符失真度下的信息率失真函数为R(D)。则对于任意ε>0和D≥0，可以找到满足保真度准则(D+ε)的许可码C(M,K)，当K足够大时，其信息率满足 R≤R(D)+ε(5.45) 另外，对于满足保真度准则D的所有许可码，其信息率应满足 R≥R(D)(5.46) 定理5.1就是限失真信源编码定理，即香农第三定理，它可以推广到离散有记忆信源。定理5.1表明，对于率失真函数为R(D)的离散无记忆信源X，当信息率R＞R(D)时，只要信源序列长度K足够长，一定存在一种编码方法，其译码失真度小于或等于D+ε，其中ε为任意小的正数； 反之若R＜R(D)，则无论采用什么样的编码方法，其译码失真度必大于D。或者说，在失真限度内使信息率任意接近R(D)的编码方法存在，然而要使信息率小于R(D)，平均失真一定会超过失真限度D。 习题解答 5.1设输入符号集为X={0,1}，输出符号集为Y={0,1}。定义失真函数为 d(0,0)=d(1,1)=0 d(0,1)=d(1,0)=1 试求失真矩阵D。 解根据题意和定义，容易得到失真矩阵 D=01 10■ 5.2设有离散对称信源(r=s)，信源符号集为X={x1,x2,…,xr}，接收符号集为Y={y1,y2,…,ys}，定义单个符号失真度为 d(xi,yj)=0，i=j 1，i≠j 求失真矩阵D(［d］)。 解在失真度定义下，失真矩阵是一个方阵［d］，并有 ［d］=011…1 101…1 110…1  111…0 是r×r阶矩阵。■ 5.3假定离散矢量信源输出的矢量序列为X=X1X2X3，其中Xi(i=1,2,3)的取值为0和1，经信道传输后的输出为Y=Y1Y2Y3，其中Yi(i=1,2,3)的取值为0和1，定义单个符号失真函数 d(0,0)=d(1,1)=0 d(0,1)=d(1,0)=1 求矢量失真矩阵D3=［d3］。 解由矢量失真函数的定义得 d3(X,Y)=13∑3i=1d(Xi,Yi)=13［d(X1,Y1)+d(X2,Y2)+d(X3,Y3)］ 所以有 d3(000,000)=13［d(0,0)+d(0,0)+d(0,0)］ =13［0+0+0］=0 d3(001,000)=13［d(0,0)+d(0,0)+d(1,0)］ =13［0+0+1］=13 类似计算其他元素值，最后得其矢量失真矩阵为 D3=［d3］=01313231323231 13023132313123 13230132311323 23131301232313 13232310131323 23131231302313 23113231313013 12323132313130■ 5.4设有一个二元等概率信源： U={0，1}，p0=p1=12，通过一个二进制对称信道(BSC)。其失真函数dij与信道转移概率Pji分别定义为 dij=1,i≠j 0,i=j，Pji=ε，i≠j 1-ε,i=j 试求： (1) 失真矩阵［dij］； (2) 平均失真度。 解(1) 失真矩阵［dij］=01 10。 (2) 由信道转移概率矩阵 ［Pji］=1-εε ε1-ε 及 D-=∑i∑jpiPijdij 得D-=ε■ 5.5试证对离散信源，R(D=0)=H(p)(信源熵)的充要条件是失真矩阵D的每行中至少有一个为0，而每列中至多有一个为0。 证明必要性： 由于 D=0∑i∑jpiPjidij=0 又 pi>0,dij≥0,Pji≥0 故 D=0i,j,piPjidij=0Pji≠0,dij=0 Pji=0,dij=∞ 若［dij］矩阵中某行没有0，则对应的Pji全为0，必失真，与D=0矛盾。 若［dij］矩阵中某列有超过两个以上的0，则表示有不止一个i使得Pji≠0，必失真，从而得证。 充分性： 当D=0却无失真时，i、j一一对应，即 Pji=δij=1,i=j 0,i≠j 即对应的(dij)矩阵某行必有一个0，某列只有一个0。易知 R（D）D=0=∑i∑jpiδijlogδijpi=∑ipilog1pi=H(P)■ 5.6某信源含有三个消息，概率分布为p1=0.2,p2=0.3,p3=0.5，失真矩阵为 D=［d］=421 032 201 求Dmin和Dmax。 解因为有失真，所以Dmin不为零。 Dmin=∑Xp(xi)minY d(xi,yj) =1×0.2+0×0.3+0×0.5=0.2 根据率失真函数的定义域，可得 Dmax=minY∑Xp（x）d（x,y） =min4×0.2+2×0.5,2×0.2+3×0.3,1×0.2+2×0.3+1×0.5=1.3■ 5.7有一离散泊松信源，其分布为Pi=λii!e-λ，且∑∞i=0λii!e-λ=1，设其失真函数为 dij=1-δij=0,i=j 1，i≠j 试求： (1) 信源R（D）函数的定义域D； (2) 若令参数值λ=1，具体的D值范围。 解(1) 由R（D）函数性质可得 Dmin=0 Dmax=minj∑ipidij=minj∑iλii!e-λdij 由定义 (dij)=011… 101… 110… ………… 再由泊松分布性质可知λ>0，则 当j=0时，Dmax=λe-λ+λ22!e-λ+…=1-e-λ 当j=1时，Dmax=e-λ+λ22!e-λ+…=1-λe-λ 当j=2时，Dmax=e-λ+λe-λ+…=1-λ22!e-λ 因为D>0，则由前三项可知 λ≤1 所以有 1-e-λ<1-λe-λ<1-λ22!e-λ<… 故R（D）函数定义域为 ［0,1-e-λ］ (2) 令λ=1，则定义域为 ［0,1-e-1］■ 5.8设输入符号集为{0,1,2,3}，且输入信源的分布为 p（xi）=14（i=0,1,2,3） 设失真矩阵为 ［d］=0111 1011 1101 1110 求Dmin和Dmax及R(D)。 解四元对称信源在汉明失真矩阵下，它的平均失真度等于信道的平均错误概率pE，即 D=∑XYp(xi,yj)=pE 又根据最大允许失真度的定义，有 Dmax=minY∑xp（x）d（x,y）=1-1r=34 而最小允许失真度 Dmin=∑4i=1p(xi)minj d(xi,yj)=0 因为是四元对称信源，又是等概率分布，所以根据r元离散对称信源可得 R（D）=log4-Dlog3-H（D）,0≤D≤34 0,D>34■ 5.9设二进制信源为 X P=01 1212 失真函数矩阵为 ［d］=0a a0 求这个信源的Dmin和Dmax及R(D)。 解由已知条件可以求得 Dmin=0,Dmax=a2 (1) 达到Dmin的信道为 P=10 01 所以 R(0)=I（X； Y）=H(X)=H12 (2) 达到Dmax的信道为 P=01 01，P=10 10，或P=a1-a a1-a，0≤a≤1 在这些信道中，可计算得 R(Dmax)=Ra2=0 (3) 一般情况下，0a2 其中，HDa=-DalogDa-1-Dalog1-Da。■ 5.10设已知离散无记忆信源在给定失真量度 d(i,j),i=1,2,…,K;j=1,2,…,J 下的信息速率失真函数为R（D）。现定义新的失真量度 d′(i,j)=d(i,j)-gi 试证： 在新的失真量度下信息率失真函数R′（D）为R′（D）=R(D+G)，其中G=∑ip(ai)gi。 证明对离散无记忆信源 R（D）=min{I（X； Y）,E{d(X,Y)}≤D} 因为 R′（D）=min{I（X； Y）,E{d′(X,Y)}≤D} =min{I（X； Y）,E{d(i,j)-gi}≤D} =min{I（X； Y）,E{d(i,j)-E{gi}≤D}} =min{I（X； Y）,E{d(i,j)≤E{gi}+D}} 而E{gi}=∑ip(ai)gi=G，故上式可以表示为 R′（D）=min{I（X； Y）,E{d(i,j)≤D+G}}=R(D+G) 得证。■ 5.11一个离散无记忆信源输出符号等概率，失真函数如下所示： ［dij］=12 11 21 试求： (1) 信息率失真R（D）函数； (2) 试验信道转移概率。 解容易计算 Dmin=1,Dmax=43 在信源等概的条件下，若［d］具有对称性，则在p(y|x)具有对称性时，求出的I（X； Y）就等于率失真函数R（D）。 在本题中，根据［d］的对称性，可假设信道转移概率 ［p(y|x)］=1-aa 1212 a1-a，a为待定常数a<12 由假设的信道转移概率计算出信息量 I（X； Y）=H(Y)-H(Y|X) =∑Yp(y)log1p(y)-∑XYp(y|x)p（x）log1p(y|x)(5.49) 可以求出 {p(y1)=∑Xp(y1|x)p（x）=131-a+12+a=12 p(y2)=1-p(y1)=12(5.50) 将式(5.50)代入式(5.49)得 I（X； Y）=log2+13∑XYp(y|x)logp(y|x) =log2+13×2×(1-a)log(1-a)+aloga+12log12 =23［log2-H(a)］(5.51) 由假设的信道转移概率计算平均失真，得 =∑XYp(y|x)p（x）d（x,y）=13×2×(1-a)+2a+12=1+23a(5.52) 因为≤D，由式(5.52)得 a≤32(D-1) 图5.8习题5.11图 考虑到a<12，则有 32(D-1)<12Dmax=43 如图5.8所示，在043■ 5.12三元信源的概率分别为p0=0.4,p1=0.4,p2=0.2，失真函数为 dij=0,i=j 1,i≠j，i,j=0,1,2 试求： (1) 信息率失真函数R（D）； (2) 若此信源用容量为1bit和0.1bit的信道传送，其最小误码率Pe分别是多少？ 解(1) 根据题意 ［dij］=011 101 110 ［pij］=(0.4,0.4,0.2) Dmin=0,Dmax=minqj∑jqj∑ipidij=minj Dj D0=∑ipidi=0.6 D1=0.6,D2=0.8 则Dmax=0.6。 由参量表达式∑ipiλiesdij=1，得下列方程组 0.4λ0+0.4λ1es+0.2λ2es=1 0.4λ0es+0.4λ1+0.2λ2es=1 0.4λ0es+0.4λ1es+0.2λ2es=1 λ0=2.51+2es λ1=2.51+2es λ2=51+2es ∑jqjesdij=1λi 则有 q0+q1es+q2es=0.4(1+2es) q0es+q1+q2es=0.4(1+2es) q0es+q1es+q2=0.2(1+2es)q0=0.2(2-es)1-es q1=0.2(2-es)1-es q2=0.2(1-3es)1-eses≤13 故 D(S)=∑i∑jpiqjλiesdijdij =2es1+2esD2(1-D)≤13D≤52=0.4 R(S)=SD(S)+∑ipilogλi =S·2es1+2es+0.8log2.51+2es+0.2log51+2es =D·logD2(1-D)+log5-0.8log2+log(1-D) =log5-(D+0.8)log2-H(D,1-D)(D≤0.4) 因而 R（D）=0.15(bit)，D=0.4 R(0)=1.522(bit)，D=0 若D>0.4，则es>13。因为必须有q2=0，所以q0=q1=12。由∑jqjesdij=1λ，求得 λ0=λ1=21+es,λ2=1es 所以 D(S)=0.2+es1+eses=D-0.21-D R(S)=SD+0.8log21+es+0.2log1es =(D-0.2)log(D-0.2)+(1-D)log(1-D)-0.8log0.4 这里0.4≤D≤0.6。当D=0.6时，R（D）=0。 (2) 当信道容量为1bit时，R（D）=1，反求得D=Pe=0.0885。 当信道容量为0.1bit时，R（D）=0.1，反求得D=Pe=0.436。■