信息论与编码（傅祖云讲义）第二章ppt课件.ppt

《信息论与编码（傅祖云讲义）第二章ppt课件.ppt》由会员分享，可在线阅读，更多相关《信息论与编码（傅祖云讲义）第二章ppt课件.ppt（62页珍藏版）》请在三一办公上搜索。

1、第二章 离散信源及其信息测度,第一节 信源的数学模型及分类,第二节 离散信源的信息熵,第三节 信息熵的基本性质,第四节 离散无记忆的扩展信源,第五节 离散平稳信源,第六节 马尔可夫信源,第七节 信源剩余度与自然语言的熵,信源的主要问题 1如何描述信源（信源的数学建模问题） 2怎样计算信源所含的信息量 3怎样有效的表示信源输出的消息，也就是信源编码问题,第一节 信源的数学模型及分类,在通信系统中，收信者在未收到信息以前，对信源发出什么样的消息是不确定的，是随机的，所以可以用随机变量、随机矢量或随机过程来描述信源输出的消息，或者说用一个样本空间及其概率测度来描述信源。 不同的信源根据其输出消息的不

2、同的随机性质进行分类。,信源的定义及分类,离散信源连续信源,信源是发出消息的源，信源输出以符号形式出现的具体消息。按照信源发出的消息在时间上和幅度上的分布情况：,是指发出在时间和幅度上都是离散分布的离散消息的信源，如文字、数字、数据等符号都是离散消息。,是指发出在时间和幅度上都是连续分布的连续消息（模拟消息）的信源，如语言、图像、图形等都是连续消息。,第一节 信源的数学模型及分类,1、离散信源 数学模型如下：,集合X中，包含该信源包含的所有可能输出的消息，集合P中包含对应消息的概率密度，各个消息的输出概率总和应该为1。 例：掷骰子；抛硬币；天气预报,第一节 信源的数学模型及分类,2、连续信源

3、数学模型如下：,每次只输出一个消息，但消息的可能数目是无穷多个。 例：电压、温度等。,离散信源的进一步分类,发出单个符号的信源发出符号序列的信源,指信源每次只发出一个符号代表一个消息,指信源每次发出一组含二个以上符号的符号序列代表一个消息,根据随机变量间是否统计独立将信源分为有记忆信源和无记忆信源。离散无记忆信源离散有记忆信源,所发出的各个符号是相互独立的，发出的符号序列中的各个符号之间没有统计关联性，各个符号的出现概率是它自身的先验概率。,所发出的各个符号的概率是有关联的。,有记忆信源符号间的概率关联性可用两种方式：一种是用信源发出的一个符号序列的整体概率（即联合概率）反映有记忆信源的特征一

4、种限制记忆长度，即某一个符号出现的概率只与前面一个或有限个符号有关，而不依赖更前面的那些符号，这样的信源可以用信源发出符号序列内各个符号之间的条件概率来反映记忆特征，这就是发出符号序列的马尔可夫信源,根据各维随机变量的概率分布是否随时间的推移而变化将信源分为平稳信源和非平稳信源,一个实际信源的统计特性往往是相当复杂的，要想找到精确的数学模型很困难。实际应用时常常用一些可以处理的数学模型来近似。随机序列，特别是离散平稳随机序列是我们研究的主要内容。,第二节 离散信源的信息熵,1、自信息 我们认为，一个字符它所携带的信息量是和该字符出现的概率有关，概率可以表征自信息量的大小,根据客观事实和人们的习

5、惯概念，应满足以下条件:,第二节 离散信源的信息熵,（3）当 时,（4）两个独立事件的联合信息量应等于它们分别的信息量之和。,(1) 应是先验概率的单调递减函数，即当 时,第二节 离散信源的信息熵,根据上述条件可以从数学上证明这种函数形式是对数函数，即：,有两个含义：,1、当事件发生前，表示该事件发生的不确定性；2、当事件发生后，表示该事件所提供的信息量,自信息量的单位取决于对数所取的底，若以2为底，单位为比特，以e为底，单位为奈特，以10为底，单位为哈特,通常取比特为单位,第二节 离散信源的信息熵,例：设天气预报有两种消息，晴天和雨天，出现的概率分别为1/4和3/4，我们分别用 来表示晴天，

