信息论基础教学课件ppt-离散信源.ppt

1、第第3章章 离散离散信源信源1本章主要内容本章主要内容 3.13.1离散信源的分类与数学模型离散信源的分类与数学模型3.1.1 离散信源的分类3.1.2 离散无记忆信源数学模型3.1.3 离散有记忆信源数学模型3.1.4 离散平稳信源数学模型 3.2 3.2 离散无记忆信源的扩展离散无记忆信源的扩展3.2.1 等长消息扩展3.2.2 变长消息扩展2本章主要内容本章主要内容 3.3 3.3 离散平稳信源的熵离散平稳信源的熵 3.3.1 单符号信源的熵 3.3.2 等长无记忆扩展源的熵 3.3.3 变长无记忆扩展源的熵 3.3.4 平稳有记忆信源的熵 3.4 3.4 有限状态马尔可夫链有限状态马尔

2、可夫链 3.4.1马氏链的基本概念 3.4.2 齐次马氏链 3.4.3 马氏链状态分类 3.4.4 马氏链的平稳分布3本章主要内容本章主要内容 3.5 3.5 马尔可夫信源马尔可夫信源 3.5.1 马氏源的基本概念 3.5.2 马氏源的产生模型 3.5.3 马氏链N次扩展源熵的计算 3.5.4 马氏源符号熵的计算3.6 3.6 信源的相关性与剩余度信源的相关性与剩余度 3.6.1 信源的相关性 3.6.2 信源的剩余度 3.6.3 文本信源43.1 3.1 离散信源的分类与数学模型离散信源的分类与数学模型3.1.1 离散信源的分类3.1.2 离散信源的数学模型53.1.1 3.1.1 离散信源

3、的分类离散信源的分类6根据信源符号取值：连续/离散根据输入符号间的依赖关系：无记忆/有记忆无记忆无记忆/有记忆有记忆根据符号集的取值范围：有限/无限根据信源统计特性：平稳/非平稳3.1.2 3.1.2 离散无记忆信源的数学模型离散无记忆信源的数学模型niiinnapapapapaaPX1111)(,0)()()(单符号离散无记忆信源的数学模型7A=a1，an 信源的符号集n 符号集的大小ai 随机变量的取值p(ai)X=ai的概率单符号离散无记忆信源单符号离散无记忆信源qpPX10n例3.1 一个二元无记忆信源，符号集 A=0,1,p为X=0的概率,q为X=1的概率，q=1-p；写出信源的模型

4、。83.1.2 3.1.2 离散无记忆信源的数学模型离散无记忆信源的数学模型11()()NMMXppPNX XMNA1n1aa A9的符号集3.1.2 3.1.2 离散无记忆信源的数学模型离散无记忆信源的数学模型 10121()(,)()NNiipp x xxp xx3.1.3 3.1.3 离散有记忆信源的数学模型离散有记忆信源的数学模型11可以从有限状态机的概念出发定义马尔可夫信源。123.1.4 3.1.4 离散离散平稳信源数学模型平稳信源数学模型,21naaaA,2,1,iXxjjhiiiNN及,11),(),(22112211NNNNjhijhijhijijijiaxaxaxpaxax

5、axpix则称信源为离散平稳信源，所产生的序列为平稳序列。Page 133.1.4 3.1.4 离散离散平稳信源数学模型平稳信源数学模型平稳序列的统计特性与时间的推移无关),(),(2121hihihiiiiNNxxxpxxxp),(),(11NjjjNiiixxxpxxxp 143.1.4 3.1.4 离散平稳信源数学模型离散平稳信源数学模型n例3.2一平稳信源X的符号集A=0，1，产生随机序列xn,其中P(x1=0)=p,求P(xn=1)（n 1）的概率。解平稳性pxPn)0(pxPn1)1(153.1.4 3.1.4 离散平稳信源数学模型离散平稳信源数学模型n例3.2续对同一信源，若P(

6、x1=0，x2=1)=b，求P(x4=1/x3=0)。解：平稳性bxxPxxP)1,0()1,0(2143pbxPxxPxxP/)0(/)1,0()0/1(34334pbxPxxPxxP/)0(/)1,0()0/1(12112而3.2 3.2 离散无记忆信源的扩展离散无记忆信源的扩展3.2.1 等长消息扩展3.2.2 变长消息扩展163.2.1 3.2.1 等长消息扩展等长消息扩展 信源X的N次扩展源：设信源为X，由X构成的N维随机矢量集合 信源与其扩展源的关系：)(,21同分布与XXXXXXiNNNNXXXX,21X173.2.1 3.2.1 等长消息扩展等长消息扩展解)()()()()11

