《信息论与编码第2章.ppt》由会员分享,可在线阅读,更多相关《信息论与编码第2章.ppt(134页珍藏版)》请在三一办公上搜索。
1、1,2.1 信源的描述与分类,2.2 离散信源熵和互信息,第二章信源及信源熵,2.3 连续信源的熵和互信息,2.4 离散序列信源的熵,2.5 冗余度,2,第二章信源及信源熵,2.1 信源的描述与分类 信源的分类 信源的分类方法依信源特性而定,一般按照信源发出的消息在时间上和幅度上的分布情况,把信源分为:连续信源:发出在时间上和幅度上都是连续分布的连续消息的信源,如语音、图像、图形等都是连续消息。离散信源:发出在时间上和幅度上都是离散分布的信源,如文字、数字、数据等符号都是离散消息。,3,第二章信源及信源熵,离散信源又可以细分为:(1)离散无记忆信源:所发出的各个符号之间相互独立,发出的符号序列
2、中各个符号之间没有统计关联性,各个符号的出现概率是其自身的先验概率。可细分为发出单个符号的无记忆信源与发出符号序列的无记忆信源。布袋摸球实验:每次取1个球,球的颜色作为消息输出;每次先后取2个球,由两个球的颜色组成的消息就是符号序列,记录完颜色后球被放回。(2)离散有记忆信源:发出的各个符号之间不是相互独立的,各个符号出现的概率是有关联的。可细分为发出符号序列的平稳有记忆信源与发出符号序列的非平稳有记忆信源,后者诸如:发出符号序列的马尔可夫信源。每次先后取2个球,但记录完颜色后球不放回。,4,第二章信源及信源熵,2.1.2 离散信源的描述与度量发送方消息的选择具有随机性,否则就没有通信的必要了
3、。换句话说,我们在收到消息之前,并不知道信源将要发出什么消息,信源是随机的、不确定的,因此,可用随机变量或随机矢量来描述信源输出的消息。或者说,用概率空间来描述信源。离散信源的数学模型就是离散型的概率空间:,5,第二章信源及信源熵,发出单个符号的无记忆信源输出的都是单个符号的消息,出现的消息数是有限的,且只可能是符号集中的一种,即符合完备性信源可能取的消息(符号)只有q个:,且每次必定取其中一个。,6,第二章信源及信源熵,然而,很多实际信源输出的消息往往是由一系列符号所组成的。例如:中文信源的样本空间集合x是所有中文字母及标点符号的集合。由这些单字和标点符号组成的消息即是中文句子和文章。从时间
4、上看,中文信源的输出是时间上离散的一系列符号,而其中每个符号的出现是随机的,由此构成了不同的中文消息。,7,第二章信源及信源熵,例如:对离散化的平面图像来说,从空间上来看是一系列离散的符号,而空间每一点的符号(灰度)又都是随机的,由此形成了不同的图像。因此,可以将一般信源输出的消息看作为时间或空间上离散的一系列随机变量,即随机矢量。符号序列信源的输出可用 N 维随机矢量 来描述,其中 N 可为有限正整数或可数的无限值。,8,第二章信源及信源熵,在上述随机矢量中,若每个随机变量 都是离散的,则可用N重离散概率空间来描述这类信源。即若N维随机矢量 中 则,9,第二章信源及信源熵,信源的N重概率空间
5、为:这个空间共有 个元素。,10,第二章信源及信源熵,在某些简单的情况下,信源先后发出的一个个符号彼此是统计独立的,则N维随机矢量的联合概率分布满足即N维随机矢量的联合概率分布可用随机矢量中单个随机变量的概率乘积来表示。这种信源就是离散无记忆信源。,11,第二章信源及信源熵,有记忆信源:输出的随机序列X中各随机变量之间有依赖关系。例如在中文字母组成的中文消息中,前后文字的出现是有依赖的,不能认为是彼此不相关的,放在N维随机矢量的联合概率分布中,就必然要引入条件概率分布来说明它们之间的关联。此外,对弈时,当前怎样走,通常是与先前已走步数所形成的局势有关。,12,第二章信源及信源熵,描述有记忆信源
6、要比表述无记忆信源困难得多。比较特殊的情况:信源发出的符号往往只与前面几个符号的依赖关系较强,而与更前面的符号依赖关系就弱。为此可以限制随机序列的记忆长度。m阶马尔可夫信源:信源每次发出的符号只与前m个符号有关,与更前面的符号无关。,齐次马尔可夫信源:上述条件概率与时间起点i无关,13,第二章信源及信源熵,2.1.3 概率复习,14,第二章信源及信源熵,15,第二章信源及信源熵,2.2 离散信源熵和互信息信息的度量信息的可度量性-建立信息论的基础;信息度量的方法:结构度量统计度量语义度量模糊度量等;统计度量:用事件统计发生概率的对数来描述事物的不确定性,得到消息的信息量,建立熵的概念;熵概念是
7、香农信息论最基本最重要的概念。,16,第二章信源及信源熵,2.2.1 自信息量 在讨论了信源的数学模型,即信源的数学描述问题后,很自然接着会提出这样一个问题,即信源发出某一符号 后,它提供多少信息量?这就是要解决信息的度量问题。在通信的一般情况下,信宿所获取的信息量,在数量上等于通信前后不确定性的消除(减少)的量。,信息量不确定性的减少量,17,第二章信源及信源熵,事件发生的不确定性与事件发生的概率有关。事件发生的概率越小,猜测它有没有发生的困难程度就越大,不确定性就越大;而事件发生的概率越大,猜测这事件发生的可能性就越大,不确定性就越小;对于发生概率等于1的必然事件,就不存在不确定性。信源发
8、生的概率越小,一旦它出现必然使人感到意外,给人的信息量就越大;反之,消息出现的概率很大,一旦出现人们不会感到意外,所以给人的信息量就很小,对必然出现的信息,则不具任何信息量。根据已有的数学理论可知对数函数具有上述特征。因此,信息量可以定义如下。,18,第二章信源及信源熵,给出一个离散信源:,其中p(xi)为xi出现概率,且,如果消息xi已发生,则xi包含的自信息量为,(2-2-1),19,第二章信源及信源熵,式中:p(xi)xi发生的先验概率;I(xi)xi发生所含信息量。自信息量的单位与所用对数底有关。在信息论中常用的对数底是2,信息量的单位是比特(bit,binary unit);若取自然
9、对数e为底,则信息量的单位为奈特(nat,natural unit);若以10为对数底,则信息量的单位为笛特(det,decimal unit)或者Hart(Hartley,哈特莱)。这三个信息量单位之间的转换关系如下:1bit0.693nat0.301det 1nat=log2e1.433bit1det=log2102.322bit,20,第二章信源及信源熵,如果p(xi)0.5,则由式(2-2-1)得I(xi)1bit。若是一个m位的二进制数,因为该数的每一位可以从0,1两个数字中任取1个,因此有2m个等概率的可能组合。所以,就是需要m比特的信息来指明这样的二进制数。Page17的例2-3
10、,21,第二章信源及信源熵,式(2-2-1)表示的自信量I(xi)有两方面的含意:信源X发出符号xi以前,收信者对xi存在的先验不确定性。信源X发出符号xi之后,xi所含有的(或能提供的)全部信息量。不确定度与自信息量:随机事件的不确定度在数量上等于它的自信息量,两者的单位相同,但含义却不同。某种概率分布的随机事件不管发生与否,都存在不确定度;而自信息量则是在该事件发生后给予观察者的信息量。,22,第二章信源及信源熵,自信息量I(xi)的性质:,I(xi)是 p(xi)的单调递减函数,当 p(xi)=0时,I(xi)=;,当 p(xi)=1时,I(xi)=0;,I(xi)是非负值;,23,第二
11、章信源及信源熵,发出符号序列的离散无记忆信源发出的消息的信息量:式中ni为第i个符号出现的次数,p(xi)为第i个符号出现的概率,N为离散消息源的符号数目。例2.1:(习题2-7)设有一离散无记忆信源,其概率空间为该信源发出的消息202 120 130 213 001 203 210 110 321 010 021 032 011 223 210,求:(1)此消息的自信息量是多少?(2)在此消息中平均每个符号携带的信息量是多少?,24,第二章信源及信源熵,解:(1)此消息总长为45个符号,其中0出现14次,1出现13次,2出现12次,3出现6次,则此消息的信息量(2)平均每个符号携带的信息量I
12、/451.95比特/符号,25,第二章信源及信源熵,两个消息xi、yj同时出现的联合自信息量:用联合概率 来表示,联合自信息量为当 和 相互独立时,有 于是有,26,第二章信源及信源熵,条件自信息量:当 和 相互联系时,在事件 出现的条件下,的自信息量称为条件自信息量,定义为 为在事件 出现的条件下,发生的条件概率。,27,第二章信源及信源熵,联合自信息量与条件自信息量也满足非负与单调递减性。关系当X和Y独立时,,28,第二章信源及信源熵,2.2.2 离散信源熵前面定义的自信息是指某一信源发出某一消息所含有的信息量。所发出的消息不同,它们所含有的信息量也就不同。所以自信息 是一个随机变量,不能
13、用它来作为整个信源的信息测度。Page-18 例2-4:定义自信息的数学期望为信源的平均自信息量,即,29,第二章信源及信源熵,类似地,引入信源的平均不确定度,即在总体平均意义上的信源不确定度。这个平均不确定度的表达式和统计物理学中热熵的表达式很相似。在统计物理学中,热熵是一个物理系统杂乱性(无序性)的度量。这在概念上也有相似之处。因而就借用“熵”这个词把平均不确定度 H(X)称为“信源熵”,也被称作“香农熵”、“无条件熵”、“熵函数”。,30,第二章信源及信源熵,例2.2 计算例2.1中信源的平均信息量,并用平均信息量计算例2.1中消息的总的信息量。解:(Page18-19的例2-5,例2-
14、6,例2-7),例2.1I87.81(bit)思考一下为什么与例2.1的结果不同?,31,第二章信源及信源熵,信源熵与平均自信息量数值上相等,但含义不同:信源熵:某一信源,不管它是否输出符号,只要这些符号具有某些概率特性,就必有信源熵,这熵值是从平均意义上来表征信源的不确定度的,因而是一个确定的值。不同的信源因统计特性不同,其熵也不同。平均自信息量是消除信源不确定性所需信息的平均量度,即收到一个信源符号,全部解除了该符号的不确定性;或者说获得这样大的信息量后,信源的不确定性就被消除了。信息量只有当信源输出的符号被接收到后才有意义,是给予接收者的信息度量,该值可以是随机的,如前面的自信息量;也可
15、能与接收者的情况有关,如后面将提到的其他信息量。,32,第二章信源及信源熵,由于可能与接收者的情况有关,因此,信源熵作为信源的平均不确定性的描述,一般情况下并不等于平均获得的信息量。只是在无噪情况下,接收者才能正确无误地接收到信源所发出的信息,消除信源熵H(X)值大小的平均不确定性,此时获得的平均信息量才等于信源熵H(X)的值。后面将会看到:在一般情况下,获得的信息量是两熵之差,并不是信源熵本身。,33,信源熵与信息量的比较,熵 信息量,34,第二章信源及信源熵,信源熵小结:信源熵和平均自信息量两者在数值上是相等的,但含义并不同。信源熵表征信源的平均不确定度,平均自信息量是消除信源不确定性所需
16、要的信息的平均量度。信源熵的三种物理含义H(X)表示信源输出后,每个离散消息所提供的平均信息量。H(X)表示信源输出前,信源的平均不确定度。H(X)反映了信源的随机性。,35,第二章信源及信源熵,条件熵:在给定 的条件下,的条件自信息量为,随机事件X在给定yj的条件熵H(X/yj)为 表示Y为符号 的前提下,获得关于X的平均信息量,为随机量,随 变化。而 条件熵是在联合符号集合XY上的条件自信息量的联合概率加权统计平均值。,36,第二章信源及信源熵,称H(X/Y)为X的条件熵,表示Y(即各个yj)给定的前提下,获得的关于X的平均信息量。类似地,称 H(Y/X)为Y的条件熵,表示X(即各个xi)
17、给定的前提下,获得的关于Y的平均信息量。,37,第二章信源及信源熵,联合熵:是联合符号集合XY的每个元素对xi yj的自信息量的概率加权统计平均值,定义为 表示X和Y同时发生的不确定度。,38,第二章信源及信源熵,2.2.3 离散信源熵的基本性质(1)非负性:(2)对称性:H(x1,x2,xn)H(x2,x1,xn)熵函数的所有变元可以互换,不影响结果。(3)确定性:确知信源的不确定度为零。,39,第二章信源及信源熵,(4)可加性:(证明)正因为具有可加性,可以证明熵的形式是唯一的。(5)扩展性虽然概率很小的事件出现后,给予接收者的信息量很大,但对熵的贡献很小,可以忽略不计。,40,第二章信源
18、及信源熵,(6)极值性(最大离散熵定理):即等概率分布时,熵达到极值。对于具有M个符号的离散信源,只有在M个信源符号等可能出现的情况下,信源熵才能达到最大值,表明等概率分布时信源的平均不确定性最大。这是一个很重要的结论,称为最大离散熵定理。,41,第二章信源及信源熵,(7)香农辅助定理:对于任意n及概率矢量 和,有如下不等式成立 上式表明,就任意概率分布pi而言,它对其他概率分布qi的自信息量-logqi取数学期望时,必不小于pi本身的熵。只有当P=Q时,上式取等号。,42,第二章信源及信源熵,根据该性质,可以证明条件熵小于等于无条件熵:H(Y/X)H(Y)当且仅当 y 和 x 相互独立时,p
19、(y/x)=p(y),取等号。从而可得联合熵小于信源熵之和:H(XY)H(X)+H(Y),43,(8)上凸性 若 f 的定义域中任意两个矢量或者变量X、Y 满足,则称 f 为严格上凸函数,设P、Q为两组概率矢量。即,44,则有,条件熵、联合熵的例子:Page 20-21的例2-8,例2-9,45,信息论与编码-信源及信源熵,2.2.4 互信息信息传输的根本问题,是从信宿的接收信号中获取有关信源的信息。现在来讨论如何定量计算信宿收到信道输出的某一符号后,从中获取关于信源符号的信息量(如图2.1)。,46,信息论与编码-信源及信源熵,当接收到输出符号Yyj后,可以得到条件概率p(xi/yj),i=
20、1,2,N,此条件概率被称作后验概率。互信息量定义为后验概率与先验概率比值的对数:,两个不确定度之差,就是不确定度被消除的部分,代表已确定的成分。互信息量实际上是从yj中获得的关于xi的信息量。,47,?,理想情况:,收到yj后,xi仍有不确定性,但与原来的不确定性有所不同。不确定性发生变化的部分,即为观察者从接收端获得的关于发送端的信息量。,48,49,?,理想情况:,发送xi后,yj仍有不确定性,但与原来的不确定性有所不同。不确定性变化的部分,即为观察者从发送端获得的关于接收端的信息量。,50,信息论与编码-信源及信源熵,可以从互信息的定义来理解自信息,I(xi,xi)=I(xi)互信息量
21、的性质:可正可负,如果互信息量I(xi;yj)取负值,说明由于噪声的存在,接收到消息yj后,反而使接收者对消息xi是否出现的猜测疑难程度增加了。即收到消息yj后对xi出现的不确定性反而增加,所以获得的信息量为负值。xi与yj相互独立时,互信息为0。对称性互信息的例子:Page23的例2-10,51,信息论与编码-信源及信源熵,I(X;Y)称为X与Y之间的平均互信息。它代表接收到符号集Y后获得的关于X的平均信息量。平均互信息I(X;Y)就是互信息I(xi;yj)在两个概率空间X与Y中求统计平均的结果,也被称作平均交互信息量,交互熵。,52,根据平均互信息量的定义,可得:I(X;Y)H(X)H(X
22、/Y)H(X)为输入X的不确定度,H(X/Y)为收到输出Y后关于输入X的平均不确定度,可见当Y已知时,X的不确定度减少了I(X;Y),即已知信道输出Y后,获得的关于X的信息量为I(X;Y)。损失熵或(信道)疑义度:当信道无失真时,输出Y等于输入X,这时获得的关于X的信息量为H(X);当信道有失真时,获得的关于X的信息量从H(X)下降为I(X;Y),损失的信息量为H(X/Y)。为此,条件熵H(X/Y)被称作损失熵;又因H(X/Y)是由于信道失真所造成的对于信源符号X的不确定性,也被称作(信道)疑义度。,信息论与编码-信源及信源熵,53,信息论与编码-信源及信源熵,如果是一一对应信道,那么接收到符
23、号集Y后,对X的不确性完全消除,则信道疑义度H(X/Y)0。条件熵小于无条件熵,即H(X/Y)H(X),说明已知输出符号Y后,关于输入符号X的平均不确定性减少了,即总能消除一些关于输入端X的不确定性,从而获得相应的信息。,54,噪声熵或散布度:I(Y;X)H(Y)H(Y/X),H(Y/X)表示在已知X条件下,对Y存在的不确定性,反映了信道中噪声源的不确定性,故又称为噪声熵或者散布度。收、发端的熵的关系,信息论与编码-信源及信源熵,图2-7 收、发端的熵关系,55,信息论与编码-信源及信源熵,全损离散信道:如果X与Y是相互独立的,收到Y时给出关于X的条件概率等于无条件概率,相应地,X的条件熵就等
24、于X的无条件熵,此时I(X;Y)0。可理解为X与Y相互独立时,无法从Y中提取关于X的信息。这可看成信道噪声相当大,以至于H(X|Y)H(X),传输的平均信息量为零,收到符号Y后不能提供有关信源发出符号X的任何信息量。这种信道由于信源发出的信息量在信道上全部损失掉了,故称作全损离散信道。,56,信息论与编码-信源及信源熵,无扰离散信道:当X与Y一一对应时,即X与Y满足确定函数关系时,条件概率必为1,即I(X;Y)H(X),此时收到Y就完全解除了关于X的不确定性,所获得的信息就为X的不确定性或熵。由于没有噪声,所以信道不损失信息量,此时信道疑义度H(X/Y)0,于是I(X;Y)H(X)H(Y),这
25、种信道被称作无扰离散信道。,57,信息论与编码-信源及信源熵,通常情况下,X与Y既非相互独立,也不是一一对应,那么从Y获得X的信息必在零与H(X)之间,通常小于X的熵。熵是平均不确定性的描述,不确定性的消除(熵差)才等于接收端所获得的信息量,因此,信息量不应该与不确定性混为一谈。互信息量对应的熵差,自信息量对应的熵差。,58,平均互信息的性质,对称性,1,物理意义,59,非负性,2,物理意义:从整体平均意义而言,从一个事件提取另一个事件的信息,最坏情况是0,不会由于知道了一个事件,反而使另一个事件的不确定性增加。,60,极值性,1,3,物理意义,61,2,62,1,4,凸函数性,研究信道容量的
26、理论基础。,63,2,研究信源的信息率失真函数的理论基础。,64,信息论与编码-信源及信源熵,三维联合集的平均互信息:,65,信息论与编码-信源及信源熵,2.2.5 数据处理中信息的变化在一些实际的通信系统中,常常需要在信道输出端对接收到的信号或数据进行适当的处理,这种处理称为数据处理。数据处理系统也可以看成是一种信道,它与之前传输数据的信道相互间是级联的关系。,第 一 级处理器,X,输入,第 二 级处理器,Y,Z,图2.8 级联处理器示意图,66,信息论与编码-信源及信源熵,从级联信道输出端Z中获取的关于输入端X的平均交互信息量I(X;Z),不会超过从第一级信道的输出端Y中获取关于输入端X的
27、平均交互信息量I(X;Y),也不会超过从第二级信道的输出端Z中获取关于输入端Y的平均交互信息量I(Y;Z)。结论:随着级联处理器数目的增多,输入消息与输出消息之间的平均互信息量趋于变小。这就是数据处理定理:多级处理使得信息量减少,数据处理过程中只会失掉一些信息,绝不会创造出新的信息,即信息不增性。,67,信息论与编码-信源及信源熵,数据处理定理的另一个应用:若想从测量结果中获得更多的关于X的信息量,必须付出代价。常用的方法代价可以是多次测量。,结论:多次测量得到的互信息量大于单次测量所得到的结果。,Page-27 例2-11,68,信息论与编码-信源及信源熵,2.2.6 各种熵之间的关系,H(
28、X/Y),H(Y/X),I(X;Y),H(X),H(Y),H(XY),69,70,71,72,73,限峰功率最大熵定理,2.3.1 连续信源熵,2.3.2 最大熵定理,2.3 连续信源的熵和互信息,限平均功率最大熵定理,74,连续信源的数学模型:,R为实数集,是变量X的取值范围,为随机变量的概率密度函数,连续信源熵,75,假设xa,b,令x=(b-a)/n,xia+(i-1)x,a+ix,利用中值定理X取xi的概率:,积分中值定理:如果函数f(x)在闭区间a,b上为连续函数,则在积分区间a,b上,至少存在一点,使下式成立。,连续信源熵,76,连续信源X被量化为离散信源:,且,连续信源熵,77,
29、这时离散信源 的熵是:当 时,离散随机变量 趋于连续随机变量X,而离散信源 的熵 的极限值就是连续信源的不确定度/绝对熵/香农熵。,连续信源熵,78,定义连续信源的熵为:,连续信源熵,这样定义的熵虽然在形式上和离散信源的熵相似,也满足离散信源熵的主要特性,如可加性,但在概念上二者有差异,前者失去了部分离散熵的含义与性质,如非负性。,H(X)为无穷大,79,例:求均匀分布的连续信源熵,结论:连续信源熵不具备非负性。由于绝对熵还有一个正的无限大项,因此依然为正(无穷大)。,80,例2-14 有一信源概率密度如图所示,求连续熵,解:由图(a)得由图(b)得,连续信源熵,81,同理,可以定义两个连续随
30、机变量X、Y的联合熵与条件熵,即,连续信源熵,82,它们之间也有与离散信源一样的相互关系,并且可以得到具有信息特征的互信息:,连续信源熵,83,连续信源熵(相对熵)这样定义的好处:,在形式上与离散信源熵统一,实际问题常常讨论的是熵差,此时的熵差同样具有信息的特征,1,2,84,连续信源的熵具有相对性,有时也称为相对熵、差熵,在取两熵之间的差时才具有信息的所有特性。,连续信源熵小结:连续信源有无穷多个状态,其绝对熵为无穷大。连续信源熵为相对熵,为绝对熵减去无穷大量。连续信源熵不等于消息所具有的平均信息量,其熵是有限的,而信息量是无限的。连续信源熵不具有非负性,可以为负值。,85,离散信源:信源符
31、号等概率分布时信源的熵取最大值。,还有其它约束,约束条件不同,连续信源熵最大值不同。一般情况下,求最大差熵值就是在多个约束下:,连续信源:信源熵也具有最大值,但其情况有所不同。除存在完备集条件:,求 的极值。用拉格朗日法求解,2.3.2 最大熵定理,86,(1)限峰功率最大熵定理(取值幅度受限):,定理:若信源X输出的幅度被限定在a,b区域内,则当输出信号幅度的概率密度pX(x)是均匀分布时,信源具有最大熵。此时,,2.3.2 最大熵定理,该结论与离散信源在等概时达到最大熵的结论类似。,87,(2)限平均功率最大熵定理:,定理:若一个连续信源输出符号的平均功率被限定,则其输出信号幅度的概率密度
32、pX(x)是正态(高斯)分布时,信源具有最大熵。,高斯分布:(其中,m为数学期望,为方差),2.3.2 最大熵定理,88,2.3.2 最大熵定理,在限定信号平均功率的条件下,正态分布的信源可输出最大相对熵,其值仅与随机变量的方差 有关,而方差在物理含义上往往表示信号的平均交流功率,即,随平均功率的增加而增加。,给定噪声平均功率的前提下,如果噪声是正态分布,则噪声熵最大,因此,高斯噪声达到最大噪声熵,换句话说,高斯噪声为最有害的干扰。,连续信源在不同限制条件下最大熵是不同的,在无限制条件时,最大熵不存在。,89,平稳有记忆信源序列,离散无记忆信源的序列熵,离散有记忆信源的序列熵,2.4 离散序列
33、信源的熵,马尔可夫(Markov)信源(非平稳离散有记忆信源),m阶马尔可夫信源,马尔可夫信源的信息熵,平稳随机序列的熵,平稳随机序列的定义,90,设信源输出的随机序列为,序列中的变量,即序列长为L。随机序列的概率为:,2.4.1 离散无记忆信源的序列熵,无记忆信源:,91,信源的序列熵为:,若又满足平稳性,即与序号l无关时:,则信源的序列熵为H(X)=LH(X),平均每个符号的熵为:,2.4.1 离散无记忆信源的序列熵,离散无记忆平稳信源平均每个符号的符号熵 HL(X)就等于单个符号信源的符号熵 H(X)。,92,2.4.1 离散无记忆信源的序列熵,离散无记忆平稳信源平均每个符号的符号熵 就
34、等于单个符号信源的符号熵H(X)。,例:(题干见习题2.7),93,2.4.2 离散有记忆信源的序列熵,例:谈用不包有所适从事事无奈何可争辩,后面几乎以概率“1”出现“事”字,后面有四个字可以出现,94,(1)平稳随机序列的定义:,所谓平稳随机序列,就是序列的统计特性(事件发生的概率)与时间的推移无关,即信源所发符号的概率分布与时间起点无关。所以对于平稳信源来讲,其条件概率也与时间起点无关,只与关联长度 N 有关。,2.4.2 一、平稳有记忆信源序列,95,(2)平稳随机序列的熵:,2.4.2 一、平稳有记忆信源序列,96,当信源退化为无记忆时,有,这一结论与离散无记忆信源结论是完全一致的,可
35、见,无记忆信源可以看作有记忆信源的特例。,2.4.2 一、平稳有记忆信源序列,97,例:已知离散有记忆信源中各符号的概率空间为现信源发出二重符号序列消息,这两个符号的关联性用条件概率 表示,并由上表给出。求信源的序列熵和平均符号熵。,2.4.2 一、平稳有记忆信源序列,98,解:,条件熵为,单符号信源熵为,2.4.2 一、平稳有记忆信源序列,99,发二重符号序列的熵为:,平均符号熵为:,比较上述结果可知:,即二重序列的符号熵值较单符号熵变小了,也就是不确定度减小了,这是由于符号之间存在相关性造成的。,2.4.2 一、平稳有记忆信源序列,100,对离散平稳信源,其联合概率具有时间推移不变性,此时
36、有如下结论:,是 L 的单调非增函数。,是 L 的单调非增函数。,当 时,称为极限熵或者极限信息量,有时又称作平稳信源的熵率。,对于一般的离散平稳信源,由于取L不很大时就能得出非常接近 的或者,2.4.2 一、平稳有记忆信源序列,101,2.4.2 一、平稳有记忆信源序列,:等概率无记忆信源单个符号的熵,:一般无记忆信源单个符号的熵,:两个符号组成的序列平均符号熵,注意:信源的概率空间是一个完备集,102,(1)m 阶马尔可夫信源的定义:,常见的m阶马尔可夫信源,它在任何时刻i,符号发生的概率只与前面m个符号有关,与更前面的符号无关。则,上述公式在工程上很实用。,2.4.2 二、马尔可夫(Ma
37、rkov)信源,103,m 阶马尔可夫离散信源的数学模型:,并满足,2.4.2 二、马尔可夫(Markov)信源,104,设状态,则信源的状态集,条件概率又可变换为:,任何m时刻信源处在 状态时,发出符号 的概 率,而在m时刻,信源发出符号 后,由符号组成了新的信源状态信源所处的状态也由 转移到,2.4.2 二、马尔可夫(Markov)信源,105,状态转移概率 表示已知在时刻m系统处于状态si,经(nm)步后转移到状态sj的概率。状态转移概率具有下列性质:,齐次马尔可夫链(离散情况下的齐次马尔可夫信源),其转移概率具有时移不变性,即只与状态有关,基本转移概率、一步转移概率,2.4.2 二、马
38、尔可夫(Markov)信源,106,k步转移概率,系统在任一时刻可处于状态空间 中的任意一个状态,因此转移概率是一个矩阵:,由一步转移概率pij可以写出其转移矩阵或,每行元素之和为1,2.4.2 二、马尔可夫(Markov)信源,107,注意:状态转移矩阵与条件概率矩阵是不同的:此处,前者 Q 行 Q 列,后者 Q 行 q 列。,2.4.2 二、马尔可夫(Markov)信源,108,转移概率的切普曼-柯尔莫郭洛夫方程:(k步、l步与k-l步转移概率之间的关系)当l=1时,有用矩阵表示,就是,对于齐次马尔可夫链来说,一步转移概率完全决定了k步转移概率。,2.4.2 二、马尔可夫(Markov)信
39、源,109,无条件状态概率 的计算:就是从初始状态经k步转移后,停留在某一个状态 的概率。为了计算这个概率,需要知道初始状态概率,即这时,,2.4.2 二、马尔可夫(Markov)信源,110,转移概率 的平稳分布:两个问题:(1)此极限是否存在;(2)如果存在,其值是多少。存在问题:如果存在,且等于一个与起始状态 i无关的被称为稳态分布的,则不论起始状态是什么,此马氏链可以达到最后稳定,即所有状态的概率分布均不变,这也被称作遍历性。在这种情况下,就可以完全用矩阵P来描述稳定的马氏链,起始状态只使前面有限个变量的分布改变,如同电路中的暂态一样。,2.4.2 二、马尔可夫(Markov)信源,1
40、11,稳态分布概率的求法:设只要它存在,平稳分布Wj可用下列方程组来求得上式中,与 均为稳态分布概率。再加上约束条件,两式联立求解,就可以求出稳态分布概率。,2.4.2 二、马尔可夫(Markov)信源,112,W有唯一解是平稳分布存在的必要条件,并不是充分条件。为了使M氏链最后达到稳定,成为遍历的M氏链,还必须有不可约性和非周期性。,香农线图:也叫马尔可夫状态转移图,不可约性:就是对任意一对i和j,都存在至少一个k,使p(k)ij0.Page-12的图2-1,非周期性,就是所有p(n)ii0的n中没有比1大的公因子。Page-13的图2-2,2.4.2 二、马尔可夫(Markov)信源,Pa
41、ge-14的例2-1:遍历性满足不可约性、非周期性,可求得平稳分布。,113,例题:三态马尔柯夫信源的状态转移矩阵及符号概率矩阵为:画出其状态转移图,求其稳态概率分布和符号概率分布。,解:香农线图为,2.4.2 二、马尔可夫(Markov)信源,注意:状态转移矩阵与条件概率矩阵不同,114,稳态状态概率分布:解得:,符号概率分布为:,2.4.2 二、马尔可夫(Markov)信源,115,Page-14的例2-2:注意:此处也展示了状态转移矩阵与条件概率矩阵的不同,2.4.2 二、马尔可夫(Markov)信源,116,(2)马尔可夫信源的信源熵,对于齐次、遍历的马尔可夫链,其状态 由 唯一决定,
42、因此有,两边同取对数,对和取统计平均,再取负,可以得到,2.4.2 二、马尔可夫(Markov)信源,117,2.4.2 二、马尔可夫(Markov)信源,118,马尔可夫链的稳态分布概率Wi,信源处于某一状态 时发出一个符号的平均不确定性,,2.4.2 二、马尔可夫(Markov)信源,119,2.4.2 二、马尔可夫(Markov)信源,M氏链分析方法:,根据状态转移概率矩阵与符号条件概率矩阵画出马尔可夫信源状态转移图(香农线图),根据状态转移图判断能否达到稳定(是否满足不可约性和非周期性),求出平稳分布W。,求出 H(X/si),Page-34的例题2-13,120,2.5 冗余度,非平
43、稳离散信源不一定存在,平稳离散信源,m阶马尔可夫信源,离散无记忆信源,等概分布的无记忆离散信源,121,2.5 冗余度,冗余度的来源:,冗余度的定义 表示给定信源在实际发出消息时所包含的多余信息,也称余度或剩余度。,信源符号间的相关性;,信源符号分布的不均匀性,当等概率分布时信源熵最大,信息效率,122,2.5 冗余度,例:以符号是英文字母的信源为例,英文字母加上空格共有27个。,最大熵为:,近似为无记忆信源的熵:,各个字母出现的概率,考虑到字母之间的依赖性,例如字母T后面出现H、R的可能性较大,出现J、K、L、M、N的可能性极小,而根本不会出现Q、F、X。,二阶、三阶直至高阶平稳信源熵:,1
44、23,2.5 冗余度,信息效率和冗余度为:,写文字的人自由选择的,由语言结构、实际意义等确定,100页的英文书,大约只要存储29页就可以了,其中的71页可以压缩掉,这压缩掉的文字完全可以根据英文的统计特性来恢复。信源的冗余度正是表示这种信源可压缩的程度的。,124,2.5 冗余度,实际的通信系统中,为了提高传输的效率,往往需要把信源的大量冗余进行压缩,这就是所谓的信源编码。,从提高抗干扰能力的角度来看,即提高可靠性来看,总是希望增加或者保留信源的冗余度,或者是传输之前在信源编码后去除冗余的符号序列里加入某些特殊的冗余度,以达到通信系统理想的传输有效性和可靠性,这就是所谓的信道编码。,125,小
45、结信源的描述与分类离散信源的信源熵及互信息量(1)自信息量:联合自信息量:条件自信息量:(2)离散信源熵:,第二章 小结,126,(3)信源熵的三个物理含义表示信源输出后,每个离散消息所提供的平均信息量。表示信源输出前,信源的平均不确定度。反映了信源X的随机性。(4)条件熵:(5)联合熵:,第二章 小结,127,(6)离散信源熵的基本性质:非负性:对称性:确定性:可加性:扩展性:极值性(最大离散熵定理):香农辅助定理:上凸性:(7)互信息量:,第二章 小结,128,(8)数据处理定理:多级处理信息不增、多次独立测量得到的信息大于单次测量的结果。(9)信源熵、互信息之间的关系,第二章 小结,12
46、9,连续信源的熵和互信息量(1)连续信源的相对熵:(2)最大熵定理:限峰功率(取值幅度受限)最大熵定理。限平均功率最大熵定理。离散序列信源熵(1)离散无记忆信源的序列熵:,第二章 小结,130,(2)平稳随机序列的熵:(3)马尔可夫(Markov)信源:稳态分布概率的求法马尔可夫(Markov)信源的信源熵:,第二章 小结,131,冗余度:信息效率:信源的冗余度:,第二章 小结,132,第二章信源及信源熵,发出单个符号的信源:指信源每次只发出一个符号代表一个消息。发出符号序列的信源:指信源每次发出一组含两个以上符号的符号序列代表一个消息。,133,第二章信源及信源熵,发出符号序列的平稳有记忆信源:用信源发出的符号序列的整体概率(即联合概率)反映有记忆信源的特性,序列的统计特性与时间的推移无关。当记忆长度很长甚至无限长时,表述很困难,在实际问题中,我们往往试图限制记忆长度。发出符号序列的非平稳有记忆信源:用信源发出的符号序列的整体概率(即联合概率)反映有记忆信源的特性,序列的统计特性与时间的推移有关。发出符号序列的马尔可夫信源:某一个符号出现的概率只与前面一个或有限个符号有关,而不依赖更前面的那些符号,这样就可以用信源发出符号序列内各个符号之间的条件概率来反映记忆特征。,134,信息论与编码-信源及信源熵,可加性证明:,