马尔科夫信源知识讲解

1、马尔科夫信源 马尔可夫信源 一类相对简单的离散平稳有记忆信源 该信源在某一时刻发出字母的概率除与该字母有关外,只与此前发出的有限个字母有关 m阶马尔可夫信源： 信源输出某一符号的概率仅与以前的m个符号有关，而与更前面的符号无关。 条件概率),|(),|(111mLLLLLxxxpxxxp)|()|()|()(),(121121321LLLLLxxpxxpxxpxpxxxxp 一阶马尔可夫信源： 若把有限个字母记作一个状态S，则信源发出某一字母的概率除与该字母有关外，只与该时刻信源所处的状态有关。 信源将来的状态及其送出的字母将只与信源现在的状态有关，而与信源过去的状态无关。 引入状态变量的好处

2、：使得高阶马尔科夫过程可以转化为一阶马尔科夫过程处理。 令si = (xi1, xi2, xim) xi1,xi2, xim (a1, a2, an) 状态集S = s1,s2,sQ Q = nm 信源输出的随机符号序列为：x1, x2,xi-1, xi 信源所处的随机状态序列为：s1, s2,si-1 , si 例：二元序列为01011100 考虑m = 2，Q = nm =22= 4 s1 = 00 s2 = 01 s3 = 10 s4 = 11 变换成对应的状态序列为 s2 s3 s2 s4 s4 s3 s1 设信源在时刻m处于si状态,它在下一时刻(m+1)状态转移到sj的转移概率为：

3、 pij(m) = pSm+1=sj| Sm= si=psj | si pij(m)：基本转移概率（一步转移概率） 若pij(m)与m 的取值无关,则称为齐次马尔可夫链 pij= pSm+1=sj| Sm= si= pS2=sj| S1= si pij具有下列性质： pij0jijp1 若信源处于某一状态si ,当它发出一个符号后,所处状态就变了,任何时候信源处于什么状态完全由前一时刻的状态和发出符号决定。 系统在任一时刻可处于状态空间S = s1,s2,sQ中的任意一个状态,状态转移时,转移概率矩阵QQQQijppppsspP1111)|(QnQnijppppsxpP1111)|( 符号条件

4、概率矩阵 例，如图所示是一个相对码编码器,输入的码Xr(r=1,2,)是相互独立的，取值0或1，且已知P(X=0)=p, P(X=1)=1p=q，输出的码是Yr，显然TXrYrYr-1+,12211YXYXY Yr是一个马氏链,Yr确定后,Yr+1概率分布只与Yr有关,与Yr-1 、Yr-2 等无关,且知Yr序列的条件概率sos1pqqpp00= P(Y2=0/Y1=0)= P(X=0)= p p01= P(Y2=1/Y1=0)= P(X=1)= q p10= P(Y2=0/Y1=1)= P(X=1)= q p11= P(Y2=1/Y1=1)= P(X=0)= p pqqpP 状态转移图 齐次

5、马尔可夫链可以用其状态转移图(香农线图)表示 每个圆圈代表一种状态 状态之间的有向线代表某一状态向另一状态的转移 有向线一侧的符号和数字分别代表发出的符号和条件概率sos11/0.60/0.30/0.4s21/0.20/0.81/0.7 例2 设一个二元一阶马尔科夫信源，信源符号集X=0,1，信源输出符号的条件概率为 p(0|0)=0.25, p(0|1)=0.5, p(1|0)=0.75, p(1|1)=0.5 求状态转移概率，画出状态转移图。12111221222,1,20;1( | ) 0.25, ( | ) 0.5; ( | ) 0.75, ( | ) 0.5mqmqssps sps

6、sps sps s 1：0.750：0.50：0.251：0.5 例3 设有一个二元二阶马尔科夫信源，其信源符号集X=0,1，信源输出符号的条件概率为P(0|00)=p(1|11)=0.8, p(1|00)=0.2p(0|01)=p(0|10)=p(1|01)=p(1|10)=0.5求状态转移概率矩阵，画出状态转移图解：12342,2,400;01;10;11mqmqssss由于信源只可能发出0或者1，所以信源下一时刻只可能转移到其中的两种状态之一。如目前所处状态为00，那么下一时刻信源只可转移到00或者01。而不会转到10或者11状态。114432134242232134( | )( | )

7、 0.8,( | )( | )( | )( | )( | ) 0.5;( | )( | ) 0.2ps sps sps sps sps sps sps sps sps s0：0.80：0.51：0.20：0.51：0.51：0.50：0.21：0.80.8 0.200000.5 0.50.5 0.500000.2 0.8P 齐次马尔可夫链中的状态可以根据其性质进行分类:1、如状态si经若干步后总能到达状态sj，即存在k,使pij(k)0，则称si可到达sj; 若两个状态相互可到达,则称此二状态相通；2、过渡态：一个状态经过若干步以后总能到达某一其他状态，但不能从其他状态返回；3、吸收态：一个只

8、能从自身返回到自身而不能到达其他任何状态的状态；4、常返态：经有限步后迟早要返回的状态；5、周期性的：在常返态中，有些状态仅当k能被某整数d1整除时才有pii(k)0；6、非周期性的：对于pii(k)0的所有k值，其最大公约数为1。s3s2s4s5s1s6周期性的：在常返态中,有些状态仅当k能被某整数d1整除时才有pii(k)0,图中的周期为2；x5:1非周期性的：对于pii(k)0的所有k值，其最大公约数为1。 常返态：经有限步后迟早要返回的状态，x4:1x3:1/2x2:1/2x3:1/2x2:1/2x2:1/2x4:1/4x1:1/4x6:1x6:1/4过渡态过渡态吸收态吸收态相通相通

9、遍历状态： 非周期的、常返的状态,如图中的状态s2和s3 闭集： 状态空间中的某一子集中的任何一状态都不能到达子集以外的任何状态 不可约的： 闭集中除自身全体外再没有其他闭集特殊结论 一个不可约的、非周期的、状态有限的马尔可夫链其k步转移概率pij(k)在k时趋于一个和初始状态无关的极限概率Wj，它是满足方程组 的唯一解； Wj ：马尔可夫链的一个平稳分布， Wj 或或p(sj)就是系统此时处于状态sj的概率。1jjiijijWpWW无论随机点从哪一无论随机点从哪一个状态个状态si出发，当出发，当转移的步数转移的步数k足够足够大时，转移到状态大时，转移到状态sj的概率的概率pij(k)都近都近

10、似于一个常数似于一个常数Wjsos11/0.60/0.30/0.4s21/0.20/0.81/0.70.6 0.40(| )0.30jip ss5 . 0,1429. 0,3571. 018 . 07 . 04 . 02 . 03 . 06 . 0210210221100210WWWWWWWWWWWWWWWpijjiiWW例4 例5：有一个二元二阶马尔可夫信源,其信源符号集为0，1，已知符号条件概率： p(0|00) = 1/2 p(1|00)=1/2 p(0|01) = 1/3 p(1|01)=2/3 p(0|10) = 1/4 p(1|10)=3/4 p(0|11) =

11、 1/5 p(1|11)=4/5 求：信源全部状态及状态转移概率画出完整的二阶马尔可夫信源状态转移图。 求平稳分布概率 121234( )( )() 1/21/2() 1/32/3(|)() 1/43/4(0100011011) 1/54/5jiaassp asss 状态转移概率矩阵 符号条件概率矩阵5/45/100004/34/13/23/100002/12/1)|(43214321sssssspssssij(1)1/2(0)1/2(0)1/3(1)2/300011110s2s1s4s3(1)3/4(0)1/4(0)1/5(1)4/5 稳态分布概率1543251314341212143214

12、42342231131WWWWWWWWWWWWWWWWpijjiiWW74,356,356,3534321WWWW 稳态后的符号概率分布11( )(|) ( )iiip ap as p s221326364426()(|) ( )2353354355735iiip ap as p s1316161492353354355735 一个二元二阶马尔可夫信源,其信源符号集为0,1信源开始时：p(0) = p(1) = 0.5发出随机变量X1。 下一单位时间：输出随机变量X2与X1有依赖关系x2x10100.30.410.70.6p(x2|x1)再下一单位时间：输出随机变量X3与X2X1有依赖关系x3

13、x1 x200011010.40.6p(x3|x1x2) 从第四单位时间开始，随机变量Xi只与前面二个单位时间的随机变量Xi-2Xi-1有依赖关系: p(xi| xi-1 xi-2x2 x1) = p(xi| xi-1 xi-2) (i3) 且 p(xi| xi-1 xi-2) = p(x3| x2x1) (i3)求：信源状态转移情况和相应概率； 画出完整的二阶马尔可夫信源状态转移图； 求平稳分布概率； （4）马尔科夫信源达到稳定后，0和1的分布概率。 解: 设信源开始处于s0状态,并以等概率发出符号0和1,分别到达状态s1和s2 : 若处于s1 ,以

14、0.3和0.7的概率发出0和1到达s3和s4 若处于s2,以0.4和0.6的概率发出0和1到达s5和s600011011(0)0.5(1)0.5(0)0.3(0)0.4(1)0.7(1)0.6s1s2s0s6s5s4s3 信源发完第2个符号后再发第3个及以后的符号。 从第3单位时间以后信源必处在s3 s4 s5 s6四种状态之一。在i3后,信源的状态转移可用下图表示:10110100(0)0.3(0)0.4(1)0.7(0)0.2(1)0.8(1)0.6(0)0.4(1)0.6 状态s1和s5功能是完全相同 状态s2和s6功能是完全相同 可将二图合并成s3s4s5s6s0(0)0.5(1)0.

15、5 s0是过渡状态 s3 s4 s5 s6组成一个不可约闭集,并且具有遍历性。发出0、1概率相同，状态转移变化相同 由题意,此马尔可夫信源的状态必然会进入这个不可约闭集,所以我们计算信源熵时可以不考虑过渡状态及过渡过程。 由 1)()()()()(6.0)(8.0)()(4.0)(2.0)()(7.0)(6.0)()(3.0)(4.0)(6543646645534533spspspspspspspspspspspspspspspsp 得稳态分布概率94)(92)(92)(91)(6543spspspspWj=p(sj) 当马尔可夫信源达到稳定后,符号0和符号1的概率分布：32)(6 . 0)(

16、7 . 0)(8 . 0)(6 . 0) 1 (31)(4 . 0)(3 . 0)(2 . 0)(4 . 0)0(65436543spspspsppspspspspp 信源达到稳定后，信源符号的概率分布与初始时刻的概率分布是不同的，所以，一般马尔可夫信源并非是平稳信源。 但当时齐、遍历的马尔可夫信源达到稳定后，这时就可以看成一个平稳信源。：60( )( ) ( | )ikkkkp xps p x s马尔可夫信源的信息熵马尔可夫信源的信息熵 马尔可夫信源马尔可夫信源),|(),|(111mLLLLLxxxpxxxp121112()lim()lim(|)(|)LLLLLmmHXHXH XX XXH

17、 XX XX 齐次、遍历的马尔可夫信源的熵齐次、遍历的马尔可夫信源的熵( )( ) ( | )iiiHp s H X sXjijijisxpsxpsXH)|(log)|()|(例三状态马尔可夫信源8 . 02 . 005 . 005 . 09 . 001 . 0)|(ijssps2s30/0.50/0.81/0.6s11/0.11/0.21/0.50/0.959/45,59/9,59/518 . 05 . 09 . 02 . 05 . 01 . 0321321332123121WWWWWWWWWWWWWWWpijjiiWW8 . 02 . 005 . 005 . 09 . 001 . 0)|(

18、ijssp符号符号符号/722. 0) 8 . 0 , 2 . 0 (8 . 0log8 . 02 . 0log2 . 0)|(/1) 5 . 0 , 5 . 0 (5 . 0log5 . 05 . 0log5 . 0)|(/469. 0) 9 . 0 , 1 . 0 (9 . 0log9 . 01 . 0log1 . 0)|(321bitHsXHbitHsXHbitHsXH()( )(|)59450.46910.7220.743/595959iiiHp s H X sbit 符号X冗余度冗余度 冗余度(多余度、剩余度) 表示信源在实际发出消息时所包含的多余信息。 冗余度： 信源符号间的相关性

19、。 相关程度越大,信源的实际熵越小 信源符号分布的不均匀性。 等概率分布时信源熵最大。)()()()(log2102XHXHXHXHn 对于有记忆信源,极限熵为H(X)。 这就是说我们需要传送这一信源的信息,理论上只需要传送H(X)即可。但必须掌握信源全部概率统计特性,这显然是不现实的。 实际上,只能算出Hm(X)。那么与理论极限值相比,就要多传送Hm(X)H(X)。)()(XHXHm信息效率冗余度)()(11XHXHm 由于信源存在冗余度,即存在一些不必要传送的信息,因此信源也就存在进一步压缩其信息率的可能性。 信源冗余度越大,其进一步压缩的潜力越大。这是信源编码与数据压缩的前提与理论基础。

20、 在实际通信系统中，为了提高传输效率，往往需要把信源的大量冗余进行压缩，即所谓信源编码。但是考虑通信中的抗干扰问题，则需要信源具有一定的冗余度。因此在传输之前通常加入某些特殊的冗余度，即所谓信道编码，以达到通信系统中理想的传输有效性和可靠性。 例：英文字母： 等概率 H0 = log27 = 4.76比特/符号 不等概率 H1 = 4.03比特/符号 考虑相关性 H2 = 3.32比特/符号 极限熵 H =1.4比特/符号 冗余度71. 076. 4/ )4 . 176. 4(马尔可夫链马尔可夫链马尔可夫链，因安德烈马尔可夫（A.A.Markov，18561922）得名，是数学中具有马尔可夫性

21、质的离散时间随机过程。该过程中，在给定当前知识或信息的情况下，过去（即当期以前的历史状态）对于预测将来（即当期以后的未来状态）是无关的。 马尔可夫链是随机变量X_1,X_2,X_3.的一个数列。这些变量的范围，即他们所有可能取值的集合，被称为“状态空间”，而X_n的值则是在时间n的状态。如果X_n+1对于过去状态的条件概率分布仅是X_n的一个函数，则P(X_n+1=x|X_0, X_1, X_2, ldots, X_n) = P(X_n+1=x|X_n). 这里x为过程中的某个状态。上面这个恒等式可以被看作是马尔可夫性质。 马尔可夫在1906年首先做出了这类过程 。而将此一般化到可数无限状态空间是由柯尔莫果洛夫在1936年给出的。 马尔可夫链与布朗运动以及遍历假说这两个二十世纪初期物理学重要课题是相联系的，但马尔可夫寻求的似乎不仅于数学动机，名义上是对于纵属事件大数法则的扩张。物理马尔可夫链通常用来建模排队理论和统计学中的建模，还可作为信号模型用于熵编码技术，