《信息论与编码》课件1第6章.ppt

1、第第6章章 离散信源及其信息冗余离散信源及其信息冗余 第第6章章 离散信源及其信息冗余离散信源及其信息冗余 6.1 信源的描述与分类信源的描述与分类 6.2 离散无记忆信源的扩展信源离散无记忆信源的扩展信源 6.3 离散平稳信源离散平稳信源 6.4 马尔可夫信源马尔可夫信源 6.5 信源的信息冗余信源的信息冗余习题习题6第第6章章 离散信源及其信息冗余离散信源及其信息冗余 6.1 信源的描述与分类信源的描述与分类信源是发出信息的某种设备，可以是人、生物、机器或其他任何向外发出信息的事物。信源的输出称做消息。在人类的社会活动中，发出信息的信息源多种多样，其输出可以是离散的符号，如书信中的文字和字

2、母，也可以是连续的信号，如人发出的语声。第第6章章 离散信源及其信息冗余离散信源及其信息冗余 在信息理论的研究中，人们感兴趣的仅仅是载荷着信息的信源输出的符号或信号，而对于信源内部的结构和产生输出符号的控制过程一般不需要作深入了解。例如，人用语言方式向外界发出信息，便是由大脑指挥发声器官发出声音，以“音”的排列构成符号（消息）序列输出某种信息。研究这样的输出语音的信源（人）时，我们并不需要考虑人脑控制发声器官发出声音并构成某种“音”的排列的复杂过程，而只需要分析它的输出，即载荷着信息的符号（消息）。因此，在下面的讨论中，我们并不研究信源的内部结构和产生输出符号的复杂关系，只是将信源看做一个发出

3、某种符号（序列）的设备（见图6-1）。第第6章章 离散信源及其信息冗余离散信源及其信息冗余 图6-1 信源模型 第第6章章 离散信源及其信息冗余离散信源及其信息冗余 由于信息的基本属性是随机性，因此信源输出的符号或符号序列具有随机性，信源输出的符号需要使用随机变量、随机矢量或随机过程表示。所以，信源的描述与分类也仅仅考虑信源的外部特性，即依据信源的输出符号（序列）所具有的特点和统计关系加以描述和分类。第第6章章 离散信源及其信息冗余离散信源及其信息冗余 6.1.1 信源的描述信源的描述由于信源输出的消息载荷着信息，这种消息所具有的一个基本属性便是随机性，因此信源输出的符号或符号序列可以使用随机

4、变量、随机矢量或随机过程表示。由第2章的讨论我们知道，如果已知信源的消息集合（即样本空间或值域）和消息发生的概率分布，则可以使用由样本空间和它的概率分布所构成的概率空间来描述信源。设信源输出随机变量X的样本空间（值域）为R。若在此值域上随机变量X的概率分布为P，则此信源的概率空间为R,P或X,P。第第6章章 离散信源及其信息冗余离散信源及其信息冗余 6.1.2 信源的分类信源的分类信源的输出是随机变量，信源的描述是一个统计模型，那么对信源进行分类也应从信源的统计特性出发，即依据信源输出的消息在取值范围、概率分布及统计关系等方面的不同特点和性质，将信源划分为不同的类型。第第6章章 离散信源及其信

5、息冗余离散信源及其信息冗余 1 连续信源与离散信源连续信源与离散信源根据信源输出消息X的取值特点，可将信源划分为连续信源和离散信源。1）离散信源信源输出符号为离散随机变量的信源称为离散信源。设离散信源输出随机变量X的值域R为一离散集合R=a1,a2,an，其中，n可以是有限正数，也可以是可数的无限大正数。若已知R上每一消息发生的概率分布为P(a1),P(a2),P(an)第第6章章 离散信源及其信息冗余离散信源及其信息冗余 则离散信源X的概率空间为(6.1)其中,信源输出消息的概率 P(ai)（i=1,2,n）满足:1212,()()()nnaaaR PX Pp ap ap a1()0 1,2

6、,()1iniip ainp a第第6章章 离散信源及其信息冗余离散信源及其信息冗余 2)连续信源如果信源输出符号的种类是不可数的无限值，即信源输出随机变量X的取值为一个连续区间，那么这样的信源称为连续信源。假设随机变量X的取值是在一个连续区间(a,b)内，即XR，而R=(a,b)（当a,b+时，这个区间成为一个包含所有实数的集合）。如果R内X的概率密度分布为p(x)，则连续信源的概率空间为(,),()()a bX Pp xp xR第第6章章 离散信源及其信息冗余离散信源及其信息冗余 其中:p(x)0 xR且或3)混合信源若信源的一些符号取值于一个连续区间，而另一些符号取值于离散集合，则这样的

