信息论与信息编码第四章信道2

1、第四章信道(2)各种特殊信道的信道容量计算1.几种极限情况无噪无损信道（ X,Y一一对应）H(Y|X)=0 噪声熵H(X|Y)=0 疑义度I(X;Y)=H(X)=H(Y)输入等概率时，信道的传输能力达到信道容量C=maxI(X;Y)=logM无损信道：无输出的有噪声信道H(Y|X)0H(X|Y)=0 疑义度I(X;Y)=H(X）输入等概率时，信道的传输能力达到信道容量C=maxI(X;Y)=logMn>m无噪有损信道多个输入变成一个输出，如下图噪声熵H(Y|X)=0疑义度H(X|Y)0H(X)>H(Y)I(X,Y)=H(Y)-H(Y|X)I(X,Y)=H(X)-H(X|Y)信道容量

2、C=maxI(X;Y)=maxH(Y)=logm有噪声打印机信道信道输人以概率1/2在输出端无改变地被接收，或以概率1/2转变为下一个宇母。若输入端有26个字符。并以间隔的方式使用输入字符，那么在每次传输过程中可以毫无误差地传输其中的13个字符。因此，该信道的容量为log13比特。也可计算得到C=maxI(X;Y)=maxH(Y)-H(Y|X)=maxH(Y)-1=log26-1=log13对称DMC信道（n个输入，m个输出）对称信道转移概率矩阵中每行的元素相同，每列的元素也相同é1/ 21/ 6ù1/ 31/ 21/ 6如： é6/ù16ú和

3、ê1/ 61/ 3úê3û/13ëêêë1/ 3ú1/ 2úû则条件熵H(Y|X)=-p(xi)p(yj|xi)logp(yj|xi)ji p(yj|xi)logp(yj|xi)j=H(Y|xi)上述条件熵与信道输入符号的概率p(xi)无关信道容量为：C=maxI(X;Y)p(xi)=maxH(X)-H(X|Y)= maxH(Y)-H(Y|X)p(xi)= maxH(Y)-H(Y|X)p(xi)p(xi)求信道容量，就是求最佳分布时的最大输出熵。由离散信源最大熵定理：输出分布等概率时，

4、输出熵最大。关键是求输入如何分布时，输出等概率分布？若输入等概率分布p(xi)=1/n,则由于转移概率矩阵的列对称，所以p(yj)=p(xi)p(yj|xi) = p(yj|xi)/nii与j无关，即输出符号等概率分布。由于信道的对称性，要使输出等概率分布，输入也为等概率分布。输入符号等概率分布输出符号等概率分布需H(Y)最大因此要使I最大输入符号等概率分布输出符号等概率分布所以，对称DMC信道的容量为：mC=log2m-H(Y|xi)=log2m+pijlogpijj=1结论：对于对称的离散无信道，当输入符号等概时，达到信道容量。二元对称信道（BSC)容量：æ -ee 1-1ee&

5、#246;P = ç÷øè-=HCe )-e-e)H22信道容量仅与信道本身有关系例：信道转移概率矩阵为：P1313求其信道容量。m=4,C=log2m-H(Y|xi)=log2m+pjilogpji=2-1/3log26-2/3log23=0.0817 bit/符号3、 准对称DMC信道再进一步放松条件若P(yj/xi)不满足对称条件，但是将信道矩阵按列分割为多个子矩阵：PPP1,r若所有子阵满足对称性条件，则称P为准对称信道。例：æ1-e 1-eeeeæ1-e 1-eeee1 ö1 öM÷ = (P1