6、以 来表示雨天，则我们的信源模型如下：,第二节 离散信源的信息熵,我们定义自信息的数学期望为信源的平均信息量,信息熵具有以下两种物理含义：1、表示信源输出前信源的平均不确定性2、表示信源输出后，每个符号所携带的平均信息量,2、信息熵,例：天气预报，有两个信源,则：,说明第二个信源的平均不确定性更大一些,第二节 离散信源的信息熵,第三节 信息熵的基本性质,熵函数可以表示为：,第三节 信息熵的基本性质,性质1：非负性,H(X)0由于0pi1,所以logpi0，则总有H(X)0。,性质2：对称性,根据加法交换律可以证明，当变量交换顺序时熵函数的值不变。信源的熵只与概率空间的总体结构有关，而与个概率分

7、量对应的状态顺序无关；,第三节 信息熵的基本性质,性质3：确定性；,当信源X的信源空间X，P中。任一个概率分量等于1，根据完备空间特性，其它概率分量必为0，这时信源为一个确知信源，其熵为0。如果一个信源的输出符号几乎必然为某一状态，那么这个信源没有不确定性，信源输出符号后不提供任何信息量。,第三节 信息熵的基本性质,性质4：扩展性,这说明信源空间中增加某些概率很小的符号，虽然当发出这些符号时，提供很大的信息量，但由于其概率接近于0，在信源熵中占极小的比重，使信源熵保持不变。,第三节 信息熵的基本性质,性质5 ：极值性,上式表明，对于具有q个符号的离散信源，只有在q个信源符号等可能出现的情况下，

8、信源熵才能达到最大值，这也表明等概分布的信源的平均不确定性最大，这是一个很重要得结论，称为最大离散熵定理,例：对于一个二元信源 H(X)=H(1/2,1/2)=log2=1bit/信源符号,第四节 离散无记忆的扩展信源,实际信源输出的消息往往是时间上或空间上的一系列符号，如电报系统，序列中前后符号间一般是有统计依赖关系的。 我们先讨论离散无记忆信源，此时，信源序列的前后符号之间是统计独立的 如在二元系统中，我们可以把两个二元数字看成一组，会出现四种可能情况：00、01、10和11，我们可以把这四种情况看成一个新的信源称为二元无记忆信源的二次扩展信源，相应的，如果把N个二元数字看成一组，则新的信

9、源称为二元无记忆信源的N此扩展信源。,第四节 离散无记忆的扩展信源,一般情况设一个离散无记忆信源为：,则该信源的N次扩展信源为：,第四节 离散无记忆的扩展信源,其中：,根据信息熵的定义：,可以证明，对于离散无记忆的扩展信源,例: 离散无记忆信源的N次扩展信源离散无记忆信源为：X:a1,a2,a3; P(X):1/4, 1/2, 1/4,2次扩展信源为：,:A1A9,信源的9个符号为：,第四节 离散无记忆的扩展信源,第四节 离散无记忆的扩展信源,其概率关系为 :,计算可知,第五节 离散平稳信源,一般来说，信源的前后消息之间有前后依赖关系，可以用随机矢量描述：,信源在某一时刻发出什么样的值取决于两

10、方面1、这一时刻该变量的概率分布2、这一时刻以前发出的消息 如一个人讲话 我们现在讨论平稳的随机序列，所谓平稳是指序列的统计性质与时间的推移无关（两个任意时刻信源发出相同符号的概率分布完全相同）。,1、离散平稳信源的数学定义,第五节 离散平稳信源,2、二维平稳信源及其信息熵,最简单的平稳信源二维平稳信源，信源发出序列中只有前后两个符号间有依赖关系，我们可以对其二维扩展信源进行分析。信源的概率空间:连续两个信源符号出现的联合概率分布为：,第五节 离散平稳信源,已知符号 出现后，紧跟着 出现的条件概率为：,由二维离散信源的发出符号序列的特点可以把其分成每两个符号一组，每组代表新信源 中的一个符号。

11、并假设组与组之间是统计独立的，互不相关的。,得到一个新的离散无记忆信源 ，其联合概率空间为：,第五节 离散平稳信源,根据信息熵的定义，可得：（1）联合熵,可以表征信源输出长度为2的平均不确定性，或所含有的信息量。因此可以用 作为二维平稳信源的信息熵的近似值,第五节 离散平稳信源,(2)条件熵,则：,第五节 离散平稳信源,可以证明：,例2-15 设某二维离散信源的原始信源的信源空间 X=x1,x2,x3; P(X)=1/4, 1/4, 1/2, 一维条件概率为： p(x1/x1)=1/2; p(x2/x1)=1/2; p(x3/x1)=0; p(x1/x2)=1/8; p(x2/x2)=3/4;