7、()10()01()00()(432143212pppppX243221)1()(),()1()(,)(pppppppp11,10,01,00:212符号集二次扩展源XXX:2的模型X二元信源X的符号集为 0,1:2各符号的概率为X求 例3.1 中信源的二次扩展模型。例3.3183.2.2 3.2.2 变长消息扩展变长消息扩展构造消息图构造消息图设离散无记忆信源X，符号集为A，n=|A|分裂终止时每片树叶表示的是从根节点到该叶路径上的信源消息，叶的概率就是消息的概率，叶的阶数就是消息长度。如果消息构成满树，消息概率也满足归一化条件，这时消息集中的消息可视为某个信源的输出。这个信源称为信源X的变

8、长扩展源193.2.2 3.2.2 变长消息扩展变长消息扩展如果消息树是全树就对应着信源的等长扩展。所以等长扩展可以视为变长扩展的特例。203.2.2 3.2.2 变长消息扩展变长消息扩展什么消息集可以作为某信源的扩展？适定消息集适定消息集概率满足归一化条件概率满足归一化条件完备消息集完备消息集异前置异前置(0)pp(10)(1)ppp2(11)(1)pp设例3.1中信源的消息集为A*=0,10,11，求以此消息集进行变长扩展的信源符号的概率。解 消息集A*中各个符号概率为很明显，上面消息的概率满足归一化条件，并且是适定消息集。例例3.43.4 21平稳有记忆信源的熵无记忆信源的熵3.3 3.

9、3 离散平稳信源的熵离散平稳信源的熵220.5 11)(pH0 p 3.3.1 3.3.1 单符号信源的熵单符号信源的熵H(p)pppH1log)(0)1(1)(log)(ppepH 23（1）具有熵的一切性质（2）对p的导函数为（3）p=0.5时,H(p)达到最大值1bit（4）H(p)是p的上凸函数离散无记忆信源X的N次扩展源的熵等于信源X熵的N倍，即3.3.23.3.2等长无记忆扩展源的熵等长无记忆扩展源的熵)()(1niiNXHXH证明：熵的可加性无记忆信源互相独立且分布相同iX)(XNH24)()(XNHXHNPage 25n例3.6 给定离散无记忆信源模型：求其二次扩展源熵。3.3

10、.23.3.2等长无记忆扩展源的熵等长无记忆扩展源的熵4/14/12/1321aaaPX解：)(2XH2)41log41(21log2125.12)(2XH3/bit扩展符号3.3.33.3.3变长无记忆扩展源的熵变长无记忆扩展源的熵离散无记忆信源的变长扩展源X*的熵为消息平均长度 与信源熵的乘积，即*()()()H XE L H X等长扩展变长扩展特例*()()()H XE L H X)()(XHNXHN特例263.3.33.3.3变长无记忆扩展源的熵变长无记忆扩展源的熵n例3.7有一个二元无记忆信源X，发“0”的概率为p，对信源符号按下表进行分组得到一个新信源，符号集为Sn=s1,s2,s

11、3,sm+1，信源符号分组与信息信源符号的对应关系如下表：信源消息 101001 00001（m-1个“0”，1个“1”）0000（m个“0”）新信源符号 s1s2 s3 sn sm+1求新信源的熵Hn。273.3.33.3.3变长无记忆扩展源的熵变长无记忆扩展源的熵消息的平均长度：1()1(1)/(1)mmE Lpppp 新信源的熵Hn：()()()(1)/(1)mmHE L H pH ppp其中()log(1)log(1)H ppppp 当m时lim(1)/(1)1/(1)mmmHppp283.3.43.3.4平稳有记忆信源的熵平稳有记忆信源的熵。，XHNXHN成立仅当无记忆信源时等式)(

12、)(1)(1)(1)(1NNNXXHNXHNXH根据平稳性和熵的不增原理对于X的N次扩展源,定义平均符号熵为29信源X的极限符号熵：)(1lim)(1lim)(1NNNNXXHNXHNXH简称：符号熵或熵率3.3.43.3.4平稳有记忆信源的熵平稳有记忆信源的熵30 对任意离散平稳信源，若 不随N而增加 不随N而增加 存在，且:31)(1XH)/(11NNXXXH)/()(11NNNXXXHXH)(XHN)(XH)/(lim)(11NNNXXXHXH说明：有记忆信源的符号熵也可通过计算极限条件熵得到3.3.43.3.4平稳有记忆信源的熵平稳有记忆信源的熵定理3.2（1）不随N而增加)/()/(

13、)/(112111NNNNNNXXXHXXXHXXXH这说明对于平稳信源，条件越多，条件熵越不增加3.3.43.3.4平稳有记忆信源的熵平稳有记忆信源的熵32).|(11NNXXXH（2）11()(/)NNNHXH XXX只要证明N 个 的和不小于)(XHN)/(11NNXXXHN)/()/()/()()()(11111211NNNNNNXXXHNXXXHXXHXHXXHXNH)/()(11NNNXXXHXH平均符号熵不小于条件熵3.3.43.3.4平稳有记忆信源的熵平稳有记忆信源的熵33（3）不随N而增加()NHX)()()1()/()()1()(1111XHXHNXXXHXHNXHNNNN

14、NNN)()(1XHXHNN)(XNHN)/()(1111NNNXXXHXXH由于根据平均符号熵的定义和（2）的结果，有平均符号熵不随序列的长度而增加3.3.43.3.4平稳有记忆信源的熵平稳有记忆信源的熵34（4）存在，且11()lim(/)NNNHXH XXX()HX)()()(011XHXHXHNN)()(lim01XHXHNN()HX即存在()11)()()NjNNNjNj HXH XXXX计（算通过以上证明可得)/()/()(111111jNjNNNNXXXHXXXHXXH3.3.43.3.4平稳有记忆信源的熵平稳有记忆信源的熵35（4）存在，且11()lim(/)NNNHXH XX

15、X()HX1111(/)(/)NjNjNNH XXXH XXX)/()1()()()1111)(NNNjNXXXHjXXHXHjN（)/(1)(1)(1111)(NNNjNXXXHjNjXXHjNXH利用(1)的结果与平稳性，有3.3.43.3.4平稳有记忆信源的熵平稳有记忆信源的熵36（4）存在，且11()lim(/)NNNHXH XXX()HX先令 ，后令 ，得 另外，由（2）的结果，当 时,有所以 证毕。jN)/(lim)(11NNNXXXHXH)/(lim)(11NNNXXXHXHN)/(lim)(11NNNXXXHXH3.3.43.3.4平稳有记忆信源的熵平稳有记忆信源的熵37定理3

16、.3的注释 3.3.43.3.4平稳有记忆信源的熵平稳有记忆信源的熵（1）信源熵率等于最小的平均符号熵；（2）该定理提供了通过计算极限条件熵计算平稳信源 熵率的方法（3）当信源记忆长度有限时，计算极限条件熵通常 要比计算极限平均符号熵容易得多。383.4 3.4 有限状态马尔科夫链有限状态马尔科夫链39内容内容马氏链的基本概念齐次马氏链马氏链状态分类马氏链的平稳分布 ：状态 构成的集合：状态集合定义3.4.1 3.4.1 马氏链的基本概念马氏链的基本概念0,nxn1,nnxx 随机变量 ：马氏链在n时刻的状态nxJ,1 J,1 40随机变量 对 的依赖只通过 实现；在 给定条件下，与 无关；在

17、 给定条件下，与 是条件独立的；在 给定条件下，与 是条件独立的。对于一阶马氏链，下述说法等价：上述等价说法可以推广到多阶马氏链。nx413.4.1 3.4.1 马氏链的基本概念马氏链的基本概念1nxnx23,nnxx1nxnx23,nnxxn kxnx12,n kn kxx 1nx1,nnxx3.4.1 3.4.1 马氏链的基本概念马氏链的基本概念42一阶马氏链的当前状态只与前一个状态有关m阶马氏链的当前状态只与前m个状态有关马氏链是时间离散，状态也离散的随机过程状态集合为有限集有限状态马氏链状态集合为无限集无穷状态马氏链对于离散时刻n、l，相应的状态转移概率可表示为：表示从时刻n的i状态转

18、移到时刻l 的j状态的概率l-n表示转移的步数 是经 步转移的概率3.4.1 3.4.1 马氏链的基本概念马氏链的基本概念描述马氏链的最重要的参数：状态转移概率(/)(,)lnijp sj sipn l43(,)ijpn l()ln ln3.4.1 3.4.1 马氏链的基本概念马氏链的基本概念转移概率的主要性质转移概率的主要性质0(,)1,；ijpn li j(,)1ijjpn l；一步转移概率1(,1)(/)()ijnnijpn np xj xipn,其中 为起始时刻ni j443.4.1 3.4.1 马氏链的基本概念马氏链的基本概念转移概率的主要性质转移概率的主要性质K步转移概率()()(

19、/)kijn knpnp xj xi0步转移概率 jijipij01)0(45系统在任何时刻必处于中某一状态3.4.2 3.4.2 齐次马氏链（齐次马氏链（1 1）若马氏链转移概率与起始时刻无关，即对任意n,有则称为齐次马氏链。对齐次马氏链，仍然有1()(/)ijnnijpnp xj xip齐次马氏链K步转移概率也与起始时刻无关，写成)(kijp46jijijpp1,03.4.2 3.4.2 齐次马氏链（齐次马氏链（2 2）47表示方法表示方法转移概率矩阵网格图 每时刻的网格节点与马氏链的状态一一对应状态转移图 状态转移图与矩阵有一一对应关系111212122212JJijJJJJpppppp

20、ppppP 3.4.2 3.4.2 齐次马氏链（齐次马氏链（3 3）例3.8 一个矩阵，验证此矩阵对应一个齐次马氏链的转移概率矩阵并确定此马氏链的状态数1/3 1/3 1/31/41/21/41/41/41/2P解：元素非负状态数=3每行和为1齐次马氏链转移概率矩阵3.4.2 3.4.2 齐次马氏链（齐次马氏链（4 4）例3.8 续画出此马氏链的网格图。解493.4.2 3.4.2 齐次马氏链（齐次马氏链（5 5）例3.8 续画出此马氏链的状态转移图解：132131413141414131212503.4.2 3.4.2 齐次马氏链（齐次马氏链（6 6）例3.8 续求从状态3到状态2的2步转移

21、概率解：S21/41/3S2S3S3S11/21/21/41/451解：3.4.2 3.4.2 齐次马氏链（齐次马氏链（6 6）1)计算从m时刻从s3经m+1时刻某状态sk 到m+2时刻s2的转移概率2)对1）中计算的经m+1时刻的所有状态 sk（k=1,2,3）概率相加，得到所求 结果。计算得下面分两步来计算:31412121413141/322sxsxpmm52Kolmogorov-ChapmanKolmogorov-Chapman方程方程(1)(1)53由此例可以看出:1、计算从状态i到状态j的2步转移概率可通过下式:2 是 的第(i,j)个元素3 是 的m次幂 的第(i,j)个元素4k

