第3讲离散信源的熵和互信息2014

第三讲,熵和互信息量,自信息、联合自信息量、条件自信息量,平均自信息量，信源熵（信息熵）,定义：自信息的数学期望,熵的物理含义消除信源不确定度所需要的信息量信源输出所提供的平均信息量无错编码所需的最小编码长度,熵、条件熵、联合熵关系,熵的基本性质,概率矢量,熵函数,非负性H(X)0,对称性信源熵与各概率分量对应的状态顺序无关。,确定性,扩展性,极值性最大离散熵定理,等概信源的不确定性最大,2个基本不等式：不等式）：当且仅当x=1时等号成立。2.二个任意概率矢量,设有4枚同值硬币，其中1枚硬币可能是假币，如是假币，其重量与真币不同。现在给你一部没有砝码的天平和1枚真币，问题：回答有无假币？如有假币要求找出那枚假币，并指出那枚假币比真币是轻还是重？试用信息量观点分析最少需称多少次保证一定能找出那枚假币，并给出具体称法。（2次？）,设有13枚同值硬币，其中1枚硬币可能是假币，如是假币，其重量与真币不同。现在给你一部没有砝码的天平和1枚真币，问题：回答有无假币？如有假币要求找出那枚假币，并指出那枚假币比真币是轻还是重？试用信息量观点分析最少需称多少次保证一定能找出那枚假币，并给出具体称法。（3次？）,具体称法：1，2，3，4，5（真）(1,2),(3,5),41+2,3+5平衡，5,41+2,3+5不平衡，假设1+23+5比较1,2具体称法：1,2,3,4,5,6,7,8,9,10,11,12,13,14（真）1-4，5-9，10-145-9，10-14平衡，余下1-4，2次5-9，10-14不平衡，假设5-910-14;分3组，(5,6,11),(10,7,8),(9,12,13);比较(5,6,11),(10,7,8)，即可判断是出现在（5，6,10），（11,7，8）还是（9,12,13）组。再称1次就可找出那枚假币并给出是轻还是重？,第三讲,离散无记忆扩展信源,设信源输出的随机序列为序列中的变量Xlx1,x2,xN,离散无记忆信源,离散无记忆信源:,离散信源的序列熵,信源的序列熵,平均符号熵,离散无记忆信源,例:有一个无记忆信源随机变量X(0,1),等概率分布,若以单个符号出现为一事件,则此时的信源熵:,即用1比特就可表示该事件。如果以两个符号出现(L=2的序列)为一事件，则随机序列X(00,01,10,11)，信源的序列熵,即用2比特才能表示该事件。信源的符号熵,离散无记忆信源实例,例:已知离散有记忆信源中各符号的概率为:,设发出的符号只与前一个符号有关,这两个符号的概率关联性用条件概率p(aj|ai)表示,如表,p(aj|ai),离散有记忆信源实例,由p(ai,aj)=p(ai)p(aj|ai)计算得联合概率p(aiaj)如表,离散有记忆信源实例,发二重符号序列的熵,p(aiaj),平均符号熵,符号之间存在关联性,比较,有记忆信源实例,而信源X的信息熵为,条件熵,若信源输出一个L长序列，则信源的序列熵为,平均符号熵为,极限熵,离散有记忆信源的极限熵,（1）条件熵H(XL|X1X2XL-1)随L的增加非递增,离散平稳信源特点,（3）平均符号熵HL(X)随L的增加非递增,（2）L给定时,HL(X)H(XL|X1X2XL-1),（4）,对于平稳信源,故,H(XL|X1X2XL-1)随L非递增,（1）条件熵H(XL|X1X2XL-1)随L的增加非递增,离散平稳信源特点,（3）平均符号熵HL(X)随L的增加非递增,（2）L给定时,HL(X)H(XL|X1X2XL-1),（4）,HL(X)H(XL|X1X2XL-1),根据性质1,随L非递增,故,（1）条件熵H(XL|X1X2XL-1)随L的增加非递增,离散平稳信源特点,（3）平均符号熵HL(X)随L的增加非递增,（2）L给定时,HL(X)H(XL|X1X2XL-1),（4）,HL(X)随L非递增,根据性质2H(XL|X1X2XL-1)HL(X),上式,于是,从而,（1）条件熵H(XL|X1X2XL-1)随L的增加非递增,离散平稳信源特点,（3）平均符号熵HL(X)随L的增加非递增,H1(X)H2(X)H(X)0,（2）L给定时,HL(X)H(XL|X1X2XL-1),（4）,冗余度,表明信源的记忆长度越长，熵就越小；即信源符号的相关性越强，所提供的平均信息量就越小。,为了定量地描述信源的有效性，定义:,相对率,冗余度,小结：,多符号离散信源的熵HL(X),离散无记忆信源,离散有记忆信源,-极限熵,-冗余度,离散信源的互信息,设有两个随机事件X和Y，X取值于信源发出的离散消息集合,Y取值于信宿收到的离散符号集合,信道,干扰源,信源,信宿,互信息定义,X,Y,定义：X和Y之间的平均互信息量定义为,注：由Y提供的关于X的信息量等于由X提供的关于Y的信息量,由定义，可得,仿照自信息量，我们也可以定义非平均互信息量,条件互信息与联合互信息,条件互信息,联合互信息,条件互信息,联合互信息,对称性：非负性：与熵的关系：极值性：,平均互信息性质,平均互信息与熵之间的关系,基本关系式,用维拉图理解,H(X),H(Y),H(Z),A,B,C,D,E,F,G,A+B+C,C,A+B,系统1,系统2,X,Y,Z,两级串联信道的情况X-Y-Z构成Markov链,当消息经过多级处理后，随着处理器数目的增多，输入消息与输出消息之间的平均互信息量趋于变小。,数据处理定理,例设二元对称信道(BSC)的信源空间为：X=0,1;Q(X)=,1-;求I(X;Y),01-p0pp,11-p1,因为已知转移概率，所以利用公式I(X,Y)=H(Y)-H(Y/X)。,H(Y/X)=-q(xi)p(yj/xi)logp(yj/xi)=q(xi)-plogp+(1-p)log(1-p)=H(p),其中：H(p)=-plogp+(1-p)log(1-p),另外：为了求H(Y)，利用w(yj)=q(xi)p(yj/xi)；可得：w(y=0)=(1-p)+(1-)pw(y=1)=p+(1-)(1-p),所以：H(Y)=-(1-p)+(1-)plog(1-p)+(1-)p+p+(1-)(1-p)logp+(1-)(1-p)=H(1-p)+(1-)p),可得平均互信息量为：I(X,Y)=H(1-p)+(1-)p)-H(p),当固定信源先验概率分布时，I(X,Y)是信道转移概率p的下凸函数，如图所示。01/21p从图中可知，当信源固定后，存在一种BSC信道，p=(1-p)=1/2，使在信道输出端获得信息量最小，即等于0。,I(X,Y),H(),根据这个关系，当p值一定，即固定信道，可知I(X,Y)是的上凸函数，其曲线如图：I(X,Y)1-H(p)01/21从图中可知，当BSC信道的信道矩阵固定后，若输入符号集X的概率分布不同，在接收端平均每个符号获得的信息量就不同。只有当输入为等概分布时即，p(0)=p(1)=1/2时，接收端的信息量才为最大值1-H(p)。,基本关系式,证明：,由联合互信息定理，可得,对此系统而言，有,因而,再由条件互信息的非负性，可得,又,因而可得,系统1,系统2,X,