7、信源称为混合信源。()d1p xx R()d1bap xx 第第6章章 离散信源及其信息冗余离散信源及其信息冗余 2 有记忆信源与无记忆信源有记忆信源与无记忆信源实际信源的输出往往是由信源输出的一系列符号所组成的一个符号序列：X1X0X1XNXN+1信源输出的符号序列为一个随机变量序列，可以用随机矢量来表示。例如，若将英文文字信源的取值集合看做26个英文字母和空格及标点符号，则使用一段英文文字表达具有某种含义的信息时，该信源的输出将是一个由不同字母、空格和标点符号构成的消息序列。第第6章章 离散信源及其信息冗余离散信源及其信息冗余 由于信源输出的符号序列是一个随机变量序列，因此可以用随机矢量来

8、表示。设信源输出为一个N维随机矢量X=(X1,X2,XN)其中:XiR(i=1,2,N)。N维随机矢量X的统计特性需要使用联合概率密度函数：第第6章章 离散信源及其信息冗余离散信源及其信息冗余 P(X1=x1,X2=x2,XN=xN)=P(x1,x2,xN)=P(x)来描述。这里随机变量的样值为xiR i=1,2,N于是，根据信源输出的随机矢量中各分量之间是否存在相关性，可将信源划分为无记忆信源和有记忆信源。第第6章章 离散信源及其信息冗余离散信源及其信息冗余 1）无记忆信源如果信源输出的随机矢量中，各元素Xi相互独立，则信源是无记忆的。对于输出N维随机矢量的离散无记忆信源，如果各元素Xi具有

9、相同的概率密度，则其联合概率密度可表示为(6.2)121()(,)()NNiiPP x xxp x x第第6章章 离散信源及其信息冗余离散信源及其信息冗余 2)有记忆信源若随机矢量X=(X1,X2,XN)中各分量之间存在某种关联，则信源是有记忆信源。有记忆信源需要使用条件概率P(xN|x1,x2,xN1)描述其统计关系。显然，与无记忆信源相比，有记忆信源的描述要困难得多。当信源输出符号之间的记忆长度较大时，有记忆信源的描述与分析将更加困难。第第6章章 离散信源及其信息冗余离散信源及其信息冗余 3 平稳信源与非平稳信源平稳信源与非平稳信源对于更一般的信源，其输出实际上是时间t的一个连续函数X(t

10、)，或者是一个任意的消息序列X1X2Xi，即信源的输出是随机过程或随机序列。对这种信源的分析需要应用随机过程理论。对于一个随机过程或随机序列，根据其统计特性是否随着时间的平移而改变可将其划分为平稳随机过程和非平稳随机过程。相应地，信源也可划分为平稳信源或非平稳信源。如果信源输出的随机变量序列X1X2Xi是平稳的随机序列，则该信源是平稳信源，否则该信源是非平稳信源。第第6章章 离散信源及其信息冗余离散信源及其信息冗余 6.2 离散无记忆信源的扩展信源离散无记忆信源的扩展信源实际信源的输出往往是一个相当长的符号序列。例如，电报系统中的二进制信源的输出是一个由二进制符号0、1（点、画）构成的数据序列

11、。灰度图像信源输出有256种取值可能，图像信源输出的一幅灰度图像需要由若干行、若干列的像素组成，每一像素的取值可能为0255。显然，实际信源输出的任意长度符号序列的统计关系复杂，其输出信息特性的分析非常困难。此处，我们首先从最简单的信源入手，针对离散无记忆信源所输出的离散随机变量序列，分析其统计关系、信息度量及基本关系。第第6章章 离散信源及其信息冗余离散信源及其信息冗余 设离散无记忆信源输出离散随机变量序列为X1X2Xi，为了便于分析此信源输出信息的特性，将信源输出的随机变量分组（如取N个随机变量为一组），并且将每组随机变量表示为一个随机矢量。于是，输出随机变量序列的信源可以等效为一个输出N

12、维随机矢量的新信源，并且将这样的新信源称做原信源的N次扩展信源。第第6章章 离散信源及其信息冗余离散信源及其信息冗余 例如，将输出0、1符号的电报系统看做一个二进制离散无记忆信源X。若将该信源X输出的数据序01000110000101000中的每两个二进制符号划分为一组，则可等效为输出二维随机矢量的新信源。信源输出二维随机矢量X00,01,10,11。这个输出二维随机矢量X的新信源X2称为二进制离散无记忆信源X的二次扩展信源。对于一般的离散无记忆信源X，定义其N次扩展信源如下：设有一离散无记忆信源:第第6章章 离散信源及其信息冗余离散信源及其信息冗余 若将其输出的符号序列用一组长度为N的矢量序

