第13讲――离散无记忆信道的容量(1)

离散无记忆信道的容量离散无记忆信道离散无记忆信道的容量的容量第十三讲第十三讲信道容量{}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信道容量计算•对于一般信道,信道容量计算相当复杂,我们只讨论某些特殊类型的信道•几种特殊类型的信道－无噪无损信道－有噪无损信道－无噪有损信道－对称、准对称信道Review【定理】准对称DMC的最佳分布为等概分布。【准对称信道容量公式】∑−=====10)(log)();();(JjjwkjpkjpYkxIYXIC∑∑−=−==1010)(1)(log)(JjKiijpKkjpkjp∑−=+=10)(log)(logJjkjpkjpJC准对称信道容量计算Review例KSC信道⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡−−−−−−−−=pKpKpKpKpKpKppP11111111其中0p1。称p为错误概率。特别当K=2时，记为BSC⎥⎦⎤⎢⎣⎡−−=ppppP11例KSC信道容量z对称信道z最佳输入分布为等概分布z当输入等概时，输出分布也为等概z信道容量)()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-qDMC的输入为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+=β0kQ对上面得到的解进行验证。特别注意可逆矩阵信道容量计算wjCjjw−=β2计算Qk求解方程组0kQ若即所得到的解是正确的否则满足条件的最大值在边界上，于是kQ令某个为0，再次进行试解。验证∑=kkjkjpQw)(可逆矩阵信道容量∑∑=jjjkjpkjpkjp)(log)()(β1,,1,0−=Kk)2log(∑=jjCβCjjw−=β2∑=kkjkjpQw)(列方程组计算信道容量验证0kQ对上面得到的解进行验证。特别注意可逆矩阵信道容量计算wjCjjw−=β2计算Qk求解方程组0kQ若即所得到的解是正确的否则满足条件的最大值在边界上，于是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经验证0kQ，因此结果正确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);();(【定理】)()(2121NNNNXXXYYYHXYH=)()(1212211YXXXYHXXXYHNN+=)(12121−+NNNYYYXXXYH∑==NnnnXYH1)(无记忆信道)()(21NNYYYHYH=)()(121YYHYH+=)(121−+NNYYYYH∑=≤NnnYH1)(N次扩展信道容量证明注：当输入字母序列中各字母统计独立时，输出各字母y也相互独立，此时等号成立。)()(2121NNNNXXXYYYHXYH=)()(1212211YXXXYHXXXYHNN+=)(12121−+NNNYYYXXXYH∑==NnnnXYH1)(无记忆信道)()(21NNYYYHYH=)()(121YYHYH+=)(121−+NNYYYYH∑=≤NnnYH1)(证明N次扩展信道容量N次扩展信道容量[]∑=−≤−=NnnnnNNNNNXYHYHXYHYHYXI1)()()()();(∑==NnnnYXI1);(注：当输入字母序列中各字母统计独立时，等号成立。CYXInn≤);(NCCYXINnNN=≤∑=1);(注：若对每个n，输入分布可使极大，则有，从而等式成立。)(nxQ);(nnYXICYXInn由信道容量的定义知，对于任意n，有=);()(11xyp1X1Y)(22xyp2X2Y)(NNxypNXNY组合信道N次扩展信道容量若信道1和信道2同时传送信息，则组合信道的输入集由所有的有序对组成，其中)',(kk1Xk∈2'Xk∈输出集由所有的有序对组成，其中)',(jj1Yj∈2'Yj∈)''()()''(kjpkjpkkjjp=转移概率，称这样组成的信道为信道1和信道2的独立并行信道或积信道。信道1和信道2称作积信道的分信道。信道1{}kaX=1{}jbY=1)(kjp{}'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，则合成的积信道的输入、输出空间及转移概率分布和容量分别为∏==NnnXX1∏==NnnYY1∏==NnnPP1和∑==NnnCC1积信道【例】DMC的N次扩展信道【例】波形信道看作是时间离散的连续信道的组合若任一单位时间可随机地选用信道1或信道2中的一个（两者不能同时选用）。选用信道1的概率为p1，选用信道2的概率为p2,且p1+p2=1。组合信道的输入空间为称此组合信道为和信道，或称作并信道。21XXX∪=输出空间为，转移概率分布为21YYY∪={}2121Y'j,Y,Xk',Xk:)''(),(∈∈∈∈∀jkjpkjp和信道信道1{}kaX=1{}jbY=1)(kjp{}'2kaX={}'2jbY=)''(kjp【例】⎥⎦⎤⎢⎣⎡−−=ppppP111⎥⎦⎤⎢⎣⎡−−=qqqqP10012此时和信道的转移概率矩阵为和信道⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡−−−−=∪=qqqqppppPPP100001000001000121[][])()(21)|(00)|(MJNKMNJKuvpxyp+×+××⎥⎦⎤⎢⎣⎡和信道的互信息为∑∑+=',''2'2,11)''(log)''()(log)();(jkjkjkjkwpkjpkjpQpwpkjpkjpQpYXI∑∑+=','''2,1)''(log)''()(log)(jkjkjkjkwkjpkjpQpwkjpkjpQp2211loglogpppp−−)();();(222111PHpYXIpYXI++=其中2211loglog)(ppppH−−=P和信道定理信道1和信道2的和信道的容量C满足21222CCC+=证明：{})();(max);(maxmax);(max222'111',,PHpYXIpYXIYXICQQPQQP++=={})(max2211PHCpCpP++=)1(12pp−=∵{})1log()1(lo