极限熵及马科夫信源.ppt

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为任意整数且ij）,则信源称为二维平稳信源。 上述等式表示任何时刻信源连续发出二个符号的联合概率分布也完全相等。,以此类推，如果各维联合概率分布均与时间起点无关，既当t=i, t=j（i、j为任意整数且ij）时有：,离散平稳信源的数学定义(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信源输出下一个符号的平均不确定性。 以下表所示的信源为例,二维平稳信源的信息熵(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.2 P(aiaj),例如： P(ai=0 ，aj=0 )=1/4， P(ai=0，aj=1)=1/18,例题讲解(2),由概率关系可得,不难求得条件概率P(aj|ai)，把计算结果列于表2.3,表2.3 P(aj|ai),例如： P(aj=0|ai=0)=9/11， P(aj=0|ai=1)=1/8,例题讲解(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|X1X2XN-1)随N的增加是非递增的 N给定时，平均符号熵条件熵 ，即 HN(X)H(XN|X1X2XN-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|X1X2XN-1)H(XN-1|X1X2XN-2) H(XN-2|X1X2XN-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|X1X2XN-1) H(XN|X1X2XN-1)+ H(XN|X1X2XN-1)+ + H(XN|X1X2XN-1) =N H(XN|X1X2XN-1) 所以证得性质(2),即 HN(X)H(XN|X1X2XN-1),同理 NHN(X)=H(X1X2XN) = H(XN|X1X2XN-1)+ H(X1X2XN-1) = H(XN|X1X2XN-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 即有 0HN(X)HN-1(X)HN-2(X)H1(X),故,存在，且处于0和H1(X)之间的某一有限值。,现在证明性质(4),离散平稳信源的极限熵(7),当k取足够大时(k),固定N，而H(X1X2XN-1)和H(XN|X1X2XN-1)为定值，所以,上式中，再令N，因其极限存在,所以得,H(XN+k|X1X2XNXN+k-1)H(XN|X1X2XN-1) H(XN+k-1|X1X2XNXN+k-2)H(XN|X1X2XN-1) H(XN+k-2|X1X2XNXN+k-3)H(XN|X1X2XN-1) H(XN+1|X1X2XNXN+k-1)H(XN|X1X2XN-1),离散平稳信源的极限熵(7),当k取足够大时(k),固定N，而H(X1X2XN-1)和H(XN|X1X2XN-1)为定值，所以,上式中，再令N，因其极限存在,所以得,离散平稳信源的极限熵(8),根据夹逼定理得,由性质(2)，令N，则,HN(X)H(XN|X1X2XN-1),故性质(4)得证,2.6 马科夫信源,2.6.1 马科夫信源的定义 2.6.2 马科夫信源的信源熵,马科夫信源的定义,在非平稳信源中，其输出的符号系列中符号之间的依赖关系是有限的，即任何时刻信源符号发生的概率只与前面已经发出的若干个符号有关。描述这类信源，还需引入状态变量Ei。,设一般信源所处的状态SE1，E2,，EJ，在每一状态下可能的输出的符号XA=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 设信源符号XA=a1，a2，a3，信源所处的状态SE1，E2，E3，E4，E5，各状态之间的转移情况由图2.4给出。,图2.4 状态转移图,E1状态下输出的概率分布为 P(a1|E1)=1/2 P(a2|E1)=1/4 P(a3|E1)=1/4 E2状态下输出的概率分布为 P(a1|E2)=0 P(a2|E2)=1/2 P(a3|E2)=1/2 以此类推得在各状态下的输出概率分布表如下表所示,马科夫信源的判定例解,可见，它们都符合2.6.1定义中的 (1), 另从图中可得：,所以符合2.6.1定义中的 (2),马科夫信源的判定例解,状态的一步转移概率：,可见此信源满足定义2.6.1, 是马可夫信源,马科夫信源的极限熵,马科夫信源的应用,例2.7 有一个二元二阶马可夫信源，其信源符号集为0，1,条件概率定为： P(0|00)=P(1|11)=0.8 P(1|00)=P(0|11)=0.2 P(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.8 P(E2|E1)=P(E3|E4)=0.2 P(E3|E2)=P(E2|E3) =P(E4|E2)=P(E1|E3)=0.5 除此以外，其他的转移概率都为0，由此可见，状态转移概率完全依赖于给定的条件概率。,马科夫信源的判定例解,二元信源发出的一串二元序列就可以变换成状态序列。如二元序列为,马科夫信源的信息熵,一般马科夫信源输出的消息是非平稳的随机序列，它们的各维概率分布随时间的推移可能会改变。 根据马科夫信源的定义，可计算得信源处于某状态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),马科夫信源的信息熵,以例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),马科夫信源的信息熵,求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(XiXi-1)= P(X2|X1） i3，试用马尔科夫信源的图示法画出状态转移图，并计算信息熵,解： 依题意状态转移图如下：,状态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