13、列表示，则可等效为一个新信源。新信源输出的符号是长度为N的原符号序列，用N维随机矢量表示X，其样矢量为x=x1x2xNxiX;i=1,2,N 显然，离散无记忆信源X输出的长度为N的符号序列（N维随机矢量X）可以组成rN种不同的样矢量，并且样矢量中的各符号相互独立。1212.()().()rraaaX,PP aP aP a第第6章章 离散信源及其信息冗余离散信源及其信息冗余 定义输出N维随机矢量X的新信源为离散无记忆信源X的N次扩展信源XN。XN的概率空间为(6.3)1212 ,()()()()NNNrrXPPPP xxxxxxx第第6章章 离散信源及其信息冗余离散信源及其信息冗余 其中：由于信

14、源X是离散无记忆的，扩展信源XN输出的样矢量x=x1x2xN中各分量统计独立，因此有：10()1 1,2,1()NNiriiPirP xx12121()(,)()()()()NNNjjPP x xxP x P xP xP xx第第6章章 离散信源及其信息冗余离散信源及其信息冗余 于是，N次扩展信源XN的熵为(6.4)()()()log()NNXHH XPP xxx第第6章章 离散信源及其信息冗余离散信源及其信息冗余 性质性质 离散无记忆信源X的N次扩展信源XN的熵等于离散信源X的熵的N倍,即H(XN)=NH(X)(6.5)第第6章章 离散信源及其信息冗余离散信源及其信息冗余 证明：证明：其中，

15、内和式为11()()log()1()log()NNNXNjXjH XPPPP x xxx第第6章章 离散信源及其信息冗余离散信源及其信息冗余 1212111212121111()log()()()log()()1()()()log()1()()()()log()1 ()()log()NNNjjjNNXXjjNxX xXxXjjjxXxXxXxXjjNxXxXjPP x P xP xP xP xP x P xP xP xP xP xP xP xp xP xP xP x x第第6章章 离散信源及其信息冗余离散信源及其信息冗余 由于lj时：则因此证毕。()1llxXP x111()log()log(

16、)()1()log()()NjjxXXjjrlllPP xP xP xP aH XP ax1()()()NNjH XH XN H X第第6章章 离散信源及其信息冗余离散信源及其信息冗余【例例6.1】有一离散无记忆信源，求出其三次扩展信源X3的概率空间，计算H(X3)并与H(X)比较。解解：离散无记忆信源X的三次扩展信源X3共包含23=8种不同的样矢量。因为信源X无记忆，所以有P(x)=P(x1)P(x2)P(x3)xlX;l=1,2,312,3144aaX P第第6章章 离散信源及其信息冗余离散信源及其信息冗余 三次扩展信源X3的样矢量和相应的概率分布为X3:x1x2x3x4x5x6x7x8符

17、号取值：a1a1a1a1a1a2a1a2a1a1a2a2a2a1a1a2a1a2a2a2a1a2a2a2概率分布：2764964964364964364364164由此可以写出三次扩展信源的概率空间为1 1 11 1212112221 12122212223,2799393316464646464646464a a aa a aa a aa a aa a aa a aa a aa a aXP 第第6章章 离散信源及其信息冗余离散信源及其信息冗余 分别计算信源X及其三次扩展信源X3的熵为比特/符号因此H(X3)=3H（X）3 1()(,)0.81125 4 4H XH3279939331()(,

18、)64 64 64 64 64 64 64 64=2.43375 H XH比特 符号第第6章章 离散信源及其信息冗余离散信源及其信息冗余 以上结论也可以用熵的可加性解释。由于矢量的各分量间统计独立同分布，因此可以将扩展信源的熵看成是三个统计独立信源（信源熵均为H(X)）的联合熵。由熵的可加性有：H(X3)=H(X)+H(X)+H(X)=3H(X)对于XN而言，使用N1次熵的可加性即有：H(XN)=NH（X）第第6章章 离散信源及其信息冗余离散信源及其信息冗余 6.3 离散平稳信源离散平稳信源实际信源的输出往往是一个具有任意长度的随机变量序列。因此，对于实际信源输出的信息量及其关系的讨论是非常困