12、 p(x3/x2)=1/8; p(x1/x3)=0; p(x2/x3)=1/4; p(x3/x3)=3/4;,第五节 离散平稳信源,例2-15 原始信源的熵为： H(X)=1.5 bit/符号条件熵： H(X2/X1)=1.4 bit/符号可见： H(X2/X1)H(X)二维信源的熵：H(X1X2)=H(X1)+H(X2/X1)=2.9 bit/消息每个信源符号提供的平均信息量为： H2(X1X2)=H(X1X2)/2=1.45 bit/符号。,第五节 离散平稳信源,第五节 离散平稳信源,我们现在有两种方法去近似信源的实际熵，一种是平均符号熵H(X1X2)/2为1.45bit，但这种方法不太准

13、确，因为它把两个消息看成一组，认为两组之间是统计独立的，实际上它们之间是有关联的；另一种是我们可以用条件熵来近似，H(X2/X1)为1.4bit，到底那一种正确呢？我们可以通过对一般离散平稳信源的分析来找到这个答案。,分析：我们用,来近似信源的实际熵,第五节 离散平稳信源,3、离散平稳信源的极限熵,平均符号熵,条件熵,有以下几点性质,（1）条件熵随N的增加是非递增的 （2）N给定时，平均符号熵大于等于条件熵 （3）平均符号熵随N的增加是非递增的 （4）,称 为极限熵。,第五节 离散平稳信源,可以证明，对于二维离散平稳信源，条件熵等于极限熵，因此条件熵就是二维离散平稳信源的真实熵 对于一般信源，

14、求出极限熵是很困难的，然而，一般来说，取N不大时就可以得到与极限熵非常接近的条件熵和平均符号熵，因此可以用条件熵和平均符号熵来近似极限熵,第六节 马尔可夫信源,在很多信源的输出序列中，符号之间的依赖关系是有限的，任何时刻信源符号发生的概率只与前边已经发出的若干个符号有关，而与更前面的符号无关。 为了描述这类信源除了信源符号集外还要引入状态集。这时，信源输出消息符号还与信源所处的状态有关。 若一个信源满足下面两个条件，则称为马尔可夫信源：（1）某一时刻信源输出的符号的概率只与当前所处的状态有关，而与以前的状态无关；（2）信源的下一个状态由当前状态和下一刻的输出唯一确定。,设某二阶马尔可夫信源所处

15、的状态E=E0,E1,E2,E3=00，01，10，11 ，在每一状态下可能输出的符号0，1。,0 0 1 0 1 1 0 0 1 1 0 1 0,E0=00,1,E1=01,0,E2=10,1,E1=01,1,E3=11,0,E2=10,P(1/E0)= P(E1/E0)=P01,第六节 马尔可夫信源,（1）某一时刻信源输出的符号的概率只与当前所处的状态有关，而与以前的状态无关。即,当符号输出概率与时刻L无关，称为具有时齐性。即,第六节 马尔可夫信源,（2）信源的下一个状态由当前状态和下一刻的输出唯一确定。,条件（2）表明，若信源处于某一状态 ，当它发出 一个符号后，所处的状态就变了，一定转

16、移到另一状态。 状态的转移依赖于发出的信源符号，因此任何时刻信源处在什么状态完全由前一时刻的状态和发出的符号决定。,第六节 马尔可夫信源,例：二阶马尔可夫信源，原始符号集为1,0， 条件概率定为：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 由此可见，信源共有22=4种状态 E：E1=00,E2=01,E3=10,E4=11,第六节 马尔可夫信源,状态之间有转移概率，p(e2/e1)=p(e3/e4)=0.2p(e2/e4)=p(e1/e3)=p(e2/e3)=p(e3/e2)=0.5P(

17、e1/e1)=p(e4/e4)=0.8其状态转移图如下页。在状态转换图中，把信源的每一种状态用圆圈表示，用有向箭头表示信源发出某一符号后由一种状态到另一状态的转移。,第六节 马尔可夫信源,0:0.5,1:0.2,0:0.2,1:0.5,0:0.5,1:0.5,由上例可知，m阶马尔可夫信源符号集共有q个符号，则信源共有 个不同状态。信源在某一时刻时，必然处于某一种状态，等到下一个字符输出时，转移到另外一个状态。,举 例,例2.2.3 设信源符号 Xx1, x2, x3 ，信源所处的状态Se1, e2, e3, e4, e5 。各状态之间的转移情况由图2.2.1给出。,将图中信源在ei状态下发符号