6、P2 )P = çè÷ = ç2222Me1- e -ee1- e -eM1 ø è1 ø212212显然子阵P1,P2满足对称性（行，列）准对称信道有下列定理：对于单消息、离散、准对称信道，当且仅当信道输入为等概率分布时，信道达容量值:rClog nH Y | xiNk log Mkk1i )ai )j= å p (bji和, MkMK是第k个子矩阵中列元r是不互相交的子集个数4.二元对称删除信道eeeö1-æP = çee ÷212-11e2ø1è2输

7、入集合中只有两个消息信道的输入消息集合中只有两个消息的情况信道的消息集合X中只有 和 两个消息，并设它们的概率为P( )，P( )1。根据给定的信道传输概率集合或信道矩阵，可求得各个联合概率P(和各个信宿消息的概率P( ) ,它们都以为参变量的函数)然后用公式I(X；Y)H(Y)H(Y|X)C是I(X；Y)对某个信源概率矢量P(P( ), P( )的极大值,故可用偏导为¶ I ( X ; Y )¶ a= ，0得出I(X；Y)极大值时的值，代入I(X；Y)零的方法,即CRmaxI(X；Y)max中，-0.2 ln(0.3 + 0.2a ) - 0.2 + 0.2 ln(0.5

8、 - 0.2a ) + 0.2 = 0解法二：利用准对称信道P1 = é6/ùê3ú/ëûé6/ù13é/1 3ù/1 é6/ùúú, êú,可以分解成êê3û/16ë/1 3û/1 ë6/ûëP2 = é2.ùê7.úëûé0.70.2ùé0.1ù0.7&#

9、250;,可以分解成ê0.2ê0.1úëûëû当输入等概时，达到信道容量为：rClog nH Y | xiNklog Mkk1其中n为输入符号集个数；Nk为第k个子矩阵中行元 Mk为第k个子矩阵中列元r为子集个数和；和；已知信道转移概率矩阵为0.50.30.2求其信道容量。P0.30.50.20.20.50.3分解成：0.20.30.5n=2,N1=0.5+0.3=0.8, M1=0.5+0.3=0.8r=2N2=0.2,M2=0.2+0.2=0.4rClog nH Y | xiNk log Mkk1一般离散信道容量的计算(

10、信道矩阵可逆)x)p上凸函数，故极大值存在。并且为由于p(x)要满足非负且归一化的条件，因此，求信道容量归结为求有约束极值的问题 。为了书写方便，记pi=p(x),pij= p(y|x),qj=q(y) 。现求pij在约束å iijåipp³=0I ( X ;Y ) =p plogiiq ji, j下的极值。利用拉格朗日乘子法，求函数J的极值。¶J = I ( X ;Y ) - lå piir= åi=1qp p并使其为0 并考虑到计算，jiij¶pk¶J = ¶å p pp- åq

11、log q- l å p 得：iijijjji¶p¶pi, jjikk= å pkjj log pk- å( pkj log e) - l = 0j log qj + pkjjpkjå pkjjdq= log e + l所以，有= å pi p jiilogqjj = pqijdpjiI (a ;Y ) = å p log pkj记k = 1,., nkkjqjjå pk I (ak ;Y ) = I ( X ;Y )k因为，所以C = å pk I (ak ;Y ) = log e + lk有

12、：å pijj= C Þ å pij log pij = å pij (C + log qj )logjjÞ å pij b j = å pij令b j = C + log qjlog pijjjìïb j = C + log qjÞ å2jåjb j -Cb j= 1 Þ C = logåqj2íïî= 1j= 2b j -Cqj= å pi pijiÞ pi q j一般离散信道容量的计算步骤：å

13、; pij b j = å pijlog pijb(1) 由求jjjC = log å 2b j求 C(2) 由j= 2b j -C(3) 由qj求qj= å pi pijiÞ pi qjp(4) 由求i的理解I (ak ;Y )通过信道传输的互信息I(X;Y)是I(ak;Y)的平均值,若某一个ak可传送的互信息I(ak;Y)比其他字母可传送的互信息大，可以用提高pk的办法来使总的互信息增加。但当我们提高pk时， I(x=ak;Y)必然减小，这是因为I (a ;Y ) = å p log pkj = å p logpkjå

14、p pkkjkjqjjjiiji当pk增加时，pkj就更加接近qj。因此用这样的方法反复调整输入字母的概率分布，最终必然使所有字母的I(x=ak;Y)相等，这时调整也随之终止，且取到最大值。达到信道容量时分布的唯一性达到信道容量C的时候，输入字母分布唯一吗？最优输入分布不唯一输出分布是唯一达到信道容量时的输出分布是唯一的。任何导致这一输出分布的输入分布都是最佳分布，可以使互信息达到信道容量。串联信道和并联信道的信道容量串联信道（级联信道）x串联信道的信道矩阵为信道1的信道矩阵1与信道2的信道矩阵2的乘积，即 1·2根据矩阵乘法，中的i行第k列的元素P()为åJP ( z k

15、| x i ) =P ( y| x i ) P ( z k| y )jj等效信道P(z|x)z信道2 P(z|y)zx信道1 P(y|x)y串联信道的性质lll数据处理定理：I(Y;Z)I(X;Z)随着串联信道数目的增多，其容量趋近于0将级联信道的i 乘起来，得整个级联信道的，即可求解级联信道的容量。例：两个交叉传输概率为的二进制对称信道相串联，求这串联信道的信道矩阵及信道上传输的最大平均信息量解：由题意有ee1 -1 -eÕ= Õ=12e1 - ee1 -1 - ee1 - eÕ= Õ· Õ=·12eee(1 - e) 2

16、 +e 22e(1 - e)=2e(1 - e)(1 - e) 2 +e 2对称串联信道的等效信道仍为对称信道，但交叉传输概率变成了2(1-)，等效信道的信道容量为LC = H (Y )max - H (Y | xi ) = log m + å Pji log Pjij =1= 1 + 2e (1 - e ) log 2e (1 - e ) + (1 - e )2 + e 2 log(1 - e ) 2 + e2 并联信道xyy 'xx '当各信道相互独立时，联合条件概率为：¢平均联合互信息量为：xxy¢y)P|( =¢xyP¢

17、x)×) log (| yxP¢¢)yxåPx(xyy¢¢I ( XX 'YY ') =( yP¢y)×(|() xy¢¢yPPxXXY¢¢Yå¢(P)(x¢|¢yl|yoP()Pg=××yP¢y)(XXY¢¢YNåi = 1一般来说，当N个相互独立的信道并联时，其总信道容量C为：£CCiC£N C当并联的各个信道相同时，i信道 2y 

18、9;x '信道 1y并联信道的性质特点：输入相同的X，输出不同的Y1,Y2,，随机矢量Y性质：输入并联信道的容量大于任何一个单独的信道，小于Max H(X)。思考：N个二元对称信道输入并联之后的信道容量，N越大，CN越大，越接近H(X）信道编码定理定理 对离散平稳无信道，其容量为C，输入序列长度为L。则，只要实际信息率R<C，就必可找到一种编码：当L足够长时，有Pe< e 。反之，若实际信息率R>C，则对任何编码， Pe必大于零说明 前者为正定理，后者为逆定理 给出了信息传输率的极限只要R<C，必可无失真传输若R>C，必为有失真传输 存在性定理信息论最重要

19、的结论，1948年得到了证明n该定理的结论非常反：若信道有错误，如何能够完全纠正之？尤其是：纠正的过程本身也受错误的影响。n工程上可行的方法成为60年来工程师们追求的目标译码方案译码时所用的准则在一般的信息传输系统中，信宿收到的集合Y不一定与信源发出的信息集合X相同，而信宿需要知道此时信源发出的是哪一个信源信息，故需要把信宿收到的消息恢复成相对应的信源消息。这个消息恢复过程称为译码，用公式表示为Xg(Y)X ' = g (Y )ì x1YXx1 x2ì y1üüï xï y ïïï 2 ï

20、;ïï2ííýïïïî yL ïþ译ýïïïî xMïxM þ信道最小错误概率译码准则最小错误概率最大后验概率译码准则最大后验概率译码准则最大似然概率译码准则最大似然概率译码准则用数学公式表示：若 P(*|)> P(| ) ，对所有的i1，2，M(但除掉*所对应的下标i)，则把 译成 *，此准则使消息的错误传输概率最小，例：已知一个信源的概率空间为X，P(X)1/2， 1/4， 1/4。找出能使错误传输概率最小

21、的0012所使用的信道的信道矩阵Õ=120译码方案，并求出错误传输概率解：信道传输特性如图通常采用的译码方案是最大后验准则：把信道输出符号消息 译成具有最大后验概率P(*|)的那个信道输入符号消息*由公式 P()P( )·P()矩阵形式表示的联合概率分布:10018åX1yP)( =Pxy 再由公式行矩阵形式表示的Y中三个消息的概率分布：31再由公式矩阵形式表示的后验概率分布:488Pxy )yx)P|(=yP)(20031010130收到 后对 ，的后验概率分布为：P( | )2/3P(| )1/3P(| )0比较大小后，按最大后验概率准则，应把信宿收到的译成同

22、理，信宿收到 后对 ，中以P(| )最大，应把译成信宿收到 后对 ，中以P(| )最大，应把 译成所以此准则的译码方案为：g( )g( )g( )总的来说，各个消息的传输和译码过程如下：XYX'x1P(y1 | x1) =1x1y1x2x2y2x3x3P(y3 | x3 ) =1，信宿收到y3，译信源发出消息译成(正确传输)信源发出消息，信宿收到，译译成（不正确传输）信源发出消息，信宿收到或 ，译译成(正确传输)采用此准则的译码方案后，这个消息传输系统的正确传输概率PC为：PC P( )+ P(错误传输概率PE为:)1/2 + 1/43/4PE P()1/4译码中两种特殊情况：若信道的输入消息以等概率分布，即P( )1/M，这时对于某个收到的消息 而言，当信道的传输概率P( |)为最大时，其相应的后验概率P(| )也是最大。所以在信道输入消息以等概率分布的条件下，可以从最大信道传输概率P( | *)直接判定此