《信息论与编码》 课件 第2章信源与信息熵

1第2章信源与信源熵信源的分类与数学模型离散单符号信源熵离散序列信源熵马尔科夫信源极限熵连续信源熵波形信源熵连续信源最大熵定理信源的冗余度2信号分类

离散信号

时间和幅度均离散

连续信号

时间和幅度均连续

时间离散幅度连续信号

抽样信号

幅度离散时间连续信号2.1信源的分类及数学模型2.1.1信源分类31、离散信源离散单符号信源离散序列信源2、时间离散幅度连续信源连续单符号信源连续序列信源无记忆有记忆马尔科夫信源无记忆有记忆3、时间连续幅度连读信源（波形信源）2.1.1信源分类信源分类：（由简单到复杂）（1）离散单符号信源；（2）离散序列信源；（3）马尔科夫信源；（4）连续单符号信源；（5）连续序列信源；（6）波形信源。452.1.2信源的数学模型描述：通过概率空间描述（1）离散单符号信源离散信源：，pi

0。2.1.2信源的数学模型（2）离散序列信源（L次扩展信源）联合概率：无记忆：

62.1.2信源的数学模型（3）马尔科夫信源联合概率：

78（4）连续单符号信源显然应满足pX(x)

0，

2.1.2信源的数学模型9（5）连续序列信源若为无记忆的，则

2.1.2信源的数学模型2.1.2信源的数学模型（6）波形信源某时刻的取值是随机的，用随机过程{x(t)}来描述对于限频波形信源，设其最高频率为fm，根据奈奎斯特抽样定理，只要抽样频率fs≥2fm，则可用其抽样信号无失真恢复原信号。设该波形信源持续时间为tB，如果我们取最低抽样频率fs＝2fm，则只需要个2fmtB采样点即可。因此，一个代表波形信源的平稳随机过程{x(t)}，可以用序列长度L＝2fmtB的随机矢量来表示即可，其概率空间可

用序列长度L＝2fmtB的连续序列信源的概率空间

来描述。1011从理论上说任何时间受限的函数，其频谱是无限的；反之，任何频带受限的函数，其时间上是无限的。实际中，可认为函数在频带fm、时间tB以外的取值很小，不至于引起函数的严重失真。2.1.2信源的数学模型12（1）马尔可夫信源简化形式当信源的记忆长度为m+1时，该时刻发出的符号与前m个符号有关联性，而与更前面的符号无关。2.1.3马尔科夫信源的稳态分布13离散有记忆序列信源与马尔可夫信源区别(a)离散有记忆序列信源(b)马尔可夫信源14（2）齐次马尔可夫信源齐次马尔可夫信源：条件概率与时间起点无关。平稳包含齐次，齐次不一定平稳。2.1.3马尔科夫信源的稳态分布平稳与齐次区别若Q和T为任意两个时刻，平稳满足15运用概率的一般运算法则16（3）马尔可夫信源状态转移概率矩阵信源在某一时刻出现符号概率xj与信源此时所处状态si有关，用符号条件概率表示p(xj/si)，状态转移概率表示为p(sj/si)状态集为：2.1.3马尔科夫信源的稳态分布17马尔可夫信源一步转移概率特别关心n-m=1情况，pij(m,m+1)2.1.3马尔科夫信源的稳态分布18马尔可夫信源一步转移概率矩阵系统在任一时刻可处于状态空间的任意一状态，状态转移时，转移概率是一个矩阵。由于共有Q=nm种不同状态，可用Q×Q的矩阵来描述一步转移概率矩阵：2.1.3马尔科夫信源的稳态分布19齐次马尔可夫信源性质对于齐次马尔可夫链，一步转移概率完全决定了k步转移概率。定义：若齐次马尔可夫链对一切i,j存在不依赖于i的极限，则称其具有遍历性，pj称为平稳分布2.1.3马尔科夫信源的稳态分布20马尔可夫信源定理：设有一齐次马尔可夫链，其状态转移矩阵为P，其稳态分布为wj=p(sj)2.1.3马尔科夫信源的稳态分布2.1.3马尔科夫信源的稳态分布该方程是否存在解？解是否唯一结论1：该方程一定存在非零解。

212.1.3马尔科夫信源的稳态分布解的唯一性

说明：以上条件只是马尔科夫信源存在稳态分布的必要条件，并不是充要条件。22由于23不可约性:就是任意一对i和j，都存在至少一个k，使pij(k)>0。非周期性:所有pii(n)>0的n中没有比1大的公因子。2.1.3马尔科夫信源的稳态分布24如图2-1所示的二进制相对码编码器（其中T为时延模块），初始状态Y1=X1；其余时刻，如输入X=0，则当前时刻输出等于上时刻输出，Yi+1=Yi；如输入X=1，则当前时刻输出异于上时刻输出，

；若已知P(X=0)=p，P(X=1)=1-p=q，试写出其转移概率矩阵，并画出状态转移图。2.1.3马尔科夫信源的稳态分布解：由于当前时刻的输出，取决于当前时刻的输入，以及前一个时刻的输出，所以输出序列是一个一阶马尔可夫链。对于二进制信源，前一个时刻的输出共有两种（0或者1），所以状态共有两种：“0”状态和“1”状态。

