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

1、 信道容量信道容量),(maxYXICkQ信道容量信道容量);(YXI)|()|()|(2211NNxypxypxyp),|,()|(22N1N1Nxxxyyyppxy离散无记忆离散无记忆Review达到达到C充要条件充要条件输入概率矢量输入概率矢量KQQQQ,10达到转移概率为达到转移概率为)( kjp的的DMC的容量的容量C的充要条件为的充要条件为CYkxI);(0,kQkCYkxI);(0,kQk其中，其中，iiji jpQkjpkjpYkxI)()(log)();(Review定理定理3 对于准对称对于准对称DMC信道信道（1）达到信道容量的最佳输入分布为等概分布；）达到信道容量的最佳

2、输入分布为等概分布；（2）信道容量为）信道容量为kYkXIijpKkjpkjpCJjKi；);()|(1)|(log)|(1010准对称信道的容量准对称信道的容量最佳输入分布为等概分布最佳输入分布为等概分布kYkXIijpKkjpkjpCJjKi；);()|(1)|(log)|(1010Review准对称准对称DMC信道信道准对称信道容量计算公式准对称信道容量计算公式101010)(1)(log)()(log)();(JjKiJjji jpKkjpkjpwkjpkjpYkxIC对称对称DMC信道信道10)(log)(logJjkjpkjpJC 例例 KSC信道信道pKpKpKpKpKpKppP

3、11111111其中其中0p1。称称p为错误概率。为错误概率。特别当特别当K=2时，记时，记为为BSCppppP11例例 KSC信道容量信道容量l 对称信道对称信道l 最佳输入分布为等概分布最佳输入分布为等概分布l 当输入等概时，输出分布当输入等概时，输出分布 也为等概也为等概l 信道容量信道容量)() 1log(log) 1(log) 1() 1()1log()1 (logpHKpKKpKpKppKC)(12pHCK 时：当例例 KSC信道容量信道容量pKpKpKpKpKpKppP1111111110)(log)(logJjkjpkjpJC例例 二元删除信道容量二元删除信道容量例：二元删除信

4、道例：二元删除信道输入事件集为输入事件集为0,1；输出事；输出事件集为件集为0,2,1；转移概率矩阵；转移概率矩阵为为qpqppqqpP1112010当当q=0时，简化为时，简化为BSC。当当p=0时，简化为纯删除信道。时，简化为纯删除信道。达到信道容量时的最佳输入分达到信道容量时的最佳输入分布为等概分布。布为等概分布。信道容量是转移概率矩阵任何信道容量是转移概率矩阵任何一行所对应的半平均互信息量。一行所对应的半平均互信息量。它为准对称信道，它为准对称信道， 达到达到C的分布为等概分布，即的分布为等概分布，即2/110 QQ10)1 (2121)1 (21wqpqpwqqqw21212YXIY

5、XI; 1; 0)1 (21loglog)1 (21)1 (log)1 (qppqqqqqpqp21log)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加性噪声信道加性噪声信道+X

