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

2.5 离散平稳信源 v2.5.1 离散平稳信源的数学定义 v2.5.2 二维平稳信源及其信息熵 v2.5.3 离散平稳信源的极限熵 2.5.1 离散平稳信源的数学定义 v实际情况下，离散信源的输出是空间或时间的离散符号序 列，而且在序列中符号之间有依赖关系.此时可用随机矢量 来描述信源发出的消息，即 其中任一变量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 二维平稳信源及其信息熵 v二维平稳信源满足以下条件： 设有离散一维信源的概率空间为： 二维平稳信源的信息熵(1) 由此一维信源组成的二维信源的概率空间为： 同时还已知连续两个信源符号出现的联合概率分布 P(aiaj) (i, j=1,2, q) ,并有： 根据信息熵的定义可求得此信源的信息熵为 ： 二维平稳信源的信息熵(2) 我们把H(X1X2)称为X1X2的联合熵。此值表示原来信源 X输出任意一对消息的共熵，即描述信源X输出长度为2的 序列的平均不确定性，或者是信息量。 因为信源X发出的符号序列中前后两个符号之间有依赖 性，所以首先可以求得已知前面一个符号X1=ai信源输出 下一个符号的平均不确定性。 以下表所示的信源为例 XiXi+1a1a2a3a4 a1P(a1/a1)P(a2/a1)P(a3/a1)P(a4/a1) a2P(a1/a2)P(a2/a2)P(a3/a2)P(a4/a2) a3P(a1/a3)P(a2/a3)P(a3/a3)P(a4/a3) a4P(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.2 P(aiaj) ajai 012 0141180 111813118 20118736 例如： P(ai=0 ，aj=0 )=1/4， P(ai=0，aj=1)=1/18 例题讲解(2) 由概率关系可得 不难求得条件概率P(aj|ai)，把计算结果列于表2.3 ajai 012 0911180 12113429 201879 表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) 关于本例的说明： 1.信源的这个条件熵比信源无依赖时的熵H(X)减少了 0.672比特，这正是符号之间有依赖性所造成的结果。 2.联合熵H(X1X2)表示平均每二个信源符号所携带的信息 量。那么平均每一个信源符号携带的信息量近视为 H2(X)= H(X1X2)/2=1.205（比特/符号） 可见 H2(X),固定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) 马科夫信源的定义 v定义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/2,0) 例题讲解 v根据贝叶斯可得： 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 v解此方程得： P(a)=P(b)=3/8 P(c)=1/4 H3=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/信源符号） v所以，此马科夫信源的熵为： 信息的剩余度 熵的相对率：一个信源的信息熵与具有相同符 号及的最大熵比值 信源的剩余度：等于1减去熵的相对率 本章小结 v自信息 I(a