2.2-多符号离散平稳信源的熵PPT推荐.ppt

2.2-多符号离散平稳信源的熵PPT推荐.ppt

《2.2-多符号离散平稳信源的熵PPT推荐.ppt》由会员分享，可在线阅读，更多相关《2.2-多符号离散平稳信源的熵PPT推荐.ppt（85页珍藏版）》请在冰点文库上搜索。

,理解,若单符号离散信源的数学模型为：

则信源X的N次扩展信源用XN来表示，该新信源有nN个元素（消息序列），其数学模型为：

其中q=nN，每个符号i对应于某个由N个xi组成的序列，而i的概率p（i）是对应的N个ai的概率组成的概率序列，考虑到信源是无记忆的，故消息序列的概率为,则N次扩展信源的熵（消息信息的熵）为：

理解,因为是离散无记忆信源,符号序列概率:

设离散信源是由n个符号消息组成的集合X=a1,a2,an若离散信源所发出的消息是集合X中N个符号组成的符号序列XN=（a1,a2,aq），其中aiai1,ai2,ain，则XN称为X的N次扩展，N称为符号序列的长度。

注意：

ai1,ai2,ain可以在a1,a2,an中重复选取。

X的N次扩展的不同的符号序列共有nN个。

【例】X=a1,a2X2=a1a1,a1a2,a2a1,a2a1X3=a1a1a1,a1a1a2,a1a1a2,a1a2a1,x2a2a21符号序列概率P（XN）=P（a1a2aq）=P（a1）P（a2/a1）P（a3/a1a2）P（aq/a1a2,aq-1）2当信源无记忆时P（XN）=P（a1a2,aq）=P（a1）P（a2）P（a3）P（aq）二、无记忆信源的序列熵例:

X=a1,a2,p（a1）=0.2,p（a2）=0.8则H（X）=0.2log20.20.8log20.8=0.464+0.258=0.722bit/符号,X2=a1a1,a1a2,a2a1,a2a1=1,2,3,4p

（1）=p（a1a1）=p（a1）p（a1）=0.04p

（2）=p（a1a2）=p（a1）p（a2）=0.16p（3）=p（a2a1）=p（a2）p（a1）=0.16p（4）=p（a2a2）=p（a2）p（a2）=0.64H（X2）=0.186+0.423+0.423+0.412=1.444=2H（X）或H（X2）=-p（a1）p（a1）logp（a1）p（a1）+p（a1）p（a2）logp（a1）p（a2）+p（a2）p（a1）logp（a1）p（a2）+p（a2）p（a2）logp（a2）p（a2）=-2p（a1）p（a1）+2p（a1）p（a2）logp（a1）+2p（a1）p（a2）+2p（a2）p（a2）logp（a2）=-2p（a1）logp（a1）+p（a2）logp（a2）=2H（X）因p（a1）+p（a2）=1,p（x1）=0.2,p（x2）=0.8,离散无记忆信源X，其信源熵为H（X）。

1.则离散无记忆信源的序列熵：

记为H（XN）H（XN）=NH（X）序列熵的单位：

bit/序列消息或bit/每N个消息2.序列的平均每个符号消息的熵：

记为HN（X）,【例2.2.1】离散平稳无记忆信源X的N次扩展信源的熵为离散信源X的熵的N倍，即H（XN）=NH（X）,证明：

求和是对信源XN中所有nN个元素求和，可以等效成N个求和,而其中的每一个又是对X中的n个元素求和，所以有：

（2.2.6）,（2.2.5）,共有N项，考察其中第一项,因为,同理其余各项均等于H（X），故有,（2.2.7）,【例2.2.2】一离散平稳无记忆信源,解：

先求出此离散平稳无记忆信源的二次扩展信源。

扩展信源的每个元素是信源X的输出长度为N=2的消息序列。

由于扩展信源是无记忆的，故,求此信源的二次扩展信源的熵。

n=3N=2,nN=32=9,根据熵的定义，二次扩展信源的熵为,结论：

