离散马氏链信源

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2018/5/31,#,离散马氏链信源,平稳信源的,m,阶马尔可夫信源：,信源发出的符号只与前面的,m,个符号有关，而与更前面出现的符号无关。,用概率意义表达为,:,p(x,t,/x,t-1,x,t-2,x,t-3,x,t-m,)=p(x,t,/x,t-1,x,t-2,x,t-m,),状态转移描述,对于,m,阶马尔可夫信源,在某一时刻（,m,1,），信源符号出现的概率，仅与前面已出现的,m,个符号有关，而与更前面出现的符号无关。可通过引人状态转移概率，从而转化为马尔可夫链，即令,如果信源符号表中的数目为,q,，则由前面出现的,m,个符号所组成的序列,s,i,共有,Q,q,m,种，将这些序列看作是状态集,S=s,1,s,2,s,Q,，则信源在某一时刻出现符号,x,j,的概率就与信源此时所处的状态,s,i,有关，用条件概率表示为,p(x,j,/s,i,),，,i=1,2,.,Q,；,j=l,2,q,。当信源符号,x,j,出现后，信源所处的状态将发生变化，并转人一个新的状态。用转移概率表示 如下,:,p,ij,(m,n)=pS,n,=s,j,/S,m,=s,i,=ps,j,/s,i,s,i,s,j,S,状态转移概率,p(s,j,/s,i,),由信源符号条件概率,p(x,j,/s,i,),确定。,为什么状态转移概率是一个条件概率,?,(1),状态转移概率,P,ij,(m,n),表示已知在时刻,m,系统处于状态,s,i,，或,S,m,取值,s,i,的条件下，经,(n-m),步后转移到状态,s,j,的概率。,(2),把,P,ij,(m,n),理解为已知在时刻,m,系统处于状态,i,的条件下，在时刻,n,系统处于状态,j,的条件概率，故状态转移概率实际上是一个条件概率。,两个基本转移概率性质,:,什么叫基本转移概率,(,一步转移概率,)?,当,n=m+1,时，把,p,ij,(m,m+1),记为,p,ij,(m),，,m0,，并称为基本转移概率,(,一步转移概率,),。,记,齐次马尔可夫链转移概率具有时间推移不变性,转移概率性质：,转移概率可表示为：,k,步转移概率表示为,:,k,步转移概率矩阵,:,说明,:,一步转移概率矩阵为,:,一步矩阵,P,中第,i,行元素对应于从某一个状态,S,i,转移到所有状态,S,j,的转移概率，显然矩阵中的每一个元素都是非负的，并且每行之和均为,1,；,一步矩阵,P,中第,j,列元素对应于从所有状态,S,i,转移到同一个状态,S,j,的转移概率，列元素之和不一定为,1,。,一步矩阵,P,中第,i,行元素对应于从某一个状态,S,i,转移到所有状态,S,j,的转移概率，显然矩阵中的每一个元素都是非负的，并且每行之和均为,1,；第,j,列元素对应于从所有状态,S,i,转移到同一个状态,S,j,的转移概率，列元素之和不一定为,1,。,切普曼一柯尔莫郭洛夫方程,说明,:,(1),k,步转移概率,P,(k),ij,与,l,（,l,k),步和（,k-l,）步转移概率之间关系,;,(2),上式右侧是对第,l,步的所有可能取值求和，因而也就是,k,步转移概率。,(3),当,l=1,时,矩阵表示,:,(p,(k),)=(p)(p,(k-1),)=(p)(p)(p,(k-2),)=(p),k,对于齐次马氏链来说，一步转移概率完全决定了,k,步转移概率。,如何确定无条件概率,?,令初始概率为,p,0i,p(S,0,s,i,),如何确定平稳分布的,W,j,p(S,k,=s,j,),?,其中,W,i,和,W,j,均为稳态分布概率,.,分析,:,所以,有非零解,W,1,W,2,W,Q,。,如果再用 就可解得各稳态分布概率,W,j,。,若 的秩是,(n-1),，则解是唯一的。,马氏链的可约性,马氏链可约性,:,若对所有,k,，都有,p,(k),ij,=0,，就意味着一旦出现,S,i,以后不可能到达,S,j,也就是不能各态遍历，或者状态中应把,S,j,取消，这样就成为可约的了。,马氏链不可约性,:,对任意一对,i,和,j,，都存在至少一个,k,使,p,(k),ij,0,，这就是说从,Si,开始，总有可能到达,Sj.,香农线图,S,1,S,3,S,2,1/2,1/2,1/2,1/2,1,S,4,S,5,1/2,1/2,可约马氏链,1/2,1/2,注意,:,(1),S,1,S,2,S,3,是三种状态，箭头是指从一个状态转移到另一个状态，旁边的数字代表转移概率。这就是香农提出的马尔可夫状态图，也叫香农线图,。,(2),由状态,S,3,转移到,S,1,的转移概率,p,(k),31,=0,，因为一进人状态,S,3,就一直继续下去，而不会再转移到其他状态。,P,(k),41,=0,也是明显的，因,S,4,和,S,1,之间没有连接箭头，因此这种链就是可约的。,马氏链周期性,非周期性，就是所有,p,(k),ii,0,的,n,中没有比,1,大的公因子。,S,1,S,4,S,2,1/2,1/2,1/2,周期性马氏链,S,3,1/2,1/2,1/2,1/2,1/2,1/2,注意,:,(1),上图周期为,2.,因为从,S,1,出发再回到,S,1,所需的步数必为,2,，,4,，,6,，,，,.,(2),p,(n),ij,矩阵,当,k,为奇数时,当,k,为偶数时,若起始状态为,s,1,，则,经奇数步后，,S,k,=s,j,的概率为,达不到稳定状态,!,经偶数步后,例,2-4-2,+,T,X,r,Y,r,1,0,1,q,q,p,p,输入的码,X,r,(r=1,2,),是相互独立的，取值,0,或,1,，且已知,p(X=0)=p,，,p(X=1)=1-p=q,，输出的码是,Y,r,，显然有,Y,1,=X,1,，,Y,2,X,2,Y,1,其中 表示模,2,加，那么,Yr,就是一个马氏链，因,Yr,确定后，,Yr+1,布只与,Yr,有关，与,Yr-1,、,Yr-2,等无关，且知,Yr,序列的条件概率为,p,00,=p(Y,2,=0/Y,1,=0)=p(X=0)=p,p,01,=(Y,2,=1/Y,1,=0)=p(X=1)=q,p,10,=p(Y,2,=0/Y,1,=1)=p(X=1)=q,p,11,=p(Y,2,=1/Y,1,=1)=p(X=0)=p,说明,:,(1),转移矩阵为，它与,r,无关，因而是齐次的。,(2),由图容易验证该马氏链具有不可约性和非周期性,问题：,冗余度产生的原因？,信息效率、冗余度的定义？,第五节,冗余度,问题,1,：冗余度产生的原因,冗余度（多余度、剩余度）,表示给定信源在实际发出消息时所包含的多余信息。,冗余度来自两个方面,，一是,信源符号间的相关性,，由于信源输出符号间的依赖关系使得信源熵减小，这就是信源的相关性。相关程度越大，信源的实际熵越小，趋于极限熵,H,（,X,）；反之相关程度减小，信源实际熵就增大。,另一个方面是,信源符号分布的不均匀性,，当等概率分布时信源,熵,最大。而实际应用中大多是不均匀分布，使得实际,熵,减小。当信源输出符号间彼此不存在依赖关系且为等概率分布时，信源实际,熵,趋于最大,H,0,（,X,）。,问题,2,：信息效率、冗余度的定义,信息效率,表示不肯定的程度,冗余度,表示肯定性的程度，因为肯定性不含有信息量，,因此是冗余的。,书,P,28,例子,由上述例子可看出：,由于各个符号出现的概率不均匀,所以：,H,1,H,0,随着序列增长，字母间的相关性越来越强,:,所以：,H,H,3,H,2,正是因为信源符号中存在的这些统计不均匀性和相关性，才使得信源存在冗余度。,当英文字母的结构信息已预先充分获得时，可用合理符号来表达英语，例如传送或存储这些符号，可大量压缩，,100,页的英语，大约只要,29,页就可以了。,结论：,在实际通信系统中，为了提高传输效率，往往需要把信源的大量冗余进行压缩，即所谓,信源编码,。但是考虑通信中的抗干扰问题，则需要信源具有一定的冗余度。因此在传输之前通常加人某些特殊的冗余度，即所谓,信道编码,，以达到通信系统理想的传输有效性和可靠性。,作业,:,2-18,到,2-21,2-23,到,2-29,