6、xZz)(xQ)(zpYzxy)(yw输入输出干扰求信道容量求信道容量C若记若记P(Z=z)=sz，则转移概率矩，则转移概率矩阵为阵为0321301221011210ssssssssssssssssKKKKKK例例 模模K加性信道容量加性信道容量显然，模显然，模K加性噪声信道是对称加性噪声信道是对称DMC，则信道容量为，则信道容量为)(logloglog10ZHKssKCkKkkp(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)。假定所有输入字母的概率假定所有输

7、入字母的概率kQ，则，则kkjkjpQw)( 1, 1 , 0Jj由由CwkjpkjpYkxIjj)(log)();( 1, 1 , 0Kk可得可得Cwkjpkjpkjpjjjlog)()(log)(即即log )()(log)(jjjwCkjpkjpkjp 可逆矩阵信道容量可逆矩阵信道容量j令令jjwClog，得，得 jjjkjpkjpkjp)(log)()(1, 1 , 0Kk可以看成是有可以看成是有J个未知数个未知数 的线性方程组。由假设的线性方程组。由假设P是是非奇异矩阵，故必有唯一解。非奇异矩阵，故必有唯一解。j令令 j是其解，由上假设是其解，由上假设jjCCjw222又又1jjw，

8、可得，可得)2log(jjC可逆矩阵信道容量可逆矩阵信道容量jjwClog0kQ对上面得到的解进行验证。对上面得到的解进行验证。 特别注意特别注意可逆矩阵信道容量可逆矩阵信道容量计算计算wjCjjw2计算计算Qk求解方程组求解方程组验证验证0kQ 若若 即所得到的解是正确的即所得到的解是正确的否则满足条件的最大值在边界上，于是否则满足条件的最大值在边界上，于是kQ令某个令某个为为0， 再次进行试解。再次进行试解。kkjkjpQw)(可逆矩阵信道容量可逆矩阵信道容量jjjkjpkjpkjp)(log)()(1, 1 , 0Kk)2log(jjCCjjw2kkjkjpQw)(列方程组列方程组计算信

9、道容量计算信道容量验证验证0kQ对上面得到的解进行验证。对上面得到的解进行验证。 特别注意特别注意可逆矩阵信道容量可逆矩阵信道容量计算计算wjCjjw2计算计算Qk求解方程组求解方程组验证验证0kQ 若若 即所得到的解是正确的即所得到的解是正确的否则满足条件的最大值在边界上，于是否则满足条件的最大值在边界上，于是kQ令某个令某个为为0， 再次进行试解。再次进行试解。KJ 多解多解有时要令多个有时要令多个kQ为为0，进行试解，进行试解特别特别kkjkjpQw)(例例 题题DMC信道的转移概率矩阵为信道的转移概率矩阵为 2/14/104/1010000104/104/12/1P求其信道容量求其信道

10、容量C。非奇异矩阵非奇异矩阵 例例 题题2/14/104/1010000104/104/12/1P根据根据jjjkjpkjpkjp)(log)()(列方程组列方程组21log2141log4141log412141410041log4141log4121log2141412143132421得得241 032 从而从而 )2log(jjC15log例例 题题验证验证jjCCjw222，求得，求得1012411wwC 522322wwC再根据再根据kkjkjpQw)(，得到方程组，得到方程组101214152415241101412141432141QQQQQQQQ 可得可得 30441 QQ3

11、01132 QQ经验证经验证0kQ，因此结果正确，因此结果正确15log C最佳分布为最佳分布为30441 QQ301132 QQ根据根据2/14/104/1010000104/104/12/1PN次扩展信道容量次扩展信道容量NCYXIYXINnnnNN1);();(有：有：【定理定理】：DMC)()(2121NNNNXXXYYYHXYH)(log)(111111NNyyxxNNxxyypyyxxpNN NnnnXYH1)(无记忆信道无记忆信道)()(21NNYYYHYH)()(121YYHYH)(121NNYYYYH NnnYH1)(证明证明注：等号成立条件注：等号成立条件 )()()(lo

12、g)(221111NNNNxypxypxypyyxxp)(log)(1111xypyyxxpNN)()(2121NNNNXXXYYYHXYH)(log)(111111NNyyxxNNxxyypyyxxpNN NnnnXYH1)(无记忆信道无记忆信道)()(21NNYYYHYH)()(121YYHYH)(121NNYYYYH NnnYH1)(证明证明注：等号成立条件注：等号成立条件 )()()(log)(221111NNNNxypxypxypyyxxp)(log)(1111xypyyxxpNNNnnnnNNNNNXYHYHXYHYHYXI1)()()()();(NnnnYXI1);(注：当输入字

13、母序列中各字母统计独立时，等号成立。注：当输入字母序列中各字母统计独立时，等号成立。 CYXInn);(NCCYXINnNN1);(由信道容量的定义知，对于任意由信道容量的定义知，对于任意n，有，有注：若对每个注：若对每个n，输入分布，输入分布 可使可使 极大极大，则有，则有 ，从而等式成立。，从而等式成立。)(nxQ);(nnYXICYXInn);(DMC，有问题：对有记忆信道上式是否成立？NCYXIYXINnnnNN1);();(例：例： 模模2加性噪声信道加性噪声信道考虑满足的考虑满足的 二元对称信道，其中二元对称信道，其中 表示模表示模2加法运算，并且加法运算，并且假设假设 具有分布具

14、有分布 但但不一定相互独立。假设不一定相互独立。假设Zn与输入与输入Xn相互独立，相互独立，C=1-H(p).则有：则有：iiiZXYNCYYYXXXINNxxxpN).;.(max2121),.,(211 , 0,iiYXiZ,1)0Pr(,) 1Pr(pZpZiiniZZZ,.,21该结论的证明，用到互信息的当 （信道无记忆）时，有当 （信源无记忆）时，有当信源和信道都是无记忆时，有之间的关系：与);();(iiNNYXIYXINnnnNNYXIYXI1);();(NnnnNNYXIYXI1);();(niiixypp1)/()/(xyniixpp1)()(xNnnnNNYXIYXI1);

