信息论与编码纠错第2章.ppt

《信息论与编码纠错第2章.ppt》由会员分享，可在线阅读，更多相关《信息论与编码纠错第2章.ppt（77页珍藏版）》请在三一办公上搜索。

1、第二章 信息的度量,根据香农对于信息的定义，信息是一个系统不确定性的度量，尤其在通信系统中，研究的是信息的处理、传输和存储，所以对于信息的定量计算是非常重要的。本章主要从通信系统模型入手，研究离散情况下各种信息的描述方法及定量计算，讨论它们的性质和相互关系。,内容提要,2.1 自信息量和互信息量,一个事件的自信息量就是对其不确定性的度量。互信息量则表明了两个随机事件的相互约束程度。,对于随机事件集X=x1，x2，xi，xI中的随机事件xi，其出现概率记为p(xi)，将两个事件xi，yj同时出现的概率记为p(xi yj)，则p(xi)，p(xi yj)应满足：,且下列关系式成立,一自信息量和条件

2、自信息量,1自信息量,直观地看，自信息量的定义应满足以下四点：,（1）I(x)应该是p(x)的单调递减函数：概率小的事件一旦发生赋予的信息量大，概率大的事件如果发生则赋予的信息量小；（2）信息量应具有可加性：对于两个独立事件，其信息量应等于各事件自信息量之和；（3）当p(x)=1时，I(x)=0：表示确定事件发生得不到任何信息；（4）当p(x)=0时，I(x)：表示不可能事件一旦发生，信息量将无穷大。,综合上述条件，将自信息量定义为:,【例】若盒中有6个电阻，阻值为1、2、3的分别为2个、1个、3个，将从盒子中取出阻值为i的电阻记为事件xi（i=1，2，3），则事件集X=x1,x2,x3，其概

3、率分布,计算出各事件的自信息量列表如下：,自信息量I(xi)代表两种含义：,事件xi发生以前，表示事件发生的先验不确定性。一个事件不常出现，它的概率就小，当该事件发生时收信者获得的信息量就多，或者说事件携带的信息量大，因此自信息量也可以说是随机事件的一个固有特征。当事件xi发生以后，表示事件xi所能提供的最大信息量。,【例】信源消息X0，1，信源等概率分布，计算出自信息量如表所示。,可以看出，1bit的信息量就是两个互不相容的等可能事件之一发生时所提供的信息量。,【推广】二维联合集X Y上元素xi yj的联合自信息量I(xi yj)定义为：,2条件自信息量,在已知事件yj条件下，随机事件xi发

4、生的概率为条件概率p(xi/yj)，条件自信息量定义为：,【例】某住宅区共建有若干栋商品房，每栋有5个单元，每个单元住有12户，甲要到该住宅区找他的朋友乙，若,（1）甲只知道乙住在第5栋，找到乙的概率有多大？能得到多少信息？（2）甲除知道乙住在第5栋外，还知道乙住在第3单元，他找到乙的概率又有多大？他能得到多少信息？,【解】用xi代表单元数，yj代表户号：,二互信息量和条件互信息量,1互信息量,从通信的角度引出互信息量的概念。,信源符号：X=x1,x2,xI，xia1,a2,ak，i=1,2,I。,xi的概率分布p(xi)称为先验概率。,经过信道传输，信宿方接收到符号,信宿符号：Y=y1,y2

5、,yJ，yjb1,b2,bD，j=1,2,J。,接收到符号yj后，接收者重新估计xi发生的概率，记为条件概率p(xi/yj)，也称为后验概率。,事件xi是否发生具有不确定性，用I(xi)度量。接收到符号yj后，事件xi是否发生仍保留有一定的不确定性，用I(xi/yj)度量。,观察事件前后，这两者之差就是通信过程中所获得的信息量，为事件xi和事件yj之间的互信息量。用I(xi;yj)表示：,根据概率互换公式 p(xi yj)=p(yj/xi)p(xi)=p(xi/yj)p(yj)互信息量I(xi;yj)有多种表达形式：,【推广】将事件互信息量的概念推广至多维空间。,在三维X Y Z联合集中，有：