22、kjikijppp)2()2(ijp2P)(mijpPmP()()()mnmnmnmnijikkjkpppPPPKolmogorov-ChapmanKolmogorov-Chapman方程方程(2)(2)()()()(|)(,|)(|)(|,)(|)(|)m nijm n llm n ll mlkl mlm n lll mkl mlm n ll mkmnikkjkpp xj xip xj xk xip xk xi p xj xi xkp xk xi p xj xkpp 提供了计算多步转移概率的方法54Kolmogorov-ChapmanKolmogorov-Chapman方程方程(3)(3)5

23、)设马氏链的初始状态概率分布为 其中J为状态数，经k步转移后的状态概率分布为 ，则有:()(0)()()()()kTTkmTk mppPpP()()()()12(,)kkkkTJpppp(0)(0)(0)(0)12(,)TJpppp 一个齐次马氏链，当初始状态概率分布给定后，可计算转移后任何时刻的状态概率分布。55Kolmogorov-ChapmanKolmogorov-Chapman方程方程(4)(4)例3.9设例3.8中马氏链的初始状态的概率分布为1/2、1/4、1/4，分别求1步转移后和2步转移后的状态的概率分布。56解：Kolmogorov-ChapmanKolmogorov-Chap

24、man方程方程(4)(4)(1)(0)1/31/31/31/21/41/41/41/21/41/41/41/2ppP48/1748/1724/7(2)(0)25/1813/3613/361/21/41/413/4819/481/313/481/319/48ppP576/209576/209288/79573.4.3 3.4.3 马氏链状态分类马氏链状态分类(1)(1)若对某一k1，有 ，则称状态j可由状态i到达，记为 ij()0kijp如果ij，且 ji，则称状态i与状态j可互通，记为ij定义每个状态都与该状态本身互通，即互通关系满足自反性互通关系还满足对称性和传递性58如果状态i是经过有限步

