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

第二章离散信源及其信息测度通信的根本问题是将信源的输出信息尽可能快速可靠的传输并在接受端尽可能精确的复现。从本章开始，我们将从有效而可靠地传输信息的观点出发，对组成信息传输系统（通信系统）的各个部分分别进行讨论。本章首先讨论信源，重点是信源的统计特性和数学模型，以及各类离散信源的信息测度——熵及其性质，从而引入信息理论的一些基本概念和重要结论。主要内容2.1信源的数学模型及分类2.2离散信源的信息熵2.3信息熵的基本性质2.4离散无记忆信源的扩展信源2.5离散平稳信源2.6信源剩余度2.1信源的数学模型及分类2.1信源的数学模型及分类通信过程是从信源开始的，信源发送的是消息或消息序列，通信系统中传递的是消息，消息中包含信息。因此，通过研究消息来研究信源。在通信系统中收信者在收到消息之前，对信源发出的消息是不知道的，是不确定的、随机的，所以可以用随机变量、随机矢量或者随机过程来描述信源输出的消息。通常用一个样本空间及其概率测度——概率空间来描述信源。2.1信源的数学模型及分类不同的信源输出的消息不同，可以根据消息的不同的随机性质来对信源进行分类。2.1.1信源输出的消息用随机变量描述信源的的消息符号是离散的且是有限的，每次信源的输出为单个的信源符号，且所有符号的概率满足完备性，这是最基本的离散信源。如书信、文稿、电报、计算机输出的代码等。如果信源输出为连续信号，如语音、热噪声信号，传感器测得电压、温度、压力、振动信号等，这些信源的输出都是连续取值的，称为连续信源。其输出消息是不可数的。其数学模型是连续型的概率空间，用下面的形式表示。2.1信源的数学模型及分类2.1信源的数学模型及分类2.1.2信源输出的消息用随机矢量描述实际信源每次输出的消息是按一定概率选取的符号序列，可以看做是时间上或者空间的随机矢量。用N维随机矢量X=(X1,X2,…,XN)表示，又称为随机序列。若随机矢量的各维概率分布都与时间起点无关，这样的信源称为平稳信源。每个随机变量Xi都是离散取值且其可能取值是有限的，这样的信源称为离散平稳信源。每个随机变量Xi都是连续取值的连续型随机变量，则为连续平稳信源。2.1信源的数学模型及分类若信源先后发出的各个符号彼此统计独立，则：若随机变量Xi不同时刻的取值来自于同一个符号集合A：{a1,a2,…aq}.则有：若该信源不同时刻发出的符号之间无依赖关系，彼此统计独立，则为离散无记忆信源。2.1信源的数学模型及分类则信源X所输出的随机矢量X所描述的信源称为离散无记忆信源X的N次扩展信源若信源在不同时刻发出的符号之间是相互依赖的，这种信源为有记忆信源。通常符号之间的依赖关系（记忆长度）是有限的，若记忆长度为m+1,则称这种有记忆信源为m阶马尔可夫信源。

