信息论与编码 信源与信息熵2

12.1信源的描述和分类2.2离散信源熵和互信息2.3离散序列信源熵2.4连续信源的熵和互信息2.5冗余度内容22.3离散序列信源熵32.3离散序列信源熵前面讨论了单个消息（符号）的离散信源熵，并较详细地讨论了它的性质。然而实际信源的输出往往是空间或时间的离散随机序列，其中有无记忆的离散信源熵序列，当然更多的序列是有记忆的，即序列中的符号之间有相关性。此时需要用联合概率分布函数或条件概率分布函数来描述信源发出的符号间的关系。这里讨论离散无记忆序列信源和两类较简单的离散有记忆序列信源(平稳序列和齐次遍历马尔可夫链信源)。4离散信源{离散无记忆信源离散有记忆信源{{发出单个符号的无记忆信源发出符号序列的无记忆信源发出符号序列的有记忆信源发出符号序列的马尔可夫信源2.3.1离散无记忆信源的序列熵•发出单个符号的信源–指信源每次只发出一个符号代表一个消息；•发出符号序列的信源–指信源每次发出一组含二个以上符号的符号序列代表一个消息。5•发出符号序列的信源6/16/16/16/16/16/1101100011010001000PX6/16/16/16/16/16/1654321PX•发出单个符号的信源6离散无记忆信源的序列熵•随机序列的概率为1212(X=)(,,,)1,2,,,1,2,,LiiiLliLppXxXxXxinnix•设信源输出的随机序列为X=(X1X2…Xl…XL)•序列中的单个符号变量Xl∈{x1,x2,…xn},l=1,2,…,L.•X称为离散无记忆信源X的L次扩展信源7离散无记忆信源的序列熵•信源的序列熵为•随机序列的概率为1212131212112131121(=)(,,,)()(|)(|)(|)()(|)(|)(|)LLLLiiiiiiiiiiiiiLiiiiiiiippxxxpxpxxpxxxpxxxxpxpxxpxxpxxXx1212121111()()log()(,,,)log(,,,)LLLLiininnniiiiiiiiiHpppxxxpxxxXxx8离散无记忆信源的序列熵121231()(,,,)()()()()()LLliiiLiiiiiilppxxxpxpxpxpxpxx•当信源无记忆时•信源的序列熵11()()log()()log()()LllniLLLiilillliiHpppxpxHXXxx9离散无记忆信源的序列熵•若又满足平稳特性,即与序号l无关时：()()HLHXX1()()lLLilppxpX•信源的序列熵•平均每个符号(消息)熵为1()()()LHHHXLXX离散无记忆信源平均每个符号的符号熵HL(X)等于单个符号信源的符号熵H(X)10例:有一个无记忆信源随机变量X∈(0,1),等概率分布,若以单个符号出现为一事件,则此时的信源熵:符号/12log)(2bitXH21(X)4log1/42/4Hbit序列符号/1)(21)(2bitHHXX–即用1比特就可表示该事件。•如果以两个符号出现(L=2的序列)为一事件，则随机序列X∈(00,01,10,11)，信源的序列熵–即用2比特才能表示该事件。•信源的符号熵11•例:有一离散平稳无记忆信源414121)(321xxxxpX求：二次扩展信源的熵X2信源的元素a1a2a3a4a5a6a7a8a9对应的消息序列x1x1x1x2x1x3x2x1x2x2x2x3x3x1x3x2x3x3概率p(ai)1/41/81/81/81/161/161/81/161/161291()()()log()3/LiiiHHXpapabit序列Χ符号/5.1)(log)()(31bitxpxpXHiii序列/35.12)(2)(bitXHH•平均每个符号(消息)熵为•信源的序列熵•序列熵为132.3.2离散有记忆信源序列熵•对于有记忆信源,就不像无记忆信源那样简单,它必须引入条件熵的概念,而且只能在某些特殊情况下才能得到一些有价值的结论。•对于由两个符号组成的联合信源,有下列结论:)|()(),|()()|()()|()()(12221121212121XXHXHXXHXHXXHXHXXHXHXXH)()|(),()|()()()(2121212121XHXXHXHXXHXHXHXXH•当前后符号无依存关系时,有下列推论：14•信源的联合熵(即前后两个符号(X1,X2)同时发生的不确定度)等于信源发出前一个符号X1的信息熵加上前一个符号X1已知时信源发出下一个符号X2的条件熵。•对于一般的有记忆信源如文字、数据等，它们输出的不是单个或两个符号，而是由有限个符号组成的序列，这些输出符号之间存在着相互依存的关系。可依照上述结论来分析序列的熵值。离散有记忆信源序列熵15•若信源输出一个L长序列,则信源的序列熵为121211111()()()(|)(|)(|)()LLLLlLllHHXXXHXHXXHXXXHXXHXX•平均每个符号的熵为：)(1)(LLXHLHX•若当信源退化为无记忆时:1()()LllHHXX()()HLHXX若进一步又满足平稳性时16a0a1a2a09/112/110a11/83/41/8a202/97/9•例2-12已知离散有记忆信源中各符号的概率空间为:41943611210aaaPX•设发出的符号只与前一个符号有关,这两个符号的概率关联性用条件概率p(aj|ai)表示,如表.p(aj|ai)•求离散信源的序列熵和平均每个符号熵?17•由p(ai,aj)=p(ai)p(aj|ai)•计算得联合概率p(aiaj)如表a0a1a2a01/41/180a11/181/31/18a201/187/3620()()ijijpaapa•当信源符号之间无依赖性时,信源X的信息熵为1120()()()log()1.543()/iiiHXHXpaitHpab符号X•当考虑符号之间有依赖性时,计算得条件熵符号/872.0)|(log)()|(202012bitaapaapXXHiijjijH(X2|X1)＜H(X)信源的条件熵比无依赖时的熵H(X)减少了0.671比特,这正是因为符号之间有依赖性所造成的结果。18•联合熵H(X1,X2)表示平均每二个信源符号所携带的信息量。•我们用1/2H(X1,X2)作为二维平稳信源X的信息熵的近似值。那么平均每一个信源符号携带的信息量近似为:符号/41.2),(log),(),(202021bitaapaapXXHijijij符号之间存在关联性•发二重符号序列的熵符号/21.1)(21)(22bitXHHX21(X)(1.21/)(X)(1.54/)HbitHbit符号符号比较12121(,)()(|)1.5430.8722.41/HXXHXHXXbit符号或19离散平稳信源•对于离散平稳信源,有下列结论：⑴条件熵H(XL|XL-1)随L的增加是非递增的–条件较多的熵必小于或等于条件较少的熵，而条件熵必小于或等于无条件熵。)()|()|()|()|()|()|(11231222121112121XHXXHXXXHXXXHXXXHXXXHXXXXHLLLLLLLLLL平稳性，联合概率具有时间推移不变性。20⑶HL(X)是L的单调非增函数HL(X)≤HL-1(X)⑷121()lim()lim(|)LLLLLHHHXXXXXX–H∞(X)称为平稳信源的极限熵或极限信息量H0(X)≥H1(X)≥H2(X)≥…≥H∞(X)⑵L给定时,平均符号熵≥条件熵：HL(X)≥H(XL|XL-1)推广结论3可得：不等概率无记忆信源单个符号的熵两个符号组成的序列平均符号熵等概率无记忆信源单个符号的熵21马尔可夫信源的信息熵•马尔可夫信源121112()lim()lim(|)(|)LLLLLmmHXHXHXXXXHXXXX),|(),|(111mLLLLLxxxpxxxp•齐次、遍历的马尔可夫信源的熵()()(|)iiiHpsHXsXjijijisxpsxpsXH)|(log)|()|(马尔可夫链的稳态分布22s2s31/0.61/0.20/0.5s11/0.51/0.10/0.98.02.005.005.09.001.0)|(ijssp59/45,59/9,59/518.05.09.02.05.01.0321321332123121符号符号符号/722.0)8.0,2.0(8.0log8.02.0log2.0)|(/1)5.0,5.0(5.0log5.05.0log5.0)|(/469.0)9.0,1.0(9.0log9.01.0log1.0)|(321bitHsXHbitHsXHbitHsXH()()(|)59450.46910.7220.743/595959iiiHpsHXsbit符号X242.5冗余度25冗余度•冗余度(多余度、剩余度)–表示信源在实际发出消息时所包含的多余信息。•冗余度：–信源符号间的相关性。•相关程度越大,信源的实际熵越小–信源符号分布的不均匀性。•等概率分布时信源熵最大。)()()()(log2102XHXHXHXHn26冗余度•对于有记忆信源,极限熵为H∞(X)。•这就是说我们需要传送这一信源的信息,理论上只需要传送H∞(X)即可。但必须掌握信源全部概率统计特性,这显然是不现实的。•实际上,只能算出Hm(X)。那么与理论极限值相比,就要多传送Hm(X)－H∞(X)。•为了定量地描述信源的有效性,定义:)()(XHXHm)()(11XHXHm信息效率冗余度27冗余度•由于信源存在冗余度,即存在一些不必要传送的信息,因此信源也就存在进一步压缩其信息率的可能性。•信源冗余度越大,其进一步压缩的潜力越大。这是信源编码与数据压缩的前提与理论基础。•在实际通信系统中，为了提高传输效率，往往需要把信源的大量冗余进行压缩，即所谓信源编码。但是考虑通信中的抗干扰问题，则需要信源具有一定的冗余度。因此在传输之前通常加入某些特殊的冗余度，即所谓信道编码，以达到通信系统中理想的传输有效性和可靠性。28冗余度•例：英文字母：等概率H0=log27=4.76比特/符号不等概率H1=4.03比特/符号考虑相关性H2=3.32比特/符号极限熵H∞=1.4比特/符号•冗余度71.076.4/)4.176.4(英语文章有71%是由语言结构定好的,只有29%是自由选择29习题•2-26•2-30本章小结31信源的描述•一个离散信源发出的各个符号消息的集合为：},,,{21nxxxX)}(,),(),({21nxpxpxpP•它们的概率分别为•p(xi):xi的先验概率•单符号离散信源的数学模型—概率空间)()()(2121nnxpxpxpxxxPX1)(0)(1niiixpxpa,b,c,…z32000111105/45/14/34/13/23/12/12/1)|(432110sssssapaaij•状态转移概率矩阵•符号条件概率矩阵5/45/100004/34/13/23/100002/12/1)|(43214321sssssspssssij(1)1/2(1)3/4(0)1/3(0)1/4(0)1/2(0)1/5(1)2/3(1)4/5s