25、后迟早要返回的状态；不是常返态。即存在某状态j经过若干步以后总能达到某一其它状态，但不能从其它状态返回。在一个常返类中，表示从状态i出发经过k步首次返回到i状态的概率。设 为正整数集 的最大公约数。若 ，则称为周期的，若 ，则称为非周期的或称为遍历的。3.4.3 3.4.3 马氏链状态分类马氏链状态分类(2)(2)()0kiipid():1,0kiik kp1id 1id 例3.103.4.3 3.4.3 马氏链状态分类马氏链状态分类(3)(3)按互通性将状态分成若干类（子集）解：3.4.3 3.4.3 马氏链状态分类马氏链状态分类(4)(4)11C22C33,4,5,6,7C48,9,10C

26、常返态过渡态周期的非周期():1,0kiikkp最大公约数id1id1id613.4.3 3.4.3 马氏链状态分类马氏链状态分类(4)(4)对任何马氏链（有限或无限可数状态），同一类中所有状态都有相同周期。62非周期的常返态称为遍历态 3.4.4 3.4.4 马氏链的平稳分布马氏链的平稳分布(1)(1)若对任意整数m,n,马氏链的状态分布满足 则称 为平稳分布，或稳态分布。其中，为平稳分布列矢量inmixPixP)()(i12,TJ63（3.25）111其中,为 维列矢量,为平稳分布列矢量TJe(,),3.4.4 3.4.4 马氏链的平稳分布马氏链的平稳分布(2)(2)(0)(0)(0)(0

27、)12(,),TJpppp0(),nnp平稳马氏链 如果一个遍历有限状态马氏链的转移概率矩阵为 P 那么limkTkPelimkTkP因此，是一个每行都相同,都等于的矩阵。64定理3.53.4.4 3.4.4 马氏链的平稳分布马氏链的平稳分布(3)(3)6500()()()lim()lim()()kTTkTTTkkpppPe对于遍历马氏链，无论初始分布如何，当转移步数足够大时，状态概率分布总是趋于稳定值（稳态分布），与初始状态概率分布无关。k时刻：初始概率：平稳分布：()()()()12(,)kkkkTJpppp0()p3.4.4 3.4.4 马氏链的平稳分布马氏链的平稳分布(4)(4)对于有

28、限状态马氏链，稳态分布恒存在；如果马氏链中仅存在一个常返类，则方程(3.31)的解是唯一的；如果存在r个常返类，则具有r个线性独立的矢量解；如果马氏链中仅存在一个常返类而且是非周期的（即遍历的），则(3.32)式成立；如果有多个常返类，但都是非周期的，则Pn 也收敛，但矩阵的每行可能不同；如果马氏链具有一个或多个周期常返类，则 Pn 不收敛66例3.113.4.4 3.4.4 马氏链的平稳分布马氏链的平稳分布(5)(5)0011 21 31 61 21 20/P一马氏链的转移概率矩阵如下，问此马氏链是否具有遍历性并求平稳分布和 的值。12312131212161limkkP解：3.4.4 3.

29、4.4 马氏链的平稳分布马氏链的平稳分布(6)(6)123123001 1/21/31/61/21/20132121/87/23/13211 32 78 211 32 78 211 32 78 21/lim/kkP68例3.123.4.4 3.4.4 马氏链的平稳分布马氏链的平稳分布(7)(7)一马氏链的状态转移矩阵为确定它的n次幂是否收敛并求其平稳分布0110P3.4.4 3.4.4 马氏链的平稳分布马氏链的平稳分布(7)(7)1212121解：该马氏链的状态转移图为：所以马氏链是一个周期常返类，周期=2。由于另外，马氏链是有限状态的，因此存在唯一的平稳分布。11122kPI21kPP011

30、0212170 1.1.2.2.马氏源的产生模型马氏源的产生模型 3.3.马氏源马氏源N N次扩展源熵的计算次扩展源熵的计算 4.4.马氏源符号熵的计算马氏源符号熵的计算3.5 3.5 马尔可夫信源马尔可夫信源713.5 3.5 马尔可夫信源的基本概念（马尔可夫信源的基本概念（1 1）当前时刻输出符号的概率仅与当前时刻的信源状态有关下一时刻的信源状态由当前信源状态和当前输出符号唯一确定。马氏源：1111 ,/,0 ,kkkkklkkkksg sxp sj xa sisg sx72m m阶马氏链的处理方法阶马氏链的处理方法(2)(2)1)m阶马氏链的符号转移概率已给定:)/(11mmxxxp1i

31、nxAaa其中 取自2)做m长符号序列到信源状态的映射 x取遍 ，k=m,m+1,；状态 取自 ，为状态数；1（）k mkkxxs1nA a aks1,2,n mmn73m m阶马氏链的处理方法阶马氏链的处理方法(2)(2)3)符号转移概率转换成状态转移概率 其中 ,1(/)(/)kkkkp ssp xs1（）kmkkxxs4)得到马氏源模型：11（）kmkkxxs11121,21222,1,2,mmmmmmnnnnnnpppppppppP743.5.13.5.1马氏源的基本概念马氏源的基本概念(3)(3)给定二阶马氏源符号集A=0，1，转移概率分别为：p(0/00)=p(1/11)=0.8，