19、难的。此处，我们限定随机矢量的长度为N，通过分析N维随机矢量的统计关系，讨论信源输出信息的特性。设信源连续输出的长度为N的符号序列可以表示成N维随机矢量xj=(xj+1,xj+2,xj+N)其中:xj+iX X=a1,a2,ar;i=1,2,N（N为任意正整数）第第6章章 离散信源及其信息冗余离散信源及其信息冗余 于是，N维随机矢量的统计关系可以使用联合概率分布描述，即：P(xj)=P(xj+1,xj+2,xj+N)由前几章的讨论可知，信源输出信息量的大小依赖于符号的统计特性。在实际信源发出的符号序列中，信源的统计特性不仅与符号序列以及符号之间的统计关系有关，而且一般情况下这种统计关系也是时间

20、或位置的函数，即有：第第6章章 离散信源及其信息冗余离散信源及其信息冗余 因此，一般信源输出的随机变量序列应当是一个统计关系与时间、位置有关的非平稳的随机过程。显然，对于这种输出非平稳随机变量序列的非平稳信源，其信息特性的分析是十分困难的。如果信源符号序列的统计关系与其起点和位置的起点无关，则由随机过程理论可知，该符号序列具有平稳性。输出随机变量序列满足平稳性的信源为离散平稳信源。1212()()(|)(|)ijiiii Njjjj NPPP xxxxP xxxxijxx第第6章章 离散信源及其信息冗余离散信源及其信息冗余 设有离散平稳信源，其输出为N维随机矢量x=(x1,x2,xN)，由于N

21、维随机矢量x的联合概率分布P(x)与时间和位置的起点无关，即P(xi)=P(xi+1,xi+2,xi+N)=P(xj+1,xj+2,xj+N)=P(xj)ij(6.6)第第6章章 离散信源及其信息冗余离散信源及其信息冗余 于是，N维随机矢量x的联合概率分布P(x)可以表示为P(x)=P(x1,x2,xN)平稳信源输出的符号之间可能存在某种程度的关联，这种关联需要使用条件概率加以表示。依据联合概率与条件概率的关系：P(xj)=P(x1)P(x2|x1)P(x3|x1x2)P(xN|x1x2xN1)第第6章章 离散信源及其信息冗余离散信源及其信息冗余 可知，平稳信源输出符号之间的条件概率也与时间、

22、位置的起点无关，即满足：(6.7)11212121312112112121()()()()()()(|)(|)(|)(|)(|)(|)(|)(|)(|)ijijiijjiiijjji Niii NjNjjjNNNp xp xp xP xP xP xP xxP xxP xxP xx xP xx xP xx xP xx xxP xx xxP xx xx第第6章章 离散信源及其信息冗余离散信源及其信息冗余 如果信源输出的某一符号只与该符号前面的N-1个符号有统计依赖关系，则认为该信源符号序列的关联长度为N。由于离散平稳信源的熵及其特性的讨论仍然比较复杂，因此此处我们仅给出反映离散平稳信源信息特性的几

23、个定义和重要结论。设有离散平稳有记忆信源，其中:1212.,.rraaaX Ppppi01 1,2,piri11rip第第6章章 离散信源及其信息冗余离散信源及其信息冗余 该信源发出符号序列X1X2XNXN+1,设符号间关联长度为N，则该平稳信源输出的长度为N的样矢量:x=x1x2xN xiX;i=1,2,N具有联合概率分布P(x1,x2,xN)。下面首先给出度量平稳信源输出信息量的三个定义。第第6章章 离散信源及其信息冗余离散信源及其信息冗余 定义定义6.1 平稳信源输出的长度为N的随机矢量的联合熵为(6.8)12121212()()log()NNNNX XXH X XXP x xxP x

24、xx 第第6章章 离散信源及其信息冗余离散信源及其信息冗余 定义定义6.2 关联长度为N信源符号中平均每个符号所携带的信息量为平均符号熵，即(6.9)121()(,)NNHH XXXNX第第6章章 离散信源及其信息冗余离散信源及其信息冗余 定义定义6.3设信源符号序列之间的依赖关系长度为N，若已知前面N1个符号，则第N个符号所携带的平均信息量为条件熵，即(6.10)对于离散平稳信源，当H1(X)=H(X)时，具有以下性质：1121111(|)()log(|)NNNNNNNXXH XXXXP xxP xxx 第第6章章 离散信源及其信息冗余离散信源及其信息冗余 性质性质1 条件熵H(XN|X1X

25、2XN2XN1)随N的增加是非递增的，即H（X1）H(X2|X1)H(X3|X2X1)H(XN1|X1X2XN2)H(XN|X1X2XN1)(6.11)第第6章章 离散信源及其信息冗余离散信源及其信息冗余 证明：证明：第2章中式(2.33)所给出的条件熵的性质H(X|Y)H(X)表明，对于任意的X和Y，在已知Y的条件下关于X的平均不确定性不会超过关于X的先验不确定性，即条件熵不大于无条件熵。因此，当N=2，即平稳信源输出二维随机矢量(X1,X2)时，有H(X2)H(X2|X1)由于X1,X2X且具有相同的概率分布，则H(X1)=H(X2)=H(X)第第6章章 离散信源及其信息冗余离散信源及其信

