第3讲离散信源的熵和互信息2014

第三讲熵和互信息量Review1()loglog()01)()2,;,iaaiiIxpxapxabitsaenats（非负性单位：单位：自信息、联合自信息量、条件自信息量)(log)(jijiyxpyxI)/(log)/(jijiyxpyxI可加性)/()()/()()(jijijijiyxIyIxyIxIyxI平均自信息量，信源熵（信息熵）定义：自信息的数学期望Review()()iHXEIx，熵()(/)ijHXYEIxy，条件熵()()ijHXYEIxy，联合熵熵的物理含义消除信源不确定度所需要的信息量信源输出所提供的平均信息量无错编码所需的最小编码长度)()()()()/()()()()()(YHXHXYHXHYXHYXHYHXYHXHXYHNnnnNNNUUUUHUUUUHUUUHUUHUHUUUH112112121312121)()()()()()(熵、条件熵、联合熵关系ReviewKkkkKpppppHXH121log),()(),...,2,1(0,11KkppkKkk熵的基本性质KKpppxxxPX2121概率矢量熵函数Review非负性H(X)≥01()logKkkkHppPReview对称性信源熵与各概率分量对应的状态顺序无关。确定性(1,0,0,...0)0H扩展性),,,(),,,,(lim21210KKKKpppHpppH极值性——最大离散熵定理()logHXK等概信源的不确定性最大2个基本不等式：1.不等式）：当且仅当x=1时等号成立。2.二个任意概率矢量0,ln1xxxReview11loglog.KKkkkkkkpppqpq有，等号成立的充要条件是=1212(,,...,),(,,...,)KKpppqqqpq设有4枚同值硬币，其中1枚硬币可能是假币，如是假币，其重量与真币不同。现在给你一部没有砝码的天平和1枚真币，问题：回答有无假币？如有假币要求找出那枚假币，并指出那枚假币比真币是轻还是重？试用信息量观点分析最少需称多少次保证一定能找出那枚假币，并给出具体称法。（2次？）设有13枚同值硬币，其中1枚硬币可能是假币，如是假币，其重量与真币不同。现在给你一部没有砝码的天平和1枚真币，问题：回答有无假币？如有假币要求找出那枚假币，并指出那枚假币比真币是轻还是重？试用信息量观点分析最少需称多少次保证一定能找出那枚假币，并给出具体称法。（3次？）具体称法：1，2，3，4，5（真）(1,2),(3,5),41+2,3+5平衡，5,41+2,3+5不平衡，假设1+23+5比较1,2具体称法：1,2,3,4,5,6,7,8,9,10,11,12,13,14（真）1-4，5-9，10-145-9，10-14平衡，余下1-4，2次5-9，10-14不平衡，假设5-910-14;分3组，(5,6,11),(10,7,8),(9,12,13);比较(5,6,11),(10,7,8)，即可判断是出现在（5，6,10），（11,7，8）还是（9,12,13）组。再称1次就可找出那枚假币并给出是轻还是重？第三讲离散无记忆扩展信源)|()|()|()(),,,()(12121312121LLLiiiiiiiiiiiiiixxxxpxxxpxxpxpxxxppx设信源输出的随机序列为序列中的变量Xl∈{x1,x2,…xN}离散无记忆信源LliiiiiiiiilLLxpxpxpxpxpxxxpp1)()()()()(),,,()(32121x离散无记忆信源:)X,...,X,...,X,XLi21（X离散信源的序列熵信源的序列熵)XXX()(L21HHLX平均符号熵)X(1)(LHLHLX)()()()X()H(X)X()(L21XHHXLHHHHLLXX离散无记忆信源例:有一个无记忆信源随机变量X∈(0,1),等概率分布,若以单个符号出现为一事件,则此时的信源熵:bitXH12log)(2bitH24log)X(22bitHH1)X(21)(22X–即用1比特就可表示该事件。•如果以两个符号出现(L=2的序列)为一事件，则随机序列X∈(00,01,10,11)，信源的序列熵–即用2比特才能表示该事件。•信源的符号熵离散无记忆信源实例2()(X)HHXa0a1a2a09/112/110a11/83/41/8a202/97/9例:已知离散有记忆信源中各符号的概率为:419436112101aaaPX设发出的符号只与前一个符号有关,这两个符号的概率关联性用条件概率p(aj|ai)表示,如表p(aj|ai)离散有记忆信源实例由p(ai,aj)=p(ai)p(aj|ai)计算得联合概率p(aiaj)如表a0a1a2a01/41/180a11/181/31/18a201/187/36离散有记忆信源实例bitsaapaapXXHijijij41.2),(log),()(2022021发二重符号序列的熵p(aiaj)平均符号熵符号之间存在关联性bitsXXHH21.1)(21)(212X)X()(12HHX比较有记忆信源实例而信源X的信息熵为bitsapapXHiii543.1)(log)()(201)X()XX(112HH条件熵bitsaapaapXXHiijjij872.0)|(log)()|(202012若信源输出一个L长序列，则信源的序列熵为)|()|()()()(1112121XXXHXXHXHXXXHHLLLLX平均符号熵为)(1)(XXHLHL极限熵离散有记忆信源的极限熵)(limXLLHH（1）条件熵H(XL|X1X2···XL-1)随L的增加非递增离散平稳信源特点（3）平均符号熵HL(X)随L的增加非递增)|(lim)(lim)(121LLLLLXXXXHHXHX（2）L给定时,HL(X)≥H(XL|X1X2···XL-1)（4）)()(23213XXHXXXH)()(1223XXHXXH31221()()HXXXHXX)()(2211121LLLLXXXXHXXXXH)(3212LLXXXXH)/(12XXH对于平稳信源故H(XL|X1X2···XL-1)随L非递增2()HX1()HX（1）条件熵H(XL|X1X2···XL-1)随L的增加非递增离散平稳信源特点（3）平均符号熵HL(X)随L的增加非递增)|(lim)(lim)(121LLLLLXXXXHHXHX（2）L给定时,HL(X)≥H(XL|X1X2···XL-1)（4）HL(X)≥H(XL|X1X2···XL-1))()(21LLXXXHLHX)()()(121121LLXXXXHXXHXH)()(121LLLXXXXHLLHX根据性质1)(121LLXXXXH随L非递增)()(121LLLXXXXHHX故（1）条件熵H(XL|X1X2···XL-1)随L的增加非递增离散平稳信源特点（3）平均符号熵HL(X)随L的增加非递增)|(lim)(lim)(121LLLLLXXXXHHXHX（2）L给定时,HL(X)≥H(XL|X1X2···XL-1)（4）HL(X)随L非递增)()(21LLXXXHLHX)()(121121LLLXXXXHXXXH)()()1(1211LLLXXXXHHLX根据性质2H(XL|X1X2···XL-1)≤HL(X))()()1(1XXLLHHL上式于是)()1()()1(1XXLLHLHL)()(1XXLLHH从而（1）条件熵H(XL|X1X2···XL-1)随L的增加非递增离散平稳信源特点（3）平均符号熵HL(X)随L的增加非递增121()lim()lim(|)LLLLLHHHXXXXXXH1(X)≥H2(X)≥…≥H∞(X)≥0（2）L给定时,HL(X)≥H(XL|X1X2···XL-1)（4）冗余度)()()()(log2102XHXHXHXHn表明信源的记忆长度越长，熵就越小；即信源符号的相关性越强，所提供的平均信息量就越小。为了定量地描述信源的有效性，定义:nXHXHXH20log)()()(nXH2log)(11相对率冗余度小结：多符号离散信源的熵HL(X)–离散无记忆信源–离散有记忆信源()()LHHXX()()LHHXX)(limXLLHHnXH2log)(11-极限熵-冗余度离散信源的互信息•设有两个随机事件X和Y，X取值于信源发出的离散消息集合,Y取值于信宿收到的离散符号集合)()/(XHYXH信道干扰源信源信宿)()()(2121nnxpxpxpxxxPX)()()(2121nnypypypyyyPY互信息定义)(XH的信息量所提供的关于的差值为由与XYH(X/Y))(XHXY);();();()()/(log)()()()(log)()()/(log)();(111111XYIYXIXYIypxypyxpypxpyxpyxpxpyxpyxpYXIjijnimjjijijinimjjiijinimjji)/()();(YXHXHYXI定义：X和Y之间的平均互信息量定义为注：由Y提供的关于X的信息量等于由X提供的关于Y的信息量由定义，可得仿照自信息量，我们也可以定义非平均互信息量);()()|(log)()()(log)()|(log);(ijjijjijiijijixyIypxypypxpyxpxpyxpyxI)|()()|()();(ijjjiijixyIyIyxIxIyxInimjjijijiyxIyxpyxIEYXI11);(),();();()()|(log)/()();(ijijiijixpyxpyxIxIyxI)/()/(log)/;(kikjikjizxpzyxpzyxI)()(log);(ikjikjixpzyxpzyxI条件互信息与联合互信息);()/;(kikjizxIzyxI)()()()(logikikikjixpzxpzxpzyxp)()(log)()(logikikikjixpzxpzxpzyxp条件互信息联合互信息?(;)(;/)ikijkIxzIxyz)/()/(log),,(/;()/;(kikjiijkkjikjizxpzyxpzyxpzyxIEZYXI)/;();()/;();();()()(log),,();(ZYXIZXIzyxIzxIEzyxIExpzyxpzyxpYZXIkjikikjiikjiijkkji条件互信息联合互信息•对称性：•非负性：•与熵的关系：•极值性：);();(XYIYXI0);(YXI)();()();(YHXYIXHYXI平均互信息性质)()()()|()()|()();(XYHYHXHXYHYHYXHXHYXI名称符号图示无条件熵条件熵联合熵平均互信息)(XH)(YH)/(YXH)/(XYH)()(YXHXYH);();(XYIYXIYXYXYXYXYXYX平均互信息与熵之间的关系)|;()|;();();(YZXIZYXIZXIYXI基本关系式);();();();(ZXIYZXIYXIYZXI);();()|;();();();(YZXIXYZIZYX