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

1、信息论基础理论与应用极限熵及马科夫信源第1页，共50页，2022年，5月20日，1点20分，星期一2.5.1 离散平稳信源的数学定义实际情况下，离散信源的输出是空间或时间的离散符号序列，而且在序列中符号之间有依赖关系.此时可用随机矢量来描述信源发出的消息，即其中任一变量Xi表示t=i时刻所发出的信号。信源在此时刻将要发出什么信号取决于以下两点：(1) 与信源在t=i时刻随机变量Xi的取值的概率分布P(Xi)有关。(2) 与t=i时刻以前信源发出的符号有关，即与条件概率 P(xi|xi-1xi-2) 有关,一般情况下，它也是时间t=i的函数，第2页，共50页，2022年，5月20日，1点20分，

2、星期一如果信源分布与与时间无关，即时间的推移不引起信源统计特性的变化，设i、j为两任意时刻，若有离散平稳信源的数学定义(1)具有这样性质的信源称为一维平稳信源掷骰子掷5次后， 再掷第6次时，掷出的点数的概率分布与前5次的概率分布相同-平稳信源第3页，共50页，2022年，5月20日，1点20分，星期一离散平稳信源的数学定义(2) 如果一维平稳信源的联合概率分布P(xixi+1)也与时间起点无关，即（i、j为任意整数且ij） 则信源称为二维平稳信源。 上述等式表示任何时刻信源连续发出二个符号的联合概率分布也完全相等。以此类推，如果各维联合概率分布均与时间起点无关，既当t=i, t=j（i、j为任

3、意整数且ij）时有：第4页，共50页，2022年，5月20日，1点20分，星期一离散平稳信源的数学定义(3) 2.5-1那么，信源是完全平稳的。这种各维联合概率分布均与时间起点无关的完全平稳信源称为离散平稳信源。因为联合概率与条件概率有以下关系：第5页，共50页，2022年，5月20日，1点20分，星期一离散平稳信源的数学定义(4)根据2.5-1式可得注意： 平稳信源的条件概率与时间起点无关，只与关联长度N有关。如果某时刻发出什么信号与前发出的N个符号有关，那么任何时刻他们的依赖关系是一样的。第6页，共50页，2022年，5月20日，1点20分，星期一2.5.2 二维平稳信源及其信息熵二维平稳

4、信源满足以下条件：设有离散一维信源的概率空间为：第7页，共50页，2022年，5月20日，1点20分，星期一二维平稳信源的信息熵(1)由此一维信源组成的二维信源的概率空间为：同时还已知连续两个信源符号出现的联合概率分布P(aiaj) (i, j=1,2, q) ,并有： 根据信息熵的定义可求得此信源的信息熵为：第8页，共50页，2022年，5月20日，1点20分，星期一二维平稳信源的信息熵(2) 我们把H(X1X2)称为X1X2的联合熵。此值表示原来信源X输出任意一对消息的共熵，即描述信源X输出长度为2的序列的平均不确定性，或者是信息量。 因为信源X发出的符号序列中前后两个符号之间有依赖性，所

5、以首先可以求得已知前面一个符号X1=ai信源输出下一个符号的平均不确定性。 以下表所示的信源为例XiXi+1a1a2a3a4a1P(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)第9页，共50页，2022年，5月20日，1点20分，星期一二维平稳信源的信息熵(3)所以，已知前面一个符号X1=ai信源输出下一个符号的平均不确定性，即信息熵为:上式是对下一个符号aj的可能取值进行统计

6、平均。而前一个符号X1取值范围是a1,a2,a3,a4中的任一个。对于某一个ai存在一个平均不确定性H(X2|X1=ai)。对所有ai的可能值进行统计平均就得当前面一个符号已知时，再输出后面一个符号的总的平均不确定性 第10页，共50页，2022年，5月20日，1点20分，星期一二维平稳信源的信息熵(4)此值为二维平稳信源的条件熵 根据概率关系展开式，我们可以得到联合熵与条件熵的关系式第11页，共50页，2022年，5月20日，1点20分，星期一二维平稳信源的信息熵(5)根据概率关系展开式，我们可以得到联合熵与条件熵的关系式而上式中的第一项可变换为：第12页，共50页，2022年，5月20日，

