信息论与编码(傅祖云-讲义)第二章

第二章离散信源及其信息测度第一节信源的数学模型及分类第二节离散信源的信息熵第三节信息熵的基本性质第四节离散无记忆的扩展信源第五节离散平稳信源第六节马尔可夫信源第七节信源剩余度与自然语言的熵信源的主要问题1．如何描述信源（信源的数学建模问题）2．怎样计算信源所含的信息量3．怎样有效的表示信源输出的消息，也就是信源编码问题第一节信源的数学模型及分类在通信系统中，收信者在未收到信息以前，对信源发出什么样的消息是不确定的，是随机的，所以可以用随机变量、随机矢量或随机过程来描述信源输出的消息，或者说用一个样本空间及其概率测度来描述信源。不同的信源根据其输出消息的不同的随机性质进行分类。信源的定义及分类离散信源连续信源信源是发出消息的源，信源输出以符号形式出现的具体消息。按照信源发出的消息在时间上和幅度上的分布情况：是指发出在时间和幅度上都是离散分布的离散消息的信源，如文字、数字、数据等符号都是离散消息。是指发出在时间和幅度上都是连续分布的连续消息（模拟消息）的信源，如语言、图像、图形等都是连续消息。时间（空间)取值信源种类举例数学描述离散离散离散信源（数字信源）文字、数据、离散化图象离散随机变量序列离散连续连续信号跳远比赛的结果、语音信号抽样以后连续随机变量序列连续连续波形信源（模拟信源）语音、音乐、热噪声、图形、图象随机过程连续离散不常见第一节信源的数学模型及分类1、离散信源数学模型如下：1212......nnaaaXpppP11qiip集合X中，包含该信源包含的所有可能输出的消息，集合P中包含对应消息的概率密度，各个消息的输出概率总和应该为1。例：掷骰子；抛硬币；天气预报第一节信源的数学模型及分类2、连续信源数学模型如下：(,)()()Xabpxpx()1bapxdx每次只输出一个消息，但消息的可能数目是无穷多个。例：电压、温度等。发出单个符号的无记忆信源离散无记忆信源发出符号序列的无记忆信源离散信源发出符号序列的有记忆信源离散有记忆信源发出符号序列的马儿可夫信源离散信源的进一步分类发出单个符号的信源发出符号序列的信源指信源每次只发出一个符号代表一个消息．指信源每次发出一组含二个以上符号的符号序列代表一个消息．根据随机变量间是否统计独立将信源分为有记忆信源和无记忆信源。离散无记忆信源离散有记忆信源所发出的各个符号是相互独立的，发出的符号序列中的各个符号之间没有统计关联性，各个符号的出现概率是它自身的先验概率。所发出的各个符号的概率是有关联的。有记忆信源符号间的概率关联性可用两种方式：一种是用信源发出的一个符号序列的整体概率（即联合概率）反映有记忆信源的特征．一种限制记忆长度，即某一个符号出现的概率只与前面一个或有限个符号有关，而不依赖更前面的那些符号，这样的信源可以用信源发出符号序列内各个符号之间的条件概率来反映记忆特征，这就是发出符号序列的马尔可夫信源．根据各维随机变量的概率分布是否随时间的推移而变化将信源分为平稳信源和非平稳信源一个实际信源的统计特性往往是相当复杂的，要想找到精确的数学模型很困难。实际应用时常常用一些可以处理的数学模型来近似。随机序列，特别是离散平稳随机序列是我们研究的主要内容。第二节离散信源的信息熵1、自信息我们认为，一个字符它所携带的信息量是和该字符出现的概率有关，概率可以表征自信息量的大小()[()]iiIafPa根据客观事实和人们的习惯概念，应满足以下条件:第二节离散信源的信息熵（2）当()1iPa时()0ifP()ifP（3）当时()0iPa（4）两个独立事件的联合信息量应等于它们分别的信息量之和。(1)应是先验概率的单调递减函数，即当时()ifp1122()()PaPa12()()fPfP第二节离散信源的信息熵根据上述条件可以从数学上证明这种函数形式是对数函数，即：1()log()iiIaPa()iIa有两个含义：1、当事件发生前，表示该事件发生的不确定性；2、当事件发生后，表示该事件所提供的信息量．自信息量的单位取决于对数所取的底，若以2为底，单位为比特，以e为底，单位为奈特，以10为底，单位为哈特,通常取比特为单位第二节离散信源的信息熵例：设天气预报有两种消息，晴天和雨天，出现的概率分别为1/4和3/4，我们分别用来表示晴天，以来表示雨天，则我们的信源模型如下：1a2a1,2()1/4,3/4aaXpx1()log42Ia24()log0.4153Ia第二节离散信源的信息熵我们定义自信息的数学期望为信源的平均信息量11()[log]()log()()qiiiiHXEPaPapa信息熵具有以下两种物理含义：1、表示信源输出前信源的平均不确定性2、表示信源输出后，每个符号所携带的平均信息量2、信息熵例：天气预报，有两个信源1,21()1/4,3/4aaXpx1,22()1/2,1/2aaXpx1134()log4log0.809443HX211()log2log2122HX则：说明第二个信源的平均不确定性更大一些第二节离散信源的信息熵第三节信息熵的基本性质熵函数可以表示为：HXHpppppniiin()(,)log121ppiniini11012,(,,...,)第三节信息熵的基本性质性质1：非负性H(X)≥0由于0≤pi≤1,所以logpi≤0H(X)≥0。性质2：对称性HpppHppppnnn(,,...)(,,,...)12121根据加法交换律可以证明，当变量交换顺序时熵函数的值不变。信源的熵只与概率空间的总体结构有关，而与个概率分量对应的状态顺序无关；第三节信息熵的基本性质性质3：确定性；HHH(,)(,)(,,,...)100110000当信源X的信源空间[X，P]中。任一个概率分量等于1，根据完备空间特性，其它概率分量必为0，这时信源为一个确知信源，其熵为0。如果一个信源的输出符号几乎必然为某一状态，那么这个信源没有不确定性，信源输出符号后不提供任何信息量。第三节信息熵的基本性质性质4：扩展性112120lim(,,...,,)(,,...,)qqqqHpppHppp这说明信源空间中增加某些概率很小的符号，虽然当发出这些符号时，提供很大的信息量，但由于其概率接近于0，在信源熵中占极小的比重，使信源熵保持不变。第三节信息熵的基本性质性质5：极值性12(,,...,)(1/,1/,...,1/)logqHpppHqqqq上式表明，对于具有q个符号的离散信源，只有在q个信源符号等可能出现的情况下，信源熵才能达到最大值，这也表明等概分布的信源的平均不确定性最大，这是一个很重要得结论，称为最大离散熵定理例：对于一个二元信源H(X)=H(1/2,1/2)=log2=1bit/信源符号第四节离散无记忆的扩展信源实际信源输出的消息往往是时间上或空间上的一系列符号，如电报系统，序列中前后符号间一般是有统计依赖关系的。我们先讨论离散无记忆信源，此时，信源序列的前后符号之间是统计独立的如在二元系统中，我们可以把两个二元数字看成一组，会出现四种可能情况：00、01、10和11，我们可以把这四种情况看成一个新的信源称为二元无记忆信源的二次扩展信源，相应的，如果把N个二元数字看成一组，则新的信源称为二元无记忆信源的N此扩展信源。第四节离散无记忆的扩展信源一般情况设一个离散无记忆信源为：piin111212...()()...()NNNqqXpppP则该信源的N次扩展信源为：1212......nnaaaXpppP第四节离散无记忆的扩展信源其中：12()()()...()iiiiNPPaPaPa根据信息熵的定义：()()log()NNNNXHXPXPX可以证明，对于离散无记忆的扩展信源()()NHXNHX例:离散无记忆信源的N次扩展信源离散无记忆信源为：X:{a1,a2,a3};P(X):{1/4,1/2,1/4}2次扩展信源为：2X:{A1…A9}信源的9个符号为：A1=a1a1A2=a1a2A3=a1a3A4=a2a1A5=a2a2A6=a2a3A7=a3a1A8=a3a2A9=a3a3第四节离散无记忆的扩展信源第四节离散无记忆的扩展信源其概率关系为:A1A2A3A4A5A6A7A8A91/161/81/161/81/41/81/161/81/16计算可知2()3HXbit()1.5HXbit2()2()HXHX第五节离散平稳信源一般来说，信源的前后消息之间有前后依赖关系，可以用随机矢量描述：12(...,,,...,...)iXXXX信源在某一时刻发出什么样的值取决于两方面1、这一时刻该变量的概率分布2、这一时刻以前发出的消息如一个人讲话我们现在讨论平稳的随机序列，所谓平稳是指序列的统计性质与时间的推移无关（两个任意时刻信源发出相同符号的概率分布完全相同）。1、离散平稳信源的数学定义第五节离散平稳信源2、二维平稳信源及其信息熵最简单的平稳信源——二维平稳信源，信源发出序列中只有前后两个符号间有依赖关系，我们可以对其二维扩展信源进行分析。信源的概率空间:连续两个信源符号出现的联合概率分布为：1212,,,()1(),(),,()()qiqaaaXpapapapaPXqi=1且1()()1qqijijjPaaPaai=1且第五节离散平稳信源已知符号出现后，紧跟着出现的条件概率为：iaja()(|)()ijjiiPaaPaaPa由二维离散信源的发出符号序列的特点可以把其分成每两个符号一组，每组代表新信源中的一个符号。并假设组与组之间是统计独立的，互不相关的。12XXX得到一个新的离散无记忆信源，其联合概率空间为：12XX1212()XXPxx11121,,...,,()()(|)qqqqijijiaaaaaaaaPaaPaPaa第五节离散平稳信源1211()()log()qqijijijHXXPaaPaa根据信息熵的定义，可得：（1）联合熵可以表征信源输出长度为2的平均不确定性，或所含有的信息量。因此可以用作为二维平稳信源的信息熵的近似值121/2()HXX第五节离散平稳信源(2)条件熵211(|)(|)log(|)qijijijHXXaPaaPaa则：21211(|)()(|)qiiiHXXPaHXXa11()(|)log(|)qqijijiijPaPaaPaa11()log(|)qqijjiijPaaPaa第五节离散平稳信源另外还可以得到：21(|)()HXXHX1212()()()2()HXXHXHXHX只有信源统计独立时等号成立。可以证明：12121()()(|)HXXHXHXX[例2-15]设某二维离散信源的原始信源的信源空间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/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.5bit/符号条件熵：H(X2/X1)=1.4bit/符号可见：H(X2/X1)H(X)二维信源的熵：H(X1X2)=H(X1)+H(X2/X1)=2.9bit/消息每个信源符号提供的平均信息量为：H2(X1X2)=H(X1X2)/2=1.45bit/符号。第五节离散平稳信源第五节离散平稳信源我们现在有两种方法去近似信源的实际熵，一种是平均符号熵H(X1X2)/2为1.45bit，但这