数据通信第二章

1、第二章第二章 离散信源及其信息测度离散信源及其信息测度 第一节 信源的数学模型及分类第二节 离散信源的信息熵第三节 信息熵的基本性质第四节 离散无记忆的扩展信源第五节 离散平稳信源第六节 马尔可夫信源第七节 信源剩余度与自然语言的熵n 信源的主要问题信源的主要问题 1 1如何描述信源（信源的数学建模问题）描述信源（信源的数学建模问题） 2 2怎样计算信源所含的信息量怎样计算信源所含的信息量 3 3怎样有效的表示信源输出的消息，也就是信源编码问题怎样有效的表示信源输出的消息，也就是信源编码问题第一节 信源的数学模型及分类 在通信系统中，收信者在未收到信息以前，对信源发出什么样的消息是不确定的，是

2、随机的，所以可以用随机变量、随机矢量或随机过程来描述信源输出的消息，或者说用一个样本空间及其概率测度来描述信源。 不同的信源根据其输出消息的不同的随机性质进行分类。信源的定义及分类信源的定义及分类n离散信源n连续信源n是指发出在时间和幅度上都是离散分布的离是指发出在时间和幅度上都是离散分布的离散消息的信源，如文字、数字、数据等符号散消息的信源，如文字、数字、数据等符号都是离散消息。都是离散消息。是指发出在时间和幅度上都是连续分布的连是指发出在时间和幅度上都是连续分布的连续消息（模拟消息）的信源，如语言、图像、续消息（模拟消息）的信源，如语言、图像、图形等都是连续消息。图形等都是连续消息。离散离

3、散离散信源（数字信源）文字、数据、离散化图象 离散随机变量序列 离散连续连续信号跳远比赛的结果、语音信号抽样以后 连续随机变量序列 连续连续波形信源（模拟信源） 语音、音乐、热噪声、图形、图象 随机过程 连续离散不常见第一节 信源的数学模型及分类1、离散信源 数学模型如下：1212.nnaaaXpppP11qiip 集合X中，包含该信源包含的所有可能输出的消息，集合P中包含对应消息的概率密度，各个消息的输出概率总和应该为1。 例：掷骰子；抛硬币；天气预报第一节 信源的数学模型及分类2、连续信源 数学模型如下：( , )( )( )Xa bp xp x( )1bap x dx 每次只输出一个消息

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

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

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

7、，要想找到精确的数学模型很困难。实际应用时常常用一些可以处理可以处理的数学模型来近似。随机序列，特别是离散平稳随机序列是我们研究的主要内容。第二节 离散信源的信息熵1、自信息 我们认为，一个字符它所携带的信息量是和该字符出现的概率有关，概率可以表征自信息量的大小 ( ) ( )iiI af P a 根据客观事实和人们的习惯概念，应满足以下条件:第二节 离散信源的信息熵（2）当( )1iP a时( )0if P ( )if P （3）当 时()0iP a（4）两个独立事件的联合信息量应等于它们分别的信息量之和。(1) 应是先验概率的单调递减函数，即当 时()if p1122( )( )P aP

8、a12( )()f Pf P第二节 离散信源的信息熵 根据上述条件可以从数学上证明这种函数形式是对数函数，即： 1()log()iiI aP a( )iI a有两个含义： 1、当事件发生前，表示该事件发生的不确定性；2、当事件发生后，表示该事件所提供的信息量 自信息量的单位取决于对数所取的底，若以2为底，单位为比特，以e为底，单位为奈特，以10为底，单位为哈特,通常取比特为单位第二节 离散信源的信息熵例：设天气预报有两种消息，晴天和雨天，出现的概率分别为1/4和3/4，我们分别用 来表示晴天，以 来表示雨天，则我们的信源模型如下： 1a2a1,2( )1/ 4,3/ 4aaXp x1( )lo

9、g42I a 24()log0.4153I a第二节 离散信源的信息熵我们定义自信息的数学期望为信源的平均信息量11()log( )log( )( )qiiiiH XEP aP ap a 信息熵具有以下两种物理含义：1、表示信源输出前信源的平均不确定性2、表示信源输出后，每个符号所携带的平均信息量2、信息熵例：天气预报，有两个信源1,21( )1/4,3/4aaXp x1,22( )1/2,1/2aaXp x1134()log4log0.809443H X 211()log2log2122H X则：说明第二个信源的平均不确定性更大一些第二节 离散信源的信息熵第三节 信息熵的基本性质熵函数可以表

