第1章熵和互信息量.ppt

第1章 熵和互信息量,本章介绍 信源的统计特性和数学模型 各类信源的信息测度-熵及其性质 引入信息理论的一些基本概念和重要结论,通信系统模型：,对信息论的学习可从信源开始 消息是信息的载荷者。信息是抽象的，消息是具体的。要研究信息，还得从研究消息入手。 由于信源发送什么消息预先是不可知的，只能用概率空间来描述信源,1.1 信源的数学模型及分类,单符号信源：输出是单个符号（代码）的消息 离散信源 连续信源 平稳随机序列信源：信源输出的消息由一系列符号序列所组成，可用N维随机矢量 X(X1,X2,XN)描述，且随机矢量X 的各维概率分布都与时间起点无关-平稳！ 离散平稳信源 连续平稳信源 无记忆（独立）离散平稳信源 有记忆信源 m阶马尔可夫信源 随机波形信源,离散信源(单符号),特点：输出是单个符号（代码）的消息，符号集的取值A:a1,a2,aq是有限的或可数的，可用一维离散型随机变量X来描述。 例：投硬币、书信、电报符号等等。 数学模型：设每个信源符号ai出现的(先验)概率 p(ai) (i=1,2,q) 满足：,概率空间能表征离散信源的统计特性，因此也称概率空间为信源空间。,连续信源,特点：输出是单个符号（代码）的消息，输出消息的符号集A的取值是连续的，可用一维的连续型随机变量X 来描述。 例：语音信号、热噪声信号、遥控系统中有关电压、温度、压力等测得的连续数据等等。 数学模型：连续型的概率空间。即：,或,满足,或,1.2 离散信源的信息熵及其性质,基本的离散信源可用一维随机变量X来描述信源的输出，信源的数学模型可抽象为:,问题：这样的信源能输出多少信息? 每个消息的出现携带多少信息量?,信息的度量,考虑： 信息的度量（信息量）和不确定性消除的程度有关，消除的不确定性获得的信息量； 不确定性就是随机性，可以用概率论和随机过程来测度，概率小不确定性大； 推论： 概率小 信息量大，即信息量是概率的单调递减函数； 信息量应该具有可加性；,信息量的推导,某事件发生所含有的信息量应该是该事件发生的先验概率的函数。即： I (ai) f p(ai) 根据客观事实和人们的习惯概念，函数 f p(ai) 应满足以下条件： （1）它应是先验概率p(ai)的单调递减函数，即当 p (a1) p (a2) 时，有 f p (a1) f p (a2) ； （2）当p (ai) =1时， f p (ai) = 0 （3）当p (ai) =0时， f p (ai) = （4）两个独立事件的联合信息量应等于它们分别的信息量之和。即统计独立信源的信息量等于它们分别的信息量之和。 可以证明对数函数满足上述条件：,一. 自信息,设离散信源X的概率空间为：,I(ai)代表两种含义： （1）当事件ai发生以前，表示事件ai发生的不确定性 （2）当事件ai发生以后，表示事件ai所提供的信息量,称事件ai发生所含有的信息量为 ai 的自信息量。定义为：,一点说明,计算自信息量时要注意有关事件发生概率的计算； 自信息量的单位取决于对数的底； 底为2，单位为“比特（bit, binary unit）”； 底为e，单位为“奈特（nat, nature unit）”； 底为10，单位为“哈特（hat, Hartley）”； 根据换底公式得：,一般计算都采用以“2”为底的对数，为了书写简洁，常把底数“2”略去不写,1 nat = 1.44bit , 1 hat = 3.32 bit；,例 8个串联的灯泡x1，x2，x8，其损坏的可能性是等概率的，现假设其中有一个灯泡已损坏，问每进行一次测量可获得多少信息量？总共需要多少次测量才能获知和确定哪个灯泡已损坏。,解：收到某消息获得的信息量(即收到某消息后获得关于某事件发生的信息量) 不确定性减少的量 (收到此消息前关于某事件发生的不确定性) - (收到此消息后关于某事件发生的不确定性),已知8个灯泡等概率损坏，所以先验概率P (x1)1/8 ，即,第二次测量获得的信息量 = I P (x2) - I P (x3)=1(bit) 第三次测量获得的信息量 = I P (x3) =1(bit) 至少要获得3个比特的信息量就可确切知道哪个灯泡已坏了。,第一次测量获得的信息量 = I P (x1) - I P (x2)=1(bit) 经过二次测量后，剩2个灯泡，等概率损坏，P (x3)1/2,一次测量后，剩4个灯泡，等概率损坏，P (x2)1/4,二. 信息熵,对一个信源发出不同的消息所含有的信息量也不同。所以自信息I(ai)是一个随机变量，不能用它来作为整个信源的信息测度。 定义自信息的数学期望为平均自信息量Hr(X)，称为信息熵：,由于这个表达式和统计物理学中热熵的表达式相似，且在概念上也有相似之处，因此借用“熵”这个词，把H(X)称为信息“熵”； 信息熵的单位由自信息量的单位决定，即取决于对数的底。,H(X)的单位：r 进制单位符号 （r1）,熵的计算例： 有一布袋内放l00个球，其中80个球是红色的，20个球是白色的。随便摸出一个球，猜测是什么颜色，那么其概率空间为：,如果被告知摸出的是红球，那么获得的信息量是： I (a1) log p(a1) log0.8= 0.32 （比特） 如被告知摸出来的是白球，所获得的信息量应为： I (a2) log p(a2) log0.2 = 2.32 （比特） 平均摸取一次所能获得的信息量为 ： H(X)= p(a1) I (a1) + p(a2) I (a2) =0.72（比特/符号）,熵的含义,熵是从整个集合的统计特性来考虑的，它从平均意义上来表征信源的总体特征。 在信源输出后，信息熵H(X)表示每个消息提供的平均信息量； 在信源输出前，信息熵H(X) 表示信源的平均不确定性； 信息熵H(X) 表征了变量X的随机性。 例如，有两信源X、Y，其概率空间分别,计算其熵，得：H(X)=0.08（ bit /符号） H(Y)=1（bit / 符号） H(Y)H(X)，因此信源Y比信源X的平均不确定性要大。,例 设甲地的天气预报为：晴(占48)、阴(占28)、大雨(占18)、小雨(占18)。又设乙地的天气预报为：晴 (占78)，小雨(占18)。试求两地天气预报各自提供的平均信息量。若甲地天气预报为两极端情况，一种是晴出现概率为1而其余为0。另一种是晴、阴、小雨、大雨出现的概率都相等为14。试求这两极端情况所提供的平均信息量。又试求乙地出现这两极端情况所提供的平均信息量。,两个信源,解：甲地天气预报构成的信源空间为:,则其提供的平均信息量即信源的信息熵:,乙地天气预报的信源空间为:,结论：甲地天气预报提供的平均信息量大于乙地，因为乙地比甲地的平均不确定性小。,甲地极端情况,极端情况1：晴天概率1,结论：等概率分布时信源的不确定性最大，所以信息熵（平均信息量）最大。,极端情况2：各种天气等概率分布,乙地极端情况,极端情况1：晴天概率1,结论：在极端情况2下，甲地比乙地提供更多的信息量。 因为，甲地可能出现的消息数比乙地可能出现的消息数多。,极端情况2：各种天气等概率分布,信息熵是信源概率空间的一种特殊矩函数。这个矩函数的大小，与信源的符号数及其概率分布有关。 我们用概率矢量P来表示概率分布P(x)：,三、信息熵的基本性质,这样，信息熵H(X)是概率矢量P或它的分量p1，p2，pq的q-1元函数(因各分量满足上述条件限制，所以独立变量只有q-1元)。 一般 H(X)可写成：,熵函数,H(P)是概率矢量P的函数，称为熵函数。 用下述表示方法： 用H(x) 表示以离散随机变量x描述的信源的信息熵； 用H(P) 或 H(p1, p2 , , pq )表示概率矢量为 P = (p1, p2 , , pq )的q个符号信源的信息熵。 若当 q =2 时，因为 p1+p2 = 1, 所以将两个符号的熵函数写成H(p1)或H(p2)。 熵函数H(P)是一种特殊函数，具有以下性质。,性质：,1、对称性： H(P) 的取值与分量 p1, p2 , ··· , pq的顺序无关。 说明： 从数学角度： H(P)= pi · log pi 中的和式满足交换率； 从随机变量的角度：熵只与随机变量的总体统计特性有关。 例,2、确定性：H(1,0)=H(1,0,0)=H(1,0,0,0)=0 性质说明：从总体来看，信源虽然有不同的输出符号，但它只有一个符号几乎必然出现，而其它符号则是几乎不可能出现，那么，这个信源是一个确知信源，其熵等于零。 3、非负性： H(P) 0 说明： 随机变量X的概率分布满足0pi1，当取对数的底大于1时，log(pi) 0，-pilog(pi ) 0，即得到的熵为正值。只有当随机变量是一确知量时熵才等于零。 这种非负性合适于离散信源的熵，对连续信源来说这一性质并不存在。以后可看到在相对熵的概念下，可能出现负值。,非负性体现信息是非负的。,4、扩展性,性质说明：信源的取值数增多时，若这些取值对应的概率很小(接近于零)，则信源的熵不变。,所以，上式成立,因为,5、可加性 统计独立信源X和Y的联合信源的熵等于信源X和Y各自的熵之和。 H(XY) = H(X)+ H(Y),可加性是熵函数的一个重要特性，正因具有可加性，才使熵函数的形式是唯一的。,证明：,例如，甲信源为,它们的联合信源是,可计算得联合信源的联合熵： 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个元素的概率之和等于原元素的概率，而其他符号的概率不变，则新信源的熵增加。 熵的增加量等于由分割而产生的不确定性量。,证明可以从熵的定义或强可加性得出：,即得：,递增性的推广,它表示n个元素的信源熵可以递推成(n-1)个二元信源的熵函数的加权和。这样，可使多元信源的熵函数的计算简化成计算若干个二元信源的熵函数。因此，熵函数的递增性又可称为递推性。,8、极值性(定理1.1) 在离散信源情况下，信源各符号等概率分布时，熵值达到最大。,性质表明等概率分布信源的平均不确定性为最大。 这是一个很重要的结论，称为最大离散熵定理。,证明： 因为对数是型凸函数，满足詹森不等式Elog Y log EY，则有：,二进制信源是离散信源的一个特例。 该信源符号只有二个，设为“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、上凸性,当离散平稳无记忆信源发出固定长度的消息序列时，则得到原信源的扩展信源 。 例如在电报系统中，若信源输出的是二个二元数字组成的符号序列，此时可认为是一个新的信源，它由四个符号（00，01，10，11）组成，我们把该信源称为二元无记忆信源的二次扩展信源。 如果把N个二元数字组成一组，则信源等效成一个具有2N个符号的新信源，把它称为二元无记信源的N次扩展信源。,1.3 离散无记忆信源的扩展信源,一般情况下，对一个离散无记忆信源X，其样本空间为a1,a2, ,aq ，对它的输出消息序列，可用一组组长度为N的序列来表示它。这时，它等效成一个新信源。 新信源输出的符号是N维离散随机矢量X =(X1，X2,XN)，其中每个分量Xi (i1,2,N)都是随机变量，它们都取值于同一信源符号集，并且分量之间统计独立，则由随机矢量X 组成的新信源称为离散无记忆信源X的N次扩展信源。,单符号离散信源X的数学模型：,N次扩展信源与单符号离散信源比较：数学模型相同但输出不是单个符号，而是一串N个相互独立的符号序列： X(X1,X2, XN) ，联合分布密度P(X)=P(X1X2XN) 把 X 等效为一个新信源，称为X的N次扩展信源，其数学模型：,因为是无记忆的(彼此统计独立)则：,离散平稳无记忆N次扩展信源的熵 H(X ) = H(XN) = N·H(X),其中：,同理计算式中其余各项，得到：,H(XN) = H(X)+H(X)+H(X)= N H(X),证：,例 求如下离散无记忆信源的二次扩展信源及其熵。,解：二次扩展信源的概率空间为,一、离散平稳信源的数学定义 在一般情况下，信源在 t = i 时刻将要发出什么样的符号决定于两方面： (1) 信源在 t = i 时刻随机变量Xi 取值的概率分布P(xi)。 一般 P(xi) P(xj) (2) t= i 时刻以前信源发出的符号。 即与条件概率P(xi/xi-1 xi-2)有关 对平稳随机序列，序列的统计性质与时间的推移无关，即信源发出符号序列的概率分布与时间起点无关。,1.4 联合熵,平稳随机序列的数学定义如下： 若当t = i，t = j时(i,j 是大于1的任意整数)，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 ),由于联合概率与条件概率有以下关系：,结论：对于平稳信源来说，其条件概率均与时间起点无关，只与关联长度N有关。即平稳信源发出的平稳随机序列前后的依赖关系与时间起点无关。,从平稳性可得：,对平稳信源如果某时刻发出什么符号只与前面发出的N个符号有关，那么任何时刻它们的依赖关系都是一样的。即：,二、二维平稳信源及其信息熵 最简单的平稳信源就是二维平稳信源。它满足一维和二维概率分布与时间起点无关。,同时已知：连续两个信源符号出现的联合概率分布为P(ai aj) (i, j = 1,q) ，且：,设有一个离散一维平稳信源，其概率空间为：,对离散二维平稳信源的信息测度： 由于只有两个符号有关联，且其关联与时间无关，则我们可把这个信源输出的随机序列分成每二个符号一组(因为相邻的两个符号才有关联)，每组构成新信源的一个符号，并假设组与组之间统计无关(实际上，组尾的符号与下一组组头的符号是有关的)。 这时，等效成一个新的信源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/X1ai)，那么对所有ai的可能值进行统计平均就得当前面一个符号巳知时，再输出下一个符号的总的平均不确定性H(X2/X1) ：,（3）根据概率关系，可以得到联合熵与条件熵的关系：,即：H(X1X2)H(X1)+H(X2/X1) 而 H(X2/X1) H(X2) 因此 H(X1X2)H(X1)+H(X2/X1) H(X1)+H(X2) = 2H(X) 所以，一般情况下，输出二个符号的联合熵总是小于二倍信源的熵。,例 某一离散二维平稳信源,其发出的符号只与前一个符号有关，即可用联合概率P(aiaj)给出它们的关联程度，如下表所示,求信源的熵H(X)、条件熵H(X2/X1)和联合熵H(X1X2) 。,解：根据概率关系可计算得条件概率P（aj/ai）,计算结果列表如下：,得：,一、条件熵(信道疑义度),信道输入信源X的熵,H(X)是在接收到输出Y以前，关于输入变量X的先验不确定性，称为先验熵。,1.5 条件熵和互信息量,接受到bj后，关于X的不确定性为,后验熵在输出符号集Y范围内是个随机量，对后验熵在符号集Y中求数学期望，得条件熵-信道疑义度：,这是接收到输出符号bj后关于X的后验熵。 后验熵是当信道接收端接收到输出符号bj后，关于输入符号的信息测度。,互信息量 I(xi ; yj)：收到消息yj 后获得关于xi的信息量。,即：互信息量表示先验的不确定性减去尚存的不确定性，这就是收信者获得的信息量,二、平均互信息,平均互信息I(X; Y)： I(xi ; yj)的统计平均,它代表接收到符号集Y后平均每个符号获得的关于X的信息量，也表示了输入与输出两个随机变量之间的统计约束程度。,关于平均互信息I(X;Y) 互信息 I(x ; y) 代表收到某消息y后获得关于某事件x的信息量。它可取正值，也可取负值。 若互信息I(x ; y)= 0。 若I(X;Y) = 0，表示在信道输出端接收到输出符号Y后不获得任何关于输入符号X的信息量-全损信道。,I(X;Y) = H(X) - H(X|Y) I(X;Y) = H(Y) - H(Y|X) I(X;Y) = H(X)+H(Y)-H(XY) 其中：,平均互信息与各类熵的关系,平均互信息与各类熵之间关系的集合图（维拉图）表示： H(X|Y) = H(X) - I(X;Y) H(Y|X) = H(Y) - I(X;Y) H(XY) = H(X)+H(Y)- I(X;Y),H(X),H(Y),H(X/Y),H(Y/X),I(X;Y),图中，左边的圆代表随机变量X的熵，右边的圆代表随机变量Y的熵，两个圆重叠部分是平均互信息I(X;Y)。每个圆减去I(X;Y)后剩余的部分代表两个疑义度。,两种特殊信道,（1）离散无干扰信道 ( 无损信道 ),信道的输入和输出一一对应，信息无损失地传输，称为无损信道。 H(X|Y) = H(Y|X) = 0 损失熵和噪声熵都为“0” 由于噪声熵等于零，因此，输出端接收的信息就等于平均互信息: I(X;Y) = H(X) = H(Y),（2）输入输出独立信道 ( 全损信道 ) 信道输入端X与输出端Y完全统计独立,H(X|Y) = H(X) , H(Y|X) = H(Y) 所以 I(X;Y) = 0 I(X;Y) = H(X) - H(X|Y) 信道的输入和输出没有依赖关系，信息无法传输，称为全损信道。 接收到Y后不可能消除有关输入端X的任何不确定性，所以获得的信息量等于零。同样，也不能从X中获得任何关于Y的信息量。 平均互信息I(X;Y)等于零，表明了信道两端随机变量的统计约束程度等于零。,二种极限信道各类熵与平均互信息之间的关系,H(X|Y) = H(X) H(Y|X) = H(Y) I(X;Y) = 0,H(X|Y)=H(Y|X)=0 I(X;Y)=H(X)=H(Y),无损信道：完全重迭,全损信道：完全独立,无损信道：,全损信道：,平均互信息的性质,平均互信息 I(X;Y) 具有以下特性： （1）非负性 即 I(X;Y) = 0 当X、Y统计独立时等式成立。 （2）极值性 即 I(X;Y) = H(X) 当 H(X/Y)=0 时，即信道中传输信息无损时，等式成立。,（3）交互性（对称性） 即 I(X;Y) = I(Y;X) 当 X、Y统计独立时 I(X;Y) = I(Y;X)=0 当信道无干扰时 I(X;Y) = I(Y;X)=H(X)=H(Y),（4）凸状性,所以，平均互信息I(X;Y)只是信源X的概率分布P(x)和信道的传递概率P(y/x)的函数，即： I(X;Y) = f P(x), P(y|x),平均互信息I(X;Y)是输入信源的概率分布P(x)的型凸函数。,（1）对固定信道，选择不同的信源(其概率分布不同)与信道连接，在信道输出端接收到每个符号后获得的信息量是不同的。 （2）对于每一个固定信道，一定存在有一种信源(某一种概率分布P(x)，使输出端获得的平均信息量为最大。,平均互信息I(X;Y)是信道传递的概率P(y/x)的型凸函数。,当信源固定后，选择不同的信道来传输同一信源符号，在信道输出端获得关于信源的信息量是不同的。 对每一种信源都存在一种最差的信道，此时干扰 (噪声) 最大，而输出端获得的信息量最小。,1.6 离散无记忆信道的扩展信道,离散无记忆信道 ( DMC，Discrete Memoryless Channel) ，其传递概率满足：,仍可用 X，P( y / x )，Y 概率空间来描述。 设离散无记忆信道的 输入符号集Aa1， ， ar， 输出符号集Bb1 ， ， bs，信道矩阵为:,则此无记忆信道的N次扩展信道的数学模型如图所示:,而信道矩阵：,其中：,例3 求二元无记忆对称信道（BSC）的二次扩展信道。 解：BSC的输入和输出变量X和Y的取值都是0或1，因此，二次扩展信道的输入符号集为A00，01，10，11，共有224个符号，输出符号集为B 00，01，10，11。 由于是无记忆信道，可求得二次扩展信道的传递概率：,信道矩阵：,根据平均互信息的定义，可得无记忆信道的N次扩展信道的平均互信息：,若信道的输入随机序列为X= (X1X2XN)，通过信道传输，接收到的随机序列为Y(Y1Y2YN)。假若信道是无记忆的，即信道传递概率满足：,则有：,式中Xi Yi是对应第 i 位的随机变量。 若信源是无记忆的，则等式成立。,直观分析：如果信源有记忆，前面传送的符号带有后面符号的信息，使得后面传送的符号的互信息减少,若信道的输入随机序列为X= (X1X2XN)，通过信道传输，接收到的随机序列为Y(Y1Y2YN)。假若信源是无记忆的，则有：,其中Xi和Yi是随机序列X和Y中的第 i 位随机变量。 直观分析：如果信道有记忆，后面传送的符号带有前面符号的信息，使得前面传送的符号的互信息增加。 若信道和信源都是无记忆的，则：,熵之间的相互关系 H(XY) = H(X) + H(Y|X) H(XY) = H(Y) + H(X|Y) H(X) = H(X|Y) H(Y) = H(Y|X) H(XY) = H(X) + H(Y),熵的意义（对通信系统） H(X)：表示信源中每个符号的平均信息量（信源熵）。 H(Y)：表示信宿中每个符号的平均信息量（信宿熵）。 H(X|Y)：表示在输出端接收到Y的全部符号后，发送端X尚存的平均不确定性。这个对X尚存的不确定性是由于干扰引起的。信道疑义度(损失熵，含糊度) H(Y|X)：表示在已知X的全部符号后，对于输出Y尚存的平均不确定性。信道散布度(噪声熵) H(XY)：表示整个信息传输系统的平均不确定性（联合熵）。,解：信源X的熵为：,例：有两个同时输出的信源X和Y，其中X的信源符号为A，B，C，Y的信源符号为D，E，F，G，已知 P(X)和P（Y/X），求联合信源的联合熵和条件熵。,信源XY输出每一对消息的联合概率为：P(XY) = P(Y/X)P(X) ，结果如下表：,联合信源的联合熵：,信源Y的条件熵： 信道散布度 (噪声熵),从上述结果可得： H(XY)=H(X)+H(Y/X) =1.461+1.956=3.417(bit/每对符号),当两个信源统计独立时，H(XY)=H(X)+H(Y)，为最大。,对第二个信源Y，其熵H(Y)的计算。由全概率公式：,因此：,联合熵的最大值为：,由于信源相关，使联合熵减小，其减小量为：,