信息论与编码-第2章PPT课件.pptVIP

第2章 信源与信息熵,2.1 信源的描述与分类 2.2 离散信源的信息熵和互信息 2.3 离散序列信源的熵 2.4 连续信源的熵与互信息 2.5 冗余度,信息论中的概率论基础(1),无条件概率、条件概率、联合概率满足以下关系：,信息论中的概率论基础(2),乘法定理 两个随机变量 统计独立，则 且 bayes公式,信息论中的概率论基础(3),数学期望 随机变量 发生的概率 ，则该随机变量 的数学期望为 jensen(詹森)不等式 随机矢量 ，函数 为上凸函数，则,2.1信源的描述与分类,信源是产生消息（符号symbol）、消息序列和连续消息的来源。从数学上，由于消息的不确定性，因此，信源是产生随机变量、随机序列和随机过程的源 信源的基本特性是具有随机不确定性 shannon信息论的基点,2.1信源特性与分类,分类 时间 离散 连续 幅度 离散 连续 记忆 有 无 三大类： 单符号离散信源 符号序列信源（有记忆和无记忆） 连续信源,2.1信源描述与分类,描述：通过概率空间描述 单符号离散无记忆信源的数学模型 其中，x 信源消息变量； 信源符号；n 信源空间符号个数；且 表示信源空间的完备性 例如：对二进制数字与数据信源,2.1信源描述与分类,离散序列信源（多符号离散信源） 其中 为一个符号序列，例如 以3位pcm信源为例,2.1信源描述与分类,当,2.1信源描述与分类,连续信源 且应满足 其中，积分表达式代表连续信源空间的完备性,2.2离散信源熵与互信息,信息量 -自信息量：发生某一事件（信源发出某一符号）所提供（携带）的信息量 -联合自信息量：多个随机变量同时发生某一事件所提供（携带）的信息量 -条件自信息量：多个随机变量，其中某些事件发生后，另外的事件再发生所提供的信息量 单符号离散信源熵 符号熵；条件熵；联合熵,2.2离散信源熵与互信息,信息 不确定性的消除 信息的度量 随机性、概率 相互独立符合事件概率相乘、信息相加 熵 事件集的平均不确定性,2.2离散信源熵与互信息,直观推导信息测度 信息 应该是消息概率 的递降函数 由两个不同的消息（相互统计独立）所提供的信息等于它们分别提供信息之和（可加性）,2.2离散信源熵与互信息,定义：对于给定的离散概率空间表示的信源，x=ai事件所对应的自信息为 以2为底，单位为比特(bitbinary unit) （常用） 以e为底，单位为奈特 (natnatural unit) 1nat=1.433bit 以10为底，单位为笛特(detdecimal unit) 1det=3.322bit,2.2离散信源熵与互信息,自信息的性质：,2.2离散信源熵与互信息,定义：联合概率空间中任一联合事件的联合（自）信息量为： 定义：联合概率空间中，在事件y=yj出现的条件下，事件x=xi所对应的条件（自）信息量为：,2.2离散信源熵与互信息,联合自信息、条件自信息与自信息间的关系,2.2离散信源熵与互信息,例2.1 设在一正方形棋盘上共有64个方格，如果甲将一粒棋子随意地放在棋盘中的某方格内，让乙猜测棋子所在的位置： （1）将方格按顺序编号，令乙猜测棋子所在方格的顺序号 （2）将方格按行和列编号，甲将棋子所在的方格的行（或列）编号告诉乙，再令乙猜测棋子所在列（或行）所在的位置。,2.2离散信源熵与互信息,解：由于甲将一粒棋子随意地放在棋盘中的某方格内，因此棋子在棋盘中所处位置为二维等概率分布 （1）联合（自）信息量为 （2）条件（自）信息量为,2.2离散信源熵与互信息,例2.2 (p.18)一个布袋内放100个球，其中80个球为红色，20球为白色。若随机摸取一个球，猜测其颜色，求平均摸取一次所获得的（自）信息量。 解：随机事件的概率空间为,2.2离散信源熵与互信息,2.2离散信源熵与互信息,单符号离散信源（信息）熵（information entropy） 定义：对于给定离散概率空间表示的信源所定义的自信息量i（随机变量）的数学期望为信源的（信息）熵，单位为比特/符号（或 nat/sym, det/sym） 信息熵的物理意义： 信源发出各个消息所提供的平均信息量； 总体平均意义上的信源不确定度（uncertainty）； 信源发出消息 x（随机变量）的随机性的大小,2.2离散信源熵与互信息,例2.3 (p.19) 信源符号集 ，概率分布 为 ，求信源熵。 解： 即为了表明和区分信源的每个符号只需用1.5bit的信息量,2.2离散信源熵与互信息,例2.4 (p.19) 二元信源符号集 ，概率分布 为 ，考察信源熵。 解： 其中h(p)称为二元熵函数（binary entropy function); 由图可以看出1.信息 熵为上凸函数；2.信息熵有最大值； 3.信源等概分布时信息熵最大。,2.2离散信源熵与互信息,离散信源条件熵 定义：对于给定离散概率空间表示的信源所定义的随机变量 在集合x上的数学期望为给定y条件下信源的条件熵，单位为比特/序列（或 nat/sym, det/sym）,2.2离散信源熵与互信息,离散信源联合熵 定义：对于给定离散概率空间表示的信源所定义的随机变量 的数学期望为集合 x 和集合 y 的信源联合熵，单位为比特/序列（或 nat/sym, det/sym）,2.2离散信源熵与互信息,联合熵、条件熵与熵的关系,2.2离散信源熵与互信息,当前作业 p.41-42, 习题2-32-7,2.2离散信源熵与互信息,当前作业 p.41-42, 习题2-32-7,2.2离散信源熵与互信息,单符号离散信源互信息 定义：对于给定离散概率空间表示的信源，在出现y事件后所提供有关事件x的信息量定义互信息（mutual information） ，单位为bit 其中p(x/y)称为后验概率,对应的p(x)称为先验概率,2.2离散信源熵与互信息,单符号离散信源互信息（mutual information）,2.2离散信源熵与互信息,条件互信息量与联合互信息量 定义：对于给定离散概率空间表示的信源，在事件z给定条件下，事件x与事件y之间的条件互信息量为：,2.2离散信源熵与互信息,条件互信息量与联合互信息量 定义：对于给定离散概率空间表示的信源，在事件x与联合事件yz之间的联合互信息量为：,2.2离散信源熵与互信息,例2.5 (p.23) 设信源发出8种消息符号，各消息等概发送，各符号分别用3位二进码元表示，并输出事件。通过对输出事件的观察来推测信源的输出。假设信源发出的消息x4，用二进码011表示， 接收到每个二进制码元后得到有关x4信息量。,2.2离散信源熵与互信息,2.2离散信源熵与互信息,平均互信息量互信息在x和y联合集合上的统计平均值 其中,2.2离散信源熵与互信息,熵的性质 对称性 非负性 确定性 香农辅助定理 最大熵定理 条件熵小于无条件熵,2.2离散信源熵与互信息,非负性 证明 含义：任何信源多少总能提供一些信息,2.2离散信源熵与互信息,对称性 例如： 含义：熵函数只与信源随机变量的总体结构有关,2.2离散信源熵与互信息,确定性 含义：确定信源不提供任何信息 香农辅助定理 对于任意随机变量 如下不等式成立 含义：对于任意概率分布 ，它对其它的自信息 取数学期望，必小于 本身的熵，等号在 时成立,2.2离散信源熵与互信息,最大熵定理等概分布信源，熵最大 含义：信源发出任何符号的可能性一样时，不确定性最大 条件熵小于无条件熵， 当且仅当x与y相互独立时，等号成立 含义：有相关性的信源熵不会无相关性的信源熵,2.2离散信源熵与互信息,平均互信息的性质 非负性 互易性 与熵和条件熵及联合熵关系 极值性 凸性函数性质 信息不增性原理,2.2离散信源熵与互信息,非负性 当且仅当 x与y统计独立时等号成立 含义：对于两个有相关性的信源，从其中一个信源总会得到一些另一个信源的信息,2.2离散信源熵与互信息,互易性（对称性） 设x和y分别是信道的输入和输出变量，互易性说明，信道是对称的,2.2离散信源熵与互信息,平均互信息与熵的关系 如果x和y分别是信道的输入和输出变量，条件熵h(x/y)称为（信道）疑义度；条件熵h(y/x)称为（信道）噪声熵； h(xy)称为联合熵（共熵）,其中一个关系式的证明,2.2离散信源熵与互信息,互信息量与熵的关系（维拉图）,2.2离散信源熵与互信息,极值性 含义：信道接收端所接收的信息量不会多与信源本身能够提供的信息量,2.2离散信源熵与互信息,凸性函数 当条件概率（传递概率）给定时，平均互信息量是输入概率分布的上凸函数，存在极大值 当集合x的概率分布保持不变时，平均互信息量是条件概率分布的下凸函数，存在极小值,2.2离散信源熵与互信息,信息不增性,2.2离散信源熵与互信息,数据处理定理：数据处理过程中只会失掉一些信息，绝不会创造出新的信息。所谓信息的不增性 由 可得，任何信息处理过程总会失掉信息，最多是保持原来的信息不变，而一旦失掉了信息，用任何手段也不可能再恢复丢失的信息,2.2离散信源熵与互信息,当前作业 p.42-43, 习题2-132-15,2.3离散序列信源的熵,离散无记忆序列信源 离散有记忆序列信源 马尔可夫信源 离散无记忆信源的序列熵 离散有记忆信源的序列熵,2.3离散序列信源的熵,离散序列信源的数学模型 信源输出的随机序列用随机矢量x表示 序列中的变量 l=2时的离散序列信源的概率空间可表示为,2.3离散序列信源的熵,离散无记忆序列信源 布袋摸球实验，若每次取出两个球，由两个球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色放回布袋，再取另一个球，称为放回布袋方式，则两次摸球彼此无关，称为无记忆（memoryless）,2.3离散序列信源的熵,离散有记忆序列信源 布袋摸球实验，每次取出两个球，由两个球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色不放回布袋，再取另一个球，则两次摸球彼此相关，称为有记忆（memory）,2.3离散序列信源的熵,马尔可夫(markov)信源 当信源的记忆长度为m+1时，该时该发出的符号与前m个符号有关联性，而与更前面的符号无关。,2.3离散序列信源的熵,马尔可夫信源 由于高阶马尔可夫信源需要引入矢量进行分析，现方法将矢量转化为状态变量。定义状态： 信源在某一时刻出现符号概率xj与信源此时所处状态si有关，用条件概率表示p(xj/si),状态转移概率表示为p(sj/si),2.3离散序列信源的熵,马尔可夫信源的状态转移图,2.3离散序列信源的熵,马尔可夫信源 更一般，经过n-m步后转移至sj的概率,2.3离散序列信源的熵,马尔可夫信源 特别关心n-m=1情况，pij(m,m+1),2.3离散序列信源的熵,马尔可夫信源 系统在任一时刻可处于状态空间的任意一状态，状态转移时，转移概率是一个矩阵， 一步转移转移矩阵为,2.3离散序列信源的熵,马尔可夫信源 k步转移概率pij(k)与l步和k-l步转移概率之间满足切普曼-柯尔莫郭洛夫方程。 定义：如果从状态i转移到状态j的概率与m无关，则称这类马尔可夫链为齐次 对于齐次马尔可夫链，一步转移概率完全决定了k步转移概率,2.3离散序列信源的熵,马尔可夫信源 定义：若齐次马尔可夫链对一切i,j存在不依赖于i的极限，则称其具有遍历性，pj称为平稳分布,2.3离散序列信源的熵,马尔可夫信源 定理：设有一齐次马尔可夫链，其状态转移矩阵为p，其稳态分布为wj,2.3离散序列信源的熵,不可约性，对于任意一对i和j， 都存在至少一个k，使pij(k)0 非周期性，所有pij(n)0的n中没有比1大的公因子。 定理：设p是某一马尔可夫链的状态转移矩阵，则该稳态分布存在的充要条件是存在一个正整数n，使矩阵pn中的所有元素均大于零。,2.3离散序列信源的熵,离散无记忆（序列中的符号之间无相关性）信源的序列熵,2.3离散序列信源的熵,平均每个符号熵（消息熵）平均符号熵,2.3离散序列信源的熵,离散有记忆信源的序列熵和消息熵 其中 称为平均符号熵,2.3离散序列信源的熵,例2.6 (p.31) 求离散序列信源的序列熵和平均符号熵 信源各符号的概率空间 二重符号序列(ai,aj)的概率 关联性由条件概率p(aj/ai),2.3离散序列信源的熵,例2.6 (p.31) 求信源的序列熵和平均符号熵 解： 条件熵 单符号信源熵 二重序列的熵 平均符号熵 注意： 存在关联性引起的,2.3离散序列信源的熵,离散有记忆信源的序列熵的性质 结论1 条件熵 是l的单调非增函数 即条件熵不大于无条件熵；条件较多的条件熵不大于条件较少的条件熵 结论2 平均符号熵不小于条件最多的条件熵 结论3 是l的单调非增函数 结论4 其中 称为极限熵,2.3离散序列信源的熵,马氏链极限熵,2.3离散序列信源的熵,根据以上的讨论研究，可得如下结论： 其中 等概分布单符号无记忆信源熵（最大）； 非等概分布单符号无记忆信源熵； 两符号序列平均符号熵； l符号序列平均符号熵； 极限熵,2.4连续信源的熵与互信息,幅度连续的单个符号信源熵,2.4连续信源的熵与互信息,幅度连续的单个符号信源熵 结果中第一项与离散信源熵的形式类似，是定值，称为连续信源的相对熵（差熵）； 第二项我无穷大项，这与连续信源消息数为无穷大相对应。,2.4连续信源的熵与互信息,为什么连续信源的不确定度为无穷大? 虽然连续信源熵与离散信源熵具有相同的形式，但其意义不同 连续信源的不确定度应为无穷大，这是因为连续信源可以假设是一个不可数的无限多个幅度值的信源，需要无限多个二进制比特来表示，因而它的熵为无穷大(绝对熵) 但采用上式来定义连续信源的熵是因为在实际问题中，常遇到的是熵之间的差，如互信息量，只要两者逼近时所取的x 一致，上式中第二项无穷大量是可以抵消的,2.4连续信源的熵与互信息,幅度连续的单个符号信源熵,2.4连续信源的熵与互信息,波形信源熵,2.4连续信源的熵与互信息,最大熵定理,2.4连续信源的熵与互信息,最大熵定理 限平均功率最大熵定理：对于相关矩阵一定随机变量x，当它是正态分布时具有最大熵,2.5冗余度,冗余度（多余度、剩余度）表示给定信源在实际发出消息时所包含的多余信息。它来自两个方面，一是信源符号间的相关性；二是信源符号分布的不均匀性,2.5冗余度,例2.7 (p.38-39)计算英文字母冗余度,只考虑27个符号，不考虑字母出现的概率分布时,2.5冗余度,考虑字母出现的概率分布，但认为字母间是离散无记忆的，则 考虑字母之间存在较强的相关性，某些双字母组合及三字母组合出现概率很大，如 th,he,in,