《信息论与编码第二章离散信源新.ppt》由会员分享，可在线阅读，更多相关《信息论与编码第二章离散信源新.ppt（103页珍藏版）》请在三一办公上搜索。
1、第二章 离散信源,提纲,信源的数学模型及分类 离散信源的自信息和信息熵离散无记忆的扩展信源离散平稳信源 马尔可夫信源,信源是产生消息的源，根据X的不同情况，信源可分为以下类型：,根据信源的统计特性，离散信源又分为两种：,无记忆信源 X的各时刻取值相互独立。,有记忆信源 X的各时刻取值互相有关联。,2.1信源的数学模型及分类,离散无记忆信源(Discrete Memoryless Source，简记为DMS)输出的是单个符号的消息，不同时刻发出的符号之间彼此统计独立，而且符号集中的符号数目是有限的或可数的。离散无记忆信源的数学模型为离散型的概率空间，即：,p(xi)：信源输出符号消息xi的先验概
2、率;满足：0 q(xi)1，1 i I,一 离散无记忆信源,例1：掷骰子的结果作为信源消息，则就构成了一个这样的信源，其概率空间为：例2：箱中有赤、橙、黄、青、兰、紫六种颜色的32只彩球，其中赤16球，澄8球，黄4球，青2球，蓝、紫各1球。有放回抽取：,一 离散无记忆信源（续）,实际情况下，信源输出的消息往往不是单个符号，而是由许多不同时刻发出的符号所组成的符号序列。设序列由N个符号组成，若这N个符号取自同一符号集 a1,a2,ak，并且先后发出的符号彼此间统计独立，我们将这样的信源称作离散无记忆的N维扩展信源。其数学模型为N维概率空间：,x为各种长为N的符号序列，x=x1 x2 xN，xi
3、a1,a2,ak，1 i N，序列集X=a1a1 a1,a1a1 a2,akak ak，共有kN种序列，x X。,序列的概率p(x)=p(x1x2 xN)=,二 离散无记忆的扩展信源,例,如果X的条件概率分布与时间起点无关，即任意两个不同时刻X的概率分布都相同，则该信源为平稳信源。,对于离散平稳有记忆信源，在 t=i 时刻将要发出什么样的符号决定于两方面：(1)信源在 t=i 时刻随机变量Xi 取值的概率分布P(xi)。一般 P(xi)P(xj)(2)t=i 时刻以前信源发出的符号。即与条件概率P(xi/xi-1 xi-2)有关,三 离散平稳有记忆信源,若当t=i，t=j时(i,j 是大于1的
4、任意整数)，P(xi)=P(xj)=P(x)，则序列是一维平稳的。具有这样性质的信源称为一维平稳信源。除上述条件外，如果联合概率分布P(xixi+1)也与时间起点无关，即P(xixi+1)=P(xjxj+1)(i,j为任意整数且ij)，则信源称为二维平稳信源。它表示任何时刻信源发出二个符号的联合概率分布也完全相等。如果各维联合概率分布均与时间起点无关，那么，信源是完全平稳的。这种各维联合概率分布均与时间起点无关的完全平稳信源称为离散平稳信源。这时有：,P(xi)=P(xj)P(xi xi+1)=P(xj xj+1)P(xi xi+1 xi+N)=P(xj xj+1 xi+N),如如果在任何时刻
5、其符号发生的概率只与前面已经发生的m个符号有关，而与更前面发生的符号无关，则称该信源为m价马尔可夫信源,四马尔可夫信源,如果上述条件概率与时间起点i无关，则称为时齐马可夫信源。,2.2 离散信源的自信息和信息熵,针对离散信源进行基本概念样本空间：某一事物各种可能出现的不同状态，即所有可能选择的信息的集合概率测度：对每个可能选择的信息指定一个概率（非负，总和为1）概率空间：一个样本空间和他的概率测度先验概率：后验概率自信息：信息熵,概率空间,样本空间,概率测度,例1 如果将掷一次骰子的结果作为信源消息，则就构成了一个这样的信源，其概率空间为：,例2 箱中有赤、橙、黄、青、兰、紫六种颜色的32只彩
6、球，其中赤16球，澄8球，黄4球，青2球，蓝、紫各1球。现任取一球，将其色彩视为一个离散信源的输出，则该信源可用下列概率空间描述：,发送端 接收端,自信息,解决信息的度量问题 信源发出的消息是随机的。未接收之前，收信者对信源发出的消息是不确定的。消息传到收信者后，才消除了不确定性，获得了信息。某一消息发出的不确定性越大，一旦发生，接收者消除的不确定性就越大，获得的信息也就越大。一般而言，收信者所获取的信息量，在数量上等于通信前后不确定性消除（减少）的量。,获取信息量=收信前对某事件发生的不确定性-该事件发生后仍然存在的不确定性假设发送符号为ai,，接收符号为收bj。可以直观地把信息量定义为：收
7、到某消息bj后获得关于某事件ai发生的信息量=收到bj前、后对某事件ai存在的不确定性的消除=收信前关于某事件的不确定性（先验不定度）-收信后关于某事件发生的不确定性（后验不定度）,先验概率越大，得到的信息量越小，反之信息量越大中国足球队3:0战胜巴西足球队巴西足球队3:0战胜中国足球队,注意,例1 一个布袋内放100个球，其中80个球是红色的，20个球是白色的，若随机摸取一个球，猜测其颜色，求平均摸取一次所能获得的自信息量。解:依据题意 这一随机事件的概率空间为,其中：x1表示摸出的球为红球事件，x2表示摸出的球是白球事件.如果摸出的是红球，则获得的信息量是 I（x1）=-log2p（x1）
8、=-log20.8 bit 如果摸出的是白球，则获得的信息量是 I（x2）=-log2p（x2）=-log20.2 bit,说明：,自信息量I(x1)和I(x2)只是表征信源中各个符号的不确定度，一个信源总是包含着多个符号消息，各个符号消息又按概率空间的先验概率分布，因而各个符号的自信息量就不同。所以自信息量不能作为信源总体的信息量。,信息熵,定义：,例1续,（3）如果每次摸出一个球后又放回袋中，再进行下一次摸取。则如此摸取n次，红球出现的次数为np（x1）次，白球出现的次数为np（x2）次。随机摸取n次后总共所获得的信息量为 np（x1）I（x1）+np（x2）I（x2）,则平均随机摸取一次
9、所获得的信息量为 H（X）=1/nnp(x1)I(x1)+np(x2)I(x2)=-p(x1)log2p(x1)+p(x2)log2p(x2),=0.72比特/次,例2 设甲地的天气预报为：晴(占48)、阴(占28)、大雨(占18)、小雨(占18)。又设乙地的天气预报为：晴(占78)，小雨(占18)。试求两地天气预报各自提供的平均信息量。若甲地天气预报为两极端情况，一种是晴出现概率为1而其余为0。另一种是晴、阴、小雨、大雨出现的概率都相等为14。试求这两极端情况所提供的平均信息量。又试求乙地出现这两极端情况所提供的平均信息量。,两个信源,解：甲地天气预报构成的信源空间为:,则其提供的平均信息量
10、即信源的信息熵:,乙地天气预报的信源空间为:,结论：甲地天气预报提供的平均信息量大于乙地，因为乙地比甲地的平均不确定性小。,甲地极端情况,极端情况1：晴天概率1,结论：等概率分布时信源的不确定性最大，所以信息熵（平均信息量）最大。,极端情况2：各种天气等概率分布,乙地极端情况,极端情况1：晴天概率1,结论：在极端情况2下，甲地比乙地提供更多的信息量。因为，甲地可能出现的消息数比乙地可能出现的消息数多。,极端情况2：各种天气等概率分布,说明：,熵的基本性质,（5）可加性 统计独立信源X和Y的联合信源的熵等于信源X和Y各自的熵之和。H(XY)=H(X)+H(Y),可加性是熵函数的一个重要特性，正因
11、具有可加性，才使熵函数的形式是唯一的。,证明：,例如，甲信源为,它们的联合信源是,可计算得联合信源的联合熵：H(Z)=H(XY)=log(nm)=log m+log n=H(X)+H(Y),乙信源为,（6）强可加性两个互相关联的信源X和Y的联合信源的熵等于信源X的熵加上在X已知条件下信源Y的条件熵。H（XY）=H（X）+H（Y/X）,H（Y/X）表示信源 X 输出一符号的条件下，信源Y再输出一符号所能提供的平均信息量，称为条件熵。,H（XY）=H（X）+H（Y/X）的证明：,H（XY）=H（X）+H（Y/X）,（7）递增性,若原信源 X 中有一个符号分割成了m个元素(符号)，这m个元素的概率之
12、和等于原元素的概率，而其他符号的概率不变，则新信源的熵增加。熵的增加量等于由分割而产生的不确定性量。,证明可以从熵的定义或强可加性得出：,即得：,递增性的推广,它表示n个元素的信源熵可以递推成(n-1)个二元信源的熵函数的加权和。这样，可使多元信源的熵函数的计算简化成计算若干个二元信源的熵函数。因此，熵函数的递增性又可称为递推性。,（8）极值性在离散信源情况下，信源各符号等概率分布时，熵值达到最大。,性质表明等概率分布信源的平均不确定性为最大。这是一个很重要的结论，称为最大离散熵定理。,证明：因为对数是型凸函数，满足詹森不等式Elog Y log EY，则有：,二进制信源是离散信源的一个特例。
13、该信源符号只有二个，设为“0”和“1”。符号输出的概率分别为“”和“1-”，即信源的概率空间为：,H(X)=-log(1-)log(1-)=H(),即信息熵H(x)是的函数。取值于0，1区间，可画出熵函数H()的曲线来，如右图所示。,熵函数H(P)是概率矢量P(p1，p2，pq)的严格型凸函数(或称上凸函数)。它表示：对任意概率矢量P1(p1,p2,pq)和P2(p1,p2,pq)，和任意的 01，有：H P1十(1-)P2 H(P1)十(1-)H(P2)因为熵函数具有上凸性，所以熵函数具有极值，其最大值存在。,（9）上凸性,例题,例4,例5,当离散平稳无记忆信源发出固定长度的消息序列时，则得
14、到原信源的扩展信源。例如在电报系统中，若信源输出的是二个二元数字组成的符号序列，此时可认为是一个新的信源，它由四个符号（00，01，10，11）组成，我们把该信源称为二元无记忆信源的二次扩展信源。如果把N个二元数字组成一组，则信源等效成一个具有2N个符号的新信源，把它称为二元无记信源的N次扩展信源。,2.3 离散无记忆的扩展信源,一般情况下，对一个离散无记忆信源X，其样本空间为a1,a2,aq，对它的输出消息序列，可用一组组长度为N的序列来表示它。这时，它等效成一个新信源。新信源输出的符号是N维离散随机矢量X=(X1，X2,XN)，其中每个分量Xi(i1,2,N)都是随机变量，它们都取值于同一
15、信源符号集，并且分量之间统计独立，则由随机矢量X 组成的新信源称为离散无记忆信源X的N次扩展信源。,单符号离散信源X的数学模型：,N次扩展信源与单符号离散信源比较：数学模型相同但输出不是单个符号，而是一串N个相互独立的符号序列：X(X1,X2,XN)，联合分布密度P(X)=P(X1X2XN)把 X 等效为一个新信源，称为X的N次扩展信源，其数学模型：,因为是无记忆的(彼此统计独立)则：,例6,离散无记忆扩展信源的信息熵,其中：,同理计算式中其余各项，得到：,H(XN)=H(X)+H(X)+H(X)=N H(X),证：,例7,一、离散平稳信源的数学定义二、二维平稳信源及其信息熵三、离散平稳信源的
16、极限熵,2.4离散平稳信源,一、离散平稳信源的数学定义 在一般情况下，信源在 t=i 时刻将要发出什么样的符号决定于两方面：(1)信源在 t=i 时刻随机变量Xi 取值的概率分布P(xi)。一般 P(xi)P(xj)(2)t=i 时刻以前信源发出的符号。即与条件概率P(xi/xi-1 xi-2)有关对平稳随机序列，序列的统计性质与时间的推移无关，即信源发出符号序列的概率分布与时间起点无关。,平稳随机序列的数学定义如下：若当t=i，t=j时(i,j 是大于1的任意整数)，P(xi)=P(xj)=P(x)，则序列是一维平稳的。具有这样性质的信源称为一维平稳信源。除上述条件外，如果联合概率分布P(x
17、ixi+1)也与时间起点无关，即P(xixi+1)=P(xjxj+1)(i,j为任意整数且ij)，则信源称为二维平稳信源。它表示任何时刻信源发出二个符号的联合概率分布也完全相等。如果各维联合概率分布均与时间起点无关，那么，信源是完全平稳的。这种各维联合概率分布均与时间起点无关的完全平稳信源称为离散平稳信源。这时有：,P(xi)=P(xj)P(xi xi+1)=P(xj xj+1)P(xi xi+1 xi+N)=P(xj xj+1 xi+N),由于联合概率与条件概率有以下关系：,结论：对于平稳信源来说，其条件概率均与时间起点无关，只与关联长度N有关。即平稳信源发出的平稳随机序列前后的依赖关系与时
18、间起点无关。,从平稳性可得：,对平稳信源如果某时刻发出什么符号只与前面发出的N个符号有关，那么任何时刻它们的依赖关系都是一样的。即：,二、二维平稳信源及其信息熵 最简单的平稳信源就是二维平稳信源。它满足一维和二维概率分布与时间起点无关。,同时已知：连续两个信源符号出现的联合概率分布为P(ai aj)(i,j=1,q)，且：,设有一个离散一维平稳信源，其概率空间为：,由于只有两个符号有关联，且其关联与时间无关，则我们可把这个信源输出的随机序列分成每二个符号一组(因为相邻的两个符号才有关联)，每组构成新信源的一个符号，并假设组与组之间统计无关(实际上，组尾的符号与下一组组头的符号是有关的)。这时，
19、等效成一个新的信源X1X2，它们的联合概率空间为：,根据信息熵的定义，得：,H(X1X2)称为X1X2的联合熵。,关于离散二维平稳信源联合熵的说明,H(X1X2)表示原来信源X输出任意一对消息的共熵，即描述信源X输出长度为2的序列的平均不确定性（或所含有的信息量）。可用H(X1X2)/2作为信源X的信息熵的近似值。,从另一角度（来研究信源X的信息熵的近似值）：（1）由于信源X发出的符号序列中前后两个符号之间有依赖性，可以先求出在已知前面一个符号Xlai时，信源输出下一个符号的平均不确定性：,（2）前面一个符号Xl又可取aia1，a2，aq中任一个，对某一个ai存在一个平均不确定性H(X2/X1
20、ai)，那么对所有ai的可能值进行统计平均就得当前面一个符号巳知时，再输出下一个符号的总的平均不确定性H(X2/X1)：,（3）根据概率关系，可以得到联合熵与条件熵的关系：,（4）也可以得到条件熵和无条件熵的关系H(X2/X1)H(X2)（证明见p43）,因此 H(X1X2)H(X1)+H(X2/X1)H(X1)+H(X2)=2H(X)所以，一般情况下，输出二个符号的联合熵总是小于二倍信源的熵。,例8 某一离散二维平稳信源,其发出的符号只与前一个符号有关，即可用联合概率P(aiaj)给出它们的关联程度，如下表所示,求信源的熵H(X)、条件熵H(X2/X1)和联合熵H(X1X2)。,三、离散平稳
21、信源的极限熵,其中,的性质,该性质表明联合熵等于起始时刻的无条件熵与各阶条件熵之和，并不随时间的推移而变化,该性质表明：在确知前面（N1）个时刻的符号的前提下，再发第N个符号提供的平均信息量，一定不超过每发一个符号提供的平均信息量（即平均符号熵）。,表明，平均符号熵HN（X）的最大值就是原始信源X p的熵，而且它随N的增加是非递增的,2.5 马尔可夫信源,一、马氏链的基本概念和主要特性二、马尔柯夫信源 三、马尔柯夫信源的信息熵,一、马氏链的基本概念和主要特性,马尔可夫信源是一类相对简单的有记忆信源，信源在某一时刻发出某一符号的概率除与该符号有关外，只与此前发出的有限个符号有关。,二、马尔柯夫信
22、源,我们把前面若干个符号看作一个状态，可以认为信源在某一时刻发出某一符号的概率除了与该符号有关外，只与该时刻信源所处的状态有关，而与过去的状态无关。信源发出一个符号后，信源所处的状态即发生改变，这些状态的变化组成了马氏链。,马尔可夫信源状态转移图,描述马尔可夫信源，我们可以用马尔可夫链的状态转移图。1、把每个可能出现的状态用一个圆圈表示；2、圆圈之间用有向线段连接，表示状态的迁移；3、在有向线段旁边，注明发出的符号 及在状态 下发出 的条件概率,马尔可夫信源状态转移图,该马尔可夫信源有三个状态：，其中设为初始状态，初始概率为，等概率的转移到 这两个状态,例,一步转移概率矩阵,m阶马尔可夫信源的条件概率,m阶马尔可夫信源的极限熵,三、马尔柯夫信源的信息熵,例 设有一个二元2阶马尔可夫信源，其信源符号集为,解得,计算极限熵,
