信息论与编码曹雪虹著第二章

第2章信源与信息熵2.1信源描述与分类2.2离散信源的信息熵和互信息2.3离散序列信源的熵2.4连续信源的熵与互信息2.5冗余度12.1信源的描述与分类信源定义:

信源是产生消息（符号）、消息序列和连续消息的来源。从数学上，由于消息的不确定性，因此，信源是产生随机变量、随机序列和随机过程的源信源的基本特性是具有随机不确定性22.1信源特性与分类信源分类(1)按信源发出消息在时间和幅度上分布情况离散信源:时间和幅度上都是离散分布的离散消息。如:文字、数字等。

单符号离散信源符号序列离散信源连续信源:时间或幅度上是连续分布的连续消息。如:话音、图像等。32.1信源特性与分类(2)按信源发出的符号之间关系无记忆信源:发出单个符号和发出符号序列无记忆信源。有记忆信源:发出符号序列的有记忆信源和发出符号序列的马尔可夫信源。(3)按照输出序列的平稳性，可分为：平稳信源非平稳信源42.1信源描述与分类几个概念样本空间：某事物各种可能出现的不同状态，即所有可能选择的消息集合。概率测度：每一个可能选择消息的概率，又称先验概率。后验概率：指条件概率P(ai/bj)。概率空间：一个样本空间和它的概率测度组合。52.1信源描述与分类数学模型描述：通过概率空间描述（1）单符号离散信源其中,符号集A={u1,u2,u3……un}，UA成为U的样本空间，且Pi≥0，。

62.1信源描述与分类例如：对二进制数字与数据信源72.1信源描述与分类例如：有100个球，其中有80个红色球，20个白色球，随机取出一个球，然后放回，在随机取一个球，如此反复。每次取球为何种颜色作为消息，则随机变量X的样本空间集A={x1=“红色”,x2=“白色”}，而X的概率分布p(x1)=0.8,p(x2)=0.2，信源的概率空间为82.1信源描述与分类（2）离散序列信源：每次发出1组含2个以上符号的符号序列来代表一个消息的信源。每个消息要用符号序列来描述，即用随机序列或随机矢量来描述：

x

∈

{a1，a2

·

··an

}最简单L=2情况，此时信源其概率空间为：92.1信源描述与分类举例：以3位PCM（脉冲编码调制）信源为例102.1信源描述与分类当p=1/2112.1信源描述与分类（3）连续信源:输出消息取值是无限的，即可能出现的消息数是不可数的无限值。其数学模型为连续型的概率空间且概率密度分布函数P(u)≥0,。符号集中的取值是介于（a,b）之间连续值，P(u)概率密度分布函数。122.1信源描述与分类例如：

一个袋中有很多干电池，随机摸出一个，测其电压值作为输出符号，该信源每次输出一个符号，但符号取值在[0，1.5]之间的所有实数，可用连续型随机变量U来描述，连续信源的概率空间为显然满足P(u)≥0,

。132.1信源描述与分类无记忆信源定义：所发出的各个符号或符号序列之间无统计（概率）关联性。则N维随机矢量的联合概率分布满足P(X=X1X2X3…XN)=P１(Ｘ１)P２(Ｘ２)…PＮ(ＸＮ)142.1信源描述与分类（1）单符号无记忆信源

定义：离散无记忆信源是由n个单符号消息组成的集合

X={x1，x2

···xn

}，这n个符号消息的概率分布为：称为符号xi

的先验概率,离散信源数学模型表示为：

称为概率空间,其中152.1信源描述与分类例1：离散无记忆信源单个符号X={0,1}X={A,B,…,Z}

