信息论与编码_曹雪虹_PPT第二章

1、第第2章章 信源与信息熵信源与信息熵n信源描述与分类信源描述与分类n离散信源的信息熵和互信息离散信源的信息熵和互信息n离散序列信源的熵离散序列信源的熵n连续信源的熵与互信息连续信源的熵与互信息n冗余度冗余度引言 有效性和可靠性是通信系统中研究的中有效性和可靠性是通信系统中研究的中心问题，信息论是在信息可度量基础上，心问题，信息论是在信息可度量基础上，研究有效地和可靠地传递信息的科学。因研究有效地和可靠地传递信息的科学。因此，概率论、随机过程是信息论研究的基此，概率论、随机过程是信息论研究的基础和工具。础和工具。信源的数学模型信源的数学模型正如绪论中所述，在通信系统中收信者在未收到正如绪论中所述

2、，在通信系统中收信者在未收到消息以前，对信源发出什么消息是不确定的，消息以前，对信源发出什么消息是不确定的，所以可用随机变量或随机矢量来描述信源输出所以可用随机变量或随机矢量来描述信源输出的消息。或者说，用概率空间来描述信源。的消息。或者说，用概率空间来描述信源。离散信源的数学模型就是离散型的概率空间：离散信源的数学模型就是离散型的概率空间： 信息量与不确定性： 信息是事物运动状态或存在方式的不确定性的描述。那么,根据香农信息的定义，信息该如何度量呢？ 当人们收到一封E_Mail，或看了电视，到底得到多少信息量呢？显然，信息量与不确定性消除的程度有关。消除多少不确定性，就获得多少信息量。那么，

3、不确定性的大小能度量吗？ 用数学的语言来讲，不确定性就是随机性，具有不确定性的事件就是随机事件。因此，可以应用研究随机事件的数学工具 概率论来度量不确定性的大小。简单地说，不确定性的大小可以直观地看成是猜测某随机事件是否发生的难易程度。不确定性的大小能够度量，信息也可以度量：n例如：设有甲、乙两个布袋内各装有100个球。甲袋内红、白球各50个，乙袋内有红、白、蓝、黄四种球，各25个。现随意从甲袋或乙袋中摸出一球，并猜测“从甲袋中摸出的是红球”和“从乙袋中摸出的是红球”的不确定性哪一个大？n由此可见，某一事物状态的不确定性的大小，与该事物可能出现的不同状态数目以及各状态出现的概率大小有关。既然不

