信息论之马尔可夫信源

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

  第二章离散信源及其信息测度 2.7 马尔可夫信源 2.8 信源剩余度与自然语言的熵 *2.9 信息意义和加权熵 非平稳离散信源:描述信源输出消息的随机序列X 是非平稳的随机序列——马尔可夫信源 输出的随机序列X中各随机变量之间有依赖关系。 但记忆长度有限且满足马尔可夫链的性质,因此可 以用马尔科夫链来处理。本节将讨论这类信源及其 信息熵。 2.7 马尔可夫信源 定义若信源输出的符号序列和信源所处的状态满足下列两 个条件。 某一时刻信源符号的输出只与此刻信源所处的状 态有关,而与以前的状态及以前的输出符号都无关。即 若时齐马尔可夫链对一切存在不依赖于 的极限 注:条件表明,若信源处于某一状态,当它输出一个符 号后,所处的状态就变了,一定从状态 转移到另一状态。 显然,状态的转移依赖于输出的信源符号,因此任何时刻信源 处于什么状态完全由前一时刻的状态和输出的符号决定。 这种信源的状态序列在数学模型上可以作为时齐马尔可夫链来处理。因而可用马尔可夫链的状态转移图来描述信源。 马尔可夫链的状态转移图:每个圆圈代表一种状态,状 态之间的有向线代表某一状态向另一状态转移。有向线一侧 的符号和数字分别代表发出的符号和条件概率。 现先举一例说明这些概率及状态转移图 例2.8 设信源符号 ,信源所处的状态 各状态之间转移情况如图2.4 图2.4状态转移图 定义m阶有记忆离散信源的数学模型可由一组信源符号集和一 组条件概率确定: 不同状态,对应于个长度为m的不同符号序列。 阶马尔可夫信源在任何时刻,符号发生的概率只与前m个 符号有关,所以可设状态 。由于 可取,的信源状态集 则已知的条 件概率可变换成 条件概率则表示任何 时刻信源处在状态 时输出 符号 的概率。而 表示。而且当在时刻,信源输出符号 后,由符号序 信源所处的状态也由转移到 例2.9有一个二元二阶马尔可夫信源,其信源符号集为 求状态转移图及状态之间的转移概率。01 10 11 00 1:0.2 0:0.8 0:0.5 0:0.2 1:0.5 0:0.5 1:0.5 1:0.8 是时齐的、遍历的马尔可夫状态链的极限概率(即马尔可夫信源稳定后(N)各状态的极限概率。)。 它满足 3.马尔可夫信源的熵时齐的、遍历的m阶马尔可夫信源的熵 写成 4.m阶马尔可夫信源的信息熵它是时齐、遍历m阶马尔可夫状态 链的极限概率,是信源在足够长时间以后符号序列达到稳定 后的m长符号序列的联合概率分布。它不等于起始的有限长 时间段内的m维联合概率分布。 根据条件熵的定义,时齐、遍历的m阶马尔可夫信源的熵又可 写成: 由此得时齐、遍历的m阶马尔可夫信源的熵等于有限记忆长度为m的条件熵。但必须注意它不同于有限记忆长度为m的离散平稳 信源。时齐、遍历的m阶马尔可夫信源并非是记忆长度为m的离 散平稳信源。只有当时间N足够长以后,信源所处的状态链达到 稳定,这时由m个符号组成的各种可能的状态达到一种稳定分布 后,才可将时齐、遍历的m阶马尔可夫信源作为记忆长度为m的 离散平稳信源。 一阶马尔可夫信源的概率空间为 例2.10一个二元二阶马尔可夫信源,其信源符号集为{0,1} 信源开始时:p(0) 。下一单位时间:输出随机变量X 0.30.4 0.70.6 再下一单位时间:输出随机变量X 0001 10 11 0.40.2 0.3 0.4 0.60.8 0.7 0.6 从第四单位时间开始,任一时刻随机变量只与前面二 个单位时间的随机变量 有依赖关系,即 求:信源状态转移情况和相应概率; 画出完整的二阶马尔可夫信源状态转移图; 求平稳分布概率; 马尔科夫信源达到稳定后,0和1的分布概率。 状态,并以等概率发出符号0和1,分别到达状 ,以0.3和0.7的概率发出0和1到达E 0001 10 11 1:0.5 0:0.3 0:0.4 1:0.7 1:0.6 从第3单位时间以后信源必处在E3 E4 E5 E6四种状态之一。在 i3后,信源的状态转移可用图b 表示: 00 10 11 01 0:0.4 0:0.4 0:0.3 0:0.2 1:0.6 1:0.7 1:0.8 1:0.6 0:0.40:0.4 0:0.3 0:0.5 1:0.5 1:0.6 1:0.8 1:0.7 0:0.2 1:0.6 组成一个不可约闭集,并且具有遍历性。 由题意,此马尔可夫信源的状态必然会进入这个不可约闭集,所以我们计算信源熵时可以不考虑过渡状态及过渡过程。 m阶马尔可夫信源在起始的有限时间内,信源不是平稳和遍历/各态历经性的,状态的概率分布有一段起始渐 变过程。经过足够长时间之后,信源处于什么状态已 与初始状态无关,这时每种状态出现的概率已达到一 种稳定分布。 一般马尔可夫信源并非是平稳信源。但当时齐、遍历的马尔可夫信源达到稳定后,这时就可以看成是平稳 信源。m阶马尔可夫信源是非平稳离散有记忆信源的一 个特例。 并非在任何情况下都存在。对q元m阶马尔可夫信源来说,只有状态极限概率 ,j=1,2,„,q 离散平稳信源 m阶马尔可 夫信源 一阶马尔 可夫信源 实际信源 离散无 记忆信 散无记忆信源 1、关于离散信源熵 实际信源可能是非平稳离散有记忆随机序列信源,其 信息熵不一定存在;解决的方法是假设其为离散平稳随机 序列信源,信息熵存在,但求解困难;进一步假设其为m阶 马尔可夫信源,用其m阶信息熵近似;再进一步假设为一阶 马尔可夫信源,用其一阶信息熵来近似;最简化的信源是 离散无记忆信源,其熵为 ;最后可以假定为等概的离 散无记忆信源,其熵 为了衡量信源符号间的依赖程度,我们把一个信源实际的信息熵与具有同样符号集的最大熵的比值称为熵的相 2.自然熵语言把英语看成离散无记忆信源 英语字母26个,加上一个空格,共27个符号。 英语信源的最大熵(等概率) =log27=4.76(比特/符号) 英语字母并非等概率出现,字母之间有严格的依赖关系。表2.2.2是对27个符号出现的概率统计结果。 表2.2.2 27 个英语符号出现的概率 符号 概率 符号 概率 符号 概率 空格 0.2 按表2.2.2的概率分布,随机地选择英语字母并排列起来,得到一个输出序列: AI_NGAE_ITE_NNR_ASAEV_OTE_BAINTHA_HYROO_PORE_SETRYGAIETRWCO_EHDUARU_EUEU_C_FT_NSREM_DIY_EESE_F_O_SRIS_ R_UNNASHOR„ 这个序列看起来有点像英语,但不是。实际英语的某个字母出现后,后面的字母并非完全随机出现,而是满足一定 关系的条件概率分布。例如T后面出现H,R的可能性较大, 出现J,K,M,N的可能性极小,而根本不会出现Q,F,X。即英 语字母之间有强烈的依赖性。上述序列仅考虑了字母出现 的概率,忽略了依赖关系。 把英语看成马尔可夫信源为了进一步逼近实际情况,可把英语信源近似看做一阶, 二阶,„阶马尔可夫信源,它们的熵为 H2=3.32(比特/符号) H3=3.1(比特/符号) 若把英语信源近似成二阶马尔可夫信源,可得到某个输出 序列: IANKS_CAN_OU_ANG_RLER_THTTED_OF_TO_SHOR_OF_TO_HAVEM EM_A_I_MAND_AND_BUT_WHISS_ITABLY_THERVEREER„ 这个序列中被空格分开的两字母或三字母,组成的大都是有意 义的英语单词,而四个以上字母组成的“单词”,很难从英语 词典中查到。因为该序列仅考虑了3个以下字母之间的依赖关系。 实际英语字母之间的关系延伸到更多的符号,单词之间也有依 赖关系。 有依赖关系的字母数越多,即马尔可夫信源的阶数越高,输出 的序列就越接近于实际情况。当依赖关系延伸到无穷远时,信 源输出的就是真正的英语,此时可求出马尔可夫的极限熵 =1.4(比特/符号)。(1)对于英文字母 写英语文章时,71%是由语言结构定好的,只有29%是写文字的人可以自由选择的。100页的书,大约只传输29页就可以了 ,其余71页可以压缩掉。信息的剩余度表示信源可压缩的程 剩余度大的消息抗干扰能力强。能通过前后字之间的关联纠正错误。 后面我们讨论信源编码和信道编码时会涉及到,信源编 码就是通过减小或消除信源的剩余度,提高通信的有效 性;而信道编码是通过增加信源的剩余度,提高通信的 抗干扰能力,即提高通信的可靠性 *2.9 意义信息和加权熵 设信源 指定一个非负实数这组实数称为事件的权重。 加权熵: 随机变量X,其概率分布为 及其对应的权为

  马尔可夫链 马尔可夫 隐马尔可夫模型 马尔可夫决策过程 马尔可夫随机场 马尔可夫模型 马尔可夫过程 马尔可夫链模型 马尔可夫分析法 马尔可夫性


上一篇:第三章连续信源及信源熵ppt    下一篇:第三章信源熵ppt