第2章-信息论基本概念1.ppt

《第2章-信息论基本概念1.ppt》由会员分享，可在线阅读，更多相关《第2章-信息论基本概念1.ppt（68页珍藏版）》请在三一文库上搜索。

1、第二章 信息论的基本概念,第一节 信源的描述和分类,第二节 离散信源的信息论概念,第三节 离散信源的熵,第一节 信源的描述和分类,一、香农信息论的基本点,用随机变量或随机矢量来表示信源，运用概率论和随机过程的理论来研究信息。,二、信源的分类,按照信源发出的消息在时间上和幅度上的分布情况可将信源分成离散信源和连续信源两大类,信源,离散信源,连续信源,连续信源 连续信源是指发出在时间和幅度上都是连续分布的连续消息（模拟消息）的信源，如语言、图像、图形等都是连续消息。,离散信源 离散信源是指发出在时间和幅度上都是离散分布的离散消息的信源，如文字、数字、数据等符号都是离散消息。,离散信源,离散无记忆信

2、源,离散有记忆信源,发出单个符号的无记忆信源,发出符号序列的无记忆信源,发出符号序列的有记忆信源,发出符号序列的马尔可夫信源,离散无记忆信源 离散无记忆信源所发出的各个符号是相互独立的，发出的符号序列中的各个符号之间没有统计关联性，各个符号的出现概率是它自身的先验概率。,离散有记忆信源 离散有记忆信源所发出的各个符号的概率是有关联的。,发出单个符号的信源 发出单个符号的信源是指信源每次只发出一个符号代表一个消息；,发出符号序列的信源 发出符号序列的信源是指信源每次发出一组含二个以上符号的符号序列代表一个消息。,发出符号序列的有记忆信源 发出符号序列的有记忆信源是指用信源发出的一个符号序列的整体

3、概率（即联合概率）反映有记忆信源的特征。,发出符号序列的马尔可夫信源 发出符号序列的马尔可夫信源是指某一个符号出现的概率只与前面一个或有限个符号有关，而不依赖更前面的那些符号，这样的信源可以用信源发出符号序列内各个符号之间的条件概率来反映记忆特征。,三、先验概率及概率空间的形式,一个离散信源发出的各个符号消息的集合为：,它们的概率分别为：,先验概率,一般信源可用一个概率空间来描述，信源的不确定程度可用该概率空间的可能状态数目及其概率来描述。,状态空间,信息论所关心的就是这种随机变量的不确定性，驱使我们对随机变量进行观察和测量，从中获取信息。,问题： 什么叫自信息量？ 什么叫不确定度？ 什么叫互

4、信息量？ 什么叫平均自信息量？ 什么叫条件熵？ 什么叫联合熵？ 联合熵、条件熵和熵的关系是什么？ 熵的性质有哪些？ 什么叫平均互信息量？ 什么叫信源熵？如何计算离散信源熵？,第二节 离散信源的信息论概念,（一） 自信息量,1. 信息量？,2. 自信息量？,3. 不确定度？,4. 联合自信息量？,5. 条件自信息量？,本节的重点内容：,I（信息量）不确定程度的减少量,（一） 自信息量,1. 信息量,定义：一个随机事件的自信息量定义为其出现概率对数的负值:,2. 自信息量,即：收信者收到一个消息后，所获得的信息量等于收到信息前后不确定程度减少的量。（举例）,c. 因为概率 越小， 的出现就越稀罕，

5、一旦出现，所获得的信息量也就较大。由于 是随机出现的，它是X的一个样值，所以是一个随机量。而 是 的函数，它必须也是一个随机量。,说明：,a. 自信息量 是非负的。,b. 对于离散无记忆信源，符号串中各符号统计独 立，符号串自信息量具有可加性：,d. 自信息量单位的确定 在信息论中常用的对数底是2，信息量的单位为比特（bit），用log2或lb表示；（ bit /符号） 若取自然对数，则信息量的单位为奈特（nat），用loge或ln表示；（nat/符号） 若以10为对数底，则信息量的单位为哈脱莱(Hartley)，用log10或lg表示；（hartley/符号） 若对数底为r，则信息量的单位为

