第2章 信源与信息熵-1.ppt

1、信源与信息熵,第二章,本章内容,信源的分类及基本的信源数学模型描述、自信息和信息熵的定义及性质、互信息的概念及性质、信源冗余度的描述等。,本章重点,理解信源不确定性的含义，熵函数H(X)的性质、平均互信息量的定义、性质，联合信源的联合熵、条件熵，离散平稳信源的信源熵、极限熵等概念和计算方法。 了解马尔可夫信源的定义和计算方法。,2.1 信源的描述和分类,一、香农信息论的基本点,用随机变量或随机矢量来表示信源 用概率论和随机过程的理论来研究信息 常用的信息度量方法统计度量。 （另有结构度量、语义度量、语用度量和模糊度量等方法。）,2.1 信源的描述和分类,5,二、信源的分类,按照信源发出的消息在

2、时间上和幅度上的分布情况可将信源分成离散信源和连续信源两大类,连续信源是指发出在时间和幅度上都是连续分布的连续消息（模拟消息）的信源，如语言、图像、图形等都是连续消息。,离散信源是指发出在时间和幅度上都是离散分布的离散消息的信源，如文字、数字、数据等符号都是离散消息。,6,离散无记忆信源所发出的各个符号是相互独立的，发出的符号序列中的各个符号之间没有统计关联性，各个符号的出现概率是它自身的先验概率。 离散有记忆信源所发出的各个符号的概率是有关联的。 发出单个符号的信源是指信源每次只发出一个符号代表一个消息。 发出符号序列的信源是指信源每次发出一组含二个以上符号的符号序列代表一个消息。 发出符号

3、序列的有记忆信源是指用信源发出的一个符号序列的整体概率（即联合概率）反映有记忆信源的特征。 发出符号序列的马尔可夫信源是指某一个符号出现的概率只与前面一个或有限个符号有关，而不依赖更前面的那些符号，这样的信源可以用信源发出符号序列内各个符号之间的条件概率来反映记忆特征。,7,三、信源的描述,单符号离散信源 定义：一个离散无记忆信源是由n个符号消息组成的集合：X= x1，x2 xn ， 这n个符号消息的概率分布为： 称为符号xi的先验概率，信源数学模型表示为： 称为概率空间，其中,8,例如：对二进制数字与数据信源,9,单个连续信源 pX(x)为随机变量X的概率密度函数,10,概率论知识复习,随机

4、变量X和Y分别取值于集合 和 X发生xi和Y发生yj的概率为p(xi)和p(yj)，它们一定满足0 p(xi) ,p(yj ) 1以及和 。如果考察X和Y同时发生xi和yj的概率，则二者构成联合随机变量XY，取值于集合xiyj|i=1,2,n,j=1,2,m，元素xiyj发生的概率称为联合概率，用p(xi yj)表示。,11,概率论知识复习,如X发生xi以后，Y又发生yj的条件概率为p(yj /xi)，代表xi已知的情况下，又出现yj的概率。当xi不同时，即使发生同样的yj ，其条件概率也不同，说明xi对yj的影响。而p(yj)则是对xi一无所知情况下， yj发生的概率，有时相应地称为p(yj

5、)为yj的无条件概率。同理， yj 已知的条件下xi 的条件概率记为p(xi / yj)。相应地， p(xi)称为xi的无条件概率。,12,概率论知识复习,13,概率论知识复习,1）条件概率 2）联合概率,14,概率论知识复习,3)全概率： 4)Bayes公式:,15,2.2 离散信源熵和互信息,16,2.2 离散信源熵和互信息,信源发出消息，经过信道，到达信宿，信宿收到消息，获得了信息，这个过程就称作通信。我们现在来研究通信的源头，也就是信源的特性。那么实际有用的信源应该具有什么特性呢？我们认为它应该具有不确定性（不肯定性）。信源至少应该包含两种不同的消息，例如两元信元（包含0、1），而信宿

6、是知道信元发送（0、1）的，但是它就是不知道在具体的某一时刻，信源发送的是哪个消息。这是显然的，如果它知道，就不需要通信了！,一、 不确定性,17,【例2.1 】某二元信源（含有两个不同消息的信源）发送1的概率0.99，0的概率0.01，信宿仅凭猜测就可以简单的认为信源发出的消息始终都是1，即使如此，猜错的概率仅为百分之一。这说明在这种情况下，信源基本上在发送1，信源的不确定性很小。 【例2.2 】某二元信源发送1和0的概率相等，均为0.5，这时信宿不依赖通信仅凭猜测的话，猜错的概率高达50%。这说明在这种情况下，猜测信源发送什么消息就困难了，因为信源发送什么消息相当不确定。,18,【例2.3