162.1信源描述与分类单符号无记忆信源的性质它是最简单也是最基本的信源，是组成实际信源的基本单元。当信源给定，其相应的概率空间就已给定；反之，如果概率空间给定，这就表示相应的信源已给定。所以，概率空间能表征这离散信源的统计特性，因此有时也把这个概率空间称为信源空间。这些信源可能输出的消息数是有限的或可数的，而且每次只输出其中一个消息。因此，可以用一个离散型随机变量X来描述这个信源输出的消息。这个随机变量X的样本空间就是符号集A；而X的概率分布就是各消息出现的先验概率，信源的概率空间必定是一个完备集。172.1信源描述与分类(2)序列符号无记忆信源定义：每次发出1组含2个以上符号的符号序列来代表一个消息的信源。每个消息要用符号序列来描述，即用随机序列或随机矢量来描述,这些符号序列中的各个符号之间没有统计关联性,各个符号出现的概率是它自身的先验概率,即

P(X=X1X2X3…XN)=P1(X1)P2(X2)…PN(XN)182.1信源描述与分类最简单L=2的情况，其概率分布为：其中：且192.1信源描述与分类例:

符号序列X={00,01,10,11}X={AA,AB,…,AZ,BA,BB,…,BZ,…,ZZ}202.1信源描述与分类(3)离散平稳信源定义：信源输出的随机序列X=(Ｘ１,Ｘ２,…,ＸＮ)满足：每个随机变量Xi都是离散型随机变量。随机矢量X的各维概率分布都与时间起点无关。这样的信源称为离散平稳信源。一般来说，我们假设信源输出的是平稳的随机序列，也就是序列的统计性质与时间的推移无关。很多序列符号无记忆信源也满足这个假设。212.1信源描述与分类例：在上一个例子中，如果每次取出两个球，则两个球的颜色组成的消息就是符号序列。如先取出一个球，记下颜色后再取出另外一个球，则每次取出的两个球的颜色是独立的，因而该信源是无记忆的，即发出符号序列的无记忆信源。由于布袋中红球、白球的分布情况不随时间变化，也就是信源发出的序列的统计性质与时间的推移无关，是平稳的随机序列。这一点特别重要，会给问题的分析带来很大的方便，于是每个变量的一维分布都相同：有时也将这种信源称为离散无记忆信源X的L次扩展信源。22离散平稳信源特征:

平稳信源发出的平稳随机序列前后的依赖关系与时间起点无关.如果某时刻发出的符号与前面发出的N个符号有关,那么任何时刻它们的依赖关系都是一样的,

即232.1信源描述与分类有记忆信源定义：所发出的各个符号或符号序列之间有统计（概率）关联性。一般情况下，信源在不同时刻发出的符号之间是相互依赖的。表述有记忆信源要比表述无记忆信源困难得多。实际上可以限制随机序列的记忆长度。当记忆长度为m+1时，称这种有记忆信源为m阶马尔可夫信源。也就是信源每次发出的符号只与前m个符号有关，与更前面的符号无关。242.1信源描述与分类(1)序列符号有记忆信源其概率分布比较复杂，需要引入条件概率来反映符号序列内各个符号之间的记忆特征：在实际应用中限制记忆的长度，使问题简化。252.1信源描述与分类例：在一个布袋中放100个球，其中80个球是红色的，20个球是白色的，随机的从布袋中取球，则取出球的颜色带有随机性，由此布袋可看作一个离散信源。每次取球时，先取出一个球，记下颜色后不放回布袋，接着取另一个，这在取第二个球时布袋中红白颜色球的概已于第一次不同，此时的概率分布与第一个球的颜色有关。因此是有记忆离散信源。现实中还有许多其它的例子，如英文单词，字母间是有关联性的。不是任何字母都能组成有意义的单词。262.1信源描述与分类(2)马尔可夫信源

a)马尔可夫链定义：