即转移概率矩阵为：其状态转移图为：

25pqp10q2.1.3马尔科夫信源的稳态分布二阶马尔科夫信源，X{0,1},求稳态概率分布26起始状态符号01s1(00)1/21/2s2(01)1/32/3s3(10)1/43/4s4(11)1/54/5表2-1符号条件概率p(aj|si)解：对二阶马尔可夫链，其状态共有四种，分别为：S=(00，01，10，11)，根据符号条件概率表2-1，可以写出符号条件概率矩阵为：可得状态转移概率矩阵为2728状态转移概率起始状态(si)s1(00)s2(01)s3(10)s4(11)1/201/401/203/4001/301/502/304/5s1(00)s2(01)s3(10)s4(11)2.1.3马尔科夫信源的稳态分布表2-2状态条件概率p(sj|si)终止状态(sj)状态转移图：2900100111(0)1/2(0)1/5(1)2/3(0)1/4(1)1/2(1)4/5(1)3/4(0)1/330

设四种状态的稳态概率为W1，W2，W3，W4可得方程组解得稳态分布的概率为：达到稳态后的符号概率为：2.1.3马尔科夫信源的稳态分布例：设有一马尔科夫链，其状态转移矩阵为判断该马尔科夫链是否存在稳态分布？

31322.2离散单符号信源熵自信息量离散单符号信源熵离散单符号信源条件熵离散单符号信源联合熵互信息信源熵性质332.2.1自信息量自信息量

例以2为底，单位为比特，用bit（或b）表示。自信息量与不确定度自信息量：符号出现后，提供给收信者的信息量；不确定度：符号出现前，所含有的不确定性。二者数量上相等，物理含义不同。342.2.1自信息量352.2.1自信息量自信息量的性质p(xi)=1,I(xi)=0；确定性事件不包含任何信息量；p(xi)=0,I(xi)=∞；出现的概率越小，包含的信息量越大；概率等于零时，包含的信息量为无穷大；非负性：p(xi)∈[0,1]，所以，故I(xi)≥0；可加性：如果符号xi中包含I(xi)的信息量，符号yj中包含I(yj)的信息量，则符号xi和yj同时出现包含的信息量，为两者的自信息量之和（假定两者互相独立p(xi,yj)＝p(xi)p(yj)）：

I(xi,yj)=I(xi)+I(yj)

例：假设一次掷两个各自均匀、互相不可区分但又不相关的骰子。如(A)、(B)分别表示：仅有一个骰子是3；至少有一个骰子是4；试计算(A)、(B)发生后提供的信息量。36372.2.2离散单符号信源熵离散单符号信源熵就是其平均不确定度

对于

，平均信息量为

离散单符号信源熵例题例：二元信源的熵38H(X)=-plogp-(1-p)log(1-p)=H(p)当p=0.5时，具有最大熵；当p=1或p=0时，H(X)=0;信源熵是p的上凸函数。392.2.3离散单符号信源条件熵给定条件yj，信源X的概率空间变化为

给定条件yj，可得条件熵：信息量例：某高三毕业生中，25%的女生考取了大学。在考取大学的女生中75%居住在城区，而高三毕业生中50%住在城区。假如我们得知“住在城区的女生考取了大学”的消息，试问获取了多少信息量？40412.2.3离散单符号信源条件熵若Y∈{yj,j=1,2,…,m}，可得{H(Y|y1),H(Y|y2),…,H(Y|ym)}若以Y为条件下，则X的条件熵为条件熵H(Y|X)表示当已知Y时，X仍然具有的不确定度。

例2-4

某二进制数字通信系统如图2-5所示。发送端信源X为二进制信源{0，1}，其概率空间为由于通信信道中有干扰和噪声，导致接收端判决结果除了“0”和“1”以外，还有一种未知的状态（既不是“0”也不是“1”），我们表示为“？”状态。设信道的符号转移概率为：求信源熵H(X)、条件熵H(X/Y)和H(Y/X)，以及信源熵H(Y)。42p(y=0/x=0)=3/4，

p(y=0/x=1)=0；p(y=1/x=0)=0，

p(y=1/x=1)=1/2；p(y=?/x=0)=1/4，

p(y=?/x=1)=1/2；图2-5二进制数字通信系统解：（1）信源熵H(X)可直接由公式求得（2）根据条件熵公式，求条件熵H(Y/X)，，需要知道条件概率p(y=0/x=0)、p(y=1/x=0)、p(y=？/x=0)和p(y=0/x=1)、p(y=1/x=1)、p(y=？/x=1)；以及联合概率p(x=0,

y=0)、p(x=0,

y=1)、p(x=0,y=？)和p(x=1，y=0)、p(x=1,y=1)、p(x=1,y=？)等：p(x

=0,y=0)=p(x=0)p(y=0/x=0)=1/2p(x

=0,

y=1)=p(x=0)p(y=1/x=0)=0p(x=0,y=?)=p(x=0)p(y=?/x=0)=1/6p(x=1,y=0)=p(x=1)p(y=0/x=1)=0p(x=1,y=1)=p(x=1)p(y=1/x=1)=1/6p(x=1,y=?)=p(x=1)p(y=?/x=1)=1/6则由条件熵公式可得：43（3）、根据条件熵公式，求条件熵H(X/Y)，，需要知道条件概率p(x=0/y=0)、p(x=0/y=1)、p(x=0/y=？)和p(x=1/y=0)、p(x=1/y=1)、p(x=1/y=？)；以及联合概率p(x=0,y=0)、p(x=0,y=1)、p(x=0,y=？)和p(x=1,y=0)、p(x=1,y=1)、p(x=1,y=?)等：故