26、息冗余 因此H(X1)H(X2|X1)当N3，即平稳信源输出N维随机矢量(X1,X2,XN)时，考察：1112112-1-112-2121122112211122(|)(|)()log(|)()log(|)NNNNNNNNNNNNNXXXNNNNXXXH XX XXH XX XXP x xxxP xx xxxP x xxxP xx xx 第第6章章 离散信源及其信息冗余离散信源及其信息冗余 由于离散平稳信源的联合概率分布和条件概率分布与时间或位置的起点无关，有：12121111221112221231121122()log(|)()log(|)()log(|)NNNNNNNNNNXXXNNNN

27、XXXNNNNXXXP x xxxP xx xxP xxxP xx xxP x xxxP xx xx第第6章章 离散信源及其信息冗余离散信源及其信息冗余 因此11112-1-112-22112112112112121121121121(|)(|)(|)()()log(|)()(|)()()log()NNNNNNNNNNNNXXXNNNNNNNNXXNNH XX XXH XX XXP xxxP x xxP x xxxP xx xxP x xxP xxxP x xxP x xxxP x xxx第第6章章 离散信源及其信息冗余离散信源及其信息冗余 已知对数函数是上凸函数，于是：11111121121

28、1211212112112121121(|)()log()()log(|)()log()(|)log()log10NNNNNNNNNNXXNNNNNXXNNNXXXNXXP xxxP x xxP x xxxP x xxxP xxxP x xxP x xxP xxxP x xx上式第第6章章 离散信源及其信息冗余离散信源及其信息冗余 因此有：H(XN|X1X2XN1)H(XN1|X1X2XN2)证毕。在观察平稳信源输出的符号序列时，如果已知X1、X2、XN1已发生，则关于将要发生的符号XN的平均不确定性为条件熵H(XN|X1X2XN1)。性质1表明，当条件增加时，关于信源输出符号XN的平均不确定

29、性不会增大。第第6章章 离散信源及其信息冗余离散信源及其信息冗余 性质性质2HN(X)H(XN|X1X2XN1)(6.12)证明证明：由平均符号熵的定义知：11211()()()log()NNNNNXXNHH X XXP xxP xx X第第6章章 离散信源及其信息冗余离散信源及其信息冗余 因为所以1121312121()()(|)(|)(|)NNNP xxP x P xx P xx xP xx xx111121122112121()()log()()log(|)()log(|)NNNNNNXXXXNNNXXNHP x xxP xP x xxP xxP x xxP xx xx X第第6章章 离

30、散信源及其信息冗余离散信源及其信息冗余 其中：1121121121111()log()()log()()log()()NNNNXXXXXXP x xxP xP x xxP xP xP xH X 11231212211221122121()log(|)()log(|)()log(|)(|)NNNNXXX XXXX XP x xxP xxP x xxP xxP x xP xxH XX112121121()log(|)(|)NNNNNNXXP x xxP xx xxH XX XX第第6章章 离散信源及其信息冗余离散信源及其信息冗余 于是有(6.13)性质1表明：12121121()()(|)(|)N

31、NNH X XXH XH XXH XX XX121121()(|)(|)NNH XH XXH XX XX第第6章章 离散信源及其信息冗余离散信源及其信息冗余 故必有即证毕。121211()()(|)NNNNHXH X XXH XX XXN121()(|)NNNHH XX XXX第第6章章 离散信源及其信息冗余离散信源及其信息冗余 由定义6.2、6.3可以看出，对于平稳信源输出N个信源符号X1X2XN1XN，平均符号熵HN(X)以简单的算术平均表示每一符号所载荷的平均信息量，而条件熵H(XN|XN1X1)描述的是已知前面N1个符号时关于符号XN的信息量。可见，平均符号熵HN(X)和条件熵H(XN

32、|X1X2XN1)均为单个符号平均信息量的度量方法。第第6章章 离散信源及其信息冗余离散信源及其信息冗余 由于当已知条件的数量N增加时，符号XN所携带的信息量将单调减小，因此，以N个符号的算术平均度量单个符号的信息量，一定不小于N1个符号已发生的条件下，关于第N个符号的信息量,即121(|)()NNNH XX XXHX第第6章章 离散信源及其信息冗余离散信源及其信息冗余 性质性质3HN(X)HN1(X)(6.14)证明证明：1212112112111()()(|)()(|)(1)()()(1)()NNNNNNNNNNNHH X XXH XX XXH X XXH XX XXNHHNHXXXX第第

