资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,信源与信息熵,第二章,1,2.1,信源的描述和分类,2.2,离散信源熵和互信息,2.3,离散序列信源的熵,2.4,连续信源的熵和互信息,2.5,冗余度,2,内容,本章重点,信源熵和离散,/,连续互信息,3,本章难点,离散序列有记忆信源的熵,4,2.1,信源的描述和分类,信源,信源,产生消息,(,符号,),、消息序列和连续消息的来源,产生随机变量、随机序列和随机过程的源,。,在通信系统中收信者在未收到消息以前对信源发出什么消息是不确定的,是随机的，所以可用,随机变量、随机序列或随机过程,来描述信源输出的消息,或者说用一个样本空间及其概率测度,概率空间,来描述信源,信源的基本特性,：具有,随机不确定性,。,5,香农信息论的基本点,用,随机变量,或,随机矢量,来,表示信源,用,概率论,和,随机过程,的理论来,研究信息,6,信源的分类,按照信源发出的消息在,时间,上和,幅度,上的分布情况可将信源分成离散信源和连续信源两大类,7,信源,离散信源,:,文字、数据、电报,随机序列,连续信源,:,话音、图像,随机过程,连续信源,指发出在时间和幅度上都是,连续分布,的连续消息（模拟消息）的信源，如语言、图像、图形等都是连续消息。,信源的分类,离散信源,指发出在时间和幅度上都是,离散分布,的离散消息的信源，如文字、数字、数据等符号都是离散消息。,8,离散,信源,离散,无记忆,信源,离散,有记忆,信源,发出单个符号的无记忆信源,发出符号序列的无记忆信源,发出符号序列的有记忆信源,发出符号序列的马尔可夫信源,2.1.1,无,记忆信源,离散无记忆信源,所发出的各个符号是相互独立的，发出的符号序列中的各个符号之间,没有统计关联性,，各个符号的出现概率是它自身的先验概率。,9,例如扔骰子，每次试验结果必然是,1,6,点中的某一个面朝上。,用一个离散型随机变量,X,来描述这个信源输出的消息。,离散,无,记忆信源,发出单个符号的信源,指信源每次只发出一个符号代表一个消息；,发出符号序列的信源,指信源每次发出一组含二个以上符号的符号序列代表一个消息,10,信源的描述,一个离散信源发出的各个符号消息的集合为：,11,它们的概率分别为,p,(,x,i,):,x,i,的,先验概率,单符号,离散,信源的数学模型,概率空间,a,b,c,z,离散信源的统计特性,离散消息是从有限个符号组成的符号集中选择排列组成的随机序列（组成离散消息的信息源的符号个数是有限的）,在形成消息时，从符号集中选择各个符号的概率不同 。,组成消息的基本符号之间有一定的统计相关特性 。,12,信源的描述,连续信源,：,输出在时间和幅度上都是连续分布的消息,单符号,连续,无记忆信源的,概率空间,13,随机取一节干电池测其电压值作为输出符号,符号取值为,0,1.5,之间的所有实数。,该信源就是发出单符号的,连续无记忆,信源,信源的描述,发出,符号序列,的信源,14,设信源输出的随机序列为,X,=(X,1,X,2,X,l,X,L,),序列中的变量,X,l,x,1,x,2,x,n,这种由信源,X,输出的,L,长随机序列,X,所描述的信源称为离散无记忆信源,X,的,L,次扩展信源,信源的描述,随机序列的概率,15,当信源,无记忆,时,2.1.2,有记忆信源,一般情况下,信源在不同时刻发出的符号之间是,相互依赖,的，也就是信源输出的平稳随机序列,X,中，各随机变量,X,l,之间是有依赖的。,如在汉字序列中前后文字的出现是有依赖的，不能认为是彼此不相关的。,表述有记忆信源要比表述无记忆信源困难得多,离散有记忆信源,所发出的各个符号的概率是,有关联,的。,发出符号序列的有记忆信源,发出符号序列的马尔可夫信源,16,用信源发出的一个符号序列的整体概率,(,即联合概率,),反映有记忆信源的特征,一个符号出现的概率只与前面一个或有限个符号有关,而不依赖更前面的那些符号,概率论基础,无条件概率、条件概率、联合概率的性质和关系,17,概率论基础,无条件概率、条件概率、联合概率的性质和关系,18,2.1.3,马尔可夫信源,马尔可夫信源,一类相对简单的离散平稳信源,该信源在某一时刻发出字母的,概率,除与该字母有关外,只与此前发出的,有限,个字母有关,m,阶马尔可夫信源,：,信源输出某一符号的概率仅与以前的,m,个符号有关，而与更前面的符号无关。,条件概率,19,马氏链的基本概念,一阶马尔可夫信源,：,20,若把,有限个字母,记作一个,状态,S,，则信源发出某一字母的概率除与该字母有关外，只与该时刻信源所处的状态有关。,信源,将来的状态,及其送出的字母将只与信源,现在的状态,有关，而与信源过去的状态无关。,马氏链的基本概念,令,s,i,= (,x,i,1,x,i,2,x,i,m,),x,i,1,x,i,2,x,i,m,(,a,1,a,2,a,n,),状态集,S,= s,1,s,2,s,Q,Q = n,m,信源输出的随机,符号,序列为,：,x,1,x,2,x,i,-1,x,i,信源所处的随机,状态,序列为,：,s,1,s,2,s,i,-1,s,i,例：二元序列为,01011100,考虑,m = 2,，,Q = n,m,=2,2,= 4,s,1,= 00 s,2,= 01 s,3,= 10 s,4,= 11,变换成对应的,状态序列,为,s,2,s,3,s,2,s,4,s,4,s,3,s,1,21,马尔可夫信源,设信源在时刻,m,处于,s,i,状态,它在下一时刻,(m+1),状态转移到,s,j,的,转移概率,为：,p,ij,(,m,) =,p,S,m+1,=s,j,| S,m,= s,i,=,p,s,j,| s,i,p,ij,(,m,),：,基本转移概率（一步转移概率）,若,p,ij,(,m,),与,m,的取值无关,则称为,齐次,马尔可夫链,p,ij,= p,S,m+1,=s,j,| S,m,= s,i,=,p,S,2,=s,j,| S,1,= s,i,p,ij,具有下列性质,：,p,ij,0,22,若信源处于某一状态,s,i,当它发出一个符号后,所处状态就变了,任何时候信源处于什么状态完全由前一时刻的状态和发出符号决定。,系统在任一时刻可处于状态空间,S,= s,1,s,2,s,Q,中的任意一个状态,状态转移时,转移概率矩阵,23,符号,条件概率矩阵,例,2-1,，如图所示是一个相对码编码器,输入的码,X,r,(,r,=1,2,),是相互独立的，取值,0,或,1,，且已知,P(X=0)=,p, P(X=1)=1,p,=,q,，输出的码是,Y,r,，显然,24,T,X,r,Y,r,Y,r,-1,+,Y,r,是一个,马氏链,Y,r,确定后,Y,r+1,概率分布只与,Y,r,有关,与,Y,r-1,、,Y,r-2,等无关,且知,Y,r,序列的条件概率,p,00,= P,(,Y,2,=0/Y,1,=0,),= P,(,X=0,),= p,p,01,= P,(,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,25,s,o,s,1,p,q,q,p,马尔可夫信源,状态转移图,齐次马尔可夫链可以用其状态转移图,(,香农线图,),表示,每个圆圈代表一种,状态,状态之间的有向线代表某一状态向另一状态的,转移,有向线一侧的符号和数字分别代表发出的,符号,和,条件概率,26,s,o,s,1,1/0.6,0/0.3,0/0.4,s,2,1/0.2,0/0.8,1/0.7,27,s,3,s,2,s,4,s,5,s,1,s,6,周期性,的：在常返态中,有些状态仅当,k,能被某整数,d,1,整除时才有,p,ij,(,k,),0,图中的周期为,2,；,x,5,:1,非周期性,的：对于,p,ij,(,k,),0,的所有,k,值，其,最大公约数为,1,。,常返态,：,经有限步后迟早要返回的状态，,x,4,:1,x,3,:1/2,x,2,:1/2,x,3,:1/2,x,2,:1/2,x,2,:1/2,x,4,:1/4,x,1,:1/4,x,6,:1,x,6,:1/4,马尔可夫信源,遍历状态,：,非周期的、常返的状态,如图中的状态,s,2,和,s,3,闭集：,状态空间中的某一子集中的任何一状态都不能到达子集以外的任何状态,不可约的,：,闭集中除自身全体外再没有其他闭集的闭集,28,马尔可夫信源,一个不可约的、非周期的、状态有限的马尔可夫链其,k,步转移概率,p,ij,(,k,),在,k,时趋于一个和初始状态无关的,极限概率,W,j,，它是满足方程组,的唯一解；,W,j,：马尔可夫链的一个,平稳分布,，,W,j,p(s,j,),就是系统此时处于状态,s,j,的概率。,29,例,30,s,o,s,1,1/0.6,0/0.3,0/0.4,s,2,1/0.2,0/0.8,1/0.7,例,2-2,：,有一个二元二阶马尔可夫信源,其信源符号集为,0,，,1,，已知符号条件概率：,p(0|00) = 1/2 p(1|00)=1/2,p(0|01) = 1/3 p(1|01)=2/3,p(0|10) = 1/4 p(1|10)=3/4,p(0|11) = 1/5 p(1|11)=4/5,求：,信源全部状态及状态转移概率,画出完整的二阶马尔可夫信源状态转移图。,求平稳分布概率,31,32,状态转移,概率矩阵,符号,条件概率矩阵,(1)1/2,(0)1/2,(0)1/3,(1)2/3,00,01,11,10,s,2,s,1,s,4,s,3,(1)3/4,(0)1/4,(0)1/5,(1)4/5,33,稳态分布概率,稳态后的符号概率分布,例,一个二元二阶马尔可夫信源,其信源符号集为,0,1,信源开始时,：,p(0) = p(1) = 0.5,发出随机变量,X,1,。,下一单位时间,：输出随机变量,X,2,与,X,1,有依赖关系,x,2,x,1,0,1,0,0.3,0.4,1,0.7,0.6,34,p,(,x,2,|x,1,),再下一单位时间,：输出随机变量,X,3,与,X,2,X,1,有依赖关系,x,3,x,1,x,2,00,01,10,11,0,0.4,0.2,0.3,0.4,1,0.6,0.8,0.7,0.6,p,(,x,3,|x,1,x,2,),从第四单位时间开始，随机变量,X,i,只与前面二个单位时间的随机变量,X,i-2,X,i-1,有依赖关系,:,p,(,x,i,|,x,i-1,x,i-2,x,2,x,1,) =,p,(,x,i,|,x,i-1,x,i-2,) (,i,3),且,p,(,x,i,|,x,i-1,x,i-2,) =,p,(,x,3,|,x,2,x,1,) (,i,3),35,解,:,设信源开始处于,s,0,状态,并以等概率发出符号,0,和,1,分别到达状态,s,1,和,s,2,:,若处于,s,1,以,0.3,和,0.7,的概率发出,0,和,1,到达,s,3,和,s,4,若处于,s,2,以,0.4,和,0.6,的概率发出,0,和,1,到达,s,5,和,s,6,00,01,10,11,(0)0.5,(1)0.5,(0)0.3,(0)0.4,(1)0.7,(1)0.6,s,1,s,2,s,0,s,6,s,5,s,4,s,3,信源发完第,2,个符号后再发第,3,个及以后的符号。,从第,3,单位时间以后信源必处在,s,3,s,4,s,5,s,6,四种状态之一。在,i3,后,信源的状态转移可用下图表示,:,36,10,11,01,00,(0)0.3,(0)0.4,(1)0.7,(0)0.2,(1)0.8,(1)0.6,(0)0.4,(1)0.6,状态,s,1,和,s,5,功能是完全相同,状态,s,2,和,s,6,功能是完全相同,可将二图合并成,s,3,s,4,s,5,s,6,s,0,(0)0.5,(1)0.5,s,0,是过渡状态,s,3,s,4,s,5,s,6,组成一个不可约闭集,并且具有遍历性。,由题意,此马尔可夫信源的状态必然会进入这个不可约闭集,所以我们计算信源熵时可以不考虑过渡状态及过渡过程。,由,37,得稳态分布概率,当马尔可夫信源达到稳定后,符号,0,和符号,1,的概率分布：,38,信源达到稳定后，信源符号的概率分布与初始时刻的概率分布是不同的，所以，一般马尔可夫信源并非是平稳信源。,但当时齐、遍历的马尔可夫信源达到稳定后，这时就可以看成一个平稳信源。,：,习题,2-1,2-2,39,
展开阅读全文