第三章信源熵ppt

发布者:admin 发布时间:2019-10-29 16:11 浏览次数:

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  第三章 信源及信源熵(3) 上节课回顾 马尔可夫链基础知识 什么是马尔可夫链? 转移概率---转移概率矩阵 平稳性 遍历性 本节课内容 马尔科夫信源 信源的相关性和剩余度 3.6 马尔可夫信源 马尔可夫信源是一类相对简单的有记 忆信源,信源在某一时刻发出某一符号 的概率除与该符号有关外,只与此前发 出的有限个符号有关。因此我们把前面 若干个符号看作一个状态,可以认为信 源在某一时刻发出某一符号的概率除了 与该符号有关外,只与该时刻信源所处 的状态有关,而与过去的状态无关。信 源发出一个符号后,信源所处的状态即 发生改变,这些状态的变化组成了马氏 链。 例1 设一个二元一阶的马尔可夫信源,信源符号集为x={0,1},信源输出符号的条件概率为: p(00)=0.25, p(01)=0.5, p(10)=0.75, p(11)=0.5 求状态转移概率 对于一般的 阶马尔可夫信源,它的概率空间可以表示成: 令 ,从而得到 马尔可夫信源的状态空间: 状态空间由所有状态及状态间的状态转移概率组成。通过引入状态转移概率,可以将对马尔可夫信源的研究转化为对马尔可夫链的研究。 下面计算遍历的m阶马尔可夫信源的熵率。 当时间足够长后,遍历的马尔可夫信源可以视作平稳信源来处理,又因为m阶马尔可夫信源发出的符号只与最近的m个符号有关,所以极限熵 等于条件熵 。 例3 求例2中的二阶马尔可夫信源的极限熵。 解:这4种状态是不可约的非周期长返态,因此是遍历的。 设状态的平稳分布为(w1,w2,w3,w4),根据马尔可夫链遍历的充分条件:WP=W,得 所以, 符号的平稳概率分布为: 例3 一阶马尔可夫信源的状态图如下图所示。信源X的符号集为{0, 1, 2}。 (1) 求平稳后信源的概率分布; (2) 求信源的熵H∞。 (3)求当P=0或P=1时信源的熵 ,并说明理由 信源的剩余度来自两个方面:一是信源符号间的相关性,相关程度越大,符号间的依赖关系越长,信源的 越小;另一方面是信源输出消息的不等概分布使信源的 减小。当信源输出符号间不存在相关性并且输出消息为等概分布时信源的 最大,等于 。对于一般平稳信源来说,其极限熵 远小于 。 为了更经济有效的传送信息,需要尽量压缩信源的剩余度,压缩剩余度的方法是尽量减小符号间的相关性,并且尽可能的使信源输出消息等概率分布。 当冗余度=0时,信源的熵=极大熵 ,表明信源符号之间:(1)统计独立无记忆;(2)各符号等概分布。因此,冗余度可衡量信源输出的符号序列中各符号之间的依赖程度。 例:以符号是英文字母的信源为例,英文字母加上空格共有27个,则最大熵为 但实际上,用英文字母组成单词,再由单词组成句子时,英文字母并不是等概率出现,此时有: 因此,在信源所输出的序列中依赖关系越复杂,信息熵就越小。实际上,英文信源的信息熵还要小得多,一般认为 。因此,信息效率和冗余度为: 这说明,写英语文章时,71%是由语言结构定好的,是多余成分,只有29%是写文章的人可以自由选择的。直观的说,100页英文书,理论上看仅有29页是有效的,其余71页可以压缩掉,这压缩掉的文字可以根据英文的统计特性来恢复。 信源的冗余度表示信源的可压缩程度。 从提高信息传输效率的观点出发,人们总是希望尽量去掉剩余度。比如发电报,我们都知道尽可能把电文写的简洁些以去除相关性。但冗余度大的消息具有比较强的抗干扰性。从我们的第五章开始,将讨论信源编码和信道编码,信源编码是减少或消除信源的剩余度以提高信息的传输效率,而信道编码则通过增加冗余度来提高消息传输的抗干扰能力。 * * 马尔可夫链的定义 时间和状态都是离散的马尔可夫过程称为马尔 可夫链, 简记为 称条件概率 转移概率 平稳性 有关时, 称转移概率具有平稳性. 同时也称此链是齐次的或时齐的. 定义 则称此链具有遍历性. 遍历性 图 马尔可夫信源 例2:二阶马尔可夫信源,原始符号集为{1,0}, 条件概率定为:P(000)=P(111)=0.8 P(100)=P(011)=0.2 P(001)=P(010)=P(101)=P(110)=0.5 由此可见,信源共有2^2=4种状态 S:{S1=00,S2=01,S3=10,S4=11} 01 10 0:0.5 1:0.2 0:0.2 00 0:0.8 11 1:0.8 1:0.5 0:0.5 1:0.5 由上例可知,m阶马尔可夫信源符号集共有q个符号,则信源共有 个不同状态。信源在某一时刻时,必然处于某一种状态,等到下一个字符输出时,转移到另外一个状态。 对于齐次遍历的马尔可夫链,其状态 由 唯一确定,所以 求出 3.7 信源剩余度与自然语言的熵 1、关于离散信源熵的总结: 实际信源可能是非平稳的有记忆随机序列信源;其极限熵是不一定存在的;解决的方法是假设其为离散平稳随机序列信源,极限熵存在,但求解困难;进一步假设其为m阶Markov信源,用其m阶条件熵近似;再进一步假设为一阶Markov信源,用其一阶条件熵来近似;最简化的信源是离散无记忆信源,其熵为H(x);最后还可以假定为等概的离散无记忆信源,其熵H(x); 它们之间的关系可以表示为: 2、熵的相对率(一个信源的熵率与具有相同符号集的最大熵的比值) 3、信源剩余度 Bit/符号 Bit/符号 Bit/符号 Bit/符号

  请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。用户名:验证码:匿名?发表评论


上一篇:信息论之马尔可夫信源    下一篇:没有了