33、6章章 离散信源及其信息冗余离散信源及其信息冗余 于是：证毕。性质3表明，平均符号熵HN(X)也是随着N的增加而非递增的。进一步分析：对于信息熵H(X)的平稳信源X，由于熵具有非负性，即HN(X)0，因此由性质3可以看出，信源符号序列长度不同时，平稳信源输出的每一个符号所载荷的信息量，即平均符号熵满足：1(1)()(1)()NNNHNHXX1()()NNHHXX第第6章章 离散信源及其信息冗余离散信源及其信息冗余(6.15)可见，随着信源符号序列长度N的增加，HN(X)将单调非递增地收敛于某有限值。对于平稳信源X，当其输出的符号序列足够长（N）时，每一个信源符号所载荷的信息有效地反映出了信源输

34、出的实际信息量。因此，定义为离散平稳信源X的极限信息量或极限熵。12-1()()()()()0NNHHHHH XXXXXlim()NNHHX第第6章章 离散信源及其信息冗余离散信源及其信息冗余 lim()NNHHX性质性质4 存在，且(6.16)121lim()lim(|)NNNNNHHH XX XXX第第6章章 离散信源及其信息冗余离散信源及其信息冗余 证明证明：对于一个任意的正整数k，有1211211211121211211211()()1 ()(|)(|)(|)1 ()(1)(|)NkNNNkNNNNNNkNkNNNHH X XX XXNkH X XXH XX XXNkH XX XXH

35、XX XXH X XXkH XX XXNk X12112111()(/)NNNkH X XXH XX XXNkNk第第6章章 离散信源及其信息冗余离散信源及其信息冗余 固定N，令k，得 已知N时，H+(X)的极限存在且为H，故有121lim()0(|)N kNNkHH XX XXXlim()N kkHHX第第6章章 离散信源及其信息冗余离散信源及其信息冗余 结合性质2指出的关系可知，条件熵H(XN|X1X2XN1)满足：H(X)H(XN|X1X2XN1)HN(X)令N，因为，所以lim()NNHHX121lim(|)NNNH XX XXH第第6章章 离散信源及其信息冗余离散信源及其信息冗余 于

36、是：证毕。121lim()lim(|)NNNNNHHXH XX XX第第6章章 离散信源及其信息冗余离散信源及其信息冗余 性质2、3、4说明：当平稳信源输出的符号序列长度达到无限大时，平均符号熵HN(X)和条件熵H(XN|X1X2XN1)都非递增地一致收敛于平稳信源的信息极限熵。因此，对于一个实际的平稳信源，当经过足够长的时间后，信源输出每一符号所载荷的信息量，即信源的极限熵可以用平均符号熵或条件熵加以度量。第第6章章 离散信源及其信息冗余离散信源及其信息冗余 6.4 马尔可夫信源马尔可夫信源实际信源往往是有记忆的，其输出符号序列中相邻符号间存在某种程度的相关性。例如，若将英文文字信源的取值集

37、合看做26个英文字母、空格和标点符号，则英文信源输出的一段语句不仅是一个由字母、空格和标点符号组成的随机变量序列，并且由于该语句具有某种含义，英文文字信源输出的符号组合必须满足英文的词法、语法结构要求，随机变量序列中的符号相互依赖。同样，由于模拟信号的变化相对于采样速率很慢，因此离散图像信源和离散语音信源输出的数据序列中，数值的变化大多是缓慢的。第第6章章 离散信源及其信息冗余离散信源及其信息冗余 在图像信源输出的灰度点阵中，相邻像元点的灰度相似，即像元点的灰度取值与其邻近像素点的灰度取值相近。语音信源输出的离散数据序列中，同一帧内相邻样点的幅度值差异小。可见，有记忆信源输出的符号序列中，符号

38、之间存在关联并且这种关联的程度与符号之间的距离有关。因此，有记忆信源的统计模型需要由一组信源符号和一组条件概率P(xi|xi1xi2xiL1xiL)来描述。显然，相对于无记忆信源，有记忆信源信息特性的分析要复杂得多，特别是相关距离很大甚至是无限大时。第第6章章 离散信源及其信息冗余离散信源及其信息冗余 在实际信源输出的随机变量序列中，信源在某时刻的输出符号往往只与前面邻近的若干个信源符号有较强的依赖关系，而相距较远时，随机变量之间的相关性将变得较弱，甚至可以忽略不计。因此可以依实际信源的统计关系和应用要求，将有记忆信源的统计模型适当地简化。于是，通常限定有记忆信源的记忆长度，认为某时刻信源符号