18、xk 的条件概率p(xk /ei)用矩阵表示由矩阵看出：由图中看出：由图中可得状态的一步转移概率：该信源满足马尔可夫信源定义。,第六节 马尔可夫信源,定义 (P58)为各状态的极限概率，则时齐、遍历的马尔可夫信源的熵为,第六节 马尔可夫信源,马尔可夫信源的熵：这里这给出结论：,表明m阶马尔可夫信源的极限熵等于m阶条件熵。根据求条件熵公式还可得到,(3) 举 例,例2.2.4 二元2阶马尔可夫信源，原始信号X的符号集为X1=0, X2=1，其状态空间共有nm=22=4个不同的状态e1,e2,e3,e4，即 E：e1=00,e2=01,e3=10,e4=11 状态转移图见右图所示。解：p(e1/e

19、1)= p(x1/e1)=p(0/00)=0.8 p(e2/e1)= p(x2/e1)=p(1/00)=0.2 p(e3/e2)= p(x1/e2)=p(0/01)=0.5 p(e4/e2)= p(x2/e2)=p(1/01)=0.5 p(e1/e3)= p(x1/e3)=p(0/10)=0.5 p(e2/e3)= p(x2/e3)=p(1/10)=0.5 p(e3/e4)= p(x1/e4)=p(0/11)=0.2 p(e4/e4)= p(x2/e4)=p(1/11)=0.8,由二元信源X0,1得到的状态空间(e1,e2,e3,e4)和相应的一步转移概率构成的2阶马尔可夫信源模型为求出稳定状

20、态下的p(ej) ，称为状态极限概率。将一步转移概率代入上式得p(e1)=0.8 p(e1)+0.5 p(e3)p(e2)=0.2 p(e1)+0.5 p(e3)p(e3)=0.5 p(e2)+0.2 p(e4)p(e4)=0.5 p(e2)+0.8 p(e4),解方程组得p(e1)= p(e4)=5/14p(e2)= p(e3)=2/14计算极限熵,第六节 马尔可夫信源,例：一个二元二阶马尔可夫信源，信源符号集A=0,1。信源开始时，它以概率p(0)=p(1)=0.5发出随机变量X1。然后，下一单位时间输出的随机变量X2与X1有依赖关系，由条件概率p(x2|x1)表示： 再下一单元时间输出随

21、机变量X3，而X3依赖于前面变量。依赖关系由条件概率p(x3|x1x2)表示：,第六节 马尔可夫信源,由从第四单位时间开始，任意时刻信源发出的随机变量Xi只与前面二个单位时间的随机变量有关，根据提议可得信源的状态转移图：,第六节 马尔可夫信源,00,01,10,11,第六节 马尔可夫信源,0.5,0.5,0.4,0.8,0.3,0.6,0.2,0.7,0.6,0.4,第六节 马尔可夫信源,解得：,第六节 马尔可夫信源,解得： 代入式（2.136） 得 0.8956当马尔可夫信源达到稳定后，符号0和1的分布概率可根据下式计算 因此得：,第七节 信源剩余度与自然语言的熵,1、关于离散信源熵的总结： 实际信源可能是非平稳的有记忆随机序列信源；其极限熵是不存在的；解决的方法是假设其为离散平稳随机序列信源，极限熵存在，但求解困难；进一步假设其为m阶Markov信源，用其m阶条件熵近似； 再进一步假设为一阶Markov信源，用其一阶条件熵 来近似；最简化的信源是离散无记忆信源，其熵为H(x); 最后可以假定为等概的离散无记忆信源，其熵H(x)； 它们之间的关系可以表示为：,第七节 信源剩余度与自然语言的熵,2、熵的相对率(传输效率),3、信源剩余度,第七节 信源剩余度与自然语言的熵,4、自然语言的熵,（1）对于英文字母,（2）对于中文,我们可以压缩剩余度来压缩信源，提高通信的可靠性。,