6、r进制用单位/符号。 这三个信息量单位之间的转换关系如下：,1 natlog2e l.433 bit， l Hartley log210 3.322 bit,定义：随机事件的不确定度在数量上等于它的自信息量 说明: 两者的单位相同，但含义却不相同。 具有某种概率分布的随机事件不管发生与否，都存在不确定度，不确定度表征了该事件的特性，而自信息量是在该事件发生后给予观察者的信息量。,3. 不确定度,一个出现概率接近于1的随机事件，发生的可能性很大，所以它包含的不确定度就很小； 反之，一个出现概率很小的随机事件，很难猜测在某个时刻它能否发生，所以它包含的不确定度就很大； 若是确定性事件，出现概率为1

7、，则它包含的不确定度为0。,几个关于自信息量的例子：,（1） 一个以等概率出现的二进制码元（0，1）所包含的自信息量为： I（0）= I（1）= - log2 （1/2）=log22=1 bit/符号,（2）若是一个m位的二进制数，因为该数的每一位可从0, 1两个数字中任取一个，因此有2m个等概率的可能组合。所以I= -log2(1/2m)=m bit/符号，就是需要m比特的信息来指明这样的二进制数。,（3）具有四个取值符号的随机变量 各符号概率相等，均为1/4，各符号的自信息量：,注： bit的含义是二进制数字（0、1），自信息量为2（bit/符号），意味着其不确定性可用2位二进制数字来度量

8、（00、01、10、11）。 若取4为对数底，自信息量为1（四进制单位/符号），意味着其不确定性可用1位四进制数字来度量（0、1、2、3）。,（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）= -lb 0.0019.97 （bit/符号）,（5）某离散无记忆信源（DMS Discrete Memoryless Source）的概

9、率空间为 信源发出消息202 120 130 213 001 203 210 110 321 010 021 032 011 223 210。 求该消息的自信息量以及消息中平均每符号的自信息量？,解：信源符号的自信息量：,单位都是 bit/符号,信源无记忆，发出的符号串中各符号统计独立，由自信息量的可加性，符号串自信息量等于各符号自信息量之和：,平均一个符号的自信息量：,（6）同时抛掷一对质地均匀的骰子，每个骰子各面朝上的概率均为1/6，试求： (a). 事件“3和5同时发生”的自信息量？ (b). 事件“两个1同时发生”的自信息量？ (c). 事件“两个点数中至少有一个是1”的自信息量？,解

