所以当n足够大时可以使 exp{?M2将上式代入式（7——21）中，得
?n[R(D)??]}??dmax
dn(B)?D???dmax[?p(xi)??i?1i?1NNp(xi)]??p(xi)?q(yj|xi)]?dmax[?dmaxi?1yj?Ui?VIjN?D?2??dmax[1??（7——22） 令U?N
i?1yj?Ui?p(x)q(yi|xi)]?VI?si?1Ni，V??Vi?1Ni,则有
1??Ni?1yj?Ui?p(x)q(yij|xi)??VI （7——23）
1?p(U?V)?p(U?V)?P(U)?P(V)因为信源是无记忆的，所以有
np(xiyj)??p(xik)q(yjk|xik)
k?1如果选择q(yj|xi)为 q(yj|xi)??q(yk?1njk|xik)
则随机变量d(xik,yjk)，k?1,2,?,n是独立同分布的，其算数平均值dn(xi,yj)为
1n dn(xi,yj)??d(xik,yjk)
nk?1由弱大数定理可知，dn(xi,yj)依概率收敛于d(xik,yjk)的均值E[d]为
1nNM E[d]??[??p(xiyj)d(xik,yjk)]?D
nk?1i?1j?1即dn(xi,yj)依概率收敛于D，而
U?{(xi,yj):dn(xi,yj)?D??} 所以
limp(U)?0 （7——24）
n??如果选择q(yj)为p(yj|xi)的边沿分布，则
q(yj)??p(xi)q(yj|xi)?i?1N??p(x
i?1k?1nNk?1ni?1Nnik)q(yjk|xik)?
?[?p(x?q(yk?1jkik)q(yjk|xik)]?)所以令码字中的每个符号都是相互独立的。 令
1q(yj|xi)In(xi,yj)?lb?nq(yj)q(yjk|xik)1n ?lb?nk?1q(yjk)1nIn(xi,yj)?nk?1由弱大数定理可知，In(xi,yj)依概率收敛于I(xik,yjk)的均值E[I]为
q(yjk|xik)1nNM E[I]??[??p(xiyj)lb]?R(D)
nk?1i?1j?1q(yjk)即In(xi,yj)依概率收敛于R(D),而
??1q(yj|xi)???R(D)??? V??(xi,yj):lbnq(yj)????所以
limp(V)?0 （7——25）
n??由式（7——24）和式（7——25）可得，当n足够大时，可满足
p(U)?
?dmaxp(V)??dmax
将上式和式（7——23）代入式（7——22）中得
dn(B)?D?2??dmax?如果选取??4?，则
dn(B)?D??
???????D?4? （7——26） ?dmaxdmax?即当n足够大时，分组编码满足保真度准则(D??)，码数目M为 M?2分组码B的速率R为 R?n[R(D)??]?2n[R(D)??/2]?2n[R(D)??]
11lbM?lb{2n[R(D)??]}?R(D)?? (7——27) nn由式（7——26）和式（7——27）可得，当n足够大时，存在分组码B?(M,n)，满足保真度准则(D??),且速率R?R(D)??。 7.3.2 限失真信源编码逆定理
定理 7.3.2 限失真信源编码逆定理 设离散n长序列无记忆信源为
x2?xN??X??x1 ?????
Pp(x)p(x)?p(x)???12N?单字符失真函数d(xik,yjk)，给定单字符失真度下的信息失真函数为R(D),则所有满足保真度准则D的信源编码得速率都不小于D，即
1lbM(n,D)?R(D) n证明：设B?[y1y2?yM]是允许码，且使平均失真度d(xi,yj)最小的平均交互信息量为
I(xi;yj)，对于编码，I(xi;yj)为
I(xi;yj)?H(yj)?ibM （7——28） 因为
I(xi;yj)?H(xi)?H(xi|yj) 所以
I(xi;yj)?H(xi)?H(xi1.,xi2,?,xin|yj1,yj2?,yjn) （7——29） 其中
H(xi1.,xi2,?,xin|yj1,yj2?,yjn)?
?H(xk?1nnik|yj1,yj2?,yjn)?|yjk)
?H(xk?1ik对于离散无记忆信源有 H(xi)??H(xnik) （7——30）
k?1由式（7——29）和（7——30）可得 nn
?H(xik)?I(xi;yj)?lbMk?1?H(xik,yjk)?k?1设Dk是对xik编码产生的平均失真度，则
R(DK)?I(xik;yjk)?H(xik)?H(xik|yjk) 由R(D)的下凸性可知
1n?nR(D(1n k)?R?1n?Dk) kk?1由式（7——31）、（7——32）和（7——33），得
1n1n?nR(Dk)??R(Dk)?k?1nk?1 1n?n[H(xik)?H(xik|yjk)]? k?11nlbM因为B设为满足保真度准则D的允许码，所以
1nn?Dk?D
k?1由R(D)的单调递减性得
R(D)?R(1n?nD?1k)lbM
k?1n在允许码B中选择码数目最少的码M(n,D)，则
1nlbM(n,D)?R(D) （7——31）
（7——32） （7——33）
（7——34）
由定理7.3.1和定理7.3.2可以得出，对于任意的D?0,允许码M(n,D)有 lim1lbM(n,D)?R(D) n??n即对于任意D?0，R(D)是允许码的可能的最小速率，为了达到这个速度，需要增大码长
n和增加码数目M。
7.4 信息率失真的函数的计算
已知信源的概率分布p(x)和失真函数d(x,y)，就可以确定信源的信息率失真函数
R(D),它是在约束条件，即保真度准则下，求极小值问题，一般情况下难于求的闭式解，
常采用参量表示法，或采用迭代算法求解。 7.4.1 R(D)参量表示法求解 设离散信源的输入序列为 ?输出序列为 ????x2?xn??X??x1???p(x)p(x)?p(x)? P???12n??y1?p(y1)y2? ?p(y2)?p(ym)??yn?Y??P?字符传输的失真函数为d(xi,yj)，i?1,2,?,n；j?1,2,?,m。为了方便书写，引入记号：
dij?d(xi,yj)，pij?p(yj|xi) pi?p(xi)，qj?p(yj) 式中
p(yj)??p(x)p(yii?1nj|xi)??pipij
i?1n信息率失真函数R(D)的计算为在约束条件
?nm???pipijdij?D?i?1j?1(i?1,2,?,n) （7——35） ?m?p?1?ij?j?1?下，求