6、,一对事件yjzk发生后，与事件xi之间的互信息量，等于事件yj与xi之间的互信息量加上在事件yj已知的条件下，事件xi与zk的之间的互信息量。,类似，在N维U1 U2 UN联合空间，有,2条件互信息量,三维X Y Z联合集中，在给定条件zk的情况下,xi,yj的互信息量I(xi;yj/zk)定义为：,3互信息量的性质,（1）互易性（对称性）：,（2）可加性：,（3）当xi，yj统计独立时，互信息量及条件互信息量均等于零。,xi和yj相互独立，,表明之间不存在统计约束关系。,（4）互信息量I(xi；yj)可以是正数，也可以是负数。,（5）两个事件的互信息量不大于单个事件的自信息量，即有：,表2

7、-4为8个三位二进制数对应的各种概率。,【例2.8】信源包含8个消息x0,x1,x2,x3,x4,x5,x6,x7,信源编码器将其对应编成8个三位二进制数000，001,110。各消息的先验概率已知，在接收过程中，每收到一个数字，各消息的后验概率都相应地发生变化。考虑在接受100三个数字的过程中，各后验概率的变化，计算信息量I(x4;100)。,根据给定的先验概率，可算出：,将各种后验概率的计算结果列于表2-4中，再根据式（2-10）计算出互信息量：I(x4;100)=I(x4;1)+I(x4;01)+I(x4;010)=3(比特)也可直接计算出：(比特),P(x4100)=1,例：某地二月份

8、气候的概率空间为,则此四种天气状态的不确定性分别为：,假如有天气预报说“今天不是晴天”（作为收到的消息y1)，收到y1后（假设y1是准确的），再去重新估计各种天气发生的概率。,它们之间的互信息量为：,收到消息y1之后，使得x2，x3，x4的不确定性各降低了1bit，这是由于互信息量的存在，使得不确定性减少。,自信息量减去互信息量是收到消息y1之后，x2，x3，x4仍存在的不确定性，因为不知道到底会发生哪件事情。,收到消息y1之后使得x1的不确定性降低了负无穷（增加了无穷大的不确定性），即收到y1之后，x1 基本不会再发生。,2.2 离散集的平均自信息量,一信 息 熵,1平均自信息量（熵）,对于

9、无记忆信源，各个消息的出现概率是相互统计独立的，其平均自信息量定义为各消息自信息量的概率加权平均值（统计平均值），即平均自信息量H(X)定义为：,唯一确定事件xi所需要的信息量。,唯一确定集合X中任一事件xi所需要的平均信息量，它反映了X中事件xi出现的平均不确定度。,集合X的信息熵，简称熵,信息熵和平均自信息量两者在数值上相等，但含义并不相同。信息熵表征信源的平均不确定度，平均自信息量则表示消除不确定度所需要的信息的量度。,【例】计算下列信源的熵。,（1）信源一：,（比特/符号）,（2）信源二：等概率信源,（3）信源三：等概率信源,（比特/符号）,（比特/符号）,（4）信源四：信源为确定事件

10、,（比特/符号）,（5）信源五：一般情况下的二元信源,（比特/符号）,2平均条件自信息量（条件熵）,（1）定义：,若事件xi yj的联合分布概率为p(xi yj)，给定yj条件下事件xi的条件自信息量为 I(xi/yj)，则条件熵H(X/Y)定义为：,在联合符号集合XY上的条件自信息量的联合概率加权统计平均值。,当X，Y统计独立时，有p(xi yj)p(xi)p(yj)，p(xi/yj)=p(xi)，则,（2）物理含义:,从通信角度来看，若将X=x1，x2，xi，视为信源输出符号；Y=y1，y2，yj，视为信宿接收符号；I(xi/yj)可看作信宿收到yj后，关于发送的是否为xi仍然存在的不确定