7、 】如果信源具有更多的消息，例如发10个数字0,1.9(例如采用4位十进制树的中文电报)，而且假定这是个消息是等概率分布的，均为0.1，这时信宿仅凭猜测的话，就更难猜了。因为信源发送什么消息更加不确定。 【例2.4 】现在讨论一种极端的情况，信源只发送一种消息，即永远只发送1或者只发送0，从这样的信源中我们就不能从中获取任何信息，也就是说信源的不确定性为0。,19,信源如果没有不确定性，那么就没有实用价值。不确定度和发送的消息数目和发送符号的概率有关。为了确切的描述信源，我们采用概率空间来描述信源。 离散信源：若一类信源输出的消息常常是以一个个符号的形式出现，例如文字、字母等，这些符号的取值是

8、有限的或可数的，这样的信源称为离散信源。比如（0、1）二元信元，它的消息是以一定的概率来出现的，所以可以采用概率空间来描述。 若信源的输出是随机变量X，其出现概率为P(X)，则它们所构成的集合，称为信源的概率空间或简称为信源空间。,20,1) 定义：一个符号消息 xi 的自信息量为其发生概率的对数的负数，并记为 I(xi)； I (xi) = -log p(xi) 当p(xi)=0，则 I(xi)；当p(xi)=1，则 I(xi)=0. 2) 自信息量的单位 自信息量的单位与所用对数的底有关： 1 对数的底是2 时，单位为比特 bit(binary unit) 2 对数的底是 e (自然对数)

9、时，单位为奈特 nat(nature unit),二、自信息量,21,3 对数的底是10(常用对数) 时，单位为笛特或哈特 det (decimal unit) or Hart (Hartley) 三种信息量单位之间的换算： 1 det = log2 10 3.322 bit 1 bit = ln 2 0.6931 nat 1 bit = lg 2 0.3010 det 1 nat = log2 e 1.4427 bit 在信息论中常用以2为底的对数，为了书写方便，以后将log2书写为log，因其单位为比特bit，不会产生混淆； 注意 有些文献将log2书写为 lb。,22,【例2.5 】一个

10、1, 0等概的二进制随机序列，求任一码元的自信息量。 解：任一码元不是为0就是为1 因为 P(0) = P(1) = 1/2 所以 I (0) = I (1) = lb (1/2) = 1(bit),23,【例2.6 】 对于2n进制的数字序列, 假设每一符号的出现完全随机且概率相等，求任一符号的自信息量。 解：设2n进制数字序列任一码元xi的出现概率为p (xi)，根据题意， p(xi) = 1/2n I (xi ) = lb(1/2n) = n (bit) 事件的自信息量只与其概率有关，而与它的取值无关。,24,3) 自信息量的含义 是随机量、根据单个符号消息的先验概率确定其信息量和不确定

11、度。是该符号出现后，提供给收信者的信息量。 4) 随机事件的不确定度： 不确定度在数量，单位与自信息量相同，含义不同。具有某种概率的信源符号在发生之前，存在不确定度，不确定度表征该符号的特性。,25,5) 自信息量 I(xi) 的特性 1事件xi 先验概率p(xi)=1（确定事件）, 则不存在不确定性，同时不会带来信息量；I(xi)=0。 2事件xi 先验概率p(xi)=0（不可能事件）,则存在不确定性应为无穷大，同时会带来无穷的信息量；I(xi) 3非负性 4单调性 若有两个事件xi，xj ，其先验概率为p(xi)p(xj)，则事件xi 比事件xj 有更大的不确定性，同时会带来更多的信息量；

12、I(xi )I(xj ) 5可加性 两个统计独立事件的联合自信息量应等于它们各自信息量之和; 则 I( x y ) = I( x )I( y ),26,6) 联合自信息量与条件自信息量 1 联合自信息量 定义：若有两个消息xi ， yj同时出现，用联合概率p(xi yj) 表示，联合自信息量为：I(xi yj) =log p(xi yj) 当X和Y相互独立时， p(xiyj )= p(xi) p(yj )，代入到前式就有：I(xiyj )=- log2p(xi)-log2p(yj )= I(xi)+I(yj ) 说明两个随机事件相互独立时，同时发生得到的自信息量，等于这两个随机事件各自独立发生