10、示为：HXHpppppniiin()(,)log 121ppiniini1101 2,(, ,.,)第三节 信息熵的基本性质性质1：非负性H(X)0由于0pi1,所以logpi0，则总有H(X)0。性质2：对称性 H pppH ppppnnn(,.)(,.)12121n根据加法交换律可以证明，当变量交换顺序时熵函数的值不变。n信源的熵只与概率空间的总体结构有关，而与个概率分量对应的状态顺序无关；第三节 信息熵的基本性质性质3：确定性；HHH( , )( , )( , , ,. )1 00 11 0 000当信源X的信源空间X，P中。任一个概率分量等于1，根据完备空间特性，其它概率分量必为0，这

11、时信源为一个确知信源，其熵为0。如果一个信源的输出符号几乎必然为某一状态，那么这个信源没有不确定性，信源输出符号后不提供任何信息量。第三节 信息熵的基本性质性质4：扩展性112120lim(,., )(,.,)qqqqHp ppHp pp 这说明信源空间中增加某些概率很小的符号，虽然当发出这些符号时，提供很大的信息量，但由于其概率接近于0，在信源熵中占极小的比重，使信源熵保持不变。 第三节 信息熵的基本性质性质5 ：极值性12( ,.,)(1/ ,1/ ,.,1/ )logqH p ppHqqqq 上式表明，对于具有q个符号的离散信源，只有在q个信源符号等可能出现的情况下，信源熵才能达到最大值

12、，这也表明等概分布的信源的平均不确定性最大，这是一个很重要得结论，称为最大离散熵定理最大离散熵定理例：对于一个二元信源 H(X)=H(1/2,1/2)=log2=1bit/信源符号第四节 离散无记忆的扩展信源 实际信源输出的消息往往是时间上或空间上的一系列符号，如电报系统，序列中前后符号间一般是有统计依赖关系的。 我们先讨论离散无记忆信源，此时，信源序列的前后符号之间是统计独立的 如在二元系统中，我们可以把两个二元数字看成一组，会出现四种可能情况：00、01、10和11，我们可以把这四种情况看成一个新的信源称为二元无记忆信源的二次扩展信源，相应的，如果把N个二元数字看成一组，则新的信源称为二元

13、无记忆信源的N此扩展信源。第四节 离散无记忆的扩展信源一般情况设一个离散无记忆信源为：piin111212.()().()NNNqqXpppP 则该信源的N次扩展信源为：1212.nnaaaXpppP第四节 离散无记忆的扩展信源其中：12()() (). ()iiiiNPP aP aP a根据信息熵的定义：()()log()NNNNXH XP XP X 可以证明，对于离散无记忆的扩展信源()()NH XNH X例例: 离散无记忆信源的N次扩展信源离散无记忆信源为：X:a1,a2,a3; P(X):1/4, 1/2, 1/42次扩展信源为：2X:A1A9信源的9个符号为：A1=a1a1A2=a1

14、a2A3=a1a3A4=a2a1A5=a2a2A6=a2a3A7=a3a1A8=a3a2A9=a3a3第四节 离散无记忆的扩展信源第四节 离散无记忆的扩展信源其概率关系为 :A1A2A3A4A5A6A7A8A91/16 1/81/16 1/81/41/81/16 1/81/16计算可知2()3H Xbit()1.5H Xbit2()2()H XH X第五节 离散平稳信源 一般来说，信源的前后消息之间有前后依赖关系，可以用随机矢量描述：12(.,.,.)iXXXX信源在某一时刻发出什么样的值取决于两方面1、这一时刻该变量的概率分布2、这一时刻以前发出的消息 如一个人讲话 我们现在讨论平稳的随机序

15、列，所谓平稳是指序列的统计性质与时间的推移无关（两个任意时刻信源发出相同相同符号的概率分布完全相同）。1、离散平稳信源的数学定义第五节 离散平稳信源2、二维平稳信源及其信息熵 最简单的平稳信源二维平稳信源，信源发出序列中只有前后两个符号间有依赖关系，我们可以对其二维扩展信源进行分析。信源的概率空间:连续两个信源符号出现的联合概率分布为：1212,()1(),(),()()qiqaaaXp ap ap ap aP Xqi=1且1()()1qqijijjP a aP a ai=1且第五节 离散平稳信源已知符号 出现后，紧跟着 出现的条件概率为：iaja()(|)()ijjiiPa aPaaPa 由

16、二维离散信源的发出符号序列的特点可以把其分成每两个符号一组，每组代表新信源 中的一个符号。并假设组与组之间是统计独立的，互不相关的。 12XX X得到一个新的离散无记忆信源 ，其联合概率空间为：12X X1212()X XP x x11121,.,()() (|)qqqqijijia a a aaaa aP a aP a P aa第五节 离散平稳信源1211()()log ()qqijijijH X XP a aP a a 根据信息熵的定义，可得：（1）联合熵可以表征信源输出长度为2的平均不确定性，或所含有的信息量。因此可以用 作为二维平稳信源的信息熵的近似值121/2()H X X第五节 离