39、Xi发生的概率只与该时刻前面邻近的若干个信源输出符号相关联，而与更前面的符号是无关的。由于这类信源的输出符号序列近似为一个马尔可夫(Markov)过程，因此这类有记忆信源称为马尔可夫信源。第第6章章 离散信源及其信息冗余离散信源及其信息冗余 马尔可夫信源是一类特殊的离散有记忆信源，其特殊性在于任何时刻信源符号发生的概率只与前面已经发生的m个符号有关，而与更前面发生的符号无关。对符号序列:有：10111,mmmxxxxxx12,irxXXa aa11111(|)(|)t mt mtttt mt mttP xxxx xP xxxx(6.17)第第6章章 离散信源及其信息冗余离散信源及其信息冗余 因

40、为这种信源在任何时刻符号发生的概率只与前m个符号有关，所以，可以把这前m个符号看做信源在此时刻所处的状态，它对应于rm个不同的长为m的符号序列。定义状态集：E=E1,E2,EJ J=rm第第6章章 离散信源及其信息冗余离散信源及其信息冗余 若信源所处状态为sE，在每一状态下可能输出的符号xX，则当发出一个符号后，所处的状态就变了，即从状态s变到了另一状态，新状态由s的后m1个符号和发出的一个符号唯一确定。可见，状态的转移依赖于发出的信源符号，因此任何时刻信源处在什么状态完全由前一时刻的状态和发出的符号决定，对应信源的符号输出序列:,x1,x2,xl1,xl第第6章章 离散信源及其信息冗余离散信

41、源及其信息冗余 有唯一的状态序列：,s1,s2,sl1,sl对于m阶有记忆离散信源，它在t=1时刻输出符号x1的概率只与t=1时刻前面m个符号所对应的状态sl1有关。在输出符号后，进入由最新的m个符号组成的状态sl，如图6-2所示。第第6章章 离散信源及其信息冗余离散信源及其信息冗余 图6-2 状态转移图第第6章章 离散信源及其信息冗余离散信源及其信息冗余 其状态转移概率分布为P(xl=ak|sl1=Ei)k=1,2,r;i=1,2,rm 一般情况下，状态转移概率及已知状态下发出符号的概率均与时刻l有关。若与l无关，即P(xl=ak|sl=Ei)=P(ak|Ei)(6.18)则记pij=P(E

42、j|Ei)，称此状态序列是时齐的。第第6章章 离散信源及其信息冗余离散信源及其信息冗余 定义定义6.4 一个随机状态序列：s1,s2,sl,，若满足以下条件：(1)有限性：可能状态数目J0，且经过n0步，从状态Ei转移到状态Ej的转移概率，则在经过足够长的时间后，信源可以由一种状态转移到任意一种其他状态，并且满足：12,mrEE EE()0nijp第第6章章 离散信源及其信息冗余离散信源及其信息冗余(1)新状态si+1的概率仅与前一时刻的状态有关，而与更前面的状态无关，即P（si+1|sisi1si2）=P(si+1|si)(2)状态之间的转移概率P(El|Ek)与状态发生转移的时间或位置无关

43、。(3)无论信源的初始状态Ei为何，各种状态发生的概率都稳定在某极限概率：即每一种由各态历经过程产生的符号序列具有同样的统计特性。()lim()0nijjnpP E第第6章章 离散信源及其信息冗余离散信源及其信息冗余 可见，在经过足够长的时间后，有限、时齐、遍历马尔可夫信源成为一种平稳信源，且存在不依赖初始状态的状态极限概率(即平稳分布)。需要强调的是，只有在转移一定步数后各状态之间均可相通的条件下，当转移步数足够大，m阶马尔可夫信源达到稳定时，各状态出现的概率才能稳定在某一极限值，存在极限概率。对于m阶马尔可夫信源，状态一步转移概率可由状态一步转移矩阵表示，也可以用状态一步转移图表示。对于各

44、态遍历的马尔可夫信源，相应的状态一步转移图具有以下两个特点：第第6章章 离散信源及其信息冗余离散信源及其信息冗余（1）不可约性。在状态空间集合中，不存在一个各状态之间都能相互到达，而又与集合以外的状态不相通的集合，即闭集中不能再分出闭集。（2）非周期性。对于各态遍历的m阶马尔可夫信源来说，存在一个正整数n00，经过n0步转移后，各态均能相通，各态均能回到出发状态。在回到出发状态的可能步数中，必定包括n0和n0+1或n01。所以，在可能回到出发状态的步数中，不存在大于1的公因子，具有非周期性。第第6章章 离散信源及其信息冗余离散信源及其信息冗余【例例6.2】有一个二进制二阶马尔可夫信源，X=0,