11、性，则,反映了经过通信后，信宿符号yj(j=1,2,)关于信源符号xi(i=1,2,)的平均不确定性，称疑义度。,（3）条件熵H(YX),若给定xi条件下事件yj的条件自信息量为I(yj/xi)，则H(Y/X)定义为：,当X，Y统计独立时，有p(xi yj)=p(xi)p(yj)，p(yj/xi)=p(yj)，有,从通信角度来看，H(Y/X)是发出确定消息xi后，由于信道干扰而使yj存在的平均不确定性，称H(Y/X)为噪声熵（散布度）。,3联合熵（共熵）,联合熵H(XY)是定义在二维空间X Y上，对元素xi yj的自信息量的统计平均值，若记事件xi yj出现的概率为p(xi yj)，其自信息量

12、为I(xi yj)，则联合熵H(X Y)定义为：,4各种熵之间的关系,由熵、条件熵、联合熵的定义式可导出三者的关系式：,H(X Y)=H(X)+H(Y/X)=H(Y)+H(X/Y),上式反映了信息的可加性。当X，Y统计独立时，有,H(X Y)=H(X)+H(Y),1凸集合与凸函数简单介绍凸集和凸函数的概念。定义2.1 是n维实矢量空间集合R中任意两个n维矢量，对实数，0 1，有+（1-）R则称R为凸集合。,二熵函数的性质,从几何上来看，若，是集合R中的任意两点，+（1-）表示这两点间的连线，若该连线也在集合R中，则称R为凸集。下面给出了几个凸集和非凸集合的例子。,定义2.2设f(x)=f(x1

13、,x2,xn)为一个n元函数，若对任意f(x1),f(x2)f(x)，任意正数，0 1，有f(x1)+（1-）f(x2)f x1+（1-）x2(2-23),x,则称f(x)为定义域上的型凸函数。一元型凸函数可用图2-4所示的几何图形表示。,定义2.3设f(x)=f(x1,x2,xn)为一个n元函数，若对任意f(x1),f(x2)f(x)，任意正数，0 1，有f x1+（1-）x2 f(x1)+（1-）f(x2)(2-24),则称f(x)为定义域上的型凸函数，一元型凸函数可用图2-5所示的几何图形表示。,二熵函数的性质,1极大离散熵定理,设信源X中包含M个不同的符号，信源熵H(X)有,当且仅当X

14、中各个符号以等概率出现时，上式取等号。,2熵函数的性质,（1）对称性,集合X=x1，x2，xN 中的各元素x1，x2，xN任意改变其顺序时，熵只和分布（概率）有关，不关心某个具体事件对应哪个概率。,例：某二进制通信系统，信源符号集0，1，由于存在失真，传输时会产生误码，用符号表示下列条件：u0：发“0”；u1：发“1”；v0：收“0”；v1：收“1”。已知下列概率：,则此信道转移概率示意图为：,求：（1）已知发出符号“0”，收到一个符号所获得的平均信息量,（2）已知发出的符号，收到一个符号所获得的平均信息量,转移概率矩阵p(v/u),联合概率矩阵 p(uv),（3）已知发出和收到符号，所获得的

15、平均信息量,或可由定义式求：,联合概率矩阵 p(uv),（4）收到一个符号后又被告知发出的符号，所获得的平均信息量,联合概率矩阵 p(uv),先求接收符号的概率：,后验概率矩阵 p(u/v)=p(uv)/p(v),或者：,2.4 N维扩展信源的熵和平均互信息量,一各种离散信源的熵,信源输出序列为XN=x1 xi xN，xia0,a1,ak-1，记 XN=x1 x 2 xN的概率分布为p(XN)，则信源熵为,（1）单符号无记忆信源,由于无记忆，则信源的熵为：,（2）N维扩展无记忆信源,H(XN)=H(X1)+H(X2X1)+H(X3X1X2)+H(XNX1X2XN-1),p(XN)=p(x1)p

