信息论基础 6.ppt

信息论基础 第 六 讲 马尔可夫信源 马尔可夫信源 马尔可夫信源 马尔可夫信源 马尔可夫信源 马尔可夫信源 马尔可夫信源 马尔可夫信源 马尔可夫信源 马尔可夫信源 马尔可夫信源 m阶马尔可夫信源的熵 m阶马尔可夫信源的熵 m阶马尔可夫信源的熵 信息冗余度及信息变差 信息冗余度及信息变差 信息冗余度及信息变差 本讲结束 例3：对如图所示马尔可夫信源，写出其状态转移矩阵，求出稳态概率分布，并求其极限熵。 解：由图可以写出 其状态转移矩阵为： 1:0.1 0:0.9 1:0.5 0:0.5 1:0.2 0:0.8 S0 S1 S2 稳态概率分布： 解得 条件熵 因此 由于信源符号间的依赖关系使信源的熵减小。它们的依赖关系越长，信源的熵越小。也就是说，信源符号之间依赖关系越强，每个符号提供的信息量就越小。每个符号提供的平均自信息量随着符号间的依赖关系长度的增加而减少。 由离散熵的性质有： H? Hm+1 Hm··· H1H0=Hmax=log(K) 为此，我们引进信源的冗余度（也叫剩余度或多余度）来衡量信源的相关性程度。 信息率：平均一个符号所携带的信息量，称为信息率，记为R。 R =I(X) =H?(X) bit /符号 其中ts表示信源平均发出一个符号的时间间隔。 信息效率：信源单位时间内发出的平均信息量，称为信息效率，记为Rt。 例题3：设离散无记忆信源X=[x1, x2, x3]，P(x1)=1/2, P(x2)=1/3, P(x3)=1/6 。求信息含量效率和冗余度。 例题4：以符号是英文字母的信源为例，计算该类信源的冗余度。 解：英文字母(含空格)出现的概率统计如下： 0.001 Z 0.0175 P 0.054 R 0.001 J,Q 0.021 M 0.055 I 0.002 X 0.0225 F,U 0.059 N 0.003 K 0.023 C 0.063 A 0.008 V 0.029 L 0.0654 O 0.0105 B 0.035 D 0.072 T 0.011 G 0.047 H 0.105 E 0.012 Y,W 0.052 S 0.2 空格 概率 字母 概率 字母 概率 字母 英文字母出现的概率 * * 在许多多符号离散信源中，信源输出的序列中，符号之间的依赖关系是有限的，也就是说，任何时刻信源符号发生的概率只与前面已经发出的有限个符号有关，而与更前面发生的符号无关。如果任何时刻，信源发出的符号只与前面发出的ｍ个符号有关，这样的信源称为ｍ阶有记忆离散信源，或ｍ阶马尔可夫信源。 　　设信源输出的序列为： 信源的联合概率分布满足下述条件： 即这种信源可用马尔可夫链来描述。 　　最简单的马尔可夫信源是1阶马尔可夫信源，即m=1的情形。此时有： 　　若上述条件概率与时间起点无关，则信源输出的符号序列可看成齐次马尔可夫链，这样的信源叫做齐次马尔可夫信源。 　　显然完全平稳的马尔可夫信源是齐次马尔可夫信源，反之，不一定成立。 　　为了方便的分析和处理马尔可夫信源，引入一些新的概念和处理方法。 状态转移矩阵描述了信源的输出特性 状态转移概率矩阵满足如下关系： 为方便，一步状态转移概率常用状态转移图来分析。 t 步状态转移概率矩阵还满足如下关系： m阶马尔可夫信源的极限熵 就等于m阶条件熵，记为 当信源处于状态ei时，发出一个符号所携带的平均信息量记为： 计算m阶马尔可夫信源的熵时，需要知道信源的稳态概率和状态一步转移概率。满足条件时稳态概率可由状态一步转移概率求出。在一般情况下，状态一步转移概率是给定的或是从系统中测定出来的。 4/5 1/5 11(S4) 3/4 1/4 10(S3) 2/3 1/3 01(S2) 1/2 1/2 00(S1) 1 0 符 号 起始状态 4/5 0 2/3 0 11 0 3/4 0 1/2 01 1/5 0 11 0 1/4 10 1/3 0 01 0 1/2 00 10 00 终 止 状 态 起始状态 例1：一个二阶马氏链X?{0,1}，其符号概率如表1，状态变量S?{00,01,10,11} ，求其状态转移概率表，画出其状态转移图，求出各状态的平稳分布概率。 表1 符号条件概率表 表2 状态转移概率表 求得状态转移表如表2所示。方法是：如在状态01时，出现符号0，则将0加到状态01后，再将第一位符号0挤出，转移到状态10，概率为1/3，依此类推。状态转移图如下图所示： 1:1/2 0:1/4 1:2/3 0:1/5 0:1/3 1:3/4 0:1/2 1:4/5 00 11 01 10 4/5 0 2/3 0 11