信息论离散信道及其容量.ppt

第4章 离散信道及其容量,通信系统模型,信息论的研究基础是通信系统模型。,4.1 信道的数学模型及其分类,信道是信息传输的通道。由于干扰的存在，信道的输出Y与信道的输入X不完全相同，用条件概率p(y|x)描述。而输入和输出又有各自的统计特性，分别用 和表示。第3章介绍有记忆信源的时候用到了条件概率，现在又用到了条件概率，两种情况下条件概率所表达的含义相同吗？不同信源：表示前后输出的符号之间的关联关系信道：表示传输时发生错误的情况，或者说干扰的情况,信道的分类,根据输入输出事件的时间特性离散信道：GSM连续信道：有线电视、广播根据输入输出个数两端信道（单路信道）：电话多元接入信道：信道的复用广播信道：广播根据统计特性恒参信道：信道的统计特性不随时间发生变化。随参信道：信道的统计特性随时间发生变化。根据记忆特性无记忆信道：信道的输出仅与当前的输入有关，与以前的输入无关。有记忆信道：信道的输出不仅与当前的输入有关，与以前的输入也有关系。,一些特殊信道,无损信道：输出可以决定输入，即知道了信道的输出符号，能确切判断出它对应的输入符号是什么。确定信道：输出完全由输入决定，即输入符号一旦定下来，信道的输出是确定的。无噪信道：既是无损信道，又是确定信道。输出能决定输入，输入也能决定输出。现实生活中很少存在这样的信道。无用信道：输入与输出相互独立，没有任何关系。,4.2 离散无记忆信道,离散信道的输入序列为X=X1,X2,XN，其取值为x=x1,x2,xN，其中xnA=a1,a2,ar。信道的输出序列为Y=Y1,Y2,YN，其取值为y=y1,y2,yN，其中ynB=b1,b2,bs。离散信道特性：p(y|x)=p(y1y2yN|x1x2xN)信道的数学模型：X,p(y|x),Y,离散无记忆信道,定义 若离散信道对任意N长的输入、输出序列有p(y|x)=p(y1y2yN|x1x2xN)=，则称它为离散无记忆信道，简称DMC。其数学模型为：X,p(y|x),Y=X,p(yn|xn),Y无记忆的含义：信道的输出只与此时信道的输入有关，与以前的输入无关。定义 对任意n和m，若离散无记忆信道还满足P(yn=j|xn=i)=P(ym=j|xm=i)则称此信道为平稳的或者恒参的。,无记忆离散平稳信道中序列的转移概率和单个符号的转移概率的关系,后面如无特殊声明，所讨论的离散无记忆信道都是平稳的。因为无记忆，所以序列的转移概率可以表示为单个符号的转移概率的乘积。因为平稳，所以序列的转移概率和符号的转移概率都不随时间发生变化。因此对于无记忆离散平稳信道，只需研究单个符号的传输，即研究一维概率分布即可。,三种常见的离散信道,无扰（无噪）信道输出符号与输入符号之间有确定的一一对应关系：yn=f(xn)，常见的情况是yn=xn，这表明传输没有发生错误（信道上没有干扰），发送的是什么，接收到的就是什么。无扰信道还可以表示为：有干扰无记忆信道有干扰有记忆信道 实际信道往往是既有干扰又有记忆,4.2.2 单符号离散信道,N=1，信道传递概率：p(y|x)=P(Y=bj|X=ai)=p(bj|ai)=pij，满足pij0，所有的信道传递概率可以组成一个矩阵：信道矩阵P：,例 二元对称信道简称为BSC二元：输入和输出符号集均为0,1对称：1变成0和0变成1的概率相等。p(0|0)=p(1|1)=1-p，p(0|1)=p(1|0)=pBSC的信道矩阵：,例 二元删除信道二元：输入符号集为0,1，输出符号集中的有效字符也为0,1。删除：输出符号集为0,x,1，不过信道不会发生错误（0不可能变为1，1也不可能变为0），但是0和1都有被删除的可能（删除用变为x表示）。信道矩阵：,例 二元对称消失信道二元：输入符号集为0,1，输出符号集中的有效字符也为0,1。消失：输出符号集为0,x,1，信道有可能发生错误（0可能变为1，1也可能变为0），而且0和1都消失的可能（消失用变为x表示）。信道矩阵：,离散信道中常用的几种概率,先验概率：p(ai)，PX=p(a1)p(a2)p(ar)联合概率：p(aibj)=p(ai)p(bj|ai)=p(bj)p(bj|ai)信道传递概率：p(bj|ai)=pij，后验概率：p(ai|bj)输出符号概率：PY=p(b1)p(b2)p(bs)=PXP,4.2.3 信道疑义度,定义 称输入空间X对输出空间Y的条件熵 为信道疑义度。含义：收到全部输出符号Y以后，对输入符号X尚存在的平均不确定性。这种不确定性是由信道干扰引起的。对无扰信道：H(X|Y)=0。H(X|Y)H(X)：收到输出符号Y以后，总能消除一些对X的不确定性，获得一些信息。表示接收到符号bj后，仍然保留的关于X的平均不确定性。,例4.2.4 二元删除信道则由此可得,4.2.4 平均互信息,定义 原始信源熵与信道疑义度之差称为平均互信息。I(X;Y)=H(X)-H(X|Y)含义：接收到信道的输出符号集Y之后，平均每个符号获得的关于信道输入符号集X的信息量。平均互信息具有非负性。,两个定理,定理 对于固定的信道，平均互信息I(X;Y)是信源概率分布p(x)的上凸函数。固定信道：信道传递概率p(y|x)不变定理 对于固定的信源分布，平均互信息I(X;Y)是信道传递概率p(y|x)的下凸函数。固定信源：信源概率分布p(x)不变,平均互信息的例子,例 信源：信道：则互信息量：,例对信道的输入符号集X：设面1、2、3、4朝上为事件X=0；设面5、6朝上为事件 X=1。则信源概率空间为：对信道的输出符号集Y：设出现0次正面为 事件Y=0；设出现1次正面为事件Y=1；设出 现2次正面为事件Y=2。则信道矩阵为：联合分布为：条件熵为：输出符号集Y的分布：则所以：I(X;Y)=H(Y)-H(Y|X)=1.325-1.166=0.159,4.2.5 熵、信道疑义度及平均互信息的相互关系,H(X,Y)=H(X|Y)+H(Y)=H(Y|X)+H(X)I(X;Y)=H(X)-H(X|Y)I(X;Y)=I(Y;X)I(X;Y)=I(Y;X)0I(X;X)=H(X),4.3 离散无记忆扩展信道,4.2节讨论了单个符号的信道传输情况。实际上，一般离散信道的输入和输出是一序列，因此有必要研究扩展信道。N次扩展信道与单符号信道之间的关系，类似于N次扩展信源与单符号信源之间的关系。N次扩展信道中，输入变量和输出变量均为N维的：X=X1,X2,XN，Y=Y1,Y2,YN，输入序列共有rN个，输出序列共有sN个，输入和输出序列分别记为k和h。N次扩展信道的数学模型为,例 二元无记忆对称信道的二次扩展信道。二元对称信道二次扩展信道的输入和输出：N=2,r=2,s=2，则rN=4,sN=4，输入、输出符号集00,01,10,11扩展信道的传递概率：信道矩阵为：扩展信道的平均互信息：I(X;Y)=I(XN;YN),4.3.2 定理,定理 若信道的输入和输出分别是N长序列X和Y，且信道是无记忆的，则：I(X;Y)I(Xi;Yi)定理 若信道的输入和输出分别是N长序列X和Y，且信源是无记忆的，则：I(X;Y)I(Xi;Yi)当信源和信道都是无记忆的，此时I(X;Y)=I(Xi;Yi)当信道输入序列的每一个符号来自同一个符号集A，信道输出序列的每一个符号来自同一个符号集B，则I(Xi;Yi)=NI(X;Y)，即I(X;Y)=NI(X;Y)来自同一符号集：00,01,10,11，每一序列的两个符号均来自0,1 来自不同符号集：a1,a2,b1,b2，每一序列的第一个符号来自a,b，第二个符号来自1,2,4.4 信道的组合,组合方式 并行：积信道 串行：级联信道 例如：Internet 例如：GSM重点介绍级联信道（串联信道）,假设串联的两个信道为信道I和信道II，信道I的传递概率为p(y|x)，信道II的传递概率为p(z|xy)。定理 若随机变量X,Y,Z构成一个马尔可夫链（p(z|xy)=p(z|y)），则有I(X;Z)I(X;Y)I(X;Z)I(Y;Z)定理叫做数据处理定理，它的含义是通过串联信道的传输，只会丢失信息，不会增加信息，至多保持原来的消息量。这是信息不增性原理。,信道Ip(y|x),信道IIp(z|xy),X,Y,Z,例4.4.1 两个二元对称信道串联,一个马尔可夫链，则串联信道总的信道矩阵为则 I(X;Y)=1-H(p)I(X;Z)=1-H(2p(1-p)从图中能够看出 I(X;Z)I(X;Y),例信道I和信道II的信道矩阵分别为X,Y,Z构成一个马尔可夫链，则,4.5 信道容量,定义 信道容量定义为平均互信息的最大值：C=maxp(x)I(X;Y)由定理知，I(X;Y)是p(x)的上凸函数，称使I(X;Y)取最大值的p(x)为最佳输入分布。由I(X;Y)的定义式可知，I(X;Y)是由信道特性p(y|x)和信源特性p(x)共同决定的，但是容量C已对所有可能的p(x)取最大值，因此容量C仅与信道特性p(y|x)有关，也就是说，容量C是信道的固有特性，与信源无关。,信息传输率,信道的信息传输率R定义为平均互信息：R=I(X;Y)其含义是：平均每个符号所能传送的信息量。研究信道的核心问题是求出信道容量C，以及达到信道容量C的信源分布p(x)（最佳输入分布）。,4.5.2 特殊信道的信道容量,无损信道：logr确定信道：logs无噪信道：logr=logs,4.5.2.1 无损信道,一个输入对应多个互不 相交的输出，即信道矩 阵的每一列只有一个非 零元素。由于知道输出之后，必然能够确定其对应的输入是什么，因此信道疑义度H(X|Y)=0。则I(X;Y)=H(X)-H(X|Y)=H(X)因此信道容量C=maxp(x)I(X;Y)=maxp(x)H(X)=logr,4.5.2.2 确定信道,一个输出对应多个互不相交 的输入，即信道矩阵的每一行 只有一个“1”，其余元素均为0。由于知道输出之后，必然能够确定其对应的输入是什么，因此噪声熵H(Y|X)=0。则I(X;Y)=H(Y)-H(Y|X)=H(Y)因此信道容量C=maxp(x)I(X;Y)=maxp(x)H(Y)=logs,4.5.2.3 无噪信道,输出与输入是一一对应关系，即信道矩阵为单位矩阵。因此信道疑义度H(X|Y)=0，噪声熵H(Y|X)=0。则I(X;Y)=H(X)-H(X|Y)=H(X)=H(Y)-H(Y|X)=H(Y)因此信道容量C=maxp(x)I(X;Y)=maxp(x)H(X)=logr=maxp(x)H(Y)=logs,4.5.3 对称信道,定义 信道矩阵的每一行都是其他行的不同排列，则称此类信道为输入对称信道。定义 信道矩阵的每一列都是其他列的不同排列，则称此类信道为输出对称信道。定义 信道矩阵的每一行（列）都是其他行（列）的不同排列，则称此类信道为对称信道。,对称信道的容量,定理 若一个离散对称信道有r个输入符号，s个输出符号，则当输入为等概分布时，达到信道容量C，且C=logs-H(p1p2ps)式中，p1p2ps为信道矩阵中的任一行。“当输入为等概分布时，达到信道容量C”的含义是最佳输入为等概分布。,对称信道容量的例子,例4.5.2 最佳输入为：信道容量为：C=logs-H(p1p2ps)=log3-H(1/2,1/3,1/6),4.5.7 信源和信道的匹配,信源与信道达到匹配的含义：信源处于最佳输入分布，使得信息传输率R达到了信道容量C。但通常情况下，让信源处于最佳输入分布并不容易，此时信道有剩余：信道剩余度=C-I(X;Y)信源编码的目的就是通过编码，改变原始信源的统计特性，使得信道剩余度尽可能小。,原始信源,信道,不匹配,原始信源,信道,信源编码,基本匹配,本章小结,信道：PX,PY|X。离散无记忆信道：一维（单符号）信道疑义度：H(X|Y)；噪声熵：H(Y|X)。平均互信息：I(X;Y)。串联信道：数据处理定理。信道容量对称信道：C=logs-H(p1p2ps)，最佳输入为等概分布。,