第二章 离散信源及其信息测度

第一章内容回顾信息论研究的对象、目的和内容信息论发展简史与现状(了解)信息论的形成与发展信息论方法的应用及其取得的成果信息的概念信息消息、信号、信息的区别与联系1第二章：离散信源及信息测度

孙桂萍2信息论对信源研究的内容信源的建模与分类：根据消息的随机性质对信源分类离散信源的信息熵及性质：什么是信息熵；九大性质几种具体信源：离散平稳信源马尔可夫信源3信源特性与分类信源的统计特性1）什么是信源？信源是信息的来源，实际通信中常见的信源有：语音、文字、图像、数据…。在信息论中，信源是产生消息（符号）、消息（符号）序列以及连续消息的来源，数学上，信源是产生随机变量，随机序列和随机过程的源。2）信源的主要特性信源的最基本的特性是具有随机不确定性，它可用概率统计特性来描述。4信源特性与分类单消息（符号）信源：离散信源连续变量信源平稳信源无/有记忆信源马尔可夫信源随机波形信源※5单消息（符号）信源它是最简单也是最基本的信源，是组成实际信源的基本单元。它可以用信源取值随机变量X和对应的概率分布P(x)共同组成的概率空间来表示。离散信源与概率空间的一一对应关系：当信源给定，其相应的概率空间就已给定；反之，如果概率空间给定，这就表示相应的信源已给定。所以，概率空间能表征这离散信源的统计特性，因此有时也把这个概率空间称为信源空间。

表示随机现象各种结果的变量6单消息（符号）信源－－离散信源特点：这些信源可能输出的消息数是有限的或可数的，而且每次只输出其中一个消息。因此，可以用一维离散型随机变量X来描述这个信源输出的消息。这个随机变量X的样本空间就是符号集A；而X的概率分布就是各消息出现的先验概率，信源的概率空间必定是一个完备集。在实际情况中，存在着很多这样的信源。例如投硬币、计算机的代码、电报符号、阿拉伯数字码等等。这些信源输出的都是单个符号(或代码)的消息，它们符号集的取值是有限的或可数的。我们可用一维离散型随机变量X来描述这些信源的输出。它的数学模型就是离散型的概率空间：7单消息（符号）信源－－离散信源对离散信源的建模例：对于二进制数据/数字信源：U={0,1}，则有

重点掌握：形式，每个符号的含义8单消息（符号）信源－－连续信源有的信源虽输出是单个符号(代码)的消息，但其可能出现的消息数是不可数的无限值，即输出消息的符号集A的取值是连续的，或取值是实数集(-∞，∞)。例如，语音信号、热噪声信号某时间的连续取值数据，遥控系统中有关电压、温度、压力等测得的连续数据。这些数据取值是连续的，但又是随机的。我们可用一维的连续型随机变量X来描述这些消息。这种信源称为连续信源，其数学模型是连续型的概率空间：