10、: (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）。,（7）在布袋中放入81枚硬币，它们的外形完全相同。已知有一枚硬币与其它80枚硬币重量不同，但不知这个硬币比其它硬币的重量是重还是轻。问确定随意取出的一枚硬币恰好是重量不同硬币的所需要的信息量是多少？并进一不确定它比其它硬币是重还是轻所需要的信息量是多少？,解: (a) P(A

11、)=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）。,4. 联合自信息量,bit/二元符号,随机变量Z是两个随机变量X、Y的联合，即Z=XY，其概率空间：,二元联合符号的自信息量称为联合自信息量：,同理，三元联合符号的联合自信息量：,bit/三元符号,注意: 当(xi，yj)相互独立时，有P(xi，yj)=P(xi)P(yj)，那么就有 I(xi，yj)=I(xi)+I(yj)。 (xi，yj) 所包含的不确定度在数值上也等于它们的自信息量。,定义：,注意: 在给定yj条件下，随机事件xi所包

12、含的不确定度在数值上与条件自信息量相同，但两者含义不同。,5. 条件自信息量,bit/符号,定义两种条件自信息量：,bit/符号,条件自信息量物理意义：,几个关于条件自信息量的例子：,（1）由于棋子落入任一方格都是等可能的，则,棋子落入某方格的不确定性就是自信息量,bit/符号,解：设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. 居住在某

13、地区的女孩中有25是大学生，在女大学生中有75是身高1.6m以上的，而女孩中身高1.6m以上的占总数一半。假如我们得知“身高1.6m以上的某女孩是大学生”的消息，问获得多少信息量？,（二） 互信息量,互信息量,设观察输入为:,设观察结果为:,从yj中得到有关输入符号xi的信息称为xi与yj之间的互信息量（事件信息） （注意与联合自信息量符号标志不同 ）。,信息先验不确定性后验不确定性,xi在观察到yj前不确定性 xi在观察到yj后不确定性,(1) yj对xi的互信息 I(xi;yj) I(xi;yj)= I(xi)- I(xi/yj) 含义 互信息I(xi;yj) =自信息I(xi) - 条件

14、自信息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的概率,即互信息量为后验概率与先验概率比值的对数 :,(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) 不同！,(4

15、) 实在信息： 后验概率p(xi|yj)1，即收到yj时就能完全肯定此时的输入一定是xi ， xi的后验不确定性完全消除：,即从输出结果中得到了输入实有的全部信息实在信息：,注意 a. 输入的先验不确定性 在数值上等于自身含有的实 在信息。 b. 信息与不确定性是两个不同的物理概念， 不是信息， 只是不确定性，互信息量 才是信息，把 当作信息只是说明一种数量上的相等关系。,(4) 互信息量定义扩展： 符号xi与符号对yj zk之间的互信息量定义为：,2. 互信息的性质（具体推导可见课本p24） (1) 对称性I(xi ;yj) = I(yj ;xi) (2) X与Y独立时I(xi ;yj) =

16、 0 (3) I(xi;yj) 可为正、负、0 当事件xi 和yj 统计独立时，互信息量为零;互信息量为正，说明yj 的出现有助于减小xi 的不确定性；反之，互信息量为负说明yj 的出现增大了xi 的不确定性（比如信道存在干扰）。 (4)任何两个事件之间的互信息量不可能大于其中任意事件的自信息量,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) =

17、0 当xi代表“飞机正点起飞”时，I(xi/yj)I(xi)，I(xi;yj) 0,3. 条件互信息量 给定zk条件下，xi 与yj间的互信息量,另外，还存在xi 与yjzk 之间的互信息量：,（该式推导见p25-26）,由上述两式得：,说明：一个联合事件yjzk 出现后提供的有关xi的信息量=zk事件出现后提供的有关xi的信息量在给定zk条件下再出现yj事件后所提供的有关xi的信息量,4. 关于互信息的例子 已知信源发出 两种消息，且 此消息在二进制对称信道上传输，信道传输特性为： 求互信息量,解：根据 得到：,一个布袋内放100个球，其中80个球是红色的，20个球是白色的，若随机摸取一个球

18、，猜测其颜色，求平均摸取一次所能获得的自信息量。 解: 依据题意 这一随机事件的概率空间为,（三) 平均自信息量-熵,其中：x1表示摸出的球为红球事件，x2表示摸出的 球是白球事件 . 如果摸出的是红球，则获得的信息量是 I（x1）= -log2p（x1）= - lb0.8 =3bit 如果摸出的是白球，则获得的信息量是 I（x2）= -log2p（x2）= -lb0.2 =1bit,如果每次摸出一个球后又放回袋中，再进行下一次摸取。则如此摸取n次，红球出现的次数为np（x1）次，白球出现的次数为np（x2）次。随机摸取n次后总共所获得的信息量为 np（x1）I（x1）+np（x2）I（x2）

