《信息论讲义_第六讲》由会员分享，可在线阅读，更多相关《信息论讲义_第六讲（44页珍藏版）》请在金锄头文库上搜索。
1、信息理论基础 （第六讲）,授课教师：于 泽 电子信息工程学院201教研室,2,第三章 离散信源,内容提要3.1 信源的数学模型及其分类3.2 离散无记忆信源3.3 离散无记忆信源的扩展信源3.4 离散平稳信源3.5 马尔可夫信源,3, N次扩展信源熵的性质 (1) 条件熵 随N的增加是非递增的 (2) (3) 平均符号熵 随N的增加是非递增的。 (4) 极限熵 存在，且,3.4 离散平稳信源（续）,对于平稳信源，极限熵是考虑了符号相关性的最小值,4,3.4 离散平稳信源_性质（续）, 条件熵H (XL|XL-1) 随L的增加是非递增的 条件较多的熵必小于或等于条件较少的熵，而条件熵必小于或等于
2、无条件熵。,5,(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 离散平稳信源_性质（续）,6,(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) H
3、1(X) H0(X) H0(X) :等概率无记忆信源单个符号的熵， H1(X)为一般无记忆（不等概率）信源单个符号的熵 H2(X)为两个符号组成的序列平均符号熵，依次类推。,7,3.4 离散平稳信源_性质（续）,8,(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 离散平稳信源_性质（续）,
4、9,说明: (i) 如何计算极限熵是一个十分困难的问题. (ii) 在实际应用中常取有限L下的条件熵 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 离散平稳信源_性质（续）,10,信源发出的符号只与前面的m个符号有关，而与更前面出现的符号无关。用概率意义表达为p(xt|xt-1,xt-2,xt-3,xt-m,)=p
5、(xt|xt-1,xt-2,xt-m) 则根据（4）可得,=H(Xm+1|X1X2Xm)=Hm+1(X),3.4 离散平稳信源_性质（续）,11,3.5 马尔可夫信源,3.5.1 马尔可夫过程 3.5.2 有限状态马尔可夫链 3.5.3 马尔可夫信源,12,3.5.1 马尔可夫过程,1. 定义：设X(t), tT是随机过程，任取0t1t2 tn，tiT, i=1,2, n ,若t1,t2, ,tn时刻, 取值分别为x1,x2, ,xn，并有,注： k=0时，称为零阶马尔可夫过程。零阶马尔可夫过程=白噪声过程。,13,3.5.2 有限状态马尔可夫链,1. 定义：设 xn , nN+ 为一随机序列
6、，时间参数集N+=0,1,2, 其状态空间S=S1,S2,SJ有限或可数，若对所有n N+ ，有,则称, xn,nN+ 为有限状态一阶马尔可夫链。 例：蛙跳,14,3.5.2 有限状态马尔可夫链,解释：(1) S=S1,S2,SJ是状态空间即xn所有可能取值,15,3.5.2 有限状态马尔可夫链,(2) 转移概率m时刻状态Si，经(n-m)步后转移到状态Sj的概率,16,3.5.2 有限状态马尔可夫链, 基本转移概率（即一步转移概率）一步转移概率pij(m,m+1)记成pij(m),17,3.5.2 有限状态马尔可夫链, k步转移概率k步转移概率pij(m,m+k)记成p(k)ij(m),18
7、,3.5.2 有限状态马尔可夫链, k步转移矩阵m时刻的k步转移矩阵,每行之和都为1,19,states : sunny, cloudy, rainy. state transition matrix : The probability of the weather given the previous days weather.,3.5.2 有限状态马尔可夫链,例：,20,3.5.2 有限状态马尔可夫链,(3) K阶马尔可夫链,21,3.5.2 有限状态马尔可夫链,(4) 时齐马尔可夫链（齐次马尔可夫链）若pij(m)=P(xm+1=Sj|xm=Si)于时刻m无关。即pij(m)=pij ，
8、则称为时齐马尔可夫链（齐次马尔可夫链） 一步转移矩阵P为,22,例,3.5.2 有限状态马尔可夫链,23,输入的码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 有限状态马尔可夫链,24,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
9、(Y2=1|Y1=1)=p(X=0)=p 说明: 转移矩阵为 ，它与r无关，因而是齐次的。,3.5.2 有限状态马尔可夫链,25,3.5.2 有限状态马尔可夫链,2. 切普曼科尔莫哥洛夫方程（C-K方程） 命题：设P(n)是时齐马尔可夫链的n步转移矩阵(n1)， P=P(1)是基本转移矩阵，则从而有 元素 注意：P(n)是经过n步的转移矩阵。,26,3.5.2 有限状态马尔可夫链,3.初始分布 定义：设P(X0=Si)=pi , 且则称它为马尔可夫链的初始分布,27,3.5.2 有限状态马尔可夫链,例,已知本月机床的状态向量,预测机床两个月后的状态,28,3.5.2 有限状态马尔可夫链,两个月
10、后机床的状态向量,29,3.5.2有限状态马尔可夫链,4. 平稳分布定义：若齐次马尔可夫链对所有i,j存在不依赖于i的极限且满足,则称其具有遍历性，pj称为平稳分布,30,3.5.2有限状态马尔可夫链,解释：当n充分大时，可用常数pj作为pij(n)的近似值,31,3.5.2有限状态马尔可夫链,32,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
11、. 稳态分布存在定理,33,3.5.2 有限状态马尔可夫链,(2)定理二：稳态分布存在设P是齐次马尔可夫链转移矩阵，则该链稳态分布存在 存在一个正整数N,使矩阵PN 中所有元素均大于零,34,马氏链可约性: 若对所有 k，都有p(k)ij=0，就意味着一旦出现 Si以后不可能到达Sj, 也就是不能各态遍历，或者状态中应把Sj取消，这样就成为可约的了。 马氏链不可约性:对任意一对i和j，都存在至少一个k使 p(k)ij0，这就是说从Si开始，总有可能到达Sj.,3.5.2 有限状态马尔可夫链,35,香农线图,3.5.2 有限状态马尔可夫链,36,注意: (1)S1,S2,S3是三种状态，箭头是指
12、从一个状态转移到另一个状态，旁边的数字代表转移概率。这就是香农提出的马尔可夫状态图，也叫香农线图。(2)由状态S3转移到S1的转移概率p(k)31=0，因为一进人状态S3就一直继续下去，而不会再转移到其他状态。P(k)41=0也是明显的，因S4和S1之间没有连接箭头，因此这种链就是可约的。,3.5.2 有限状态马尔可夫链,37,马氏链周期性,非周期性，就是所有p(k)ii0的k中没有比1大的公因子。,S1,S4,S2,1/2,1/2,周期性马氏链,S3,1/2,1/2,1/2,1/2,1/2,1/2,3.5.2 有限状态马尔可夫链,38,注意: (1)上图周期为2.因为从S1出发再回到S1所需
13、的步数必为2，4，6， . (2) p(n)ij矩阵,3.5.2 有限状态马尔可夫链,39,当k为奇数时,当k为偶数时,3.5.2 有限状态马尔可夫链,40,若起始状态为s1，则经奇数步后，Sk=Sj的概率为,经偶数步后,3.5.2 有限状态马尔可夫链,达不到稳定状态 !,41,方程组 是有解？,3.5.2 有限状态马尔可夫链,42,m时刻,总 结 有限状态马尔可夫链,有限状态 马尔科夫链,状态空间,转移概率,基本转移概率pij(m),k步转移概率p(k)ij(m),k步转移矩阵P=p(k)ij(m),齐次马尔科夫链 （时齐马尔科夫链）,基本转移概率同时刻m无关 （具有平稳转移概率矩阵）,C-K方程,初始分布,任意时刻系统的 状态分布,43,总 结有限状态马尔可夫链,C-K方程,初始分布,任意时刻系统的 状态分布,平稳分布 （极限分布）,稳态分布 存在定理,唯一性定理,存在定理,44,作业,时齐马尔可夫链计算机模拟 初始分布 基本概率矩阵（含有零元素） 逐步进入稳态分布 给出理论计算结果和计算机仿真结果,
