第2章-信息论基本概念3.ppt
《第2章-信息论基本概念3.ppt》由会员分享,可在线阅读,更多相关《第2章-信息论基本概念3.ppt(51页珍藏版)》请在三一文库上搜索。
1、3. 离散有记忆信源马尔可夫信源,马尔可夫信源非平稳离散信源中的一类特殊信源。 是由信源发出的各个符号之间的关连性构成一个整体消息。这种关连性用符号的转移概率(条件概率)表示: 如:BOY P(B) P(O|B) P(Y|BO) 若马尔可夫信源发出每个符号都取决于它与前面的K个符号之间的关连性,也就是该信源是以转移概率P(Xi|Xi-k, Xi-k+1, , Xi-1)发出每个符号,这种信源称作K阶马尔可夫信源。,马尔可夫过程: 对于任意的大于2的自然数n,在连续的时间T轴上有n个不同时刻,t1,t2,tn满足,在tn时刻的随机变量Xn与其前面(n1)个时刻的随机变量X1,X2,Xn1的关系可
2、用它们之间的条件概率密度函数来表示,如果满足下式: p(Xn ,tn| Xn 1 , tn1 ,Xn2, tn2,X1,t1) p(Xn ,tn| Xn 1,tn 1) 则这种随机过程称为单纯马尔可夫过程(一阶马尔可夫过程) K阶马尔可夫过程的特征为: p(Xn ,tn| Xn 1 , tn1 ,Xn2, tn2,X1,t1) p(Xn ,tn| Xn1,tn1 ,Xn2, tn2,Xnk,tnk),预备知识:马尔可夫过程、马尔可夫链,马尔可夫链: 当马尔可夫过程的随机变量幅度和时间参数均取离散值时,就称作马尔可夫链。 设随机过程在时间域上Tt1,t2, ,tk1,tk,tn1,tn的n个离散
3、时刻上的状态Xk (k1,2,3, ,n)都是离散型的随机变量,并且有M个不同的取值S1,S2,SM,这M个取值便构成一个状态空间S,SS1,S2,SM.在n个时刻上的n个状态构成一个随机序列(X1,X2, ,Xk1,Xk,Xn1,Xn),对于这个随机序列,若有: 则此序列称为单纯马尔可夫链(一阶马尔可夫链)。 一阶马尔可夫链在tn时刻的取值Xn Sin的概率仅与前一状态Xn-1有关,与其它时刻状态无关,它的记忆长度为两个时刻。若与它前面K个时刻tn-1,tn-2, ,tn-k有关,则为K阶马尔可夫链,它的记忆长度为(K+1)个时刻。 设一阶马尔可夫链在时刻tk1随机序列的取值Xk1Si,而在
4、下一时刻tk,随机序列的取值XkSj,则条件概率为: P(j|i)P(XkSj|Xk1Si ) 因为P(j|i)仅取决于状态Sj和Si ,因此称P(j|i)为由状态Si向Sj的转移概率。,对于具有M个不同的状态空间,M2个转移概率可排成一转移矩阵: 每行元素代表同一起始状态到M个不同终止状态的转移概率; 每列元素代表M个不同起始状态到同一终止状态的转移概率; 显然有: P(j|i)1 (i=1,2, ,M) K阶马尔可夫链每个状态由K个符号组成。若信源符号有D种,则状态数目M为: MDK,马尔可夫链可以用香农线图表示。(a),(b),(c)分别表示信源含两种字母(D2)的一阶、二阶和三阶马尔可
5、夫链的线图。(d),(e)分别表示D3和D4的一阶马尔可夫链的线图。,一、概述 一般情况下,信源输出符号之间的相关性可以追溯到最初的一个符号,而在许多信源的输出符号序列中,符号之间的依赖关系是有限的任何时刻信源符号发生的概率只与前面已经发出的若干个符号有关,而与更前面发出的符号无关。这类信源在输出符号时不仅与符号集有关,还与信源的状态有关。,状态转移图(香农线图),【注】E1、E2、E3是三种状态,箭头是指从一个状态转移到另一个状态,旁边的数字代表发出的某符号和条件概率p(ak/Ei) 。这就是香农提出的马尔可夫状态转移图,也叫香农线图。,二、马尔可夫信源 若信源输出的符号和信源所处的状态满足
6、以下两个条件,则称为马尔可夫信源:,【注】上述条件表明,若信源处于某一状态Ei,当它发出一个符号后,所处的状态就变了。状态的转移依赖于所发出的信源符号,因此任何时刻信源处在什么状态完全由前一时刻的状态和发出的符号决定。又因条件概率p(ak/Ei)已给定,所以状态之间的转移有一定的概率分布,并可求出状态的一步转移概率p(Ej/Ei)。,例:设某信源符号XA=a1,a2,a3,信源所处的状态 SE=E1,E2,E3,E4,E5。各状态之间的转移情况如下 图所示,请判断这是否是一个马尔可夫信源?,解:(1)信源在Ei状态下输出符号ak的条件概率p(ak/Ei)用矩阵 表示为:,(2)该信源在l时刻所
7、处的状态由当前的输出符号与前一时刻(l-1) 信源的状态唯一决定:,此信源满足马尔可夫的两个条件,所以是马尔可夫信源,并且是齐次马尔可夫信源。,三、 m阶马尔可夫信源 一般有记忆信源: 发出的是有关联性的各符号构成的整体消息,即输出的是符号序列,并用符号间的联合概率描述这种关系。 马尔可夫信源: 用符号之间的转移概率(条件概率)来描述这种关联关系。即马尔可夫信源是以转移概率输出每个信源符号。,m阶马尔可夫信源 在某一时刻l,符号出现的概率仅与前面已出现的m个符号有关,可以把这前面m个符号序列看成信源在l时刻所处的状态。若每符号取值q种,则共有qm种状态,每种状态对应一个m长(q 进制)序列 ,
8、这种状态序列符合马尔可夫链的性质,可用马氏链来描述,这种信源称为m阶马尔可夫信源。数学模型:,【注】当m=1时,为一阶马尔可夫信源。,马尔可夫信源熵,设状态,信源处于状态,时,再发出下一个符号,此时,符号序列,就组成了新的信源状态,,这时信源所处的状态由,转移到,【注】可见求解马尔可夫信源条件熵关键是要得到,【注】 上述定理说明,有限齐次、遍历马尔可夫链信源,在初始时刻可以处在任意时刻,然后状态之间可以转移,经过足够长时间之后,信源处于什么状态已与初始状态无关。 状态极限概率方程组可写为:,例1 设有二元二阶马尔可夫信源:,【结论】 信源达到稳定后,信源符号的概率分布与初始概率不同,因此一般马
9、尔可夫信源并非是平稳信源。但当时齐、遍历的马尔可夫信源达到稳定后,就可看成一个稳定信源。 计算信源的信息熵,对于平稳信源须知道信源的各维概率分布,而对于m阶马尔可夫信源,只要知道与前面m个符号有关的条件概率,因此一般信源可用m阶马尔可夫信源来近似。,例2:有一个马尔可夫信源,已知 试画出该信源的香农线图,并求出信源熵。 解:该信源的香农线图为: 在计算信源熵之前,先用转移概率求稳定状态下二个状态x1和 x2 的概率 和 可得: 马尔可夫信源熵,例3:一阶马尔可夫信源的状态图如下,信源的符号集为0,1,2,并定义p+q=1。 (1) 求信源平稳后的状态极限概率分布; (2) 求此信源的熵; (3
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息论 基本概念
链接地址:https://www.31doc.com/p-2566034.html