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

第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.2 随机过程的信息度量随机过程的信息度量例例1：一个马尔可夫过程的基本符号为0，1，2，这3个符号等概率出现，开且具有相同的转移概率。请画出一阶马尔可夫过程的状态图，并求稳定状态下的一阶马尔可夫信源熵和信源剩余度.解：一阶马尔可夫过程 的状态转移图第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.2 随机过程的信息度量随机过程的信息度量设状态的平稳分布为 ，根据一阶马尔科夫信源熵：信源冗余度：第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.2 随机过程的信息度量随机过程的信息度量例例2：一阶马尔可夫信源的状态转移图如下图所示，信源 的符号集为 (1)求平稳后的信源的概率分布；(2)求信源熵 解：设状态的平稳分布为根据：第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.2 随机过程的信息度量随机过程的信息度量（2）第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.3 渐近等分性质渐近等分性质渐近等分性渐近等分性（AEP）弱典型序列弱典型序列弱典型序列的数值实例弱典型序列的数值实例第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.3 渐近等分性质渐近等分性质渐近等分性渐近等分性（AEP）弱典型序列弱典型序列弱典型序列的数值实例弱典型序列的数值实例第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.3 渐近等分性质渐近等分性质 是随机变量长序列的一种重要特性，是编码定理的理论基础，简称AEP。当随机变量的序列足够长时,其中一部分序列就显现出一种典型的性质：这些序列中各个符号的出现频数非常接近于各自的出现概率，而这些序列的概率则趋近于相等，且它们的和非常接近于1,这些序列就称为典型序列。其余的非典型序列的出现概率之和接近于零。序列的长度越长，典型序列的总概率越接近于1,它的各个序列的出现概率越趋于相等。渐近等分性即因此得名。第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.3 渐近等分性质渐近等分性质 渐近等分性有许多不同的具体形式，但一般地可以表述如下：若X是一个符号表，共有M个不同的符号x1,x2，,xM,它们的出现概率分别是p1，p2，pM。对X进行N次独立的选择,于是得到一个长度为N的符号序列;总共有MN个长度为N的不同序列。可以证明,对于给定的两个任意小的数0和0，一定可以找到一个正整数N0(它是X,和的某种函数)，使所有长度为NN0的序列可划分为以下两组：第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.3 渐近等分性质渐近等分性质第一组包含WMN个序列，其中各个序列都具有几乎相等的出现概率p，且有?实际上,当N充分大时,W=2NH,式中H是X的符号熵。第二组包含其余的MN-W个序列，它们的出现概率之和小于。显然第一组包含的是典型序列,第二组包含的是非典型序列。在各个符号的概率不相等的情况下，序列长度N越大,则W与MN的差别越大,而pW与1的差别越小，-logp/N与H的差别也越小。第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.3 渐近等分性质渐近等分性质渐近等分性的意义在于：对于任意取有限个值的随机变量X,当用N次独立选择的方法来形成编码序列时,只要N 取得足够大，就可以只考虑其中W个典型序列，而其余所有的非典型序列均可以忽略。第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.3 渐近等分性质渐近等分性质信息论中，渐近等分性是弱大数定理的直接推论.大数定理指出：对于统计独立、有等同分布的随机变量 ，只要n足够大，就接近数学期望渐近等分性指，对于统计独立、有等同分布的随机变量 ，只要n足够大，联合概率就接近信源熵第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.3 渐近等分性质渐近等分性质定理定理2.3.1 对无记忆信源 有以概率收敛到 .其中，Xi是统计独立，且服从分布p(x);视为一个扩展信源视为一个扩展信源简证：由于相互独立随机变量的函数也是随机变量及弱大数定理第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.3 渐近等分性质渐近等分性质渐近等分性渐近等分性（AEP）弱典型序列弱典型序列弱典型序列的数值实例弱典型序列的数值实例第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.3 渐近等分性质渐近等分性质定义定义2.3.1 称满足性质的n长序列为弱典型序列，或 -典型序列.记所有集为定义式等价于：第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.3 渐近等分性质渐近等分性质利用AEP可得到弱典型序列的如下性质：定理定理2.3.2 ，当n足够大时，有 1）（2）第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.3 渐近等分性质渐近等分性质渐近等分性渐近等分性（AEP）弱典型序列弱典型序列弱典型序列的数值实例弱典型序列的数值实例第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.3 渐近等分性质渐近等分性质第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.3 渐近等分性质渐近等分性质第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.2-2.3作业：作业：P42:3),4)-(b)第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.3 渐近等分性质渐近等分性质定义定义2.3.1 称满足性质的n长序列为弱典型序列，或 -典型序列.记所有集为定义式等价于：第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.3 渐近等分性质渐近等分性质利用AEP可得到弱典型序列的如下性质：定理定理2.3.2 ，当n足够大时，有 （1）（2）第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.3 渐近等分性质渐近等分性质弱典型序列集占n长序列Xn总数的比例：弱典型序列只占全体序列的一小部分！第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.4 渐近等分性在数据压缩中的应用渐近等分性在数据压缩中的应用第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.4 渐近等分性在数据压缩中的应用渐近等分性在数据压缩中的应用任何一个离散随机序列信源当序列长度n时,信源序列会产生两极分化：大概率事件集合 与小概率事件集合 .由此可见，信源编码只需对信源中由此可见，信源编码只需对信源中少数少数落入落入典型典型大概率事件的集合大概率事件的集合的符号进行编码即可；而对的符号进行编码即可；而对大多数大多数属于非典型小概率事件集合中的属于非典型小概率事件集合中的信源符号无需编码信源符号无需编码.码字总数减少码字总数减少，所需码长可以减少第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.4 渐近等分性在数据压缩中的应用渐近等分性在数据压缩中的应用记上述编码的误差概率为：记上述编码的误差概率为：由弱渐进等分性由弱渐进等分性该编码的码率满足：该编码的码率满足：误差概率：误差概率：当n充分大时，码码率接近率接近H(X)！误差概率误差概率趋于趋于0.信源编码信源编码正定理正定理第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 在该码率的任意邻域内存在符合某种条件的编码器与解码器 2.5 Shannon-McMillan-Breiman定理 在通信的数学理论中，Shannon首先运用典型序列的思想给出了离散无记忆信源下的可达码率区间；而后，Shannon又进一步推广到有限状态的遍历Markov信源；第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.5 Shannon-McMillan-Breiman定理 1953年，McMillan将统计力学中的术语渐近等分性质（AEP）引入信息论，并且还进一步运用概率论中的遍历定理推广了Shannon关于典型序列的结果，得出了每一个有限字符集的平稳遍历过程都满足AEP性质的结论.一般的教科书通常将之称为Shannon-McMillan定理；运用Shannon-McMillan定理，平稳遍历过程的可达码率区问题就可以非常容易地运用AEP性质解决.第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.5 Shannon-McMillan-Breiman定理 然而，对于非平稳或者非遍历的信源，并不一定满足Shannon-McMillan定理，所以需要更一般的理论来研究这些信源.1993年，Breiman提出了信息谱的方法，运用该方法可以计算任意一般信源的可达码率.从而形成了Shannon-McMillan-Breiman定理定理.第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.5 Shannon-McMillan-Breiman定理 定理定理2.53（强渐近等分性）（强渐近等分性）设设X1，X2为为取取值值于于有有限限字字母母集集的的平平稳稳遍遍历历马马氏氏链链，则则第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.5 Shannon-McMillan-Breiman定理 证明：设马氏链的一步转移概率矩阵为 P=(pij)，其pij=P(Xn+1=j|Xn=i)马氏链的初始分布服从平稳分布PrX1=i=(i),则 H(Xn+1|X1,Xn)=H(Xn+1|Xn)=H(X2|X1)=-(i)pij log pij;第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.5 ShannonMcMillan-Breiman定理 -logPr(X1,Xn)/n =-log(X1)Pr(X2|X1)Pr(Xn|Xn-1)/n =(-log Pr(Xi+1|Xi)/n-log(X1)/n;记Wi=-log Pr(Xi+1|Xi)；由于马氏链是平稳遍历的，得 lim-logPr(X1,Xn)/n =lim-(n-1)/nWi/(n-1)-log(X1)/n =EW1=H(X2|X1).第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.5 Shannon-McMillan-Breiman定理 定理定理2.5.3（强渐近等分性）（强渐近等分性）设设X1，X2为为取取值值于于有有限限字字母母集集的的平平稳稳遍遍历历马马氏氏链链，则则定理定理2.5.1 设设X1，X2为独立同分布为独立同分布p(x)随机过程，则随机过程，则第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.5 Shannon-McMillan-Breiman定理 定理定理2.5.3（强渐近等分性）（强渐近等分性）设设X1，X2为取值于有限字母集为取值于有限字母集的平稳遍历马氏链的平稳遍历马氏链,则则定理定理2.5.4（一般平稳遍历信源的一般平稳遍历信源的强渐近等分性）强渐近等分性）设设X1，X2为取值于有限字母集为取值于有限字母集的平稳遍历过程的平稳遍历过程，则则第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 2.5 Shannon-McMillan-Breiman定理 定理定理2.5.5（信源编码定理）（信源编码定理）设设X1，X2为为平稳遍历信源平稳遍历信源，熵率为，熵率为H(X).当当n充分大时，充分大时，使得使得第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 第第2章章 随机过程的信息度量随机过程的信息度量和渐近等分性和渐近等分性 2.1 信源和随机过程的基本概念信源和随机过程的基本概念 2.2随机过程的信息度量随机过程的信息度量 2.3 渐近等分性质渐近等分性质 2.4 渐近等分性质在数据压缩中的应用渐近等分性质在数据压缩中的应用 信源编码定理信源编码定理 2.5 Shannon-McMillan-Breiman定理定理 习题二习题二 第第2章章 随机过程的信息度量和渐近等分性随机过程的信息度量和渐近等分性 较新发展较新发展信息科学与信息论全信息理论信息-知识-智能的转化