《信息论与编码(第二版)》第2章-4

1、22.1 2.1 信源的描述和分类信源的描述和分类2.2 2.2 离散信源熵和互信息离散信源熵和互信息2.3 2.3 离散序列信源的熵离散序列信源的熵2.4 2.4 连续信源的熵和互信息连续信源的熵和互信息2.5 2.5 冗余度冗余度34第一级处理器第二级处理器XYZ输入 级联处理器 数据处理定理 : 当消息通过多级处理器时,随着处理器数目增多,输入消息与输出消息间的平均互信息量趋于变小 假设Y条件下X和Z相互独立 );();();();(YXIZXIZYIZXI5 数据处理定理说明： 当对信号、数据或消息进行多级处理时,每处理一次,就有可能损失一部分信息,也就是说数据处理会把信号、数据或消息

2、变成更有用的形式，但是绝不会创造出新的信息,这就是所谓的信息不增原理。 6 三维联合集XYZ上的平均互信息量 )|;();()|;();();()|;()|;();();()|;();();();()|;();();()|;(),();(YZXIZYIXZYIZXIZXYIZYXIYZXIYXIZXIZYXIZXIZYXIYZXIYXZIXYIXYZIYZXIYXIYZXI71.非负性 H(X)H(p1，p2，pn)0 式中等号只有在pi =1时成立。2.对称性 H(p1，p2，pn) = H(p2，p1，pn) 例如下列信源的熵都是相等的：6 / 12 / 13 / 1321xxxPX2/

3、16/ 13/ 1321yyyPY6 / 13 / 12 / 1321zzzPZ83.确定性 H(X)H(p1，p2，pn)0 只要信源符号中有一个符号出现概率为1,信源熵就等于零。4.极值性(香农辅助定理) 对任意两个消息数相同的信源 niyqYxpX, 2 , 1,)()(iniiniiinqppppppHloglog),(112195.最大熵定理 离散无记忆信源输出M个不同的信息符号,当且仅当各个符号出现概率相等时即( pi1/M)熵最大。MMMHXH2log1,1)()()()()()|()()|(YHXHXYHYHXYHXHYXH6.条件熵小于无条件熵 1011离散信源离散无记忆信源

4、离散有记忆信源发出单个符号的无记忆信源发出符号序列的无记忆信源发出符号序列的有记忆信源发出符号序列的马尔可夫信源 发出单个符号的信源 指信源每次只发出一个符号代表一个消息； 发出符号序列的信源 指信源每次发出一组含二个以上符号的符号序列代表一个消息。12 发出符号序列的信源6/ 16/ 16/ 16/ 16/ 16/ 1101100011010001000PX6/ 16/ 16/ 16/ 16/ 16/ 1654321PX 发出单个符号的信源13 随机序列的概率为 )|()|()|()()|()|()|()(),()(1211312112121312121Liiiiiiiiiiiiiiiiii

5、iixxpxxpxxpxpxxxxpxxxpxxpxpxxxppLLLLX 设信源输出的随机序列为 X =(X1X2XlXL) 序列中的变量Xlx1,x2, xn X称为离散无记忆信源X的L次扩展信源 14LliiiiiiiilLLxpxpxpxpxpxxxpp1)()()()()(),()(32121X 当信源无记忆时 信源的序列熵 LlliLliiniiiXHxpxpxpxpHllL)()(log)()(log)()(1X15 若又满足平稳特性,即与序号l无关时：)()(XLHHXLLlipxppl1)()(X 信源的序列熵 平均每个符号(消息)熵为 )()(1)(XHHLHLXX16例例

6、:有一个无记忆信源随机变量X(0,1),等概率分布,若以单个符号出现为一事件,则此时的信源熵:符号/12log)(2bitXH序列/24log)X(2bitH符号/1)(21)(2bitHHXX 即用 1比特就可表示该事件。 如果以两个符号出现(L=2的序列)为一事件，则随机序列X(00,01,10,11)，信源的序列熵 即用2比特才能表示该事件。 信源的符号熵17 例:有一离散平稳无记忆信源 414121)(321xxxxpX求：二次扩展信源的熵X2信源的元素 a1 a2a3a4a5a6a7a8a9对应的消息序列 x1x1x1x2x1x3x2x1x2x2x2x3x3x1x3 x2x3 x3概

7、率p(ai) 1/4 1/81/81/81/16 1/161/81/16 1/1618序列/3)(log)()()(91bitapapXHHiiiL符号/5 . 1)(log)()(31bitxpxpXHiii序列/35 . 12)(2)(bitXHH 平均每个符号(消息)熵为 信源的序列熵19 对于有记忆信源,就不像无记忆信源那样简单,它必须引入条件熵的概念,而且只能在某些特殊情况下才能得到一些有价值的结论。 对于由两个符号组成的联合信源,有下列结论:)|()(),|()()|()()|()()(12221121212121XXHXHXXHXHXXHXHXXHXHXXH)()|(),()|(

8、)()()(2121212121XHXXHXHXXHXHXHXXH 当前后符号无依存关系时,有下列推论：20 若信源输出一个L长序列,则信源的序列熵为)()|()|()|()()()(11112121LLlllLLLXHXXHXXXHXXHXHXXXHHX 平均每个符号的熵为： )(1)(LLXHLHX 若当信源退化为无记忆时:)()(XLHHXLllXHH)()(X若进一步又满足平稳性时 21a0a1a2a09/112/110a11/83/41/8a202/97/9 例例已知离散有记忆信源中各符号的概率空间为:41943611210aaaPX 设发出的符号只与前一个符号有关,这两个符号的概率

9、关联性用条件概率p(aj|ai)表示,如表p(aj|ai) 求离散信源的序列熵和平均每个符号的熵? 22 由 p(ai,aj) = p(ai) p(aj| ai) 计算得联合概率p(ai aj)如表a0a1a2a01/41/180a11/181/31/18a201/187/3631)()(jijiapaap 当信源符号之间无依赖性时,信源X的信息熵为符号/543. 1)(log)()(20bitapapXHiii 当考虑符号之间有依赖性时,计算得条件熵符号/872. 0)|(log)()|(202012bitaapaapXXHiijjij H(X2| X1)H(X)信源的条件熵比无依赖时的熵H

10、(X)减少了0.671比特,这正是因为符号之间有依赖性所造成的结果。23 联合熵H(X1,X2)表示平均每二个信源符号所携带的信息量。 我们用1/2H(X1,X2)作为二维平稳信源X的信息熵的近似值。那么平均每一个信源符号携带的信息量近似为: 符号/41. 2),(log),(),(202021bitaapaapXXHijijij符号之间存在关联性 发二重符号序列的熵 符号/21. 1)(21)(22bitXHHX)()(12XXHH比较24 对于离散平稳信源,有下列结论： 条件熵H (XL|XL-1) 随L的增加是非递增的 条件较多的熵必小于或等于条件较少的熵，而条件熵必小于或等于无条件熵。

11、)()|()|()|()|()|()|(11231222121112121XHXXHXXXHXXXHXXXHXXXHXXXXHLLLLLLLLLL25 HL(X)是L的单调非增函数 HL(X)HL-1(X)|(lim)(lim)(121LLLLLXXXXHXHXH H称为平稳信源的极限熵或极限信息量 H0(X)H1(X)H2(X)H(X) L给定时,平均符号熵条件熵： H L(X)H (XL|XL-1)26 马尔可夫信源)()|()|(lim)(lim)(1211121XHXXXXHXXXXHXHXHmmmLLLLL),|(),|(111mLLLLLxxxpxxxp 齐次、遍历的马尔可夫信源的

12、熵iiimsXHspH)|()(1jijijisxpsxpsXH)|(log)|()|(27s2s31/0.61/0.20/0.5s11/0.51/0.10/0.98 . 02 . 005 . 005 . 09 . 001 . 0)|(ijssp59/45,59/9,59/518 . 05 . 09 . 02 . 05 . 01 . 0321321332123121WWWWWWWWWWWWWWWpijjiiWW例三状态马尔可夫信源0/0.828符号符号符号/722. 0) 8 . 0 , 2 . 0(8 . 0log8 . 02 . 0log2 . 0)|(/1) 5 . 0 , 5 . 0(

13、5 . 0log5 . 05 . 0log5 . 0)|(/469. 0) 9 . 0 , 1 . 0(9 . 0log9 . 01 . 0log1 . 0)|(321bitHsXHbitHsXHbitHsXH符号/743. 0722. 059451599469. 0595)|()(1bitsXHspHiiim2930 冗余度(多余度、剩余度) 表示信源在实际发出消息时所包含的多余信息。 冗余度： 信源符号间的相关性。 相关程度越大,信源的实际熵越小 信源符号分布的不均匀性。 等概率分布时信源熵最大。)()()()(log2102XHXHXHXHn31 对于有记忆信源,极限熵为H(X)。 这就

14、是说我们需要传送这一信源的信息,理论上只需要传送H(X)即可。但必须掌握信源全部概率统计特性,这显然是不现实的。 实际上,只能算出Hm(X)。那么与理论极限值相比,就要多传送Hm(X)H(X)。 为了定量地描述信源的有效性,定义:)()(XHXHm)()(11XHXHm信息效率冗余度32 由于信源存在冗余度,即存在一些不必要传送的信息,因此信源也就存在进一步压缩其信息率的可能性。 信源冗余度越大,其进一步压缩的潜力越大。这是信源编码与数据压缩的前提与理论基础。 例：英文字母： 等概率 H0 = log27 = 4.76比特/符号 不等概率 H1 = 4.03比特/符号 考虑相关性 H2 = 3

15、.32比特/符号 极限熵 H =1.4比特/符号 冗余度71.076.4/)4.176.4(英语文章有71%是由语言结构定好的,只有29%是自由选择33 2-13 2-16 2-26 2-3035 一个离散信源发出的各个符号消息的集合为：,21nxxxX)(,),(),(21nxpxpxpP 它们的概率分别为 p(xi): xi的先验概率先验概率 单符号离散信源的数学模型概率空间)()()(2121nnxpxpxpxxxPX1)(0)(1niiixpxpa,b,c,z36000111105/45/14/34/13/23/12/12/1)|(432110sssssapaaij 状态转移概率矩阵

16、符号条件概率矩阵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/5s2s1s4s337 稳态分布概率154325131432121214321442342231131WWWWWWWWWWWWWWWWpijjiiWW74,356,356,3534321WWWW 稳态后的符号概率分布35267454356433563235321)()|()(3597451356413563135321)()|()(2211iiiiiispsapapspsap

17、ap38 问题：问题： 什么叫不确定度？ 什么叫自信息量？ 什么叫平均不确定度？ 什么叫信源熵？ 什么叫平均自信息量？ 什么叫条件熵？ 什么叫联合熵？ 联合熵、条件熵和熵的关系是什么？39 问题：问题： 什么叫后验概率？ 什么叫互信息量？ 什么叫平均互信息量？ 什么叫疑义度？ 什么叫噪声熵（或散布度）？ 数据处理定理是如何描述的？ 熵的性质有哪些？40 设离散信源X，其概率空间为)(log)(iixpxI)()()(2121nnxpxpxpxxxPX I (xi) 含义: 当事件xi发生以前,表示事件xi 发生的不确定性 当事件xi发生以后,表示事件xi所含有的信息量41 自信息量)(log)

18、(iixpxI 条件自信息量 联合自信息量)|(log)|(jijiyxpyxI)(log)(jijiyxpyxI42 离散信源熵H(X)iiiiiixpxpxIxpXH)(log)()()()( 信源熵具有以下三种物理含意： 信息熵H(X)表示信源输出后,每个离散消息所提供的平均信息量。 信息熵H(X)表示信源输出前,信源的平均不确定性。 信息熵H(X)反映了变量X的随机性 。43 无条件熵无条件熵)|(log)|()|(jiijijyxpyxpyXH)|(log),()|(jiijjiyxpyxpYXH),(log),(),(jiijjiyxpyxpYXH 条件熵条件熵 联合熵联合熵iii

19、xpxpXH)(log)()(44 互信息 定义为 xi的后验概率与先验概率比值的对数)()|(log);(2ijijixpyxpyxI 互信息I(xi;yj)表示接收到某消息yj后获得的关于事件xi的信息量。45 平均互信息定义 信息= 先验不确定性后验不确定性 = 不确定性减少的量)|()();(YXHXHYXI Y未知,X 的不确定度为H(X) Y已知,X 的不确定度变为H(X |Y)ijijijixpyxpyxpYXI)()|(log)();(46H(X|Y)H(X)H(Y)H(XY)H(Y|X)I(X;Y)()()()|()()|()();(XYHYHXHXYHYHYXHXHYXI)

20、|()()|()()()()()|()()|()()(XYHYHYXHXHYHXHXYHYXHYHXYHXHXYH47I(X;Y) H(X) H(Y) H(X/Y)疑义度疑义度 H(Y/X)噪声熵噪声熵48 齐次、遍历的马尔可夫信源的熵iiimsXHspH)|()(1jijijisxpsxpsXH)|(log)|()|(49 无条件概率、条件概率、联合概率的性质和关系1)()/()/()()(0jijiijjiyxpyxpxypypxp， mjnijimjijnijimjjniiyxpxypyxpypxp1111111)(, 1)/(, 1)/(, 1)(, 1)()()(),()(11imj

21、jijnijixpyxpypyxp50 无条件概率、条件概率、联合概率的性质和关系)/()()/()()(jijijijiyxpypxypxpyxp，相互独立时，与当)()/()()/()()()(ijijijjijixpyxpypxypypxpyxpYXmjjijiijnijijijiyxpyxpxypyxpyxpyxp11)()()/()()()/(，51 例 一个二元二阶马尔可夫信源,其信源符号集为0,1信源开始时：p(0) = p(1) = 0.5发出随机变量X1。 下一单位时间：输出随机变量X2与X1有依赖关系x2x10100.30.410.70.6p(x2|x1)再下一单位时间：输出随机变量X3与X2X1有依赖关系x3x1 x200011010.40.6p(x3|x1x2)52 从第四单位时间开始，随机变量Xi只与前面二个单位时间的随机变量Xi-2Xi-1有依赖关系: p(xi| xi-1 xi-2x2 x1) = p(xi| xi-1 xi-2) (i3) 且 p(xi| xi-1 xi-2) = p(x3| x2x1) (i3) 解: 设信源开始处于s0状态,并以等概率发出符号0和1,分别到达状态s1和s2 : 若处于s1 ,以0.3和0.7的概率发出0和1到达s3和