15、();(证明：假设信源无记忆，有因此，有NnnnNNYXIYXI1);();(Niixpp1)()(xCpHZHYHYXIiixpiixpii)(1)()(max);(max)()(NnnnxpNNxxxpYXIYXInN1)(),.,();(max);(max21NnnnNNYXIYXI1);();(NCYXINNxxxpN);(max),.,(21组合信道组合信道若信道若信道1和信道和信道2同时同时传送信息，则组合信道的输入集传送信息，则组合信道的输入集由所有的有序对由所有的有序对 组成，其中组成，其中) ,(kk1Xk2Xk 输出集由所有的有序对输出集由所有的有序对 组成，其中组成，其中

16、) ,(jj1Yj2 Yj) ()() (kjpkjpkkjjp转移概率转移概率 ，称这样组成的信道，称这样组成的信道为信道为信道1和信道和信道2的的独立并行信道独立并行信道或或积信道积信道。信道。信道1和信和信道道2称作积信道的分信道。称作积信道的分信道。信道1 kaX 1 jbY 1)( kjp积信道积信道定理定理 独立并行信道的容量独立并行信道的容量C为各分信道容量之和为各分信道容量之和21CCC证明：证明：);();(2121YYXXIYXI) () (log) (kkjjjjwkkjjpjjkkp) () ()(log) (kkjjjjwkjpkjpjjkkpkjjwkjpkjpYX

17、I)(log)();(11)(log) (kkjjjwkjpjjkkp22) (log) ();(kjjwkjpjkpYXI) (log) (kkjjjwkjpjjkkp );();();(22112121YXIYXIYYXXI) (log) (kkjjjjjjwwwjjkkp) (log) (jjjjjjwwwjjw0 1) ()()(logjjjjjjwwwjjwe由此得由此得12CCC特别注意特别注意) (jjwwjjw时等号成立。时等号成立。 条件下，相当于要求条件下，相当于要求) ()() (kjpkjpkkjjp) (kkQQkkQ即要求两个分信道的输入彼此独立。这样对于积信道的即

18、要求两个分信道的输入彼此独立。这样对于积信道的最佳利用是将两个信道独立地使用，并使每个分信道的最佳利用是将两个信道独立地使用，并使每个分信道的输入分布为最佳，就能保证到达信道容量。输入分布为最佳，就能保证到达信道容量。 推论（推论（N个独立信道构成的并行信道）个独立信道构成的并行信道）设每个分信道的输入空间、输出空间和转移概率分设每个分信道的输入空间、输出空间和转移概率分 布相应为布相应为Xn，Yn和和Pn，则合成的积信道的输入、输，则合成的积信道的输入、输出空间及转移概率分布和容量分别为出空间及转移概率分布和容量分别为NnnXX1NnnYY1NnnPP1和和NnnCC1【例例】DMC的的N次

19、扩展信道次扩展信道积信道积信道若任一单位时间可随机地选用信道若任一单位时间可随机地选用信道1或信道或信道2中的一个（中的一个（两者不能同时选用两者不能同时选用）。选用信道）。选用信道1的概率为的概率为p1，选用信道，选用信道2的概率为的概率为p2,且且p1+p2=1。组合信道的输入空间为。组合信道的输入空间为称此组合信道为和信道，或称作并信道。称此组合信道为和信道，或称作并信道。21XXX输出空间为输出空间为 ，转移概率分布为，转移概率分布为21YYY2121Y j ,Y,Xk,Xk: ) (),(jkjpkjp和信道和信道信道1 kaX 1 jbY 1)( kjp【例例】ppppP111 q

20、qqqP10012此时和信道的转移概率矩阵为此时和信道的转移概率矩阵为qqqqppppPPP100001000001000121)()(21)|(00)|(MJNKMNJKuvpxyp和信道的互信息为和信道的互信息为, 22,11) (log) ()(log)();(jkjkjkjkwpkjpkjpQpwpkjpkjpQpYXI, 2,1) (log) ()(log)(jkjkjkjkwkjpkjpQpwkjpkjpQp2211loglogpppp)();();(222111PHpYXIpYXI其中其中2211loglog)(ppppHP定理定理 信道信道1和信道和信道2的和信道的容量的和信道

21、的容量C满足满足21222CCC证明：证明：)();(max);(maxmax);(max222111,PHpYXIpYXIYXICQQPQQP)(max2211PHCpCpP)1(12pp)1log()1 (log)1 (max11112111ppppCPCpP令令epepCCdpYXdIlog)1log(loglog);(11211 0loglog2121ppCC所以所以 2211loglogpCpC解之解之 121cp222cp又又 ,则则 121 pp21222cc或或22log21cc回代回代 入关系式入关系式2211loglogpCpC)(2211PHCpCpC则则21222CCC

22、可得可得 )(loglog2211PHppppC21pp121cp222cpccp121ccp222推论（推论（N个独立信道的和信道）个独立信道的和信道）若各分信道的输入、输出空间、转移概率和容量分别为若各分信道的输入、输出空间、转移概率和容量分别为Xn，Yn和和Pn和和Cn，则和信道的信道容量为，则和信道的信道容量为NnCnC12log每个信道被利用的概率为每个信道被利用的概率为CCnnp 2和信道和信道【例例】求解信道求解信道 的容量的容量C 1000101ppppP解解和信道和信道ppppP111 12P)(11phC02C12log)(12pHC12/22)(1)(111pHpHCCp

23、121pp最佳分布最佳分布11021pQQ22pQ 若将信道若将信道1的输出作为信道的输出作为信道2的输入，信道的输入，信道1的输入的输入集就是组合信道的输入集，信道集就是组合信道的输入集，信道2的输出集就是组的输出集就是组合信道的输出集。称这样组成的信道为级联信道，合信道的输出集。称这样组成的信道为级联信道，又称串行信道。又称串行信道。信道1 kaX 1 jbY 1)( kjp 级联信道级联信道转移概率转移概率jjkjpkjpkjp)()()(将信道将信道1与信道与信道2级联，组成级联信道，求其信道容级联，组成级联信道，求其信道容量和最佳输入分布。量和最佳输入分布。100.250.750.80.201信道信道1信道信道2100.250.750.80.200.8BSC信道信道，C=1-H(0.2)，最佳分布为等概分布。，最佳分布为等概分布。级联信道级联信