计算（无记忆）扩展信源的熵时，不必构造新的信源，可直接从原信源X的熵导出。

即离散平稳无记忆信源X的N次扩展信源的熵为离散信源X的熵的N倍。

思考：

证明二维离散有记忆信源的熵不大于二维平稳无记忆信源的熵？

【例2.2.3】将二维离散平稳有记忆信源推广到N维情况，可证明,证明：

则,表明：

多符号离散平稳有记忆信源X的熵H（X）是X中起始时刻随机变量X1的熵与各阶条件熵之和。

总结：

多符号离散平稳信源实际上就是原始信源在不断地发出符号，符号之间的统计关联关系也并不限于长度N之内，而是伸向无穷远。

所以要研究实际信源，必须求出信源的极限熵，才能确切地表达多符号离散平稳有记忆信源平均每发一个符号提供的信息量。

问题的关键在于极限熵是否存在？

当离散有记忆信源是平稳信源时，从数学上可以证明，极限熵是存在的，且等于关联长度N时，条件熵H（XN/X1X2XN-1）的极限值。

极限熵代表了一般离散平稳有记忆信源平均每发一个符号提供的信息。

一般情况下有下式成立,（2.2.30）,一般情况下，信源在不同时刻发出的符号之间是相互依赖的。

也就是信源输出的平稳随机序列X中，各随机变量Xi之间是有依赖的。

如在汉字组成的中文序列中，只有根据中文的语法、习惯用语、修辞制约和表达实际意义的制约所构成的中文序列才是有意义的中文句子或文章。

所以，在汉字序列中前后文字的出现是有依赖的，不能认为是彼此不相关的。

其他如英文，德文等自然语言都是如此。

这种信源称为有记忆信源。

我们需在N维随机矢量的联合概率分布中，引入条件概率分布来说明它们之间的关联。

2.2.2离散平稳（有记忆）信源的数学模型,平稳随机序列：

是序列的统计性质与时间的推移无关，即信源所发符号序列的概率分布与时间起点无关。

若任意两个不同时刻i和j，信源发出消息的概率完全相同，则称这种信源为一维平稳信源。

即在任何时刻信源发出符号的概率完全相同。

除上述条件外，如果联合概率分布也与时间起点无关，则称信源为二维平稳信源。

这种信源在任何时刻发出两个符号的概率完全相同，即各维联合概率均与时间起点无关的完全平稳信源称为离散平稳信源。

2.2.3离散平稳信源的信源熵和极限熵,离散平稳信源一般是指有记忆的信源，即发出的各个符号之间具有统计关联关系的一类信源。

这种统计关联性可用两种方式表示：

用信源发出的一个符号序列的整体概率，即N个符号的联合概率来反映有记忆信源的特征，这种信源是发出符号序列的有记忆信源。

用信源发出符号序列中各个符号之间的条件概率来反映记忆特征，这是发出符号序列的马尔可夫信源。

一、有记忆二维平稳信源的信息熵二维平稳信源是所发出的随机序列中只有两相邻符号之间有依赖关系的信源。

所以只需给出随机序列的一维和二维概率分布就能很好地从数学上描述离散二维平稳信源。

1.二维平稳信源的数学模型假定,，则矢量,相应的概率分布为,得X的数学模型为,并且,即新的信源也满足概率的归一性。

2.二维平稳有记忆信源的熵根据信源熵的定义有,（2.2.20）,其中,由（2.2.20）式得到这样一个结论：

两个有相互依赖关系的随机变量X1和X2所组成的随机矢量X=X1X2的联合熵H（X），等于第一个随机变量的熵H（X1）与第一个随机变量X1已知的前提下，第二个随机变量X2的条件熵之和H（X2/X1）。

特例：

当X1和X2相互统计独立时，则由概率的性质有,当X1和X2相互统计独立时，二维离散平稳无记忆信源X=X1X2的联合熵H（X），等于第一个随机变量的熵H（X1）与第二个随机变量的熵H（X2）之和。

