信息论与编码第2章信源与信息熵的知识

1、1普通高等教育“十五”国家级规划教材信息论与编码第2章 信源与信息熵信源描述与分类离散信源的信息熵和互信息离散序列信源的熵连续信源的熵与互信息冗余度2普通高等教育“十五”国家级规划教材信息论与编码2.1信源的描述与分类信源是产生消息（符号）、消息序列和连续消息的来源。从数学上，由于消息的不确定性，因此，信源是产生随机变量、随机序列和随机过程的源信源的基本特性是具有随机不确定性3普通高等教育“十五”国家级规划教材信息论与编码2.1信源特性与分类分类时间 离散 连续幅度 离散 连续记忆 有 无三大类：单符号离散信源符号序列信源（有记忆和无记忆）连续信源4普通高等教育“十五”国家级规划教材信息论与编

2、码2.1信源描述与分类描述：通过概率空间描述单符号离散信源例如：对二进制数字与数据信源(举例)5普通高等教育“十五”国家级规划教材信息论与编码2.1信源描述与分类连续信源6普通高等教育“十五”国家级规划教材信息论与编码2.1信源描述与分类离散序列信源以3位PCM信源为例（L次扩展信源）7普通高等教育“十五”国家级规划教材信息论与编码2.1信源描述与分类当p=1/2有记忆信源？8普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息信息量自信息量联合自信息量条件自信息量单符号离散信源熵符号熵条件熵联合熵9普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息信息不

3、确定性的消除信息的度量随机性、概率相互独立符合事件概率相乘、信息相加熵事件集的平均不确定性10普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息直观推导信息测度信息I应该是消息概率p的递降函数由两个不同的消息（相互统计独立）所提供的信息等于它们分别提供信息之和（可加性）11普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息定义：对于给定的离散概率空间表示的信源，x=ai事件所对应的（自）信息为以2为底，单位为比特（bit)以e为底，单位为奈特（nat) 1nat=1.433bit以10为底，单位为笛特（det) 1det=3.322bit举例1，2，3自

4、信息量的特点12普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息定义：联合概率空间中任一联合事件的联合（自）信息量为：定义：联合概率空间中，事件x在事件y给定条件下的条件（自）信息量为：13普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息联合自信息、条件自信息与自信息间的关系14普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息例1 设在一正方形棋盘上共有64个方格，如果甲将一粒棋子随意地放在棋盘中的某方格内，让乙猜测棋子所在的位置：（1）将方格按顺序编号，令乙猜测棋子所在方格的顺序号 （2）将方格按行和列编号，甲将棋子所在的方格

5、的行（或列）编号告诉乙，再令乙猜测棋子所在列（或行）所在的位置。15普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息解：由于甲将一粒棋子随意地放在棋盘中的某方格内，因此棋子在棋盘中所处位置为二维等概率分布 （1）联合（自）信息量为 （2）条件（自）信息量为16普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息例2. 一个布袋内放100个球，其中80个球为红色，20球为白色。若随机摸取一个球，猜测其颜色，求平均摸取一次所获得的（自）信息量。解：随机事件的概率空间为17普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息18普通高等教育“

6、十五”国家级规划教材信息论与编码2.2离散信源熵与互信息单符号离散信源熵定义：对于给定离散概率空间表示的信源所定义的随机变量I的数学期望为信源的信息熵，单位为比特/符号熵事件集的平均不确定性举例2-5，2-6，2-719普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息离散信源条件熵定义：对于给定离散概率空间表示的信源所定义的随机变量I（x/y)在集合X上的数学期望为给定y条件下信源的条件熵，单位为比特/序列20普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息离散信源联合熵定义：对于给定离散概率空间表示的信源所定义的随机变量I（x，y)的数学期望为集合

7、X和集合Y的信源联合熵，单位为比特/序列21普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息联合熵、条件熵与熵的关系22普通高等教育“十五”国家级规划教材信息论与编码必须掌握的概率论知识1）条件概率(conditional probability)2）联合概率(joint probability)23普通高等教育“十五”国家级规划教材信息论与编码概率论知识复习3)全概率： 设 B 1 , B 2 , 是一列互不相容的事件(B i B j = 0），且有 B 1 B 2 =（样本空间）；p（Bi）0 ，i=1，2，则对任一事件A，有： 4)Bayes公式:设 B 1 , B

