信息论与编码纠错第4章.ppt

第4章 离散信道的信道容量,内容提要,信道对于信息率的容纳并不是无限制的，它不仅与物理信道本身的特性有关，还与信道输入信号的统计特性有关，它有一个极限值，即信道容量，信道容量是有关信道的一个很重要的物理量。这一章研究信道，研究在信道中传输的每个符号所携带的信息量，并给出信道容量的定义和计算方法。,4.1信道容量的定义,对于单符号传输情况，信息传输率为：,信道容量C就是在保证可靠通信的前提下，信道所能容纳的最大信息传输量。对于固定信道，信道容量C是一个固定值；对于不同信道，C不同，信道容量C是信道转移概率p(y/x)的函数。,4.2 离散无记忆信道容量的计算,证明：对于DMC信道，由定理2.4（若信道离散无记忆，则信道输入、输出符号序列间的平均互信息量I（XN；YN）小于等于各单个符号间平均互信息量的总和）,综上，在信源和信道都离散无记忆的情况下，有CNNC，即定理中等号成立，这时N长序列的传输问题可归结为单符号传输问题。,二达到信道容量的充要条件,说明：定理只给出了使平均互信息量达到信道容量的充要条件，并没有给出求信道容量及信道输入概率分布的显式，它只能用来求解一些特殊情况的信道容量。,下面介绍几种特殊信道信道容量的求解。,对于特殊信道，信道的输入X和输出Y之间有着确定的关系，一般有三类：有噪无损信道、无噪确定信道和无噪无损信道。,【解】,1先考察平均互信息量I（X;Y）=H（X）-H（X/Y），在无噪信道条件下，H（X/Y）=0，则平均互信息量I（X;Y）=H（X）。,3.根据平均互信息量I（X;Y）达到信道容量的充要条件式对C进行验证：,先根据计算出p(yj)（j=1，2，3，4，5，6）,再计算出：,上面三式均满足平均互信息量达到信道容量C的充要条件，故C=log3。,【例】无噪确定信道,确定信道的输入符号集的元素个数大于输出符号集的个数，信道的一个输出对应多某个个互不交叉的输入，这时输入符号以确定的概率1指向某个输出符号，如图所示。信道输入符号集Xx1,x2,x3,x4,x5，输出符号集Yy1,y2，其信道转移概率矩阵记为P，计算该信道的容量。,【解】,1先考察平均互信息量I（X;Y）=H（Y）-H（Y/X），对于确定信道，H（Y/X）=0，则平均互信息量I（X;Y）=H（Y）,3.根据平均互信息量I（X;Y）达到信道容量的充要条件式对C进行验证：,上面的式子均满足平均互信息量达到信道容量C的充要条件，故C=log2。,【例】无噪无损信道,无损确定信道的输入符号集的元素个数等于输出符号集的个数，且信道的输入符号以确定概率1指向某个固定的输出符号，如图所示，信道输入符号集Xx1,x2,x3,x4,x5，输出符号集Y y1,y2,y3,y4,y5，其信道转移概率矩阵为P，计算信道容量。,【解】该信道的信道容量为：,三几类特殊信道的信道容量,1.准对称信道,定义1：如果信道转移概率矩阵P中，每一行元素都是另一行相同元素的不同排列，则称该信道关于行（输入）对称。,定义2：如果信道转移概率矩阵P中，每一列元素都是另一列相同元素的不同排列，则称该信道关于列（输出）对称。,定义4：如果信道转移概率矩阵P可按输出符号集Y化分的子集（子矩阵）只有一个，则该信道关于关于行、列都对称，称此信道为对称信道。,【定理一】（准）对称信道的条件熵H(Y/X)与信道输入消息的分布p(x)无关，且有H(Y/X)=H(Y/xi)。,【定理二】离散对称信道，若信源（信道输入集合）等概率分布，则信宿（信道输出集合）也是等概率分布的；反之亦然。,【定理三】实现DMC准对称信道的信道容量的信源分布为等概率分布。,证明：若信源含有K个消息，等概率分布，即p(xk)=1/K，k1，2，.，K，则,准对称信道是关于行对称，对任何k值，上式中的和值相等，与k无关，故I(xk；Y)是常数，根据前面的定理，知平均互信息量达到信道容量C。,【例】信道输入符号集X=x1,x2，输出符号集Y=y1,y2,y3,y4，给定信道转移概率矩阵为P，求该信道的信道容量C。,这是一个准对称信道，根据定理，当X等概分布，p(x1)p(x2)1/2时，信道容量,平均互信息量,可算得信道容量,【例】BSC信道的转移概率如下，求信道容量：,该信道为一个对称信道，当输入等概率分布（此时输出也是等概率分布），取得信道容量。,时，信道的输入符号和输出符号是一一对应的关系，在这种情况下，信道容量Clog2，达到最大值。,时，信道的不确定性最大，在这种情况下，信道容量C0，是一种最差信道。,时，这是一种强噪声信道，但也是一种确定信道，在这种情况下，可将判决取反，收到y1 判为x2，y2收到判为 x1，也能达到信道容量的最大值Clog2。,2.信源只含两个消息,【例】信道输入符号集X=x1,x2，输出符号集Y=y1,y2,y3，给定信道转移概率矩阵P，求信道容量C。,设使平均互信息量达到信道容量的信源分布为:p(x1)=，p(x2)=1-。,平均互信息量,根据定义，求C的问题就转化为为何值时，I(X;Y)达到最大值。令,则信道容量,3信道转移概率矩阵为非奇异方阵,计算信道容量C按下面步骤进行：,(1)先验证信道转移概率矩阵P=p(yj/xi)是方阵，且矩阵P的行列式|P|0；,(2)计算出逆矩阵P-1=p-1(yjxk)；,(3)计算出,【例】已知信道转移概率矩阵P，求信道容量C。,（2）P的逆矩阵：,（3）算出,（5）下面验证是否p(xi)0，i=1,2,再算得,这相当于信道是离散无记忆的，根据定理2.4，对于离散无记忆信道，下式成立,说明在两信道并行使用的情况下，总容量小于等于两信道单独使用时的信道容量之和。,根据定义，有,对数以2为底，注意到p2=1-p1，得,代入条件p1+p2=1，得,式（*）中的p1，p2就是使平均互信息量I（p1，p2）达到最大的取值，将其代入信道容量公式，得：,故信道容量为：,串行信道的信道转移概率,用矩阵表示为：,串连信道的总信道转移概率矩阵,第一个信道的转移概率矩阵,第二个信道的转移概率矩阵,【例】给定两个信道，信道转移概率矩阵分别为：,串行信道的转移概率矩阵为：,串行级联信道的信道转移概率趋向于两个独立信道转移概率的均值。这是很不利的，这种情况下出错概率增大，使信息能力减小。,求得串联信道的总转移概率矩阵，利用前面的方法可以求得信道的总容量。若将N个转移概率相同的信道级联，当N 时，其总信道容量将趋于零。,数据处理定理：无论经过何种数据处理，都不会使信息量增加。,证明：,则：I（X;Z）I（X;Y）同理：I（X;Z）I（Y;Z）,若满足：H(X/Y)=H(X/Z)，即满足p(x/y)=p(x/z)，则等号成立I（X;Z）=I（X;Y），说明这种情况下串行传输不会增加信息的损失。,【例】两个离散信道，将它们串行连接使用，计算总信道容量C。,【解】（1）先计算总信道的信道转移概率矩阵,串联信道的总信道矩阵P等于第一级信道的信道矩阵P1，从而概率满足,对上式两边关于x求和，得,上式说明：无论信源如何分布，只要串行信道的总信道转移概率矩阵等于第一个信道的转移概率矩阵，这样串行噪声信道就不会增加信道的信息损失，总的信道容量就等于第一个信道的容量。,(2)计算信道容量C 第一个信道是输入只有两个消息的情况，设最佳分布为 p(x1)=，p(x2)=1-，仿照前面的方法可算出=0.4，则信道容量C=C1=0.32(比特/符号)。,本 章 小 结,本章主要定义了信道容量及讨论了信道容量的计算方法。讨论并证明了使平均互信息量达到信道容量的充要条件，并给出如下几种情况下信道容量的计算方法。,（1）准对称信道（2）信源只含两个消息（3）信道转移概率矩阵为可逆方阵,还讨论了多个信道组合使用情况下，总信道容量的计算方法，讨论了以下几种情况：,（1）N个信道独立并行使用：记每个信道单独使用时的信道容量为Ck，k=1,2,N，则总信道容量C满足，当N个信道独立输入且独立使用时等号成立。,（3）N个信道串联使用：记各个信道的信道转移概率矩阵为Pk，k=1,2,N，则总信道的信道转移概率矩阵P等于各信道转移概率矩阵相乘，即P=P1 P2 PN，矩阵的乘法要满足：左乘矩阵的列数应等于右乘矩阵的行数，且矩阵相乘不满足交换率。,