4、确定性的大小能够度量，可见，信息是可以度量的。下面先回忆几个基本概念：1）样本空间：n在随机事件（或实验）中，把某事物可能出现状态，即所有可能选择的消息集合在一起，称为样本空间。 每个可能选择的消息称作是该样本空间的元素。2）概率测度：n就是对每一个可能选择的消息指定一个概率。（非负的，且总和为1）。概率空间： 样本空间和它的概率测度统称为一个概率空间，用X，P来表示。在离散情况下，概率空间表示为：n其中： 就是消息 的概率，称为先验概率。4）随机变量： X 可称为随机变量，就是从样本空间到实数区域的单值映射。)(,),(),(,)(2121qqapapapaaaxpX iapia2.1信源的

5、描述与分类信源的描述与分类n信源是产生消息（符号）、消息序列和连续消信源是产生消息（符号）、消息序列和连续消息的来源。从数学上，由于消息的不确定性，息的来源。从数学上，由于消息的不确定性，因此，信源是产生随机变量、随机序列和随机因此，信源是产生随机变量、随机序列和随机过程的源过程的源n信源的基本特性是信源的基本特性是具有随机不确定性具有随机不确定性2.1信源特性与分类信源特性与分类n分类分类 时间时间 离散离散 连续连续 幅度幅度 离散离散 连续连续 记忆记忆 有有 无无 三大类：三大类： 单符号离散信源单符号离散信源 符号序列信源（有记忆和无记忆）符号序列信源（有记忆和无记忆） 连续信源连续

6、信源 2.1信源特性与分类信源特性与分类n离散无记忆序列信源离散无记忆序列信源u布袋摸球实验，若每次取出两个球，由两布袋摸球实验，若每次取出两个球，由两个球的颜色组成的消息就是符号序列。若个球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色放回布袋，再取先取出一个球，记下颜色放回布袋，再取另一个球。另一个球。)()()(),(2121LLlXpXpXpXXXXp2.1信源特性与分类信源特性与分类n离散有记忆序列信源离散有记忆序列信源u布袋摸球实验，每次取出两个球，由两个布袋摸球实验，每次取出两个球，由两个球的颜色组成的消息就是符号序列。若先球的颜色组成的消息就是符号序列。若先取出一个球，

7、记下颜色取出一个球，记下颜色不放回布袋不放回布袋，再取，再取另一个球。另一个球。)/()/()(),(1112121LLLXXXpXXpXpXXXp2.1信源特性与分类信源特性与分类n马尔可夫信源马尔可夫信源u当信源的记忆长度为当信源的记忆长度为m+1时，该时该发出时，该时该发出的符号与前的符号与前m个符号有关联性，而与更前个符号有关联性，而与更前面的符号无关。面的符号无关。)/()/()(),(112121mLLLXXXpXXpXpXXXp2.1信源描述与分类信源描述与分类n描述：通过描述：通过概率空间概率空间描述描述u单符号离散信源单符号离散信源 例如：对二进制数字与数据信源例如：对二进制

8、数字与数据信源nnpppuUuUuUupU,)(212121,211, 0,1, 010pppU2.1信源描述与分类信源描述与分类u连续信源连续信源为概率密度函数)(),()(),()(upUuupbaupU2.1信源描述与分类信源描述与分类u离散序列信源离散序列信源 以以3位位PCM信源为例信源为例)(, )(, )(,)(2121LLnnLupupupuUuUuUupU3112030,111,001,000)(ppppUUUupUL2.1信源描述与分类信源描述与分类 当当p=1/281,81,81111,001,000)( UUUupUL2.1信源描述与分类信源描述与分类n离散无记忆序列信

9、源离散无记忆序列信源u布袋摸球实验，若每次取出两个球，由两布袋摸球实验，若每次取出两个球，由两个球的颜色组成的消息就是符号序列。若个球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色放回布袋，再取先取出一个球，记下颜色放回布袋，再取另一个球。另一个球。)()()(),(2121LLlXpXpXpXXXXp2.1信源描述与分类信源描述与分类n离散有记忆序列信源离散有记忆序列信源u布袋摸球实验，每次取出两个球，由两个布袋摸球实验，每次取出两个球，由两个球的颜色组成的消息就是符号序列。若先球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色取出一个球，记下颜色不放回布袋不放回布袋，再取，再

10、取另一个球。另一个球。)/()/()(),(1112121LLLXXXpXXpXpXXXp2.1信源描述与分类信源描述与分类n马尔可夫信源马尔可夫信源u当信源的记忆长度为当信源的记忆长度为m+1时，该时该发出时，该时该发出的符号与前的符号与前m个符号有关联性，而与更前个符号有关联性，而与更前面的符号无关。面的符号无关。)/()/()(),(112121mLLLXXXpXXpXpXXXp马尔可夫过程马尔可夫过程的概念的概念离散参数离散参数马尔可夫链马尔可夫链连续参数连续参数马尔可夫链马尔可夫链补充：马尔可夫过程有限维概率分布有限维概率分布(簇簇)转移概率转移概率 绝对概率绝对概率 极限分布极限分

11、布 平稳分布平稳分布状态空间的性质状态空间的性质 马尔可夫过程马尔可夫过程补补1 1 马尔可夫过程马尔可夫过程的概念的概念补补1.1 1.1 有关定义有关定义随机过程马尔可夫性：随机过程马尔可夫性：（物理描述）（物理描述） 当随机过程在时刻当随机过程在时刻 ti 所处的状态为已知的条件下，过所处的状态为已知的条件下，过程在时刻程在时刻 t(ti)所处的状态，与过程在所处的状态，与过程在ti时刻以前的状态无时刻以前的状态无关，而仅与在关，而仅与在ti时刻的状态有关。这种已知时刻的状态有关。这种已知“现在现在”状态的状态的条件下，条件下，“将来将来”状态与状态与“过去过去”状态无关的性质，称为状态

12、无关的性质，称为马尔可夫性马尔可夫性或或无后效性无后效性。 具有具有马尔可夫性马尔可夫性或或无后效性的无后效性的随机过程，即是随机过程，即是马尔可马尔可夫夫过程过程。补补1 1 马尔可夫过程的概念马尔可夫过程的概念 补补1.1 1.1 有关定义有关定义马尔可夫过程定义：马尔可夫过程定义：（条件概率）（条件概率） 给定随机过程给定随机过程X(t), t T, ,若对于任意若对于任意n(3)个时刻个时刻t1t2 tn-1 tn T, 有有 PX(tn) xn | X(t1) = x1, X(t2) = x2, , X(tn-1) = xn-1 = PX(tn) xn | X(tn-1) = xn-

13、1或或 Fxn | x1, x2, , xn-1; t1, t2, , tn-1= Fxn; tn| xn-1 ; tn-1或或 fxn | x1, x2, , xn-1; t1, t2, , tn-1= fxn; tn| xn-1 ; tn-1则称则称随机过程随机过程X(t), t T为为马尔可夫过程马尔可夫过程。补补1 马尔可夫过程马尔可夫过程的概念的概念补补1.1 1.1 有关定义有关定义例例1 1 直线上的随机游动。直线上的随机游动。例例2 2 电话交换站在某时刻接到的呼唤次数。电话交换站在某时刻接到的呼唤次数。 0,t=0,tm+(tm,t 次数次数(t)=次数次数(tm)+次数次数

14、(tm,t) 例例3 布朗运动。布朗运动。概率概率p概率概率q概率概率p概率概率qX(0)X(n)补补1 1 马尔可夫过程马尔可夫过程的概念的概念补补1.1 1.1 有关定义有关定义转移概率分布函数和转移概率密度的定义：转移概率分布函数和转移概率密度的定义： 把马尔可夫过程把马尔可夫过程X(t), t T的条件概率分布函数的条件概率分布函数， F(x2 ; t2 | x1 ; t1= PX(t2) x2 | X(t1) = x1称为称为马尔可夫过程的马尔可夫过程的( (状态）状态）转移概率函数转移概率函数。 如果如果 则称则称f(x; t| x0 ; t0) 为为马尔可夫过程的马尔可夫过程的转

15、移概率密度转移概率密度。0000( ; |; )( ; |; )F x t x tf x t x tx补补1 1 马尔可夫过程马尔可夫过程的概念的概念补补1.1 1.1 有关定义有关定义齐次马尔可夫过程的定义：齐次马尔可夫过程的定义： 如果马尔可夫过程的转移如果马尔可夫过程的转移概率函数或概率函数或转移概率密度转移概率密度, ,只与只与转移前后的状态及相应的二个时刻的时间差有关，而与二个转移前后的状态及相应的二个时刻的时间差有关，而与二个时刻无关，即时刻无关，即 F(x2 ; t2 | x1 ; t1)= F(x2 | x1 ; t2 -t1) f(x2 ; t2 | x1 ; t1)= f(

16、x2 | x1 ; t2 -t1)称具有这种特性的称具有这种特性的马尔可夫过程为马尔可夫过程为齐次马尔可夫过程齐次马尔可夫过程。补补1 1 马尔可夫过程马尔可夫过程的概念的概念补补1.1 1.1 有关定义有关定义高阶马尔可夫过程的定义：高阶马尔可夫过程的定义： 如果马尔可夫过程在如果马尔可夫过程在tn时刻的状态，只与时刻的状态，只与tn时刻以前的时刻以前的tn-1, tn-2, tn-k这这k个时刻的状态有关，而与更前时刻的状态无关，个时刻的状态有关，而与更前时刻的状态无关，即即 F(xn ; tn | xn-1, xn-2, xn-k , xn-k-1 , x2 , x1 ;tn-1, tn

17、-2, tn-k , tn-k-1 , t2 , t1 )= F(xn ; tn | xn-1, xn-2, xn-k;tn-1, tn-2, tn-k)或或 f(xn ; tn | xn-1, xn-2, xn-k , xn-k-1 , x2 , x1 ;tn-1, tn-2, tn-k , tn-k-1 , t2 , t1 )= f(xn ; tn | xn-1, xn-2, xn-k;tn-1, tn-2, tn-k)则称具有这种特性的则称具有这种特性的马尔可夫过程为马尔可夫过程为k阶马尔可夫过程阶马尔可夫过程。5.1 5.1 马尔可夫过程马尔可夫过程的概念的概念5.1.2 5.1.2

18、切普曼柯尔莫哥洛夫方程切普曼柯尔莫哥洛夫方程定理：定理：马尔可夫过程的转移概率密度之间有下列关系：马尔可夫过程的转移概率密度之间有下列关系：其中，其中， tktrtn 。此式。此式称为称为切普曼柯尔莫哥洛夫切普曼柯尔莫哥洛夫(Chapman-Kolmogorov)方程。方程。 证证 利用由联合概率密度求边缘概率密度公式得利用由联合概率密度求边缘概率密度公式得根据条件概率密度公式，上式的被积函数可表示成根据条件概率密度公式，上式的被积函数可表示成(;|; )( ;|; ) ( ;|; )nnkknnrrrrkkrf x tx tf x tx tf x tx t dx(;|; )( ,; ,|;

19、)nnkknrnrkkrf x tx tf x x t tx t dx补补1 1 马尔可夫过程马尔可夫过程的概念的概念补补1.2 1.2 切普曼柯尔莫哥洛夫方程切普曼柯尔莫哥洛夫方程带入上式右端有带入上式右端有( ; |; )( ; |; ) ( ; |; )nnkknnrrrrkkrf x tx tf x tx t f x tx t dx( ,; , , )( , ; , |; )( ; )( ; |,; , ) ( ,; , )( ; )( ; |,; , ) ( ; |, )( ; |; ) ( ; |, )nrknrknrnrkkkknnrkrkrkrkkknnrkrkrrkknnrr

20、rrkkf x x x t t tf x x t tx tf x tf x tx x t tf x x t tf x tf x tx x t tf x tx tf x tx t f x tx t补补1 1 马尔可夫过程马尔可夫过程的概念的概念补补1.3 1.3 马尔可夫过程的分类马尔可夫过程的分类（1 1）时间离散、状态离散的马尔可夫过程）时间离散、状态离散的马尔可夫过程马尔可夫链马尔可夫链。 参数集参数集T=0,1,2,T=0,1,2,状态空间状态空间E=E=整数整数 （2 2）时间连续、状态离散的马尔可夫过程）时间连续、状态离散的马尔可夫过程可列马尔可夫可列马尔可夫过程、连续参数马尔可夫链

21、过程、连续参数马尔可夫链。 参数集参数集T=0, ,T=0, ,状态空间状态空间E=E=整数整数 （3 3）时间离散、状态连续的马尔可夫过程）时间离散、状态连续的马尔可夫过程马尔可夫序列马尔可夫序列。 参数集参数集T= 0,1,2,T= 0,1,2,状态空间状态空间E= (-, +)E= (-, +)（4 4）时间连续、状态连续的）时间连续、状态连续的马尔可夫过程马尔可夫过程。 参数集参数集T= 0, ,T= 0, ,状态空间状态空间E= (-, +)E= (-, +)补补1 1 马尔可夫过程马尔可夫过程的概念的概念 例例1 1 独立过程是马尔可夫过程独立过程是马尔可夫过程。 证证 设设X(t

22、), t T是一是一独立过程，随机事件独立过程，随机事件X(t1)=x1, X(t2)=x2, X(tn-1)=xn-1, X(tn) xn相互独立，所以相互独立，所以 PX(tn) xn | X(t1) = x1, X(t2) = x2, , X(tn-1) = xn-1 = PX(tn) xn = PX(tn) xn | X(tn-1) = xn-1因此，因此， X(t), t T是是马尔可夫过程。马尔可夫过程。补补1 1 马尔可夫过程马尔可夫过程的概念的概念 例例2 2 独立增量过程是马尔可夫过程独立增量过程是马尔可夫过程。 证证 设设X(t), t T是一是一独立增量过程，且独立增量过

23、程，且X(0)=0，有，有X(t1)- X(0) = X(t1) , X(t2)- X(t1), , X(tn-1)- X(tn-2), X(tn)- X(tn-1) 相相互独立。在互独立。在X(tn-1)已知的条件下，已知的条件下， X(tn)- X(tn-1) 与与X(t1) ，X(t2) =X(t2)- X(t1)+ X(t1), X(t3) =X(t3)- X(t2)+ X(t2), X(tn-1) =X(tn-1)- X(tn-2)+ X(tn-2)相互独立。相互独立。 PX(tn) xn | X(t1) = x1, X(t2) = x2, , X(tn-1) = xn-1 = PX

24、(tn)- X(tn-1) xn- xn-1 | X(t1) = x1, X(t2) = x2, , X(tn-1) = xn-1 = PX(tn)- X(tn-1) xn- xn-1 = PX(tn) xn | X(tn-1) = xn-1因此，因此， X(t), t T是是马尔可夫过程。马尔可夫过程。补补1 1 马尔可夫过程马尔可夫过程的概念的概念例例3 3 维纳过程维纳过程W(t), t0是是独立增量过程，且独立增量过程，且W(0) = 0，所以，所以，维纳过程是马尔可夫过程。维纳过程是马尔可夫过程。例例4 4 泊松过程泊松过程N(t), t0是是独立增量过程，且独立增量过程，且N(0)

25、 = 0，所以，所以，泊松过程是马尔可夫过程。泊松过程是马尔可夫过程。思考：思考：马尔可夫过程的无前效性。马尔可夫过程的无前效性。补补2 2 马尔可夫链马尔可夫链补补2.1 2.1 马尔可夫链的概念马尔可夫链的概念 马尔可夫链是参数集马尔可夫链是参数集T和状态空间和状态空间E皆离散的马尔可夫过皆离散的马尔可夫过程。程。 T=0,1,2,，E=i1,i2,.马尔可夫链定义：马尔可夫链定义： 设随机序列设随机序列X(n), n=0,1,2,的离散状态空间为的离散状态空间为E=i1, i2, , ,若对于任意的非负整数若对于任意的非负整数k k和和n1n20.u非周期性，所有非周期性，所有pij(n

26、)0的的n中没有比中没有比1大的大的公因子。公因子。u定理：设定理：设P是某一马尔可夫链的状态转移是某一马尔可夫链的状态转移矩阵，则该稳态分布存在的充要条件是存矩阵，则该稳态分布存在的充要条件是存在一个正整数在一个正整数N，使矩阵，使矩阵PN中的所有元素中的所有元素均大于零。均大于零。2.1信源描述与分类信源描述与分类nEg. 一个相对编码器，一个相对编码器，求平稳分布求平稳分布+TXY 2.1信源描述与分类信源描述与分类nEg. 二阶马氏链，二阶马氏链，X 0,1,求平稳分布求平稳分布起始状态000110111/201/401/203/4001/301/502/304/5S1(00)S2(0

27、1)S3(10)S4(11)2.2离散信源熵与互信息离散信源熵与互信息n信息量信息量u自信息量自信息量u联合自信息量联合自信息量u条件自信息量条件自信息量n单符号离散信源熵单符号离散信源熵u符号熵符号熵u条件熵条件熵u联合熵联合熵2.2离散信源熵与互信息离散信源熵与互信息n信息信息q不确定性的消除不确定性的消除n信息的度量信息的度量q随机性、概率随机性、概率q相互独立符合事件概率相乘、信息相加相互独立符合事件概率相乘、信息相加n熵熵q事件集的平均不确定性事件集的平均不确定性2.2离散信源熵与互信息离散信源熵与互信息G直观推导信息测度直观推导信息测度C信息信息I应该是消息概率应该是消息概率p的递

28、降函数的递降函数C由两个不同的消息（相互统计独立）所提供的信息等由两个不同的消息（相互统计独立）所提供的信息等于它们分别提供信息之和（可加性）于它们分别提供信息之和（可加性）0)(,1,)(,)(,0,)(,iiiiiiiipIppIppIppIp时且当时且当2.2离散信源熵与互信息离散信源熵与互信息l定义：对于给定的离散概率空间表示的信源，定义：对于给定的离散概率空间表示的信源，x=ai事件所对应的（自）信息为事件所对应的（自）信息为 以以2为底，为底，单位单位为比特（为比特（bit) 以以e为底，单位为奈特（为底，单位为奈特（nat) 1nat=1.433bit 以以10为底，单位为笛特（

29、为底，单位为笛特（det) 1det=3.322bit)(1log)(log)(iiiixpxpaxI 2.2离散信源熵与互信息离散信源熵与互信息l定义：联合概率空间中任一联合事件的联合（自）信定义：联合概率空间中任一联合事件的联合（自）信息量为：息量为：l定义：联合概率空间中，事件定义：联合概率空间中，事件x在事件在事件y给定条件下的给定条件下的条件条件（自）信息量为（自）信息量为：),(1log),(log),(jijijiyxpyxpyxI )/(1log)/(log)/(jijijiyxpyxpyxI 2.2离散信源熵与互信息离散信源熵与互信息n联合自信息、条件自信息与自信息间的关系联

30、合自信息、条件自信息与自信息间的关系)/()/()()()()()()/()()/(log)(log)/()(log),(log),()/()()/()(),(12112121NNNxxxxIxxIxIxxxIyIxIxyIyxxyIxIxypxpxypxpyxpyxIyxpypxypxpyxp推广相互独立和当2.2离散信源熵与互信息离散信源熵与互信息 Eg1 设在一正方形棋盘上共有设在一正方形棋盘上共有64个方格，如果甲将个方格，如果甲将一粒棋子随意地放在棋盘中的某方格内，让乙猜测棋一粒棋子随意地放在棋盘中的某方格内，让乙猜测棋子所在的位置：子所在的位置： （1）将方格按顺序编号，令乙猜测棋

31、子所在方格的）将方格按顺序编号，令乙猜测棋子所在方格的顺序号顺序号 （2）将方格按行和列编号，甲将棋子所在的方格的）将方格按行和列编号，甲将棋子所在的方格的行（或列）编号告诉乙，再令乙猜测棋子所在列（或行（或列）编号告诉乙，再令乙猜测棋子所在列（或行）所在的位置行）所在的位置。2.2离散信源熵与互信息离散信源熵与互信息 解：由于甲将一粒棋子随意地放在棋盘中的某方格内，因此解：由于甲将一粒棋子随意地放在棋盘中的某方格内，因此棋子在棋盘中所处位置为二维等概率分布棋子在棋盘中所处位置为二维等概率分布 （1）联合（自）信息量为）联合（自）信息量为 （2）条件（自）信息量为）条件（自）信息量为641),

32、(jiyxpbityxpyxIjiji6641log),(log),(22bitypyxpyxpyxIjjijiji381log)(),(log)/(log)/(2222.2离散信源熵与互信息离散信源熵与互信息 Eg2. 一个布袋内放一个布袋内放100个球，其中个球，其中80个球为红色，个球为红色，20球为白色。若随机摸取一个球，猜测其颜色，求平球为白色。若随机摸取一个球，猜测其颜色，求平均摸取一次所获得的（自）信息量。均摸取一次所获得的（自）信息量。 解：随机事件的概率空间为解：随机事件的概率空间为2 . 08 . 021xxPX2.2离散信源熵与互信息离散信源熵与互信息iiixpxpxIx

33、pxIxpINxIxNpxIxNpINbitxpxIbitxpxI)(log)()()()()()2 . 0log2 . 08 . 0log8 . 0()()()()(2 . 0log)(log)(8 . 0log)(log)(221122221122222121量为平均每次所获得的信息次后所获得的信息量为信息熵: 前面定义的自信息是指某一信源发出某一消息所含前面定义的自信息是指某一信源发出某一消息所含有的信息量。所发出的消息不同，它们所含有的有的信息量。所发出的消息不同，它们所含有的信息量也就不同。所以自信息信息量也就不同。所以自信息 是一个随机变量是一个随机变量，不能用它来作为整个信源的信

34、息测度。，不能用它来作为整个信源的信息测度。我们定义自信息的数学期望为信源的平均信息量，我们定义自信息的数学期望为信源的平均信息量，即即)(iaIiiiiiixpxpxIxpXIEXH)(log)()()()()(2.2离散信源熵与互信息离散信源熵与互信息n单符号离散信源熵单符号离散信源熵l定义：对于给定离散概率空间表示的信源所定定义：对于给定离散概率空间表示的信源所定义的随机变量义的随机变量I的数学期望为的数学期望为信源的信息熵信源的信息熵，单位为单位为比特比特/符号符号iiixpxpxIEXH)(log)()()(香农熵的简单性质与例子香农熵的简单性质与例子 推论推论1：香农熵满足一下性质

35、：香农熵满足一下性质： a.对称性；对称性； b.非负性，非负性，H(X)大于等于大于等于0。 例：如果例：如果X是一个贝努利试验，是一个贝努利试验， 则则 H(p)被称为熵函数，图被称为熵函数，图,1)0(,) 1 (pppp)()1log()1 (log)(pHdefppppXH00.20.40.60.81.00.20.40.60.81.0p()H p信息熵信息熵H是从整个信源的统计特性来考虑的。它是从整个信源的统计特性来考虑的。它是从平均意义上来表征信源的总体特性的。对是从平均意义上来表征信源的总体特性的。对于某特定的信源，其信息熵只有一个。不同的于某特定的信源，其信息熵只有一个。不同的

36、信源因统计特性不同，其熵也不同。信源因统计特性不同，其熵也不同。 所以信息熵是从平均意义上来表征信源的总体所以信息熵是从平均意义上来表征信源的总体特性的一个量。特性的一个量。n例 A、B两城市天气情况概率分布如下表：n 晴 阴 雨 n A城 08 015 005 n B城 04 03 03 问哪个城市的天气具有更大的不确定性？222( )0.8 log 0.8 0.15 log 0.15 0.05 log 0.05H A 0.8842222( )0.4log 0.40.3 log 0.30.3 log 0.3H B 1 .5 7 1 0所以，B城市的天气具有更大的不确定性。2.2离散信源熵与互

37、信息离散信源熵与互信息n离散信源条件熵离散信源条件熵l定义：对于给定离散概率空间表示的信源所定义的随定义：对于给定离散概率空间表示的信源所定义的随机变量机变量I（x/y)在集合在集合X上的数学期望为给定上的数学期望为给定y条件下条件下信源的条件熵信源的条件熵，单位为单位为比特比特/序列序列iiiyxpyxpyXIEyXH)/(log)/()/()/(jijijijyxpyxpypyXHEYXH,)/(log)/()()/()/(2.2离散信源熵与互信息离散信源熵与互信息n离散信源联合熵离散信源联合熵l定义：对于给定离散概率空间表示的信源所定义的随定义：对于给定离散概率空间表示的信源所定义的随机

38、变量机变量I（x，y)的数学期望为集合的数学期望为集合X和集合和集合Y的的信源联信源联合熵，合熵，单位为单位为比特比特/序列序列jijijiyxpyxpxyIEXYH,),(log),()()(2.2离散信源熵与互信息离散信源熵与互信息n联合熵、条件熵与熵的关系联合熵、条件熵与熵的关系)/()/()()()()()()/()()()/()()()/()()/()(),(12112121NNNXXXXHXXHXHXXXHYHXHXYHYXYXHYHXYHXYHXHXYHyxpypxypxpyxp推广相互独立和当集合2.2离散信源熵与互信息离散信源熵与互信息n单符号离散信源互信息单符号离散信源互信

39、息l定义：对于给定离散概率空间表示的信源，在定义：对于给定离散概率空间表示的信源，在出现出现y事件后所提供有关事件事件后所提供有关事件x的信息量定义互的信息量定义互信息信息，单位为单位为比特比特YyXxxpyxpyxIa,)()/(log);(互信息互信息jib，yax/ij;Xi( /b )( ;)logP (a )X YX YijPaIa b( / )( ; )log( )p x yI x yp x( ;)logjiijipI a bp)|()();(yxIxIyxI2.2离散信源熵与互信息离散信源熵与互信息n单符号离散信源互信息单符号离散信源互信息);()()/(log)()()/()(

40、log)()(),(log)()()()/(log)()/(log);(xyIypxypypxpxypxpypxpyxpypxpypyxpxpyxpyxI2.2离散信源熵与互信息离散信源熵与互信息n条件互信息量与联合互信息量条件互信息量与联合互信息量l定义：对于给定离散概率空间表示的信源，在定义：对于给定离散概率空间表示的信源，在事件事件z给定条件下，事件给定条件下，事件x与事件与事件y之间的条件之间的条件互信息量为：互信息量为：ZzYyXxzxpyzxpzyxIa,)/()/(log)/;(互信息互信息互信息的性质互信息的性质互信息的性质互信息的性质)(eI)|(feI)(eI)|(feI)

