第二章信息与编码

1、第二章第二章 离散信源及其信息测度离散信源及其信息测度 第一节第一节 信源的数学模型及分类信源的数学模型及分类 第二节第二节 离散信源的信息熵离散信源的信息熵 第三节第三节 信息熵的基本性质信息熵的基本性质 第四节第四节 离散无记忆的扩展信源离散无记忆的扩展信源 第五节第五节 离散平稳信源离散平稳信源 第六节第六节 马尔可夫信源马尔可夫信源 第七节第七节 信源剩余度与自然语言的熵信源剩余度与自然语言的熵 n 信源的主要问题信源的主要问题 1 1如何描述信源（信源的数学建模问题）描述信源（信源的数学建模问题） 2 2怎样计算信源所含的信息量怎样计算信源所含的信息量 3 3怎样有效的表示信源输出的

2、消息，也就是信源编码问题怎样有效的表示信源输出的消息，也就是信源编码问题 第一节第一节 信源的数学模型及分类信源的数学模型及分类 在通信系统中，收信者在未收到信息以前，对在通信系统中，收信者在未收到信息以前，对 信源发出什么样的消息是不确定的，是随机的，信源发出什么样的消息是不确定的，是随机的， 所以可以用随机变量、随机矢量或随机过程来描所以可以用随机变量、随机矢量或随机过程来描 述信源输出的消息，或者说用一个述信源输出的消息，或者说用一个样本空间样本空间及其及其 概率测度概率测度来描述信源。来描述信源。 不同的信源根据其输出消息的不同的随机性质不同的信源根据其输出消息的不同的随机性质 进行分

3、类。进行分类。 信源的定义及分类信源的定义及分类 n离散信源 n连续信源 n是指发出在时间和幅度上都是离散分布的离 是指发出在时间和幅度上都是离散分布的离 散消息的信源，如文字、数字、数据等符号散消息的信源，如文字、数字、数据等符号 都是离散消息。都是离散消息。 是指发出在时间和幅度上都是连续分布的连是指发出在时间和幅度上都是连续分布的连 续消息（模拟消息）的信源，如语言、图像、续消息（模拟消息）的信源，如语言、图像、 图形等都是连续消息。图形等都是连续消息。 第一节第一节 信源的数学模型及分类信源的数学模型及分类 1 1、离散信源、离散信源 数学模型如下：数学模型如下： 12 12 . .

4、q n aaxX pppP 1 1 q i i p 集合集合X X中，包含该信源包含的所有可能输出中，包含该信源包含的所有可能输出 的消息，集合的消息，集合P P中包含对应消息的概率密度，各中包含对应消息的概率密度，各 个消息的输出概率总和应该为个消息的输出概率总和应该为1 1。 例：天气预报例：天气预报 第一节第一节 信源的数学模型及分类信源的数学模型及分类 2 2、连续信源、连续信源 数学，模型如下：数学，模型如下： ( , ) ( )( ) Xa b p xp x ( )1 b a p x dx 每次只输出一个消息，但消息的可能数目是无穷每次只输出一个消息，但消息的可能数目是无穷 多个。

5、多个。 例：电压、温度等。例：电压、温度等。 发出单个符号的无记忆信源 离散无记忆信源 发出符号序列的无记忆信源 离散信源 发出符号序列的有记忆信源 离散有记忆信源 发出符号序列的马儿可夫信源 离散信源的进一步分类离散信源的进一步分类 指信源每次只发出指信源每次只发出 一个符号代表一一个符号代表一 个消息个消息 指信源每次发出一指信源每次发出一 组含二个以上符号组含二个以上符号 的符号序列代表一的符号序列代表一 个消息个消息 n根据随机变量间是否统计独立将信源分为有记忆信源有记忆信源和无无 记忆信源记忆信源。 n离散无记忆信源 n离散有记忆信源 所发出的各个符号是相互独立所发出的各个符号是相互

6、独立 的，发出的符号序列中的各个的，发出的符号序列中的各个 符号之间没有统计关联性，各符号之间没有统计关联性，各 个符号的出现概率是它自身的个符号的出现概率是它自身的 先验概率。先验概率。 所发出的各个符号所发出的各个符号 的概率是有关联的。的概率是有关联的。 有记忆信源符号间的概率关联性可用两种方式：有记忆信源符号间的概率关联性可用两种方式： n一种是用信源发出的一个符号序列的整体概率（即联合概率）一种是用信源发出的一个符号序列的整体概率（即联合概率） 反映有记忆信源的特征反映有记忆信源的特征 n一种限制记忆长度，即某一个符号出现的概率只与前面一个一种限制记忆长度，即某一个符号出现的概率只与

