第11讲――离散无记忆信道的容量

离散无记忆信道的容量第十一讲信道容量kaXjbY)(kjp)},({maxYXICkQ信道容量);(YXIN21,x,,xxN1yyy,,,2)|(xyNp)|()|()|(2211NNxypxypxyp),,,|,,,()|(22N1N1Nxxxyyyppxy离散无记忆Review达到C充要条件输入概率矢量KQQQQ,,,10达到转移概率为)(kjp的DMC的容量C的充要条件为CYkxI);(0,kQkCYkxI);(0,kQk其中，iijijpQkjpkjpYkxI)()(log)();(Review定理3对于准对称DMC信道（1）达到信道容量的最佳输入分布为等概分布；（2）信道容量为kYkXIijpKkjpkjpCJjKi；);()|(1)|(log)|(1010准对称信道的容量最佳输入分布为等概分布kYkXIijpKkjpkjpCJjKi；);()|(1)|(log)|(1010Review准对称DMC信道准对称信道容量计算公式101010)(1)(log)()(log)();(JjKiJjjijpKkjpkjpwkjpkjpYkxIC对称DMC信道10)(log)(logJjkjpkjpJC例KSC信道pKpKpKpKpKpKppP11111111其中0p1。称p为错误概率。特别当K=2时，记为BSCppppP11例KSC信道容量对称信道最佳输入分布为等概分布当输入等概时，输出分布也为等概信道容量)()1log(log)1(log)1()1()1log()1(logpHKpKKpKpKppKC)(12pHCK时：当例KSC信道容量pKpKpKpKpKpKppP1111111110)(log)(logJjkjpkjpJC例二元删除信道容量例：二元删除信道输入事件集为{0,1}；输出事件集为{0,2,1}；转移概率矩阵为qpqppqqpP1112010当q=0时，简化为BSC。当p=0时，简化为纯删除信道。达到信道容量时的最佳输入分布为等概分布。信道容量是转移概率矩阵任何一行所对应的半平均互信息量。它为准对称信道，达到C的分布为等概分布，即2/110QQ10)1(2121)1(21wqpqpwqqqw21212YXIYXI;1;0)1(21loglog)1(21)1(log)1(qppqqqqqpqp21log)1(log)1log()1(qqppqpqp解：BSC(q=0)C=1-H(p)纯删除信道(p=0)C=1-q例二元删除信道容量DMC的输入为X，X的所有事件为{0,1,…,K-1}；DMC的噪声为Z，Z的所有事件为{0,1,…,K-1}；DMC的输出为Y，Y的所有事件为{0,1,…,K-1}；X与Z相互独立；Y=X+Z(modK)。例模K加性噪声信道+XxZz)(xQ)(zpYzxy)(yw输入输出干扰求信道容量C若记P(Z=z)=sz，则转移概率矩阵为0321301221011210ssssssssssssssssKKKKKK例模K加性信道容量显然，模K加性噪声信道是对称DMC，则信道容量为)(logloglog10ZHKssKCkKkkp(y|x)=P(Y=y|X=x)=P(X+Z(modK)=y|X=x)=P(x+Z(modK)=y|X=x)=P(Z=y-x(modK)|X=x)=P(Z=y-x(modK))。假定所有输入字母的概率kQ，则kkjkjpQw)(1,,1,0Jj由CwkjpkjpYkxIjj)(log)();(1,,1,0Kk可得Cwkjpkjpkjpjjjlog)()(log)(即]log[)()(log)(jjjwCkjpkjpkjp可逆矩阵信道容量j令jjwClog，得jjjkjpkjpkjp)(log)()(1,,1,0Kk可以看成是有J个未知数的线性方程组。由假设P是非奇异矩阵，故必有唯一解。j令j是其解，由上假设jjCCjw222又1jjw，可得)2log(jjC可逆矩阵信道容量jjwClog0kQ对上面得到的解进行验证。特别注意可逆矩阵信道容量计算wjCjjw2计算Qk求解方程组验证0kQ若即所得到的解是正确的否则满足条件的最大值在边界上，于是kQ令某个为0，再次进行试解。kkjkjpQw)(可逆矩阵信道容量jjjkjpkjpkjp)(log)()(1,,1,0Kk)2log(jjCCjjw2kkjkjpQw)(列方程组计算信道容量验证0kQ对上面得到的解进行验证。特别注意可逆矩阵信道容量计算wjCjjw2计算Qk求解方程组验证0kQ若即所得到的解是正确的否则满足条件的最大值在边界上，于是kQ令某个为0，再次进行试解。KJ多解有时要令多个kQ为0，进行试解特别kkjkjpQw)(例题DMC信道的转移概率矩阵为2/14/104/1010000104/104/12/1P求其信道容量C。非奇异矩阵例题2/14/104/1010000104/104/12/1P根据jjjkjpkjpkjp)(log)()(列方程组21log2141log4141log412141410041log4141log4121log2141412143132421得241032从而)2log(jjC15log例题验证jjCCjw222，求得1012411wwC522322wwC再根据kkjkjpQw)(，得到方程组101214152415241101412141432141QQQQQQQQ可得30441QQ301132QQ经验证0kQ，因此结果正确15logC最佳分布为30441QQ301132QQ根据2/14/104/1010000104/104/12/1PN次扩展信道容量信道1,,2,1,0KXxnn1,,2,1,0JYynn)(N21,x,,xx),,,(2N1yyy)|(xyNpNXNY)|(nnxypNCYXIYXINnnnNN1);();(有：【定理】：DMC)()(2121NNNNXXXYYYHXYH)(log)(111111NNyyxxNNxxyypyyxxpNNNnnnXYH1)(无记忆信道)()(21NNYYYHYH)()(121YYHYH)(121NNYYYYHNnnYH1)(证明注：等号成立条件)()()(log)(221111NNNNxypxypxypyyxxp)(log)(1111xypyyxxpNN)()(2121NNNNXXXYYYHXYH)(log)(111111NNyyxxNNxxyypyyxxpNNNnnnXYH1)(无记忆信道)()(21NNYYYHYH)()(121YYHYH)(121NNYYYYHNnnYH1)(证明注：等号成立条件)()()(log)(221111NNNNxypxypxypyyxxp)(log)(1111xypyyxxpNNNnnnnNNNNNXYHYHXYHYHYXI1)()()()();(NnnnYXI1);(注：当输入字母序列中各字母统计独立时，等号成立。CYXInn);(NCCYXINnNN1);(由信道容量的定义知，对于任意n，有注：若对每个n，输入分布可使极大，则有，从而等式成立。)(nxQ);(nnYXICYXInn);(DMC，有问题：对有记忆信道上式是否成立？NCYXIYXINnnnNN1);();(例：模2加性噪声信道考虑满足的二元对称信道，其中表示模2加法运算，并且假设具有分布但不一定相互独立。假设Zn与输入Xn相互独立，C=1-H(p).则有：iiiZXYNCYYYXXXINNxxxpN)...;...(max2121),...,,(21}1,0{,iiYXiZ,1)0Pr(,)1Pr(pZpZiiniZZZ,...,21该结论的证明，用到互信息的当（信道无记忆）时，有当（信源无记忆）时，有当信源和信道都是无记忆时，有之间的关系：与);();(iiNNYXIYXINnnnNNYXIYXI1);();(NnnnNNYXIYXI1);();(niiixypp1)/()/(xyniixpp1)()(xNnnnNNYXIYXI1);();(证明：假设信源无记忆，有因此，有NnnnNNYXIYXI1);();(Niixpp1)()(xCpHZHYHYXIiixpiixpii)(1)]()([max);(max)()(NnnnxpNNxxxpYXIYXInN1)(),...,,();(max);(max21NnnnNNYXIYXI1);();(NCYXINNxxxpN);(max),...,,(21信道1)(11xyp1X1Y信道2)(22xyp2X2Y信道N)(NNxypNXNY组合信道若信道1和信道2同时传送信息，则组合信道的输入集由所有的有序对组成，其中)',(kk1Xk2'Xk输出集由所有的有序对组成，其中)',(jj1Yj2'Yj)''()()''(kjpkjpkkjjp转移概率，称这样组成的信道为信道1和信道2的独立并行信道或积信道。信道1和信道2称作积信道的分信道。信道1kaX1jbY1)(kjp信道2'2kaX'2jbY)''(kjp积信道定理独立并行信道的容量C为各分信道容量之和21CCC证明：);();(2121YYXXIYXI'')'()''(log)''(kkjjjjwkkjjpjjkkp'')'()''()(log)''(kkjjjjwkjpkjpjjkkpkjjwkjpkjpYXI)(log)();(11'')(log)''(kkjjjwkjpjjkkp'''22)''(log)''();(kjjwkjpjkpYXI''')''(log)''(kkjjjwkjpjjkkp);();();(22112121YXIYXIYYXXI''')'(log)''(kkjjjjjj'')'(log)'(jjjjjj]1)'()['()(log''jjjjjj特别注意')'(jjwwjjw时等号成立。条件下，相当于要求)''()()''(kjpkjpkkjjp')'(kkQQkkQ即要求两个分信道的输入彼此独立。这样对于积信道的最佳利用是将两个信道独立地使用，并使每个分信道的输入分布为最佳，就能保证到达信道容量。推论（N个独立信道构成的并行信道）设每个分信道的输入空间、输出空间和转移概率分布相应为Xn，Yn和Pn，则合成的积信道的输入、输出空间及转移概率分布和容量分