资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 离散信源,1,离散信源的分类与数学模型, 离散无记忆信源的熵, 离散平稳信源的熵, 有限状态马尔可夫链, 马尔可夫信源, 信源的相关性与剩余度,本章内容,2,信源,：信息的来源；,其,功能：,直接产生可能包含信息的消息。,3,3.1,离散信源的分类与数学模型,信源离散信源的分类,离散信源的数学模型,4,3.1.1,离散信源的分类,根据信源符号取值连续,/,离散, 根据输入符号间的依赖关系,无记忆,/,有记忆, 有限离散信源,/,无限离散信源,平稳信源,/,非平稳信源,5,3.1.2,离散无记忆信源的数学模型,注释 ,A=a,1,，,，,a,n, ,信源的符号集,n ,符号集的大小,a,i,随机变量的取值,p(a,i,) X= a,i,的概率。,单符号离散无记忆信源的数学模型：,6,3.1.1,一个二元无记忆信源，符号集,A=0,1, p,为,X=0,的概率,q,为,X=1,的概率，,q=1-p,；写出信源的模型。,解：,信源的模型：,例,单符号离散无记忆信源,7,多维离散无记忆信源,数学模型,:,3.1.2,离散无记忆信源的数学模型,8,信源,X,的,N,次扩展源 ：设信源为,X,，由,X,构成的,N,维随机矢量集合, 信源与其扩展源的关系：,离散无记忆信源的,N,次扩展源,N,个连续输出的符号合并,9,3.1.2,求,例,3.1.1,中信源的二次扩展模型。,解：,二元信源,X,的符号集为,0,1,例,离散无记忆信源的,N,次扩展源,10,马氏链是随机过程，因此可看成信源，即马尔可夫信源；这种信源是有记忆信源。, 有限记忆的系统可以用有限状态机来描述。在有限状态机中，既包含状态之间的转移关系，也包含输出与状态之间的关系。, 可以从有限状态机的概念出发定义马尔可夫信源。,3.1.3,离散有记忆信源的数学模型,离散马尔可夫信源,11,3.2,离散,无,记忆信源的,熵,单符号离散无记忆信源的熵,离散无记忆信源,N,次扩展源的熵,12,3.2.1,3.2.1,单符号离散无记忆信源的熵,写出例,3.1.1,中的二元无记忆信源的熵的表达式。,解：,例,13,具有熵的一切性质, 对,p,的导函数为,p=0.5,时,H(p),达到最大值,1bit, H(p),是,p,的上突函数,0.5,1,1,0,p,H(p),的主要性质：,3.2.1,单符号离散无记忆信源的熵,14,3.2.2,离散无记忆信源,N,次扩展源的熵,定理,3.2.1,离散无记忆信源,X,的,N,次扩展源 的熵等于信源,X,熵的,N,倍，即,证明：,熵的可加性,15,3.2.2,给定离散无记忆信源模型：,求其二次扩展源熵。,解：,例,3.2.2,离散无记忆信源,N,次扩展源的熵,16,3.3,离散平稳信源,的熵,离散平稳信源, 离散平稳有记忆信源的熵,17,信源,X,具有有限符号集, 信源产生随机序列, 对所有 有,3.3.1,离散平稳信源,(1),定义：,则称信源为离散平稳信源，所产生的序列为平稳序列,18,平稳序列的统计特性与时间的推移无关,3.3.1,离散平稳信源,(2),19,3.3.1,一平稳信源,X,的符号集,A=0,，,1,，产生随机序列，其中,P(x,1,=0)=p,求,P(x,n,=1),（,n 1,）的概率。,解：,例,平稳性,3.3.1,离散平稳信源,(3),20,3.3.1,续,对同一信源，若,P(x,1,=0,，,x,2,=1)=b,求,P(x,4,=1/x,3,=0),。,解：,例,平稳性,3.3.1,离散平稳信源,(4),21,对于平稳信源，条件概率也是平稳的。一般地，有, 平稳信源的熵与时间起点无关，即,3.3.1,离散平稳信源,(5),22,根据平稳性和熵的不增原理,对于,X,的,N,次扩展源,定义平均符号熵：,3.3.2,离散平稳有记忆信源的熵,(1),23,信源,X,的极限符号熵：,简称：,符号熵或熵率,3.3.2,离散平稳有记忆信源的熵,(2),24,1,） 不随,N,而增加,2,）,3,） 不随,N,而增加,4,） 存在，且,说明：有记忆信源的符号也可通过计算极限条件熵得到,定理,3.3.1,：,任意离散平稳信源，若,3.3.2,离散平稳有记忆信源的熵,(3),25,1,）,信源的平稳性,熵的不增原理,这说明对于平稳信源，条件越多，条件熵越不增加,3.3.2,离散平稳有记忆信源的熵,(4),26,2,）,只要证明,N,个 的和不小于,平均符号熵不小于条件熵,3.3.2,离散平稳有记忆信源的熵,(5),27,3,）,由于,平均符号熵不随序列的长度而增加,根据平均符号熵的定义和,2,）的结果，有,3.3.2,离散平稳有记忆信源的熵,(6),28,4,）,通过以上证明可得，,3.3.2,离散平稳有记忆信源的熵,(7),29,先令 ，后令 ，得,另外，由（,2,）的结果，当 时,有,所以,证毕。,3.3.2,离散平稳有记忆信源的熵,(8),30,该定理提供了通过计算极限条件熵得到信源符号熵的方法；这样，当信源为有限记忆时，极限条件熵的计算要比极限平均符号熵的计算容易得多。, 极限熵等于最小的平均符号熵。,定理,3.3.1,的注释：,3.3.2,离散平稳有记忆信源的熵,(9),31,马氏链的基本概念, 齐次马氏链, 马氏链状态分类,马氏链的平稳分布,3.4,有限状态马尔可夫链,32,*,、马尔可夫过程定义,(,补充,),随机过程 ，其值域（状态）可连续取值，也可以离散取值，若它的条件概率满足下列条件：,式中， ，则称,X(t),马尔可夫过程。,33,假设在现时刻,t,n,的状态是,X,n,即,X(t,n,)=X,n,而在将来某时刻,t,n+1,的状态,X,n+1,仅与现在的状态,X,n,有关，而与过去时刻的状态,X,n-1,，,X,n-2,，,.,，,X,1,X,0,无关。马尔可夫过程称为无后效过程。,*,、马尔可夫过程定义,(,补充,),34,离散马尔科夫链：时间、状态均离散；,连续马尔科夫链：时间离散、状态连续；,离散马尔科夫过程：时间连续、状态离散；,连续马尔科夫过程：时间、状态均连续；,*,、马尔可夫过程分类,(,补充,),35,随机序列, 每个随机变量 仅依赖于,定义：,3.4.1,马氏链的基本概念,(1),随机变量 ：马氏链在,n,时刻的状态, ：,状态, 的集合,S,：,状态集合,36,1),一阶马氏链的当前状态只与前一个状态有关,2) n,阶马氏链的当前状态只与前,n,个状态有关,3),马氏链是时间离散，状态也离散的随机过程,4),状态集合为有限集,有限状态马氏链,状态集合为无限集无穷状态马氏链,3.4.1,马氏链的基本概念,(2),37,描述马氏链的最重要的参数：状态转移概率, 对于离散时刻,m,、,n,，相应的状态转移概率可表示为：,表示从时刻,m,的,i,状态转移到时刻,n,的,j,状态的概率，,m-n,表示转移的步数。 是经 步转移的概率。,3.4.1,马氏链的基本概念,(3),38,一步转移概率,K,步转移概率,0,步转移概率,系统在任何时刻必处于,S,中某一状态,转移概率的主要性质：,3.4.1,马氏链的基本概念,(4),39,转移概率与起始时刻无关,K,步转移概率也与起始时刻无关，写成,3.4.2,齐次马氏链,(1),40,3.4.2,齐次马氏链,(2),齐次马氏链的表示方法,转移概率矩阵,状态转移图,由状态,j,转移到状态,2,的概率；,非负,=1,网格图,状态转移图与矩阵有一一对应关系,每时刻的网格节点与马氏链的状态一一对应,41,3.4.2,齐次马氏链,(3),3.4.1,一个矩阵，验证此矩阵对应一个齐次马氏链的转移概率矩阵并确定此马氏链的状态数,解：,例,元素非负,状态数,=3,每行和为,1,=1,=1,=1,42,3.4.1,续,画出此马氏链的网格图。,解：,例,3.4.2,齐次马氏链,(4),43,3.7.1,续,画出此马氏链的状态转移图,解：,例,3.4.2,齐次马氏链,(5),1,3,2,1,3,1,4,1,3,1,4,1,4,1,4,1,3,1,2,1,2,44,3.7.1,续,求从状态,3,到状态,2,的,2,步转移概率,解：,例,S,2,1/4,1/3,S,2,S,3,S,3,S,1,1/2,1/2,1/4,1/4,3.4.2,齐次马氏链,(6),45,1),计算从,m,时刻从,s,3,经,m+1,时刻某状态,s,k,到,m+2,时刻,s,2,的转移概率,2),对,1,）中计算的经,m+1,时刻的所有状态,s,k,（,k=1,，,2,，,3,）概率相加，得到所求结果。计算得,下面分两步来计算,:,3.4.2,齐次马氏链,(7),46,计算从状态,i,到状态,j,的,2,步转移概率可通过下式,:,Kolmogorov-Chapman方程,(1),由此例可以看出,:,2),是 的第,(i,j),个元素,3),是 的,m,次幂 的第,(i,j),个元素,4),47,Kolmogorov-Chapman方程,(2),5),设马氏链的初始状态概率分布为,其中J为状态数，经k步转移后的状态概率分布为 ，则有,:,因此，一个齐次马氏链，当初始状态概率分布给定后，可计算转移后任何时刻的状态概率分布。,48,3.4.2,设例,3.4.1,中马氏链的初始状态的概率分布为,1/2,、,1/4,、,1/4,，分别求,1,步转移后和,2,步转移后的状态的概率分布。,解：,例,Kolmogorov-Chapman方程,(2),49,3.4.3,马氏链状态分类,(1),若对某一,n,1,，有 ，则称状态,j,可由状态,i,到达，记为,ij,如果 ，且 ，则称状态,i,与状态,j,可互通，记为,定义每个状态都与该状态本身互通，即互通关系满足自反性, 互通关系还满足对称性和传递性,50,3.4.3,马氏链状态分类,(2),3.4.3,按互通性将状态分成若干类（子集）,解：,例,51,3.4.3,马氏链状态分类,(3),常返态,过渡态,周期的,非周期,最大公约数,1,1,52,3.4.3,马氏链状态分类,(4),对任何马氏链（有限或无限可数状态），同一类中所有状态都有相同周期。,定理,3.4.1,：,非周期的常返态称为遍历态,53,定义,:,若对任意整数,m,n,马氏链的状态分布满足,则称 为平稳分布，或稳态分布,其中， 为平稳分布行矢量,3.4.4,马氏链,的平稳分布,(1),(3.4.11),54,3.4.4,马氏链,的平稳分布,(2),平稳马氏链, 定理,3.4.2,如果一个遍历有限状态马氏链的转移概率矩阵为,P,，那么,(3.4.12),55,对于遍历马氏链，无论初始分布如何，当转移步数足够大时，状态概率分布总是趋于稳定值，与初始状态概率分布无关,。,3.4.4,马氏链,的平稳分布,(3),56,3.4.4,马氏链,的平稳分布,(4),对于有限状态马氏链，稳态分布恒存在, 如果马氏链中仅存在一个常返类，则方程,(3.4.11),的解是唯一的；如果存在,r,个常返类，则具有,r,个线性独立的矢量解, 如果马氏链中仅存在一个常返类而且是非周期的（即遍历的），则,(3.4.12),式成立；如果有多个常返类，但都是非周期的，则 也收敛，但矩阵的每行可能不同；如果马氏链具有一个或多个周期常返类，则 不收敛,57,3.4.4,马氏链,的平稳分布,(5),3.4.4,一马氏链的转移概率矩阵如下，问此马氏链是否具有遍历性并求平稳分布和 的值,解：,例,1,2,3,1,2,1,3,1,2,1,2,1,6,1,58,3.4.4,马氏链,的平稳分布,(6),59,一马氏链的状态转移矩阵如下，确定它的,n,次幂是否收敛并求其平稳分布,3.4.4,马氏链,的平稳分布,(7),3.4.5,解：,例,1,1,1,2,60,马氏源的基本概念, 马氏源的产生模型, 马氏源,N,次扩展源熵的计算, 马氏源符号熵的计算,3.5,马尔可夫信源,61,当前时刻输出符号的概率仅与当前时刻的信源状态有关, 当前时刻的信源状态由前一时刻信源状态和前一时刻输出符号唯一确定。,马氏源的定义：,3.5.1,马氏源的基本概念,(1),62,给定二阶马氏源符号集,A=0,，,1,，转移概率分别为：,p(0/00)=p(1/11)=0.8,，,p(1/00)=P(0/11)=0.2,，,p(0/01)=p(0/10)=p(1/01)=p(1/10)=0.5,，确定该马氏源的状态，写出状态转移矩阵，画出信源的状态转移图。,3.5.1,例,3.5.1,马氏源的基本概念,(2),63,解：,3.5.1,马氏源的基本概念,(3),64,m,阶马氏链的符号转移概率已给定,2),做,m,长符号序列到信源状态的映射 ， 取遍 ，,i=1,m,； 状态取自 ，,为状态数；,3),符号转移概率转换成状态转移概率,其中,4),得到一阶马氏源模型：,m,阶马氏源的处理方法,65,3.5.2,马氏源的产生模型,(1),66,设独立随机序列 ， ， ， ， 随机序列 与 的关系为 其中 为模,2,加；问：（,1,）随机序列 是否为马氏链？（,2,）如果是马氏链，那么求状态转移概率并画状态转移概率图。,3.5.2,例,3.5.2,马氏源的产生模型,(2),67,解：,3.5.2,马氏源的产生模型,(3),序列 为有记忆序列，在,n,时刻的取值仅与,n-1,时刻与,n-2,时刻有关，而与以前的时间无关，因此 构成二阶马氏链。,68,有一个二元马氏链,X,，符号集为,0,，,1,，其中符号转移概率为 ， ；计算该信源三次扩展源的所有符号的概率。,3.5.3,例,3.5.3,马氏链N次扩展源的熵的计算,(1),解：,首先求平稳分布,69,3.5.3,马氏链N次扩展源的熵的计算,(2),类似得到,70,做映射 ，,i = 0,N-m,，其中,i,为时间标号，,j,为状态序号。,H(X,1,X,2,X,N,) = H(S,m+1,S,m+2,S,N+1,),其中，,S,i,=X,i-m,X,i-m+1,X,i-1,利用熵的可加性，将上式展开，并利用马氏性得,H(X,1,X,2,X,N,) = H(S,m+1,)+ H(S,m+2,/S,m+1,)+H(S,N+1,/S,m+1,S,m+2,S,N,),3.5.3,马氏链N次扩展源的熵的计算,(3),= H(S,m+1,)+ H(S,m+2,/S,m+1,)+H(S,N+1,/S,N,),= H(S,m+1,)+,71,3.5.3,马氏链N次扩展源的熵的计算,(4),72,该项由状态转移概率矩阵,P,的第,j,行所确定。写成矩阵形式,其中，,为第,i,状态概率分布行矢量,; ,为行矢量,其中每个元素由,P,的每一行所确定。,3.5.3,马氏链N次扩展源的熵的计算,(5),73,如果起始状态概率为平稳分布,则,N,次扩展源的平均符号熵为,:,3.5.3,马氏链N次扩展源的熵的计算,(6),74,当信源从某一状态转移到另一状态时,输出符号唯一,则一个,m,阶马氏源的符号熵为,:,m,阶马氏源符号熵仅由平稳分布和状态转移概率矩阵所决定。,3.5.4,马氏源符号熵的计算,(1),计算方法,1,：,75,当信源从某一状态转移到另一个新状态时，存在多个信源序列对应一个状态。这样由状态转移概率矩阵不能确定信源的熵，而只能以状态条件下信源的输出符号的概率求信源的熵。,给定当前信源状态条件下信源的输出符号熵为：,计算方法,2,：,3.5.4,马氏源符号熵的计算,(2),76,在给定某特殊状态,s,1,=j,和以前的输出,X,1,X,2,X,m-1,条件下当前输出符号,X,m,的熵满足：,对,S,1,取平均,引理,3.5.1,：,3.5.4,马氏源符号熵的计算,(3),77,对于平稳信源，状态概率与时间起点无关，所以,对于,m,阶平稳马氏源的符号熵为,利用平稳性及马氏性，有,3.5.4,马氏源符号熵的计算,(4),78,当 给定条件下， 与以前的状态无关,为状态平稳分布行矢量,h,的各分量由状态转移概率矩阵的每一行得出的条件熵,3.5.4,马氏源符号熵的计算,(5),79,3.5.4,马氏源符号熵的计算,(6),定理,3.5.2,：,平稳马氏源的符号熵为,80,几点注释,：,1),定理,3.5.2,给出了马氏源符号熵的计算方法：,先求每个状态下的条件符号熵，再用状态的概,率平均；,2),计算符号熵要用状态的平稳分布；,3),单位为比特,/,符号。,3.5.4,马氏源符号熵的计算,(7),81,求信源的极限符号熵,3.5.1,续,解：,例,3.5.4,马氏源符号熵的计算,(8),82,3.6,信源的相关性与剩余度,信源的相关性,信源剩余度（冗余度）,自然语言的相关性和剩余度,83,信源的相关性就是信源符号间的依赖程度。设信源有,m,个符号，那末对于不同情况可以分别计算信源的熵为：,（符号独立等概）,（独立信源）,（一阶马氏源）,（,n-1,阶马氏源）,由平稳性与熵的不增原理，有：,可见，符号相关程度越大，熵越小，反之亦然。,3.6.1,信源的相关性,84,为描述信源的相关性，引入信源效率和剩,余度的概念。,信源效率,信源剩余度,3.6.2,信源剩余度（冗余度）,85,英文字母概率表,3.6.3,自然语言的相关性和剩余度,(1),字母,概率,字母,概率,字母,概率,空格,0.1859,I,0.0575,R,0.0484,A,0.0642,J,0.0008,S,0.0514,B,0.0127,K,0.0049,T,0.0796,C,0.0218,L,0.0321,U,0.0228,D,0.0317,M,0.0198,V,0.0083,E,0.1031,N,0.0574,W,0.0175,F,0.0208,O,0.0632,X,0.0013,G,0.0152,P,0.0152,Y,0.0164,H,0.0467,Q,0.0008,Z,0.0005,86,对于实际英文字母组成的信源：,3.6.3,自然语言的相关性和剩余度,(2),(,比特,/,符号,),87,汉字近似概率表,3.6.3,自然语言的相关性和剩余度,(3),类别,汉字个数,所占概率,P,每个汉字的概率,P,i,140,0.5,0.5/140,625-140=485,（,0.85-0.5,）,=0.35,0.35/485,2400-625=1775,（,0.997-0.85,）,=0.147,0.147/1775,7600,0.003,0.003/7600,88,根据上表，可近似估算汉语信源的信息熵：,3.6.3,自然语言的相关性和剩余度,(4),(,比特,/,符号,),89,1,离散信源,X,的,N,次扩展源的熵 ，仅当信源无记忆时等式成立； 离散信源,X,的,N,次扩展源的平均符号熵 ，仅当信源无记忆时等式成立。,本 章 小 结,(1),90,2,有记忆信源的符号熵：,并且,3,马氏源的符号熵：,其中 ，,4,信源剩余度,本 章 小 结,(2),91,
展开阅读全文