信息论讲义第六讲PPT讲稿.ppt

《信息论讲义第六讲PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《信息论讲义第六讲PPT讲稿.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、源（续）离散平稳信源（续）对于平稳信源，对于平稳信源，极限熵极限熵是考虑了符号相关性的是考虑了符号相关性的最小值最小值3第3页，共44页，编辑于2022年，星期四3.4 离散平稳信源离散平稳信源_性质（续）性质（续）条件熵H(XL|XL-1)随L的增加是非递增的条件较多的熵必小于或等于条件较少的熵，而条件熵必小于或等于无条件熵。4第4页，共44页，编辑于2022年，星期四(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 离散平稳信源离

3、散平稳信源_性质（续）性质（续）5第5页，共44页，编辑于2022年，星期四(3)HL(X)是L的单调递减函数证明: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页，编辑于2022年，星

4、期四3.4 离散平稳信源离散平稳信源_性质（续）性质（续）7第7页，共44页，编辑于2022年，星期四(4)H(X)=HL(X)=H(XL|X1X2XL-1)证明：证明：HL+k(X)=H(X1X2XL-1)+H(XL|X1X2XL-1)+H(XL+k|X1X2XL+k-1)H(X1X2XL-1)+H(XL|X1X2XL-1)+H(XL|X1X2XL-1)=H(X1X2XL-1)+H(XL|X1X2XL-1)3.4 离散平稳信源离散平稳信源_性质（续）性质（续）8第8页，共44页，编辑于2022年，星期四说明:(i)如何计算极限熵是一个十分困难的问题.(ii)在实际应用中常取有限L下的条件熵

5、H(XL|XL-1)作为H(X)的近似值。(iii)当平稳离散信源输出序列的相关性随着L的增加 迅速减小时，其序列熵的增加量H(XL|XL-1)与相关性有关，相关性很弱，则 H（XL|X1X2XL-1）H（XL|X2 XL-1）=H（XL-1|X1 XL-2），增加量不再变小，所以平均符号熵也几乎不再减小。3.4 离散平稳信源离散平稳信源_性质（续）性质（续）9第9页，共44页，编辑于2022年，星期四 信源发出的符号只与前面的m个符号有关，而与更前面出现的符号无关。用概率意义表达为 p(xt|xt-1,xt-2,xt-3,xt-m,)=p(xt|xt-1,xt-2,xt-m)则根据（4）可得

6、 =H(Xm+1|X1X2Xm)=Hm+1(X)3.4 离散平稳信源离散平稳信源_性质（续）性质（续）10第10页，共44页，编辑于2022年，星期四 3.5 马尔可夫信源马尔可夫信源3.5.1 马尔可夫过程马尔可夫过程3.5.2 有限状态马尔可夫链有限状态马尔可夫链3.5.3 马尔可夫信源马尔可夫信源11第11页，共44页，编辑于2022年，星期四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时，称为

7、时，称为零阶马尔可夫过程零阶马尔可夫过程。零阶马尔可夫过程零阶马尔可夫过程=白噪声过程白噪声过程。12第12页，共44页，编辑于2022年，星期四3.5.2 有限状态马尔可夫链有限状态马尔可夫链 1.定义：定义：设设 xn,n N+为一随机序列，时间参数集为一随机序列，时间参数集N+=0,1,2,其状态空间其状态空间S=S1,S2,SJ有限或可数，有限或可数，若对所有若对所有n N+，有，有则称则称,xn,n N+为为有限状态一阶马尔可夫链。有限状态一阶马尔可夫链。例：蛙跳例：蛙跳 13第13页，共44页，编辑于2022年，星期四3.5.2 有限状态马尔可夫链有限状态马尔可夫链解释解释：(1)

8、S=S1,S2,SJ是状态空间是状态空间 即即xn所有可能取值所有可能取值 14第14页，共44页，编辑于2022年，星期四3.5.2 有限状态马尔可夫链有限状态马尔可夫链(2)转移概率转移概率 m时刻状态时刻状态Si，经，经(n-m)步后转移到状态步后转移到状态Sj的概率的概率15第15页，共44页，编辑于2022年，星期四3.5.2 有限状态马尔可夫链有限状态马尔可夫链 基本转移概率基本转移概率（即一步转移概率）（即一步转移概率）一步转移概率一步转移概率pij(m,m+1)记成记成pij(m)16第16页，共44页，编辑于2022年，星期四3.5.2 有限状态马尔可夫链有限状态马尔可夫链

9、k步步转转移概率移概率k步步转转移概率移概率pij(m,m+k)记记成成p(k)ij(m)17第17页，共44页，编辑于2022年，星期四3.5.2 有限状态马尔可夫链有限状态马尔可夫链 k步转移矩阵步转移矩阵m时刻的时刻的k步转移矩阵步转移矩阵每行之和每行之和都为都为118第18页，共44页，编辑于2022年，星期四states:sunny,cloudy,rainy.state transition matrix:The probability of the weather given the previous days weather.3.5.2 有限状态马尔可夫链有限状态马尔可夫链例：例

10、：19第19页，共44页，编辑于2022年，星期四3.5.2 有限状态马尔可夫链有限状态马尔可夫链(3)K阶马尔可夫链阶马尔可夫链20第20页，共44页，编辑于2022年，星期四3.5.2 有限状态马尔可夫链有限状态马尔可夫链(4)时齐马尔可夫链时齐马尔可夫链（齐次马尔可夫链）（齐次马尔可夫链）若若pij(m)=P(xm+1=Sj|xm=Si)于时刻于时刻m无关。无关。即即pij(m)=pij，则称为，则称为时齐马尔可夫链时齐马尔可夫链（齐次马尔可夫齐次马尔可夫链链）一步转移矩阵一步转移矩阵P为为21第21页，共44页，编辑于2022年，星期四例例+TXrYr101qqpp3.5.2 有限状态

11、马尔可夫链有限状态马尔可夫链22第22页，共44页，编辑于2022年，星期四输入的码输入的码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、Yr-2等无关，等无关，且知且知Yr序列的条件概率为序列的条件概率为 3.5.2 有限状态马尔可夫链有限状态马尔可夫链23第23页，共44页，编辑于2022年

12、，星期四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页，编辑于2022年，星期四3.5.2 有限状态马尔可夫链有限状态马尔可夫链2.切普曼切普曼科尔莫哥洛夫方程（科尔莫哥洛夫方程（C-K方程）方程）命题命题：设：设P(n)是时齐马尔可夫链的是时齐马尔可夫链的n步转移矩阵步转移矩阵(

13、n 1)，P=P(1)是基本转移矩阵，则是基本转移矩阵，则从而有从而有元素元素注意注意：P(n)是经过是经过n步的转移矩阵。步的转移矩阵。25第25页，共44页，编辑于2022年，星期四3.5.2 有限状态马尔可夫链有限状态马尔可夫链3.初始分布初始分布定义定义：设：设P(X0=Si)=pi,且且则称它为马尔可夫链的则称它为马尔可夫链的初始分布初始分布26第26页，共44页，编辑于2022年，星期四3.5.2 有限状态马尔可夫链有限状态马尔可夫链例例120.90.20.10.8机床的状态转移已知本月机床的状态向量 预测机床两个月后的状态 27第27页，共44页，编辑于2022年，星期四3.5.

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

15、限状态马尔可夫链有限状态马尔可夫链31第31页，共44页，编辑于2022年，星期四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页，编辑于2022年，星期四3.5.2 有限状态

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

17、不可约性:对任意一对对任意一对i和和j，都存在至少一个，都存在至少一个k使使 p(k)ij0，这，这就是说从就是说从Si开始，总有可能到达开始，总有可能到达Sj.3.5.2 有限状态马尔可夫链有限状态马尔可夫链34第34页，共44页，编辑于2022年，星期四香农线图香农线图 S1S3S21/21/21/21/21S4S51/21/2可约马氏链可约马氏链1/21/23.5.2 有限状态马尔可夫链有限状态马尔可夫链35第35页，共44页，编辑于2022年，星期四注意注意:(1)S1,S2,S3是三种状态，箭头是指从一个状态转移到另一个状是三种状态，箭头是指从一个状态转移到另一个状态，旁边的数字代表

18、转移概率。这就是香农提出的马尔可夫状态，旁边的数字代表转移概率。这就是香农提出的马尔可夫状态图，也叫香农线图态图，也叫香农线图。(2)由状态由状态S3转移到转移到S1的转移概率的转移概率p(k)31=0，因为一进人，因为一进人状态状态S3就一直继续下去，而不会再转移到其他状态。就一直继续下去，而不会再转移到其他状态。P(k)41=0也是明显的，因也是明显的，因S4和和S1之间没有连接箭头，因此之间没有连接箭头，因此这种链就是可约的。这种链就是可约的。3.5.2 有限状态马尔可夫链有限状态马尔可夫链36第36页，共44页，编辑于2022年，星期四马氏链周期性马氏链周期性 非周期性，就是所有非周期

19、性，就是所有p(k)ii0的的k中没有比中没有比1大的公因子。大的公因子。S1S4S21/21/2周期性马氏链周期性马氏链S31/21/21/21/21/21/23.5.2 有限状态马尔可夫链有限状态马尔可夫链37第37页，共44页，编辑于2022年，星期四注意注意:(1)上图周期为上图周期为2.因为从因为从S1出发再回到出发再回到S1所所需的步数必为需的步数必为2，4，6，.(2)p(n)ij矩阵矩阵 3.5.2 有限状态马尔可夫链有限状态马尔可夫链38第38页，共44页，编辑于2022年，星期四当当k为奇数时为奇数时 当当k为偶数时为偶数时 3.5.2 有限状态马尔可夫链有限状态马尔可夫链

20、39第39页，共44页，编辑于2022年，星期四若起始状态为若起始状态为s1，则，则 经奇数步后，经奇数步后，Sk=Sj的概率为的概率为 经偶数步后经偶数步后 3.5.2 有限状态马尔可夫链有限状态马尔可夫链达不到稳定状态达不到稳定状态 !40第40页，共44页，编辑于2022年，星期四 方程组方程组 是有解？是有解？3.5.2 有限状态马尔可夫链有限状态马尔可夫链41第41页，共44页，编辑于2022年，星期四m时刻总总 结结 有限状态马尔可夫链有限状态马尔可夫链有限状态有限状态马尔科夫链马尔科夫链状态空间状态空间转移概率转移概率基本转移概率基本转移概率pij(m)k步转移概率步转移概率p(

21、k)ij(m)k步转移矩阵步转移矩阵P=p(k)ij(m)齐次马尔科夫链齐次马尔科夫链（时齐马尔科夫链）（时齐马尔科夫链）基本转移概率同时刻基本转移概率同时刻m无关无关（具有（具有平稳平稳转移概率矩阵）转移概率矩阵）C-K方程方程初始分布初始分布任意时刻系统的任意时刻系统的状态分布状态分布42第42页，共44页，编辑于2022年，星期四总总 结结有限状态马尔可夫链有限状态马尔可夫链C-K方程方程初始分布初始分布任意时刻系统的任意时刻系统的状态分布状态分布平稳分布平稳分布（极限分布）（极限分布）稳态分布稳态分布存在定理存在定理唯一性定理唯一性定理存在定理存在定理43第43页，共44页，编辑于2022年，星期四作业作业时齐马尔可夫链计算机模拟时齐马尔可夫链计算机模拟初始分布初始分布基本概率矩阵（含有零元素）基本概率矩阵（含有零元素）逐步进入稳态分布逐步进入稳态分布给出理论计算结果和计算机仿真结果给出理论计算结果和计算机仿真结果44第44页，共44页，编辑于2022年，星期四