21信源的描述和分类解析

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