离散信道及其容量.ppt

第4章 离散信道及其容量,4.1 信道的数学模型及其分类,1什么是信道？信道是传送信息的载体信号所通过的通道。信息是抽象的，信道则是具体的。比如：二人对话，二人间的空气就是信道；打电话，电话线就是信道；看电视，听收音机，收、发间的空间就是信道。2信道的作用在信息系统中信道主要用于传输与存储信息，而在通信系统中则主要用于传输。,3研究信道的目的在通信系统中研究信道，主要是为了描述、度量、分析不同类型信道，计算其容量，即极限传输能力，并分析其特性。,信 道,输入量X(随机过程),输出量Y(随机过程),p(Y|X),按输入/输出信号在幅度和时间上的取值:离散信道：输入和输出的随机序列取值都是离散的信道连续信道：输入和输出的随机序列取值都是连续的信道半离散(半连续)信道：输入变量取值离散而输出变量取值连续输入变量取值连续而输出变量取值离散,时间离散的连续信道：信道输入和输出是连续的时间序列波形信道：输入和输出都是时间的实函数x(t),y(t),两端信道多端信道恒参信道：参数不随时间变化随参信道：参数随时间变化无记忆信道和有记忆信道对称信道和非对称信道,多元接入信道广播信道无损信道确定信道无噪信道,4.2 离散无记忆信道,4.2.1离散信道数学模型,信道描述信道可以引用三组变量来描述：信道输入：X=(X1,X2 Xi,),Xi a1 an信道输出：Y=(Y1,Y2 Yj,),Yj b1 bm信道概率转移矩阵：py/x=p(y1y2.yn|x1x2xn)即：X p(y|x)Y,定义4.2.1若离散信道对任意N长的输入、输出序列有 则称它为离散无记忆信道DMC。其信源模型为X p(yn|xn)Y任何时刻信道的输出至于此时刻信道的输入有关,而与以前的输入无关。,定义4.2.2对任意n和m,iA,jB,若离散无记忆信道还满足则称此信道为平稳的或恒参的。,1、无扰(无噪)信道信道的输出信号Y与输入信号X之间有确定的关系Y=f(X),已知X后就确知Y转移概率:,2、有干扰无记忆信道,信道的输出信号Y与输入信号X之间没有确定的关系,但转移概率满足:,3、有干扰有记忆信道,4.2.2单符号离散信道,X=a1,a2,ar P(Y/X)=p(bj/ai)(i=1,2,r;j=1,2,s)Y=b1,b2,bs0p(bj/ai)1,信道的传递概率又称为转移概率,矩阵P称为转移矩阵或信道矩阵；表示为：,P矩阵为一个rs矩阵，其每行元素之和等于1,3、图示法描述,例4.2.1：二元对称信道,二元对称信道BSC输入符号X取值0,1；输出符号Y取值0,1 很重要的一种特殊信道信道转移概率：p(0|0)=1p p(1|1)=1p p(0|1)=p p(1|0)=p,4.2.2二元删除信道BEC,二元删除信道BEC 输入符号X取值0,1；输出符号Y取值0,1,2 转移矩阵,0,2,1,0,1,p,1-p,q,1-q,4.2.3二元对称消失信道,二元删除信道BEC 输入符号X取值0,1；输出符号Y取值0,1,2 转移矩阵,0,x,1,0,1,1-p-q,q,1-p-q,q,p,p,先验概率:信源发出消息ai的概率p(ai)=P(X=ai)(i=1,2,r),后验概率:信宿收到bj 后推测信源发出ai的概率p(ai|bj)=P(X=ai|Y=bj),联合概率:,p(ai|bj)=P(X=ai,Y=bj)=p(ai)p(bj|ai)=p(bj)p(ai|bj),前向概率:（及信道传递概率）,输出符号概率:,p(bj|ai)=P(Y=bj|X=ai),p(bj)=P(Y=bj),4.2.3信道疑义度,定义4.2.3称输入空间X对输入空间Y的条件熵,可疑度，它表示接收者收到Y后，对信源X仍然存在的平均不确定度。对于接收者来说，条件熵H(X/Y)称为疑义度，对X尚存在的平均不确定度是由于干扰(噪声)引起的,4.2.4平均互信息,定义4.2.4原始信源熵与信道疑义度之差称为平均互信息。,信息=先验不确定性后验不确定性=不确定性减少的量,Y未知,X 的不确定度为H(X)Y已知,X 的不确定度变为H(X|Y),平均互信息,有扰信道,干扰源,信源X,信宿Y,通信系统中,若发端的符号为X,收端的符号为Y如果是一一对应信道,接收到Y后,对X的不确定性将完全消除：H(X|Y)=0一般情况：H(X|Y)H(X),即了解Y后对X的不确定度的将减少通过信道传输消除了一些不确定性,获得了一定的信息。,平均互信息的另一种定义方法：,定理4.2.1对于固定的信道（给定转移概率矩阵P后）,平均互信息I(X;Y)是输入信源的概率分布p(x)的上凸函数。,定理4.2.2对于固定的信源分布,平均互信息I(X;Y)是信道传递概率p(y|x)的下凸函数。,4.2.5平均互信息与各类熵的关系,熵只是平均不确定性的描述;不确定性的消除(两熵之差)才等于接收端所获得的信息量。获得的信息量不应该和不确定性混为一谈,维拉图,H(X|Y),H(X),H(Y),H(XY),H(Y|X),I(X;Y),4.3离散无记忆扩展信道,4.3.1 N次扩展信道,1、简单的离散无记忆信道,2、N次扩展信道,定理：设离散信道的输入序列X(X1X2XN)通过信道传输，接收到的随机序列为Y=(Y1Y2YN)，而信道的转移概率为p(yx)。若信道是无记忆的，则有：若信源是无记忆的，则有：若信源与信道都是无记忆的，则有：,4.4 信道的组合,在实际通信系统中,信号往往要通过几个环节的传输,或多步的处理,这些传输或处理都可看成是信道,它们串接成一个串联信道。,定理4.4.1级联信道中的平均互信息满足以下关系,定理4.4.2若随机变量X,Y,Z构成一个马尔可夫链，则有：,例 设有两个离散BSC信道,串接如图,两个BSC信道的转移矩阵为:,X0,0Z,Y,1,1,1-p,1-p,1-p,p,串联信道的转移矩阵为:,1-p,p,4.5 信道容量,4.5.1 信道容量的定义,定义4.5.1 信道容量定义为平均互信息的最大值：,信道容量表征信道传送信息的最大能力。实际信道传送信息量必须小于信道容量，否则会出现错误。,平均互信息I(X;Y)：接收到符号Y后平均每个符号获得的关于X的信息量。,信道的信息传输率就是平均互信息,我们研究信道的目的是要讨论信道中平均每个符号所能传送的信息量,即信道的信息传输率R,信道在单位时间内平均传输的信息量，称为信息传输速率Rt。,单位：bit/s,若平均传输一个符号需要t秒钟，则信道在单位时间内平均传输的最大信息量Ct，为,单位：bit/s,4.5.2 离散无噪信道,1、无损信道,设信道的输入XA=a1 an,输出YB=b1 bm无损信道的一个输入对应多个互不相交的输出,由于其矩阵的每一列元素只有一个非零元素，所以后验概率不等于1，就等于0,可知疑义度H(X/Y)=0，平均交互信息量达到最大值I(X,Y)=H(X)，C=logr。从平均意义上讲，这种信道可以把信源的信息全部传递道信宿。,说明：I(X;Y)=H(X)0,2、确定信道,确定信道的输出对应多个互不相交的输入。,这类信道的转移概率等于1或者等于0，每一列的元素可有一个或多个1，可知其噪声熵H(Y/X)=0，此时的平均交互信息量达到最大值。,I(X;Y)=H(Y)-H(Y/X)=H(Y)H(X)C=maxI(X;Y)=maxH(Y)=logs,3、无损确定信道,无损确定信道：输入和输出是一一对应关系,X,a1 b1 Ya2 b2a3 b3,1,1,1,4.5.3 离散对称信道,定义若一个离散信道的信道矩阵中，每一行都是由同一组元素的不同排列，则称为输入对称信道。,定义4.5.3若一个离散信道的信道矩阵中，每一列都是其他列同一组元素组成的不同排列，则称为离散输出对称信道。,如果一个离散信道的信道转移矩阵中的每一行都是由同一组元素的不同组合构成的，并且每一列也是由这一组元素组成的，则称为对称信道。,定义4.5.4若一个离散无记忆信道的信道矩阵中，按照信道的输出集Y（即信道矩阵的行）可以将信道矩阵划分成n个子集（子矩阵），每个子矩阵中的每一行（列）都是其他行（列）的同一组元素的不同排列，则称这类信道为离散准对称信道。子集中元素满足对称性,例：（对称信道识别）,定理4.5.1实现离散准对称无记忆信道信道容量的输入符号集的分布为等概分布。,定理4.5.2若一个离散对称信道具有r个输入符号，s个输出符号，则当输入为等概分布是，达到信道容量C，且C=logs-H(p1p2ps),式中p1p2ps为信道矩阵中的任一行。,引理：对于对称信道，只有当信道输入分布为等概分布时，输出分布才能为等概分布。,定义4.5.5信道输入符号和输出符号个数相同，且信道矩阵为，则称此信道为强对称信道或均匀信道。,信道矩阵中各列之和也等于1。,推论：均匀信道的信道容量为C=logr-plog(r-1)-H(p),4.5.4一般信道容量的计算方法,：一般离散信道的平均互信息I(X;Y)达到极大值的充分和必要条件是输入概率p(ai)必须满足:I(ai;Y)=C 对于所有ai其p(ai)0 I(ai;Y)C 对于所有ai其p(ai)=0时，I(X;Y)达到极大值。此时，常数C记为所求的信道容量。,上式说明：当信道的平均互信息I(X;Y)达到信道容量时,输入符号概率集p(ai)中每一个符号ai对输出端Y提供相同的互信息,只是概率为0的除外。,4.5.5离散无记忆N次扩展信道,设信道的输入X=(X1,X2 Xi,),Xi a1 an 输出Y=(Y1,Y2 Yj,),Yj b1 bm,信 道,X,Y,p(Y|X),对于无记忆离散N次扩展信道,其信道转移概率为,仅与当前输入有关。若信道是平稳的,定理：若信道的输入和输出分别是L长序列X和Y,且信道是无记忆的,亦即信道传递概率为,则存在,定理：若信道的输入和输出分别是L长序列X和Y,且信源是无记忆的,亦即,则存在,若信源与信道都是无记忆的,L次扩展信道的信道容量,当信道平稳时:,一般情况下:,4.5.6独立并联信道,设有L个信道,它们的输入、输出分别是：X1,X2XL；Y1,Y2YL,信 道,信 道,信 道,p(Y1|X1),p(YL|XL),p(Y2|X2),每一个信道的输出Yl只与本信道的输入Xl有关,与其他信道的输入、输出都无关。独立并联信道的信道容量,X1,X2,XL,Y1,Y2,YL,4.5.7信源和信道匹配,一般情况下信源与信道连接时，其信息传输率R=I(X;Y)并未达到最大。若信息传输率达到了信道容量，则称信源与信道达到匹配；否则认为信道有剩余。,信道剩余度定义为 信道剩余度=C-I(X;Y),用相对剩余度描述信源与信道的匹配程度 相对剩余度=C-I(X;Y)/C=1-I(X;Y)/C,无损信道中，信道容量C=logr(r是信道输入符号的个数）,而I(X;Y)=H(X)无损信道的相对剩余度=1-H(X)/logr,