7、前面一个 或有限个符号有关，而不依赖更前面的那些符号，这样的信或有限个符号有关，而不依赖更前面的那些符号，这样的信 源可以用信源发出符号序列内各个符号之间的条件概率来反源可以用信源发出符号序列内各个符号之间的条件概率来反 映记忆特征，这就是发出符号序列的映记忆特征，这就是发出符号序列的马尔可夫信源马尔可夫信源 n根据各维随机变量的概率分布是否随时间的推移而变化将根据各维随机变量的概率分布是否随时间的推移而变化将 信源分为平稳信源和非平稳信源信源分为平稳信源和非平稳信源 ( )( () 1 HNH X H H m X离散无记忆信源：） 记忆长度无限长： 离散平稳信源 平稳信源离散有记忆信源 记忆

8、长度有限马尔可夫信源： 连续平稳信源 非平稳信源 离散信源分类 离散信源分类 离散信源分类 一个实际信源的统计特性往往是相当复杂 的，要想找到精确的数学模型很困难。实际应 用时常常用一些可以处理可以处理的数学模型来近似。 随机序列，特别是离散平稳随机序列是我们研 究的主要内容。 第二节第二节 离散信源的信息熵离散信源的信息熵 1 1、自信息、自信息 我们认为，一个字符它所携带的信息量是和该字符出我们认为，一个字符它所携带的信息量是和该字符出 现的概率有关，概率可以表征自信息量的大小现的概率有关，概率可以表征自信息量的大小 ( ) ( ) ii I af P a 根据客观事实和人们的习惯概念，应

9、满足根据客观事实和人们的习惯概念，应满足 以下条件以下条件: : 第二节第二节 离散信源的信息熵离散信源的信息熵 （2 2）当）当( )1 i P a 时时( )0 i f P ( ) i f P （3 3）当）当 时时()0 i P a （4 4）两个独立事件的联合信息量应等于它们分别的信息量）两个独立事件的联合信息量应等于它们分别的信息量 之和。之和。 (1) (1) 应是先验概率的单调递减函数，即当应是先验概率的单调递减函数，即当 时时 () i f p 1122 ()()P aP a 12 ( )()f Pf P 第二节第二节 离散信源的信息熵离散信源的信息熵 根据上述条件可以从数学上

10、证明这种函数形式是对根据上述条件可以从数学上证明这种函数形式是对 数函数，即：数函数，即： 1 ( )log ( ) i i I a P a ( ) i I a有有两个含义两个含义： 1 1、当事件发生前，表示该事件发生的不确定性；、当事件发生前，表示该事件发生的不确定性； 2 2、当事件发生后，标是该事件所提供的信息量、当事件发生后，标是该事件所提供的信息量 自信息 第二节第二节 离散信源的信息熵离散信源的信息熵 例：设天气预报有两种消息，晴天和雨天，出现的概率例：设天气预报有两种消息，晴天和雨天，出现的概率 分别为分别为1/41/4和和3/43/4，我们分别用，我们分别用 来表示晴天，以来

11、表示晴天，以 来表示来表示 雨天，则我们的信源模型如下：雨天，则我们的信源模型如下： 1 a 2 a 1,2 ( )1/ 4,3/ 4 aaX p x 1 ( )log42I a 2 4 ()log0.415 3 I a 第二节第二节 离散信源的信息熵离散信源的信息熵 我们定义自信息的数学期望为信源的平均信息量我们定义自信息的数学期望为信源的平均信息量 1 1 ()log( )log( ) ( ) q ii i i H XEP aP a p a 信息熵具有以下两种物理含义：信息熵具有以下两种物理含义： 1 1、表示信源输出前信源的平均不确定性、表示信源输出前信源的平均不确定性 2 2、表示信源

12、输出后，每个符号所携带的、表示信源输出后，每个符号所携带的 平均信息量平均信息量 2 2、信息熵、信息熵 例：天气预报，有两个信源例：天气预报，有两个信源 1,21 ( )1/4,3/4 aaX p x 1,22 ( )1/2,1/2 aaX p x 1 134 ()log4log0.809 443 H X 2 11 ()log2log21 22 H X 则：则： 说明第二个信源的平均不确定性更大一些说明第二个信源的平均不确定性更大一些 第二节第二节 离散信源的信息熵离散信源的信息熵 第三节第三节 信息熵的基本性质信息熵的基本性质 熵函数可以表示为：熵函数可以表示为： HXHppppp nii

13、 i n ()(,)lo g 12 1 ppin i i n i 1 101 2,(, ,.,) 第三节第三节 信息熵的基本性质信息熵的基本性质 性质性质1 1：非负性：非负性 H(X)0H(X)0 由于由于0pi1,0pi1,所以所以logpi0logpi0， logpi0logpi0，则总有，则总有H(X)0H(X)0。 性质性质2 2：对称性：对称性 H pppH pppp nnn (,.)(,.) 12121 根据加法交换律可以证明，当变量交换顺序时熵函数的根据加法交换律可以证明，当变量交换顺序时熵函数的 值不变。值不变。 信源的熵只与概率空间的总体结构有关，而与个概率分信源的熵只与概

14、率空间的总体结构有关，而与个概率分 量对应的状态顺序无关；量对应的状态顺序无关； 第三节第三节 信息熵的基本性质信息熵的基本性质 性质性质3 3：确定性；：确定性； HHH( , )( , )( , , ,. )1 00 11 0 000 当信源当信源X X的信源空间的信源空间XX，PP中。任一个概率分量等于中。任一个概率分量等于1 1， 根据完备空间特性，其它概率分量必为根据完备空间特性，其它概率分量必为0 0，这时信源为，这时信源为 一个确知信源，其熵为一个确知信源，其熵为0 0。 如果一个信源的输出符号几乎必然为某一状态，那么这如果一个信源的输出符号几乎必然为某一状态，那么这 个信源没有

15、不确定性，信源输出符号后不提供任何信息个信源没有不确定性，信源输出符号后不提供任何信息 量。量。 第三节第三节 信息熵的基本性质信息熵的基本性质 性质性质4 4：扩展性：扩展性 11212 0 lim(,., )(,.,) qqqq Hp ppHp pp 这说明信源空间中增加某些概率很小的符号，虽这说明信源空间中增加某些概率很小的符号，虽 然当发出这些符号时，提供很大的信息量，但由于其然当发出这些符号时，提供很大的信息量，但由于其 概率接近于概率接近于0 0，在信源熵中占极小的比重，使信源熵，在信源熵中占极小的比重，使信源熵 保持不变。保持不变。 第三节第三节 信息熵的基本性质信息熵的基本性质

16、 性质性质5 5 ：极值性：极值性 12 ( ,.,)(1/ ,1/ ,.,1/ )log q H p ppHqqqq 上式表明，对于具有上式表明，对于具有q q个符号的离散信源，只有在个符号的离散信源，只有在 q q个信源符号等可能出现的情况下，信源熵才能达到个信源符号等可能出现的情况下，信源熵才能达到 最大值，这也表明等概分布的信源的平均不确定性最最大值，这也表明等概分布的信源的平均不确定性最 大，这是一个很重要得结论，称为大，这是一个很重要得结论，称为最大离散熵定理最大离散熵定理 例：对于一个二元信源例：对于一个二元信源 H(X)=H(1/2,1/2)=log2=1bitH(X)=H(1

17、/2,1/2)=log2=1bit 第四节第四节 离散无记忆的扩展信源离散无记忆的扩展信源 实际信源输出的消息往往是时间上或空间上的一系实际信源输出的消息往往是时间上或空间上的一系 列符号，如电报系统，序列中前后符号间一般是有统列符号，如电报系统，序列中前后符号间一般是有统 计依赖关系的。计依赖关系的。 我们先讨论离散无记忆信源，此时，信源序列的前我们先讨论离散无记忆信源，此时，信源序列的前 后符号之间是统计独立的后符号之间是统计独立的 如在二元系统中，我们可以把两个二元数字看成一如在二元系统中，我们可以把两个二元数字看成一 组，会出现四种可能情况：组，会出现四种可能情况：0000、0101、

18、1010和和1111，我们可，我们可 以把这四种情况看成一个新的信源称为以把这四种情况看成一个新的信源称为二元无记忆信二元无记忆信 源的二次扩展信源源的二次扩展信源，相应的，如果把，相应的，如果把N N个二元数字看个二元数字看 成一组，则新的信源称为成一组，则新的信源称为二元无记忆信源的二元无记忆信源的N N此扩展此扩展 信源。信源。 第四节第四节 离散无记忆的扩展信源离散无记忆的扩展信源 一般情况一般情况 设一个离散无记忆信源为：设一个离散无记忆信源为： pi i n 1 1 12 12 . ()().() N N N q q X pppP 则该信源的则该信源的N N次扩展信源为：次扩展信源

19、为： 12 12 . . q n aaxX pppP 第四节第四节 离散无记忆的扩展信源离散无记忆的扩展信源 其中：其中： 12 ()() (). () iiiiN PP aP aP a 根据信息熵的定义：根据信息熵的定义： ()()log() N NNN X H XP XP X 可以证明，对于离散无记忆的扩展信源可以证明，对于离散无记忆的扩展信源 ()() N H XNH X 例例: : 离散无记忆信源的离散无记忆信源的N N次扩展信源次扩展信源 离散无记忆信源为：离散无记忆信源为：X:a1,a2,a3; P(X):1/4, 1/2, 1/4X:a1,a2,a3; P(X):1/4, 1/2

20、, 1/4 2 2次扩展信源为：次扩展信源为： 2 X :A1A9:A1A9 信源的信源的9 9个符号为：个符号为： 第四节第四节 离散无记忆的扩展信源离散无记忆的扩展信源 第四节第四节 离散无记忆的扩展信源离散无记忆的扩展信源 其概率关系为其概率关系为 : : 计算可知计算可知 2 ()3H Xbit ()1.5H Xbit 2 ()2()H XH X 第五节第五节 离散平稳信源离散平稳信源 一般来说，信源的前后消息之间有前后依赖关系，一般来说，信源的前后消息之间有前后依赖关系， 可以用随机矢量描述：可以用随机矢量描述： 12 (.,.,.) i XXXX 信源在某一时刻发出什么样的值取决于

21、两方面信源在某一时刻发出什么样的值取决于两方面 1 1、这一时刻该变量的分布概率、这一时刻该变量的分布概率 2 2、这一时刻以前发出的消息、这一时刻以前发出的消息 如一个人讲话如一个人讲话 我们现在讨论我们现在讨论平稳的平稳的随机序列，随机序列，所谓平稳是指序所谓平稳是指序 列的统计性质与时间的推移无关列的统计性质与时间的推移无关（俩个任意时刻（俩个任意时刻 信源发出符号的概率分布完全相同）。信源发出符号的概率分布完全相同）。 1 1、离散平稳信源的数学定义、离散平稳信源的数学定义 第五节第五节 离散平稳信源离散平稳信源 2 2、二维平稳信源及其信息熵、二维平稳信源及其信息熵 最简单的平稳信源

22、最简单的平稳信源二维平稳信源，信源发出序列二维平稳信源，信源发出序列 中只有前后两个符号间有依赖关系，我们可以对其二维中只有前后两个符号间有依赖关系，我们可以对其二维 扩展信源进行分析。扩展信源进行分析。 信源的概率空间信源的概率空间: : 连续两个信源符号出现的联合概率分布为：连续两个信源符号出现的联合概率分布为： 12 12 , ()1 (),(),()() q i q aaaX p a p ap ap aP X q i=1 且 1 ()()1 qq ijij j P a aP a a i=1 且 第五节第五节 离散平稳信源离散平稳信源 已知符号已知符号 出现后，紧跟着出现后，紧跟着 出现

23、的条件概率为：出现的条件概率为： i a j a () (|) () ij ji i Pa a Paa Pa 由二维离散信源的发出符号序列的特点可以把其分由二维离散信源的发出符号序列的特点可以把其分 成每两个符号一组，每组代表新信源成每两个符号一组，每组代表新信源 中的一个中的一个 符号。并假设组与组之间是统计独立的，互不相关的。符号。并假设组与组之间是统计独立的，互不相关的。 12 XX X 得到一个新的离散无记忆信源得到一个新的离散无记忆信源 ，其联合概率空间为：，其联合概率空间为： 12 X X 12 12 () X X P x x 11121 ,., ()() (|) qqqq iji

24、ji a a a aaaa a P a aP a P aa 第五节第五节 离散平稳信源离散平稳信源 12 11 ()()log () qq ijij ij H X XP a aP a a 根据信息熵的定义，可得：根据信息熵的定义，可得： （1 1）联合熵联合熵 可以表征信源输出长度为可以表征信源输出长度为2 2的平均不确定性，或所含的平均不确定性，或所含 有的信息量。因此可以用有的信息量。因此可以用 作为二维平稳作为二维平稳 信源的信息熵的近似值信源的信息熵的近似值 12 1/2()H X X 第五节第五节 离散平稳信源离散平稳信源 (2)(2)条件熵条件熵 21 1 (|)(|)log(|)

25、 q ijiji j H XXaP aaP aa 则：则： 2121 1 (|)()(|) q ii i H XXP a H XXa 11 () (|)log(|) qq ijiji ij P a P aaP aa 11 ()log(|) qq ijji ij P a aP aa 第五节第五节 离散平稳信源离散平稳信源 另外还可以得到：另外还可以得到： 21 (|)()H XXH X 1212 ()()()2()H X XH XH XH X 只有信源统计独立时等号成立。只有信源统计独立时等号成立。 可以证明：可以证明： 12121 ()()(|)H X XH XH XX 例例2-15 2-15

26、 设某二维离散信源的原始信源的信源空间设某二维离散信源的原始信源的信源空间 X=x1,x2,x3; P(X)=1/4, 1/4, 1/2, X=x1,x2,x3; P(X)=1/4, 1/4, 1/2, 一维条件概率为：一维条件概率为： p(x1/x1)=1/2; p(x2/x1)=1/2; p(x3/x1)=0;p(x1/x1)=1/2; p(x2/x1)=1/2; p(x3/x1)=0; p(x1/x2)=1/8; p(x2/x2)=3/4; p(x3/x2)=1/8;p(x1/x2)=1/8; p(x2/x2)=3/4; p(x3/x2)=1/8; p(x1/x3)=0; p(x2/x3

27、)=1/4; p(x3/x3)=3/4;p(x1/x3)=0; p(x2/x3)=1/4; p(x3/x3)=3/4; 原始信源的熵为：原始信源的熵为： H(X)=1.5 bit/H(X)=1.5 bit/符号符号 条件熵：条件熵： H(X2/X1)=1.4 bit/H(X2/X1)=1.4 bit/符号符号 可见：可见： H(X2/X1)H(X)H(X2/X1)H(X) 二维信源的熵：二维信源的熵：H(X1,X2)=H(X1)+H(X2/X1)=2.9 bit/H(X1,X2)=H(X1)+H(X2/X1)=2.9 bit/消息消息 每个信源符号提供的平均信息量为：每个信源符号提供的平均信息

28、量为： H2(X1,X2)=H(X1,X2)/2=1.45 bit/H2(X1,X2)=H(X1,X2)/2=1.45 bit/符号。符号。 第五节第五节 离散平稳信源离散平稳信源 第五节第五节 离散平稳信源离散平稳信源 我们现在有两种方法去近似信源的实际熵，一种是我们现在有两种方法去近似信源的实际熵，一种是 为为1.45bit1.45bit，但这种方法不太准确，因为它把两个消息，但这种方法不太准确，因为它把两个消息 看成一组，认为两组之间是统计独立的，实际上它们看成一组，认为两组之间是统计独立的，实际上它们 之间是有关联的；另一种是我们可以用条件熵来近似，之间是有关联的；另一种是我们可以用条

29、件熵来近似， 为为1.4bit1.4bit，到底那一种正确呢？我们可以通过对一般离，到底那一种正确呢？我们可以通过对一般离 散平稳信源的分析来找到这个答案。散平稳信源的分析来找到这个答案。 12 1/2()H X X 分析：我们用分析：我们用 2( )HX来近似信源的实际熵来近似信源的实际熵 第五节第五节 离散平稳信源离散平稳信源 3 3、离散平稳信源的极限熵、离散平稳信源的极限熵 平均符号熵平均符号熵 12 1 ()(.) NN HXH X XX N 条件熵条件熵 121 (|.) NN H XX XX 有以下几点性质有以下几点性质 （1 1）条件熵随）条件熵随N N的增加是非递增的的增加是

30、非递增的 （2 2）N N给定时，平均符号熵大于等于条件熵给定时，平均符号熵大于等于条件熵 （3 3）平均符号熵随）平均符号熵随N N的增加是非递增的的增加是非递增的 （4 4） 121 lim()lim(|.) NNN NN HHXH XX XX H称称 为为极限熵极限熵。 第五节第五节 离散平稳信源离散平稳信源 可以证明，对于二维离散平稳信源，条件熵等于极可以证明，对于二维离散平稳信源，条件熵等于极 限熵，因此条件熵就是二维离散平稳信源的真实熵限熵，因此条件熵就是二维离散平稳信源的真实熵 对于一般信源，求出极限熵是很困难的，然而，一对于一般信源，求出极限熵是很困难的，然而，一 般来说，取般

31、来说，取N N不大时就可以得到与极限熵非常接近的条不大时就可以得到与极限熵非常接近的条 件熵和平均符号熵，因此可以用条件熵和平均符号熵件熵和平均符号熵，因此可以用条件熵和平均符号熵 来近似极限熵来近似极限熵 第六节第六节 马尔可夫信源马尔可夫信源 在很多信源的输出序列中，符号之间的依赖关系是在很多信源的输出序列中，符号之间的依赖关系是 有限的，任何时刻信源符号发生的概率只与前边已经发有限的，任何时刻信源符号发生的概率只与前边已经发 出的若干个符号有关，而与更前面的符号无关。出的若干个符号有关，而与更前面的符号无关。 为了描述这类信源除了信源符号集外还要引入状态为了描述这类信源除了信源符号集外还

32、要引入状态 集。这时，信源输出消息符号还与信源所处的状态有关。集。这时，信源输出消息符号还与信源所处的状态有关。 若一个信源满足下面两个条件，则称为马尔可夫信源：若一个信源满足下面两个条件，则称为马尔可夫信源： （1 1）某一时刻信源输出的符号的概率只与当前所处的）某一时刻信源输出的符号的概率只与当前所处的 状态有关，而与以前的状态无关；状态有关，而与以前的状态无关； （2 2）信源的下一个状态由当前状态和下一刻的输出唯）信源的下一个状态由当前状态和下一刻的输出唯 一确定。一确定。 设某二阶马尔可夫信源所处的状态 E=E0,E1,E2,E3=00，01，10，11 ，在每一状 态下可能输出的符

33、号0，1。 0 0 1 0 1 1 0 0 1 1 0 1 0 E0=00 1 E1=01 0 E2=10 1 E1=01 1 E3=11 0 E2=10 P(1/E0)= P(E1/E0)=P01 第六节第六节 马尔可夫信源马尔可夫信源 （1 1）某一时刻信源输出的符号的概率只与当前所处的状态有）某一时刻信源输出的符号的概率只与当前所处的状态有 关，而与以前的状态无关。即关，而与以前的状态无关。即 1 11 (|, )(|) lklilkljlkli P xa sE xa sEP xa sE 当符号输出概率与时刻当符号输出概率与时刻L L无关，称为具有时齐性。即无关，称为具有时齐性。即 (|

34、)(|),(|)1 k lklikiki aA P xasEP aEP aE 第六节第六节 马尔可夫信源马尔可夫信源 （2 2）信源的下一个状态由当前状态和下一刻的输出唯一确定。）信源的下一个状态由当前状态和下一刻的输出唯一确定。 条件（条件（2 2）表明，若信源处于某一状态）表明，若信源处于某一状态 ，当它发出，当它发出 一个符号后，所处的状态就变了，一定转移到另一状态。一个符号后，所处的状态就变了，一定转移到另一状态。 状态的转状态的转 移依赖于发出的信源符号，因此任何时刻信源处移依赖于发出的信源符号，因此任何时刻信源处 在什么状态完全由前一时刻的状态和发出的符号决定。在什么状态完全由前一

35、时刻的状态和发出的符号决定。 i E 第六节第六节 马尔可夫信源马尔可夫信源 例：二阶马尔可夫信源，原始符号集为例：二阶马尔可夫信源，原始符号集为1,01,0， 条件概率定为：条件概率定为：P(0|00)=P(1|11)=0.8P(0|00)=P(1|11)=0.8 P(1|00)=P(0|11)=0.2 P(1|00)=P(0|11)=0.2 P(0|01)=P(0|10)=P(1|01)=P(1|10)=0.5 P(0|01)=P(0|10)=P(1|01)=P(1|10)=0.5 由此可见，信源共有由此可见，信源共有22=422=4种状态种状态 E E：e1=00,e2=01,e3=10

36、,e4=11e1=00,e2=01,e3=10,e4=11 第六节第六节 马尔可夫信源马尔可夫信源 状态之间有转移概率，状态之间有转移概率， p(e2/e1)=p(e3/e4)=0.2p(e2/e1)=p(e3/e4)=0.2 p(e2/e4)=p(e1/e3)=p(e2/e3)=p(e3/e2)=0.5p(e2/e4)=p(e1/e3)=p(e2/e3)=p(e3/e2)=0.5 P(e1/e1)=p(e4/e4)=0.8P(e1/e1)=p(e4/e4)=0.8 其状态转移图如下页。在状态转换图中，把信源的每一种状其状态转移图如下页。在状态转换图中，把信源的每一种状 态用圆圈表示，用有向箭

37、头表示信源发出某一符号后由一种态用圆圈表示，用有向箭头表示信源发出某一符号后由一种 状态到另一状态的转移。状态到另一状态的转移。 第六节第六节 马尔可夫信源马尔可夫信源 01 01 10 10 0:0.50:0.5 1:0.21:0.2 0:0.20:0.2 00 00 0:0.80:0.8 11 11 1:0.81:0.8 1:0.51:0.5 0:0.50:0.5 1:0.51:0.5 由上例可知，由上例可知，m m阶马尔可夫信源符号集共有阶马尔可夫信源符号集共有q q个符号，则个符号，则 信源共有信源共有 个不同状态。信源在某一时刻时，必然处于某一个不同状态。信源在某一时刻时，必然处于某

38、一 种状态，等到下一个字符输出时，转移到另外一个状态。种状态，等到下一个字符输出时，转移到另外一个状态。 m q 举举 例例 例例2.2.3 2.2.3 设信源符号设信源符号 X Xx x1 1, , x x2 2, , x x3 3 ，信源所处的状态，信源所处的状态S Se e1 1, , e e2 2, , e e3 3, , e e4 4, , e e5 5 。各状态之间的转移情况由图。各状态之间的转移情况由图2.2.12.2.1给出。给出。 将图中信源在将图中信源在e ei i状态下发符号状态下发符号x xk k 的条件概率的条件概率p p( (x xk k / /e ei i) )用

39、矩阵表示用矩阵表示 由矩阵看出：由矩阵看出： 由图中看出：由图中看出： 由图中可得状态的一步转移概率：由图中可得状态的一步转移概率： 该信源满足马尔可夫信源定义。该信源满足马尔可夫信源定义。 2 1 4 1 2 1 4 1 4 1 4 3 2 1 4 1 4 1 2 1 5 4 3 2 1 321 001 0 0 e e e e e xxx 3 1 5 , 4 , 3 , 2 , 1, 1)/( k ik iexp 0),/( 1),/( 1),/( 0),/( 1123 1122 1111 1112 eSxXeSP eSxXeSP eSxXeSP eSxXeSP lll lll lll ll

40、l 4 1 4 3 4 1 4 3 2 1 2 1 4 1 4 1 2 1 5 4 3 2 1 000 00000 000 000 00 54321 e e e e e eeeee 第六节第六节 马尔可夫信源马尔可夫信源 定义定义 为各状态的极限概率，则时齐、遍历的马尔可为各状态的极限概率，则时齐、遍历的马尔可 夫信源的熵为夫信源的熵为 () i Q E 1 ()(|) J ii i HQ E H X E 11 () (|)log(|) qJ ikiki ik Q E P aEP aE 第六节第六节 马尔可夫信源马尔可夫信源 马尔可夫信源的熵：马尔可夫信源的熵： 这里这给出结论：这里这给出结论

41、： 112 (|.) mm HHXX XX 表明表明m m阶马尔可夫信源的极限熵等于阶马尔可夫信源的极限熵等于m m阶条件熵。阶条件熵。 根据求条件熵公式还可得到根据求条件熵公式还可得到 1 11 ( ) (| )log ( | ) mm qq mijiji ij HHp e p e ep e e (3) (3) 举举 例例 例例2.2.4 2.2.4 二元二元2 2阶马尔可夫信源，原始信号阶马尔可夫信源，原始信号X X的符号集为的符号集为 X X1 1=0, =0, X X2 2=1=1，其状态空间共有，其状态空间共有n nm m=2=22 2=4=4个不同的状态个不同的状态e e1 1,

42、,e e2 2, ,e e3 3, ,e e4 4，即，即 E E： e e1 1=00,=00,e e2 2=01,=01,e e3 3=10,=10,e e4 4=11=11 状态转移图见右图所示。状态转移图见右图所示。 解：解：p p( (e e1 1/ /e e1 1)= )= p p( (x x1 1/ /e e1 1)=)=p p(0/00)=0.8(0/00)=0.8 p p( (e e2 2/ /e e1 1)= )= p p( (x x2 2/ /e e1 1)=)=p p(1/00)=0.2(1/00)=0.2 p p( (e e3 3/ /e e2 2)= )= p p(

43、 (x x1 1/ /e e2 2)=)=p p(0/01)=0.5(0/01)=0.5 p p( (e e4 4/ /e e2 2)= )= p p( (x x2 2/ /e e2 2)=)=p p(1/01)=0.5(1/01)=0.5 p p( (e e1 1/ /e e3 3)= )= p p( (x x1 1/ /e e3 3)=)=p p(0/10)=0.5(0/10)=0.5 p p( (e e2 2/ /e e3 3)= )= p p( (x x2 2/ /e e3 3)=)=p p(1/10)=0.5(1/10)=0.5 p p( (e e3 3/ /e e4 4)= )=

44、p p( (x x1 1/ /e e4 4)=)=p p(0/11)=0.2(0/11)=0.2 p p( (e e4 4/ /e e4 4)= )= p p( (x x2 2/ /e e4 4)=)=p p(1/11)=0.8(1/11)=0.8 由二元信源由二元信源X X0,10,1得到的状态空间得到的状态空间( (e e1 1, ,e e2 2, ,e e3 3, ,e e4 4) )和相应的一和相应的一 步转移概率构成的步转移概率构成的2 2阶马尔可夫信源模型为阶马尔可夫信源模型为 求出稳定状态下的求出稳定状态下的p p( (e ej j) ) ，称为，称为状态极限概率状态极限概率。

45、将一步转移概率代入上式得将一步转移概率代入上式得 p p( (e e1 1)=0.8 )=0.8 p p( (e e1 1)+0.5 )+0.5 p p( (e e3 3) ) p p( (e e2 2)=0.2 )=0.2 p p( (e e1 1)+0.5 )+0.5 p p( (e e3 3) ) p p( (e e3 3)=0.5 )=0.5 p p( (e e2 2)+0.2 )+0.2 p p( (e e4 4) ) p p( (e e4 4)=0.5 )=0.5 p p( (e e2 2)+0.8 )+0.8 p p( (e e4 4) ) 4 , 3 , 2 , 1)/()()

