第二章-信息论基本概念

1,第二章信息论的基本概念,第一节信源的描述和分类,第二节离散信源的信息论概念,第三节离散信源的熵,2,第一节信源的描述和分类,一、香农信息论的基本点,用随机变量或随机矢量来表示信源，运用概率论和随机过程的理论来研究信息。,二、信源的分类,按照信源发出的消息在时间上和幅度上的分布情况可将信源分成离散信源和连续信源两大类,信源,离散信源,连续信源,3,连续信源连续信源是指发出在时间和幅度上都是连续分布的连续消息（模拟消息）的信源，如语言、图像、图形等都是连续消息。,离散信源离散信源是指发出在时间和幅度上都是离散分布的离散消息的信源，如文字、数字、数据等符号都是离散消息。,离散信源,离散无记忆信源,离散有记忆信源,发出单个符号的无记忆信源,发出符号序列的无记忆信源,发出符号序列的有记忆信源,发出符号序列的马尔可夫信源,4,离散无记忆信源离散无记忆信源所发出的各个符号是相互独立的，发出的符号序列中的各个符号之间没有统计关联性，各个符号的出现概率是它自身的先验概率。,离散有记忆信源离散有记忆信源所发出的各个符号的概率是有关联的。,发出单个符号的信源发出单个符号的信源是指信源每次只发出一个符号代表一个消息；,发出符号序列的信源发出符号序列的信源是指信源每次发出一组含二个以上符号的符号序列代表一个消息。,5,发出符号序列的有记忆信源发出符号序列的有记忆信源是指用信源发出的一个符号序列的整体概率（即联合概率）反映有记忆信源的特征。,发出符号序列的马尔可夫信源发出符号序列的马尔可夫信源是指某一个符号出现的概率只与前面一个或有限个符号有关，而不依赖更前面的那些符号，这样的信源可以用信源发出符号序列内各个符号之间的条件概率来反映记忆特征。,6,三、先验概率及概率空间的形式,一个离散信源发出的各个符号消息的集合为：,它们的概率分别为：,为符号,的先验概率。,先验概率,一般信源可用一个概率空间来描述，信源的不确定程度可用该概率空间的可能状态数目及其概率来描述。,状态空间,7,信息论所关心的就是这种随机变量的不确定性，驱使我们对随机变量进行观察和测量，从中获取信息。,8,问题：什么叫自信息量？什么叫不确定度？什么叫互信息量？什么叫平均自信息量？什么叫条件熵？什么叫联合熵？联合熵、条件熵和熵的关系是什么？熵的性质有哪些？什么叫平均互信息量？什么叫信源熵？如何计算离散信源熵？,第二节离散信源的信息论概念,9,（一）自信息量,1.信息量？,2.自信息量？,3.不确定度？,4.联合自信息量？,5.条件自信息量？,本节的重点内容：,10,I（信息量）不确定程度的减少量,（一）自信息量,1.信息量,定义：一个随机事件的自信息量定义为其出现概率对数的负值:,2.自信息量,即收信者收到一个消息后，所获得的信息量等于收到信息前后不确定程度减少的量。（举例）,11,c.因为概率越小，的出现就越稀罕，一旦出现，所获得的信息量也就较大。由于是随机出现的，它是X的一个样值，所以是一个随机量。而是的函数，它必须也是一个随机量。,说明：,a.自信息量是非负的。,b.对于离散无记忆信源，符号串中各符号统计独立，符号串自信息量具有可加性：,12,d.自信息量单位的确定在信息论中常用的对数底是2，信息量的单位为比特（bit），用log2或lb表示；（bit/符号）若取自然对数，则信息量的单位为奈特（nat），用loge或ln表示；（nat/符号）若以10为对数底，则信息量的单位为哈脱莱(Hartley)，用log10或lg表示；（hartley/符号）若对数底为r，则信息量的单位为r进制用单位/符号。这三个信息量单位之间的转换关系如下：,1natlog2el.433bit，lHartleylog2103.322bit,13,定义：随机事件的不确定度在数量上等于它的自信息量说明:两者的单位相同，但含义却不相同。具有某种概率分布的随机事件不管发生与否，都存在不确定度，不确定度表征了该事件的特性，而自信息量是在该事件发生后给予观察者的信息量。,3.不确定度,14,一个出现概率接近于1的随机事件，发生的可能性很大，所以它包含的不确定度就很小；反之，一个出现概率很小的随机事件，很难猜测在某个时刻它能否发生，所以它包含的不确定度就很大；若是确定性事件，出现概率为1，则它包含的不确定度为0。,15,几个关于自信息量的例子：,（1）一个以等概率出现的二进制码元（0，1）所包含的自信息量为：I（0）=I（1）=-log2（1/2）=log22=1bit/符号,（2）若是一个m位的二进制数，因为该数的每一位可从0,1两个数字中任取一个，因此有2m个等概率的可能组合。所以I=-log2(1/2m)=mbit/符号，就是需要m比特的信息来指明这样的二进制数。,16,（3）具有四个取值符号的随机变量各符号概率相等，均为1/4，各符号的自信息量：,注：bit的含义是二进制数字（0、1），自信息量为2（bit/符号），意味着其不确定性可用2位二进制数字来度量（00、01、10、11）。若取4为对数底，自信息量为1（四进制单位/符号），意味着其不确定性可用1位四进制数字来度量（0、1、2、3）。,17,（4）英文字母中“e”出现的概率为0.105，“c”出现的概率为0.023，“o”出现的概率为0.001。分别计算它们的自信息量。解：“e”的自信息量I（e）=-lb0.105=3.25（bit/符号）“c”的自信息量I（c）=-lb0.023=5.44（bit/符号）“o”的自信息量I（o）=-lb0.0019.97（bit/符号）,18,（5）某离散无记忆信源（DMS,DiscreteMemorylessSource）的概率空间为信源发出消息202120130213001203210110321010021032011223210。求该消息的自信息量以及消息中平均每符号的自信息量？,19,解：信源符号的自信息量：,单位都是bit/符号,信源无记忆，发出的符号串中各符号统计独立，由自信息量的可加性，符号串自信息量等于各符号自信息量之和：,平均一个符号的自信息量：,20,（6）同时抛掷一对质地均匀的骰子，每个骰子各面朝上的概率均为1/6，试求：(a)事件“3和5同时发生”的自信息量？(b)事件“两个1同时发生”的自信息量？(c)事件“两个点数中至少有一个是1”的自信息量？,解:(a)存在两种情况：甲3乙5，甲5乙3。P(A)=1/362=1/18，I(A)=-lbP(A)=4.17（bit）。(b)存在一种情况：甲1乙1。P(B)=1/36，I(B)=-lbP(B)=5.17（bit）。(c)P(C)=15/65/6=11/36，I(C)=-lbP(C)=1.17（bit）。,21,（7）在布袋中放入81枚硬币，它们的外形完全相同。已知有一枚硬币与其它80枚硬币重量不同，但不知这个硬币比其它硬币的重量是重还是轻。问确定随意取出的一枚硬币恰好是重量不同硬币的所获得的信息量是多少？并进一步确定它比其它硬币是重还是轻所需要的信息量是多少？,解:(a)P(A)=1/81，I(A)=-lbP(A)=6.34（bit）。(b)P(B)=1/2，PP(A)P(B)1/162;I=-lbP=7.34（bit）。,22,4.联合自信息量,bit/二元符号,随机变量Z是两个随机变量X、Y的联合，即Z=XY，其概率空间：,二元联合符号的自信息量称为联合自信息量：,同理，三元联合符号的联合自信息量：,bit/三元符号,23,注意:当(xi，yj)相互独立时，有P(xi，yj)=P(xi)P(yj)，那么就有I(xi，yj)=I(xi)+I(yj)。(xi，yj)所包含的不确定度在数值上也等于它们的自信息量。,24,定义：,注意:在给定yj条件下，随机事件xi所包含的不确定度在数值上与条件自信息量相同，但两者含义不同。,5.条件自信息量,bit/符号,定义两种条件自信息量：,bit/符号,25,条件自信息量物理意义：,26,几个关于条件自信息量的例子：,27,（1）由于棋子落入任一方格都是等可能的，则,棋子落入某方格的不确定性就是自信息量,bit/符号,28,解：设A表示“大学生”这一事件，B表示“身高1.6m以上”这一事件，则：P(A)0.25；P(B)0.5；P(B|A)=0.75;因此：P(A|B)P(AB)/P(B)=P(A)P(B|A)/P(B)=0.750.25/0.5=0.375;I(A|B)-lbP(A|B)=1.42(bit)。,2.居住在某地区的女孩中有25是大学生，在女大学生中有75是身高1.6m以上的，而女孩中身高1.6m以上的占女生总数的一半。假如我们得知“身高1.6m以上的某女孩是大学生”的消息，问获得多少信息量？,29,（二）互信息量,30,互信息量,设观察输入为:,设观察结果为:,从yj中得到有关输入符号xi的信息称为xi与yj之间的互信息量（事件信息）（注意与联合自信息量符号标志不同）。,信息先验不确定性后验不确定性,xi在观察到yj前不确定性xi在观察到yj后不确定性,31,(1)yj对xi的互信息I(xi;yj)I(xi;yj)=I(xi)-I(xi/yj)含义互信息I(xi;yj)=自信息I(xi)-条件自信息I(xi/yj)I(xi)-信宿收到yj之前，对信源发xi的不确定度I(xi/yj)-信宿收到yj之后，对信源发xi的不确定度I(xi;yj)-收到yj而得到(关于xi)的互信息=不确定度的减少量,p(xi)先验概率：信源发xi的概率p(xi/yj)后验概率：信宿收到yj后，推测信源发xi的概率,即互信息量为后验概率与先验概率比值的对数:,32,(2)xi对yj的互信息I(yj;xi)含义信源发xi前、后，信宿收到yj的不确定度的减少(3)I(xi;yj)=I(xi)+I(yj)-I(xi，yj)注意I(xi;yj)与I(xi，yj)不同！,33,(4)实在信息：后验概率p(xi|yj)1，即收到yj时就能完全肯定此时的输入一定是xi，xi的后验不确定性完全消除。,即从输出结果中得到了输入实有的全部信息实在信息：,注意a.输入的先验不确定性在数值上等于自身含有的实在信息。b.信息与不确定性是两个不同的物理概念，不是信息，只是不确定性，互信息量才是信息，把当作信息只是说明一种数量上的相等关系。胡扯,34,(4)互信息量定义扩展：符号xi与符号对yjzk之间的互信息量定义为,35,2.互信息的性质（具体推导可见课本p24）(1)对称性I(xi;yj)=I(yj;xi)(2)X与Y独立时I(xi;yj)=0(3)I(xi;yj)可为正、负、0当事件xi和yj统计独立时，互信息量为零;互信息量为正，说明yj的出现有助于减小xi的不确定性；反之，互信息量为负说明yj的出现增大了xi的不确定性（比如信道存在干扰）。(4)任何两个事件之间的互信息量不可能大于其中任意事件的自信息量,36,I(xi;yj)可为正、负、0的举例设yj代表“闪电”，则当xi代表“打雷”时，I(xi/yj)=0，I(xi;yj)=I(xi)0当xi代表“下雨”时，I(xi/yj)I(xi)，I(xi;yj)0当xi代表“雾天”时，I(xi/yj)=I(xi)，I(xi;yj)=0当xi代表“飞机正点起飞”时，I(xi/yj)I(xi)，I(xi;yj)0,37,3.条件互信息量给定zk条件下，xi与yj间的互信息量是,另外，还存在xi与yjzk之间的互信息量：,38,（该式推导见p25-26）,由上述两式得,说明：一个联合事件yjzk出现后提供的有关xi的信息量=zk事件出现后提供的有关xi的信息量在给定zk条件下再出现yj事件后所提供的有关xi的信息量,39,4.关于互信息的例子已知信源发出两种消息，且此消息在二进制对称信道上传输，信道传输特性为：求互信息量,解：根据得到：,40,一个布袋内放100个球，其中80个球是红色的，20个球是白色的，若随机摸取一个球，猜测其颜色，求平均摸取一次所能获得的自信息量。解:依据题意，这一随机事件的概率空间为,（三)平均自信息量-熵,41,其中：x1表示摸出的球为红球事件，x2表示摸出的球是白球事件。如果摸出的是红球，则获得的信息量是I（x1）=-log2p（x1）=-lb0.8=0.322bit如果摸出的是白球，则获得的信息量是I（x2）=-log2p（x2）=-lb0.2=2.322bit,如果每次摸出一个球后又放回袋中，再进行下一次摸取。如此摸取n次，则红球出现的次数为np（x1）次，白球出现的次数为np（x2）次。随机摸取n次后总共所获得的信息量为np（x1）I（x1）+np（x2）I（x2）,42,则平均随机摸取一次所获得的信息量为H（X）=1/nnp（x1）I（x1）+np（x2）I（x2）=-p（x1）log2p（x1）+p（x2）log2p（x2）,=0.722比特/次,说明：,自信息量I（x1）和I（x2）只是表征信源中各个符号的不确定度，一个信源总是包含着多个符号消息，各个符号消息又按概率空间的先验概率分布，因而各个符号的自信息量是一个随机变量，所以自信息量不能作为整个信源的信息测度。,43,因为X中各符号xi的自信息量I（xi）为非负值，p（xi）也是非负值，且0p(xi)1，故信源的平均自信息量H（X）也是非负量。,定义：离散信源熵H(X)(平均不确定度/平均信息量/平均自信息量/信息熵/熵)定义信源的平均不确定度H(X)为信源中各个符号不确定度的数学期望，即,单位为比特/符号或比特/符号序列,平均自信息量H（X）的定义公式与热力学中熵的表示形式相同，所以又把H（X）称为信源X的熵。熵是在平均意义上来表征信源的总体特性的，可以表征信源的平均不确定度。,44,某一信源，不管它是否输出符号，只要这些符号具有某些概率特性，必有信源的熵值；这熵值是在总体平均上才有意义，因而是一个确定值，一般写成H（X），X是指随机变量的整体（包括概率分布）。信息量则只有当信源输出符号而被接收者收到后，才有意义，这就是给予接收者的信息度量，这值本身也可以是随机量，也可以与接收者的情况有关。,6）当某一符号的概率为零时，在熵公式中无意义，为此规定这时的也为零。当信源X中只含一个符号时，必定有，此时信源熵H（X）为零。,7）平均自信息量H（X）表示集X中事件出现的平均不确定性，即在观测之前，确定集X中出现一个事件平均所需的信息量；或者说在观测之后，集X中出现一个事件平均给出的信息量。,45,例：电视屏上约有500600=3105个格点，按每点有10个不同的灰度等级考虑，则共能组成个不同的画面。按等概率计算，平均每个画面可提供的信息量为,=31053.32比特/画面,46,例：有一篇千字文章，假定每字可从万字表中任选，则共有不同的千字文N=100001000=104000篇仍按等概率1/100001000计算，平均每篇千字文可提供的信息量为H（X）log2N410333213104比特千字文,比较：,“一个电视画面”平均提供的信息量远远超过“一篇千字文”提供的信息量。,47,例：设信源符号集X=x1,x2,x3，每个符号发生的概率分别为p（x1）=1/2，p（x2）l4，p（x3）14。则信源熵为H（X）=1/2log22+1/4log24+1/4log24=1.5比特/符号,48,例：该信源X输出符号只有两个，设为0和1。输出符号发生的概率分别为p和q，pq=l。即信源的概率空间为,则二元信源熵为H（X）=-plbp-qlbq=-plbp-(1-p)lb(1-p)=H(p),49,50,说明：,信源信息熵H（X）是概率p的函数，通常用H（p）表示。p取值于0，1区间。H（p）函数曲线如图所示。从图中看出，如果二元信源的输出符号是确定的，即p=1或q=1，则该信源不提供任何信息。反之，当二元信源符号0和1以等概率发生时，信源熵达到极大值，等于1比特信息量。,51,几个概念,定义：在给定yj条件下，xi的条件自信息量为I(xi/yj)，X集合的条件熵H（X/yj）为H（X/yj）=在给定Y（即各个yj）条件下，X集合的条件熵H(X/Y)定义为H（X/Y）=,条件熵,52,相应地，在给定X（即各个xi）的条件下，Y集合的条件熵H(Y/X)定义为H(Y/X)=,【注意】：条件熵是在联合符号集合XY上的条件自信息量的联合概率加权统计平均值。,53,联合熵（共熵）,定义：联合熵是联合符号集合XY上的每个元素对xiyj的联合自信息量的联合概率加权统计平均值。定义为H（XY）=【说明】表示X和Y同时发生的平均不确定度。,54,联合熵H（XY）与熵H（X）及条件熵H（X/Y）之间存在下列关系：,1）H（XY）H（X）H（YX）H（XY）H（Y）H（XY）2）H（XY）H（X）H（YX）H（Y）即H（XY）H（X）H（Y）（当X与Y相互独立时，等号成立！共熵得到最大值！）,【注】上式表明，从平均意义上讲，条件熵在一般情形下总是小于无条件熵。从直观上说，由于事物总是联系的，因此对随机变量X的了解平均讲总能使Y的不确定性减少。同样，对Y的了解也会减少X的不确定性。,55,证明:,同理:,56,所以,57,同理：,2）的证明见课本p29（略）,三维联合符号集合XYZ上的共熵H(XYZ):,存在下列关系：,1）H（X