第2讲离散信源的非平均信息量和熵2014

第二讲熵和互信息量,信源,信道,信宿,噪声源,编码器,译码器,消息,干扰,接收信号,消息,数字通信系统模型,中心问题：有效性、可靠性,发送信号,信息、消息和信号,信息事物运动状态或存在方式不确定性的描述。,消息指包含有信息的语言、文字和图像等。信号消息的物理体现。,2.1离散信源的数学模型及信息测度（I）,信源的数学描述,通信系统中收信者在未收到消息以前对信源发出什么消息是不确定的,是随机的。可用随机变量、随机序列或随机过程来描述信源输出的消息，或者说用一个样本空间及其概率测度概率空间来描述信源。,根据信源输出的消息的不同随机性质可以对信源进行分类：按照某时刻信源输出消息的取值集合的离散性和连续性,信源可分为离散信源和连续信源。按照信源输出消息的所对应的随机序列中随机变量前后之间有无依赖关系，信源可分为无记忆信源和有记忆信源。按照信源输出消息的所对应的随机序列或随机过程的平稳性,信源可分为平稳信源和非平稳信源。,信源的分类,离散信源：可能输出的消息是有限的或可数的，每次只输出一个消息，即两两不相容。数学模型：,注：X代表随机变量，指的是信源整体；ai代表信源的某个元素。,简单信源,数学模型：,注：这里的p(x)代表概率密度函数。,简单信源,连续信源：可能输出的消息数是无限的或不可数的，每次只输出一个消息。,离散信源在不同时刻发出的符号之间是无依赖的彼此统计独立的。,其中，,且,离散无记忆信源,由离散无记忆信源输出N长的随机序列构成的信源。,离散无记忆信源N次扩展信源,掷两枚硬币,掷一枚硬币,离散平稳信源：输出的随机序列中每个随机变量取值是离散的，并且随机矢量X的各维概率分布不随时间平移而改变。连续平稳信源：输出的随机序列中每个随机变量取值是连续的，并且随机矢量X的各维概率密度函数不随时间平移而改变离散无记忆信源：离散信源在不同时刻发出的符号之间是彼此统计独立的。,其它几种常见信源,有记忆信源：输出的随机序列X中各随机变量之间有依赖关系，但记忆长度有限。m阶马尔可夫信源：信源每次发出的符号只与前m个符号有关，与更前面的符号无关。随机波形信源：信源输出的消息在时间上和取值上都是连续的。,其它几种常见信源,设单符号离散信源的概率空间为,自信息量定义,如果知道事件xi已发生，则该事件所给出的信息量称为自信息，定义为:,对数换底关系：,自信息量定义,I(xi)含义当事件xi发生以前，表示事件xi发生的不确定性当事件xi发生以后，表示事件xi所含有的信息量I(xi)单位常用对数底是2，信息量的单位为比特(bits，binarydigits）)；若取自然对数，则信息量的单位为奈特(nats，naturaldigits）);1natlog2el.433bit,或,(1)I(xi)是非负值(2)当p(xi)=1时，I(xi)=0(3)当p(xi)=0时，I(xi)=(4)I(xi)是先验概率p(xi)的单调递减函数，即当p(x1)p(x2)时，I(x1)I(x2)(5)两个独立事件的联合信息量等于它们分别的信息量之和，即统计独立信源的信息量等于它们分别的信息量之和。,自信息的性质,二进制码元0,1，当符号概率为p(0)=1/4,p(1)=3/4,则这两个符号的自信息量为：I(0)=-log2(1/4)=log24=2bitsI(1)=-log2(3/4)=0.4151bits,一个以等概率出现的二进制码元(0,1)所包含的自信息量为：,自信息量例题,I(0)=I(1)=-log2(1/2)=log22=1bits,自信息量例题,一次掷两个质地均匀的色子，求下列事件发生后提供的信息量。a.仅有一个数字为3；b.至少有一个数字为4；c.两个数字之和为偶数。解：一个色子有6个数字，X=1,2,3,4,5,6，两个色子数字组合总数为36。a.事件概率为5*2/36=5/18b.事件概率为（52+1）/36=11/36c.事件概率为63/36=1/2则：I(a)=log(18/5)=1.848(bits)I(b)=log(36/11)=1.7105(bits)I(c)=log2=1(bits),考虑两个随机事件，其联合概率空间为,联合自信息与条件自信息,在事件yj出现的条件下，随机事件xi发生的条件自信息量,条件自信息量,联合自信息量,联合自信息量和条件自信息量关系,当X和Y独立时，,信源各个离散消息的自信息量的数学期望（即概率加权的统计平均值）为信源的平均信息量，称为信源的信息熵，也叫信源熵或香农熵，简称熵。熵函数的自变量是X表示信源整体，熵是离散无记忆信源平均不确定度的度量。自信息表示某一消息所含有的信息量，它是一个随机变量，不能用它来作为整个信源的信息测度。,信源熵定义,信源熵H(X)的物理含义观测X所获得的平均信息量；信源X的平均不确定度；（反映了随机变量X的随机性）消除信源不确定度所需要的信息量度.对该信源输出进行无错编码所需的最小编码长度;,信源熵理解,注意:,高清电视屏上约有1920*1080=2.0736106个格点，按每格点有8个不同的灰度等级考虑，则共能组成个不同的画面。,=6.2208106bits,信源熵例题,按等概率计算，平均每个画面可提供的信息量为,有一篇千字文章，假定每字可从万字表中任选，则共有不同的千字文N=100001000=104000篇仍按等概率1/100001000计算，平均每篇千字文可提供的信息量为H(X)log2N1.3104bits,“一个电视画面”平均提供的信息量远远超过“一篇千字文”提供的信息量。,信源熵例题,例如有两个信源，其概率空间分别为:,因为H(Y)H(X)所以信源Y比信源X的平均不确定性要大。,信源熵例题,该信源X输出符号只有两个,设为0和1输出符号发生的概率分别为p和q，pq=l，即信源的概率空间为,则二元信源熵为H(X)=-plogp-qlogq=-plogp-(1-p)log(1-p)=H(p),信源熵例题,H(p)=-plogp-(1-p)log(1-p),条件熵是在联合符号集合XY上的条件自信息量的数学期望。在已知随机变量Y的条件下，随机变量X的条件熵定义为：,要用联合概率加权,条件熵是一个确定值，表示信宿在收到Y后，信源X仍然存在的不确定度。这是传输失真所造成的。有时称H(X/Y)为信道疑义度，也称损失熵。称条件熵H(Y/X)为噪声熵。,条件熵,联合离散符号集合XY上的每个元素对的联合自信息量的数学期望。,联合熵,进一步扩展,熵、条件熵、联合熵关系,当Ui相互独立时,当X和Y相互独立时,一个二进信源X发出符号集0,1，经过离散无记忆信道传输,信道输出用Y表示.由于信道中存在噪声,接收端除收到0和1的符号外,还有不确定符号“2”已知:X的先验概率:p(x0)=2/3,p(x1)=1/3,符号转移概率：p(y0|x0)=3/4,p(y2|x0)=1/4p(y1|x1)=1/2,p(y2|x1)=1/2，,X,Y,0,1,0,1,2,3/4,1/2,1/2,1/4,信源熵H(X),例题,得联合概率：p(x0y0)=p(x0)p(y0|x0)=2/33/4=1/2p(x0y1)=p(x0)p(y1|x0)=0p(x0y2)=p(x0)p(y2|x0)=2/31/4=1/6p(x1y0)=p(x1)p(y0|x1)=0p(x1y1)=p(x1)p(y1|x1)=1/31/2=1/6p(x1y2)=p(x1)p(y2|x1)=1/31/2=1/6,由,例题,噪声熵H(Y|X),X,Y,0,1,0,1,2,3/4,1/2,1/2,1/4,联合熵H(XY)H(XY)H(X)H(Y|X)=1.8bits,得p(y0)=p(xiy0)=p(x0y0)+p(x1y0)=1/2+0=1/2p(y1)=p(xiy1)=p(x0y1)+p(x1y1)=0+1/6=1/6p(y2)=p(xiy2)=p(x0y2)+p(x1y2)=1/6+1/6=1/3,由,例题,信道输出熵H(Y),由,得,同理p(x0|y1)=0；p(x1|y1)=1p(x0|y2)=1/2；p(x1|y2)=1/2,信道疑义度H(X|Y),例题,或H(X|Y)=H(XY)-H(Y)=1.8-1.47=0.3333bit,注意：信源熵H(X)=0.9183its-.585bits,熵的基本性质,概率矢量,熵函数,非负性,非负性H(X)0,由于0pk1,所以logpk0，-logpk0，则总有H(X)0。,对称性,根据加法交换律可以证明，当变量交换顺序时熵函数的值不变,即信源的熵只与概率空间的总体结构有关，而与各概率分量对应的状态顺序无关。,对称性,确定性,当信源X的信源空间X，P中，任一概率分量等于1，根据完备空间特性，其它概率分量必为0，这时信源为一个确知信源，其熵为0。,确定性,这说明信源空间中增加某些概率很小的符号，虽然当发出这些符号时，提供很大的信息量，但由于其概率接近于0，在信源熵中占极小的比重，使信源熵保持不变。,扩展性,扩展性,可加性,证明:,可加性,极值性最大离散熵定理,信源X中包含K个不同离散消息时，信源熵，当且仅当X中各个消息出现的概率全相等时，上式取等号。,表明等概信源的不确定性最大，具有最大熵，为,极值性,H(p)1.00.500.51p,二元离散信源,H(p)=-plogp-(1-p)log(1-p),引理1（常用对数不等式）：lnxx-1,当且仅当x=1时等号成立。,令f(x)=lnx(x-1),则,可见，f(x)是x的上凸函数，且当x=1时，f(x)有极大值。故,即lnx(x-1),f(x)=lnx-(x-1)0,证明：,令，可得即等概时熵最大，为。,证明：,引理2香农辅助定理,极值性最大离散熵定理,信源X中包含K个不同离散消息时，信源熵，当且仅当X中各个消息出现的概率全相等时，上式取等号。,表明等概信源的不确定性最大，具有最大熵，为,极值性,定理：1.H(X/Y)H(X)（条件熵不大于无条件熵）2.H(XY)H(X)+H(Y),证明：,基本定理,由定理1，得,基本定理推广,H(X/Y)H(X),H(XY)H(X)+H(Y),相互独立时等号成立,唯一性香农指出，存在这样的不确定性的度量，它是概率分布的函数，且该函数应满足：对称性极值性可加性扩展性它的形式是唯一的。,唯一性,27个硬币中有一个重量偏轻，其它26个为标准重量。试用信息量观点分析在不用砝码的天平上至少称多少次，就能发现这个轻的硬币？怎样称？,思考:,设有4枚同值硬币，其中1枚