45、1，条件概率为P(0|00)=P(1|11)=0.8P(1|00)=P(0|11)=0.2P(0|01)=P(0|10)=P(1|01)=P(1|10)=0.5第第6章章 离散信源及其信息冗余离散信源及其信息冗余 该信源的转移特性只与符号序列有关，有4个状态：E1 对应序列00E2 对应序列01E3 对应序列10E4 对应序列11第第6章章 离散信源及其信息冗余离散信源及其信息冗余 由概率分布可知,状态一步转移概率为P(E1|E1)=P(E4|E4)=0.8P(E2|E1)=P(E3|E4)=0.2P(E3|E2)=P(E2|E3)=P(E4|E2)=P(E1|E3)=0.5其他状态转移概率等

46、于0。第第6章章 离散信源及其信息冗余离散信源及其信息冗余 信源是有限、既约、齐次的马尔可夫链，且可以进一步判定是各态历经源，故有：1132133244421234()0.8()0.5()()0.2()0.5()()0.5()0.2()()0.8()0.5()()()()()1P EP EP EP EP EP EP EP EP EP EP EP EP EP EP EP E第第6章章 离散信源及其信息冗余离散信源及其信息冗余 可求出：为马尔可夫信源的平稳分布，且等于初始分布。23141()()75()()14P EP EP EP E第第6章章 离散信源及其信息冗余离散信源及其信息冗余 由上述讨论

47、可以看出，由于有记忆信源输出符号之间存在关联，因此其信息特性分析的难度较大，特别是相关距离很大甚至是无限大时。工程应用中，图像、语音等实际信源输出的符号序列中，相邻符号之间的相关性较大，而距离较远的符号之间的相关性很小，往往可以忽略。因此，对于这类实际信源信息特性的分析，可以从两个方面作适当假设，以在掌握此类信源本质特性的前提下简化分析过程。第第6章章 离散信源及其信息冗余离散信源及其信息冗余 首先，由于实际信源的相关性主要表现在相邻符号之间，因此可以对有记忆信源的记忆长度加以限制。假设信源在某时刻输出的符号仅与该时刻前面输出的m个符号存在依赖关系，而与更前面的符号无关，则将信源的相关长度限定

48、为m，看做m阶的马尔可夫信源。其次，假设实际信源输出的随机变量序列满足时齐性和遍历性,那么，在经过足够长的时间后，时齐、遍历的m阶马尔可夫信源输出的符号序列为一平稳随机过程。因此，可以将工程应用中的实际信源看做一个平稳的m阶马尔可夫信源，依据平稳信源和马尔可夫信源的信息测度所满足的基本关系和性质，分析实际信源的信息特性。第第6章章 离散信源及其信息冗余离散信源及其信息冗余 假设时齐、遍历的m阶马尔可夫信源的输出是一个具有任意长度的符号序列：X1X2Xi1Xi 由6.3节的讨论可知，当其输出的符号序列足够长（N）时，平均符号熵HN(X)的极限值反映了信源输出的实际信息量。已知此信源的极限信息量或

49、极限熵为121lim()lim()NNNNNNHHHX XXXX第第6章章 离散信源及其信息冗余离散信源及其信息冗余 因为此处的N表示信源输出的符号序列足够长，这表明信源的输出已经经历了足够长的时间，所以信源符号序列可以看做一个平稳的随机过程，该信源成为一种平稳信源。对于平稳信源，极限熵H也可以表示为序列长度N足够长时的条件熵,即有：由于此信源是一个m阶的马尔可夫信源，输出符号XN仅与该符号前面的m个符号相关，而与更前面的符号无依赖关系，因此，式(6.23)反映的无限长的条件依赖关系可以转化为有限长的依赖关系，满足：121lim(|)NNNHH XX XX(6.23)第第6章章 离散信源及其信

50、息冗余离散信源及其信息冗余 进一步地，考虑到信源已进入一个平稳状态，而平稳信源输出随机变量序列的统计特性与时间或位置的起点无关，故有：H=H(Xm+1|X1X2Xm)121lim(|)NN mN mNNNHH XXXXX第第6章章 离散信源及其信息冗余离散信源及其信息冗余 于是，得到m阶马尔可夫信源的极限信息量：H=H(Xm+1|X1X2Xm)=Hm+1可见，时齐、遍历的m阶马尔可夫信源所提供的平均信息量为已知前m个信源符号的条件下，对信源将要输出的符号的不确定性。因此，m阶马尔可夫信源的极限熵的计算可以转化为条件熵的计算,即(6.24)1111lim(|)(|)NNmmNHH XXXH XX