41、;(feI);(feI0.3220.1932.3222.678-2.129( /)( ;/ )log( / )p x yzI x y zp x z条件互信息条件互信息2.2离散信源熵与互信息离散信源熵与互信息n条件互信息量与联合互信息量条件互信息量与联合互信息量l定义：对于给定离散概率空间表示的信源，在定义：对于给定离散概率空间表示的信源，在事件事件z给定条件下，事件给定条件下，事件x与事件与事件y之间的条件之间的条件互信息量为：互信息量为：ZzYyXxzxpyzxpzyxIa,)/()/(log)/;(2.2离散信源熵与互信息离散信源熵与互信息n条件互信息量与联合互信息量条件互信息量与联合互

42、信息量l定义：对于给定离散概率空间表示的信源，在定义：对于给定离散概率空间表示的信源，在事件事件x与联合事件与联合事件yz之间的联合互信息量为：之间的联合互信息量为：ZzYyXxxpyzxpyzxIa,)()/(log);(2.2离散信源熵与互信息离散信源熵与互信息nEg1(p23) 设信源发出设信源发出8种消息符号，各消息等概发送种消息符号，各消息等概发送，各符号分别用，各符号分别用3位二进码元表示，并输出事件。通位二进码元表示，并输出事件。通过对输出事件的观察来推测信源的输出。假设信源发过对输出事件的观察来推测信源的输出。假设信源发出的消息出的消息x4，用二进码用二进码011表示，表示，

43、接收到每个二进制接收到每个二进制码元后得到有关码元后得到有关x4信息。信息。ZzYyXxxpyzxpyzxIa,)()/(log);(2.2离散信源熵与互信息离散信源熵与互信息符号符号符号/3811log)011;(/28121log)01;(/18141log)0 ;(444bitxIbitxIbitxIaaa2.2离散信源熵与互信息离散信源熵与互信息n平均互信息量平均互信息量 其中其中yxypxypyxypxpyxpyxxpyxpyxpyxpyxpYXI,)()/(,)()(),(,)()/(log),(log),(log),();(),()()()/()()/()();();(YXHYH

44、XHXYHYHYXHXHXYIYXIyxyxpyxpYXH,),(1log),(),(2.2离散信源熵与互信息离散信源熵与互信息n熵的性质熵的性质u对称性对称性u非负性非负性u确定性确定性u香农辅助定理香农辅助定理u最大熵定理最大熵定理u条件熵小于无条件熵条件熵小于无条件熵2.2离散信源熵与互信息离散信源熵与互信息n非负性非负性0)(0)log(lim0log0log, 100),()(021XHpppppppppHXHiipiiiini2.2离散信源熵与互信息离散信源熵与互信息n对称性对称性信息熵相同613121216131612131),(),()(3213213211121cccpZbb

45、bpYaaapXpppHpppHXHnnn2.2离散信源熵与互信息离散信源熵与互信息n确定性确定性 n香农辅助定理香农辅助定理0)0, 0 , 1 ()0 , 0 , 1 ()0 , 1 (HHHiiiiiiqppppppHloglog),(3212.2离散信源熵与互信息离散信源熵与互信息n最大熵定理最大熵定理 n条件熵小于无条件熵条件熵小于无条件熵MMMMHXHlog)1,1,1()()()/(YHXYH2.2离散信源熵与互信息离散信源熵与互信息n平均互信息的性质平均互信息的性质u非负性非负性u互易性互易性u与熵和条件熵及联合熵关系与熵和条件熵及联合熵关系u极值性极值性u凸性函数性质凸性函数

46、性质u信息不增性原理信息不增性原理2.2离散信源熵与互信息离散信源熵与互信息n非负性非负性0);();(0);(, 0);(0 1)/()()/(log)/()(log)/();(0);(yXIEYXIYxIyXIyxpxpyxpeyxpxpyxpyXIYXIyxx同理2.2离散信源熵与互信息离散信源熵与互信息n互易性互易性);()()/(log)()()/(log)();();();(,XYIypxypxypxpyxpxypYXIXYIYXIyxyx2.2离散信源熵与互信息离散信源熵与互信息n平均互信息与熵的关系平均互信息与熵的关系)/()()/()(log)()/(log)()(log)(

47、)()/(log)();()()()()/()()/()();(,YXHXHYXHxpxpyxpxypxpxypxpyxpxypYXIXYHYHXHXYHYHYXHXHYXIxyxyxyx2.2离散信源熵与互信息离散信源熵与互信息n互信息量与熵的关系互信息量与熵的关系2.2离散信源熵与互信息离散信源熵与互信息n极值性极值性0);(,)();()();(YXIYXYHXYIXHYXI独立当2.2离散信源熵与互信息离散信源熵与互信息n凸性函数凸性函数u当条件概率分布给定时，平均互信息量是输入当条件概率分布给定时，平均互信息量是输入概率分布的上凸函数概率分布的上凸函数u当集合当集合X的概率分布保持不

48、变时，平均互信息的概率分布保持不变时，平均互信息量是条件概率分布的下凸函数量是条件概率分布的下凸函数条件互信息的定义与性质条件互信息的定义与性质 利用条件熵的定义，可以将随机变量利用条件熵的定义，可以将随机变量(X,Y)关关于随机变于随机变Z的条件互信息定义为：的条件互信息定义为：zyxzyqzxpzyxpzyxpZYXI,)|()|()|,(log),()|;(2.2离散信源熵与互信息离散信源熵与互信息2.2离散信源熵与互信息离散信源熵与互信息n信息不增性信息不增性);();()/;();();(0)/;()/;()/;();();()/;();();()/;();();(YXIZXIZYX

49、IYXIZXIYZXIZXYXYXIYZXIYXIZXIZYXIZXIYZXIYZXIYXIYZXIZXY相互独立与条件下在相互独立与条件下假设在 2.3离散序列信源的熵离散序列信源的熵n离散无记忆信源的序列熵离散无记忆信源的序列熵n离散有记忆信源的序列熵离散有记忆信源的序列熵信源的信源的N重概率空间为：重概率空间为：这个空间共有这个空间共有 个元素。个元素。 如果信源先后发出的一个个符号彼此是统计独立如果信源先后发出的一个个符号彼此是统计独立的，则的，则N维随机矢量的联合概率分布满足维随机矢量的联合概率分布满足)()()()()(111111qqqqqqNaaapaaapaaaaaaxpXN

50、q 即即N维随机矢量的联合概率分布可用随机矢量中单个随机维随机矢量的联合概率分布可用随机矢量中单个随机变量的概率乘积来表示。这种信源就是离散无记忆信源变量的概率乘积来表示。这种信源就是离散无记忆信源。 一般情况下，信源先后发出的符号之间是互相依赖的。一般情况下，信源先后发出的符号之间是互相依赖的。例如在中文字母组成的中文消息中，前后文字的出现是例如在中文字母组成的中文消息中，前后文字的出现是有依赖的，不能认为是彼此不相关的，放在有依赖的，不能认为是彼此不相关的，放在N维随机矢维随机矢量的联合概率分布中，就必然要引入条件概率分布来说量的联合概率分布中，就必然要引入条件概率分布来说明它们之间的关联

51、。这种信源即有记忆信源。明它们之间的关联。这种信源即有记忆信源。 NiixpXp1)()( 设信源为X，则由X构成的N维随机矢量集合 =X1X2XN，（其中Xi与X同分布），称为信源X的N次扩展源。信源与其扩展源的关系如下图。首先，看下面N=2的简单情况。 X =X1X2XN 图图 信源信源X的的N次扩展源次扩展源nX N N个连续输出的符号合并个连续输出的符号合并nX例例 求二进制信源中的二次扩展源模型的熵。求二进制信源中的二次扩展源模型的熵。解解 设一个二元信源设一个二元信源X，符号集，符号集0，1，其二次扩展源为，其二次扩展源为 X2=X1X2 。二次扩展源。二次扩展源 的符号集为的符号

52、集为 00,01,10,11。二次扩展源。二次扩展源 的模型如的模型如(3.5)式。式。 （3.5） 各符号的概率为：各符号的概率为：2X2X)()()()()11()10()01()00()(432143212pppppX2X243221)1 ()(),()1 ()(,)(ppppppppiX)(2XH)()(XHNXHN)()()(1XHNXHXHniiN4/14/12/1321aaaPX2)41log41(21log21 2)(2)(2XHXHbit35 . 12NNNXXX 2.3离散序列信源的熵离散序列信源的熵n离散无记忆信源的序列熵离散无记忆信源的序列熵 LllnininiiLiL

53、iLinininiiiiLininiiLiiLiiniiLiiiniiiXHxpxpxpxpxpxpxpxpxpxpxpxpxpHxpxpxppppHLLLL11111112111211211)()(log)()()()(log)()()()(log)()log()()()()()()()()(log)()(111112XxxxX 2.3离散序列信源的熵离散序列信源的熵n离散无记忆信源的序列熵离散无记忆信源的序列熵n平均每个符号熵（消息熵）平均每个符号熵（消息熵）)(1)(XXHLHL , 0, 1,nnpnp11nnpnnXppnp1)(nnnpXE1log)(nnnppXH(1,.,)n

54、例3.5 设一个无限离散源的模型为： 求该信源的均值与熵。解： 比特/符号此处利用公式：由此例可以看出，无限离散信源可以有有限的均值和熵。 nnnPX2), 1(2)21(212)(111nnnnnnXE22)2log(2)(11nnnnnnXH21(1)nnanaa 信源X的极限符号熵定义为 ： 极限符号熵简称符号熵，也称熵率。)(1lim)(1lim)(1NNNNXXHNXHNXH 2.3离散序列信源的熵离散序列信源的熵n离散有记忆信源的序列熵和消息熵离散有记忆信源的序列熵和消息熵LlllLLLlllLLXXHLHLHXXHXXXHXXHXHH111111121)/(1)(1)()/()/

