信息论讲义第六讲精.ppt-淘文阁

资源描述

《信息论讲义第六讲精.ppt》由会员分享，可在线阅读，更多相关《信息论讲义第六讲精.ppt（44页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、信息论讲义第六讲1第1页，本讲稿共44页第三章第三章离散信源离散信源内容提要内容提要 3.1 信源的数学模型及其分类信源的数学模型及其分类 3.2 离散无记忆信源离散无记忆信源 3.3 离散无记忆信源的离散无记忆信源的扩展信源扩展信源 3.4 离散离散平稳信源平稳信源 3.5 马尔可夫信源马尔可夫信源 2第2页，本讲稿共44页 N次扩展信源熵的次扩展信源熵的性质性质(1)条件熵条件熵随随N的增加是非递增的的增加是非递增的(2)(3)平均符号熵平均符号熵随随N的增加是非递增的。的增加是非递增的。(4)极限熵极限熵存在，且存在，且 3.4 离散平稳信源（续）离散平稳信源（续）对于平稳信源，

2、对于平稳信源，极限熵极限熵是考虑了符号相关性的是考虑了符号相关性的最小值最小值3第3页，本讲稿共44页3.4 离散平稳信源离散平稳信源_性质（续）性质（续）条件熵H(XL|XL-1)随L的增加是非递增的条件较多的熵必小于或等于条件较少的熵，而条件熵必小于或等于无条件熵。4第4页，本讲稿共44页(2)HL(X)H(XL/XL-1)证明:HL(X)=H(X1X2XL)/L =H(X1)+H(X2|X1)+H(XL|X1X2XL-1)/L L H(XL|X1X2XL-1)/L =H(XL/XL-1)3.4 离散平稳信源离散平稳信源_性质（续）性质（续）5第5页，本讲稿共44页(3)HL(X)是L的单