13、得到的自信息量之和。,27,2 条件自信息量 定义：在事件yj 出现条件下，xi发生的条件概率为p(xi | yj)，则 xi的条件自信息量为： I(x i | yj)=log p(xi | yj) 由于随机事件（消息）的概率在01范围内，所以联合信息量和条件自信息量也满足非负和单调递减性。,28,联合自信息、条件自信息与自信息间的关系 I(xiyj )=- log2p(xi)p(yj|xi)= I(xi)+I (yj|xi) =- log2p(yj)p(xi|yj)= I(yj)+I (xi| yj),29,作为信源总体信息测度的量应是信源各个不同符号xi (i = 1, 2, N) 所包含

14、的自信息量I(xi) (i =1, 2, , N) 在信源空间P(X) = p(x1), p(x2), , p(xi), , p(xN )中的统计平均值。,三、离散信源熵,30,【例2.7 】一个布袋内放100个球，其中80个球为红色，20球为白色。若随机摸取一个球，猜测其颜色，求平均摸取一次所获得的（自）信息量。 解：随机事件的概率空间为,31,当被告知摸出红球的信息量是 当被告知摸出白球的信息量是 如果每次摸出一个球后又放回袋中，再进行下一次摸取且如此摸取n次，那么红球出现的次数为np(x1)，白球出现的次数为np(x2)。随机摸取n次后总共所获得的信息量为,32,而平均随机摸取1次所获得

15、的信息量为,33,1)定义 信息源的平均不确定度为信源中各个符号不确定 度的数学期望，记作H(X) 其中 H(X) 又称为信源X的信源熵。,34,2) H(X) 的含义 1 表示的是信源的平均不确定度。 2 表示信源 X 发出一个符号提供的平均信息量。 3 是统计量、数学期望（统计平均）、各个符号平均不确定度和平均信息量。 3) 信源熵单位： 二进制: bit/信源符号，或bit/信源序列 十进制: det/信源符号，或det/信源序列 e进制: nat/信源符号，或nat/信源序列,35,4) 信源熵的三种特殊情况 1 当 p(xi)=0 时（p(xi)0），则 p(xi) log p(xi

16、)=0 2 信源 X = x1，x2 xn ，若其中xi 的概率p(xi)=1 则其余 xj 的 p(xj) =0，因为 则 H(X)=0 bit / 信源符号 3 当信源中X所有n个符号均有相同的概率 p(xi)=1/n， 则 H(X)= -(1/n)log(1/n) = log n bit / 信源符号,36,【例2.8】设信源符号集X=x1,x2,x3，每个符号发生的概率分别为p(x1)=1/2，p(x2)=1/4，p(x3)=1/4，则信源熵为 即该信源中平均每符号所包含的信息量为1.5bit，也即为了表明和区分信源中的各个符号只需用1.5bit。,37,【例2.10】二元符号信源0，

17、1 符号0 的概率 p(0) =p ，则 p(1) =1-p H(X)= -p log p +(1-p ) log (1-p ) p=0.5时H(X)有最大值， H(X)=1bit /信源符号,38,39,5)条件熵与联合熵 1 条件熵 在给定 y j 条件下，x i 的条件自信息量为： I(x i | yj)=log p(xi | yj) 集合X的条件熵为： 在给定Y（即各个yj）条件下，集合X的条件熵定义为：,40,2 联合熵（共熵） 联合熵是联合符号集合XY上的每个元素对xi , yj的自信息量的概率加权的统计平均值。,41,3 条件熵与联合熵的关系 I( x i | y j )=log

18、 p( x i | y j ) ，I(x i y j )= log p( x i y j ),42,所以 H( X Y ) = H(X )H(Y | X ) 同理 H( X Y ) = H(Y )H( X | Y ) 当X和Y相互独立时，有,43,简单的通信模型 若信源发出符号xi ，由于信道存在干扰，收到的不是xi而是yi ，从yi中获取有关xi 的信息量称为互信息量，用I (xi ; yi)表示。,信源X,有干扰 离散信道,信宿Y,干扰源,四、互信息,44,1 信源发送符号xi ，同时信宿接收符号yj的联合概率： 其中： p(xi) 为信源符号xi的先验概率 。 p(yj|xi)为信源符号

19、xi已发送，信宿接收到yj的条件概率；称为信道的传递概率或转移概率或前向概率。 注意：p(yi|xi)是在信源发送xi的情况下，信宿接收到 yi的概率，该概率是可通过统计获得的。 2 信宿接收符号 y j 的概率,45,3 信宿接收yj 后，推测信源发送的符号是xi 的概率（后验概率）：p(xi | yi),46,4 互信息量 定义：后验概率与先验概率比值的对数称为互信息量，记为I(xi；yj) 1.当 p(xi | yj ) = 1，则I (xi ; yj)=I (xi) 2.当 xi，yj 互不相关，p(xi| yj )=p(xi)，则 I(xi ; yj)=0 3.互信息量单位 bit,