9单消息（符号）信源－－连续信源其中：对于连续信源的建模:10随机矢量描述的信源很多实际信源输出的消息往往是由一系列符号序列所组成的。可以把这种信源输出的消息看做时间上或空间上离散的一系列随机变量，即为随机矢量。这时，信源的输出可用N维随机矢量X=(X１，X２…XN)来描述，其中N可为有限正整数或可数的无限值。这N维随机矢量X有时也称为随机序列。11平稳信源一般来说，信源输出的随机序列的统计特性比较复杂，分析起来也比较困难。为了便于分析，我们假设信源输出的是平稳的随机序列，也就是序列的统计性质与时间的推移无关。很多实际信源也满足这个假设。若信源输出的随机序列X=(Ｘ１，Ｘ２，…，ＸＮ)中，每个随机变量Xi(i=1,2,…，N)都是取值离散的离散型随机变量，即每个随机变量Xi的可能取值是有限的或可数的。而且随机矢量X的各维概率分布都与时间起点无关，也就是在任意两个不同时刻随机矢量X的各维概率分布都相同。这样的信源称为离散平稳信源。如中文自然语言文字，离散化平面灰度图像都是这种离散型平稳信源。与之对应的还有连续平稳信源。12无记忆信源在某些简单的离散平稳信源中，信源先后发出的一个个符号彼此是统计独立的。也就是说信源输出的随机矢量X=(X１X２…XＮ）中，各随机变量Xi(i=1,2,…N)之间是无依赖的、统计独立的，则N维随机矢量的联合概率分布满足P(X)=P１（Ｘ１）P２（Ｘ２）…PＮ（ＸＮ）由上述的信源空间［X，P(x)］描述的信源X为离散无记忆信源。这信源在不同时刻发出的符号之间是无依赖的，彼此统计独立的。13离散无记忆信源X的N次扩展信源N次扩展信源是由离散无记忆信源输出N长的随机序列构成的信源。离散无记忆信源的N次扩展信源的数学模型是X信源空间的N重空间。14二元无记忆信源的二次扩展信源例：一个消息是由“0”，“1”组成的一串序列：011000111000分成六组，即每两个二元数字为一组：011000111000此时的信源可以看作是能输出四个消息：00，01，10，11的一个新信源——也就称其为二元无记忆信源的二次扩展信源。15有记忆信源

一般情况下，信源在不同时刻发出的符号之间是相互依赖的。也就是信源输出的平稳随机序列X中，各随机变量Xi之间是有依赖的。例如，在汉字组成的中文序列中，只有根据中文的语法、习惯用语、修辞制约和表达实际意义的制约所构成的中文序列才是有意义的中文句子或文章。所以，在汉字序列中前后文字的出现是有依赖的，不能认为是彼此不相关的。其他如英文，德文等自然语言都是如此。这种信源称为有记忆信源。我们需在N维随机矢量的联合概率分布中，引入条件概率分布来说明它们之间的关联。16马尔可夫信源表述有记忆信源要比表述无记忆信源困难得多。实际上信源发出的符号往往只与前若干个符号的依赖关系强，而与更前面的符号依赖关系弱。为此，可以限制随机序列的记忆长度。当记忆长度为m+1时，称这种有记忆信源为m阶马尔可夫信源。也就是信源每次发出的符号只与前m个符号有关，与更前面的符号无关。17随机波形信源更一般地说，实际信源输出的消息常常是时间和取值都是连续的。例如，语音信号X(t)、热噪声信号n(t)、电视图像信号X(x0,y0,t)等时间连续函数。同时，在某一固定时间t０，它们的可能取值又是连续的和随机的。对于这种信源输出的消息，可用随机过程来描述。称这类信源为随机波形信源。随机波形信源的处理方式：在某种条件下可以转换成随机变量间统计独立的随机序列。如果随机过程是平稳的随机过程，时间离散化后可转换成平稳的随机序列。这样，随机波形信源可以转换成连续平稳信源来处理。若再对每个取样值(连续型的)经过分层(量化)，就可将连续的取值转换成有限的或可数的离散值。也就可把连续信源转换成离散信源来处理。18信息无处不在，但：信息用什么表示？如何表示？不确定性＝携载的信息可用随机变量的不确定性或随机性作为信息的表示19非负性连续性可加性等概时与取值空间N的关系（单调增）与发生的概率P的关系（单调减）考察、分析信息的特征20自信息自信息消息的不确定性即为它的自信息:考虑一定的条件,得此函数为对数形式：式（2.22）21信息量的单位

自信息的单位与公式中的对数取底有关。通信与信息中最常用的是以2为底，这时单位为比特（bit）；理论推导中用以e为底较方便，这时单位为奈特（Nat）；工程上用以10为底较方便，这时单位为哈特（Hart）。它们之间可以引用对数换底公式进行互换。比如：1bit=0.693Nat=0.301Hart22对于单个消息随机变量X，出现某个消息，对应概率为，这时可获得的信息量为，则有：通过数学公式推导解释：小概率事件，一旦出现必然使人感到意外，因此产生的信息量就大；几乎不可能事件一旦出现，将是一条爆炸性的新闻，一鸣惊人。大概率事件，是预料之中的，即使发生，也没什么信息量，特别是当必然事件发生了，它不会给人以任何信息量。注：I－－自信息23当事件ai发生以前，表示事件ai发生的不确定性当事件ai发生以后表示事件ai所含有（所提供）的信息量自信息的含义24互信息(教材P7)信源发送消息,而由于干扰，在接收端收到的为消息，此时获得的信息量——互信息，即最初的不确定性减去尚存在的不确定性。尚存在的不确定性为条件概率的函数，即：互信息消除的不确定性为先验的不确定性减去尚存在的不确定性。式（1.2）25例2.1:试验前：H(x)=log8=3(bit/符号)H(x2)－H(x3)

=1－－获得1bit信息量XP（x）＝123456781/81/81/81/81/81/81/81/812312345678第二次测量后：X2P（x2）＝123456781/21/2000000H(x2)=log2=1(bit/符号)第三次测量后：X3P（x3）＝1234567810000000H(x3)=log1=0(bit/符号)第一次测量后：X1P（x1）＝123456781/41/41/41/40000H(x1)=log4=2(bit/符号)H(x)－H(x1)

=1－－获得1bit信息量H(x1)－H(x2)

=1－－获得1bit信息量H(X)表示在获知哪个灯泡是坏的情况前，关于哪个灯泡已损坏的平均不确定性，即要确定哪个灯泡是坏的，至少需要获得3个bit的信息量，才能完全消除不确定性。26熵熵的引入香农熵与热力学熵的关系熵可以作为信息的度量熵函数的性质联合熵和条件熵27熵的引入一个离散随机变量X，以不同的取值概率有N个可能取值,

XP（x）＝a1a2…aNp1p2…pN信息论关心：X的不确定性不确定性－－大，获取的信息－－多28熵的引入不确定性分析：随机变量X、Y、ZXP（x）＝a1a20.010.99ZP（z）＝a1a2a3a4a50.20.20.20.20.2YP（y）＝a1a20.50.5问题：能否度量、如何度量？？小大29香农指出：存在熵函数

满足先验条件1、连续性条件：是的连续函数2、等概时为单调增函数：是N的增函数3、可加性条件：多次试验确定取值时，X在各次试验中的不确定性可加。结论：唯一的形式：C=常数>0，即：式2.2330香农熵与热力学中热熵的关系熵这个名词是香农从物理学中的统计热力学借用过来的，在物理学中称它为热熵是表示分子混乱程度的一个物理量，这里，香农引用它来描述信源的平均不确定性，含义是类似的。但是在热力学中已知任何孤立系统的演化，热熵只能增加不能减少；而在信息论中，信息熵正相反，一般只会减少，不会增加。所以有人称信息熵为负热熵。二者还有一个重大差别：热熵是有量纲的，而香农熵是无量纲的。31（仍有不确定性）熵可以作为信息的量度对于随机变量而言：试验前－－试验后－－各取值的概率分布确切取值（0）（不确定性）一定的确切性多次试验后－－通过试验－－消除了不确定性－－获得了信息－－信息的数量＝熵32例2.1:试验前：H(x)=log8=3(bit/符号)H(x2)－H(x3)

=1－－获得1bit信息量XP（x）＝123456781/81/81/81/81/81/81/81/812312345678第二次测量后：X2P（x2）＝123456781/21/2000000H(x2)=log2=1(bit/符号)第三次测量后：X3P（x3）＝1234567810000000H(x3)=log1=0(bit/符号)第一次测量后：X1P（x1）＝123456781/41/41/41/40000H(x1)=log4=2(bit/符号)H(x)－H(x1)

=1－－获得1bit信息量H(x1)－H(x2)

=1－－获得1bit信息量H(X)表示在获知哪个灯泡是坏的情况前，关于哪个灯泡已损坏的平均不确定性，即要确定哪个灯泡是坏的，至少需要获得3个bit的信息量，才能完全消除不确定性。33例2.2:试验前：XP（x）＝1234561/61/61/61/61/61/6H(x)=log6=2.58bits=1.79natsX1P（x1）＝123456010000H(x1)=0H(x)－H(x1)=log6试验后：34熵的物理含义观察随机变量X、Y、ZH(X)=-0.01log0.01-0.99log0.99=0.08（比特/符号）H(Y)=-0.5log0.5-0.5log0.5=1（比特/符号）H(Z)=5(-0.2log0.2)=2.32（比特/符号）XP（x）＝a1a20.010.99ZP（z）＝a1a2a3a4a50.20.20.20.20.2YP（y）＝a1a20.50.535熵的物理含义熵是随机变量的随机性的描述。变量Y、Z等概，随机性大，变量X不等概，则随机性小等概情况下，可取值越多，随机性越大H（）是描述随机变量所需的比特数熵是信源输出消息前随机变量平均不确定性的描述X试验中发生a1,获得的自信息为-log0.01=6.64(bit)Y试验中发生a1,获得的自信息为-log0.5=1(bit)H（）反映的是平均的不确定性信源熵H(X)是表示信源输出后每个消息/符号所提供的平均信息量36熵的基本性质和定理熵函数H(X)：熵H是p(x1),p(x2),…,p(xn)的n元函数（实际上，因Σp(xi)=1，独立变量只有n-1个，H是(n-1)元函数）:(1)非负性(2)对称性(3)最大离散熵定理(4)扩展性(5)确定性(6)可加性(7)上凸性37(1)非负性H(X)≥0因为随机变量X的所有取值的概率分布满足0≤p(xi)≤1；当取对数的底大于1时logp(xi)≤0，而-

p(xi)

logp(xi)≥0，所以熵H(X)≥0；38熵函数的性质－－非负性（证明）证明一：而：故：所以：（取底数大于1时）39熵函数的性质－－非负性（证明）证明二：有：或：所以：40(2)

对称性①定义：当变量p(x1),p(x2),…,p(xn)的顺序任意互换时，熵函数的值不变，即②含义：该性质说明熵只与随机变量的总体结构有关，与信源的总体统计特性有关。如果某些信源的统计特性相同（含有的符号数和概率分布相同），那么这些信源的熵就相同。41(3)最大离散熵定理(极值性)定理：离散无记忆信源输出N个不同的信息符号，当且仅当各个符号出现概率相等时(即p(xi)=1/N)，熵最大。H[p(x1),p(x2),…,p(xN)]≤H(1/N,1/N,…,1/N)=log2N

结论：出现任何一个符号的可能性相等时，信源的平均不确定性最大。42例2.3：二元熵函数是对0－1分布的随机变量所求的熵：XP（x）＝01p1-pH(X)=-plogp-(1-p)log(1-p)=H(p)H’(X)=-logp-p/p+log(1-p)+(1-p)/(1-p)=log(1-p)/p则：H(X)对p求导：可以证明，p＝1/2时，H(p)取最大值，为log2=1。而p=0或1时，H(p)＝0，故二元熵函数的曲线如图所示：431.01.00.50pH(p)/bit二元熵函数曲线等概时，p=0.5：随机变量具有最大的不确定性，p=0,1时：随机变量的不确定性消失。44(4)扩展性因为所以上式成立。本性质说明，信源的取值增多时，若这些取值对应的概率很小（接近于零），则信源的熵不变。虽然概率很小的事件出现后，给予收信者较多的信息。但从总体来考虑时，因为这种概率很小的事件几乎不会出现，所以它在熵的计算中占的比重很小。这也是熵的总体平均性的一种体现。45(5)确定性H(1,0)=H(1,0,0)=H(1,0,0,0)=…=H(1,0,…,0)=0

从总体上看，信源虽然有不同的输出消息，但它只有一个消息几乎必然出现，而其他消息都是几乎不可能出现，这个信源是一个确知信源，其熵等于零。46(6)

强可加性H(XY)=H(X)+H(Y/X)H(XY)=H(Y)+H(X/Y)

47(7)

上凸性设有一个多元矢量函数f(x1,x2,…,xn)=f(X)，对任一小于1的正数α(0＜α＜1)及f的定义域中任意两个矢量X,Y，

若f[αX+(1-α)Y]＞αf(X)+(1-α)f(Y)，则称f为严格上凸函数。设P,Q为两组归一的概率矢量：

P=[p(x1),p(x2),…,p(xn)]，Q=[p(y1),p(y2),…,p(yn)]0≤p(xi)≤1，0≤p(yi)≤1，有：H[αP

+(1-α)Q]＞αH(P)+(1-α)H(Q)

48离散无记忆的扩展信源什么是平稳离散无记忆信源？信源输出的消息序列是平稳随机序列并且符号之间是无依赖的。离散无记忆信源的数学模型与离散信源的类似，也用[X，P（x）]表示，只是离散无记忆信源输出的消息是一串符号序列，用随机矢量表示，随机矢量的联合概率分布等于组成它的各个随机变量的概率乘积(为什么？)。49离散无记忆的扩展信源定义：一个离散无记忆信源X，其样本空间为{a1,a2,…,aq}，信源输出的消息可以用一组组长度为N的序列表示。此时信源X可等效成一个新信源XN=（X1,X2,…,XN），其中的每个分量Xi都是随机变量，都取于X，分量之间统计独立，这样的新信源就是离散无记忆信源X的N次扩展信源。结论：离散无记忆信源X的N次扩展信源的熵等于离散信源x的熵的N倍。50ex：2.6某一离散无记忆平稳信源：求此信源的二次扩展信源的熵？X2信源的符号组成扩展信源的符号概率1/41/81/81/81/161/161/81/161/1651离散平稳信源（1）回忆：什么是离散平稳信源？严格的数学定义一维离散平稳信源：若当t=i，t=j时，信源输出的随机序列满足P(xi)=P(xj)=P(x)，即一维概率分布与时间起点无关，则信源称为一维离散平稳信源。二维离散平稳信源：若信源输出的随机序列同时还满足二维联合概率分布也与时间起点无关，即P(xi，xi+1)

=P(xj，xj+1)

，则信源称为二维离散平稳信源。52离散平稳信源（2）若信源输出的随机序列各维概率分布均与时间起点无关，则信源是完全平稳的，称为离散平稳信源。离散平稳信源中联合概率满足的等式：

P(xi)=P(xj)；P(xi，xi+1)

=P(xj，xj+1)……(2.61)推论：离散平稳信源的条件概率也与时间起点无关。P(xi+1/xi)=P(xj+1/xj)；P(xi+2/xixi+1)

=P(xj+2/xjxj+1)

……(2.63)53二维离散平稳信源特点：

1、信源的一维、二维概率分布均与时间起点无关。2、输出的随机序列中只有两两相邻的符号之间有依赖关系。二维离散平稳信源的概率空间：

联合概率：二者共同描述一个二维离散平稳信源。54二维离散平稳信源信息测度——信源熵一、把二维离散平稳信源输出的随机序列相邻的两个符号分成一组，每组代表新信源的一个符号。联合熵H(X1X2)二、先求出已知前面符号确定的情况下，下一个符号的平均不确定性，再对前面的符号求统计平均。条件熵H(X2/X1)55结论：两个有相互依赖关系的随机变量X1和X2所组成的随机矢量X=X1X2的联合熵H(X),等于第一个随机变量的熵H(X1)与第一个随机变量X1已知的前提下，第二个随机变量X2的条件熵H(X2/X1)之和。

H(X1X2)=H(X1)+H(X2/X1)联合熵、条件熵的关系：56联合熵、条件熵的关系：当X1,X2相互独立时，有：于是有：理解：当随机变量相互独立时，其联合熵等于单个随机变量的熵之和，而条件熵等于无条件熵。57联合熵、条件熵的关系：一般情况下理解：表明一般情形下：条件熵总是小于无条件熵。注意：这是平均意义上的58ex：2.7某一二维离散平稳信源ajai01201/41/18011/181/31/18201/187/36联合概率求此信源的熵？59（法一）求联合熵H(X1X2)（法二）求条件熵H(X2/X1)ajai01209/111/8012/113/42/9201/87/960H(X)=H(X1X2…XN-1XN)/联合熵表示平均发一个消息（由N个符号组成的序列）提供的信息量。平均符号熵：信源平均每发一个符号提供的信息量为极限熵：当N→∞时，平均符号熵取极限值称之为极限熵或极限信息量。用H∞表示，即离散平稳有记忆信源的极限熵61极限熵的存在性：当离散有记忆信源是平稳信源时，从数学上可以证明，极限熵是存在的，且等于关联长度N→∞时，条件熵H(XN/X1X2…XN-1)的极限值，即极限熵的计算：必须测定信源的无穷阶联合概率和条件概率分布，这是相当困难的。有时为了简化分析，往往用条件熵或平均符号熵作为极限熵的近似值。在有些情况下，即使N值并不大，这些熵值也很接近H∞，例如马尔可夫信源。通过推导可知，用条件熵作为极限熵的近似值更为接近。62马尔可夫信源（自学）63信源剩余度64信息传输手