17、散平稳信源(2)条件熵211(|)(|)log(|)qijijijH XXaP aaP aa 则：21211(|)()(|)qiiiH XXP a H XXa11() (|)log(|)qqijijiijP a P aaP aa 11()log(|)qqijjiijP a aP aa 第五节 离散平稳信源另外还可以得到：21(|)()H XXH X1212()()()2()H X XH XH XH X只有信源统计独立时等号成立。可以证明：12121()()(|)H X XH XH XX例2-15 设某二维离散信源的原始信源的信源空间 X=x1,x2,x3; P(X)=1/4, 1/4, 1/2

18、, 一维条件概率为： 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/x3)=0; p(x2/x3)=1/4; p(x3/x3)=3/4;第五节 离散平稳信源例2-15 原始信源的熵为： H(X)=1.5 bit/符号条件熵： H(X2/X1)=1.4 bit/符号可见： H(X2/X1)H(X)二维信源的熵：H(X1X2)=H(X1)+H(X2/X1)=2.9 bit/消息每个信源符号提供的平均信息量为： H2(X1X2)=H(X1X2)/2=1.45 bit/符号。

19、第五节 离散平稳信源第五节 离散平稳信源我们现在有两种方法去近似信源的实际熵两种方法去近似信源的实际熵，p一种是平均符号熵H(X1X2)/2为1.45bit，但这种方法不太准确，因为它把两个消息看成一组，认为两组之间是统计独立的，实际上它们之间是有关联的；p另一种是我们可以用条件熵来近似，H(X2/X1)为1.4bit，到底那一种正确呢？我们可以通过对一般离散平稳信源的分析来找到这个答案。分析：我们用2()HX来近似信源的实际熵第五节 离散平稳信源3、离散平稳信源的极限熵平均符号熵121()(.)NNHXH X XXN条件熵121(|.)NNH XX XX有以下几点性质 （1）条件熵随N的增加

20、是非递增的 （2）N给定时，平均符号熵大于等于条件熵 （3）平均符号熵随N的增加是非递增的 （4）121lim()lim(|.)NNNNNHHXH XX XXH称 为极限熵。 第五节 离散平稳信源 可以证明，对于二维离散平稳信源，条件熵等于极限熵，因此条件熵就是二维离散平稳信源的真实熵 对于一般信源，求出极限熵是很困难的，然而，一般来说，取N不大时就可以得到与极限熵非常接近的条件熵和平均符号熵，因此可以用条件熵条件熵和平均符号熵平均符号熵来近似极限熵第六节 马尔可夫信源 在很多信源的输出序列中，符号之间的依赖关系是有限的，任何时刻信源符号发生的概率只与前边已经发出的若干个符号有关，而与更前面的

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

22、（1）某一时刻信源输出的符号的概率只与当前所处的状态有关，而与以前的状态无关。即111(|, )(|)lklilkljlkliP xa sE xa sEP xa sE当符号输出概率与时刻L无关，称为具有时齐性。即(|)(|),(|)1klklikikiaAP xasEP aEP aE第六节 马尔可夫信源（2）信源的下一个状态由当前状态和下一刻的输出唯一确定。 条件（2）表明，若信源处于某一状态 ，当它发出 一个符号后，所处的状态就变了，一定转移到另一状态。 状态的转移依赖于发出的信源符号，因此任何时刻信源处在什么状态完全由前一时刻的状态和发出的符号决定。iE第六节 马尔可夫信源例：二阶马尔可夫

23、信源，原始符号集为1,0， 条件概率定为：P(0|00)=P(1|11)=0.8 P(1|00)=P(0|11)=0.2 P(0|01)=P(0|10)=P(1|01)=P(1|10)=0.5 由此可见，信源共有22=4种状态 E：E1=00,E2=01,E3=10,E4=11第六节 马尔可夫信源状态之间有转移概率，p(e2/e1)=p(e3/e4)=0.2p(e2/e4)=p(e1/e3)=p(e2/e3)=p(e3/e2)=0.5P(e1/e1)=p(e4/e4)=0.8其状态转移图如下页。在状态转换图中，把信源的每一种状态用圆圈表示，用有向箭头表示信源发出某一符号后由一种状态到另一状态的