20、47,I (xi ; yj) = I (xi) - I(xi | yj ) 互信息量等于自信息量减去条件自信息量。自信息量在数量上与随机事件发出的xi不确定度相同，可以理解为对yj一无所知的情况下xi存在的不确定度。同理，条件自信息量在数量上等于已知yj的条件下，xi仍然存在的不确定度。两个不确定度差，是不确定度被消除的部分，代表已经确定的东西，实际是从yj得到的关于xi的信息量。,48,5 互信息量的性质 I (xi ; yj) = I (yj ; xi) I (xi ; yj) = I (xi) - I(xi | yj ) I (xi ; yj) = I(xi | yj ) - I (yi

21、),49,6 互信息量计算 已知: 信源符号x i的概率p(xi) -先验概率, 信源 x i 发送的条件下，信宿接收到 yj的概率p(yj | xi) 互信息量计算即如何求 p(xi | yj)/ p(xi) 1. 联合概率 2. 全概率 3. 后验概率与先验概率之比,50,【例2.11】某二元通信系统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

22、|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( x1 ; y0) , I( x1 ; y1),51,x0 = 0 p(0|0) = 3/4 y0 = 0 p(0|1) = 1/5 p(1|0) = 1/4 x1 = 1 p(1|1) = 4/5 y1 = 1 1. 联合概率 p(x0 y0) = p(x0) p(y0 | x0 ) = 1/2 3/4 = 3/8 p(x0 y1) =

23、p(x0) p(y1 | x0 ) = 1/2 1/4 = 1/8 p(x1 y0) = p(x1) p(y0 | x1 ) = 1/2 1/5 = 1/10 p(x1 y1) = p(x1) p(y1 | x1 ) = 1/2 4/5 = 4/10,52,2. 全概率 p(y0) = p(x0 y0) + p(x1 y0) =3/8+1/10 = 19/40 p(y1) = p(x0 y1) + p(x1 y1) =1/8+4/10 = 21/40 3.后验概率与先验概率之比 p(x0 | y0)/ p(x0)= p(y0 |x0) /p(y0) = 3/419/40 = 30/19 p(x

24、0 | y1)/ p(x0)= p(y1| x0) /p(y1) = 1/421/40 = 10/21 p(x1 | y0)/ p(x1)= p(y0| x1) /p(y0) = 1/519/40 = 8/19 p(x1 | y1)/ p(x1)= p(y1| x1) /p(y1) = 4/521/40 = 32/21 4.互信息量 I( x0 ; y0) = log(30/19) bit I( x0 ; y1) = log(10/21) bit I( x1 ; y0) = log(8/19) bit I( x1 ; y1) = log(32/21) bit,53,2) 条件互信息量 假设XY

25、Z空间的事件xi、yj、zk，那么事件yjzk出现后，从yjzk中获取关于xi的信息量是多少呢？ 如果把yjzk看作一个事件，则有,54,将上式分子分母同乘以P(xi |zk )，得 上式第一项是xi与zk之间的互信息量； 第二项定义为在zk条件下xi与yj之间的互信息量，简称为条件互信息量。,55,互信息量、联合事件互信息量、条件互信息量三者都是随机变量，其值随着变量xi 、yj 、zk的变化而变化。 三者之间有如下的关系式：,56,3) 平均互信息量 定义 互信息量I(xi ; yj)在联合概率空间P(XY)上的统计平均值称平均互信息量 , 用 I(X;Y)表示 平均互信息量单位 bit

26、/消息,57,当信宿收到某一具体符号yj后，从yj中获取关于输入符号的平均信息量，显然应该是在条件概率空间中的统计平均，可用I(X；yj)表示，有 再对其在集合Y中取统计平均，得,58,平均互信息的三种不同的形式表达式,59,4) 平均互信息量的性质 1 对称性 I(X ; Y)=I(Y ; X),60,2 非负性 I(X ; Y) 0 平均互信息量的非负性告诉我们：从整体和平均的意义上来说，信道每通过一条消息，总能传递一定的信息量，或者说接收端每收到一条消息，总能提取到关于信源X的信息量，等效于总能使信源的不确定度有所下降。也可以说从一个事件提取关于另一个事件的信息，最坏的情况是0，不会由于