若某事件发生的概率只与前m个事件相关，而与更前面的事件无关，那么该事件集合称为马尔可夫链，其概率可描述为：272.1信源描述与分类b)马尔可夫信源定义：表述有记忆信源要比表述无记忆信源困难得多。实际上信源发出的符号往往只与前若干个符号的依赖关系强，而与更前面的符号依赖关系弱。为此，可以限制随机序列的记忆长度，这样就构成马尔可夫链。当记忆长度为m+1时，称这种有记忆信源为m阶马尔可夫信源。也就是信源每次发出的符号只与前m个符号有关，与更前面的符号无关.28c)一阶马尔可夫信源的数学描述如果上述条件概率与时间起点i无关，即信源输出的符号序列可看成为时齐马尔可夫链，则此信源称为时齐马尔可信源。（齐次马尔可夫信源）2.1信源描述与分类292.1信源描述与分类d)马尔可夫状态分析对于高阶马尔可夫链通常转化为一阶马尔可夫过程来处理。对于m阶马尔可夫信源，将该时刻以前的出现的m个符号定义为一个状态si，即：其中x

∈

{a1，a2

···an

}这样，条件概率就可以表示为：302.1信源描述与分类将该时刻以前出现的m个符号组成的序列定义为状态si,即

si=(x1,x2,….xm),x1,x2,….xm

∈A={a1,a2,….an}

共有Q=nm种可能取值，即状态集S={s1,s2…sQ}312.1信源描述与分类更进一步的，上述条件概率可以表示为状态之间的转移：更一般的，在时刻ｍ系统处于状态的条件下，经ｎ－ｍ步后转移到状态的概率用状态转移概率表示。也可以理解为在时刻ｍ系统处于状态ｉ的条件下，在时刻ｎ系统处于状态ｊ的条件概率，故状态转移概率实际上是一个条件概率。322.1信源描述与分类通常特别关心ｎ－ｍ＝１的情况，即，记为称为基本转移概率，也称为一步转移概率。于是有：对于齐次马尔可夫链，其转移具有推移不变性，即只与状态有关，与时刻无关，故可表示为：类似的，可以定义ｋ步转移概率：332.1信源描述与分类转移概率矩阵：系统在任一时刻可处于状态空间中的任意一个状态，因此转移概率是个矩阵，利用一步转移概率和ｋ步转移概率可得：该矩阵中，每一个元素对应一个转移概率，整个矩阵表征了状态空间中所有可能的转移，并且每行代表了从一个状态转移到所有状态的概率，转移概率和均为１。每列代表了从所有状态转移到一个状态的概率，概率之和不一定为１。34切普曼－柯尔莫郭洛夫（Chapman-Kormotopob)方程：上式右侧是对所有可能值求和，因而也就是k步转移概率，特别的当l=1时，若用矩阵表示：从这一递推关系可知，对于齐次马尔可夫链，一步转移概率完全决定了k步转移概率。35为了确定条件概率，令初始概率（初始时各状态的出现概率）为：某一状态的概率为：这是一个计算状态转移概率的基本公式。36稳态分布概率：若转移概率的极限存在，即不论马尔可夫链的起始状态是什么，最后都将等于某固定值。稳态分布的求法：应用上述公式求稳态分布需要马尔可夫链为遍历的，还需要满足不可约性和非周期性。37不可约性：所谓不可约性，就是对于任一状态，都可以达到另外一个状态，即存在：否则即称该马尔可夫链是可约的。如下图中的马尔可夫链就是可约的。

s1s2s31/21/21/211/2s4s51/21/21/21/238非周期性：所谓非周期性，就是的n中没有比1大的公因子。图中的矩阵就是周期为2的矩阵，其转移概率为：因为当k为奇数或偶数时，其结果是不一样的，这样就达不到稳定状态，虽然按公式该方程组是可解的。s1s2s4s31/21/21/21/21/21/21/21/2含义？？39例题：1、如图所示是一个相对码编码器，输入的码为相对独立的，取值为0或1，且已知输出的码为，求其稳态分布。+TXrYr01qqpp相对编码器状态转移图40例2、有一二阶马尔可夫链其状态图如图所示，求其稳态分布。s1s2s3s40110(0)1/4(1)1/2(0)1/500(0)1/211(1)4/5(0)3/4(0)1/3(1)2/341概率论知识复习基本事件：随机试验的每一个可能的结果（样本点）。样本空间：基本事件的集合。复杂事件：多个基本事件所组成的事件。随机事件：无论基本事件还是复杂事件，它们在试验中发生与否，都带有随机性。事件域：基本事件和复杂事件是样本空间的子集，所有子集的的全体。概率空间：三要素—样本空间、事件域（集合）、概率。先验概率：根据以往的统计规律得到的。42必须掌握的概率论知识1）条件概率2）联合概率433)全概率：设B1,B2,…是一系列互不相容的事件(BiBj=0），且有B1∪B2∪…=Ω（样本空间）；p（Bi）＞0，i=1，2，…，则对任一事件A，有：4)Bayes公式:

