首页 信息论基础理论与应用3极限熵及马科夫信源

信息论基础理论与应用3极限熵及马科夫信源

举报
开通vip

信息论基础理论与应用3极限熵及马科夫信源2.5离散平稳信源 2.5.1离散平稳信源的数学定义 2.5.2二维平稳信源及其信息熵 2.5.3离散平稳信源的极限熵2.5.1离散平稳信源的数学定义 实际情况下,离散信源的输出是空间或时间的离散符号序列,而且在序列中符号之间有依赖关系.此时可用随机矢量来描述信源发出的消息,即其中任一变量Xi表示t=i时刻所发出的信号。信源在此时刻将要发出什么信号取决于以下两点:(1)与信源在t=i时刻随机变量Xi的取值的概率分布P(Xi)有关。(2)与t=i时刻以前信源发出的符号有关,即与条件概率P(xi|xi-1xi-2&he...

信息论基础理论与应用3极限熵及马科夫信源
2.5离散平稳信源 2.5.1离散平稳信源的数学定义 2.5.2二维平稳信源及其信息熵 2.5.3离散平稳信源的极限熵2.5.1离散平稳信源的数学定义 实际情况下,离散信源的输出是空间或时间的离散符号序列,而且在序列中符号之间有依赖关系.此时可用随机矢量来描述信源发出的消息,即其中任一变量Xi表示t=i时刻所发出的信号。信源在此时刻将要发出什么信号取决于以下两点:(1)与信源在t=i时刻随机变量Xi的取值的概率分布P(Xi)有关。(2)与t=i时刻以前信源发出的符号有关,即与条件概率P(xi|xi-1xi-2…)有关,一般情况下,它也是时间t=i的函数,如果信源分布与与时间无关,即时间的推移不引起信源统计特性的变化,设i、j为两任意时刻,若有离散平稳信源的数学定义(1)具有这样性质的信源称为一维平稳信源掷骰子——掷5次后,再掷第6次时,掷出的点数的概率分布与前5次的概率分布相同---------------〉平稳信源离散平稳信源的数学定义(2) 如果一维平稳信源的联合概率分布P(xixi+1)也与时间起点无关,即(i、j为任意整数且i≠j)则信源称为二维平稳信源。 上述等式表示任何时刻信源连续发出二个符号的联合概率分布也完全相等。以此类推,如果各维联合概率分布均与时间起点无关,既当t=i,t=j(i、j为任意整数且i≠j)时有:离散平稳信源的数学定义(3)2.5-1那么,信源是完全平稳的。这种各维联合概率分布均与时间起点无关的完全平稳信源称为离散平稳信源。因为联合概率与条件概率有以下关系:离散平稳信源的数学定义(4)根据2.5-1式可得注意:平稳信源的条件概率与时间起点无关,只与关联长度N有关。如果某时刻发出什么信号与前发出的N个符号有关,那么任何时刻他们的依赖关系是一样的。2.5.2二维平稳信源及其信息熵 二维平稳信源满足以下条件:设有离散一维信源的概率空间为:二维平稳信源的信息熵(1)由此一维信源组成的二维信源的概率空间为:同时还已知连续两个信源符号出现的联合概率分布P(aiaj)(i,j=1,2,…,q),并有:根据信息熵的定义可求得此信源的信息熵为:二维平稳信源的信息熵(2)我们把H(X1X2)称为X1X2的联合熵。此值表示原来信源X输出任意一对消息的共熵,即描述信源X输出长度为2的序列的平均不确定性,或者是信息量。因为信源X发出的符号序列中前后两个符号之间有依赖性,所以首先可以求得已知前面一个符号X1=ai信源输出下一个符号的平均不确定性。以下表所示的信源为例 Xi Xi+1 a1 a2 a3 a4 a1 P(a1/a1) P(a2/a1) P(a3/a1) P(a4/a1) a2 P(a1/a2) P(a2/a2) P(a3/a2) P(a4/a2) a3 P(a1/a3) P(a2/a3) P(a3/a3) P(a4/a3) a4 P(a1/a4) P(a2/a4) P(a3/a4) P(a4/a4)二维平稳信源的信息熵(3)所以,已知前面一个符号X1=ai信源输出下一个符号的平均不确定性,即信息熵为:上式是对下一个符号aj的可能取值进行统计平均。而前一个符号X1取值范围是{a1,a2,a3,a4}中的任一个。对于某一个ai存在一个平均不确定性H(X2|X1=ai)。对所有ai的可能值进行统计平均就得当前面一个符号已知时,再输出后面一个符号的总的平均不确定性二维平稳信源的信息熵(4)此值为二维平稳信源的条件熵根据概率关系展开式,我们可以得到联合熵与条件熵的关系式二维平稳信源的信息熵(5)根据概率关系展开式,我们可以得到联合熵与条件熵的关系式而上式中的第一项可变换为:二维平稳信源的信息熵(6)从上面的推导得:H(X1X2)=H(X1)+H(X2|X1)物理意义:联合熵等于前一个符号出现的熵加上前一个符号已知时后一个符号出现的条件熵。这就是熵的强可加性。同理可以证明:H(X1X2)=H(X2)+H(X1|X2)二维平稳信源的信息熵(7)条件熵与无条件熵的大小关系H(X2|X1)≤H(X2)[证明]在区域[0,1]中,设函数f(x)=-xlogx,它在正区域内是∩型函数,设P(aj|ai)=pij,P(ai)=pi,根据詹森不等式得因其中所以有二维平稳信源的信息熵(8)只有当P(aj|ai)=P(aj)时,等式成立。不难看出H(X1X2)=H(X1)+H(X2|X1)≤H(X1)+H(X2)所以H(X1X2)≤2H(X)物理意义解释:因为当二个符号间有依赖关系时,就意味着在前一个符号发生的条件下,其后面跟着什么符号不是不确定的,而是有的符号发生的可能性大,有的发生的可能性小,从而平均不确定性减少。[例2.6]某离散二维平稳信源并设发出的符号只与前一个符号有关,即可用联合概率P(aiaj)给出它们的关联程度。如下表所示:例题讲解(1)表2.2P(aiaj)例如:P(ai=0,aj=0)=1/4,P(ai=0,aj=1)=1/18 aj ai 0 1 2 0 1/4 1/18 0 1 1/18 1/3 1/18 2 0 1/18 7/36例题讲解(2)由概率关系可得不难求得条件概率P(aj|ai),把计算结果列于表2.3表2.3P(aj|ai)例如:P(aj=0|ai=0)=9/11,P(aj=0|ai=1)=1/8 aj ai 0 1 2 0 9/11 1/8 0 1 2/11 3/4 2/9 2 0 1/8 7/9例题讲解(3)假设信源符号间无依赖性,计算得X的信源熵为在本例中,考虑信源符号间的依赖性时,计算得条件熵或者例题讲解(4)联合熵可见H(X1X2)=H(X1)+H(X2|X1)关于本例的说明: 信源的这个条件熵比信源无依赖时的熵H(X)减少了0.672比特,这正是符号之间有依赖性所造成的结果。 联合熵H(X1X2)表示平均每二个信源符号所携带的信息量。那么平均每一个信源符号携带的信息量近视为H2(X)=H(X1X2)/2=1.205(比特/符号)可见H2(X)<H(X)2.5.3离散平稳信源的极限熵设离散平稳有记忆信源发出的符号序列为(…,X1,X2,…,XN,XN+1,…),假设信源符号之间的依赖长度为N,并已知各维概率分布:并满足符号的相互依赖关系往往不仅存在于相邻的两个符号之间,而且存在于更多的符号之间。所以,对于一般平稳有记忆信源,可以证一些重要结论。为此,本节将从一维信源入手,来探讨多维信源的性质离散平稳信源的极限熵(1)离散平稳信源的一系列联合熵为:为了计算离散平稳信源的信息熵,我们定义N长的信源符号序列中平均每个信源符号所携带的信息量为:此值称为平均符号熵。因信源符号之间的依赖关系长度为N,所以可以求出已知前面N-1个符号时,后面出现一个符号的平均不确定性。也就是已知前面N-1个符号时,后面出现一个符号所携带的信息量,即得一系列条件熵。离散平稳信源的极限熵(2) 对于离散平稳信源,当H1(X)<∞时,具有以下几点性质:条件熵H(XN|X1X2…XN-1)随N的增加是非递增的N给定时,平均符号熵≥条件熵,即HN(X)≥H(XN|X1X2…XN-1)平均符号熵HN(X)随N的增加是非递增的4.存在且则称H∞为平稳信源的极限熵或极限信息量。离散平稳信源的极限熵(3)[证明]根据上文的讨论,同理可以证得H(X3|X1X2)≤H(X3|X2)因为是平稳信源,所以有H(X3|X2)=H(X2|X1)故得H(X3|X1X2)≤H(X2|X1)≤H(X1)由此递推,对于平稳信源有H(XN|X1X2…XN-1)≤H(XN-1|X1X2…XN-2)≤H(XN-2|X1X2…XN-3)≤…≤H(X3|X1X2)≤H(X2|X1)≤H(X1)性质(1)得证离散平稳信源的极限熵(4)[证明]根据性质(1)NHN(X)=H(X1,X2,‥,XN)=H(X1)+H(X2|X1)+‥+H(XN|X1X2‥XN-1)≥H(XN|X1X2…XN-1)+H(XN|X1X2…XN-1)+…+H(XN|X1X2…XN-1)=NH(XN|X1X2…XN-1)所以证得性质(2),即HN(X)≥H(XN|X1X2…XN-1)同理NHN(X)=H(X1X2…XN)=H(XN|X1X2…XN-1)+H(X1X2…XN-1)=H(XN|X1X2…XN-1)+(N-1)HN-1(X)再利用性质(2)NHN(X)≤HN(X)+(N-1)HN-1(X)所以HN(X)≤HN-1(X)即平均符号熵HN(X)随N的增加是非递增的。离散平稳信源的极限熵(5)又因HN(X)≥0即有0≤HN(X)≤HN-1(X)≤HN-2(X)≤…≤H1(X)<∞故存在,且处于0和H1(X)之间的某一有限值。现在证明性质(4)离散平稳信源的极限熵(7)当k取足够大时(k->∞),固定N,而H(X1X2…XN-1)和H(XN|X1X2…XN-1)为定值,所以上式中,再令N->∞,因其极限存在所以得H(XN+k|X1X2‥XN‥XN+k-1)≤H(XN|X1X2…XN-1)H(XN+k-1|X1X2‥XN‥XN+k-2)≤H(XN|X1X2…XN-1)H(XN+k-2|X1X2‥XN‥XN+k-3)≤H(XN|X1X2…XN-1)﹕H(XN+1|X1X2‥XN‥XN+k-1)≤H(XN|X1X2…XN-1)离散平稳信源的极限熵(7)当k取足够大时(k->∞),固定N,而H(X1X2…XN-1)和H(XN|X1X2…XN-1)为定值,所以上式中,再令N->∞,因其极限存在所以得离散平稳信源的极限熵(8)根据夹逼定理得由性质(2),令N->∞,则HN(X)≥H(XN|X1X2…XN-1)故性质(4)得证2.6马科夫信源2.6.1马科夫信源的定义2.6.2马科夫信源的信源熵马科夫信源的定义在非平稳信源中,其输出的符号系列中符号之间的依赖关系是有限的,即任何时刻信源符号发生的概率只与前面已经发出的若干个符号有关。描述这类信源,还需引入状态变量Ei。设一般信源所处的状态S∈{E1,E2,…,EJ,在每一状态下可能的输出的符号X∈A={a1,a2,…,aq}。当信源发出一个符号后,信源所处的状态将发生转移。信源输出的随机符号序列为:x1,x2,…,xL-1,xL,…对应信源所处的随机状态序列为E1,E2,…,EL-1,EL,…在第L时刻,信源处于状态Ei时刻,输出符号ak的概率给定为P(xL=ak|sL=Ei)马科夫信源的定义 定义2.6.1若信源符号输出的状态序列和信源所处的状态序列满足下列两个条件:(2)则此信源称为马科夫信源。马科夫信源的判定例解[例2.7]设信源符号X∈A={a1,a2,a3},信源所处的状态S∈{E1,E2,E3,E4,E5},各状态之间的转移情况由图2.4给出。图2.4状态转移图E1状态下输出的概率分布为P(a1|E1)=1/2P(a2|E1)=1/4P(a3|E1)=1/4E2状态下输出的概率分布为P(a1|E2)=0P(a2|E2)=1/2P(a3|E2)=1/2以此类推得在各状态下的输出概率分布表如下表所示�E2�E1�E4�E3�E5�马科夫信源的判定例解可见,它们都符合2.6.1定义中的(1),另从图中可得:所以符合2.6.1定义中的(2)马科夫信源的判定例解状态的一步转移概率:可见此信源满足定义2.6.1,是马可夫信源�E2�E1�E4�E3�E5�马科夫信源的极限熵马科夫信源的应用[例2.7]有一个二元二阶马可夫信源,其信源符号集为[0,1],条件概率定为:P(0|00)=P(1|11)=0.8P(1|00)=P(0|11)=0.2P(0|01)=P(0|10)=P(1|01)=P(1|10)=0.5可见,此信源任何时候发出什么符号只与前两个符号有关。那么信源有qm=22=4种可能的状态,分别用E1(-—00)、E2(-—01)、E3(—-10)、E4(-—11),根据条件概率,不难画出此二阶马可夫的信源状态图。马科夫信源的应用二阶马科夫信源状态图状态间的转移概率为:P(E1|E1)=P(E4|E4)=0.8P(E2|E1)=P(E3|E4)=0.2P(E3|E2)=P(E2|E3)=P(E4|E2)=P(E1|E3)=0.5除此以外,其他的转移概率都为0,由此可见,状态转移概率完全依赖于给定的条件概率。�00�01�E4�E1�E2�10�11�E3�马科夫信源的判定例解二元信源发出的一串二元序列就可以变换成状态序列。如二元序列为马科夫信源的信息熵一般马科夫信源输出的消息是非平稳的随机序列,它们的各维概率分布随时间的推移可能会改变。根据马科夫信源的定义,可计算得信源处于某状态Ei时,所发出的一个信源符号所携带的平均信息量,即在状态Ei下,发一个符号的条件熵为:我们可以计算马科夫信源的熵,将其与条件熵联系起来马科夫信源的信息熵而对于m阶马科夫信源马科夫信源的信息熵所以以例2.7为例,其在各状态下的概率为状态E1:P(0|E1)=0.8;P(1|E1)=0.2;H(X|Ei)=H(0.8,0.2)状态E2:P(1|E2)=0.5;P(0|E2)=0.5;H(X|E2)=H(0.5,0.5)状态E3:P(1|E3)=0.5;P(0|E3)=0.5;H(X|E3)=H(0.5,0.5)状态E4:P(0|E4)=0.2;P(1|E4)=0.8;H(X|E4)=H(0.2,0.8)�00�01�E4�E1�E2�10�11�E3�马科夫信源的信息熵以例2.7为例,其状态转移表为状态E1:P(E1|E1)=0.8;P(E2|E1)=0.2;P(Ei=3,4|E1)=0;H(X|Ei)=H(0.8,0.2)状态E2:P(E3|E2)=0.5;P(E4|E2)=0.5;P(Ei=1,2|E2)=0;H(X|E2)=H(0.5,0.5)状态E3:P(E1|E3)=0.5;P(E2|E3)=0.5;P(Ei=3,4|E3)=0;H(X|E3)=H(0.5,0.5)状态E4:P(E3|E4)=0.2;P(E4|E4)=0.8;P(Ei=1,2|E4)=0;H(X|E4)=H(0.2,0.8)�00�01�E4�E1�E2�10�11�E3�马科夫信源的信息熵求p(Ei),根据贝耶斯公式以此类推,并结合完备集条件,可得解此方程得:马科夫信源的信息熵所以,此马科夫信源的熵为:例题讲解设有一信源,它在开始时以P(a)=0.6,P(b)=0.3,P(c)=0.1的概率发出X1,如果X1为a时,则X2为a、b、c的概率为1/3;如果X1为b时,则X2为a、b、c的概率为1/3;;如果X1为c时,则X2为a、b的概率为1/2;为c的概率为0。而且后面发出Xi的概率只与Xi-1有关,又P(Xi︱Xi-1)=P(X2|X1)i≥3,试用马尔科夫信源的图示法画出状态转移图,并计算信息熵[解]:依题意状态转移图如下:状态a:P(a|a)=1/3;P(b|a)=1/3;P(c|a)=1/3;H(X|a)=H(1/3,1/3,1/3)状态b:P(a|b)=1/3;P(b|b)=1/3;P(c|b)=0;H(X|b)=H(1/3,1/3,1/3)状态c:P(a|c)=1/2;P(b|c)=1/2;P(c|c)=0;H(X|c)=H(1/2,1/2,0)�b�a�c�例题讲解 根据贝叶斯可得:P(a)=P(a)P(a|a)+P(b)P(a|b)+P(c)P(a|c)P(b)=P(a)P(b|a)+P(b)P(b|b)+P(c)P(b|c)P(c)=P(a)P(c|a)+P(b)P(c|b)+P(c)P(c|c)P(a)+P(b)+P(c)=1 解此方程得:P(a)=P(b)=3/8P(c)=1/4H3=P(a)H(X|a)+P(b)H(X|b)+P(c)H(X|c)=(3/8)H(1/3,1/3,1/3)+(3/8)H(1/3,1/3,1/3)+(1/4)H(1/2,1/2,0)=(3/4)log3+1/4(bit/信源符号) 所以,此马科夫信源的熵为:信息的剩余度熵的相对率:一个信源的信息熵与具有相同符号及的最大熵比值信源的剩余度:等于1减去熵的相对率本章小结 自信息I(ai)=-logP(ai) 信息熵H(X)=–∑p(x)logp(x) 熵函数的性质对称性确定性非负性扩展性可加性递推性极值性本章小结 离散无记忆信源的N次扩展信源的熵H(X)=H(XN)=NH(X) 离散平稳信源的平均符号熵HN(X)=H(X1X2‥XN)/N 离散平稳信源的条件熵H(XN|X1X2‥XN-1) 离散平稳信源的极限熵本章小结 离散平稳信源有H(XN|X1X2…XN-1)≤H(XN-1|X1X2…XN-2)≤H(XN-2|X1X2…XN-3)≤…≤H(X3|X1X2)≤H(X2|X1)≤H(X1)≤logq 时齐遍历的m阶马科夫信源熵
本文档为【信息论基础理论与应用3极限熵及马科夫信源】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: ¥17.0 已有0 人下载
最新资料
资料动态
专题动态
个人认证用户
xrp27580
暂无简介~
格式:ppt
大小:939KB
软件:PowerPoint
页数:0
分类:生活休闲
上传时间:2019-03-07
浏览量:27