信息论与编码,曹雪虹,课件第章-2.ppt

信息论与编码 信源与信息熵 第二章 3 2 1信源的描述和分类2 2离散信源熵和互信息2 3离散序列信源的熵2 4连续信源的熵和互信2 5冗余度 内容 4 离散信源 离散无记忆信源 离散有记忆信源 发出单个符号的无记忆信源 发出符号序列的无记忆信源 发出符号序列的有记忆信源 发出符号序列的马尔可夫信源 信源的分类 离散信源指发出在时间和幅度上都是离散分布的离散消息的信源 如文字 数字 数据等符号都是离散消息 5 信源的描述 一个离散信源发出的各个符号消息的集合为 它们的概率分别为 p xi xi的先验概率 单符号离散信源的数学模型 概率空间 6 so s1 1 0 6 0 0 3 0 0 4 s2 1 0 2 0 0 8 1 0 7 符号状态 马氏链的基本概念 7 例2 2 有一个二元二阶马尔可夫信源 其信源符号集为 0 1 已知符号条件概率 p 0 00 1 2p 1 00 1 2p 0 01 1 3p 1 01 2 3p 0 10 1 4p 1 10 3 4p 0 11 1 5p 1 11 4 5求 信源全部状态及状态转移概率 画出完整的二阶马尔可夫信源状态转移图 求平稳分布概率 8 00 01 11 10 状态转移概率矩阵 符号条件概率矩阵 1 1 2 1 3 4 0 1 3 0 1 4 0 1 2 0 1 5 1 2 3 1 4 5 s2 s1 s4 s3 稳态分布概率 稳态后的符号概率分布 10 2 2离散信源熵和互信息 11 离散信源熵和互信息 问题 什么叫不确定度 什么叫自信息量 什么叫平均不确定度 什么叫信源熵 什么叫平均自信息量 什么叫条件熵 什么叫联合熵 联合熵 条件熵和熵的关系是什么 12 离散信源熵和互信息 问题 什么叫后验概率 什么叫互信息量 什么叫平均互信息量 什么叫疑义度 什么叫噪声熵 或散布度 数据处理定理是如何描述的 熵的性质有哪些 13 2 2 1自信息量 设离散信源X 其概率空间为 如果知道事件xi已发生 则该事件所含有的信息量定义为 14 自信息量 I xi 含义 当事件xi发生以前 表示事件xi发生的不确定性当事件xi发生以后 表示事件xi所含有的信息量自信息的单位的确定在信息论中常用的对数底是2 信息量的单位为比特 bit 若取自然对数 则信息量的单位为奈特 nat 若以10为对数底 则信息量的单位为笛特 det 1nat log2e l 433bit ldet log210 3 322bit 15 自信息量 不确定度定义 随机事件的不确定度在数量上等于它的自信息量 说明 两者的单位相同 但含义却不相同 具有某种概率分布的随机事件不管发生与否 都存在不确定度 不确定度表征了该事件的特性 而自信息量是在该事件发生后给予观察者的信息量 16 自信息量 二进制码元0 1 当符号概率为p 0 1 4 p 1 3 4 则这两个符号的自信息量为 I 0 log2 1 4 log24 2bitI 1 log2 3 4 0 4151bit 一个以等概率出现的二进制码元 0 1 所包含的自信息量为 I 0 I 1 log2 1 2 log22 1bit 一个m位的二进制数 有2m个等概率的可能组合I log2 1 2m mbit 17 自信息量 I xi 的特性 I xi 是非负值 当p xi 1时 I xi 0 当p xi 0时 I xi I xi 是先验概率p xi 的单调递减函数 即当p x1 p x2 时 I x1 I x2 两个独立事件的联合信息量等于它们分别的信息量之和 即统计独立信源的信息量等于它们分别的信息量之和 18 自信息量 一个出现概率接近于1的随机事件 发生的可能性很大 所以它包含的不确定度就很小 一个出现概率很小的随机事件 很难猜测在某个时刻它能否发生 所以它包含的不确定度就很大 若是确定性事件 出现概率为1 则它包含的不确定度为0 19 自信息量 联合自信息量两个消息xi yj同时出现的联合自信息量 注意 当xi yj相互独立时 有p xiyj p xi p yj 那么就有I xiyj I xi I yj xiyj所包含的不确定度在数值上也等于它们的自信息量 20 自信息量 条件自信息量在事件yj出现的条件下 随机事件xi发生的条件概率为p xi yj 则它的条件自信息量定义为条件概率对数的负值 注意 在给定yj条件下 随机事件xi所包含的不确定度在数值上与条件自信息量相同 但两者含义不同 21 例2 3英文字母中 e 出现的概率为0 105 c 出现的概率为0 023 o 出现的概率为0 001 分别计算它们的自信息量 解 e 的自信息量I e log20 105 3 25bit c 的自信息量I c log20 023 5 44bit o 的自信息量I o log20 001 9 97bit 22 例一个布袋内放100个球 其中80个球是红色的 20个球是白色的 若随机摸取一个球 猜测其颜色 求平均摸取一次所能获得的自信息量 解 依据题意 这一随机事件的概率空间为 2 2 2离散信源熵 其中 x1表示摸出的球为红球事件 x2表示摸出的球是白球事件 23 如果摸出的是红球 则获得的信息量是I x1 log2p x1 log20 8bit如果摸出的是白球 则获得的信息量是I x2 log2p x2 log20 2bit如果每次摸出一个球后又放回袋中 再进行下一次摸取 则如此摸取n次 红球出现的次数为np x1 次 白球出现的次数为np x2 次 随机摸取n次后总共所获得的信息量为np x1 I x1 np x2 I x2 24 平均自信息量 平均随机摸取一次所获得的信息量为 H X 平均信息量 称为信源X的熵 信源熵 香农熵 25 离散信源熵 离散信源熵H X 平均不确定度 平均信息量 平均自信息量 定义信源的平均不确定度H X 为信源中各个符号不确定度的数学期望 即 单位为比特 符号或比特 符号序列 26 信源熵 信息熵 从平均意义上来表征信源的总体信息测度的一个量 自信息 指某一信源发出某一消息所含有的信息量 所发出的消息不同 它们所含有的信息量也就不同 自信息I xi 是一个随机变量 不能用它来作为整个信源的信息测度 27 信源熵 例如有两个信源 其概率空间分别为 H Y H X 信源Y比信源X的平均不确定性要大 28 信源熵 信源熵具有以下三种物理含意 信息熵H X 表示信源输出后 每个离散消息所提供的平均信息量 信息熵H X 表示信源输出前 信源的平均不确定性 信息熵H X 反映了变量X的随机性 29 例 甲地天气预报 甲地提供的平均信息量大于乙地 乙地天气预报 求 两地天气预报各自提供的平均信息量 30 甲 乙地天气预报为两极端情况 信源是一确定信源 所以不存在不确定性 信息熵等于零 lim log 0 31 甲 乙地天气预报为两极端情况 这种情况下 信源的不确定性最大 信息熵最大 甲地比乙地提供更多的信息量 因为甲地可能出现的消息数多于乙地可能出现的消息数 32 例2 6电视屏上约有500 600 3 105个格点 按每点有10个不同的灰度等级考虑 则共能组成个不同的画面 按等概率计算 平均每个画面可提供的信息量为 3 105 3 32比特 画面 33 有一篇千字文章 假定每字可从万字表中任选 则共有不同的千字文N 100001000 104000篇仍按等概率1 100001000计算 平均每篇千字文可提供的信息量为H X log2N 4 103 3 32 1 3 104比特 千字文 比较 一个电视画面 平均提供的信息量远远超过 一篇千字文 提供的信息量 34 例2 7该信源X输出符号只有两个 设为0和1输出符号发生的概率分别为p和q p q l 即信源的概率空间为 则二元信源熵为H X plogp qlogq plogp 1 p log 1 p H p 35 信源信息熵H X 是概率p的函数 通常用H p 表示p取值于 0 1 区间 H p 函数曲线如图所示 如果二元信源的输出符号是确定的 即p 1或q 1 则该信源不提供任何信息 当二元信源符号0和1以等概率发生时 信源熵达到极大值 等于1比特信息量 36 几个概念 条件熵在给定yj条件下 xi的条件自信息量为I xi yj X集合的条件熵H X yj 为 在给定Y 即各个yj 条件下 X集合的条件熵H X Y 37 几个概念 条件熵是在联合符号集合 X Y 上的条件自信息量的联合概率加权统计平均值 条件熵H X Y 表示已知Y后 X的不确定度 相应地 在给定X 即各个xi 条件下 Y集合的条件熵H Y X 定义为 38 几个概念 联合熵联合熵是联合符号集合 X Y 上的每个元素对 xi yj 的自信息量的概率加权统计平均值 联合熵H X Y 表示X和Y同时发生的不确定度 39 H XY 与H X H X Y 之间的关系 H X Y H X H Y X H X Y H Y H X Y 40 例2 9二进制通信系统用符号 0 和 1 由于存在失真 传输时会产生误码 用符号表示下列事件 u0 一个 0 发出 u1 一个 1 发出v0 一个 0 收到 v1 一个 1 收到 给定下列概率 p u0 1 2 p v0 u0 3 4 p v0 u1 1 2求 已知发出一个 0 求收到符号后得到的信息量 已知发出的符号 求收到符号后得到的信息量 知道发出的和收到的符号 求能得到的信息量 已知收到的符号 求被告知发出的符号得到的信息量 41 解 p v1 u0 1 p v0 u0 1 4 联合概率 p u0v0 p v0 u0 p u0 3 4 1 2 3 8p u0v1 p v1 u0 p u0 1 4 1 2 1 8p u1v0 p v0 u1 p u1 1 2 1 2 1 4p u1v1 p v1 u1 p u1 1 p v0 u1 1 2 1 2 1 4 42 解法1 解法2H UV H U H V U 1 0 91 1 91比特 符号 43 解法1解法2 利用贝叶斯公式 同理 p u1 v0 2 5 p u0 v1 1 3 p u1 v1 2 3 44 例2 8 一个二进信源X发出符号集 0 1 经过离散无记忆信道传输 信道输出用Y表示 由于信道中存在噪声 接收端除收到0和1的符号外 还有不确定符号 2 已知X的先验概率 p x0 2 3 p x1 1 3 符号转移概率 p y0 x0 3 4 p y2 x0 1 4p y1 x1 1 2 p y2 x1 1 2 X Y 0 1 0 1 2 3 4 1 2 1 2 1 4 信源熵 45 得联合概率 p x0y0 p x0 p y0 x0 2 3 3 4 1 2p x0y1 p x0 p y1 x0 0p x0y2 p x0 p y2 x0 2 3 1 4 1 6p x1y0 p x1 p y0 x1 0p x1y1 p x1 p y1 x1 1 3 1 2 1 6p x1y2 p x1 p y2 x1 1 3 1 2 1 6条件熵 由 46 联合熵H X Y H X H Y X 1 8bit 符号 得p y0 p xiy0 p x0y0 p x1y0 1 2 0 1