《《信源及信源熵》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《信源及信源熵》PPT课件.ppt(144页珍藏版)》请在三一办公上搜索。
1、第二章 信源及信源熵,信源及信源熵,2.1 信源的数学模型和分类2.2 离散信源熵和互信息2.3 离散序列信源的熵2.4 冗余度2.5 连续信源和波形信源,2.1 信源的数学模型和分类,信息论对信源研究的内容:,信源的建模:用恰当的随机过程来描述信号关心角度:信号中携带的信息信源输出信号中携带信息的效率的计算熵率、冗余度信源输出信息的有效表示信源编码,信息论不研究信源的内部结构,不研究信源为什么产生和怎样产生各种不同的、可能的消息,而只研究信源的各种可能的输出,以及输出各种可能消息的不确定性。,信源特性与分类,信源的统计特性1)什么是信源?信源是信息的来源,是产生消息(符号)、消息序列(符号序
2、列)以及连续消息的来源。实际通信中常见的信源有:语音、文字、图像、数据。2)信源的主要特性信源的最基本的特性是具有统计不确定性,即信源发出的消息是不确定的、随机的,因此可以用随机变量、随机矢量或随机过程来描述信源输出的消息。一般使用一个样本空间及其概率测度概率空间(信源空间)来描述信源,此概率空间也称为信源的数学模型。,一、离散信源和连续信源,离散信源信源发出的消息在时间上和幅度上是离散分布的。信源是由有限或无限个取值离散的符号。例如:投硬币、书信文字、计算机的代码、电报符号、阿拉伯数字码等等。连续信源信源发出的消息在时间上和幅度上是连续分布的。信源符号集A的取值是连续的,或者取值为实数集(,
3、)。例如:语音信号、热噪声信号、图像等等。,二、离散信源的数学模型,(一)单消息(符号)信源信源可能输出的符号集的取值是有限的或可数的,而且每次只输出其中一个符号代表一个消息。它是最简单、最基本的信源,是组成实际信源的基本单元。,单符号离散信源的数学模型,我们可用一维离散型随机变量X来描述单符号离散信源输出的消息。这个随机变量X的样本空间就是符号集A=a1 a2 aN;而X的概率分布就是各消息出现的先验概率,信源的概率空间必定是一个完备集(即P1)。该信源的数学模型就是离散型的概率空间,我们可以用信源取值随机变量的范围X和对应概率分布P(x)共同组成的二元序对X,P(x)来表示。当信源给定,其
4、相应的概率空间就已给定;反之,如果概率空间给定,这就表示相应的信源已给定。所以,概率空间能表征这离散信源的统计特性,因此有时也把这个概率空间称为信源空间。,信源空间:显然有:,X,P(x),a1 a2 aN,P(a1)P(a2)P(aN),例:对于二进制数据、数字信源:X=0,1,若这两个符号是等概率出现的,则有:,X,P(x),a1=0 a2=1,P(a1)=0.5 P(a2)=0.5,(二)多符号离散信源是发出符号序列的信源信源每次发出一组含两个以上信源符号的符号序列代表一个消息。又叫作离散信源的N次扩展。信道的输入端与输出端对应,都是一个由同样个数的符号所组成的符号序列代表的消息。,平稳
5、信源,很多实际信源输出的消息往往是由一系列符号序列所组成的。可以把这种信源输出的消息看做时间上或空间上离散的一系列随机变量,即为随机矢量。这时,信源的输出可用N维随机矢量X=(X,XXN)来描述,其中N可为有限正整数或可数的无限值。这N维随机矢量X有时也称为随机序列。一般来说,信源输出的随机序列的统计特性比较复杂,分析起来也比较困难。为了便于分析,我们假设信源输出的是平稳的随机序列,也就是序列的统计性质与时间的推移无关。很多实际信源也满足这个假设。若在信源输出的随机序列X=(,)中,每个随机变量Xi(i=1,2,,N)都是取值离散的离散型随机变量,即每个随机变量Xi的可能取值是有限的或可数的;
6、而且随机矢量X的各维概率分布都与时间起点无关,也就是在任意两个不同时刻随机矢量X的各维概率分布都相同。这样的信源称为离散平稳信源。如中文自然语言文字,离散化平面灰度图像都是这种离散型平稳信源。,离散无记忆信源,在某些简单的离散平稳信源情况下,信源先后发出的一个个符号彼此是统计独立的。也就是说发出的信源发出的符号是相互独立的,发出符号序列中各个符号之间也是相互独立的。我们称由信源空间X,P(x)描述的信源X为离散无记忆信源。这类信源在不同时刻发出的符号之间是无依赖的,彼此统计独立的,各个符号的出现概率是其自身的先验概率。信源输出的随机矢量X=(XXX)中,各随机变量Xi(i=1,2,N)之间是无
7、依赖的、统计独立的,则N维随机矢量的联合概率分布满足:,离散无记忆信源X的N次扩展信源,我们把这信源X所输出的随机矢量X所描述的信源称为离散无记忆信源X的N次扩展信源。可见,N次扩展信源是由离散无记忆信源输出N长的随机序列构成的信源。离散无记忆信源的N次扩展信源的数学模型是X信源空间的N重空间。,有记忆信源,一般情况下,信源在不同时刻发出的符号之间是相互依赖的。也就是信源输出的平稳随机序列X中,各随机变量xi之间是有依赖的。例如,在汉字组成的中文序列中,只有根据中文的语法、习惯用语、修辞制约和表达实际意义的制约所构成的中文序列才是有意义的中文句子或文章。所以,在汉字序列中前后文字的出现是有依赖
8、的,不能认为是彼此不相关的。其他如英文,德文等自然语言都是如此。这种信源称为有记忆信源。我们需在N维随机矢量的联合概率分布中,引入条件概率分布来说明它们之间的关联。,马尔可夫信源,表述有记忆信源要比表述无记忆信源困难得多。实际上信源发出的符号往往只与前若干个符号的依赖关系强,而与更前面的符号依赖关系弱。为此,可以限制随机序列的记忆长度。当记忆长度为m+1时,称这种有记忆信源为m阶马尔可夫信源。也就是信源每次发出的符号只与前m个符号有关,与更前面的符号无关。,离散信源的分类:,分类依据:前后符号之间的关系,2.2 离散信源的信息熵,信源空间:,一、离散消息的自信息量,(一)自信息量/非平均自信息
9、量离散信源符号集合A中的某一个符号ai作为一条消息发出时对外提供的信息量:I,自信息量的单位单位之间的关系:1nit=1.443bit;1 hart=3.322bit。,【例2.1】设信源只有两个符号“0”和“1”,且它们以消息的形式向外发送时均以等概率出现,求它们各自的自信息量。,(二)不确定度d(ai)与自信息量I(ai)两者的联系数值上相等,单位也相等,但含义不同。两者的区别具有某种概率分布的随机事件,不管其发生与否,都存在不确定度,不确定度是任何随机事件本身所具有的属性。自信息量是用来消除不确定度的,消息只有被接收之后才有信息量,否则只有不确定度。,二、离散信息熵离散消息集合的平均不确
10、定度,(一)信息熵自信息量的数学期望值是信源的平均自信息量。(注:数学期望就是随机变量的统计平均值)信息熵H(X)=E I(X)=P(xi)I(xi)=P(xi)log P(xi)=P(xi)log 1/P(xi)单位为:比特/符号(单符号信源)、比特/符号序列(多符号信源)。,信源熵H(X)是从平均意义上来表征信源的总体特征,可以表示信源的平均不确定度。对于特定的信源(即概率空间给定),其信源熵是一个确定的数值,不同的信源因统计特性不同,其熵也不同。,例,通过例子了解信息熵的含义:一个布袋内放100个球,其中80个为红球,20个为白球,任摸取一个,猜测是什么颜色。如果摸出红球,那么这一事件的
11、自信息量为:I(x1)=log P(x1)=log 0.8 bit 如果摸出白球,那么这一事件的自信息量为:I(x2)=log P(x2)=log 0.2 bit,如果每次摸出一个球又放回去,再进行第二次摸取,那么如此摸取n次,红球出现的次数为nP(x1)次,白球出现的次数为nP(x2)次,则摸n次后总共提供的信息量为:nP(x1)I(x1)+nP(x2)I(x2)平均每摸取一次所获得的信息量为:H(X)=nP(x1)I(x1)+nP(x2)I(x2)n=P(x1)log P(x1)+P(x2)log P(x2)=P(xi)log P(xi),三种物理含义,信息熵具有三种物理含义:信源熵H(X
12、)表示信源输出前,信源的平均不确定度。信源熵H(X)表示信源输出后,平均每个消息或符号所能提供的信息量。信源熵H(X)可用来表示变量X的随机性。,注意:,在有噪声的情况下,信源熵并不等于平均获得的信息量;只有在无噪声的情况下,接收者才能正确无误地接收到信源发出的全部消息。信源熵是表征信源平均不确定度的,是信源的总体特性,是客观存在的,平均自信息量是消除信源不确定度时信宿所需的信息量,两者数值相同,单位相同,但含义不同。,例题1,设离散信源含有26个英文字母,且每个字母以等概率出现。求信源熵。,例题2,设信源X只有两个符号x1和x2,出现的概率分别为P(x1)=q,P(x2)=(1q),求信源熵
13、。,课本23页,【例2.1】检查8个串联灯泡中哪一只是坏灯泡第一次测量获得的信息量是:IP1(x)-IP2(x)第二次测量获得的信息量是:IP2(x)-IP3(x)第三次测量获得的信息量是:IP3(x)-0,课本29页(续例题2.1),【例2.3】进一步分析例题2.1,将8个灯泡构成一信源X,每个灯泡损坏的概率都相等,计算该信源的信息熵。,课本29页(续例题2.1),分析:此时H(X)正好表示在获知哪个灯泡已损坏的情况前,关于哪个灯泡已损坏的平均不确定性。只有获得3比特的信息量,才能完全消除平均不确定性,才能确定是哪个灯泡坏了。,分析,这种测量方法每次只能获得1比特的信息量,所以说至少要测量3
14、次才能完全消除不确定性,课本29页,【例2.4】设某甲地的天气预报为:晴(4/8)、阴(2/8)、大雨(1/8)和小雨(1/8)。又设某乙地的天气预报为晴(7/8)、小雨占(1/8)。试求两地天气预报各自提供的平均信息量。若甲地天气预报为两极端情况,一种是晴出现概率为1而其余为0。另一种是晴、阴、小雨和大雨出现的概率都相等,为1/4。试求这两种极端情况所提供的平均信息量。又试求乙地出现这两种极端情况所提供的平均信息量。,熵的性质,1、非负性2、对称性3、确定性4、可加性5、极值性6、H(X/Y)H(X);H(Y/X)H(Y)7、H(XY)H(X)+H(Y),续,1、非负性离散信源熵的值不会小于
15、0,即 H(X)0。只有当随机变量是一个确知量(P(xi)=1)时等号才成立。2、对称性当变量P的顺序任意互换后,H(X)的值不变,即H(P1,P2,P3.Pn)=H(P2,P3,P4.Pn,P1)该性质表明:信源熵只与随机变量的总体结构有关,即与信源的总体统计特性有关。如果两个信源的总体统计特性相同(含有的符号数和概率分布相同),那么两个信源就是相同的。,续,3、确定性只要信源符号集中有一个符号出现的概率为1,那么信源熵就等于零。H(1,0)=H(1,0,0)=H(1,0,0.0)=0确知事件,不存在不确定度,则H(X)=0 4、可加性两个统计独立的信源X和Y的联合信源的熵等于这两个信源的独
16、立熵之和。H(XY)=H(X)+H(Y)强可加性两个互相关联的信源X和Y的联合信源的熵等于信源X的熵加上X已知条件下信源Y的条件熵。H(XY)=H(X)+H(Y/X),续,5、极值性当且仅当离散信源的各个符号以等概率出现时,熵最大。H(X)H(1/m,1/m.1/m)=log m6、条件熵小于无条件熵H(X/Y)H(X);H(Y/X)H(Y)上式说明:条件熵不可能大于信源熵,因为信宿收到符号集Y后,对信源X的平均不确定度下降了,它所能提供的信息量也必然下降,只有当X与Y相互独立时(即Y没有提供有关X的任何信息),有 H(X/Y)H(X);H(Y/X)H(Y)7、联合熵与信源熵满足以下不等式H(
17、XY)H(X)+H(Y);仅当X与Y相互独立时等号成立。,离散序列信源的熵,2.5离散无记忆的扩展信源2.6离散平稳信源2.7马尔可夫信源,2.5离散无记忆的扩展信源,实际情况,最简单的离散信源每次输出的只是单个符号的消息。很多实际信源输出的消息是时间或空间上的一系列符号。例如电报系统,发出的是一串有、无脉冲的信号(有脉冲用“1”表示,无脉冲用“0”表示),这个电报系统就是二元信源。输出的消息是一串“0”或“1”的序列。,研究,将信源输出的序列看成是一组一组发出的二元无记忆信源的N次扩展信源(每N个二元数字一组),推广,离散无记忆信源的数学模型与最简单的离散信源的数学模型基本相同,可用【X.P
18、(X)】概率空间描述。但是离散无记忆信源输出的消息是一串符号序列(用随机矢量描述)。,离散无记忆信源X的信源空间,描述,该信源输出的消息是一组长度为N的符号序列,可用N维随机矢量来描述,写成:X=(X1 X2 X3 XN)。其中序列中每个分量Xi(i=1,2,N)都是随机变量,且各个分量之间统计独立(即无记忆、相互独立),取于同一信源。随机矢量的联合概率分布等于随机矢量中各个随机变量的概率乘积。,离散无记忆信源X的N次扩展信源,由上述随机矢量X所组成的新信源称为“离散无记忆信源X的N次扩展信源”,或者“N重符号序列离散无记忆信源”。我们用N重概率空间来描述离散无记忆信源X的N次扩展信源,一般记
19、为XN信源X的N次扩展信源XN是具有qN个符号序列的离散信源,其N重概率空间为:,新信源(扩展信源),其中每个i对应于一个由N个ai组成的序列。根据该信源的无记忆性(彼此统计独立)若i=(ai1,ai2,ai3 aiN)则 P(i)=P(ai1 ai2 ai3 aiN)=P(ai1)P(ai2)P(aiN)=Pi1 Pi2 PiN其中i1,i2 iN=1,2 q,扩展信源的信息熵,根据信息熵的定义,N次扩展信源的熵:H(X)=H(XN)=P(X)logP(X),P(X)logP(X),例题,【例2.6】有一离散无记忆信源:求这个离散无记忆信源的二次扩展信源的序列熵(N=2)。,分析,扩展信源的
20、每个符号是信源 的输出长度为2的符号序列二次扩展信源共有9个不同的符号(信源有3个不同的符号,所以信源中每两个符号组成的不同排列共有32=9种)无记忆信源满足,离散无记忆信源二次扩展的信源概率空间,解答,H(X)=,代入可得:,发现,H(X)=,H(X)=2,=1.5,结论,可以证明:离散无记忆信源X的N次扩展信源的熵等于离散信源X的熵的N倍,(见书P42页)因此,信源的序列熵可表示为:H(X)=H(XN)=N H(X),说明,已知每个信源符号ai含有的平均自信息量为 H(X),N个ai组成的平稳无记忆序列平均含有的自信息量就为NH(X)。(根据熵的可加性)因此信源XN每个输出符号 含有的平均
21、自信息量为NH(X)。,信源的序列熵可表示为:H(X)=H(XN)=N H(X)平均每个符号的熵(平均符号熵)HN(X)=H(X)/N=N H(X)/N=H(X),当前后符号无依赖关系(无记忆)时,有以下推论:H(X1X2)=H(X1)+H(X2);H(X1/X2)=H(X1);H(X2/X1)=H(X2)。如果X1和X2都取自统一概率空间X,且是平稳的,则有:H(X1X2)2H(X)仅当X1X2统计独立时,有H(X1X2)=2H(X),离散有记忆信源的序列熵,一般情况下,离散信源的输出是空间或时间的离散符号序列,而且在序列中符号之间是有依赖关系的,信源在t=i时刻将要发出什么样的符号取决于两
22、个方面:与信源在 t=i 时随机变量xi的取值的概率分布P(xi)有关。一般若 t 不同则概率分布也不同,即P(xi)P(xj)与 t=i 时刻以前信源发出的符号有关,即与条件概率P(xi/xi-1 xi-2)有关。一般若 t 不同则概率分布也不同,即P(xi/xi-1 xi-2)P(xj/xj-1 xj-2)以上所述的是一般随机序列的情况,而它比较复杂,所以我们只讨论平稳随机序列。,2.6离散平稳信源,平稳随机序列就是序列的统计特性与时间无关,即信源所发出符号序列的概率分布与时间起点无关。如果各维联合分布均与时间起点无关,即当t=i,t=j,其中i、j为任意整数,且ij时有:(1)P(Xi)
23、=P(Xj)(2)P(Xi Xi+1)=P(Xj Xj+1)(3)P(Xi Xi+1 Xi+2)=P(Xj Xj+1 Xj+2)(N)P(Xi Xi+1 Xi+N1)=P(Xj Xj+1 Xj+N1)(N+1)P(Xi Xi+1 Xi+N)=P(Xj Xj+1 Xi+N),续,如果上述等式均成立,那么我们说信源是完全平稳的,信源发出的序列也是完全平稳的,这种各维联合分布均与时间起点无关的完全平稳信源称为“离散平稳信源”。如果仅满足(1),则该信源称为“一维平稳信源”,表示无论在什么时刻信源均按P(X)的概率分布发出符号Xi。如果满足(1)、(2),则该信源称为“二维平稳信源”,表示任何时刻信源
24、发出的两个符号的联合概率分布完全相同。如果满足(1)、(2)(N),则该信源称为“N维离散平稳有记忆信源”。所以,N维离散平稳有记忆信源X=X1X2XN的各维联合概率都是平稳的。,续,对于N维离散平稳有记忆信源,我们还得到:P(Xi)=P(Xj)P(Xi+1/Xi)=P(Xj+1/Xj)P(Xi+2/Xi Xi+1)=P(Xj+2/Xj Xj+1)P(Xi+N/Xi Xi+1 Xi+N-1)=P(Xj+N/Xj Xj+1.Xj+N-1)上面一系列等式表明:N维离散平稳有记忆信源X=X1X2XN的各维条件概率也是平稳的。,二维离散平稳信源及其信息熵,二维离散平稳有记忆信源二维离散平稳有记忆信源X
25、=X1X2的信息熵(此处也叫序列熵、联合熵):H(X)=H(X1X2)有以下结论:H(X1X2)=H(X1)+H(X2/X1)=H(X2)+H(X1/X2)信源的序列熵等于信源发出前一符号X1的信息熵加上前一符号X1已知时信源发出下一个符号X2的条件熵。H(X1)H(X1/X2);H(X2)H(X2/X1)条件熵小于无条件熵,离散二维平稳信源,近似等效为新的离散无记忆信源X1X2根据定义可以求出信息熵,联合熵,表示原来信源X输出任意一对可能的消息的共熵,可用1/2H(X1X2)作为二维离散平稳信源X的信息熵的近似值,条件熵,符号之间有依赖性,可以求得已知前面一个符号X1=ai时,信源输出下一个
26、符号的平均不确定性已知前面符号为X1=ai时,信源再输出一个符号的平均不确定性应是对全部可能的符号aj的不确定性求统计平均。,续,前面一个符号有q种选择,对某一个ai存在一个平均不确定性H(X2 X1=ai)对所有的ai的可能值进行统计平均就得当前面一个符号已知时,再输出后面一个符号的总的平均不确定性,例题2.7,某一二维离散平稳信源并设输出的符号只与前一个符号有关,可用联合概率P(ai aj)给出他们的关联程度,如表所示。可以计算得出联合熵、条件熵、平均符号熵。,计算结果1,,说明了符号之间有依赖性,计算结果2,问题:在联合熵和条件熵中到底哪一个值更能接近实际二维离散平稳信源的熵?,扩展,N
27、维离散平稳有记忆信源存在一个N维离散平稳有记忆信源X=X1X2XN,且Xix1x2xq对于上述N维离散平稳有记忆信源X,可以得出如下一些结论:,离散平稳信源性质,1、联合熵/序列熵H(X)=H(X1X2XN)=H(X1)+H(X2/X1)+H(X3/X1X2)+H(XN/X1X2XN-1)。2、N长的信源符号序列中平均每个信源符号所携带的信息量为平均符号熵:若信源退化为无记忆时,有H(X)=H(X1)+H(X2)+H(XN)。若进一步满足平稳性,则有。无记忆信源是有记忆信源的一种特例。,续,3、离散平稳信源具有以下性质:条件熵H(XN/X1X2XN-1)随N的增加而递减,即:H(XN/X1X2
28、XN-1)H(XN-1/X1X2XN-2)H(XN-2/X1X2XN-3)H(X3/X1X2)H(X2/X1)H(X2)H(X1),离散平稳信源的极限熵,N给定时,平均符号熵条件熵:即HN(X)H(XN/X1X2XN-1)平均符号熵HN(X)随N的增加而递减 存在,且:我们称H为离散平稳有记忆信源的极限熵或极限信息量,也称为平稳信源的熵率。H0(X)H1(X)H2(X)H(X)其中:H0(X)为等概率无记忆信源的单个符号的熵;H1(X)为一般(不等概率)无记忆信源的单个符号的熵;依次类推。,结论,离散平稳信源的极限熵等于有限记忆长度m的条件熵。对于有限记忆长度的离散平稳信源可用有限记忆长度的条
29、件熵对离散平稳信源进行信息测度。,2.7 马尔可夫信源,在非平稳离散信源中有一类特殊的信源。这类信源输出的符号序列中符号之间的依赖关系是有限的,它满足马尔可夫链的性质,因此可用马尔可夫链来处理。,马尔可夫信源和m阶马尔可夫信源的定义,若信源输出的符号序列和信源所处的状态满足下列两个条件:(1)某一时刻信源符号的输出只与此刻信源所处的状态有关,而与以前的状态及以前的输出符号都无关,即 P(xl=ak|sl=Ei,xi-1=ak1,sl-1=Ej,)=P(xl=ak|sl=Ei)当具有时齐性时,有P(xl=ak|sl=Ei)=P(ak|Ei)及,(2)信源某l时刻所处的状态由当前的输出符号和前一时
30、刻(l-1)信源的状态唯一决定。即:P(sl=Ej|xl=ak sl-1=Ei)=则此信源称为马尔可夫信源。,定义中2.105式中P(xl=ak|sl=Ei)是在第l时刻,信源处于状态Ei时,输出符号ak的概率。Pij(l)=P(sl=Ej|sl-1=Ei)是假设第(l-1)时刻信源处于Ei状态,在下一时刻状态转移到Ej的状态转移概率。一般情况下,状态转移概率和已知状态输出符号的概率均与时刻l有关,若这些概率与时刻l无关时,即满足P(xl=ak|sl=Ei)=P(ak|Ei)和Pij=P(Ej|=Ei)时,则称为时齐的或齐次的。条件(2)表明,若信源处于某一状态Ei,当它输出一个符号后,所处的
31、状态就变了,一定从状态Ei转移到另一状态。,状态的转移依赖于输出的信源符号,因此任何时刻信源处在什么状态完全由前一时刻的状态和输出的符号决定。又因条件概率P(ak|Ei)已给定,所以状态之间的转移有一定的概率分布,并可求得状态的一步转移概率P(Ej|Ei)。这种信源的状态序列在数学模型上可以作为时齐马尔可夫链来处理,可以用马尔可夫链的状态转移图来描述信源。见例2.8说明概率和状态转移图,例题2.8,P(a1E1)=1/2,P(a2E2)=1/2P(a1E5)=1/4,P(a2E1)=1/4P(a3E2)=1/2,P(a2E5)=1/4P(a3E1)=1/4,P(a2E3)=3/4P(a3E5)
32、=1/2,P(a1E4)=1P(a3E3)=1/4,其他P(akEi)=0可见,满足(i=1,2,3,4,5),续,图中可得:满足条件(2),根据已知可得:,状态的一步转移概率P(E1E1)=1/2,P(E2E2)=1/2P(E3E3)=1/4,P(E2E1)=1/4P(E3E2)=1/2,P(E5E4)=1P(E4E1)=1/4,P(E2E3)=3/4P(E5E5)=1/4,P(EjEi)=0P(E4E5)=P(a2E5)+P(E3E5)=信源满足条件(1)和(2),所以是马尔可夫信源,m阶马尔可夫信源的定义,若随机变量序列X中的任一时刻第m+1个随机变量Xm+1只依赖于它前面已发生的m个随
33、机变量X1Xm,而与更前面的随机变量无关,则称这种信源为m阶马尔可夫信源(简写为m阶M信源),依赖长度(也称记忆长度)为m+1。P(xkN|xk1xk2xk(N1)=P(xkN|xk(Nm)xk(Nm+1)xk(N1)(m阶M信源)=P(xk(m+1)|xk1xk2 xkm)其中:k1,k2,km,kN=1,2,q,m阶马尔可夫信源,对m阶M信源的数学描述为:当m=1时,任何时刻信源符号发出的概率只与前面一个符号有关,则称为一阶马尔可夫信源。m阶M信源任何时刻符号发生的概率只与前面m个符号有关,我们把这m个符号序列看作信源在此时刻所处的状态。由于信源符号集合Xx1,x2,xq共有q个符号,因此
34、信源的状态共有qm个,信源输出依赖长度为m+1的随机序列就可转换成对应的状态随机序列。,例题2.9,有一个二元二阶马尔可夫信源,其信源符号集为0,1,条件概率定为P(000)=P(111)=0.8P(100)=P(011)=0.2P(001)=P(010)=P(101)=P(110)=0.5信源任何时刻输出什么符号只与前两个符号有关,与更前面的符号无关。,续,根据给定的条件概率,可以求得状态之间的转移概率(一步转移概率)P(E1E1)=P(E4E4)=0.8 P(E2E1)=P(E3E4)=0.2P(E3E2)=P(E2E3)=P(E4E2)=P(E1E3)=0.5除此以外,其他的状态转移概率
35、为零。状态转移概率完全依赖于给定的条件概率。,续,二元信源发出的一串二元序列就可变换成状态序列。如二元序列为01011100.,变换成对应的状态序列为E2E3E2E4E4E3E1.。这串状态序列是时齐的马尔可夫链,其在任何时刻l,状态之间的转移可由一步转移概率确定。,m阶M信源所有qm种由m个符号组成的状态的集合为:E:E1,E2,Eqm 条件概率:P(ak(m+1)/ak1,ak2,akm)=P(ak(m+1)/Ei)当某时刻信源发出的符号xk(m+1)后,符号序列 Ai(ak1,ak2,akm)变成了新的信源状态 Ej(ak2,ak3,akm+1),所以:P(ak(m+1)/ak1,ak2
36、,akm)=P(ak(m+1)/Ei)=P(Ej/Ei)且有:0 P(Ej/Ei)1;P(Ej/Ei)1,马尔可夫信源特点,输出的符号是非平稳的随机序列(各维概率分布随时间的推移可能改变)在由信源输出的符号序列和信源所处的状态序列形成的随机序列中,不同时刻的各维概率分布可能会不同,但其在什么状态下输出什么符号的概率分布,以及某一状态到另一状态的转移都是唯一确定的。,马尔可夫信源的信息熵,信源处于某状态Ei时,输出一个信源符号所携带的平均信息量,即在状态Ei下输出一个符号的条件熵为:,一般马尔可夫信源的信息熵,H=H(X)=令:对于一般马尔可夫信源,此极限与初始状态概率分布有关,对于时齐、遍历的
37、马尔可夫链,其极限概率存在,即:,条件,并非所有的m阶M信源都存在状态极限概率。如果所研究的信源的状态序列是时齐的、遍历的马尔可夫链,则该信源的极限概率Q(Ei)存在,那么就可以求得H。,时齐、遍历马尔可夫状态链的极限概率,是时齐、遍历马尔可夫状态链的极限概率,满足:,时齐、遍历的马尔可夫信源的熵,时齐、遍历的m阶马尔可夫信源的熵,对于时齐、遍历的m阶马尔可夫信源,因为其任何时刻输出的符号只与前m个符号有关,所以,信源所处的状态就是由前m个符号组成的。,例题2.10,结果:,例题2.11,一个二元二阶马尔可夫信源,信源符号集A=0,1。信源开始时。以概率P(x1):P(0)=P(1)=0.5输
38、出随机变量X1。然后,下一单位时间输出的随机变量X2与X1有依赖关系,他们的依赖关系由条件概率表示。当马尔可夫信源达到平稳后,符号0和1的概率分布可根据下式计算,小结,信源达到稳定后,信源符号的概率分布与初始时刻符号的概率分布是不同的,所以一般的马尔可夫信源并非是平稳信源。但当时齐、遍历的马尔可夫信源达到稳定后,这时才可以看成一个平稳信源。由于平稳信源必须知道信源的各维概率分布,而m阶马尔可夫信源只需知道前m个符号有关的条件概率,就可以计算出信源的信息熵。所以,一般平稳信源可以用m阶马尔可夫信源来近似。,2.8 信源剩余度,定义,剩余度:也称为多余度或冗余度,表示给定信源在实际发出消息时包含的
39、多余消息。用来衡量信源的相关性程度。剩余度的来源信源符号间的相关性由H0(X)H1(X)H2(X)H(X)可以看出,信源输出符号间的相关性使得信源的熵减小。相关程度越大,信源的实际熵越小,趋于极限熵H(X);相关程度越小,信源实际熵就越大。信源符号分布的不均匀性(非等概率)当等概率分布时信源熵最大,而实际应用中概率分布大多是不均匀的,这就使得实际熵减小。,信源剩余度,信源剩余度的定义对于平稳的m阶M信源,可以用m阶M信源的平均信息熵Hm+1(X)来近似的表示实际信源熵H(X)。当离散信源的符号是等概率分布时熵最大,其平均自信息量为H0(X)=log q。为了衡量信源符号间的依赖程度,我们把离散
40、平稳有记忆信源的极限熵H与该信源等概率分布时所达到的最大熵值H0之比定义为该信源的“相对熵率/熵的相对率”:,续,而把1减去相对熵率所得之差定义为该信源的剩余度/冗余度:信源的剩余度大小反映了离散信源输出的符号序列中符号之间依赖关系的强弱。符号之间依赖关系越强,相关性就越强,信息熵H就越小,信源的剩余度就越大。所以信息熵与剩余度成反比关系。,性质,信源剩余度是进行无失真信源压缩编码的理论依据,它表示信源可以无失真压缩的程度。减少信源剩余度可以提高信息传输效率;而增加剩余度可以提高信息传输抗干扰能力。,例题1,【例2.10】以英文字母为例来进一步理解冗余度。26个英文字母再加1个空格等概率无记忆
41、:H0=4.76(比特/符号)非等概率:H1=4.03(比特/符号)一阶马尔可夫:H2=3.32(比特/符号)二阶马尔可夫:H3=3.1(比特/符号)H=1.4(比特/符号),例题2,汉语信源近似后汉语信源剩余度为,课后习题,2.2同时扔一对均匀的骰子,当得知“两骰子面朝上点数之和为2”或“面朝上点数之和为8”或“两骰子面朝上点数是3和4”时,试问这三种情况分别获得多少信息量?,习题2.3,如果你在不知道今天是星期几的情况下问你的朋友“明天是星期几?”则答案中含有多少信息量?如果你在已知今天是星期四的情况下提出同样的问题,则答案中你能获得多少信息量?(假设已知星期一至星期日的排序)P(A)=1
42、/7,I(A)=2.81比特P(B)=1,I(B)=0,习题2.4,居住在某地区的女孩中有25%是大学生,在女大学生中有75%是身高1.6米以上的,而女孩中身高1.6米以上的占总数一半。假如我们得知“身高1.6米以上的某女孩是大学生”的消息,问获得多少信息量?解:设事件A为女孩是大学生;设事件B为女孩身高1.6米以上根据题意:则知:P(A)=0.25P(B)=0.5 P(BA)=0.75而“身高1.6米以上的某女孩是大学生”这消息表明是在B事件发生的条件下,A事件发生。所以其概率为P(AB)根据贝叶斯定律可得P(AB)=P(AB)/P(B)=P(A)P(BA)/P(B)=0.25*0.75/0
43、.5=0.375则得知“身高1.6米以上的某女孩是大学生”这消息,能获得的信息量I(AB)=-log2P(AB)=log2(1/0.375)1.415比特,习题2.5,设离散无记忆信源其发出的消息为(),求(1)此消息的自信息是多少?(2)在此消息中平均每个符号携带的信息量是多少?解(1)I=14I(a1=0)+13I(a2=1)+12I(a3=2)+6I(a4=3)87.81比特(2)I=87.81/45 1.95比特/符号(3)此信源平均每个符号携带多少信息量?比特/符号,习题2.7,从大量统计资料知道,男性红绿色盲的发病率为7%,女性发病率为0.5%,如果你问一位男同志:“你是否是红绿色
44、盲?”他的回答可能是“是”,可能是“否”,问这两个回答中各含有多少信息量?平均每个回答中含有多少信息量?如果你问一位女同志,则答案中含有的平均自信息量是多少?对于男性对于女性,习题2.13,每帧电视图像可以认为是由3*105个像素组成,所以像素均是独立变化的,且每一像素又取128个不同的亮度电平,并设亮度电平等概率出现。问每帧图像含有多少信息量?若现有一广播员在约10000个汉字的字汇中选1000个字来口述此电视图像(假设汉字字汇是等概率分布,并彼此无依赖),试问广播员描述此图像所广播的信息量是多少?若要恰当地描述此图像,广播员在口述中至少需用多少汉字?H(X)=log128=7比特/像素 H
45、(XN)=NH(X)=2.1*106比特/每帧H(Y)=logq=log21000013.29比特/字H(YN)=NH(Y)=1000log2104=1.329*104比特/千字,习题2.20,设有一信源,它在开始时以P(a)=0.6,P(b)=0.3,P(c)=0.1的概率发出X1。如果X1为a时,则X2为a、b、c的概率为1/3;如果为b时,则X2为a、b、c的概率为1/3;如果X1为c时,则X2为a、b的概率为1/2,为c的概率为0。而且后面发出Xi的概率只与Xi-1有关,又当i3时,。试用马尔可夫信源的图示法画出状态转移图,并计算次信源的熵,解答1,根据状态转移图,设状态极限概率分别为
46、P(a)、P(b)和P(c),根据切普曼-柯尔莫哥洛夫方程有:,解答2,得此一阶马尔可夫的信息熵为:,2.22,一阶马尔可夫信源的状态图如图所示,信源X的符号集为0,1,2。求平稳后信源的概率分布求信源的熵H 求当p=0和p=1时信源的熵,并说明理由,状态转移图,2.23,设有一个马尔可夫信源,它的状态集为s1,s2,s3,符号集为a1,a2,a3,以及在某状态下输出符号的概率为P(aksi)(i,k=1,2,3),如图求出图中马尔可夫信源的状态极限概率并找出符号的极限概率;计算信源处在某一状态下输出符号的条件熵H(Xsj)(j=1,2,3);求出马尔可夫信源熵H,解答1,解答2,符号的极限概
47、率是:,结论,可以看出,本题平稳后符号的极限概率分布不等于状态的极限概率分布,而对于一阶马尔可夫信源,根据定义,状态集就是其符号集,由其条件概率来确定其状态转移概率,所以对于一阶马尔可夫信源来说,平稳后符号的一维极限概率分布就等于其状态的极限概率分布,但是对于一般的马尔可夫信源的情况,平稳后符号的极限概率分布一般不一定等于状态的极限概率分布。,解答3,求信源处于某一状态下输出符号的条件熵,解答4,马尔可夫信源熵,习题2.24,黑白气象传真图的消息只有黑色和白色两种,即信源X=黑,白,设黑色出现的概率为P(黑)=0.3,白色出现的概率P(白)=0.7。假设图上黑白消息出现前后没有关联,求熵H(X
48、);假设消息出现前后有关联,其依赖关系为P(白白)=0.9,P(黑白)=0.1 P(白黑)=0.2,P(黑黑)=0.8,求此一阶马尔可夫信源的熵H2;分别求上述两种信源的剩余度,并比较H(X)和H2的大小,并说明其物理意义。解答(1)H(X)0.881比特/符号(2)根据给出的依赖关系画出状态转移图,列出方程组求出状态极限概率,带入公式求出信息熵,续,一阶马尔可夫信源的熵为:,现计算得到的状态的极限概率的值不完全等于题中原先给出的概率了。所以计算马尔可夫信源的熵时不能用P(黑)和P(白)计算。如题目最初的P(黑)=1/3P(白)=2/3,则此信源为二维平稳信源。,续,(3)黑白消息给出的剩余度
49、由前面计算所得可知:,结果说明:当信源的消息(符号)之间有依赖时,信源输出消息的不确定性减弱。信息熵正是反映信源的平均不确定性的大小。信源剩余度放映信源消息依赖关系的强弱,剩余度越大,信源消息之间的依赖关系就越大。,2.9 连续信源和波形信源,连续信源的定义,用连续随机变量描述输出消息的信源称为连续信源。连续信源就是指其输出在时间上和取值上都是连续的信源。基本连续信源的输出是取值连续的单个随机变量。可用变量的概率密度,变量间的条件概率密度和联合概率密度来描述。,一、连续信源的熵Hc(X),1、连续信源熵的定义基本连续信源的数学模型为:其中R是全体实数集,是连续变量x的取值范围。P(x)是概率密
50、度函数。,根据离散化原则,连续变量X可量化分层后用离散变量描述,来近似地逼近连续变量,即认为连续变量是离散变量的特殊情况。量化单位越小,所得的离散变量和连续变量就越接近,连续信源就能看成离散信源。连续变量的信息测度就可以用离散变量的信息测度来逼近。,见图4.2(课本142页),若把连续的区间a,b分割成n个等宽的小区间,每个区间的宽度为则第i个区间的概率为连续变量X可以用取值为xi(i=1,2n)的离散变量Xn来近似,即:Xn:x1,x2,xn X(连续)。这样连续信源X就被量化成离散信源Xn。,离散信源Xn的数学模型为:且P(xi)=H(Xn)=Pi log Pi=P(xi)logP(xi)