44因此（4）由45得：462.2.4离散单符号信源联合熵当X和Y联合出现，若X∈{x1,x2,…,xn},Y∈{y1,y2,…,ym}，则其概率空间变化为

联合熵：信息量例题例2-5根据例2-4的信源X和信源Y，求联合熵H(X,Y)。

根据例2-4的求解过程，已知：

p(x

=0,y=0)=p(x=0)p(y=0/x=0)=1/2

p(x

=0,

y=1)=p(x=0)p(y=1/x=0)=0p(x=0,y=?)=p(x=0)p(y=?/x=0)=1/6

p(x=1,y=0)=p(x=1)p(y=0/x=1)=0p(x=1,y=1)=p(x=1)p(y=1/x=1)=1/6p(x=1,y=?)=p(x=1)p(y=?/x=1)=1/647482.2.5互信息互信息：例2-4数字通信系统49符号间互信息：在X取值集合上做概率统计平均，即得：进一步，在Y取值集合上做概率统计平均，即得2.2.5互信息50而且：例2-6，求例2-4中，符号X和符号Y之间的互信息2.2.5互信息51信源熵、条件熵、联合熵之间的关系若X和Y相互独立，则信源熵、条件熵、联合熵、互信息之间的关系

2.2.6信源熵、条件熵、联合熵、互信息等之间的关系522.2.6信源熵、条件熵、联合熵、互信息等之间的关系图2-6互信息量与熵之间的关系图2-7收、发两端的熵关系532.2.7信源熵的性质非负性对称性确定性可扩展性递增性54非负性55对称性56确定性可扩展性递增性这条性质表明，若原信源X中有一元素划分成m个元素（符号），而这m个元素的概率之和等于原元素的概率，则新信源的熵增加。熵增加了一项是由于划分而产生的不确定性量。例H(1/3,1/3,1/6,1/6)5758上凸性极值性（最大离散熵定理）熵函数H(P)是概率矢量P={p1，p2，…，pn}的严格∩型凸函数（上凸函数）。可加性

一般式当X、Y相互独立时熵的可加性可这样理解：复合事件集合的平均不确定性为各个分事件集合的平均不确定性的和。59递增性这条性质表明，若原信源X中有一元素划分成m个元素（符号），而这m个元素的概率之和等于原元素的概率，则新信源的熵增加。熵增加了一项是由于划分而产生的不确定性量。例H(1/3,1/3,1/6,1/6)6061

2.3离散序列信源熵离散无记忆信源及其信息熵离散有记忆信源熵离散平稳信源的极限熵

2.3离散序列信源熵离散序列信源（L次扩展信源）概率空间离散序列信源熵：

62单位：比特/序列独立但非同分布独同分布序列熵

2.3.1离散无记忆信源的序列熵63消息熵平均符号熵单位：比特/符号i.i.d.6465

2.3.2离散有记忆信源熵消息熵：序列熵：66对于有记忆离散序列信源，可得：结论1：离散序列信源的极限熵为：

结论2：

是L的单调非增函数结论3：

结论4：

是L的单调非增函数2.3.3离散平稳信源的极限熵67例

离散有记忆信源p(xj/xi)xjxix1x2x3x19/111/80x22/113/42/9x301/87/968解：

H(X2/X1)＝0.87比特/符号

H(X1)＝1.5比特/符号

H(X1,X2)＝H(X1)＋H(X2/X1)

＝1.5＋0.87＝2.37比特/序列 平均符号熵H2(X)＝0.5H(X2)＝1.185比特/符号比较上述结果可得：H2(X)<H1

(X)，即二重序列的符号熵值较单符号熵变小了，也就是不确定度减小了，这是由于符号之间存在相关性造成的。69马氏链极限熵齐次马尔科夫链2.4马尔科夫信源的极限熵70例2-8求马氏链平均符号熵（三个状态）

1/0.1s1

1/0.50/0.90/0.50/0.8s2

s31/0.2

三状态马尔可夫信源状态转移图解得：W1＝5/59，W2＝9/59，W3＝45/59。马尔可夫信源的熵：比特/符号71求解马尔可夫信源熵的步骤为：(1)根据题意画出状态转移图，或写出状态转移矩阵；(2)计算信源的平稳分布概率（假定信源具有平稳分布）；(3)根据一步转移概率和稳态分布概率，计算信源熵（极限熵）。72732.5连续单符号信源熵2.5.1