第一章无失真信源与信息熵.ppt

第第2章章 信源与信息信源与信息熵熵n n信源描述与分类n n离散信源的信息熵和互信息n n离散序列信源的熵n n连续信源的熵与互信息n n冗余度1-2.1信源的描述与分信源的描述与分类类n n信源是产生消息（符号）、消息序列和连续消息的来源。从数学上，由于消息的不确定性，因此，信源是产生随机变量、随机序列和随机过程的源n n信源的基本特性是具有随机不确定性2-2.1信源特性与分信源特性与分类类n n分类 时间时间 离散离散 连续连续 幅度幅度 离散离散 连续连续 记忆记忆 有有 无无 三大三大类类：单单符号离散信源符号离散信源 符号序列信源（有符号序列信源（有记忆记忆和无和无记忆记忆）连续连续信源信源3-2.1信源描述与分信源描述与分类类n n描述：通过概率空间描述uu单单符号离散信源符号离散信源 例如：例如：对对二二进进制数字与数据信源制数字与数据信源4-2.1信源描述与分信源描述与分类类uu连续连续信源信源5-2.1信源描述与分信源描述与分类类uu离散序列信源离散序列信源 以以3 3位位PCMPCM信源信源为为例例6-2.1信源描述与分信源描述与分类类 当当p=1/2p=1/27-2.2离散信源离散信源熵熵与互信息与互信息n n信息量uu自信息量自信息量uu联联合自信息量合自信息量uu条件自信息量条件自信息量n n单符号离散信源熵uu符号符号熵熵uu条件条件熵熵uu联联合合熵熵8-2.2离散信源离散信源熵熵与互信息与互信息n n信息n n不确定性的消除不确定性的消除n n信息的度量n n随机性、概率随机性、概率n n相互独立符合事件概率相乘、信息相加相互独立符合事件概率相乘、信息相加n n熵n n事件集的平均不确定性事件集的平均不确定性9-2.2离散信源离散信源熵熵与互信息与互信息G G直观推导信息测度C C信息信息I I应该应该是消息概率是消息概率p p的的递递降函数降函数C C由两个不同的消息（相互由两个不同的消息（相互统计统计独立）所提供的信独立）所提供的信息等于它息等于它们们分分别别提供信息之和（可加性）提供信息之和（可加性）10-2.2离散信源离散信源熵熵与互信息与互信息l l定义：对于给定的离散概率空间表示的信源，x=ai事件所对应的（自）信息为 以以2 2为为底，底，单单位位为为比特（比特（bit)bit)以以e e为为底，底，单单位位为为奈特（奈特（natnat)1nat=1.433bit)1nat=1.433bit 以以1010为为底，底，单单位位为为笛特（笛特（detdet)1det=3.322bit)1det=3.322bit11-2.2离散信源离散信源熵熵与互信息与互信息l l定定义义：联联合概率空合概率空间间中任一中任一联联合事件的合事件的联联合（自）合（自）信息量信息量为为：l l定定义义：联联合概率空合概率空间间中，事件中，事件x x在事件在事件y y给给定条件定条件下的条件下的条件（自）信息量（自）信息量为为：12-2.2离散信源离散信源熵熵与互信息与互信息n n联联合自信息、条件自信息与自信息合自信息、条件自信息与自信息间间的关系的关系13-2.2离散信源离散信源熵熵与互信息与互信息 例例1 1 设设在一正方形棋在一正方形棋盘盘上共有上共有6464个方格，如果甲将个方格，如果甲将一粒棋子随意地放在棋一粒棋子随意地放在棋盘盘中的某方格内，中的某方格内，让让乙猜乙猜测测棋子所在的位置：棋子所在的位置：（1 1）将方格按将方格按顺顺序序编编号，令乙猜号，令乙猜测测棋子所在方格棋子所在方格的的顺顺序号序号 （2 2）将方格按行和列）将方格按行和列编编号，甲将棋子所在的方号，甲将棋子所在的方格的行（或列）格的行（或列）编编号告号告诉诉乙，再令乙猜乙，再令乙猜测测棋子所棋子所在列（或行）所在的位置在列（或行）所在的位置。14-2.2离散信源离散信源熵熵与互信息与互信息 解：由于甲将一粒棋子随意地放在棋解：由于甲将一粒棋子随意地放在棋盘盘中的某方格内，中的某方格内，因此棋子在棋因此棋子在棋盘盘中所中所处处位置位置为为二二维维等概率分布等概率分布 （1 1）联联合（自）信息量合（自）信息量为为 （2 2）条件（自）信息量）条件（自）信息量为为15-2.2离散信源离散信源熵熵与互信息与互信息 例例2.2.一个布袋内放一个布袋内放100100个球，其中个球，其中8080个球个球为红为红色，色，2020球球为为白色。若随机摸取一个球，猜白色。若随机摸取一个球，猜测测其其颜颜色，色，求平均摸取一次所求平均摸取一次所获获得的（自）信息量。得的（自）信息量。解：随机事件的概率空解：随机事件的概率空间为间为16-2.2离散信源离散信源熵熵与互信息与互信息17-2.2离散信源离散信源熵熵与互信息与互信息n n单符号离散信源熵l l定义：对于给定离散概率空间表示的信源所定义的随机变量I的数学期望为信源的信息熵，单位为比特/符号18-2.2离散信源离散信源熵熵与互信息与互信息n n离散信源条件离散信源条件熵熵l l定定义义：对对于于给给定离散概率空定离散概率空间间表示的信源所定表示的信源所定义义的随机的随机变变量量I I（x/y)x/y)在集合在集合X X上的数学期望上的数学期望为给为给定定y y条件下条件下信源的条件信源的条件熵熵，单单位位为为比特比特/序列序列19-2.2离散信源离散信源熵熵与互信息与互信息n n离散信源离散信源联联合合熵熵l l定定义义：对对于于给给定离散概率空定离散概率空间间表示的信源所定表示的信源所定义义的随机的随机变变量量I I（x x，y)y)的数学期望的数学期望为为集合集合X X和集合和集合Y Y的的信源信源联联合合熵熵，单单位位为为比特比特/序列序列20-2.2离散信源离散信源熵熵与互信息与互信息n n联联合合熵熵、条件、条件熵熵与与熵熵的关系的关系21-2.2离散信源离散信源熵熵与互信息与互信息n n单符号离散信源互信息l l定义：对于给定离散概率空间表示的信源，在出现y事件后所提供有关事件x的信息量定义互信息，单位为比特22-2.2离散信源离散信源熵熵与互信息与互信息n n单符号离散信源互信息23-2.2离散信源离散信源熵熵与互信息与互信息n n条件互信息量与联合互信息量l l定义：对于给定离散概率空间表示的信源，在事件z给定条件下，事件x与事件y之间的条件互信息量为：24-2.2离散信源离散信源熵熵与互信息与互信息n n条件互信息量与联合互信息量l l定义：对于给定离散概率空间表示的信源，在事件x与联合事件yz之间的联合互信息量为：25-2.2离散信源离散信源熵熵与互信息与互信息n nEg1(p23)Eg1(p23)设设信源信源发发出出8 8种消息符号，各消息等概种消息符号，各消息等概发发送，各符号分送，各符号分别别用用3 3位二位二进码进码元表示，并元表示，并输输出事件。出事件。通通过对输过对输出事件的出事件的观观察来推察来推测测信源的信源的输输出。假出。假设设信源信源发发出的消息出的消息x x4 4，用二用二进码进码011011表示，表示，接收到每接收到每个二个二进进制制码码元后得到有关元后得到有关x x4 4信息。信息。26-2.2离散信源离散信源熵熵与互信息与互信息27-2.2离散信源离散信源熵熵与互信息与互信息n n平均互信息量 其中28-2.2离散信源离散信源熵熵与互信息与互信息n n熵的性质uu对对称性称性uu非非负负性性uu确定性确定性uu香香农辅农辅助定理助定理uu最大最大熵熵定理定理uu条件条件熵熵小于无条件小于无条件熵熵29-2.2离散信源离散信源熵熵与互信息与互信息n n非负性30-2.2离散信源离散信源熵熵与互信息与互信息n n对称性31-2.2离散信源离散信源熵熵与互信息与互信息n n确定性 n n香农辅助定理32-2.2离散信源离散信源熵熵与互信息与互信息n n最大熵定理 n n条件熵小于无条件熵33-2.2离散信源离散信源熵熵与互信息与互信息n n平均互信息的性质uu非非负负性性uu互易性互易性uu与与熵熵和条件和条件熵熵及及联联合合熵熵关系关系uu极极值值性性uu凸性函数性凸性函数性质质uu信息不增性原理信息不增性原理34-2.2离散信源离散信源熵熵与互信息与互信息n n非负性35-2.2离散信源离散信源熵熵与互信息与互信息n n互易性36-2.2离散信源离散信源熵熵与互信息与互信息n n平均互信息与熵的关系37-2.2离散信源离散信源熵熵与互信息与互信息n n互信息量与熵的关系38-2.2离散信源离散信源熵熵与互信息与互信息n n极值性39-2.2离散信源离散信源熵熵与互信息与互信息n n凸性函数uu当条件概率分布给定时，平均互信息量是输入概率分布的上凸函数uu当集合X的概率分布保持不变时，平均互信息量是条件概率分布的下凸函数40-2.2离散信源离散信源熵熵与互信息与互信息n n信息不增性41-2.3离散序列信源的离散序列信源的熵熵n n离散无记忆序列信源n n离散有记忆序列信源n n马尔可夫信源n n离散无记忆信源的序列熵n n离散有记忆信源的序列熵42-2.3离散序列信源的离散序列信源的熵熵n n离散无记忆序列信源uu布袋摸球实验，若每次取出两个球，由两个球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色放回布袋，再取另一个球。43-2.3离散序列信源的离散序列信源的熵熵n n离散有记忆序列信源uu布袋摸球实验，每次取出两个球，由两个球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色不放回布袋，再取另一个球。44-2.3离散序列信源的离散序列信源的熵熵n n马尔可夫信源uu当信源的记忆长度为m+1时，该时该发出的符号与前m个符号有关联性，而与更前面的符号无关。45-2.3离散序列信源的离散序列信源的熵熵n n马尔可夫信源uu由于高阶马尔可夫信源需要引入矢量进行分析，现方法将矢量转化为状态变量。定义状态：uu信源在某一时刻出现符号概率xj与信源此时所处状态si有关，用条件概率表示p(xj/si),状态转移概率表示为p(sj/si)46-2.3离散序列信源的离散序列信源的熵熵n n马尔可夫信源uu更一般，经过n-m步后转移至sj的概率47-2.3离散序列信源的离散序列信源的熵熵n n马尔可夫信源uu特别关心n-m=1情况，pij(m,m+1)48-2.3离散序列信源的离散序列信源的熵熵n n马尔可夫信源uu系统在任一时刻可处于状态空间的任意一状态，状态转移时，转移概率是一个矩阵，一步转移转移矩阵为49-2.3离散序列信源的离散序列信源的熵熵n n马尔可夫信源uuk步转移概率pij(k)与l步和k-l步转移概率之间满足切普曼-柯尔莫郭洛夫方程。uu定义：如果从状态I转移到状态j的概率与m无关，则称这类MovKov链为齐次uu对于齐次马尔可夫链，一步转移概率完全决定了k步转移概率。50-2.3离散序列信源的离散序列信源的熵熵n n马尔可夫信源uu定义：若齐次马尔可夫链对一切I,j存在不依赖于I的极限，则称其具有遍历性，pj称为平稳分布51-2.3离散序列信源的离散序列信源的熵熵n n马尔可夫信源uu定理：设有一齐次马尔可夫链，其状态转移矩阵为P，其稳态分布为wj52-2.3离散序列信源的离散序列信源的熵熵uu不可约性，对于任意一对I和j，都存在至少一个k，使pij(k)0.uu非周期性，所有pij(n)0的n中没有比1大的公因子。uu定理：设P是某一马尔可夫链的状态转移矩阵，则该稳态分布存在的充要条件是存在一个正整数N，使矩阵PN中的所有元素均大于零。53-2.3离散序列信源的离散序列信源的熵熵n nEg.一个相对编码器，求平稳分布54-2.3离散序列信源的离散序列信源的熵熵n nEg.二阶马氏链，X0,1,求平稳分布起始状态000110111/201/401/203/4001/301/502/304/5S1(00)S2(01)S3(10)S4(11)55-2.3离散序列信源的离散序列信源的熵熵n n离散无记忆信源的序列熵56-2.3离散序列信源的离散序列信源的熵熵n n离散无记忆信源的序列熵n n平均每个符号熵（消息熵）57-2.3离散序列信源的离散序列信源的熵熵n n离散有记忆信源的序列熵和消息熵58-2.3离散序列信源的离散序列信源的熵熵n nEg 求信源的序列熵和平均符号熵 a a1 1a a2 2a a3 3a a1 1a a2 2a a3 39/119/111/81/80 02/112/113/43/42/92/90 01/81/87/97/959-2.3离散序列信源的离散序列信源的熵熵n n离散有记忆信源的序列熵和消息熵结论结论1 1 是是L L的的单调单调非增函数非增函数结论结论2 2结论结论3 3 是是L L的的单调单调非增函数非增函数结论结论4 460-2.3离散序列信源的离散序列信源的熵熵n n马氏链极限熵61-2.3离散序列信源的离散序列信源的熵熵62-2.3离散序列信源的离散序列信源的熵熵n nEg 求马氏链平均符号熵（三个状态）63-2.4连续连续信源的信源的熵熵与互信息与互信息n n幅度连续的单个符号信源熵64-2.4连续连续信源的信源的熵熵与互信息与互信息n n幅度连续的单个符号信源熵65-2.4连续连续信源的信源的熵熵与互信息与互信息n n波形信源熵66-2.4连续连续信源的信源的熵熵与互信息与互信息n n最大最大熵熵定理定理67-2.4连续连续信源的信源的熵熵与互信息与互信息n n最大熵定理限平均功率最大限平均功率最大熵熵定理：定理：对对于相关矩于相关矩阵阵一定随机一定随机变变量量X X，当它是正，当它是正态态分布分布时时具有最大具有最大熵熵68-2.5冗余度冗余度n n冗余度，表示冗余度，表示给给定信源在定信源在实际发实际发出消息出消息时时所包含的多所包含的多余信息。它来自两个方面，一是余信息。它来自两个方面，一是信源符号信源符号间间的相关性的相关性；二是二是信源符号分布的不均匀性信源符号分布的不均匀性69-2.5冗余度冗余度n nEg.Eg.计计算英文字母冗余度算英文字母冗余度70-第第2章复章复习习 概念概念(1)n n信息是可以定量描述的，可以比较大小。由概率决定；n n对应特定信源，可以求出所含不确定度，也就是消除不确定度所需的信息量；n n可通过对信源的观察、测量获得信息，以减少对信源的不确定度；71-概念概念(2)n n考虑信源符号概率分布和符号之间的相关性，信源不确定度会下降：n nH(X)就是信源无失真时必需输出的最小信息量；72-概念概念(3)n n通过传输，信宿可以得到信息I(X;Y)，从而减小对信源的不确定度：H(X/Y)=H(X)-I(X;Y)n n信息通过系统传输，只会丢失信息，不会增加。丢失部分H(X/Y)是由噪声引起的。73-定定义义、计计算公式、相互关系算公式、相互关系n n自信息量、信源熵、相对熵n n互信息、条件熵、联合熵n n序列熵、平均符号熵、极限熵n n冗余度74-