24、转移。第六节 马尔可夫信源 01 100:0.51:0.20:0.2 000:0.8 111:0.81:0.50:0.51:0.5 由上例可知，m阶马尔可夫信源符号集共有q个符号，则信源共有 个不同状态。信源在某一时刻时，必然处于某一种状态，等到下一个字符输出时，转移到另外一个状态。mq举 例例例2.2.3 设信源符号设信源符号 Xx1, x2, x3 ，信源所处的状态，信源所处的状态Se1, e2, e3, e4, e5 。各状态之间的转移情况由图。各状态之间的转移情况由图2.2.1给出。给出。将图中信源在将图中信源在ei状态下发符号状态下发符号xk 的条件概率的条件概率p(xk /ei)用

25、矩阵表示用矩阵表示由矩阵看出：由矩阵看出：由图中看出：由图中看出：由图中可得状态的一步转移概率：由图中可得状态的一步转移概率：该信源满足马尔可夫信源定义。该信源满足马尔可夫信源定义。214121414143214141215432132100100eeeeexxx315 , 4 , 3 , 2 , 1, 1)/(kikiexp0),/(1),/(1),/(0),/(1123112211111112eSxXeSPeSxXeSPeSxXeSPeSxXeSPllllllllllll41434143212141412154321000000000000000054321eeeeeeeeee第六节 马尔

26、可夫信源定义 (P58)为各状态的极限概率，则时齐、遍历的马尔可夫信源的熵为 ()iQ E1()(|)JiiiHQ E H X E11() (|)log(|)qJikikiikQ E P aEP aE 第六节 马尔可夫信源马尔可夫信源的熵：这里这给出结论：112(|.)mmHHXX XX表明m阶马尔可夫信源的极限熵等于m阶条件熵。根据求条件熵公式还可得到111( ) (| )log ( | )mmqqmijijiijHHp e p e ep e e(3) 举 例例例2.2.4 二元二元2阶阶马尔可夫信源，原始信号马尔可夫信源，原始信号X的符号集为的符号集为X1=0, X2=1，其状态空间共有，

27、其状态空间共有nm=22=4个不同的状态个不同的状态e1,e2,e3,e4，即，即 E：e1=00,e2=01,e3=10,e4=11 状态转移图见右图所示。状态转移图见右图所示。解：解：p(e1/e1)= p(x1/e1)=p(0/00)=0.8 p(e2/e1)= p(x2/e1)=p(1/00)=0.2 p(e3/e2)= p(x1/e2)=p(0/01)=0.5 p(e4/e2)= p(x2/e2)=p(1/01)=0.5 p(e1/e3)= p(x1/e3)=p(0/10)=0.5 p(e2/e3)= p(x2/e3)=p(1/10)=0.5 p(e3/e4)= p(x1/e4)=p

28、(0/11)=0.2 p(e4/e4)= p(x2/e4)=p(1/11)=0.8 由二元信源由二元信源X0,1得到的状态空间得到的状态空间(e1,e2,e3,e4)和相应的一和相应的一步转移概率构成的步转移概率构成的2阶阶马尔可夫信源模型为马尔可夫信源模型为 求出稳定状态下的求出稳定状态下的p(ej) ，称为，称为状态极限概率状态极限概率。 将一步转移概率代入上式得将一步转移概率代入上式得p(e1)=0.8 p(e1)+0.5 p(e3)p(e2)=0.2 p(e1)+0.5 p(e3)p(e3)=0.5 p(e2)+0.2 p(e4)p(e4)=0.5 p(e2)+0.8 p(e4)4 ,

29、 3 , 2 , 1)/()()(0)(, 1)/(4 , 3 , 2 , 1,)/(41414321jeepepepepeepjieepeeeeiijijijijij由且 解方程组得解方程组得p(e1)= p(e4)=5/14p(e2)= p(e3)=2/14 计算极限熵计算极限熵)/(8 .0)/(log)/()(2414112符号比特ijijijieepeepepHH第六节 马尔可夫信源例：一个二元二阶马尔可夫信源，信源符号集A=0,1。信源开始时，它以概率p(0)=p(1)=0.5发出随机变量X1。然后，下一单位时间输出的随机变量X2与X1有依赖关系，由条件概率p(x2|x1)表示： 再下一单元时间输出随机变量X3，而X3依赖于前面变量。依赖关系由条件概率p(x3|x1x2)表示：x1x1x20100.30.410.70.6第六节 马尔可夫信源由从第四单位时间开始，任意时刻信源发出的随机变量Xi只与前面二个单位时间的随机变量有关，根据提议可得信源的状态转移图：x1x2x1x2x1x2x1x2X30001101100.40.20.30.410.60.80.70.621312(|)(|)(3)