设B1,B2,…是一列互不相容的事件(BiBj=0），且有B1∪B2∪…=Ω（样本空间）；

p（Bi）＞0，i=1，2，…，则对任一事件A，有：442.2离散信源熵与互信息信息量自信息量联合自信息量条件自信息量单符号离散信源熵符号熵条件熵联合熵452.2离散信源熵与互信息信息不确定性的消除信息的度量随机性、概率相互独立符合事件概率相乘、信息相加熵事件集的平均不确定性462.2离散信源熵与互信息自信息定义：对于给定的离散概率空间表示的信源，x=ai事件所对应的（自）信息为以2为底，单位为比特（bit)以e为底，单位为奈特（nat)1nat=1.433bit以10为底，单位为笛特（det)1det=3.322bit转换关系如下：1nat=log2e≈1.433bit，1det=log210≈3.322bit47例1若发出二进制码元0和1信源，当符号概率为p(0)=1/4,p(1)=3/4，则这两个符号所包含的自信息量分别为多少？解：I(0)=-Ib(1/4)=lb4=2bitI(1)=-Ib(3/4)=lb(4/3)=0.415bit可见，因为0出现的概率小，因而一旦出现，给予观察者的信息量就很大。482.21自信息量例2英文字母中“e”的出现概率为0.105，“c”的出现概率为０.023，“o”的出现概率为0.001。分别计算它们的自信息量。解：“e”的自信息量“c”的自信息量“o”的自信息量49自信息量的几个性质：1）单调递减性，若有两个事件xi

，xj

其先验概率为p(xi)＜p(xj)，则事件xi

比事件xj有更大的不确定性，同时会带来更多的信息量；I(xi

)>I(xj

)2）事件xi先验概率p(xi)=1（确定事件）,则不存在不确定性，同时不会带来信息量，I(xi)=0.3）事件xi先验概率p(xi)=0（不可能事件）,则存在不确定性应为无穷大，同时会带来无穷的信息量；I(xi)→∞。4）可加性，两个统计独立事件的联合自信息量应等于它们各自信息量之和;则I(x，

y

)=

I(x)＋I(y

)5）非负性，自信息量永远不可能是负值，这由概率决定。502.2.2离散信源熵一、信源熵一个信源X发出的符号往往不只一个，各个符号的自信息量不同。信源X发出某特定符号提供的自信息量不适合描述信源X发出随机符号提供的信息量。关心的是整个系统的统计特性，将信源符号集合的平均不确定度定义为熵。定义信息源的平均不确定度为信源中各个符号不确定度的数学期望，记作H(X)

其中

H(X)又称为信源X的信源熵（平均自信息量）。512.2.2离散信源熵例3一个布袋内放100个球，其中80个球是红色的，20个球是白色的，若随机摸取一个球，猜测其颜色，求平均摸取一次所能获得的自信息量。这一随机事件的概率空间为为红球，信息量为白球，信息量每次摸出一个球后又放回袋中，再进行下一次摸取。随机摸取n次后总共所获得的信息量为522.2.2离散信源熵平均随机摸取一次所获得的信息量则为

