信息论与编码A_第2章信息的度量.ppt

1,信息论与编码InformationandCodingTheory,信息科学与技术学院,西南交通大学,2,第2章信息的度量,2.1信源的数学模型及分类2.2离散信源的熵2.3离散信源序列的熵2.4连续信源的互信息和微分熵2.5信源的冗余度,3,2.1信源的数学模型及分类,消息由符号、文字、数字、语言、音符、图片、图像等能够被人们感知器官所感知的形式组成的序列。信息信息是包含在消息中的内容和意义，是通信系统传输的本质。信号把消息变换成适合信道传输的物理量，这种物理量称为信号。如电信号、光信号、声信号、生物信号等。三者关系通信系统传输的是信号，信号携带着消息，消息中包含着信息。,4,信源信源输出的消息用m表示。全体符号称为（语言的）符号集或字母集.,信源输出的消息m是一个随机变量！,2.1信源的数学模型及分类,5,按照信源发出的时间和消息的分布分类离散信源：信源发出消息的时间与消息的表示形式都是离散的。如：计算机输出的代码、文稿、人写的书信等连续信源：信源发出消息的时间与消息的表示形式都是连续的。如：语音、图像、图形等,按照信源发出符号之间的关系分类无记忆信源不同时刻发出的消息是独立的有记忆信源不同时刻发出的消息是相互依赖的,2.1信源的数学模型及分类,6,符号集（或字母集）Aa1,a2,an.信源任何时刻输出的消息是A上的一个离散随机变量X,2.1信源的数学模型及分类,定义2-1若信源每次输出一个符号，且符号个数是有限的或可数的,一维离散信源,7,2.1信源的数学模型及分类,例2.1在英文通信中，符号集A包含英文字母、数字、标点符号等.英文字母的概率分布为：,8,例2.2在中文通信中，符号集A包含中文字（常取一级汉字）、外文字母、数字、标点符号等.最常用的十个汉字的概率分布为：,2.1信源的数学模型及分类,9,2.1信源的数学模型及分类,符号集AR(实数集).信源任何时刻输出的消息是A上的一个连续随机变量X,定义2-2若信源每次输出一个符号，且符号的取值是连续的,一维连续信源,10,XX1,X2,X3N(为有限正整数或可数的无限值)维离散信源:XX1,X2,XN,Xi(i=1,2,N)为离散随机变量,2.1信源的数学模型及分类,定义2-3若信源每次输出多个符号，且符号个数是有限的或可数的,多维离散信源,离散平稳信源：信源的概率分布与时间无关,11,2.1信源的数学模型及分类,在N维随机矢量X中，若每个分量Xi(i=1,2,N)都是A上的离散随机变量，且具有相同的概率分布X0:p(ai)，则可用N重离散概率空间来描述信源X。即X=X0N。,离散无记忆信源：分量Xi(i=1,2,N)相互独立X的概率分布为：,12,2.1信源的数学模型及分类,m阶马尔可夫信源：信源每次发出的符号只与前m个符号有关，与更前面的符号无关X的概率分布满足：,时齐马尔可夫信源：条件概率与时间起点无关的马尔可夫信源X的概率分布满足：,13,N(为有限正整数或可数的无限值)维连续信源:XX1,X2,XN,Xi(i=1,2,N)为连续随机变量,2.1信源的数学模型及分类,定义2-4若信源每次输出多个符号，且符号的取值是连续的,多维连续信源,14,第2章信息的度量,2.1信源的数学模型及分类2.2离散信源的熵2.3离散信源序列的熵2.4连续信源的互信息和微分熵2.5信源的冗余度,15,随机事件的自信息量,设p=p(E),自信息量I(E)=I(p)满足：是概率p的单调递减函数当p=1时，I(p)=0当p=0时，I(p)=两个独立事件并的信息量应等于它们分别信息量之和,2.2离散信源的熵,随机事件E的自信息量I(E)=事件E发生后提供信息量=不确定性减少的量=事件E发生前的不确定性事件E发生后的不确定性,16,自信息量(self-information),2.2离散信源的熵,自信息量I(E)=I(p)=E发生前所具有的不确定性=E发生后所提供的信息量,设随机事件E发生的概率为p=p(E)，则把I(p)=I(E)=log(p)称为随机事件E的自信息量,17,自信息量(self-information),2.2离散信源的熵,自信息量I(ai)=符号ai具有的不确定性=收到符号ai后获得的信息量,18,2.2离散信源的熵,自信息量的单位对数以2为底(log)，单位为比特(bit,binaryunit)对数以e为底(ln)，单位为奈特(nat,natureunit)对数以10为底(lg)，单位为哈特(Hart,Hartley)单位转换1nat=logebit1.433bit1Hart3.322bit,19,2.2离散信源的熵,例2-3设一个信源发出二进制码元0和1，如发0的概率为p(0)=1/4，发1的概率为p(1)=3/4，则符号0和1的自信息量分别为：I(0)=log2(1/4)=2bit，I(1)=log2(3/4)=0.4bit.如发0的概率p(0)=发1的概率p(1)=1/2，则符号0和1的自信息量为：I(0)=I(1)=log2(1/2)=1bit=1自信息量的单位.,20,2.2离散信源的熵,例2-4英文字母中，p(e)=0.1031，p(c)=0.0218，p(x)=0.0013，则：I(e)=log(0.1031)=3.2779bit，I(c)=log(0.0218)=5.5195bit,I(x)=log(0.0013)=9.5873bit.,概率、不确定度与自信息量的关系：概率小不确定度大自信息量大,21,符号ai与符号aj的联合自信息量：,2.2离散信源的熵,收到符号ai与aj后获得的信息量！,符号ai与符号aj的互信息量：,收到符号aj后,从中获得的关于ai的信息量！,22,条件自信息量,2.2离散信源的熵,在出现aj的条件下，信源发出符号ai的不确定！,23,例2-5设有两个离散信源集合,2.2离散信源的熵,求：(1)自信息量I(ai)(2)条件自信息量I(ai|bj)(3)互信息量I(ai;bj)解：(1),24,2.2离散信源的熵,解：(2),25,2.2离散信源的熵,解：(3),26,2.2离散信源的熵,熵(entropy),信源熵是表示信源输出后，每个符号所提供的平均信息量信源熵是信源全体符号自信息量的平均值规定：0log0=0!,27,2.2离散信源的熵,例2-6.设信源符号集X=x1,x2,x3，每个符号发生的概率分别为:p(x1)=1/2,p(x2)=1/4,p(x3)=1/4，则信源熵为,28,2.2离散信源的熵,例2-8设二元信源X发出符号0和1，发0的概率为p，发1的概率为q，则p+q=1,H(X)=H(p)=plogpqlogq=plogp(1p)log(1p),29,信源发出消息X：,信宿收到消息Y：,2.2离散信源的熵,信道的输入X与输出Y,30,2.2离散信源的熵,联合概率p(ai,bj)=p(X=ai,Y=bj)(i=1,2,n,j=1,2,m)条件概率p(bj|ai)=p(Y=bj|X=ai)(i=1,2,n,j=1,2,m),31,2.2离散信源的熵,条件熵(conditionalentropy),I(ai|bj)H(X|bj)H(X|Y),32,2.2离散信源的熵,联合熵(jointentropy),H(X,Y)表示X和Y同时发生的不确定度,33,2.2离散信源的熵,例2-8二进制通信系统使用符号0和1，由于存在干扰，传输时会产生误码。用X表示信源发出的符号，Y表示接收到的符号。假设,p(X=0)=p(X=1)=0.5,p(Y=0|X=0)=0.75,p(Y=1|X=0)=0.25，p(Y=0|X=1)=0.5,p(Y=1|X=1)=0.5.,(1)已知发出符号0，求收到符号后得到的信息量H(Y|0).解:H(Y|0)=p(Y=0|X=0)logp(Y=0|X=0)p(Y=1|X=0)logp(Y=1|X=0)=0.75log0.750.25log0.25=0.82(bit/符号).,34,2.2离散信源的熵熵的性质,例2-8(2)已知发出的符号，求收到符号后得到的信息量H(Y|X).,解:先求X和Y的联合概率分布.p(X=0,Y=0)=p(X=0)p(Y=0|X=0)=0.50.75=0.375,同理有p(X=0,Y=1)=0.125,p(X=1,Y=0)=0.25,p(X=1,Y=1)=0.25.所以，H(Y|X)=p(X=0,Y=0)logp(Y=0|X=0)p(X=0,Y=1)logp(Y=1|X=0)p(X=1,Y=0)logp(Y=0|X=1)p(X=1,Y=1)logp(Y=1|X=1)=0.375log0.750.125log0.250.25log0.50.25log0.5=0.91(bit/符号).,35,2.2离散信源的熵熵的性质,例2-8(3)已知发出的和收到的符号，求能得到的信息量H(X,Y).,解1:H(X,Y)=p(X=0,Y=0)logp(X=0,Y=0)p(X=0,Y=1)logp(X=0,Y=1)p(X=1,Y=0)logp(X=1,Y=0)p(X=1,Y=1)logp(X=1,Y=1)=0.375log0.3750.125log0.1250.25log0.250.25log0.25=1.91(bit/符号)解2:因为H(X)=1bit/符号，所以H(X,Y)=H(X)+H(Y|X)=1+0.91=1.91(bit/符号).,36,2.2离散信源的熵熵的性质,例2-8(4)已知收到的符号，求被告知发出的符号得到的信息量H(X|Y).,解:因为p(Y=0)=p(X=0,Y=0)+p(X=1,Y=0)=3/8+1/4=5/8,p(Y=1)=p(X=0,Y=1)+p(X=1,Y=1)=1/8+1/4=3/8,所以H(Y)=H(3/8,5/8)=0.96bit/符号，H(X|Y)=H(X,Y)H(Y)=1.910.96=0.95(bit/符号).,37,2.2离散信源的熵熵的性质,非负性：H(X)=H(p1,p2,pn)0确定性：H(p1,p2,pn)=0p1,p2,pn中有一个为1，其它均为0.对称性：当变量p1,p2,pn的顺序任意改变时,熵函数的值不变。,38,2.2离散信源的熵熵的性质,扩展性,可加性：当X和Y相互独立时，有H(X,Y)=H(X)+H(Y).,强可加性：H(X,Y)=H(X)+H(Y|X)=H(Y)+H(X|Y).可加性是强可加性的特例可以推广到N个随机变量。例如N=3时，有H(X,Y,Z)=H(X)+H(Y|X)+H(Z|X,Y).当X,Y和Z相互独立时，有H(X,Y,Z)=H(X)+H(Y)+H(Z).,39,2.2离散信源的熵熵的性质,强可加性：H(X,Y)=H(X)+H(Y|X)=H(Y)+H(X|Y).,40,2.2离散信源的熵熵的性质,递增性,例2-9计算熵,41,2.2离散信源的熵熵的性质,Jesen不等式对任何凸函数f(x)0，有pif(xi)f(pixi)其中pi=1,极值性（最大离散熵定理）：H(p1,p2,pq)H(1/q,1/q,1/q)=logq.,42,2.2离散信源的熵熵的性质,极值性（最大离散熵定理）：H(p1,p2,pq)H(1/q,1/q,1/q)=logq.,43,2.2离散信源的熵熵的性质,条件熵的极值性：H(X|Y)H(X).当X和Y相互独立时，有H(X|Y)=H(X).,44,2.2离散信源的熵熵的性质,上凸性:H(p1,p2,pn)是(p1,p2,pn)的上凸函数.即对任何实数:0kH(P1)+(1k)H(P2).,45,离散信源的互信息,两个随机变量的互信息(mutualinformation),互信息I(X;Y)是表示收到符号后平均每个符号获得的关于X的信息量.,46,离散信源的互信息,例2-10设信源发出8个符号，即X=x1,x2,x8，其二进制编码和概率分布如下表.假设信道传输符号不会出错.求收到符号“01”后获得的有关发送符号x3、x4的信息量.,47,离散信源的互信息,解：首先计算收到符号“01”后关于信源X发送各符号的概率：p(xi|01).,收到符号“01”后获得的有关发送符号x3、x4的信息量：I(x3;01)=log(1/3)/(1/8)=1.415bit/符号.I(x4;01)=log(2/3)/(1/4)=1.415bit/符号.,48,离散信源的互信息,习题：设信源发出8个符号，即X=x1,x2,x8，其二进制编码和概率分布如下表.假设信道传输符号不会出错.求收到符号“10”后获得的有关发送符号x5和x6的信息量.,49,互信息的性质,非负性：I(X;Y)0，并且I(X;Y)=0X和Y相互独立对称性：I(X;Y)=I(Y;X),互信息与熵的关系I(X;Y)=H(X)H(X|Y)=H(Y)H(Y|X)=H(X)+H(Y)H(X,Y),I(X;Y)H(X)I(X;Y)H(Y)X和Y独立I(X;Y)=0.X和Y一一对应I(X;Y)=H(X).,50,互信息的性质,互信息与熵的关系：I(X;Y)=H(X)H(X|Y)=H(Y)H(Y|X),信宿收到的平均信息量=信宿对信源符号不确定度的平均减少量疑义度(equivocation)：H(X|Y)可看成由于信道上存在干扰，接收端收到Y后，对于信源符号X尚存在的不确定度，称为疑义度。也可看成信源符号通过有扰信道传输后所引起的信息量的损失，故又称为损失熵。散布度(irrelevance)：H(Y|X)表示发送端发送X后，对Y存在的不确定度，称为散布度。它反映了信道中噪声源的不确定度，故又称为噪声熵。,51,互信息的性质,如果X和Y是相互独立的，那么,可以看作是信道上的噪声相当大，那么就无法从Y中去提取关于X的信息，传输的信息量为0。也即信源发出的信息在信道上全部损失了，这种信道被称为全损信道。,52,互信息的性质,如果X和Y一一对应，那么,已知Y后就获取了X的全部信息，可以看作无干扰信道。由于无噪声，疑义度H(X|Y)=0。,53,三维联合集的信息量,54,三维联合集的信息量,H(X|Y;Z)表示在Y、Z给定的情况下，X的不确定度，即X的条件熵I(X;Y,Z)表示在Y、Z确定的情况下，所提供的X的信息量I(X;Y|Z)表示在Z给定的情况下，Y出现所提供的X的信息量，也即表示在Z给定的情况下，X和Y的互信息量中不确定度I(X;Y;Z)定义为X、Y和Z三者的互信息量,55,三维联合集的信息量,56,条件互信息,已知三个随机变量(X,Y,Z)的概率分布p(x,y,z).三个随机事件的条件互信息,三个随机变量的条件互信息,57,条件互信息,基本性质I(X;Y|Z)=H(X|Z)H(X|Y;Z)I(X;Y,Z)=I(Y;X,Z)=I(X;Y)+I(X;Z|Y)=I(X;Z)+I(X;Y|Z).I(X;Y|Z)0.,58,条件互信息,例2-11设信源等概地发出4个消息x1,x2,x3,x4,其二进制编码为:x1=00,x2=01,x3=10,x4=11.将消息送入一个二元对称信道(BSC,如图所示).试求:(1)发送符号x1和收到符号“0”产生的信息量I(x1;0).,59,条件互信息,例2-11(2)如果知道收到第二个符号也是“0”，这时带来多少附加信息量I(x1;0|0)？,60,条件互信息,例2-12设随机变量X和Y的联合概率分布如下所示,(1)H(X)，H(Y)；(2)H(X|Y)，H(Y|X)，H(X|Z)；(3)I(X;Y)，H(XYZ)。解：从题意可知,61,条件互信息,解：(1)H(X)，H(Y),解：(2)H(X|Y)，H(Y|X)，H(X|Z),62,条件互信息,求：H(X|Z),随机变量X和Z的联合概率分布：,63,条件互信息,解：(3)I(X;Y)，H(X,Y,Z),64,数据处理中信息的变化,65,数据处理中信息的变化,假设在Y条件下X和Z相互独立，则I(X;Z)=I(X;Y)+I(X;Z|Y)I(X;Y|Z)I(X,Y;Z)=I(X;Z)+I(Y;Z|X)I(X,Y;Z)=I(Y;Z)+I(X;Z|Y)I(X;Z)=I(Y;Z)+I(X;Z|Y)I(Y;Z|X),数据处理定理：H(X|Y)H(X|Z),I(X;Z)I(Y;Z),I(X;Z)I(X;Y)数据处理过程中只会丢失一些信息，绝不会创造出新的信息，这就是所谓的信息不增性。,66,数据处理中信息的变化,通信系统的信息变化I(U;V)I(X;V)I(X;V)I(X;Y)I(U;V)I(X;Y),67,第2章信息的度量,2.1信源的数学模型及分类2.2离散信源的熵2.3离散信源序列的熵2.4连续信源的互信息和微分熵2.5信源的冗余度,68,2.3离散信源序列的熵,离散消息序列离散信源的输出是时间或空间上的离散符号序列，并且序列中的符号之间有依赖关系。此时可用随机矢量来描述信源发出的消息:X=(X1,X2,XN,XN+1,),长度为N的信源符号序列的平均符号熵：,离散平稳信源的熵率（极限熵、极限信息量）,69,2.3离散信源序列的熵,一维离散平稳信源：,二维离散平稳信源：,N维离散平稳信源:,（完全）离散平稳信源,70,2.3离散信源序列的熵,离散平稳信源熵的性质对于离散平稳信源X=(X1,X2,XN,XN+1,)，如果H(X1),则,71,2.3离散信源序列的熵,例2-3-1设有离散二维平稳信源X=(X1,X2,XN,XN+1,)，X1的概率分布如下,假设发出的符号只与前一个符号有关，即可用二维联合概率p(aiaj)给出它们的关联程度，如下表,72,2.3离散信源序列的熵,例2-3-1（续）计算条件概率P(aj|ai)如下：,73,2.3离散信源序列的熵,例2-3-1（续）,74,2.3离散信源序列的熵,离散平稳无记忆信源的熵,已知X=(X1,X2,XN,XN+1,)，设离散信源Xi独立同分布X1：,X1N的熵：H(X1N)=NH(X1),X1N的概率分布：,X1的N次扩展信源：,X的平均符号熵：,X的熵率：,75,2.3离散信源序列的熵,例2.3.2设有一离散无记忆信源X，其概率空间为,求H(X)和H(X2).解：,二次扩展信源X2的概率空间为：,注意:单位中的“符号”是指扩展信源的输出符号(ai,aj),76,2.3离散信源序列的熵,马尔可夫信源的熵参考：傅祖芸.信息论基础与应用,电子工业出版社,2003.,77,第2章信息的度量,2.1信源的数学模型及分类2.2离散信源的熵2.3离散信源序列的熵2.4连续信源的互信息和微分熵2.5信源的冗余度,78,2.4连续信源的熵与互信息量,连续信源X信源输出的消息是在时间上离散，而取值上连续的、随机的，这种信源称为连续信源。例如遥控系统中有关电压、温度、压力等测得的连续数据。,波形信源信源输出消息在时间上是连续的，其取值是连续的、随机的，这种信源称为随机波形信源。例如语音信号X(t)、电视信号X(x0,y0,t)等都是时间的连续函数，这些信源输出的消息可以用随机过程来描述。,79,2.4连续信源的熵与互信息量,80,2.4连续信源的熵与互信息量,连续信源的熵（微分熵、相对熵、差熵）,连续信源X,81,2.4连续信源的熵与互信息量,例2.4.1.设X是区间(a,b)上的均匀分布，求X的熵.,注:微分熵可能是负数.例如,取a=1/2,b=1,则h(X)=1(bit).h(X)不表示信源的输出信息量,它具有相对性.,82,2.4连续信源的熵与互信息量,正态信源X密度函数:X是期望值为m,方差为2的正态随机变量,X的熵,83,2.4连续信源的熵与互信息量,X与Y的联合微分熵(jointdifferentialentropy),两个连续随机变量X与Y