32、p(1/00)=P(0/11)=0.2，p(0/01)=p(0/10)=p(1/01)=p(1/10)=0.5确定该马氏源的状态，写出状态转移矩阵，画出信源的状态转移图。75解：3.5.13.5.1马氏源的基本概念马氏源的基本概念(4)(4)8.02.000005.05.05.05.000002.08.0P763.5.2 3.5.2 马氏源的产生模型马氏源的产生模型(1)(1)平稳转移概率的马氏源的产生模型773.3.2 3.3.2 离散平稳有记忆信源的熵离散平稳有记忆信源的熵(|)(,|)(|)(|,)()(|,)kkkkkkkkkkkkkuukkkkup xsp x usp usp xs

33、up up xus1,(|,)0,kkkkkkkkkxusp xusxus:(,)(|)()kkkkkkkuxf usp xsp u,()(,)(|)1()(,)kkkkkkkkkkkkxup uxf usp xsp uxf us当为二元信源、一一对应关系时，78例3.143.5.2 3.5.2 马氏源的产生模型马氏源的产生模型(3)(3)设独立随机列 ，随机序列 与 的关系为 其中 为模2加；问：（1）随机序列 是否为马氏链？（2）如果是马氏链，那么求状态转移概率并画状态转移概率图。nu(0)np up(1)np uq1pq nu nx12nnnnxuxx nx解：3.5.2 3.5.2 马

