《离散信源.ppt》由会员分享，可在线阅读，更多相关《离散信源.ppt（59页珍藏版）》请在三一文库上搜索。
1、2 离散信源,2.1 离散信源的信息熵 2.2 熵的基本性质 2.3 信源的相关性与剩余度,信源的数学模型及分类 信息熵 联合熵与条件熵,2.1 离散信源的信息熵,一、 信源的数学模型与分类,概率空间:,样本空间,概率函数,例1：,P(a1)P(a2)1,例2：,2.1 离散信源的信息熵,一、 信源的数学模型与分类,抛硬币,音频信源,2.1 离散信源的信息熵,一、 信源的数学模型与分类,或,概率空间:,2.1 离散信源的信息熵,信源,离散无记忆信源 （DMS）,离散有记忆信源,离散 信源,连续 信源,简单DMS：,复杂信源：,时间离散的连续源,随机波形源,简单连续信源：,一、信源的数学模型与分
2、类,则其中事件ai的自信息为：,设离散信源X，其概率空间为：,2.1 离散信源的信息熵,二、 信息熵,例3,2.1 离散信源的信息熵,定义2-1： 信源输出各消息的自信息量I(ai)的数学期望为信源的平均自信息量，即：,又称为信源X的信息熵或熵。,二、 信息熵,2.1 离散信源的信息熵,平 均 自 信 息,对象,概率矢量,对某给定信源，信息熵H(X)的取值是固定的，而不是随机变量。,二、 信息熵,说明：,例4一组信源：,2.1 离散信源的信息熵,二、 信息熵,熵平均自信息,说明：,2.1 离散信源的信息熵,（A）描述信源X的平均不确定性,含义,（B）平均每个信源符号所携带的信息量,三、 信息熵
3、,例5 (从另一角度领会信息熵的含义) 若布袋内放100个球。其中，70个是红色（a1）；30个是白色（a2）。现随机摸出一个球猜颜色，求平均每次试验的信息量。,2.1 离散信源的信息熵,说明：,（A）描述信源X的平均不确定性,含义,（B）平均每个信源符号所携带的信息量,I(ai)与H(X),bit/sig, nat/sig, hart/sig,相同点： （本质）描述不确定性大小,不同点：（对象）个别事件与整个集合,辨析,单位,二、 信息熵,2.1 离散信源的信息熵,练习：,2 离散信源,2.1 离散信源的信息熵 2.2 熵的基本性质 2.3 信源的相关性与剩余度,信源的数学模型及分类 信息熵
4、 联合熵与条件熵,定义2-2：联合集XY上，联合自信息的平均值定义为联合熵，即：,2.1 离散信源的信息熵,三、 联合熵与条件熵,例6：,已知DMS：,2.1 离散信源的信息熵,(联合熵的应用),三、 联合熵与条件熵,N次扩展信源的数学模型：,2.1 离散信源的信息熵,含义：扩展信源XN中平均每个消息序列提供的信息量。 (bit/N-sigs),三、 联合熵与条件熵,(联合熵的应用),定义2-3：联合集XY上，条件自信息的平均值定义为条件熵，即：,2.1 离散信源的信息熵,三、 联合熵与条件熵,设箱中有100个球，其中40个黑球，60个白球。做从箱中取球且不放回试验，连续进行两次，试求猜中第二
5、个球颜色的难度。,例7：,解：,2.1 离散信源的信息熵,（用X表示取出第一个球的颜色，Y表示取出第二个球的颜色）,三、 联合熵与条件熵,黑,白,2.1 离散信源的信息熵,(条件熵的应用),且P(aiaj)=P(ai)P(aj|ai) (i,j=1,2,q)，,问题：信源X平均每符号输出信息量？,设：二维离散平稳信源X,三、 联合熵与条件熵,2.1 离散信源的信息熵,(条件熵的应用),二维平稳信源熵：,三、 联合熵与条件熵,例8：,有一连续信源，其输出信号的概率密度曲线如下图所示，现将信号等间隔采样，并量化为3个电平，则该连续信源转换成三元离散信源，其符号间的条件概率分布如下表所示。求该离散信
6、源熵。,2.1 离散信源的信息熵,(二维离散平稳信源),三、 联合熵与条件熵,离散二维平稳信源,二维联合概率,2.1 离散信源的信息熵,三、 联合熵与条件熵,2.1 离散信源的信息熵,小结：,自信息,熵,条件自信息,联合自信息,联合熵,条件熵,考虑两个随机事件,考虑两个随机事件集合,习题：,设（X，Y）服从如下联合分布，试求 H(X)，H(Y)，H(X|Y)，H(Y|X)，H(XY)。,2.1 离散信源的信息熵,思考题1： 设X是取值有限的随机变量，如果：,H(X)和H(Y1)及H(Y2)的关系是怎样的？,2.1 离散信源的信息熵,思考题2:,2.1 离散信源的信息熵,预习：第2.2和2.3节
7、。,2.1 离散信源的信息熵,2 离散信源,2.1 离散信源的信息熵 2.2 熵的基本性质 2.3 信源的相关性与剩余度,2. 2 熵的基本性质,1. 非负性,2. 确定性,3. 对称性,(i1,iq)为（1q）任意排列,4. 扩展性,习题,确知信源熵为0,2. 2 熵的基本性质,3. 对称性,例：分别计算下列信源熵：,2. 2 熵的基本性质,1. 非负性,2. 确定性,确知信源熵为0,3. 对称性,(i1,iq)为（1q）任意排列,熵只与随机变量的总体结构有关,4. 扩展性,极小概率事件对熵几乎无影响,习题,5. 熵的链式法则,2. 2 熵的基本性质,若X和Y统计独立，则,熵的 强可加性,熵
8、的 可加性,5. 熵的链式法则,2. 2 熵的基本性质,1. 试证明（强可加性）：,习题：,2. 2 熵的基本性质,2. 对于离散无记忆信源X的N次扩展信源XN，其信息熵为X信源熵的N倍，即：,当且仅当P1=P2=Pq=1/q时，信源具有最大熵。,2. 2 熵的基本性质,6. 极值性,证明（极值性）：,2. 2 熵的基本性质,引理：若x0，则： lnxx-1（即log2x(x-1)loge）, （当且仅当x=1时成立）,证明：,当且仅当 1/piq=1即pi1/q时等式成立。,当且仅当P1=P2=Pq=1/q时，信源具有最大熵。,信源中各事件出现概率趋于均匀时，信源的平均不确定性最大。 （数据
9、压缩的理论依据之一）,最大离散熵定理,2. 2 熵的基本性质,6. 极值性,例：,设二元信源X为,则有,熵是随机变量X概率分布的上凸函数； p=0或1时，H(p)=0； p=0.5时，H(p)达到最大 1( bit/sig)。,2. 2 熵的基本性质,练习：,2. 2 熵的基本性质,比较概率分布,的熵与概率分布,的熵的大小？,知道统计相关的变量，则可以减少不确定性； 统计平均意义上条件减少不确定性，但是针对具体的Y取值则不一定。,2. 2 熵的基本性质,7. 熵的独立界,条件作用使熵减小,定理2.2：设 服从P(x1,x2,xN)，则,当且仅当 相互独立时取等号。,（证明提示：联系链式法则）,
10、2. 2 熵的基本性质,7. 熵的独立界,熵的独立界,PX(0)=2/3, PX(1) = 1/3,H(X)=?,H(X|Y=0) = ?,H(X|Y=2) = ?,H(X|Y) = ?,H(X) = H(2/3,1/3)=0.9183 (bit/sig),H(X|Y=0) = 0,H(X|Y=1) = 0,H(X|Y) = 1/3 (bit/sig),H(X|Y=2) = H(1/2,1/2)=1 (bit/sig),练习：,2. 2 熵的基本性质,H(Y)=?,H(Y)=H(1/2,1/3,1/6)=1.46 (bit/sig),小结：,对称性,确定性,非负性,极值性,上凸性,链式法则,扩
11、展性,条件熵不增,独立界,2. 2 熵的基本性质,2 离散信源,2.1 离散信源的信息熵 2.2 熵的基本性质 2.3 信源的相关性与剩余度,扩展信源：,平稳信源：,2. 3 信源的相关性和剩余度,2. 3 信源的相关性和剩余度,定义：,为信源剩余度。,H H (XN|X1,XN-1) H(X2|X1)H(X1) H0=log q,信源实际熵H与理想熵H0相差越大，信源的剩余度就越大，信源的效率也越低。,例1,英文源：,H0=log27=4.76 (bit/sig),IN NO TH HE ER AN RE ED ON ES ST EN AT TO NT HA ND OU EA NG AS,T
12、HE ING AND HER ERE THA NTH FOR DTH HAT SHE ION INT HIS STH ERS VER ENT,2. 3 信源的相关性和剩余度,VYDYRCHOZ E ZNVDLYVZRAWZSUUKRETAHBCWSI ZALKUVFNMRTUHSREDNZJPGUGNSYZODEGWGVGZJ,T EBSET B TLK TNEIE A AE TUIIETE REAE UVL AES NPNFKDP O ENR TRIFFDII AFDTE TWF AEMBMOA DDEI,例2,中文源：,H0=log10000=13.288 比特/汉字,假设常用汉字约100
13、00个，若它们等概出现，则信源熵为,这10000个汉字中，前140个最常用汉字出现概率占50%，前625个汉字占85%，前2400个汉字占99.7%，其余7600个汉字占0.3%。据此将汉字分为四类，假设每类汉字等概出现，则汉语的信息熵为,比特/汉字,汉字的实际剩余度更大！,2. 3 信源的相关性和剩余度,1.为提高信息传输效率，总希望减少剩余度。,2.为提高信息传输可靠性，需要一定的剩余度。,提高信源输出信息的效率：信源压缩,提高信息传输可靠性：信道编码,例：中华人民共和国压缩成 “中国”,例：发送“中国”错成“X国”,关于信源剩余度的思考：,发送“中华人民共和国”错成“中X人民X和国”,2
14、. 3 信源的相关性和剩余度,数据压缩的基本途径,结论1： 有记忆信源的冗余度寓于信源符号间的相关性中。去除它们之间的相关性，使之成为或几乎成为不相关的信源，其熵将增大。,典型应用:,预测编码,2. 3 信源的相关性和剩余度,H H (XN|X1,XN-1) H(X2|X1)H(X1) H0=log q,信源有记忆,信源无记忆,相关性减弱,均匀性增强,数据压缩的基本途径,2. 3 信源的相关性和剩余度,预测编码简介,初始值,数据压缩的基本途径,2. 3 信源的相关性和剩余度,预测编码简介,200,201,203,202,204,204,原始数据,200,201,203,202,204,预测数据
15、,1,2,-1,2,0,预测误差,1,2,-1,2,0,200,201,203,202,204,预测误差,恢复数据,204,数据压缩的基本途径,2. 3 信源的相关性和剩余度,预测编码简介,根据某种模型，利用以前的（已收到）一个或几个样值，对当前的样本值进行预测，将样本实际值和预测值之差进行编码。,建立一个数学模型,利用以往样本数据，对当前样本值预测,实际值和预测值相减,对差值进行编码,预测重构 差值编码,数据压缩的基本途径,结论1： 有记忆信源的冗余度寓于信源符号间的相关性中。去除它们之间的相关性，使之成为或几乎成为不相关的信源，其熵将增大。,典型应用:,预测编码,变换编码,2. 3 信源的
16、相关性和剩余度,例：,n,fN,变换编码简介,2. 3 信源的相关性和剩余度,先对信源输出进行某种变换，将其从一种信号表示空间变换为另一种信号表示空间，使新的信号空间中各信号分量相关性很小或互不相关，然后再对变换后的分量进行编码，以达到压缩数据的目的。,基本思想：,变换域,目的,变换编码简介,2. 3 信源的相关性和剩余度,yi的方差及比特数分配,变换编码简介,2. 3 信源的相关性和剩余度,结论2：,离散无记忆信源的冗余度寓于符号概率的非均匀分布中。改变原来信源的概率分布，使之成为或接近等概分布的信源，其熵将增大。,典型应用:,统计编码,2. 3 信源的相关性和剩余度,数据压缩的基本途径,预习：第三章3.1和3.2节。,习题：P2526：2、3、8、11、12。,2 离散信源,