信息理论基础(3)

所以当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?下，求

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库信息理论基础(3)在线全文阅读。