34、氏源的产生模型马氏源的产生模型(4)(4)序列 为有记忆序列，在n时刻的取值仅与n-1时刻与n-2时刻有关，而与以前的时间无关，因此 构成二阶马氏链。设 条件概率：nx nx12121:11(|)()()|,()nnnnnnnnnnnnnuxxxxnuxxxnnnp ssp up usxx21nnnsxx80解：3.5.2 3.5.2 马氏源的产生模型马氏源的产生模型(5)(5)所求条件概率：21212121(0|0,0)(1|0,1)(1|1,0)(0|1,1)(0)nnnnnnnnnnnnnp xxxp xxxp xxxp xxxp up21212121(1|0,0)(0|0,1)(0|1

35、,0)(1|1,1)(1)1nnnnnnnnnnnnnp xxxp xxxp xxxp xxxp up81解：3.5.2 3.5.2 马氏源的产生模型马氏源的产生模型(6)(6)因此，马氏链的状态转移概率图：82n例3.15 3.5.3 3.5.3 马氏链马氏链N N次扩展源的熵的计算次扩展源的熵的计算(1)(1)有一个二元马氏链X，符号集为0，1，其中符号转移概为 ，；计算该信源三次扩展源的所有符号的概率(0/0)0.8p(1/1)0.7p83解：3.5.3 3.5.3 马氏链马氏链N N次扩展源的熵的计算次扩展源的熵的计算(2)(2)首先求平稳分布01010.80.20.30.7pppp0