19、,则平均随机摸取一次所获得的信息量为 H（X）= 1/nnp（x1）I（x1）+np（x2）I（x2） = -p（x1）log2p（x1）+p（x2）log2p（x2）,= 0.72比特/次,说明：,自信息量I（x1）和I（x2）只是表征信源中各个符号的不确定度，一个信源总是包含着多个符号消息，各个符号消息又按概率空间的先验概率分布，因而各个符号的自信息量是一个随机变量，所以自信息量不能作为整个信源的信息测度。,因为X中各符号xi的自信息量I（xi）为非负值，p（xi）也是非负值，且0 p(xi) 1，故信源的平均自信息量H（X）也是非负量。,定义：离散信源熵H(X)(平均不确定度/平均信息量

20、/平均自信息量/信息熵/熵) 定义信源的平均不确定度H(X)为信源中各个符号不确定度的数学期望，即：,单位为比特/符号或比特/符号序列,平均自信息量H（X）的定义公式与热力学中熵的表示形 式相同，所以又把H（X）称为信源X的熵。熵是在平均意义 上来表征信源的总体特性的，可以表征信源的平均不确定度。,某一信源，不管它是否输出符号，只要这些符号具有某些概率特性，必有信源的熵值；这熵值是在总体平均上才有意义，因而是一个确定值，一般写成H（X），X是指随机变量的整体（包括概率分布）。 信息量则只有当信源输出符号而被接收者收到后，才有意义，这就是给予接收者的信息度量，这值本身也可以是随机量，也可以与接收

21、者的情况有关。,6）当某一符号 的概率 为零时， 在熵公式中无意义， 为此规定这时的 也为零。当信源X中只含一个符号 时， 必定有 ，此时信源熵H（X）为零。,7）平均自信息量H（X）表示集X中事件出现的平均不确定性，即为了在观测之前，确定集X中出现一个事件平均所需的信息量；或者说在观测之后，集X 中出现一个事件平均给出的信息量。,例：电视屏上约有 500 600= 3 105个格点，按每点有 10个不同的灰度等级考虑，则共能组成 个不同的画面。按等概率 计算，平均每个画面可提供的信息量为,=3 105 3.32 比特/画面,例：有一篇千字文章，假定每字可从万字表中任选，则共有不同的千字文 N

22、=100001000=104000 篇 仍按等概率1/100001000计算，平均每篇千字文可提供的信息量为 H（X）log2N 4 103 332 13 104 比特千字文,比较：,“一个电视画面”平均提供的信息量远远超过“一篇千字文”提供的信息量。,例：设信源符号集X=x1,x2,x3，每个符号发生的概率分别为p（x1）=1/2，p（x2）l4，p（x3）14。 则信源熵为 H（X）=1/2log22+1/4log24+1/4log24 =1.5 比特/符号,例：该信源X输出符号只有两个，设为0和1。输出符号发生的概率分别为p和q，pq=l。即信源的概率空间为,则二元信源熵为 H（X）=

23、-plbp-qlbq = -plbp-(1-p)lb(1-p) =H(p),说明：,信源信息熵H（X）是概率p的函数，通常用H（p）表示。p取值于0，1区间。H（p）函数曲线如图所示。从图中看出，如果二元信源的输出符号是确定的，即p=1或q=1，则该信源不提供任何信息。反之，当二元信源符号0和1以等概率发生时，信源熵达到极大值，等于1比特信息量。,几个概念,定义： 在给定yj条件下，xi的条件自信息量为I(xi/yj)，X 集合的条件熵H（X/yj）为 H（X/yj）= 在给定Y（即各个yj）条件下，X集合的条件熵 H(X/Y)定义为 H（X/Y）= =,条件熵,相应地，在给定X（即各个xi）

24、的条件下，Y集合的条件 熵H(Y/X)定义为 H(Y/X)=,【注意】： 条件熵是在联合符号集合XY上的条件自信息量的联合概率加权统计平均值。,联合熵（共熵）,定义：联合熵是联合符号集合 XY上的每个元素对xiyj的联合自信息量的联合概率加权统计平均值。定义为： H（XY）= 【说明】表示X和Y同时发生的平均不确定度。,联合熵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相互独立时，等号成立！共熵得到最大值！）,【注

25、】上式表明，从平均意义上讲，条件熵在一般情形下 总是小于无条件熵。从直观上说，由于事物总是联 系的，因此对随机变量X的了解平均讲总能使Y的不 确定性减少。同样，对Y的了解也会减少X的不确 定性。,证明:,同理:,所以,同理：,2）的证明见课本p29（略）,三维联合符号集合XYZ上的共熵H(XYZ):,存在下列关系 ：,1） H（XYZ）H（XY）H（ZXY） H（X）H（Y X ）H（ZXY） 2） H（XYZ） H（X） H（Y） H（Z） （当X、Y、Z相互独立时，等号成立！） 3） H（ZXY） H（ZY） H（Z） （条件熵的条件越多，其条件熵就越小！）,关于熵的几个例题,1. 如有6