3、调递减函数证明:L HL(X)=H(X1X2XL)=H(X1X2XL-1)+H(XL|X1X2XL-1)=(L-1)HL-1(X)+H(XL|XL-1)(L-1)HL-1(X)+HL(X)所以 HL(X)HL-1(X)3.4 离散平稳信源离散平稳信源_性质（续）性质（续）推广：H(X)H2(X)H1(X)H0(X)H0(X):等概率无记忆信源单个符号的熵，H1(X)为一般无记忆（不等概率）信源单个符号的熵H2(X)为两个符号组成的序列平均符号熵，依次类推。6第6页，本讲稿共44页3.4 离散平稳信源离散平稳信源_性质（续）性质（续）7第7页，本讲稿共44页(4)H(X)=HL(X)=H(XL|

5、关性很弱，则 H（XL|X1X2XL-1）H（XL|X2 XL-1）=H（XL-1|X1 XL-2），增加量不再变小，所以平均符号熵也几乎不再减小。3.4 离散平稳信源离散平稳信源_性质（续）性质（续）9第9页，本讲稿共44页信源发出的符号只与前面的m个符号有关，而与更前面出现的符号无关。用概率意义表达为 p(xt|xt-1,xt-2,xt-3,xt-m,)=p(xt|xt-1,xt-2,xt-m)则根据（4）可得 =H(Xm+1|X1X2Xm)=Hm+1(X)3.4 离散平稳信源离散平稳信源_性质（续）性质（续）10第10页，本讲稿共44页 3.5 马尔可夫信源马尔可夫信源3.5.1 马尔

6、可夫过程马尔可夫过程3.5.2 有限状态马尔可夫链有限状态马尔可夫链3.5.3 马尔可夫信源马尔可夫信源11第11页，本讲稿共44页3.5.1 马尔可夫过程马尔可夫过程1.定义：定义：设设X(t),t T是随机过程，任取是随机过程，任取0 t1t2 tn，ti T,i=1,2,n,若若t1,t2,tn时刻时刻,取值分别为取值分别为x1,x2,xn，并有并有注：注：k=0时，称为时，称为零阶马尔可夫过程零阶马尔可夫过程。零阶马尔可夫过程零阶马尔可夫过程=白噪声过程白噪声过程。12第12页，本讲稿共44页3.5.2 有限状态马尔可夫链有限状态马尔可夫链 1.定义：定义：设设 xn,n N+为一随机

7、序列，时间参数集为一随机序列，时间参数集N+=0,1,2,其状态空间其状态空间S=S1,S2,SJ有限或可数，有限或可数，若对所有若对所有n N+，有，有则称则称,xn,n N+为为有限状态一阶马尔可夫链。有限状态一阶马尔可夫链。例：蛙跳例：蛙跳 13第13页，本讲稿共44页3.5.2 有限状态马尔可夫链有限状态马尔可夫链解释解释：(1)S=S1,S2,SJ是状态空间是状态空间即即xn所有可能取值所有可能取值 14第14页，本讲稿共44页3.5.2 有限状态马尔可夫链有限状态马尔可夫链(2)转移概率转移概率 m时刻状态时刻状态Si，经，经(n-m)步后转移到状态步后转移到状态Sj的概率的概率

8、15第15页，本讲稿共44页3.5.2 有限状态马尔可夫链有限状态马尔可夫链基本转移概率基本转移概率（即一步转移概率）（即一步转移概率）一步转移概率一步转移概率pij(m,m+1)记成记成pij(m)16第16页，本讲稿共44页3.5.2 有限状态马尔可夫链有限状态马尔可夫链 k步步转转移概率移概率k步步转转移概率移概率pij(m,m+k)记记成成p(k)ij(m)17第17页，本讲稿共44页3.5.2 有限状态马尔可夫链有限状态马尔可夫链 k步转移矩阵步转移矩阵m时刻的时刻的k步转移矩阵步转移矩阵每行之和每行之和都为都为118第18页，本讲稿共44页states:sunny,cloudy,

9、rainy.state transition matrix:The probability of the weather given the previous days weather.3.5.2 有限状态马尔可夫链有限状态马尔可夫链例：例：19第19页，本讲稿共44页3.5.2 有限状态马尔可夫链有限状态马尔可夫链(3)K阶马尔可夫链阶马尔可夫链20第20页，本讲稿共44页3.5.2 有限状态马尔可夫链有限状态马尔可夫链(4)时齐马尔可夫链时齐马尔可夫链（齐次马尔可夫链）（齐次马尔可夫链）若若pij(m)=P(xm+1=Sj|xm=Si)于时刻于时刻m无关。无关。即即pij(m)=pij，则

10、称为，则称为时齐马尔可夫链时齐马尔可夫链（齐次马尔可齐次马尔可夫链夫链）一步转移矩阵一步转移矩阵P为为21第21页，本讲稿共44页例例+TXrYr101qqpp3.5.2 有限状态马尔可夫链有限状态马尔可夫链22第22页，本讲稿共44页输入的码输入的码Xr(r=1,2,)是相互独立的，取值是相互独立的，取值0或或1，且已，且已知知p(X=0)=p，p(X=1)=1-p=q，输出的码是，输出的码是Yr，显然有，显然有 Y1=X1，Y2X2 Y1 其中其中表示模表示模2加，那么加，那么Yr就是一个马氏链，因就是一个马氏链，因Yr确确定后，定后，Yr+1分布只与分布只与Yr有关，与有关，与Yr-1

11、、Yr-2等无关，且等无关，且知知Yr序列的条件概率为序列的条件概率为 3.5.2 有限状态马尔可夫链有限状态马尔可夫链23第23页，本讲稿共44页p00=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 说明说明:转移矩阵为转移矩阵为，它与，它与r无关，因而是齐次的。无关，因而是齐次的。3.5.2 有限状态马尔可夫链有限状态马尔可夫链24第24页，本讲稿共44页3.5.2 有限状态马尔可夫链有限状态马尔可夫链2.切普曼切普曼科尔莫哥洛夫方程（

12、科尔莫哥洛夫方程（C-K方程）方程）命题命题：设：设P(n)是时齐马尔可夫链的是时齐马尔可夫链的n步转移矩阵步转移矩阵(n 1)，P=P(1)是基本转移矩阵，则是基本转移矩阵，则从而有从而有元素元素注意注意：P(n)是经过是经过n步的转移矩阵。步的转移矩阵。25第25页，本讲稿共44页3.5.2 有限状态马尔可夫链有限状态马尔可夫链3.初始分布初始分布定义定义：设：设P(X0=Si)=pi,且且则称它为马尔可夫链的则称它为马尔可夫链的初始分布初始分布26第26页，本讲稿共44页3.5.2 有限状态马尔可夫链有限状态马尔可夫链例例120.90.20.10.8机床的状态转移已知本月机床的状态向量

13、预测机床两个月后的状态 27第27页，本讲稿共44页3.5.2 有限状态马尔可夫链有限状态马尔可夫链两个月后机床的状态向量 28第28页，本讲稿共44页3.5.2有限状态马尔可夫链有限状态马尔可夫链4.平稳分布平稳分布定义定义：若齐次马尔可夫链对所有若齐次马尔可夫链对所有i,j存在不依赖于存在不依赖于i的极限的极限且满足且满足则称其具有遍历性，则称其具有遍历性，pj称为称为平稳分布平稳分布29第29页，本讲稿共44页3.5.2有限状态马尔可夫链有限状态马尔可夫链解释解释：当当n充分大时，可用常数充分大时，可用常数pj作为作为pij(n)的近似值的近似值30第30页，本讲稿共44页3.5.2有

14、限状态马尔可夫链有限状态马尔可夫链31第31页，本讲稿共44页3.5.2 有限状态马尔可夫链有限状态马尔可夫链(1)定理一定理一：稳态分布唯一性：稳态分布唯一性设齐次马尔可夫链转移矩阵为设齐次马尔可夫链转移矩阵为P=pij,i,j=1,2,r,稳态稳态分分布布为为Wj,j=1,2,r，则则a.b.W=W1 W2 Wr是是稳态稳态分布矢量，有分布矢量，有W=WPc.当初始分布当初始分布W(0)=W时时，对对于所有的于所有的n有有W(n)=Wd.W是唯一是唯一稳态稳态分布分布5.稳态分布存在定理稳态分布存在定理32第32页，本讲稿共44页3.5.2 有限状态马尔可夫链有限状态马尔可夫链(2)定理二

15、定理二：稳态分布存在：稳态分布存在设设P是齐次马尔可夫链转移矩阵，则是齐次马尔可夫链转移矩阵，则该链稳态分布存在该链稳态分布存在存在一个正整数存在一个正整数N,使使矩阵矩阵PN 中所有元素均大于零中所有元素均大于零33第33页，本讲稿共44页马氏链可约性马氏链可约性:若对所有若对所有 k，都有，都有p(k)ij=0，就意味着一旦出现，就意味着一旦出现 Si以后以后不可能到达不可能到达Sj,也就是不能各态遍历，或者状态中应把也就是不能各态遍历，或者状态中应把Sj取消，这样就成为可约的了。取消，这样就成为可约的了。马氏链不可约性马氏链不可约性:对任意一对对任意一对i和和j，都存在至少一个，都存

16、在至少一个k使使 p(k)ij0，这就，这就是说从是说从Si开始，总有可能到达开始，总有可能到达Sj.3.5.2 有限状态马尔可夫链有限状态马尔可夫链34第34页，本讲稿共44页香农线图香农线图 S1S3S21/21/21/21/21S4S51/21/2可约马氏链可约马氏链1/21/23.5.2 有限状态马尔可夫链有限状态马尔可夫链35第35页，本讲稿共44页注意注意:(1)S1,S2,S3是三种状态，箭头是指从一个状态转移到另一个状是三种状态，箭头是指从一个状态转移到另一个状态，旁边的数字代表转移概率。这就是香农提出的马尔可夫状态，旁边的数字代表转移概率。这就是香农提出的马尔可夫状态图，也叫

17、香农线图态图，也叫香农线图。(2)由状态由状态S3转移到转移到S1的转移概率的转移概率p(k)31=0，因为一进人，因为一进人状态状态S3就一直继续下去，而不会再转移到其他状态。就一直继续下去，而不会再转移到其他状态。P(k)41=0也是明显的，因也是明显的，因S4和和S1之间没有连接箭头，因之间没有连接箭头，因此这种链就是可约的。此这种链就是可约的。3.5.2 有限状态马尔可夫链有限状态马尔可夫链36第36页，本讲稿共44页马氏链周期性马氏链周期性非周期性，就是所有非周期性，就是所有p(k)ii0的的k中没有比中没有比1大的公因子。大的公因子。S1S4S21/21/2周期性马氏链周期性马氏

18、链S31/21/21/21/21/21/23.5.2 有限状态马尔可夫链有限状态马尔可夫链37第37页，本讲稿共44页注意注意:(1)上图周期为上图周期为2.因为从因为从S1出发再回到出发再回到S1所需所需的步数必为的步数必为2，4，6，.(2)p(n)ij矩阵矩阵 3.5.2 有限状态马尔可夫链有限状态马尔可夫链38第38页，本讲稿共44页当当k为奇数时为奇数时当当k为偶数时为偶数时 3.5.2 有限状态马尔可夫链有限状态马尔可夫链39第39页，本讲稿共44页若起始状态为若起始状态为s1，则，则经奇数步后，经奇数步后，Sk=Sj的概率为的概率为经偶数步后经偶数步后 3.5.2 有限状态

19、马尔可夫链有限状态马尔可夫链达不到稳定状态达不到稳定状态 !40第40页，本讲稿共44页方程组方程组是有解？是有解？3.5.2 有限状态马尔可夫链有限状态马尔可夫链41第41页，本讲稿共44页m时刻总总结结有限状态马尔可夫链有限状态马尔可夫链有限状态有限状态马尔科夫链马尔科夫链状态空间状态空间转移概率转移概率基本转移概率基本转移概率pij(m)k步转移概率步转移概率p(k)ij(m)k步转移矩阵步转移矩阵P=p(k)ij(m)齐次马尔科夫链齐次马尔科夫链（时齐马尔科夫链）（时齐马尔科夫链）基本转移概率同时刻基本转移概率同时刻m无关无关（具有（具有平稳平稳转移概率矩阵）转移概率矩阵）C-

20、K方程方程初始分布初始分布任意时刻系统的任意时刻系统的状态分布状态分布42第42页，本讲稿共44页总总结结有限状态马尔可夫链有限状态马尔可夫链C-K方程方程初始分布初始分布任意时刻系统的任意时刻系统的状态分布状态分布平稳分布平稳分布（极限分布）（极限分布）稳态分布稳态分布存在定理存在定理唯一性定理唯一性定理存在定理存在定理43第43页，本讲稿共44页作业作业时齐马尔可夫链计算机模拟时齐马尔可夫链计算机模拟初始分布初始分布基本概率矩阵（含有零元素）基本概率矩阵（含有零元素）逐步进入稳态分布逐步进入稳态分布给出理论计算结果和计算机仿真结果给出理论计算结果和计算机仿真结果44第44页，本讲稿共44页

展开阅读全文