16、(x2x1)p(x3x1x2)p(xNx1x2xN-1)，可以计算出其信源熵,一般情况下，同一信源输出的各事件x1 xi xN，其概率分布空间相同(平稳信源)，即各xi取值a0,a1,ak-1的概率相同，此时有,【例】二进制对称信源只能输出符号0或1，信源概率空间描述为：,进行二维无记忆扩展，则信源序列共M224种：00，01，10，11。,则将这4种序列看成4个符号，得到一个新的信源，即,（3）平稳有记忆N维扩展信源,在信源输出符号相互有关连的情况下，信源输出序列XN=x1 x 2 xN 的概率为p(XN)=p(x1)p(x2x1)p(x3x1x2)p(xNx1x2xN-1)，相应可以计算出

17、其信源熵,H(XN)=H(X1)+H(X2X1)+H(X3X1X2)+H(XNX1X2XN-1),根据熵的性质，条件熵小于等于无条件熵，有,可得：,等号在信源无记忆（统计独立）时成立。,对于平稳信源，有,等号在信源无记忆时成立。,当N较小的时候，N维扩展信源的联合熵计算还比较简单,例：某平稳信源 若此信源发出的符号只与前一符号有关，,其联合概率矩阵为,其转移概率矩阵为,若不考虑关联性，信源熵,若考虑关联性，条件熵,联合熵,当N较大的时候，N维扩展信源的联合熵计算很困难,随着条件的增加，条件熵越来越小，即条件熵是N的单调非增函数。,当N足够大时，H(XNX1X2XN-1)几乎不再随N的增大而减小

18、，而是趋于一个定值。,对于平稳有记忆N维扩展信源，我们一般求N长符号序列中，平均每个信源符号所携带的不确定性（平均符号熵）。,定义：XN的平均符号熵,N长随机符号序列中单个符号的平均信源熵。,根据条件熵的性质，随着N增大，N维条件熵减小，H(XN)的增加变缓，HN(X)减小。因此有：,离散信源的极限熵（极限信息量、极限符号熵、熵率）,若信源输出符号xia0,a1,ak-1，则H0(X)=log k（即假设信源是等概分布的离散无记忆信源）。,定理（证明略）：对任意平稳信源，只要H1(X),则有H(X)存在，且,因此，N长随机符号序列的极限符号熵可以转化为条件熵来计算。,实际中，一般的离散平稳信源

19、输出符号的相关性随N的增加而迅速减小（如语言中的词语，句子），此时，N不很大时的条件熵跟极限条件熵就很接近，因此实际中常用有限N时的条件熵来近似H(X)：,因此，对于有限记忆长度为M（即某时刻发什么符号只与前M个符号有关）的离散平稳信源，可以用有限记忆长度的条件熵来对离散平稳信源进行信息测度。,工程上很实用,p(si)为各状态的平稳分布。,对于m阶马尔可夫信源，其信源（符号）熵为,（4）时齐的有限状态马尔可夫信源（用上述方法求解）,前一时刻m阶马氏信源的状态,信源发出的下一个符号,已知当前状态的条件下，信源发出下一个符号的平均不确定度,这个计算要简单得多，只需要知道转移概率矩阵就可以,【例】某

20、二阶平稳时齐马尔可夫信源，设信源符号集为a1，a2，状态集为s1=a1a1，s2=a1a2或a2a2，s3=a2a1，各状态之间的转移情况如图(香农线图)所示，求信源熵。,转移概率矩阵为：,各状态稳态概率分布：,R为零时，信源的实际熵就等于最大值H 0(X)，这表明信源符号之间不但统计独立无记忆，而且各符号还是等概率分布。,补充 信源冗余度及信息变差,冗余度也叫多余度或剩余度，它表示一个信源在实际发出消息时所包含的多余消息。冗余度来自两个方面：,R越大，信源的实际熵H(X)越小，信源符号之间依赖关系越强，即符号之间的记忆长度越长。,信源符号间的依赖性越大，信源的实际熵越小，越趋近H(X)。,一

