uestc信息编码与加密第二章信息论基本概念4.pptVIP

马尔可夫信源 马尔可夫信源的定义： （1）某一时刻信源符号的输出只与当前的信源状态有关，而与以前的状态无关。 (2) 信源状态只由当前输出符号和前一时刻的信源状态唯一确定。 一步转移概率： 转移概率矩阵和状态转移图（香农线图） 状态转移图（香农线图） 圆圈表示状态。 状态之间的有向线段表示状态转移。 有向线段边的符号和数字代表发出的符号和条件概率。 马尔可夫链可以用香农线图表示。(a),(b),(c)分别表示信源含两种字母(D＝2)的一阶、二阶和三阶马尔可夫链的线图。(d),(e)分别表示D＝3和D＝4的一阶马尔可夫链的线图。 例： m阶马尔可夫信源的极限熵 遍历性 对于齐次马尔可夫链，若对于所有状态si ，sj 均存在不依赖于初始状态si 的极限 遍历性的意义 无论从哪个状态出发，当转移步数足够大时，转移到状态sj的概率近似等于一个常数pj。也就是说：马尔可夫链在初始时刻可以处于任意状态，经过足够长时间的状态转移后，它所处的状态与初始状态无关。此时每种状态出现的概率已达到一种平稳分布。 马尔可夫信源定义： 若一信源满足下列两点，即为马尔可夫信源。 输出符号只与当前状态有关； 当前状态和输出唯一决定了下一状态。 例： 设两位二进制码所代表的四个状态分别为 00，01，10，11，其符号转移概率和状态转移概率由下列两表给出： 试求稳定条件下各状态的概率 解：据题意，可画出相应的香农线图 设稳定状态下，各个状态的概率为 P(S0)＝P0， P(S1)＝P1， P(S2)＝P2， P(S3)＝P3 根据图示，可得 P0＝ 1/2P0 ＋ 1/4P2 P1＝ 1/2P0 ＋ 3/4P2 P2＝ 1/3P1 ＋ 1/5P3 P3＝ 4/5P3 ＋ 2/3P1 P0 ＋ P1 ＋ P2 ＋ P3 ＝1 由上面五个方程，可得： P0＝3/35 ， P1＝6/35, P2＝6/35， P3＝4/7 例：有一个一阶马尔可夫信源，已知  试画出该信源的香农线图，并求出信源熵。 解：该信源的香农线图为： 在计算信源熵之前，先用转移概率求稳定状态下二个状态x1和 x2 的概率 和 [小结] 两种有记记忆信源比较 总结:各种离散信源的熵 (1) 发出单个符号消息的离散无记忆信源熵 若信源发出N个不同符号X1，X2，…，Xi，…，XN , 代表N种不同的消息，各个符号的概率分别为 P1， P2，…， Pi，…，PN 因为这些符号相互独立，所以该信源熵为： H（X）＝－ PilogPi [ bit/符号 ] (2)发出符号序列消息的离散无记忆信源熵 发出K重符号序列消息的离散无记忆信源熵为共熵H(XK)，它与单个符号消息信源熵H(X)有如下关系： H(XK)＝KH(X)＝K[－ PilogPi] [ bit/符号序列 ] (3)发出符号序列消息的离散有记忆信源熵 发出K重符号序列消息的离散有记忆信源熵也为共熵H(XK) 当K＝2时 H(X2)＝H(X)＋H(X|X) ∵ H(X|X) H(X) ∴ H(X2) 2H(X) 推广到K重 (4) 发出符号序列消息的马尔可夫信源熵 马尔可夫信源熵是条件熵 若从前一状态Ei转移到后一状态Ej有多种可能性，则信源由状态Ei发出一个符号的熵H（X/i）为 H（X/i） ＝－ P(xj|Ei)logP(xj|Ei) 再进一步对前一状态Ei的全部可能性作统计平均，就得到马尔可夫信源熵 H 为 H＝ P(Ei) H（X/i） ＝－ P(Ei) P(xj|Ei)logP(xj|Ei) [bit/符号] 1.5 各种离散信源的时间熵 信源的时间熵——在单位时间内信源发出的平均信息量，单位 为bit/s. ①发出单个符号消息的离散无记忆信源的时间熵 已知离散无记忆信源各符号的概率空间 由于发出各