46、( 0)(, 1)/( 4 , 3 , 2 , 1, )/( 4 1 4 1 4321 jeepepep epeep ji eep eeee i ijij i j ij ij 由 且 解方程组得解方程组得 p p( (e e1 1)= )= p p( (e e4 4)=5/14)=5/14 p p( (e e2 2)= )= p p( (e e3 3)=2/14)=2/14 计算极限熵计算极限熵 )/(8 . 0)/(log)/()( 2 4 1 4 1 12 符号比特 ij ij iji eepeepepHH 第六节第六节 马尔可夫信源马尔可夫信源 例：一个二元二阶马尔可夫信源，信源符号集例

47、：一个二元二阶马尔可夫信源，信源符号集A=0,1A=0,1。 信源开始时，它以概率信源开始时，它以概率p(0)=p(1)=0.5p(0)=p(1)=0.5发出随机变量发出随机变量X1X1。 然后，下一单位时间输出的随机变量然后，下一单位时间输出的随机变量X2X2与与X1X1有依赖关有依赖关 系，由条件概率系，由条件概率p(x2|x1)p(x2|x1)表示：表示： 再下一单元时间输出随机变量再下一单元时间输出随机变量X3X3，而，而X3X3依赖于前面变依赖于前面变 量。依赖关系由条件概率量。依赖关系由条件概率p(x3|x1x2)p(x3|x1x2)表示：表示： 第六节第六节 马尔可夫信源马尔可夫信源 由从第四单位时间开始，任意时刻信源发出的随机变量由从第四单位时间