信息与通信信息论与编码 信源与信息熵

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,信息与通信信息论与编码 信源与信息熵,2.1 信源的描述和分类,2.2 离散信源熵和互信息,2.3 离散序列信源熵,2.4 连续信源的熵和互信息,2.5 冗余度,内容,2,2.3,离散序列信源熵,3,2.3,离散序列信源熵,前面讨论了单个消息符号的离散信源熵，并较详细地讨论了它的性质。然而实际信源的输出往往是空间或时间的离散随机序列，其中有无记忆的离散信源熵序列，当然更多的序列是有记忆的，即序列中的符号之间有相关性。此时需要用联合概率分布函数或条件概率分布函数来描述信源发出的符号间的关系。这里讨论离散无记忆序列信源和两类较简单的离散有记忆序列信源(平稳序列和齐次遍历马尔可夫链信源)。,4,离散,信源,离散,无记忆,信源,离散,有记忆,信源,发出单个符号的无记忆信源,发出符号序列的无记忆信源,发出符号序列的有记忆信源,发出符号序列的马尔可夫信源,2.3.1,离散无记忆信源的序列熵,发出,单个符号,的信源,指信源每次只发出一个符号代表一个消息；,发出,符号序列,的信源,指信源每次发出一组含二个以上符号的符号序列代表一个消息。,5,发出,符号序列,的信源,发出,单个符号,的信源,6,离散无记忆信源的序列熵,随机序列的概率为,设信源输出的随机序列为,X,=(X,1,X,2,X,l,X,L,),序列中的单个符号变量X,l,x,1,x,2,x,n,l =,1,2,L,.,X,称为离散无记忆信源X的,L次扩展信源,7,离散无记忆信源的序列熵,信源的序列熵为,随机序列的概率为,8,离散无记忆信源的序列熵,当信源,无记忆,时,信源的序列熵,9,离散无记忆信源的序列熵,假设又满足平稳特性,即与序号l无关时：,信源的序列熵,平均每个符号(消息)熵为,离散无记忆信源平均每个符号的符号熵,H,L,(,X,)等于单个符号信源的符号熵,H,(,X,),10,例:有一个无记忆信源随机变量X(0,1),等概率分布,假设以单个符号出现为一事件,那么此时的信源熵:,即用 1比特就可表示该事件。,如果以两个符号出现(L=2的序列)为一事件，那么随机序列X(00,01,10,11)，信源的序列熵,即用2比特才能表示该事件。,信源的,符号熵,11,例,:有一离散平稳,无记忆,信源,求：,二次,扩展信源的,熵,X,2,信源,的元素,a,1,a,2,a,3,a,4,a,5,a,6,a,7,a,8,a,9,对应的,消息序列,x,1,x,1,x,1,x,2,x,1,x,3,x,2,x,1,x,2,x,2,x,2,x,3,x,3,x,1,x,3,x,2,x,3,x,3,概率,p,(,a,i,),1/4,1/8,1/8,1/8,1/16,1/16,1/8,1/16,1/16,12,平均每个符号(消息)熵为,信源的序列熵,序列熵为,13,离散有记忆信源序列熵,对于有记忆信源,就不像无记忆信源那样简单,它必须引入条件熵的概念,而且只能在某些特殊情况下才能得到一些有价值的结论。,对于由两个符号组成的联合信源,有以下结论:,当前后符号无依存关系时,有以下推论：,14,信源的联合熵(即前后两个符号(X1,X2)同时发生的不确定度)等于信源发出前一个符号X1的信息熵加上前一个符号X1时信源发出下一个符号X2的条件熵。,对于一般的有记忆信源如文字、数据等，它们输出的不是单个或两个符号，而是由有限个符号组成的序列，这些输出符号之间存在着相互依存的关系。可依照上述结论来分析序列的熵值。,离散有记忆信源序列熵,15,假设信源输出一个L长序列,那么信源的序列熵为,平均每个符号的熵为：,假设当信源退化为无记忆时:,若进一步又满足平稳性时,16,a,0,a,1,a,2,a,0,9/11,2/11,0,a,1,1/8,3/4,1/8,a,2,0,2/9,7/9,例2-12离散有记忆信源中各符号的概率空间为:,设发出的符号只与前一个符号有关,这两个符号的概率关联性用,条件概率,p,(,a,j,|a,i,),表示,如表.,p,(,a,j,|a,i,),求离散信源的,序列熵,和,平均每个符号熵,?,17,由,p,(,a,i,a,j,) =,p,(,a,i,),p,(,a,j,|,a,i,),计算得,联合概率,p,(,a,i,a,j,),如表,a,0,a,1,a,2,a,0,1/4,1/18,0,a,1,1/18,1/3,1/18,a,2,0,1/18,7/36,当信源符号之间,无依赖性,时,信源X的信息熵为,当考虑符号之间,有依赖性,时,计算得条件熵,H(X,2,| X,1,)H(X),信源的条件熵比无依赖时的熵H(X)减少了0.671比特,这正是因为符号之间有依赖性所造成的结果。,18,联合熵H(X,1,X,2,)表示平均每二个信源符号所携带的信息量。,我们用1/2H(X,1,X,2,)作为二维平稳信源X的信息熵的近似值。那么平均每一个信源符号携带的信息量近似为:,符号之间存在关联性,发,二重符号,序列的熵,比较,或,19,离散平稳信源,对于离散平稳信源,有以下结论：, 条件熵H (XL|XL-1) 随L的增加是非递增的,条件较多的熵必小于或等于条件较少的熵，而条件熵必小于或等于无条件熵。,平稳性，联合概率具有时间推移不变性。,20,H,L,(,X,)是,L,的单调非增函数,H,L,(,X,),H,L-1,(,X,),H,(,X,)称为平稳信源的,极限熵,或,极限信息量,H,0,(,X,),H,1,(,X,),H,2,(,X,),H,(,X,),L,给定时,平均符号熵条件熵：,H,L,(,X,),H,(,X,L,|,X,L-,1,),推广结论3可得：,不等,概率,无记忆,信源单个符号的熵,两个符号组成的,序列平均符号熵,等概率,无记忆信源,单个符号的熵,21,马尔可夫信源的信息熵,马尔可夫信源,齐次、遍历的马尔可夫信源的熵,马尔可夫链的稳态分布,22,s,2,s,3,1,s,1,1,0,例2-13,三状态马尔可夫信源,0,23,24,2.5 冗余度,25,冗余度,冗余度,(多余度、剩余度),表示信源在实际发出消息时所包含的多余信息。,冗余度：,信源符号间的相关性。,相关程度越大,信源的实际熵越小,信源符号分布的不均匀性。,等概率分布时信源熵最大。,26,冗余度,对于有记忆信源,极限熵,为H,(X)。,这就是说我们需要传送这一信源的信息,理论上只需要传送H,(X)即可。但必须掌握信源全部概率统计特性,这显然是不现实的。,实际上,只能算出H,m,(X)。那么与理论极限值相比,就要多传送H,m,(X)H,(X)。,为了定量地描述信源的有效性,定义:,信息效率,冗余度,27,冗余度,由于信源存在冗余度,即存在一些不必要传送的信息,因此信源也就存在进一步压缩其信息率的可能性。,信源冗余度越大,其进一步压缩的潜力越大。这是信源编码与数据压缩的前提与理论根底。,在实际通信系统中，为了提高传输效率，往往需要把信源的大量冗余进展压缩，即所谓信源编码。但是考虑通信中的抗干扰问题，那么需要信源具有一定的冗余度。因此在传输之前通常参加某些特殊的冗余度，即所谓信道编码，以到达通信系统中理想的传输有效性和可靠性。,28,冗余度,例,：英文字母：,等概率,H,0,不等概率,H,1,考虑相关性,H,2,极限熵,H,冗余度,英语文章有71%是由语言构造定好的,只有29%是自由选择,29,习题,2-26,2-30,30,本章小结,31,信源的描述,一个离散信源发出的各个符号消息的集合为：,它们的概率分别为,p,(,x,i,):,x,i,的,先验概率,单符号,离散,信源的数学模型,概率空间,a,b,c,z,32,00,01,11,10,状态转移,概率矩阵,符号,条件概率矩阵,(1)1/2,(1)3/4,(0)1/3,(0)1/4,(0)1/2,(0)1/5,(1)2/3,(1)4/5,s,2,s,1,s,4,s,3,马尔可夫信源,33,稳态分布概率,稳态后的符号概率分布,34,离散信源熵和互信息,问题：,什么叫不确定度？,什么叫自信息量？,什么叫平均不确定度？,什么叫信源熵？,什么叫平均自信息量？,什么叫条件熵？,什么叫联合熵？,联合熵、条件熵和熵的关系是什么？,35,离散信源熵和互信息,问题：,什么叫后验概率？,什么叫互信息量？,什么叫平均互信息量？,什么叫疑义度？,什么叫噪声熵或散布度？,数据处理定理是如何描述的？,熵的性质有哪些？,36,自信息量,设离散信源X，其概率空间为,I,(,x,i,),含义,:,当事件,x,i,发生以,前,表示事件,x,i,发生的,不确定性,当事件,x,i,发生以,后,表示事件,x,i,所含有的,信息量,37,自信息量,不确定度,定义：,随机事件(符号)的不确定度在数量上等于它的自信息量。,说明:,两者的单位一样，但含义却不一样。,具有某种概率分布的随机事件不管发生与否，都存在不确定度，不确定度表征了该事件的特性，而自信息量是在该事件发生后给予观察者的信息量。,38,自信息量,I,(,x,i,)的特性,：,I,(,x,i,)是非负值, 当p(,x,i,) = 1时，,I,(,x,i,) = 0, 当p(,x,i,) = 0时，,I,(,x,i,) =,I,(,x,i,)是先验概率,p,(,x,i,)的,单调递减函数,，即,当p(,x,1,)p(,x,2,)时，,I,(,x,1,),I,(,x,2,),两个独立事件的联合信息量等于它们分别的信息量之和。,即统计独立信源的信息量等于它们分别的信息量之和。,39,自信息量,自信息量,条件自信息量,联合自信息量,40,离散信源熵,自信息量,I,(,xi,)只是表征信源中,各个符号,x,i,的不确定度，而一个信源总是包含着多个符号消息，各个符号消息又按概率空间的先验概率分布，因而各个符号的自信量就不同。,所以，自信息量,I,(,xi,)是与概率分布有关的一个随机变量，不能作为,信源总体,的信息量度。对这样的随机变量只能采取,求平均,的方法。,信息熵,：,从,平均,意义上来表征信源的,总体,信息测度的一个量。,41,离散信源熵,离散信源熵H(X),信源熵具有以下三种物理含意：,信息熵H(X)表示,信源输出后,每个离散消息所提供的,平均信息量,。,信息熵H(X)表示,信源输出前,信源的,平均不确定性。,信息熵H(X)反映了变量X的,随机性 。,42,例27,该信源X输出符号只有两个,设为0和1输出符号发生的概率分别为p和q，pq=l。即信源的概率空间为,那么二元信源熵为,H(X)= plogpqlogq,= plogp (1 p)log(1p),=H(p),43,信源信息熵H(X)是概率p的函数,通常用H(p)表示p取值于0，1区间。 H(p)函数曲线如下图。,如果二元信源的输出符号是确定的,即p=1或q=1,那么该信源不提供任何信息。当二元信源符号0和1以等概率发生时,信源熵到达极大值,等于1比特信息量。,44,信源熵,无条件熵,条件熵,在给定,y,j,条件下，,x,i,的条件自信息量为,I,(,x,i,|,y,j,), X 集合的条件熵H(X|y,j,)为,在给定,Y,(即各个y,j,)条件下,X集合的,条件熵,H(X|Y),45,信源熵,H(X,Y)H(,X,)H(Y|,X,),H(X,Y)H(,Y,)H(X|,Y,),无条件熵、条件熵、联合熵之间的关系,联合熵,联合熵,是联合符号集合(X,Y)上的,每个元素对,(,x,i,y,j,)的自信息量的概率加权统计平均值。,表示,X 和Y,同时,发生,的不确定度。,46,互信息,互信息,定义为,x,i,的后验概率与先验概率比值的对数,互信息,I,(,x,i,;,y,j,),表示接收到某消息,y,j,后获得的关于事件,x,i,的信息量。,47,平均互信息,平均互信息,定义,信息,= 先验不确定性后验不确定性,= 不确定性减少的量,Y未知,X 的不确定度为H(X),Y,X 的不确定度变为H(X |Y),48,维拉图,H(X|Y),H(X),H(Y),H(XY),H(Y|X),I(X;Y),49,条件熵,H(X|Y),：,信道疑义度，损失熵,信源符号通过有噪信道传输后所引起的信息量的损失。,信源X的熵等于接收到的信息量加上,损失掉,的信息量。,H(Y|X),：,噪声熵，散布熵,它反映了信道中,噪声源,的不确定性。,输出端信源Y 的熵H(Y)等于接收到关于X的信息量I(X;Y)加上H(Y|X),这完全是由于信道中噪声引起的。,50,收发两端的熵关系,I(X;Y),H(X),H(Y),H(X/Y)疑义度,H(Y/X)噪声熵,51,数据处理定理,数据处理定理说明：,当对信号、数据或消息进展多级处理时,每处理一次,就有可能损失一局部信息,也就是说数据处理会把信号、数据或消息变成更有用的形式，但是绝不会创造出新的信息,这就是所谓的信息不增原理。,52,熵的性质,H(X)H(p1，p2，pn)0,式中等号只有在pi =1时成立。,H(p1，p2，pn) = H(p2，p1，pn),例如以下信源的熵都是相等的：,53,熵的性质,H(X)H(p1，p2，pn)0,只要信源符号中有一个符号出现概率为1,信源熵就等于零。,4.极值性(香农辅助定理),对任意两个消息数一样的信源,54,熵的性质,离散无记忆信源输出M个不同的信息符号,当且仅当各个符号出现概率相等时即( p,i,1/M),熵最大,。,6.条件熵小于无条件熵,55,离散无记忆信源的序列熵,信源的序列熵,平均每个符号(消息)熵为,56,离散有记忆信源的序列熵,假设信源输出一个L长序列,那么信源的序列熵为,平均每个符号的熵为：,57,离散平稳信源,对于离散平稳信源,有以下结论：, 条件熵H (XL|XL-1) 随L的增加是非递增的,条件较多的熵必小于或等于条件较少的熵，而条件熵必小于或等于无条件熵。,58,离散平稳信源,H,L,(,X,)是,L,的单调非增函数,H,L,(,X,),H,L-1,(,X,),H,称为平稳信源的,极限熵,或,极限信息量,H,0,(,X,),H,1,(,X,),H,2,(,X,),H,(,X,),L,给定时,平均符号熵条件熵：,H,L,(,X,),H,(,X,L,|,X,L-,1,),推广结论3可得：,59,马尔可夫信源的信息熵,齐次、遍历的马尔可夫信源的熵,马尔可夫信源,60,冗余度,冗余度,(多余度、剩余度),表示信源在实际发出消息时所包含的多余信息。,冗余度,：,信源符号间的相关性。,信源符号分布的不均匀性。,信息效率,冗余度,61,概率论根底,无条件概率、条件概率、联合概率的性质和关系,62,概率论根底,无条件概率、条件概率、联合概率的性质和关系,63,谢谢大家！,