26、行8列的棋型方格，若有2个质点A和B，分别以等概率落入任一方格内，但A、B不能落入同一方格内，试求： （1）若仅有质点A，求A落入任一个方格的平均自信息量是多少？ （2）若已知A已入，求B落入的平均自信息量？ （3）若A、B是可分辨的，求A、B同时落入的平均自信息量？ 解：（1） （2） （3）,关于熵的几个例题,解：男性、女性红绿色盲、不是红绿色盲的概率记作：,2. 从大量统计资料知道，男性中红绿色盲的发病率为7，女性发病率为0.5，如果你问一个男同志：“你是否是红绿色盲？”他的回答可能是“是”，可能是“否”，问这两个回答中各含有多少信息量？平均每个回答中含有多少信息量？如果你问一位女同志，

27、则回答中含有的平均信息量是多少？,信源熵基本性质,1. 非负性（由定义）： 2. 对称性：当概率矢量 中的各分量的次序 任意变更时，熵值不变。 【注】熵仅与信源的总体统计特性有关，不关其内部结构如何。,3. 最大熵 ：等概时 H(X)max=log2M 附 若M=2, 则 H(X)= -plog2p (1-p)log2(1-p)=H(p)，当p=0.5时最大。 重要公式,证明： H(X)logM P(X)log1/P(X) P(X)logM （ P(X)1） P(X)log（1/P(X)M） 在这里利用自然对数性质： ln 1 ,1 当且仅当1时，式取等 令1/P(X)M,引用上述性质，得 H

28、(X)logM P(X) 1/P(X)M1loge 1/MP(X)loge 1/M P(X)loge 括号中 1/M 和 P(X)的值均为1 所以， H(X)logM 0，即 H（X） logM 当且仅当1/P(X)M1,即P(X)1/M时，式取等 此定理说明：当X集合中的各个符号消息以等概率分布出现时，可得最大信源熵为 H(X)maxlogM,定理 条件熵不大于信源熵(无条件熵) H(X/Y) H(X) H(Y/X) H(Y),当且仅当Y和X相互独立时，式取等,证明： H(Y|X)H(Y) P(x,y)log1/P(y|x) P(y)log1/P(y) P(x,y)log1/P(y|x) P

29、(y)P(x|y)log1/P(y) P(x,y)log1/P(y|x) P(x,y)log1/P(y) P(x,y)logP(y)/P(y|x) 在这里同样利用自然对数性质：ln 1 ,1 当且仅当1时，式取等 令P(y)/P(y|x)，引用 ln 1 H(Y|X)H(Y) P(xy)P(y)/P(y|x)1loge P(x)P(y)P(xy)loge （11）loge0,（续上） 当且仅当P(y)/P(y|x)1时，即P(y|x)P(y)时，式取等 同理有： H（X|Y） H（X） 此定理说明：条件熵小于或等于原符号集合的熵 推广1:两个条件下的条件熵与一个条件下的条件熵之间存在关系 H（Z|XY） H（Z|Y） 当且仅当 P(z|xy)P(z|y)时，式取等 强调指出：条件熵的条件越多，其条件熵的值就越小 H（Z|XY） H（Z|Y ） H（Z） 推广2：共熵与两个集合的信源熵存在关系 H(XY) H(X) H(Y) 当且仅当两个集合相互独立时，式取等,4. 扩展性： 信源含有的新增消息为小概率时，熵不变 5. 确定性：某消息取值概率为1时，熵为0 6. 可加性： H(XY)=H(X)+H(Y/X)=H(Y)+H(X/Y) 7. 极值性：,8. 上凸性 含义 熵H(P) P(概率分布p(xi)为上凸曲线 意义 上凸曲线有最大值 结论 H(X)max=log2m （等概）,