其中,二、N维离散平稳有记忆信源的熵离散平稳信源有记忆信源的联合熵H（X1X2XN）表示平均每发一个消息序列（由N个符号组成）所提供的信息量。

从数学角度出发，信源平均发一个符号序列所提供的信息量应为称HN（X）为平均符号熵，当N时，平均符号熵取极限值，称为极限熵或极限信息量，即,极限熵是否存在？

如何计算？

对于离散平稳信源，当H1（X）时，具有以下性质：

条件熵H（XN/X1X2XN-1）随N的增加是非递增的；

N给定时，平均符号熵条件熵，即HN（X）H（XN/X1X2XN-1）平均符号熵HN（X）随N增加是非递增的。

说明：

条件较多的熵必小于或等于条件较少的熵，而条件熵必小于等于无条件熵；

对于离散平稳信源，当考虑依赖关系为无限长时，平均符号熵和条件熵都非递增地一致趋于平稳信源的信息熵（极限熵）。

可用条件熵或平均符号熵来作为平稳信源极限熵的近似值。

【例2.2-4】已知离散有记忆信源中各符号的概率空间为现信源发出二重符号序列消息（aiaj），这两个符号的关联性用条件概率p（aj/ai）表示，并由下表给出。

求信源的序列熵和平均符号熵。

p（aj/ai）,条件熵为,单符号信源熵为,p（aj/ai）,解：

发二重符号序列的熵为平均符号熵为比较上述结果可知：

H2（X）H1（X），即二重序列的符号熵值较单符号熵变小了，也就是不确定度减小了，这是由于符号之间存在相关性造成的。

H1（X）=1.543bit/sign,H（X2/X1）=0.872bit/sign,对离散平稳信源，其联合概率具有时间推移不变性，此时有如下结论：

（1）H（XN/XN-1）是N的单调非增函数。

（2）HN（X）H（XN/XN-1）.（3）HN（X）是N的单调非增函数。

（4）当N时，H（X）称为极限熵，又称为极限信息量。

于是有：

式中，H0（X）为等概率无记忆信源单个符号的熵，H1（X）为一般无记忆信源单个符号的熵，H2（X）为两个符号组成的序列平均符号熵，依此类推。

结论：

公式（2.2.30）从理论上定义了平稳离散有记忆信源的极限熵，对于一般的离散平稳信源，实际上求此极限值是相当困难的。

但对于一般的离散平稳信源，由于N值不是很大，所以可用非常接近H（X）的H（XN/X1X2XN-1）的极限值来代替。

因此，可用条件熵H（XN/X1X2XN-1）或者平均符号熵HN（X）取极限时作为平稳信源极限熵的近似值。

2.2.4马尔可夫信源,马尔可夫信源的概念马尔可夫信源的转移概率m阶马尔可夫信源的数学模型m阶马尔可夫信源的极限熵等于m阶条件熵。

m阶马尔可夫信源与消息长度为m的有记忆信源的区别。

如果信源符号表中的数目为n，则由前面出现的m个符号所组成的序列si共有Jnm种,将这些序列看作是状态集S=s1,s2,sJ,则信源在某一时刻出现符号aj的概率就与信源此时所处的状态si有关，用条件概率表示为p（aj/si），i=1,2,.,J；

j=l,2,n。

所有的状态构成状态空间，每种状态以一定的概率发生，其数学模型为,1.马尔可夫信源,显然,当信源符号aj出现后，信源所处的状态将发生变化，并转入一个新的状态。

用转移概率psj/si表示，si,sjS状态转移概率p（sj/si）由信源符号条件概率p（aj/si）确定。

设一般信源所处的状态Ss1,s2,sJ，在每一状态下可能输出的符号为其中ak1ak2akm为符号序列.定义：

若信源输出的符号序列和信源所处的状态满足以下两个条件：