自信息量只是表征信源中各个符号的不确定度，一个信源总是包含着多个符号消息，各个符号消息又按概率空间的先验概率分布，因而各个符号的自信息量就不同。53举例3、4、5见P1954例题信源一：不等概信源信源二：等概信源熵H(X2)=-0.5log0.5-0.5log0.5=1（比特/符号）信源三:等概信源熵H(X3)=-4×0.25log0.25=log4=2（比特/符号）55

信源四：信源为确定事件

熵H(X4)=-0log0–1log1=0

计算结果说明确定事件的熵为零信源五：一般情况下，二元信源的概率分布为熵H(X)=–δlog

δ-（1-δ）log（1-δ）记H2(δ)=–δlog

δ-（1-δ）log（1-δ）H2(δ)与δ的关系如图所示。（如同势均力敌的对手，其战斗结果最难预料）

H2(δ)

00.51δ图：H2(δ)与δ关系562.2.2离散信源熵例2.2.3二元信源是离散信源的一个特例。该信源X输出符号只有两个，设为0和1。输出符号发生的概率分别为p和q，p+q=1。即信源的概率空间为可得二元信源熵为二元信源熵为信源信息熵H(X)是概率p的函数，通常用H(p)表示。函数曲线如图572电视画面有500×600像素点，10个灰度等级，各种画面等可能出现，则有n=10300000个画面

H(X)=logn=lg10300000=3×105det/画面

=3.322×3×105bit/画面

用10000字表写1000字文，各种1000字文等可能出现则有n=100001000=104000篇，

H(X)=lgn=lg104000=4000det/千字文

=3.32×4×103bit/千字文可见，一个电视画面提供的信息量，要比一篇千字文提供的信息量大的多。58二、条件熵在给定yj条件下，xi的条件自信息量为：

I(x

i

|yj)=－logp(xi

|

yj)

集合X的条件熵为：

在给定Y（即各个yj）条件下，集合X的条件熵定义为：条件熵是条件自信息量的联合概率加权统计平均值。59三、联合熵（共熵）联合熵是联合符号集合XY上的每个元素对xi

,

yj的自信息量的概率加权的统计平均值。2.条件熵与联合熵的关系

I(xi

|yj)=－logp(xi

|

yj)，I(x

i

yj)=－logp(xi

yj)因

全概率公式60所以H(X，Y)=H(X

)＋H(Y|X)同理H(X，Y)=H(Y)＋H(X|Y)

H(X，Y)

H(X)+H(Y)

例题1、P20612.2.5熵的性质例2二进制通信系统用符号“0”和“1”，由于存在失真，传输时会产生误码，用符号表示下列事件：u0：一个“0”发出；u1：一个“1”发出；v0：一个“0”收到；v1：一个“1”收到。给定下列概率：p(u=0)＝1/2，p(v0/u0)＝3/4，p(v0/u1)＝1/2，求

(1)已知发出一个“0”，收到符号后得到的信息量；

(2)已知发出的符号，收到符号后得到的信息量；

(3)知道发出的和收到的符号能得到的信息量；

(4)已知收到的符号，被告知发出的符号得到的信息量。622.2.5熵的性质解:(1)可求出(2)联合概率632.2.5熵的性质(3)因为p(u0)＝p(u1)＝1/2，所以H(U)＝1比特/符号，H(UV)=H(U)+H(V/U)=1+0.91=1.91比特/符号.(4)可求出642.2.3互信息简单的通信模型

若信源发出符号xi，由于信道存在干扰，收到的不是xi而是yi，从yi中获取有关xi的信息量称为互信息量，用I(xi;yi)表示。信源X有干扰离散信道信宿Y干扰源65一、单符号互信息量1、信源发送符号xi，同时信宿接收符号yj的联合概率：

其中：p(xi)为信源符号xi的先验概率。

p(yj

|xi)为信源符号xi

已发送，信宿接收到yj

的条件概率；称为信道的传递概率或转移概率或前向概率。注意：p(y

i|xi)是在信源发送xi的情况下，信宿接收到