8、 2 , 是一列互不相容的事件(B i B j = 0），且有 B 1 B 2 =（样本空间）；p（Bi）0 ，i=1，2，则对任一事件A，有：24普通高等教育“十五”国家级规划教材信息论与编码单符号离散信源互信息定义：对于给定离散概率空间表示的信源，在出现y事件后所提供有关事件x的信息量定义互信息，单位为比特25普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息单符号离散信源互信息符号序列之间的互信息26普通高等教育“十五”国家级规划教材信息论与编码条件互信息量与联合互信息量定义：对于给定离散概率空间表示的信源，在事件z给定条件下，事件x与事件y之间的条件互信息量为：27

9、普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息条件互信息量与联合互信息量定义：对于给定离散概率空间表示的信源，在事件x与联合事件yz之间的联合互信息量为：28普通高等教育“十五”国家级规划教材信息论与编码Eg1(p23) 设信源发出8种消息符号，各消息等概发送，各符号分别用3位二进码元表示，并输出事件。通过对输出事件的观察来推测信源的输出。假设信源发出的消息x4，用二进码011表示， 接收到每个二进制码元后得到有关x4信息。29普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息30普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息

10、平均互信息量（特点，物理意义） 其中31普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息熵的性质对称性非负性确定性香农辅助定理最大熵定理条件熵小于无条件熵32普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息非负性33普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息对称性34普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息确定性 香农辅助定理35普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息最大熵定理 条件熵小于无条件熵36普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵

11、与互信息平均互信息的性质非负性互易性与熵和条件熵及联合熵关系极值性凸性函数性质信息不增性原理37普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息非负性38普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息互易性39普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息平均互信息与熵的关系40普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息互信息量与熵的关系41普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息极值性42普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息凸性函数

12、当条件概率分布给定时，平均互信息量是输入概率分布的上凸函数当集合X的概率分布保持不变时，平均互信息量是条件概率分布的下凸函数43普通高等教育“十五”国家级规划教材信息论与编码2.2离散信源熵与互信息信息不增性44普通高等教育“十五”国家级规划教材信息论与编码 2.3离散序列信源的熵离散无记忆序列信源离散有记忆序列信源马尔可夫信源离散无记忆信源的序列熵离散有记忆信源的序列熵45普通高等教育“十五”国家级规划教材信息论与编码 2.3离散序列信源的熵离散无记忆序列信源布袋摸球实验，若每次取出两个球，由两个球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色放回布袋，再取另一个球。46普通高等教育

13、“十五”国家级规划教材信息论与编码 2.3离散序列信源的熵离散有记忆序列信源布袋摸球实验，每次取出两个球，由两个球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色不放回布袋，再取另一个球。47普通高等教育“十五”国家级规划教材信息论与编码 2.3离散序列信源的熵马尔可夫信源当信源的记忆长度为m+1时，该时该发出的符号与前m个符号有关联性，而与更前面的符号无关。48普通高等教育“十五”国家级规划教材信息论与编码 2.3离散序列信源的熵马尔可夫信源由于高阶马尔可夫信源需要引入矢量进行分析，现方法将矢量转化为状态变量。定义状态：信源在某一时刻出现符号概率xj与信源此时所处状态si有关，用条件概

14、率表示p(xj/si),状态转移概率表示为p(sj/si)49普通高等教育“十五”国家级规划教材信息论与编码 2.3离散序列信源的熵马尔可夫信源更一般，经过n-m步后转移至sj的概率50普通高等教育“十五”国家级规划教材信息论与编码 2.3离散序列信源的熵马尔可夫信源特别关心n-m=1情况，pij(m,m+1)51普通高等教育“十五”国家级规划教材信息论与编码 2.3离散序列信源的熵马尔可夫信源系统在任一时刻可处于状态空间的任意一状态，状态转移时，转移概率是一个矩阵， 一步转移转移矩阵为52普通高等教育“十五”国家级规划教材信息论与编码 2.3离散序列信源的熵马尔可夫信源k步转移概率pij(k

15、)与l步和k-l步转移概率之间满足切普曼-柯尔莫郭洛夫方程。定义：如果从状态I转移到状态j的概率与m无关，则称这类MovKov链为齐次对于齐次马尔可夫链，一步转移概率完全决定了k步转移概率。53普通高等教育“十五”国家级规划教材信息论与编码 2.3离散序列信源的熵马尔可夫信源定义：若齐次马尔可夫链对一切I,j存在不依赖于I的极限，则称其具有遍历性，pj称为平稳分布54普通高等教育“十五”国家级规划教材信息论与编码 2.3离散序列信源的熵马尔可夫信源定理：设有一齐次马尔可夫链，其状态转移矩阵为P，其稳态分布为wj55普通高等教育“十五”国家级规划教材信息论与编码 2.3离散序列信源的熵不可约性，

16、对于任意一对I和j， 都存在至少一个k，使pij(k)0.非周期性，所有pij(n)0的n中没有比1大的公因子。定理：设P是某一马尔可夫链的状态转移矩阵，则该稳态分布存在的充要条件是存在一个正整数N，使矩阵PN中的所有元素均大于零。56普通高等教育“十五”国家级规划教材信息论与编码 2.3离散序列信源的熵Eg. 一个相对编码器，求平稳分布57普通高等教育“十五”国家级规划教材信息论与编码 2.3离散序列信源的熵Eg. 二阶马氏链，X0,1,求平稳分布起始状态000110111/201/401/203/4001/301/502/304/5S1(00)S2(01)S3(10)S4(11)58普通高

17、等教育“十五”国家级规划教材信息论与编码 2.3离散序列信源的熵离散无记忆信源的序列熵59普通高等教育“十五”国家级规划教材信息论与编码 2.3离散序列信源的熵离散无记忆信源的序列熵平均每个符号熵（消息熵）60普通高等教育“十五”国家级规划教材信息论与编码 2.3离散序列信源的熵离散有记忆信源的序列熵和消息熵61普通高等教育“十五”国家级规划教材信息论与编码 2.3离散序列信源的熵Eg 求信源的序列熵和平均符号熵 a1a2a3a1a2a39/111/802/113/42/901/87/962普通高等教育“十五”国家级规划教材信息论与编码 2.3离散序列信源的熵离散有记忆信源的序列熵和消息熵结论

18、1 是L的单调非增函数结论2结论3 是L的单调非增函数结论463普通高等教育“十五”国家级规划教材信息论与编码 2.3离散序列信源的熵马氏链极限熵64普通高等教育“十五”国家级规划教材信息论与编码 2.3离散序列信源的熵65普通高等教育“十五”国家级规划教材信息论与编码 2.3离散序列信源的熵Eg 求马氏链平均符号熵（三个状态）66普通高等教育“十五”国家级规划教材信息论与编码 2.4连续信源的熵与互信息幅度连续的单个符号信源熵67普通高等教育“十五”国家级规划教材信息论与编码 2.4连续信源的熵与互信息幅度连续的单个符号信源熵68普通高等教育“十五”国家级规划教材信息论与编码 2.4连续信源的熵与互信息波形信源熵69普通高等教育“十五”国家级规划教材信息论与编码 2.4连续信源的熵与互信息最大熵定理70普通高等教育“十五”国家级规划教材信息论与编码 2.4连续信源的熵与互信息最大熵定理限平均功率最大熵定理：对于相关矩阵一定随机变量X，当它是正态分布时具有最大熵71普通高等教育“十五”国家级规划教材信息论与编码 2.5冗余度冗余度，表示给定信源在实际发出消息时所包含的多余信息。它来自两个方面，一是信源符号间的相关性；二是信源符号分布的不均匀性72普通高等教育“十五”国家级规划教材信息论与编码 2.5