（1）在某一时刻l，信源符号的输出只与此时刻信源所处的状态有关，而与以前的状态及以前的输出符号都无关，这时描述符号之间依赖关系的条件概率为,如果条件概率与时间起点无关，即信源输出的消息可看成为齐次（时齐）马尔可夫链，则此信源称为齐次马尔可夫信源。

当具有齐次性时，有

（2）信源l时刻所处的状态由当前的输出符号和前一时刻l-1信源的状态唯一决定，即则此信源称为马尔可夫信源。

式（2.2.39）中，成立时取1，不成立取0。

条件

（2）表明，若信源处于某一状态si，当它发出一个符号后，所处的状态就变了，一定从状态si转移到另一状态。

显然，状态的转移依赖于发出的信源符号，因此任何时刻信源处在什么状态完全由前一时刻的状态和当前发出的符号决定。

又因条件概率p（ak/si）已给定，所以状态之间的转移有一定的概率分布，并可求得状态的一步转移概率p（sj/si）。

可以用马尔可夫链的状态转移图来描述信源。

在状态转移图上，把J个可能的状态中每一个状态用圆圈表示，然后它们之间用有向线连接，以此表示信源发出某符号后由某一状态转移到另一状态。

并把发出的某符号xk及条件概率p（ak/si）标注在有向线的一侧.对于一阶马尔可夫信源，它的状态转移概率与信源输出符号的条件概率p（ak/si）或符号转移概率相同。

上述定义和描述的是一般的马尔可夫信源。

但常见的是m阶马尔可夫信源，它在任何时刻l，符号发生的概率只与前面m个符号有关，可以把这前面m个符号序列看作信源在此l时刻所处的状态。

因为信源符号集共有n个符号，则信源可以有nm个不同的状态，它们对应于nm个长度为m的不同的符号序列。

2.m阶马尔可夫离散信源的数学模型,m阶马尔可夫信源在任何时刻l，符号发生的概率只与前面m个符号有关，所以可设状态si=（ak1,ak2,akm）。

由于k1,k2,km均可取1,2,n，可得信源的状态集S=s1,s2,sJ，J=nm。

这样一来，条件概率可变换成,条件概率p（ak+1/si）表示任何时刻l信源处在si状态时，发出符号ak+1的概率。

而ak+1可任取a1,a2,an中之一，所以可以简化成ak表示。

因此，m阶马尔可夫离散信源的数学模型可由一组信源符号集和一组条件概率确定：

并满足,当m=1时，任何时刻信源符号发生的概率只与前面一个符号有关，称为一阶马尔可夫信源。

信源发出符号aj后，由符号（aj,aj-1,aj-m+1）组成了新的信源状态sj=（aj,aj-1,aj-m+1）S，这时信源所处的状态也由si转移到sj，它们之间的转移概率叫做一步转移概率，简记为pij（m），它可由状态概率p（sj/si）来确定，表示m时刻系统处于状态si的条件下，经一步转移到状态sj的概率。

对于齐次马尔可夫链，其转移概率具有推移不变性，因此pij（m）可简写为pij。

3.马尔可夫信源的状态转移概率p（sj/si）,马尔可夫信源的状态空间：

或,它是一个具有J2个元素的方阵，表示共有J2个可能的转移概率数目，它的每行元素代表同一个起始状态到J个不同的终止状态的转移概率，每列代表J个不同的起始状态到同一个终止状态的转移概率。

矩阵P中第i行元素对应于从某一个状态s转移到所有状态sj的转移概率，显然矩阵中每一个元素都是非负的，并且每行元素之和均为1。

第j列元素对应于从所有状态si转移到同一个状态sj的转移概率，列元素之和不一定为1。

状态转移矩阵与符号条件概率矩阵是不同的。

在马尔柯夫信源输出的符号序列中，符号之间是有依赖关系的，信源所处的起始状态不同，信源发出的符号序列也不相同。

对m阶马尔柯夫信源，能够提供的平均信息量，即信源的极限熵H，就等于Hm+1。

4.马尔可夫信源的熵,对于齐次、遍历的马尔可夫链，其状态si由唯一决定，因此有,而,即,式中：