yi

的概率，该概率是可通过统计获得的。

2、信宿接收符号yj的概率

[全概率公式]66

3、信宿接收yj后，推测信源发送的符号是xi的概率（后验概率）：p(xi|yi)[Bayes公式]

674、互信息量定义：后验概率与先验概率比值的对数称为互信息量，记为I(xi；yj)

1.当p(xi

|yj

)=1，则I(xi;yj)=I(xi)2.当xi，yj

互不相关，p(xi|

yj

)=

p(xi)，则I(xi

;yj)=03.互信息量单位bit685、互信息量的性质

I(xi;yj)=I(yj

;xi)I(xi;yj)=I(xi)-I(xi

|yj

)I(xi;yj)=I(xi|

yj

)-I(yi)6、互信息量计算已知:信源符号xi的概率p(xi)---先验概率,

信源xi发送的条件下，信宿接收到yj的概率p(yj

|xi)

互信息量计算即如何求p(xi|yj)/p(xi)1.联合概率

2.全概率

3.后验概率与先验概率之比69例某二元通信系统x0=0，x1=1，信源发送x0和x1

的概率分别为p(0)=1/2，p(1)=1/2;信宿y0=0,

y1=1

由于信道中有干扰，当信源发送0时，信宿接收为0的概率p(y0|x0)=p(0|0)=3/4

信宿接收为1的概率p(y1|x0)=p(1|0)=1/4

当信源发送1时，信宿接收为0的概率p(y0|x1)=p(0|1)=1/5

信宿接收为1的概率p(y1|x1)=p(1|1)=4/5

求互信息量

I(x0;y0),I(x0;y1),I(x0;y1),I(x0;y1)70

x0=0p(0|0)=3/4y0=0

p(0|1)=1/5p(1|0)=1/4x1=1p(1|1)=4/5y1=1

1.联合概率

p(x0y0)=p(x0)p(y0|x0)=1/2×3/4=3/8

p(x0y1)=p(x0)p(y1|x0)=1/2×1/4=1/8

p(x1y0)=p(x1)p(y0|x1)=1/2×1/5=1/10p(x1y1)=p(x1)p(y1|x1)=1/2×4/5=4/10

712.全概率

p(y0)=p(x0y0)+p(x1y0)=3/8+1/10=19/40

p(y1)=p(x0y1)+p(x1y1)=1/8+4/10=21/403.后验概率与先验概率之比

p(x0|y0)/p(x0)=p(y0|x0)/p(y0)=3/4÷19/40=30/19p(x0|y1)/p(x0)=p(y1|

x0)/p(y1)=1/4÷21/40=10/21p(x1|y0)/p(x1)=p(y0|x1)/p(y0)=1/5÷19/40=8/19p(x1|y1)/p(x1)=p(y1|x1)/p(y1)=4/5÷21/40=32/21

724.互信息量

I(x0;y0)=log(30/19)bitI(x0;y1)

=log(10/21)bitI(x1;y0)=log(8/19)bitI(x1;y1)=log(32/21)bit73二、

平均互信息量定义互信息量I(xi

;yj)在联合概率空间P(XY)上的统计平均值称平均互信息量,用I(X;Y)表示

平均互信息量单位bit/消息平均互信息量的两种表示形式：（1）I(X;Y)=H(X)–H(X|Y);(2)I(X;Y)=H(Y)–H(Y|X).还可以得到

I(X;Y)=H(X)+H(Y)–H(XY)74物理意义

1、H(X)是符号集合X的熵或不确定度

2、H(X|Y)是当信宿已收到Y时，X的条件熵或不确定度（仍有疑义），表示通信过程中信息在信道中的损失量，称为信道疑义度或疑义度；

3、H(Y|X)可以看作唯一的确定信道噪声所需的平均信息量，故称为噪声熵或散布度；

4、