用条件概率俩描述随机序列中各随机变量之间依赖关系：2.1信源的数学模型及分类若上述条件概率与时间起点无关，及条件概率也是平稳的，则此信源为时齐马尔可夫信源。在连续平稳信源情况下，也分为无记忆信源和有记忆信源。若信源输出的连续型随机矢量中，各随机变量之间无依赖且统计独立，则称此信源为连续平稳无记忆信源。若信源输出的连续型随机矢量中，各随机变量之间有依赖，则称此信源为连续有记忆信源。2.1.3信源输出的消息用随机矢量描述很多实际信源的输出消息常常是时间和取值都是连续的，例如语音信号、热噪声信号、电视信号等时间连续函数。同时在某一具体时间t0,它们的可能取值又是连续的和随机的。对于这种信源的输出消息，可用随机过程来描述。称这类信源为随机波形信源（也称随机模拟信源）。按照取样定理，随机过程也可以用一系列离散的取样值来表示，即离散随机序列。2.1信源的数学模型及分类2.2离散信源的信息熵2.2离散信源的信息熵▼讨论和研究最基本的离散信源(即输出为单个符号的消息，且这些消息间两两互不相容)。▼基本的离散信源可用一维随机变量X来描述信源的输出，信源的数学模型可抽象为:问题：这样的信源能输出多少信息?每个消息的出现携带多少信息量?2.2.1自信息▼绪论中我们已经知道，通信时信源发出的消息常常是随机的，不确定的，只有当消息通过信道传输给收信者以后，才能消除这种不确定性。▼因此，通信中获取的信息与不确定性消除的程度有关，消除的不确定性＝获得的信息量；▼不确定性就是随机性，可以用概率论和随机过程来测度，概率小→不确定性大→信息量大，即信息量是概率的单调递减函数；2.2离散信源的信息熵设离散信源X的概率空间为：事件ai发生所含有的自信息量为：I(ai)代表两种含义：▼事件ai发生前，表示事件ai发生的不确定性；▼事件ai发生后，表示事件ai所提供的信息量。2.2离散信源的信息熵{{★本书(以及通信理论中)当中,如无特殊说明,信息量的单位均默认为比特.★由以上定义可以看出：（1）自信息是关于事件发生概率P的减函数；（2）当P=1，自信息为0；（3）当P=0，自信息为无穷大；（4）两个独立的事件的联合自信息为它们各自自信息的和。2.2离散信源的信息熵[例2-1]8个串联的灯泡x1，x2，…，x8，其损坏的可能性是等概率的，现假设其中有一个灯泡已损坏，问每进行一次测量可获得多少信息量？总共需要多少次测量才能确定哪个灯泡已损坏。解：已知8个灯泡等概率损坏，所以先验概率P(x1)＝1/8，即总的不确定性为：2.2离散信源的信息熵第一次测量后，剩4个灯泡。同样等概率损坏，P(x2)＝1/4，因为前面的判断，不确定性减少拉，还剩余的不确定为：第三次测量后，即可判断出哪个灯泡是坏的，则剩余不确定性减少为零。第二次测量后，剩2个灯泡，P(x3)＝1/2，不确定性进一步减少，还剩余的不确定为：2.2离散信源的信息熵[例2-2]若从装有n个不同阻值电阻的袋中随机取出一个并猜测所取得的阻值，困难程度是多少？解：这相当于求事件的不确定性事件等概[例2-3]袋中有n(n+1)/2个电阻，其中1Ω的1个，2Ω的2个，…，nΩ的n个，随机取出一个，则“取出阻值为i的电阻”所获得的信息量。解：“取出阻值为i的电阻”的概率是多少？2.2离散信源的信息熵2.2.2信息熵★对一个信源发出不同的消息所含有的信息量也不同。所以自信息I(ai)是一个随机变量，不能用它来作为整个信源的信息测度★定义自信息的数学期望为平均自信息量Hr(X)，称为信息熵:2.2离散信源的信息熵▼因和统计物理学中热熵的表达式相似，因此借用“熵”这个词，把H(X)称为信息“熵”；▼H(X)表示信源输出前的平均不确定性；▼H(X)表示信源平均每个符号携带的信息量；▼H(X)表示信源X的随机性。2.2离散信源的信息熵[例2-3]信源X的符号集为{0，1}，其中“0”符号出现的概率为p，求信源的熵?解：[例2-4]电视屏幕的格点数为500×600=300000，每点有10个灰度等级，若每幅画面等概率出现，求每幅画面平均所包含的信息量。解：可能的画面数为10300000

幅2.2离散信源的信息熵[例2-5]一布袋内放l00个球，其中80个红球，20个白球，如果从中随机取出一个球，设a1为取出红球，a2为取出白球，则其概率空间为：

解：如果摸出的是红球，那么获得的信息量是：

I(a1)＝-logp(a1)

＝-log0.8=0.32比特）如果摸出来的是白球，所获得的信息量应为：I(a2)＝-logp(a2)

＝-log0.2=2.32（比特）平均摸取一次所能获得的信息量为：

H(X)=p(a1)I(a1)+p(a2)I(a2)=0.72（比特/符号）2.2离散信源的信息熵[例2-6]有甲、乙两箱球，甲箱中有红球50、白球20、黑球30；乙箱中有红球90、白球10。现做从两箱中分别随机取一球的实验，问从哪箱中取球的结果随机性更大？。解:设甲、乙分别用AB代表所以，从甲箱中取球的结果随机性更大。2.2离散信源的信息熵[例2-7]A、B两城市天气情况概率分布如下表：晴阴雨A城0.80.150.05B城0.40.30.3问哪个城市的天气具有更大的不确定性？解:A、B城市天气情况的平均不确定性如下:所以，B城市的天气具有更大的不确定性。2.2离散信源的信息熵2.3信息熵的基本性质2.3信息熵的基本性质设离散信源X的概率空间为：信息熵是信源概率空间的一种特殊矩函数。其大小与信源的符号数及其概率分布有关。用概率矢量P来表示概率分布，H(P)为熵函数。2.3信息熵的基本性质引理若f(x)是定义在[a、b]上的实值连续上凸函数,则对于任意一组x1,x2,…,xq∈[a、b]和任意一组非负实数λ1,λ2,…λq且满足:则有:称此为詹森不等式用数学归纳法即可证明此引理，这是一个很重要的引理，我们对它做一个简单的推广：也可以简写成:2.3信息熵的基本性质1、对称性：H(P)的取值与分量p1,p2,···,pq的顺序无关。从数学角度:H(P)=pilogpi中的和式满足交换律；从随机变量的角度:熵只与随机变量的总体统计特性有关。例如：2.3信息熵的基本性质2、确定性：H(1,0)=H(1,0,0)=H(1,0,0…,0)=0说明：总体来看，虽然有不同的输出符号，但只有一个符号几乎必然出现，而其它符号则是几乎不可能出现，信源是确知信源，其熵等于零。3、非负性：H(P)0说明：随机变量X的概率分布满足0＜pi＜1，当对数底大于1时，log(pi)＜0，-pilog(pi

)＞0，即熵为正值。当随机变量是一确知量时熵等于零。非负性只适合于离散信源的熵，对连续信源来说这一性质并不存在。相对熵可能出现负值。非负性也说明信息是非负的。4、连续性2.3信息熵的基本性质说明:熵函数是概率pi的连续函数,同时表明,信源空间中概率分量的微小波动不会引起总体信息熵的巨大变化.2.3信息熵的基本性质说明：信源的取值数增多时，若这些取值对应的概率很小(接近于零)，则信源的熵不变。5、扩展性2.3信息熵的基本性质6可加性随机变量X、Y构成联合事件集合XY,则二维随机变量(X,Y)的熵等于多少呢？或者:其中:联合集概率空间为:2.3信息熵的基本性质2.3信息熵的基本性质同理可以证明：推论：当各个变量统计独立时，有：2.3信息熵的基本性质几个关系的证明:2.3信息熵的基本性质(2)熵的不增原理(条件熵不大于信息熵)2.3信息熵的基本性质[例2-7]如，甲信源为它们的联合信源是可计算得联合信源的联合熵：H(XY)=log(nm)=logm+logn=H(X)+H(Y)乙信源为2.3信息熵的基本性质7、递增性若原信源X中有一个符号分割成了m个元素(符号)，这m个元素的概率之和等于被分割符号的概率，而其他符号的概率不变，则新信源的熵增加。熵的增加量等于由分割而产生的不确定性量。可以由熵的定义式直接证明，也可以由联合熵的强可加性来证明。下面进行直接证明：2.3信息熵的基本性质证明：递增性的推广：2.3信息熵的基本性质它表示n个元素的信源熵可以递推成(n-1)个二元信源的熵函数的加权和。这样，可使多元信源的熵函数的计算简化成计算若干个二元信源的熵函数。因此，熵函数的递增性又可称为递推性。[例2-8]：运用熵函数的递增性(递推性)，计算熵函数H(1/3，1/3，1/6，1/6)的值。2.3信息熵的基本性质2.3信息熵的基本性质8极值性利用前面的詹森公式：条件(1)(2)λk为非负实数；(3)f(x)为上凸函数。当且仅当每个事件等概率出现时等号成立。00.51.0ω1.0

0.5H(ω)2.3信息熵的基本性质H(X)=-log-(1-)log(1-)=H()

[例2-9]该信源符号只有二个，设为“0”和“1”。符号输出的概率分别为“”和“1-”，即信源的概率空间为：即信息熵H(x)是关于的函数。取值于[0，1]区间，可画出熵函数H()的曲线来，如右图所示。2.3信息熵的基本性质8上凸性熵函数H(P)是概率矢量P的严格∩型凸函数。设概率矢量P=(p1,p2,…,pr)和Q=(q1,q2,…,qr)。其中：0≤pi≤1，0≤qi≤1，Σpi=1,Σqi=1，0≤a≤1。2.3信息熵的基本性质9熵函数的唯一性(证明略!)则熵函数具有唯一性.2.4离散无记忆信源2.4离散无记忆信源2.4.1单符号离散无记忆信源信源X的符号集X={x1,x2…,xq}，每个符号的发生概率为p(xi)，信源每次发出一个符号，且符号发生的概率相互独立，称为单符号离散无记忆信源，简称离散无记忆信源。2.4离散无记忆信源2.4.2离散无记忆信源的扩展信源1离散无记忆二进制信源的二次扩展信源二次扩展信源扩展后的信源符号集合新概率的计算:举例p(00)=p(0)p(0)…2.4离散无记忆信源2离散无记忆二进制信源的三次扩展信源三次扩展信源扩展后的信源符号集合新概率的计算:举例p(000)=p(0)p(0)p(0)…2.4离散无记忆信源3任意进制离散无记忆信源的N次扩展信源N次扩展信源2.4离散无记忆信源2.4.3N次扩展信源的熵证明:离散无记忆信源X的N次扩展信源XN的熵等于信源X的熵值的N倍.2.4离散无记忆信源2.4离散无记忆信源[例2-10]已知离散无记忆信源模型如下:解:已知二元信源X={0,1},其二次扩展源X2=X1X2。则二次扩展源X2的符号集为{00,01,10,11}.其信源模型如下:求其二次扩展信源。2.4离散无记忆信源[例2-11]求离散无记忆信源的二次扩展信源及其熵。解：二次扩展信源的概率空间为X2123456789序列a1a1a1a2a1a3a2a1a2a2a2a3a3a1a3a2a3a3P(i)1/41/81/81/81/161/161/81/161/162.5离散平稳信源2.5离散平稳信源2.5.1离散平稳信源

在实际应用中，信源不是一个简单的无记忆信源。其输出往往是时间或者空间上的离散随机序列，而且序列中各符号之间存在一定的依赖（有记忆）关系。一般信源输出是双边序列：…X-1X0X1X2…Xi…其中Xi是随机变量,且其取值xi∈X={a1,a2,…aq}，i表示符号xi发送所对应的时刻，信源发送符号之间的依赖关系关系可以用联合概率来表示。2.5离散平稳信源在一般情况下，信源在t=i时刻将要发出什么样的符号决定于两方面：

(1)与信源在t=i时刻随机变量Xi的取值xi的概率分布p(xi)有关。一般t不同，概率分布也不同；(2)与t=i时刻以前信源已经发出的信源符号有关，即与条件概率p(xi|xi-1xi-2…)有关。通常该条件概率也是时间t的函数，即：当i≠j时

p(xi|xi-1xi-2…xi-N…)≠p(xj|xj-1xj-2…xj-N…)可以看出实际信源相对比较复杂，我们必须将复杂的问题简单化，下面只讨论平稳信源：2.5离散平稳信源若发送序列中，一维概率分布不随时间改变而改变，即：P(Xi=x)=P(Xj=x)=p(x)，则称为一维离散平稳信源；若一到N维联合概率分布都不随时间变化而改变，则信源为N维离散平稳信源。即：若发送序列各维联合概率都是平稳的，由此还可以推论出相应的条件概率也是平稳的:2.5离散平稳信源………………即对于平稳信源，其条件概率均与时间起点无关，只与关联长度N有关。即平稳信源发出的平稳随机序列前后的依赖关系与时间起点无关。2.5离散平稳信源2.5.2二维平稳信源的熵

离散平稳信源实际是一种有记忆信源，最简单的有记忆平稳信源是二维平稳信源，可看作是单符号离散信源的二次扩展信源，是有记忆的扩展信源。扩展后的二维联合概率空间为：2.5离散平稳信源如何对离散二维平稳信源进行信息测度？

已知扩展后的二维信源概率空间，根据信息熵的定义可以计算二维联合熵：联合熵表示平均每两个信源符号所携带的平均不确定性，与信源熵的定义——平均每个信源符号所携带的信息量不一致，近似表示为：2.5离散平稳信源[例2-12]

某一离散二维平稳信源其发出的符号只与前一个符号有关，即可用联合概率P(aiaj)给出它们的关联程度，如下表所示:P(aiaj)ajai01201/41/18011/181/31/18201/187/36求信源熵H(X)、条件熵H(X2/X1)和联合熵H(X1X2)。2.5离散平稳信源解：根据概率关系可计算得条件概率P(aj/ai),计算结果列表如下：ajai01201/41/18011/181/31/18201/187/36ajai01209/111/8012/113/42/9201/87/9到底选取哪一个值更能接近实际二维平稳信源的熵?2.5离散平稳信源2.5.3离散平稳信源的极限熵一般的平稳有记忆信源，输出符号之间的相互依赖关系不仅存在于相邻俩个符号之间，而且存在于更多(N>2)的符号之间。如何N长信源序列的熵值？若离散有记忆信源概率空间为：N长信源序列可以看作是单符号信源的N次扩展信源，即：X=X1X2…XN中各符号Xi，(i=1,2,…,N)均取自同一符号集合A=(a1,a2,…,aq)。2.5离散平稳信源信源发出的符号序列为(X1,X2,…,XN,…)，假设信源符号之间的依赖长度为N，各维概率分布为：简记为满足：2.5离散平稳信源已知联合概率分布可求得离散平稳信源的联合熵：定义N长的信源符号序列中平均每个信源符号所携带的信息量(平均符号熵)为：同时,若已知前N-1个符号，第N个符号的平均不确定性(平均信息量)，可从条件熵定义得出：2.5离散平稳信源对离散平稳信源若H1(X)＜，则有以下性质：(1)条件熵H(XN/X1X2…XN-1)随N的增加是递减的；(2)HN(X)H(XN/X1X2…XN-1)；(3)HN(X)也是随N增加而递减的；(4)H存在，并且:称为平稳信源的极限熵或者极限信息量，也有的称此为平稳信源的熵率。同时上式表明，有记忆信源的符号熵也可通过计算极限条件熵得到。2.5离散平稳信源现在简单证明这几个性质:(1)根据信源的平稳性和熵的不增原理，得：即对于平稳信源，条件越多，条件熵越不增加。(2)证明N个的和不小于 即平均符号熵不小于条件熵。2.5离散平稳信源(3)HN(X)随N增加而递减；证明:由于根据平均符号熵的定义和(2)的结果，有上式表明，平均符号熵不随序列的长度而增加。

2.5离散平稳信源(4)由前面的证明我们可以得出:是存在的。计算:利用(1)的结果与平稳性，有：2.5离散平稳信源先令 后令，得: 另外，由(2)的结果，当 时，有所以:2.5离散平稳信源定理的注释：(1)该定理提供了计算信源符号熵的方法，即通过计算极限条件熵得到。这样，当信源为有限记忆时，极限条件熵的计算要比极限平均符号熵的计算容易得多。例如：当平稳信源的记忆长度为有限m个符号长度时（及某时刻发生的符号只与其前面的m个符号有关），则得离散平稳信源的极限值：(2）极限熵等于最小的平均符号熵。[例2-13]：有两个同时输出的信源X和Y，其中X:{A，B，C}，Y:{D，E，F，G}，已知P(X)和P(Y/X)，求联合信源的联合熵和条件熵。2.5离散平稳信源XABCP(x)1/21/31/6P(y/x)D1/43/101/6E1/41/51/2F1/41/51/6G1/43/101/6解：信源