7、1点20分，星期一二维平稳信源的信息熵(6)从上面的推导得： H(X1X2)=H(X1)+H(X2|X1)物理意义：联合熵等于前一个符号出现的熵加上前一个符号已知时后一个符号出现的条件熵。 这就是熵的强可加性。同理可以证明： H(X1X2)=H(X2)+H(X1|X2)第13页，共50页，2022年，5月20日，1点20分，星期一二维平稳信源的信息熵(7)条件熵与无条件熵的大小关系 H(X2|X1) H(X2)证明 在区域0，1中，设函数f(x)=-xlogx, 它在正区域内是型函数， 设P(aj|ai)=pij,P(ai)=pi, 根据詹森不等式得 因其中所以有第14页，共50页，2022年

8、，5月20日，1点20分，星期一二维平稳信源的信息熵(8)只有当P(aj|ai)=P(aj)时,等式成立。不难看出 H(X1X2)=H(X1)+H(X2|X1)H(X1)+H(X2)所以 H(X1X2)2H(X)物理意义解释：因为当二个符号间有依赖关系时，就意味着在前一个符号发生的条件下，其后面跟着什么符号不是不确定的，而是有的符号发生的可能性大，有的发生的可能性小，从而平均不确定性减少。第15页，共50页，2022年，5月20日，1点20分，星期一例2.6 某离散二维平稳信源并设发出的符号只与前一个符号有关，即可用联合概率P(aiaj)给出它们的关联程度。如下表所示：例题讲解(1)表2.2

9、P(aiaj)ajai012014118011181311820118736例如： P(ai=0 ，aj=0 )=1/4， P(ai=0，aj=1)=1/18第16页，共50页，2022年，5月20日，1点20分，星期一例题讲解(2)由概率关系可得不难求得条件概率P(aj|ai)，把计算结果列于表2.3ajai012091118012113429201879表2.3 P(aj|ai)例如： P(aj=0|ai=0)=9/11， P(aj=0|ai=1)=1/8第17页，共50页，2022年，5月20日，1点20分，星期一例题讲解(3)假设信源符号间无依赖性，计算得X的信源熵为在本例中,考虑信源

10、符号间的依赖性时,计算得条件熵或者 第18页，共50页，2022年，5月20日，1点20分，星期一例题讲解(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)第19页，共50页，2022年，5月20日，1点20分，星期一2.5.3 离散平稳信源的极限熵设离散平稳有记忆信源发出的符号序列为

11、(,X1,X2,XN,XN+1,),假设信源符号之间的依赖长度为N，并已知各维概率分布: 并满足符号的相互依赖关系往往不仅存在于相邻的两个符号之间，而且存在于更多的符号之间。所以，对于一般平稳有记忆信源，可以证一些重要结论。为此，本节将从一维信源入手，来探讨多维信源的性质第20页，共50页，2022年，5月20日，1点20分，星期一离散平稳信源的极限熵(1)离散平稳信源的一系列联合熵为：为了计算离散平稳信源的信息熵，我们定义N长的信源符号序列中平均每个信源符号所携带的信息量为：此值称为平均符号熵。因信源符号之间的依赖关系长度为N，所以可以求出已知前面N-1个符号时，后面出现一个符号的平均不确定