I(X;Y)表示信宿获得的净信息量；75物理含义（续）从通信的角度来讨论平均互信息量I(X;Y)的物理意义设X为发送消息符号集，Y为接收符号集，H(X)是输入集的平均不确定性,H（X︱Y）是观察到Y后，集X还保留的不确定性，二者之差I(X;Y)就是在接收过程中得到的关于X,Y的平均互信息量。对于无扰信道，I(X;Y)=H(X)。对于强噪信道，I(X;Y)=0。由第一等式I(X;Y)=H（X）-H（X︱Y）看I(X;Y)的物理意义76由第二等式I(X;Y)=H（Y)-H（Y︱X）看I(X;Y)的物理意义对于无扰信道，有I(X;Y)=H(X)=H(Y)。对于强噪信道，有H（Y︱X）=H（Y），从而I(X;Y)=0。H(Y)是观察到Y所获得的信息量，H（Y︱X）是发出确定消息X后，由于干扰而使Y存在的平均不确定性，二者之差I(X;Y)就是一次通信所获得的信息量。77通信前，随机变量X和随机变量Y可视为统计独立，其先验不确定性为H(X)+H(Y)，通信后，整个系统的后验不确定性为H(XY)，二者之差H(X)+H(Y)-H(XY)就是通信过程中不确定性减少的量，也就是通信过程中获得的平均互信息量I(X;Y)。由第三等式I(X;Y)=H(X)+H(Y)-H(X,Y)看I(X;Y)的物理意义结论：平均互信息量的大小与信道的传输能力有关：信道噪声越大，平均互信息量越小；反之，信道噪声越小，平均互信息量越大。782.2.3互信息疑义度条件熵H(X/Y)信道上的干扰和噪声所造成的对信源符号x的平均不确定度．噪声熵或散布度条件熵H(Y/X)可看作唯一地确定信道噪声所需要的平均信息量．如果X与Y是相互独立的，无法从Y中去提取关于X的信息，即H(X/Y)=H(X)，故称为全损离散信道。如果Y是X的确定的一一对应函数，I(X;Y)＝H(X)，已知Y就完全解除了关于X的不确定度，所获得的信息就是X的不确定度或熵。这可看成无扰离散信道．疑义度H(X/Y)为零，噪声熵也为零。在一般情况下，X和Y既非相互独立，也不是一一对应，那么从Y获得X的信息必在零与H(X)之间，即常小于X的熵。792.2.3互信息符号x与符号对yz之间的互信息量定义为条件互信息量是在给定z条件下，x与y之间的互信息量，定义为所以三维联合集XYZ上的平均互信息量有I(X;YZ)=I(X;Y)+I(X;Z/Y)Ｉ(YZ;X)=I(Y;X)+I(Z;X/Y)Ｉ(X;YZ)=I(X;ZY)=I(X;Z)+I(X;Y/Z)802.2离散信源熵与互信息例1设在一正方形棋盘上共有64个方格，如果甲将一粒棋子随意地放在棋盘中的某方格内，让乙猜测棋子所在的位置：（1）将方格按顺序编号，令乙猜测棋子所在方格的顺序号（2）将方格按行和列编号，甲将棋子所在的方格的行（或列）编号告诉乙，再令乙猜测棋子所在列（或行）所在的位置。812.2离散信源熵与互信息解：由于甲将一粒棋子随意地放在棋盘中的某方格内，因此棋子在棋盘中所处位置为二维等概率分布（1）联合（自）信息量为（2）条件（自）信息量为822.2离散信源熵与互信息例2.一个布袋内放100个球，其中80个球为红色，20球为白色。若随机摸取一个球，猜测其颜色，求平均摸取一次所获得的（自）信息量。解：随机事件的概率空间为832.2离散信源熵与互信息842.2离散信源熵与互信息Eg1(p23)设信源发出8种消息符号，各消息等概发送，各符号分别用3位二进码元表示，并输出事件。通过对输出事件的观察来推测信源的输出。假设信源发出的消息x4，用二进码011表示，接收到每个二进制码元后得到有关x4信息。852.2离散信源熵与互信息862.2.4