p（si）是马尔可夫链的状态极限概率，熵函数H（X/si）表示信源处于某一状态si时发出一个符号的平均不确定性，即也就是说，马尔可夫信源的m阶条件熵Hm+1是信源处于某一个状态si时发出一个符号的平均符号熵H（X/si）在全部状态空间的统计平均值。

即,表明m阶马尔可夫信源的极限熵H就等于m阶条件熵Hm+1.,其中p（si）是m阶马尔可夫信源稳定后的状态极限概率。

由（2.2.30）式可得m阶马尔可夫信源的极限熵,（2.2.35）,（2.2.30）,称这种马尔可夫链是各态历经的。

其极限概率是方程组,满足条件,的惟一解。

这就是有限齐次马尔可夫链的各态历经定理。

定理：

对于有限齐次马尔可夫链，若存在一个正整数l01，对一切i，j=1,2,，nm都有，则对每一个j都存在不依赖于i的极限,（2.2.36）,先求出一步状态转移概率p（sj/si）；

再利用和约束条件求出状态极限概率p（sj）。

（2.2.36）,状态极限概率p（sj）的求法：

根据题意画出状态转移图，判断是否为时齐遍历马尔可夫信源。

根据状态转移图，写出一步转移概率矩阵，计算信源所处状态的极限概率。

根据一步转移概率矩阵和极限概率计算信源的熵。

马尔可夫信源熵的求解步骤：

【例2.2.2】有一个二阶马氏链X0,1，其符号概率如表1，状态变量S（00,01,10,11），求其状态转移概率表，画出其状态转移图，求状态极限概率。

表1符号条件概率表,解：

求出的状态转移概率如表2所示。

方法是：

如在状态01时，出现符号0，则将0加到状态01后，再将第一位符号0挤出，转移到状态10，概率为1/3。

依此类推。

表2状态转移概率,表1符号条件概率表,状态转移图,01,00,10,11,

（1）1/2,（0）1/4,

（1）2/3,（0）1/5,（0）1/3,

（1）3/4,（0）1/2,

（1）4/5,s1,s2,s3,s4是四种状态，箭头是指从一个状态转移到另一个状态，旁边的数字代表转移概率。

这就是香农提出的马尔可夫状态图，也叫香农线图。

s1,s2,s3,s4,求状态极限概率：

P（s1）=P（s1）/2+P（s3）/4P（s2）=P（s1）/2+3P（s3）/4P（s3）=P（s2）/3+P（s4）/5P（s4）=2P（s2）/3+4P（s4）/5P（s1）+P（s2）+P（s3）+P（s4）=1,得,解之得：

P（s1）=3/35P（s2）=6/35P（s3）=6/35P（s4）=4/7由例子可以看出，状态转移矩阵与条件概率矩阵是不同的。

【例2.2.3】设有一马氏链,初始概率分布为p（s1）=0.6，p（s2）=0.3，p（s3）=0.1，p（s1/s1）=p（s2/s1）=p（s3/s1）=1/3，p（s1/s2）=p（s2/s2）=p（s3/s2）=1/3,p（s1/s3）=p（s2/s3）=1/2，p（s3/s3）=0.

（1）写出该信源的状态转移概率矩阵；

（2）画出状态转移图；

（3）求信源的平稳状态分布；

（4）计算平稳信源的熵H。

解：

（1）该信源的状态转移概率矩阵为,

（2）画出状态转移图,（3）求信源的平稳状态分布,（4）计算平稳信源的熵H,或,画出其香农线图，求其状态极限概率分布和符号概率分布。

解：

香农线图为,【例2.2.4】三态马尔可夫信源的状态转移矩阵为,s1s2s3,s1s2s3,稳态状态概率分布：

符号概率分布：

解得：

由图可以写出其状态转移矩阵为,【例2.2.5】如图所示三态马尔可夫信源，写出其状态转移矩阵，画出其状态转移图，求出稳态概率分布，并求其极限熵。