12、性。也就是已知前面N-1个符号时，后面出现一个符号所携带的信息量，即得一系列条件熵。第21页，共50页，2022年，5月20日，1点20分，星期一离散平稳信源的极限熵(2)对于离散平稳信源，当H1(X)时，具有以下几点性质：条件熵H(XN|X1X2XN-1)随N的增加是非递增的N给定时，平均符号熵条件熵 ，即 HN(X)H(XN|X1X2XN-1)平均符号熵HN(X) 随N的增加是非递增的4. 存在且则称H为平稳信源的极限熵或极限信息量。第22页，共50页，2022年，5月20日，1点20分，星期一离散平稳信源的极限熵(3)证明 根据上文的讨论，同理可以证得 H(X3|X1X2)H(X3|X2

13、)因为是平稳信源，所以有 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)得证第23页，共50页，2022年，5月20日，1点20分，星期一离散平稳信源的极限熵(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-

14、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的增加是非递增的。第24页，共50页，2022年，5月20日，1点20分，星期一离散平稳信源的极限熵(5)又因 HN(X) 0即有 0HN(X)HN-1(X)HN-2(X)H1(X),固定N，而H(X1X2XN-1

15、)和H(XN|X1X2XN-1)为定值，所以上式中，再令N，因其极限存在所以得 第26页，共50页，2022年，5月20日，1点20分，星期一 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)第27页，共50页，2022年，5月20日，1点20分，星期一离散平稳信源的极限熵(7)当k取足够大时(k),固定N，而H(X1X2XN-1)和H(XN|X1X2XN-1

16、)为定值，所以上式中，再令N，因其极限存在所以得 第28页，共50页，2022年，5月20日，1点20分，星期一离散平稳信源的极限熵(8)根据夹逼定理得 由性质(2)，令N，则HN(X)H(XN|X1X2XN-1)故性质(4)得证 第29页，共50页，2022年，5月20日，1点20分，星期一2.6 马科夫信源2.6.1 马科夫信源的定义 2.6.2 马科夫信源的信源熵第30页，共50页，2022年，5月20日，1点20分，星期一马科夫信源的定义 在非平稳信源中，其输出的符号系列中符号之间的依赖关系是有限的，即任何时刻信源符号发生的概率只与前面已经发出的若干个符号有关。描述这类信源，还需引入状

17、态变量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)第31页，共50页，2022年，5月20日，1点20分，星期一马科夫信源的定义定义 若信源符号输出的状态序列和信源所处的状态序列满足下列两个条件：(2)则此信源称为马科夫信源。第32页，共50页，2022年，5月20日，1点20分，星期

18、一马科夫信源的判定例解例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以此类推得在各状态下的输出概率分布表如下表所示 第33页，共50页，2022年，5月20日，1点20分，星期一马科夫信源的判定例解可见，它们都符合定义中的 (1), 另从图中可得：所以符合定义中的 (2)第34页，共50页，

19、2022年，5月20日，1点20分，星期一马科夫信源的判定例解状态的一步转移概率： 可见此信源满足定义2.6.1, 是马可夫信源 第35页，共50页，2022年，5月20日，1点20分，星期一马科夫信源的极限熵第36页，共50页，2022年，5月20日，1点20分，星期一马科夫信源的应用例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种可能的状态

20、，分别用E1(-00)、E2(-01)、E3(-10) 、E4(-11)，根据条件概率，不难画出此二阶马可夫的信源状态图。 第37页，共50页，2022年，5月20日，1点20分，星期一马科夫信源的应用二阶马科夫信源状态图状态间的转移概率为： 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，由此可见，状态转移概率完全依赖于给定的条件概率。第38页，共50页，2022年，5月20日，1点20分，星期一马科夫信源的判定例解二元信源发出的一串二元序列

21、就可以变换成状态序列。如二元序列为第39页，共50页，2022年，5月20日，1点20分，星期一马科夫信源的信息熵 一般马科夫信源输出的消息是非平稳的随机序列，它们的各维概率分布随时间的推移可能会改变。 根据马科夫信源的定义，可计算得信源处于某状态Ei时，所发出的一个信源符号所携带的平均信息量，即在状态Ei下，发一个符号的条件熵为：我们可以计算马科夫信源的熵，将其与条件熵联系起来第40页，共50页，2022年，5月20日，1点20分，星期一马科夫信源的信息熵而对于m阶马科夫信源第41页，共50页，2022年，5月20日，1点20分，星期一马科夫信源的信息熵所以以例2.7为例，其在各状态下的概率

22、为状态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)第42页，共50页，2022年，5月20日，1点20分，星期一马科夫信源的信息熵以例2.7为例，其状态转移表为状态E1：P(E1|E1)=0.8; P(E2|E1)=0.2; P(Ei=3,4|E1)=0；

23、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)第43页，共50页，2022年，5月20日，1点20分，星期一马科夫信源的信息熵求p(Ei)，根据贝耶斯公式以此类推，并结合完备集条件，可得解此方程得 ：第44页

24、，共50页，2022年，5月20日，1点20分，星期一马科夫信源的信息熵所以，此马科夫信源的熵为： 第45页，共50页，2022年，5月20日，1点20分，星期一例题讲解设有一信源，它在开始时以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)状