21、是信源符号之间的相关性，,另一方面是信源分布的不均匀性，信源符号等概率分布时，信源熵最大，而实际中大多数信源是不均匀分布的，使得实际熵H H0(X)。,H0 最大熵H实际熵(1)相对熵率=H/H0(2)冗余度 R=1-=I0/H0(3)信息变差 I0=H0-H,R越小，信源的实际熵H(X)越大，信源符号之间依赖关系越弱，即符号之间的记忆长度越短。,例 英语26字母加 空格共27个符号。H0=4.76 bit/符号,H1=4.03 bit/符号,H2=3.32 bit/符号,H3=3.10 bit/符号 H=1.40 bit/符号，且=0.29，R=0.71，I0=3.36 bit/符号 说明

22、英文中，有71%冗余度，是由语言结构决定的，该部分无需传输，可压缩。于是：冗余度信源可压缩程度。,例 将常用的10000个汉字看做10000个符号。H0=13.288 bit/符号,H1=9.773 bit/符号,=0.736，R=0.264 说明 汉语信源中，每个汉字出现的概率不但不相等，而且有一些常用的词组。单字之间有依赖关系，词组之间也有依赖关系。如果将这些依赖关系考虑进去，计算相当复杂，但是实际汉语信源的熵一定也很小，冗余度相当大。,2.3 离散集的平均互信息量,一平均互信息量,1平均互信息量,定义xiX和yjY之间的互信息量为I(xi;yj)，在集合X上对I(xi;yj)进行概率加权

23、统计平均，可得I(X;yj)为：,再对集合Y进行统计平均，就可以得到平均互信息量：,当X，Y统计独立时，I(xi；yj)=0，从而I(X；Y)=0。,【例】二元等概率信源X通过信道转移概率矩阵为P的信道传输，信宿接收符号Y=y0，y1，计算信源与信宿间的平均互信息量I（X；Y）,【解】（1）根据 得：,（2）由 求后验概率。,（3）计算各消息之间的互信息量I(xi;yj),（比特）,（比特）,（比特）,（比特）,（4）计算平均互信息量,2平均条件互信息量,平均条件互信息量I(X;YZ)是在联合概率空间XYZ，p(xyz)上定义的物理量。由条件互信息量公式,对上式在三维空间XYZ上求概率加权平均

24、值，就得到平均条件互信息量。,二平均互信息量的性质,1平均互信息量的性质,（1）非负性,（2）互易性（对称性）,（3）平均互信息量小于发送符号、接收符号的信源熵,2平均互信息量与信源熵、条件熵的关系,3平均互信息量的物理意义,从通信的角度来讨论平均互信息量I(X;Y)的物理意义：,（1）由第一等式 I(X;Y)=H（X）-H（XY）看I(X;Y)的物理意义：,设X为发送消息符号集，Y为接收符号集，H(X)是输入集的平均不确定性，H（XY）是观察到Y后，集X还保留的不确定性，二者之差I(X；Y)就是在接收过程中得到的关于X；Y的平均互信息量。,对于无扰信道，I(X;Y)=H(X)。对于强噪信道，