状态极限概率分布：

解得条件熵,因此,或直接由公式计算,问题：

冗余度产生的原因？

最大信源熵熵的相对率（信息效率）的定义？

冗余度的定义？

2.2.5冗余度,一、冗余度产生的原因,冗余度（多余度、剩余度）：

表示给定信源在实际发出消息时所包含的多余信息。

冗余度来自两个方面:

一是信源符号间的相关性。

由于信源输出符号间的依赖关系使得信源熵减小，这就是信源的相关性。

相关程度越大，信源的实际熵就越小，趋于极限熵H（X）；

反之相关程度减小，信源实际熵就增大。

通常希望信源熵尽量的大，即它对外提供的平均信息量越大越好。

另一个方面是信源符号分布的不均匀性。

当等概率分布时信源熵最大。

而实际应用中大多是不均匀分布，使得实际熵减小。

当信源输出符号间彼此不存在依赖关系且为等概率分布时，信源实际熵趋于最大H0（X）。

前几节我们讨论了各类离散信源及其信息熵。

实际的离散信源可能是非平稳的，对于非平稳信源来说，其H不一定存在，但可以假定它是平稳的，用平稳信源的H来近似。

然而，对于一般平稳的离散信源，求H值也是极其困难的。

那么，进一步可以假设它是m阶马尔可夫信源，用m阶马尔可夫信源的平均信息熵Hm+1来近似。

如再进一步简化信源，即可假设信源是无记忆信源，而信源符号有一定的概率分布。

这时，可用信源的平均自信息量H1=H（X）来近似。

二、最大信源熵,由数据处理定理及离散熵的性质有表明信源的记忆长度越长，熵就越小；

即信源符号的相关性越强，所提供的平均信息量就越小。

由此可见，由于信源符号间的依赖关系使信源的熵减小。

它们的前后依赖关系越长，信源的熵越小。

当信源符号间彼此无依赖、等概率分布时，信源的熵才达到最大log2n。

也就是说，信源符号之间依赖关系越强，每个符号提供的信息量就越小。

每个符号提供的平均自信息量随着符号间的依赖关系长度的增加而减少。

对于一般平稳信源来说，极限熵为H，这就是说，如果要传送这一信源的信息，理论上来说只需要有传送H的手段即可。

但实际上我们对它的概率分布不能完全掌握，如果把它近似成m阶马尔可夫信源，则可以用能传送Hm的手段去传送具有H的信源，当然这里面就不太经济。

引进信源的冗余度（也叫剩余度或多余度）来衡量信源的相关性程度.,四、冗余度（相对剩余）,一个信源实际的信息熵与具有同样符号集的最大熵的比值称为相对率，即,其中H是信源的实际熵，,三、熵的相对率（信息效率）,是最大熵.,表示不肯定的程度,因为肯定性不含有信息量，因此是冗余的。

表示肯定性的程度,由冗余度的定义可见，信源的冗余度能够很好地反映信源输出的符号序列中符号之间依赖关系的强弱。

冗余度越大，表示信源的实际熵H越小，表明信源符号之间的依赖关系越强，即符号之间的记忆长度越长；

冗余度越小，表明信源符号之间的依赖关系越弱，即符号之间的记忆长度越短。

当冗余度等于零时，信源的熵就等于极大熵H0，表明信源符号之间不但统计独立无记忆，而且各符号还是等概分布。

因此，冗余度可以用来衡量信源输出的符号序列中各符号之间的依赖程度。

正由于信源存在着冗余度，即存在着不必要传送的信息，因此信源也就存在进一步压缩信息率的可能性。

冗余度越大，压缩潜力也就越大。

可见它是信源编码，数据压缩的前提与理论基础。

信息变差冗余度的公式表明：

信源的符号数一定，符号间的记忆长度越长，极限熵就越小，差值就越大。

称为信息变差。

总结：

通信的效率和可靠性问题往往是一对矛盾，信源编码就是通过减少或消除冗