27、知道了一个事件，反而使另一个事件的不确定度增加。,61,3 极值性 I (X;Y) H(X) I (Y;X) H(Y) 因此 I(X ; Y)=H( X )H( X|Y ) 当X与Y无关时，H(X |Y )= H (X )，则I(X ; Y) =0；表示无法从Y中获取X的信息。,62,4 凸函数性 由平均互信息量的定义 显然平均互信息量是信源概率分布p(xi)和表示输入输出之间关系的条件概率或称信道传递概率分布p(yj|xi)的函数，即,63,若固定信道，调整信源，则平均互信息量是信源概率分布p(xi)的函数 反之若固定信源，调整信道，则平均互信息量是信道传递概率或称信道转移概率分布p(yj|

28、xi)的函数 fp(xi)和fp(yj|xi)具有不同的数学特性,64,平均互信息量I(X;Y)是信源概率分布p(xi)的上凸函数 平均互信息量I(X;Y)是信道转移概率p(yj|xi)的下凸函数,65,5) 平均互信息量的物理意义 I(X ; Y)=H( X )H( X|Y ) 1 H( X ) 是符号集合X 的熵或不确定度 2 H ( X |Y ) 是当信宿已收到Y时，X的条件熵或不确定度（仍有疑义），表示通信过程中信息在信道中的损失量，称为信道疑义度或疑义度； 3 I( X ;Y ) 表示信宿获得的净信息量； 4 平均互信息量I(X;Y)考虑全部消息，根据统计平均的计算得出一个确定的量，

29、是信道中流通的信息量的整体测度。,66,I (Y; X) = H (Y) H (Y/X) 说明平均互信息量也可以用接收端（信宿）的熵为参考，且等于信宿熵减掉一个条件熵 同样表征接收端平均每收到一个符号所获得的信息量。 如果信道上没有任何干扰或噪声，则平均每收到一个符号所获得的信息量即是信宿熵，即I (X; Y) = H (Y)； 但是，如果信道上存在着干扰或噪声，则平均每收到一个符号所获得的信息量，它比起信宿熵小了一个条件熵，这个条件熵H (Y/X)是由于信道的干扰或噪声给出的，因此它是唯一地确定信道噪声和干扰所需的平均信息量，故称之为噪声熵，也称为散布度。,67,I (X; Y) = H(X

30、) + H(Y) H(XY) 根据各种熵的定义，从该式可以清楚看出平均互信息量是一个表征信息流通的量， 其物理意义就是信源端的信息通过信道后传输到信宿端的平均信息量。,68,【例2.12】已知信源空间 信道特性如图所示，求在该信道上传输的平均互信息量I (X; Y)，疑义度H(X|Y)，噪声熵H(Y|X)和共熵H(XY)。,69,解（1）根据P(xiyj) = P(xi)P(yj |xi)，求各联合概率，得 P(x1y1) = P(x1) P(y1|x1) = 0.50.98 = 0.49 P(x1y2) = P(x1) P(y2 |x1) = 0.50.02 = 0.01 P(x2y1) =

31、 P(x2) P(y1 |x2) = 0.50.20 = 0.10 P(x2y2) = P(x2) P(y2 |x2) = 0.50.80 = 0.40 （2）根据 ，求Y集合中各符号的概率，得 P(y1) = P(x1)P(y1|x1) +P(x2)P(y1|x2)= 0.50.980.50.2 = 0.59 P(y2) = 1 0.59 = 0.41,70,（ 3）根据P(xi|yj) = P(xi yj)/P(yj)，求各后验概率，得 P(x1| y1) = P(x1y1)/ P(y1) = 0.49/0.59 = 0.831 P(x2| y1) = P(x2y1)/ P(y1) = 0

32、.10/0.59 = 0.169 P(x1| y2) = P(x1y2)/ P(y2) = 0.01/0.41 = 0.024 P(x2| y2) = P(x2y2)/ P(y2) = 0.40/0.41 = 0.976,71,（4）求各种熵，有 I (X; Y) = H(X) + H(Y) H(XY) = 1+ 0.98 - 1.43 = 0.55 比特/信符 H(X|Y) = H(X) I(X; Y) = 1 0.55 = 0.45 比特/信符 H(Y|X) = H(Y) I(X; Y) = 0.98 0.55 = 0.43 比特/信符,72,2.2.4 数据处理中信息的变化 在一些实际的通信系统中，常常出现串联信道的情况。另外，对于信宿收到的信号或数据，常常需要进行适当的处理，以使输出消息变换成更有用的形式。这种处理称为数据处理。数据处理系统一般可看成是一种信道，它与前面传输数据的信道构成串联的关系。,73,假设Y下X和Z相互独立，则有 数据处理定理：当消息经过多级处理后，随着处理器数目的增多，输入消息与输出消息之间的平均互信息量趋于变小。 数据