55、()/()()(XXX 2.3离散序列信源的熵离散序列信源的熵nEg 求信源的序列熵和平均符号熵求信源的序列熵和平均符号熵 41943611321aaaPXa1a2a3a1a2a39/111/802/113/42/901/87/9 2.3离散序列信源的熵离散序列信源的熵n离散有记忆信源的序列熵和消息熵离散有记忆信源的序列熵和消息熵结论结论1 是是L的单调非增函数的单调非增函数结论结论2结论结论3 是是L的单调非增函数的单调非增函数结论结论4)/(1LLXXH)/()(1LLLXXHHX)(XLH),/(lim)(lim)(121LLLLLXXXXHHHLXX当信源的相关性信源的相关性 信源的相

56、关性就是信源符号间的依赖程度。设信源有信源的相关性就是信源符号间的依赖程度。设信源有m个符个符号，那末对于不同情况可以分别计算信源的熵为：号，那末对于不同情况可以分别计算信源的熵为： （符号独立等概）（符号独立等概） （独立信源）（独立信源） （一阶马氏源）（一阶马氏源） （n-1阶马氏源）阶马氏源） 由平稳性与熵的不增原理，有：由平稳性与熵的不增原理，有： 可见，符号相关程度越大，熵越小，反之亦然。可见，符号相关程度越大，熵越小，反之亦然。mHlog0)(11XHH )/(122XXHH )/(11nnnXXXHH)/(lim11nnnXXXHHHHHH210 2.3离散序列信源的熵离散序列

57、信源的熵n马氏链极限熵马氏链极限熵)(),/(),/(log),(),/(log),()/(),/(11,;,111111111111111XHXXXHxxxpxxpxxxpsxxpsxpxxxp、mmiiiiiiiiiiiiiiiiiiiiimmmmmmmmmmm左边遍历马氏链对于齐次 2.3离散序列信源的熵离散序列信源的熵 iiiiiiiiiiiiiiiiiiiiiiiiiiisXHspHsXHspsxpsxpspsxpsxpsxpsxxpmmmmmmmmm)/()()X()/()()/(log)/()()/(log),()/(log),(11111111111,;,右边右边 2.3离散序列信源的熵离散序列信源的熵nEg 求马氏链平均符号熵