数据处理中信息的变化I(X;Z)=I(X;Y)+I(X;Z/Y)-I(X;Y/Z)集合符号替代（X代Y，Y代Z，Z代X）得

I(XY;Z)=I(X;Z)+I(Y;Z/X)将右边的X和Y互换得

I(XY;Z)=I(Y;Z)+I(X;Z/Y)最后得

I(X;Z)=I(Y;Z)+I(X;Z/Y)-I(Y;Z/X)假设在Y条件下X与Z相互独立，I(X;Z/Y)=0，而且I(X;Y/Z)和I(Y;Z/X)均非负量，则得出

I(X;Z)≤I(Y;Z)、I(X;Z)≤I(X;Y)信息不增性：数据处理过程中只会失掉一些信息，绝不会创造出新的信息．872.2离散信源熵与互信息熵的性质对称性非负性确定性香农辅助定理最大熵定理条件熵小于无条件熵882.2离散信源熵与互信息非负性892.2离散信源熵与互信息对称性902.2离散信源熵与互信息确定性

香农辅助定理912.2离散信源熵与互信息最大熵定理

条件熵小于无条件熵922.2离散信源熵与互信息平均互信息与熵的关系932.2离散信源熵与互信息互信息量与熵的关系94

2.3离散序列信源的熵离散无记忆序列信源离散有记忆序列信源马尔可夫信源离散无记忆信源的序列熵离散有记忆信源的序列熵95

2.3离散序列信源的熵离散无记忆序列信源布袋摸球实验，若每次取出两个球，由两个球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色放回布袋，再取另一个球。96

2.3离散序列信源的熵离散有记忆序列信源布袋摸球实验，每次取出两个球，由两个球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色不放回布袋，再取另一个球。97

2.3离散序列信源的熵马尔可夫信源当信源的记忆长度为m+1时，该时该发出的符号与前m个符号有关联性，而与更前面的符号无关。98

2.3离散序列信源的熵马尔可夫信源由于高阶马尔可夫信源需要引入矢量进行分析，现方法将矢量转化为状态变量。定义状态：信源在某一时刻出现符号概率xj与信源此时所处状态si有关，用条件概率表示p(xj/si),状态转移概率表示为p(sj/si)99

2.3离散序列信源的熵马尔可夫信源更一般，经过n-m步后转移至sj的概率100

2.3离散序列信源的熵马尔可夫信源特别关心n-m=1情况，pij(m,m+1)101

2.3离散序列信源的熵马尔可夫信源系统在任一时刻可处于状态空间的任意一状态，状态转移时，转移概率是一个矩阵，一步转移转移矩阵为102

2.3离散序列信源的熵马尔可夫信源k步转移概率pij(k)与l步和k-l步转移概率之间满足切普曼-柯尔莫郭洛夫方程。定义：如果从状态I转移到状态j的概率与m无关，则称这类MovKov链为齐次对于齐次马尔可夫链，一步转移概率完全决定了k步转移概率。103

2.3离散序列信源的熵马尔可夫信源定义：若齐次马尔可夫链对一切I,j存在不依赖于I的极限，则称其具有遍历性，pj称为平稳分布104

2.3离散序列信源的熵马尔可夫信源定理：设有一齐次马尔可夫链，其状态转移矩阵为P，其稳态分布为wj105

2.3离散序列信源的熵不可约性，对于任意一对I和j，都存在至少一个k，使pij(k)>0.非周期性，所有pij(n)>0的n中没有比1大的公因子。定理：设P是某一马尔可夫链的状态转移矩阵，则该稳态分布存在的充要条件是存在一个正整数N，使矩阵PN中的所有元素均大于零。106

2.3离散序列信源的熵Eg.一个相对编码器，求平稳分布107

2.3离散序列信源的熵Eg.二阶马氏链，X{0,1},求平稳分布起始状态000110111/201/401/203/4001/301/