25、I(X;Y)=0。,（2）由第二等式I(X;Y)=H（Y)-H（YX）看I(X;Y)的物理意义：,H(Y)是观察到Y所获得的信息量(Y 的平均不确定性），H（YX）是发出确定消息X后，由于干扰而使Y存在的平均不确定性，二者之差I(X;Y)就是一次通信所获得的信息量。,对于无扰信道，有I(X;Y)=H(X)=H(Y)。对于强噪信道，有H（YX）=H（Y），从而I(X;Y)=0。,（3）由第三等式I(X;Y)=H(X)+H(Y)-H(XY)看I(X;Y)的物理意义,通信前，随机变量X和Y可视为统计独立，其先验不确定性为H(X)+H(Y)，通信后，整个系统的后验不确定性为H(XY)，二者之差H(X)

26、H(Y)H(XY)就是通信过程中不确定性减少的量，也就是通信过程中获得的平均互信息量I(X；Y)。,【例】已知信源消息集为X=0,1,接收符号集为Y=0,1，通过有扰信道传输，其传输特性如图所示，这是一个二进制对称信道BSC。已知先验概率为等概率，计算平均互信息量I(X;Y)及各种熵。,【解】设p(x)为信源输入概率；p(y)为信宿输出概率；p(y/x)为信道转移概率；p(x/y)为后验概率。,（1）由图及 得,（2）由 得,（3）由 计算后验概率,（4）计算各种熵及平均互信息量：,信源熵：,信宿熵：,联合熵：,三有关平均互信息量的两条定理,平均互信息量：,疑义度：,散布度：,平均互信息量定义

27、为:,上式说明I(X;Y)是信源分布概率p(x)和信道转移概率p(yx)的函数。,下面两条定理阐明了I(X;Y)与p(x)和p(yx)之间的关系。,定理1：当信道给定，即信道转移概率p(yx)固定，平均互信息量I(X;Y)是信源概率分布p(x)的型凸函数。,定理1说明，信道固定时，对于不同的信源分布，信道输出端获得的信息量是不同的。因此，对于每一个固定信道，一定存在一种信源（一种分布）p(x)，使输出端获得的信息量最大。,定理2：当信源给定，即信源分布概率p(x)固定，平均互信息量I(X;Y)是信道转移概率p(yx)的型凸函数。,定理2说明，信源固定以后，用不同的信道来传输同一信源符号时，在信

28、道输出端获得的信息量是不同的。可见，对每一种信源一定存在一种最差的信道，此信道的干扰最大，而使输出端获得的信息量最小。,【例2.16】二进制对称信道BSC如图2-10所示，输入符号集X=x1,x2=0,1，输出符号集Y=y1,y2=0,1，信道转移概率矩阵，信源分布为：，计算平均互信 息量 I(X;Y)=H（Y）-H（YX）,先由 算出：(0)=q(0)p(00)+q(1)p(01)=p(1-)+(1-p)(1)=1-(0),再计算熵和条件熵=H2 p(1-)+(1-p)=-(1-)log(1-)-log=H2(),则平均互信息量I(X;Y)=H（Y)-H（YX）=H2 p(1-)+(1-p)

29、-H2(),当信道固定，即 为恒值，则I(X;Y)是p的函数，其曲线如下图2-11所示。,当p=0.5时,I(X;Y)取得极大值，其值为log 2-H2(),这种情况对应等概分布,信源的平均不确定性最大.当p=0或1时，这是确定信源的情况，通信得不到任何信息，即I(X;Y)=0。,二N维扩展信源的平均互信息量,二维情况：,推广到三维：,推广到N维矢量：,对于复合事件的平均互信息量，下式成立：,复合事件的互信息量大于单个事件的互信息量。,三有关N维平均互信息量的两条定理,定理1：如果信源离散无记忆，即信源输出序列XN=x1 x2 xN中各xi(i=1,2,N)统计独立，则信道输入、输出符号序列间

30、的平均互信息量I（XN；YN）大于等于各单个符号间平均互信息量的总和，即有,定理2：若信道离散无记忆，则信道输入、输出符号序列间的平均互信息量I（XN；YN）小于等于各单个符号间平均互信息量的总和，即有,本 章 小 结,1本章主要阐述了对各种信息量的度量，主要内容如下：,（1）自信息量：,对自信息量求统计平均，得信源熵：,（2）条件自信息量：,对条件自信息量求联合统计平均，得条件熵：,（3）联合自信息量：,对联合自信息量求联合统计平均，得联合熵：,（4）互信息量：,2前面针对个别事件的各种信息量，可看作是一过渡物理量，我们关心的还是它们所对应的统计平均值，上面列出的4个有关信息量的统计平均值，可用维拉图帮助理清他们之间的关系。,3本章介绍了三个重要定理，请予关注（1）极大熵定理（2）信道给定，I（X；Y）是信源的型凸函数（3）信源给定，I（X；Y）是信道的型凸函数,