Ch2例题与证明三

失散平稳无记忆信源X的N次扩展信源的熵为失散信源X的熵的N倍。H(XN)NH(X)证明：H(XN)P(X)log2P(X)p(i)log2p(i)XNXN求和是对信源XN中所有nN个元素求和，可以等效成N个求和，而其中的每一个又是对X中的n个元素求和，所以有：nnnp(ai)p(xi)p(xi2)p(xi)XN1Ni11i21iN1nnnp(xi)p(xi2)p(xi)11Ni11i21iN1则H(XN)p(i)log2[p(x)p(xi)Lp(xi)]i2NXN1p(i)log2p(xi1)p(i)log2p(xi2)...XNXNp(i)log2p(xiN)XN共有N项，察看其中第一项p(i)log2p(xi)p(xi)p(xi2)Lp(xiN)log2p(xi)XN1XN11nnnp(xi1)log2p(xi1)[p(xi2)Lp(xiN)]i11i21iN1n由于p(xik)1k1,2,Nik1n所以p(i)log2p(xi1)p(xi1)log2p(xi1)H(X)XNi11同理其余各项均等于H(X)故有：H(XN)NH(X)证毕。[例]有一失散平稳无记忆信源Xx1,x2,x33P(X)111p(xi)1，求此信源的二次扩展2,,4i14信源X2的熵。先求出此失散平稳无记忆信源的二次扩展信源。扩展信源的每个元素是信源X的输出长度为2的信息序列。由于扩展信源是无记忆的，故p(ai)p(xi1)p(xi2)(i1,i21,2,3;i1,2,,9)X2信源的元素a1a2a3a4a5a6a7a8a9对应的信息序列x1x1x1x2x1x3x2x1x2x2x2x3x3x1x3x2x3x3概率p(ai)1111111114888161681616依照熵的定义，二次扩展信源的熵为H(X2)H(X1X2)H(1/16,1/8,1/16,1/8,1/4,1/8,1/16,1/8,1/16)3(bit/symbol)2H(X)2H(1/4,1/2,1/4)结论：计算扩展信源的熵时，不用构造新的信源，可直接从原信源X的熵导出。即失散平稳无记忆信源X的N次扩展信源的熵为失散信源X的熵的N倍。思虑据明二维失散有记忆信源的熵不大于二维平稳无记忆信源的熵？H(X1X2)H(X1)H(X2)[例]设某二维失散信源X=X1X2的原始信源X的信源模型为Xx1x2x31411，X=X1X2中前后两个符号的条件P(X)4936概率为X2P(X2/X1)x1x2x3X1x17/92/90x21/83/41/8x302/119/11原始信源的熵为：3H(X)p(xi)log2p(xi)1.542(bit/symbol)i1由条件概率确定的条件熵为：33H(X2/X1)p(xi1)p(xi2/xi1)log2p(xi2/xi1)0.870(bit/symbol)i11i21条件熵比信源熵（无条件熵）减少了symbol,正是由于符号之间的依赖性所造成的。信源X=X1X2平均每发一个信息所能供应的信息量，即联合熵H(X1X2)H(X1)H(X2/X1)2.412(bit/symbol)则每一个信源符号所供应的平均信息量1H2(X)H(X1X2)1.206(bit/symbol)2小于信源X所供应的平均信息量H(X)，这同样是由于符号之间的统计相关性所引起的。将二维失散平稳有记忆信源实行到N维情况，可证H(X)H(X1X2XN)H(X1)H(X2/X1)H(X3/X1X2)H(XN/X1X2XN1)证明：H(X)H(X1X2XN)令Y1X1X2XN1,Y2X1X2XN2,YN2X1X2则H(X)H(Y1XN)H(Y1)H(XN/Y1)H(X1X2XN1)H(XN/X1X2XN1)H(Y2)H(XN1/Y2)H(XN/X1X2XN1)LH(YN2)H(X3/YN2)LH(XN/X1X2LXN1)H(X1X2)H(X3/X1X2)LH(XN/X1X2LXN1)H(X1)H(X2/X1)H(X3/X1X2)LH(XN/X1X2LXN1)H(X1)H(X2)H(X3)LH(XN)表示：多符号失散平稳有记忆信源X的熵H(X)是X中初步时刻随机变量X1的熵与各阶条件熵之和。证明失散平稳信源条件熵随变量数N增大而减小的非递加性，即H(XN|X1X2...XN1)H(XN1|X1X2...XN2)由信源熵不等式qPilogPii1qq其中P1;P'1;iii1i1令PiP(xN|x1x2...xN代入上式不等式

qPilogPi'i11)，Pi'P(xN1|x1x2...xN2)P(xN|x1x2...xN1)logP(xN|x1x2...xN1)XNP(xN|x1x2...xN1)logP(xN1|x1x2...xN2)XN两边乘上P(x1x2...xN1)P(x1x2...xN1xN)logP(xN|x1x2...xN1)XNP(x1x2...xN1xN)logP(xN1|x1x2...xN2)XN两边对x1x2...xN1求和...P(x1x2...xN1xN)logP(xN|x1x2...xN1)X1X2XN...P(x1x2...xN1xN)logP(xN1|x1x2...xN2)X1X2XN...P(x1x2...xN1)logP(xN1|x1x2...xN2)X1X2XN1即H(XN|X1X2...XN1)H(XN1|X1X2...XN2)等号在P(xN|x1x2...xN1)P(xN1|x1x2...xN2)（对所有x1x2...xN都满足）时成立。证明平均符号熵大于条件熵，即HNH(XN|X1X2...XN1)依照平均符号熵的定义HN(X)1H(X1,X2,...,XN)N1{H(X1)H(X2|X1)H(X3|X1X2)...NH(XN|X1,X2,...,XN1)}NH(XN|X1,X2,...,XN1)NH(XN|X1,X2,...,XN1)证明平均符号熵随N单调下降rNNHN(X)H(X1,X2,...,XN)p(ai)logp(ai)i1r...rp(ai1ai2...aiN)logp(ai1ai2...aiN)i11iN1r...rp(ai1ai2...aiN)log{p(ai1ai2...aiN1)p(aiN|ai1ai2...aiN1)}i11iN1r...rp(ai1ai2...aiN1)logp(ai1ai2...aiN1)i11iN11rr...p(ai1ai2...aiN)log