36、11pp013/5,2/5pp0(000)(0/0)(0/0)0.6 0.8 0.80.384pp pp84解：3.5.3 3.5.3 马氏链马氏链N N次扩展源的熵的计算次扩展源的熵的计算(3)(3)类似得到(001)0.60.80.20.096p(010)0.60.20.30.036p(011)0.60.20.70.084p(100)0.40.30.80.096p(101)0.40.30.20.024p(110)0.40.70.30.084p(111)0.40.70.70.196p853.5.3 3.5.3 马氏链马氏链N N次扩展源的熵的计算次扩展源的熵的计算(4)(4)做映射 其中k为

37、时间标号，j为状态序号。利用熵的可加性，将上式展开，并利用马氏性得11（）()，k0km kmkxxsj,N-m)/()/()()(21112121NmmNmmmNSSSSHSSHSHXXXH)/()/()(1121NNmmmSSHSSHSH111()(/)NmkkkmH SH SS1212111()()，其中，NmmNkkmkmkH X XXH SSSSXXX863.5.3 3.5.3 马氏链马氏链N N次扩展源的熵的计算（次扩展源的熵的计算（5 5）对于平稳马氏链，状态序列也是平稳的，状态条件熵也不随时间平移而改变。设状态平稳分布为12,mTn则上式变为：1211()()()(/)Nmkk

38、H X XXH SNm H SSh1()()()()mnTiiiHNmhHNm87如果起始状态概率为平稳分布,则3.5.3 3.5.3 马氏链马氏链N N次扩展源的熵的计算（次扩展源的熵的计算（6 6）N次扩展源的平均符号熵为:12()()()TNH X XXHNm h1211()()()()TNNHXH X XXHNmNN h883.5.4 3.5.4 马氏源符号熵的计算马氏源符号熵的计算(1)(1)计算方法1：()lim()TNNHXHX hm阶马氏源符号熵仅由平稳分布和状态转移概率矩阵所决定。89当信源从某一状态转移到另一状态时,输出符号唯一,则一个m阶马氏源的符号熵为:Page 90n

39、例3.13续 3.5.4 3.5.4 马氏源符号熵的计算马氏源符号熵的计算(2)(2)求信源的极限符号熵()TH X h2 5.0log5.05.0log5.0712 2.0log2.08.0log8.0145符号/801.0bit计算方法计算方法2 2（FSM马氏源）当信源从某一状态转移到另一个新状态时，存在多个信源序列对应一个状态。这样由状态转移概率矩阵不能确定信源的熵，而只能以状态条件下信源的输出符号的概率求信源的熵。给定当前信源状态条件下信源的输出符号熵为：Page 913.5.4 3.5.4 马氏源符号熵的计算马氏源符号熵的计算(3)(3)1(/)()log()nilillH Xsi

40、p ap a 1(,),其中,为信源符号集lnaAaaA3.5.4 3.5.4 马氏源符号熵的计算马氏源符号熵的计算(4)(4)在给定某特殊状态s1=j和以前的输出X1,X2,Xk-1条件下当前输出符号Xk的熵满足：11111(/,)(/)(/)JkkkiH Xsj XXp si sj H Xsi11111111(/,)()(/)(/)()(/)JJkkkjiJkiH XS XXp sj p si sj H Xsip si H Xsi对s1取平均923.5.4 3.5.4 马氏源符号熵的计算马氏源符号熵的计算(5)(5)对于平稳信源，状态概率与时间起点无关，所以利用平稳性及马氏性，有 1111

41、(/,)()(/)JkkiH XS XXp si H Xsi对于m阶平稳马氏链的符号熵为11lim(|)NNNHH XXX11(/)kkHH XXX1kH933.5.4 3.5.4 马氏源符号熵的计算马氏源符号熵的计算(6)(6)当 给定条件下，与以前的状态无关1kXX1kX11111(/)(/,)kkkkH XXXH XSXX)/()(1isXHispJiT h为状态平稳分布行矢量 h h的各分量由状态转移概率矩阵的每一行得出的条件熵943.5.4 3.5.4 马氏源符号熵的计算马氏源符号熵的计算(7)(7)()HX1(/)JiiH Xsi95定理3.7Page 963.5.4 3.5.4

42、马氏源符号熵的计算马氏源符号熵的计算(8)(8)（1）定理3.7给出了马氏源符号熵的计算方法：先求每个状态下的条件符号熵，再用状态的概率平均；（2）计算符号熵要用状态的平稳分布（3）单位为比特/符号；（4）比方法1更通用。233.6 3.6 信源的相关性与剩余度信源的相关性与剩余度3.6.1 信源的相关性3.6.2 文本信源1、信源的相关性就是信源符号间的依赖程度。由平稳性与熵的不增原理，有：可见，符号相关程度越大，熵越小，反之亦然。设信源有m个符号，那么对于不同情况可以分别计算信源的熵为3.6.1 3.6.1 信源的相关性信源的相关性0logHm11()HH X221(/)HH XX11(/

43、)nnnHH XXX11lim(/)nnnHH XXX983.6.2 3.6.2 信源剩余度（冗余度）信源剩余度（冗余度）信源的冗余度是指信源中”多余”(即可以被无损压缩掉的)成分所占的比例。信源效率：信源剩余度0HH01HH字母字母概率概率字母字母概率概率字母字母概率概率空格0.1859I0.0575R0.0484A0.0642J0.0008S0.0514B0.0127K0.0049T0.0796C0.0218L0.0321U0.0228D0.0317M0.0198V0.0083E0.1031N0.0574W0.0175F0.0208O0.0632X0.0013G0.0152P0.0152Y

44、0.0164H0.0467Q0.0008Z0.00053.6.3 3.6.3 文本信源文本信源3.6.3 3.6.3 文本信源文本信源对于实际英文字母组成的信源：=1.4H(比特/符号)0=0.29HH=1-0.29=0.713.6.3 3.6.3 文本信源文本信源汉字近似概率表类别汉字个数所占概率P每个汉字的概率Pi1400.50.5/140625-140=485（0.85-0.5）=0.350.35/4852400-625=1775（0.997-0.85）=0.1470.147/177576000.0030.003/76003.6.3 3.6.3 文本信源文本信源根据上表,可近似估算汉语信

45、源的信息熵：100001()logiiiH Xpp 9.773(比特/符号)0()10.264H XH 3.6.3 3.6.3 文本信源文本信源例3.17 根据上面的统计结果，分别计算汉语语与英语信源的效率和剩余度。对于汉语，信源效率：24.1/13.290.31剩余度：2210.69 对于英语，信源效率：121.4/log270.29剩余度：1110.7 1104()()NH XN H X1()()()NNHXH XH XN本本 章章 小小 结结1052、有记忆信源的符号熵：11()lim()lim(/)NNNNNHXH XH XXXN并且2()()()()NH XH XHXH X3马氏源的符号熵：()(/)jjHXH X sj其中1(/)()log()njijiiH Xsjp ap a TT=P4信源剩余度011HH 本本 章章 小小 结结109谢谢谢谢!107