信息论-第四章.ppt

2020/5/4,1,第四章：信道及其容量,4.1信道分类4.2离散无记忆信道4.5信道的组合,2020/5/4,2,4.1信道分类,信道是传输信息的媒质或通道。（输入信道输出）说明（1）信道输入是随机过程。（2）信道响应特性是条件概率P(输出值为y|输入值为x)，又称为转移概率。（3）信道输出是随机过程，输出的概率分布可以由输入的概率分布和信道的响应特性得到。（全概率公式）（4）根据信道输入、信道响应特性、信道输出的情况，可将信道分类：离散信道（又称为数字信道）；连续信道（又称为模拟信道）；特殊的连续信道波形信道；恒参信道和随参信道；无记忆信道和有记忆信道；等等。,2020/5/4,3,4.2离散无记忆信道,定义4.2.1和定义4.2.2(p88-89)如果（1）信道的输入为随机变量序列X1,X2,X3,，其中每个随机变量Xu的事件集合都是0,1,K-1，（2）信道的输出为随机变量序列Y1,Y2,Y3,，其中每个随机变量Yu的事件集合都是0,1,J-1，则称该信道为离散信道。如果更有（3）P(Y1Y2YN)=(y1y2yN)|(X1X2XN)=(x1x2xN)=P(Y1=y1|X1=x1)P(Y2=y2|X2=x2)P(YN=yN|XN=xN)，则称该信道为离散无记忆信道（DMC）。如果更有（4）对任意x0,1,K-1，y0,1,J-1，任意两个时刻u和v，还有P(Yu=y|Xu=x)=P(Yv=y|Xv=x)，则称该信道为离散无记忆平稳信道或恒参信道。,2020/5/4,4,4.2离散无记忆信道(DMC),关于定义4.2.1和定义4.2.2的注解“离散”的含义是时间离散，事件离散。即：信道的输入、输出时刻是离散的，且输入随机变量和输出随机变量都是离散型的随机变量。“无记忆”的含义是信道响应没有时间延迟，当时的输出只依赖于当时的输入。“平稳”的含义是信道在不同时刻的响应特性是相同的。“离散无记忆平稳信道”是最简单的信道，信道在某一时刻u的响应特性P(Yu=y|Xu=x)；x0,1,K-1，y0,1,J-1，就能很简单地计算出信道在任意时间段的响应特性。即在DMC（若无特殊说明就意味着满足平稳条件）下，只需研究单个字母传送。,2020/5/4,5,4.2离散无记忆信道,例4.2.1（p89）二元对称信道BSC是离散无记忆恒参信道。当N1时，p(0/0)=p(1/1)=0.9,p(1/0)=p(0/1)=0.1当N=2时，p(00/00)=p(11/11)=p(0/0)p(0/0)=0.9*0.9=0.81P(10/00)=p(01/00)=p(01/11)=p(10/11)=0.1*0.9=0.09P(11/00)=p(00/11)=0.1*0.1=0.01,2020/5/4,6,4.2离散无记忆信道,一、有关DMC的容量定理（所说的DMC都是离散无记忆平稳信道）设DMC在某个时刻输入随机变量为X，输出随机变量为Y。信道响应特性为转移概率矩阵p(y|x)，x0,1,K-1，y0,1,J-1，它是一个KJ阶矩阵（其中p(y|x)=P(Y=y|X=x)）。X的概率分布为x,q(x),x0,1,K-1。Y的概率分布为y,w(y),y0,1,J-1。以下的结论是我们已知的。,2020/5/4,7,4.2离散无记忆信道,（1）转移概率矩阵的每一行都是一个概率向量。,2020/5/4,8,4.2离散无记忆信道,（2）对任意y0,1,J-1，由全概率公式有,2020/5/4,9,4.2离散无记忆信道,（3）I(X;Y)是概率向量q(x),x0,1,K-1和转移概率矩阵p(y|x)，x0,1,K-1，y0,1,J-1的函数。,2020/5/4,10,4.2离散无记忆信道,（4）设转移概率矩阵p(y|x)，x0,1,K-1，y0,1,J-1（是信道的响应特性）确定，希望选择概率向量q(x),x0,1,K-1使I(X;Y)达到最大。(则见p33定理2.6.2说明平均互信息量的最大值存在，可以取到。)定义4.2.3(p89)离散无记忆信道的信道容量定义为如下的C。达到信道容量的输入概率分布x,q(x),x0,1,K-1称为最佳输入分布。其中,信道容量表示了信道传送信息的最大能力，这个量在信息论研究中有重要意义。传送的信息量必须小于信道容量C,2020/5/4,11,4.2离散无记忆信道,定理4.2.2(p91)（1）输入概率分布x,q(x),x0,1,K-1是最佳输入分布的充分必要条件为：对任何满足q(k)0的k，都取一个相同的值；对任何满足q(k)=0的k，I(X=k;Y)此相同的值。（2）此时此相同的值恰好就是信道容量C。（定理4.2.2实际上叙述了定理2.6.2的含义。）,2020/5/4,12,4.2离散无记忆信道,注解给定一个DMC信道的响应特性，也就是说给定一个信道的转移概率矩阵p(y|x)，x0,1,K-1，y0,1,J-1，达到信道容量时所对应的最佳输入分布是满足定理4.2.2条件的概率向量q(x),x0,1,K-1。其信道容量是每个使得q(k)0的k所对应的半平均互信息量I(X=k;Y)。如果对DMC信道没有任何简化，要计算最佳输入分布并不容易。但是，通常使用的DMC是很简单的（比如，以下的准对称信道和对称信道），最佳输入分布很容易求出。,2020/5/4,13,4.2离散无记忆信道,二、对称DMC和准对称DMC的信道容量与最佳输入分布的计算定义4.2.45(p108)设DMC的转移概率矩阵为若P的任一行是第一行的置换，则称信道是关于输入为对称的。若P的任一列是第一列的置换，则称信道是关于输出为对称的。若信道是关于输入为对称的，又是关于输出为对称的，则称信道为对称信道。,2020/5/4,14,4.2离散无记忆信道,命题1若DMC关于输入为对称的，则对任意k0,1,K-1都成立。证明p(y|x)，y=0J-1与p(y|k)，y=0J-1互为置换，所以,2020/5/4,15,4.2离散无记忆信道,命题2若DMC关于输出为对称的，则当输入分布等概时，输出分布等概。证明此时p(y|x)，x=0K-1与p(0|x)，x=0K-1互为置换。设q(x)=1/K，x0,1,K-1。则,2020/5/4,16,4.2离散无记忆信道,定义4.2.6(p92)若DMC的转移概率矩阵P的列的全体可分成若干个列子集，每个列子集所对应的P的子阵都满足以下两条性质：（1）任一行是第一行的置换，（2）任一列是第一列的置换。则称信道为准对称信道。（显然，准对称信道关于输入是对称的。特别若列子集只有一个，即转移概率矩阵P本身的任一行是第一行的置换，任一列是第一列的置换，则称信道为对称信道。）,2020/5/4,17,4.2离散无记忆信道,例4.2.2准对称信道的例子。(见p92)因为Y0,1,2可划分为两个子集0,2和1，而每个子集对应于矩阵P的列所构成的子阵分别为,2020/5/4,18,4.2离散无记忆信道,几个简单的结论：（1）准对称信道一定是关于输入为对称的。（2）对称信道不仅是关于输入为对称的，也是关于输出为对称的。（3）对称DMC当输入分布等概时，输出分布等概。（4）准对称DMC当输入分布等概时，输出分布局部等概。（准对称DMC当输入分布等概时，若j和l属于转移概率矩阵的同一个列子集，则wj=wl。）（5）对称信道未必有J=K。,2020/5/4,19,4.2离散无记忆信道,定理4.2.3(p92)对于准对称DMC信道，（1）达到信道容量的最佳输入分布为等概分布；（2）信道容量为,2020/5/4,20,4.2离散无记忆信道,证明根据定理4.2.2的含义，只需要证明：当输入分布为等概时，对任意k0,1,K-1，半平均互信息量I(X=k;Y)都取相同的值。（此时，该相同的半平均互信息量I(X=k;Y)就是准对称信道容量C。）换句话说，只需要证明：当输入分布为等概时，对任意k0,1,K-1，I(X=k;Y)与k无关。设转移概率矩阵P的列的全体被分成S个互不相交的列子集：0,1,J-1=Y1Y2YS；Y1、Y2、YS互不相交；对任意s1,2,S，列子集Ys所对应的子阵都满足：任一行是第一行的置换，任一列是第一列的置换。自然有以下三个结论。,2020/5/4,21,4.2离散无记忆信道,结论一：准对称信道是关于输入为对称的，所以对任意k0,1,K-1，结论二：对每个列子集Ys，结论三：对每个列子集Ys，取定ysYs。则对任意yYs，,关于输入，输出是对称的,2020/5/4,22,4.2离散无记忆信道,于是,关于行求和。,关于列求和。,2020/5/4,23,4.2离散无记忆信道,于是,2020/5/4,24,4.2离散无记忆信道,定理4.2.3的一个特例是当信道是对称信道时。这时关于输出为对称的，若当输入分布等概(q(x)=1/K)时，输出分布等概(w(y)=1/J)。信道容量为,信道容量为为状态转移概率矩阵任一行所对应的半平均互信息量。,2020/5/4,25,4.2离散无记忆信道,一般，信道关于输入是对称时，不一定存在一种分布使输出分布是均匀的，此时信道容量,2020/5/4,26,4.2离散无记忆信道,例4.2.3特殊的对称DMC：K元对称信道KSC(p93),其中0p1。称p为错误概率。特别当K=2时，记为BSC,2020/5/4,27,4.2离散无记忆信道,此时有：达到信道容量时的最佳输入分布为等概分布；对应的输出分布也是等概分布；信道容量是转移概率矩阵任何一行所对应的半平均互信息量，即,准对称信道的结论定理4.2.3,2020/5/4,28,4.2离散无记忆信道,其中0p0，q(1)0。因此,2020/5/4,39,4.2离散无记忆信道,因此,2020/5/4,40,4.2离散无记忆信道,例特殊的DMC，称为Z信道：输入事件为0,1，输出事件为0,1，转移概率矩阵为其中00，q(1)0。因此,2020/5/4,41,2020/5/4,42,4.2离散无记忆信道,容易验证：q(1)0；q(0)+q(1)=1。需要验证：q(0)0。,2020/5/4,43,4.5信道的组合,总设有如下两个DMC，分别称为信道1和信道2。信道1的输入事件为全体x，共有K个输入事件；信道1的输出事件为全体y，共有J个输出事件；信道1的转移概率矩阵为p1(y|x)KJ；信道1的信道容量为C1，最佳输入分布为x,q1(x)。信道2的输入事件为全体u，共有N个输入事件；信道2的输出事件为全体v，共有M个输出事件；信道2的转移概率矩阵为p2(v|u)NM；信道2的信道容量为C2，最佳输入分布为u,q2(u)。,2020/5/4,44,4.5信道的组合,定义4.5.1（p104）信道的输入事件为全体(x,u)，共有KN个输入事件；信道的输出事件为全体(y,v)，共有JM个输出事件；转移概率矩阵为p(y,v)|(x,u)(KN)(JM)，其中p(y,v)|(x,u)=p1(y|x)p2(v|u)。则称该信道为信道1与信道2的积信道。（又称该信道为信道1与信道2的独立并行信道）（在物理上，积信道是两个信道的并行使用）,2020/5/4,45,4.5信道的组合,定理4.5.1（p104）积信道的信道容量为C=C1+C2，最佳输入分布为(x,u),q(x,u)，其中q(x,u)=q1(x)q2(u)。证明此时,2020/5/4,46,4.5信道的组合,2020/5/4,47,4.5信道的组合,2020/5/4,48,4.5信道的组合,所以I(XU)=(xu);(YV)=I(X=x;Y)+I(U=u;V)。注意到对任何满足q1(x)0的x，I(X=x;Y)=C1；对任何满足q1(x)=0的x，I(X=x;Y)C1；对任何满足q2(u)0的u，I(U=u;V)=C2；对任何满足q2(u)=0的u，I(U=u;V)C2。于是对任何满足q1(x)q2(u)0的(xu)，I(XU)=(xu);(YV)=C1+C2；对任何满足q1(x)q2(u)=0的(xu)，I(XU)=(xu);(YV)C1+C2。根据定理4.2.2(p122)，积信道的信道容量为C=C1+C2，最佳输入分布为(x,u),q1(x)q2(u)。,2020/5/4,49,4.5信道的组合,定义4.5.2（p106）信道的输入事件为全体xu，其中x与u不相交；共有K+N个输入事件；信道的输出事件为全体yv，其中y与v不相交；共有J+M个输出事件；信道的转移概率矩阵为则称该信道为信道1与信道2的和信道（或称并信道）。任一单位时间可随机地选用一个信道，而不能同时选用两个信道。若选用信道1的概率为P1，选用信道2的概率为P2，则P1+P2=1。,2020/5/4,50,4.5信道的组合,定理4.5.2（p106）（证略）,2020/5/4,51,4.5信道的组合,定义4.5.3（p107）构造一个信道，使得该信道的输入是信道1的输入；信道1的输出作为信道2的输入；信道2的输出就是该信道的输出。则称该信道为信道1与信道2的级联信道（串行信道）。请注意：此时信道1的输出事件全体恰好是信道2的输入事件全体，即y=u，J=N。,2020/5/4,52,4.5信道的组合,注：（1）级联信道的转移概率矩阵