信息论基础-随机过程的信息度量和渐近等分性.ppt

2.2 随机过程的信息度量 2.2 随机过程的信息度量 例1：一个马尔可夫过程的基本符号为0，1，2，这3个 符号等概率出现，开且具有相同的转移概率。 请画出一 阶马尔可夫过程的状态图，并求稳定状态下的一阶马尔 可夫信源熵和信源剩余度. 解：一阶马尔可夫过程 的状态转移图 2.2 随机过程的信息度量 设状态的平稳分布为 ，根据 2.2 随机过程的信息度量 例2：一阶马尔可夫信源的状态转移图如下图所示，信源 的符号集为 (1)求平稳后的信源的概率分布； (2)求信源熵 2.2 随机过程的信息度量 2.3 渐近等分性质 2.3 渐近等分性质 2.3 渐近等分性质 是随机变量长序列的一种重要特性，是编码定理的理论基础， 简称AEP。 当随机变量的序列足够长时,其中一部分序列就显现出一种典型的 性质：这些序列中各个符号的出现频数非常接近于各自的 出现概率，而这些序列的概率则趋近于相等，且它们的 和非常接近于1,这些序列就称为典型序列。 其余的非典型序列的出现概率之和接近于零。序列的 长度越长，典型序列的总概率越接近于1,它的各个序列的 出现概率越趋于相等。渐近等分性即因此得名。 2.3 渐近等分性质 渐近等分性有许多不同的具体形式，但一般地可以表述如下： 若X是一个符号表，共有M个不同的符号x1,x2，…,xM ,它们的出现概率分别是p1，p2，…，pM 。对X进行N次独立的选择,于是得到一个长度为N的符号序列;总共有MN个长度为N的不同序列。可以证明,对于给定的两个任意小的数ε＞0和δ＞0，一定可以找到一个正整数N0(它是X,ε和δ的某种函数)，使所有长度为N≥N0的序列可划分为以下两组： 2.3 渐近等分性质 第一组包含Wε＜MN个序列，其中各个序列都具有几乎相 等的出现概率p，且有 ? 实际上,当N充分大时,Wε=2NH ,式中H是X的符号熵。第二 组包含其余的MN-Wε个序列，它们的出现概率之和小于 ε。显然第一组包含的是典型序列,第二组包含的是非典 型序列。在各个符号的概率不相等的情况下，序列长度N 越大,则Wε与MN的差别越大,而p·Wε与1的差别越小，- logp/N与H的差别也越小。 2.3 渐近等分性质 渐近等分性的意义在于： 对于任意取有限个值的随机变量X,当用N次独立选择 的方法来形成编码序列时,只要N 取得足够大，就可以只 考虑其中Wε个典型序列，而其余所有的非典型序列均可 以忽略。 2.3 渐近等分性质 信息论中，渐近等分性是弱大数定理的直接推论. 大数定理指出：对于统计独立、有等同分布的随机变量 ，只要n足够大， 就接近数学期望 渐近等分性指，对于统计独立、有等同分布的随机变量 ，只要n足够大，联合概率就接近信源熵 2.3 渐近等分性质 定理2.3.1 对无记忆信源 有 2.3 渐近等分性质 2.3 渐近等分性质 定义2.3.1 称满足性质 的n长序列为弱典型序列，或 -典型序列. 记所有集为 2.3 渐近等分性质 利用AEP可得到弱典型序列的如下性质： 定理2.3.2 ，当n足够大时，有 （1） （2） 2.3 渐近等分性质 2.3 渐近等分性质 2.3 渐近等分性质 2.2-2.3 作业： P42: 3), 4)-(b) 2.3 渐近等分性质 定义2.3.1 称满足性质 的n长序列为弱典型序列，或 -典型序列. 记所有集为 2.3 渐近等分性质 利用AEP可得到弱典型序列的如下性质： 定理2.3.2 ，当n足够大时，有 （1） （2） 2.3 渐近等分性质 弱典型序列集占n长序列Xn总数的比例： 2.4 渐近等分性在数据压缩中的应用 2.4 渐近等分性在数据压缩中的应用 任何一个离散随机序列信源当序列长度n→∝时,信源序列 会产生两极分化： 大概率事件集合 与小概率事件集合 . 由此可见，信源编码只需对信源中少数落入典型大概率事件的集合 的符号进行编码即可；而对大多数属于非典型小概率事件集合中的 信源符号无需编码. 2.4 渐近等分性在数据压缩中的应用 记上述编码的误差概率为： 由弱渐进等分性 该编码的码率满足： 误差概率： 2.5 Shannon-McMillan-Breiman定理 在《通信的数学理