信息论与编码

1、122.1 2.1 信源的描述和分类信源的描述和分类2.2 2.2 离散信源熵和互信息离散信源熵和互信息2.3 2.3 离散序列信源的熵离散序列信源的熵2.4 2.4 连续信源的熵和互信息连续信源的熵和互信息2.5 2.5 冗余度冗余度3 设有两个随机事件X和Y ,X取值于信源发出的离散消息集合, Y取值于信宿收到的离散符号集合有扰信道干扰源信源X信宿Y)()()(2121nnxpxpxpxxxPX)()()(2121nnypypypyyyPY4 如果信道是无噪的,当信源发出消息xi后,信宿获得的信息量就是xi的不确定度I(xi),即xi本身含有的全部信息。 一般而言,信道中总是存在着噪声和干

2、扰,信源发出消息xi,通过信道后信宿只可能收到由于干扰作用引起的某种变型yj 。 信宿收到yj 后推测信源发出xi的概率p(xi|yj)称为xi的后验概率。 信源发出消息xi的概率p(xi) 称为xi的先验概率。有扰信道干扰源信源X信宿Y)()|(log)|()();(2ijijiijixpyxpyxIxIyxI5 互信息：一个事件yj所给出来的关于另一个事件xi的信息表示接收到某消息yj后获得的关于事件xi的信息量定义为 xi的后验概率与先验概率比值的对数 6注：I(xi ;yj ) 和I(xi,yj )的区别：前者是事件xiX和事件yjY之间的互信息量，后者是二维空间XY 上元素（xi y

3、j）的自信息量。)()|(log);(2ijijixpyxpyxI( ,)log( ,)ijijI x yp x y 7 例某地二月份天气 构成的信源为：8/ 18/ 14/ 12/ 1)(雪雨阴晴xpXbitxIxIbitxIbitxI3)()(,2)(,121log)(43221 收到信息y1 ：今天不是晴天 求在该过程中传递的所有的互信息解：先求后验概率 求得自信息量分别为 p(x1|y1) = 0, p(x2|y1) = 1/2 , p(x3|y1) = 1/4 , p(x4|y1) = 1/4 8bitxpyxpyxI14/12/1log)()|(log);(2212212 表明从y

4、1分别得到了x2 x3 x4各 1比特的信息量。 消息y1使x2 x3 x4的不确定度各减少1bit 。bityxIyxI18/14/1log);();(214130)()|(log);(111211xpyxpyxI9 1、互易性：、互易性：yj提供的有关于提供的有关于xi的信息，等于的信息，等于xi提提供的有关供的有关yj的信息。因此，取名为的信息。因此，取名为“互信息互信息”。 2、独立变量的互信息量为、独立变量的互信息量为0. （事件之间之所以（事件之间之所以存在互信息，是由于事件之间的统计相关。）存在互信息，是由于事件之间的统计相关。）( ;)(;)ijjiI x yI yx( ; )

5、( ; ) 0ijjiI x yI y x10 3、互信息量可正可负、互信息量可正可负 如：如：p20 例例2-8 ( I(x=0;y=0), I(x=0;y=?) 4、平均意义上的互信息一定大于或者等于、平均意义上的互信息一定大于或者等于0. 5、两个事件的互信息量不大于单个事件的自信息量，即有：( )( |):iijjiI xI x yyx的出现有助于减少 的不确定性；( )( |):iijjI xI x yy。i的出现增大了x的不确定性( ;)( )( ;)()ijiijjI x yI xI x yI y11 平均互信息定义 互信息= 先验不确定性后验不确定性 = 不确定性减少的量)|(

6、)();(YXHXHYXI Y未知,X 的不确定度为H(X) Y已知,X 的不确定度变为H(X |Y)有扰信道干扰源信源X信宿Y12( ;)ijI x yii(| )( ;)( |) ( ;)( |)log( )jijijijijip y xI X yp x y I x yp x yp y(;)jI X yii(|)( ; )() ( ;)() (|)log( )(|)( ,)log( )jijjjijjjijiijjip yxI X Yp y I X yp yp xyp yp yxp x yp y 另一种定义方法： )()|(log);(2ijijixpyxpyxI13(; )()(|)(|

7、)(; )()log( )ijijijiI X YH XH X Yp xyI X Yp x yp x I(X;Y)等于互信息量I(xi;yj)的概率加权平均值 平均互信息量=平均不确定性消除的程度 收到集合Y后获得的关于集合X的平均信息量14(; )( ;)I X YI Y X(; )0I X Y (; )()( ;)( )I X YH XI Y XH Yi.对称性：ii.非负性：iii.极值性：( ; )( ; )I X YI Y X( ; ) 0I X Y (; )()()( ;)( )( )I X YH XI XI Y XH YI Yiv.凸函数性 （1）平均互信息量I(X;Y)是输入信

8、源概率分布 p(xi)的上凸函数，这一点研究信道容量的理论基础。 （2）平均互信息量I(X;Y)是条件转移概率(或称信道转移概率) p(yj|xi)的下凸函数，这一点是研究信源的信息率失真函数的理论基础。 通信系统中,若发端的符号为X ,收端的符号为Y 如果是一一对应信道,接收到Y后,对X的不确定性将完全消除,H(X|Y) = 0, I(X;Y)=H(X). 信道上干扰很大或者X、Y相互独立，I(X;Y)=0 一般情况： H(X |Y) H(X),即了解Y后对X的不确定度的将减少 通过信道传输消除了一些不确定性,获得了一定的信息。)();(0XHYXI(; )0I X Y 1516定理定理1

9、图 函数的均值均值的函数q1 q1+(1-) q2 q2 q(x)I (q1)+(1-) I (q2)Iq(x)I q1+(1-) q2 17定理定理2 当信源给定，即信源分布概率当信源给定，即信源分布概率q( (x) )固定，平均互信固定，平均互信息量息量I( (X ; Y) )是信道转移概率是信道转移概率p( (yx) )的的型凸函数。型凸函数。图 函数的均值均值的函数)(xypI)(xyp p1 p1+(1-) p2 p2 I p1+(1-) p2 I (p1)+(1-) I (p2) 18例例 二元等概信源 ，通过信道转移概率为 的信道传输，信宿接收符号Y = y0, y1，计算信源与

10、信宿间的平均互信息量I（X；Y）。2121)(10 xxXqX010151661122yyxxP P （1） 先根据 计算出iiijjxqxypy)()()(32216521)()()()()(1100000 xqxypxqxypy31216121)()()()()(1110011xqxypxqxypy （2） 由 计算后验概率)()()()(jiijjiyxqxypyx85322165)()()()(000000yxqxypyx1983322121)()()()(011001yxqxypyx41312161)()()()(100110yxqxypyx43312121)()()()(11111

11、1yxqxypyx322. 045log2185log)()(log);(00000 xqyxyxI121log2141log)()(log);(01010 xqyxyxI415. 043log2183log)()(log);(10101xqyxyxI585. 023log2143log)()(log);(11111xqyxyxI （3）计算各消息之间的互信息量I(xi ;yj ) （比特） （比特） （比特） （比特） 20);()();(jiijjiyxIyxpYXI);()()(jiiijjiyxIxypxq093. 0585. 021)415. 0(21) 1(61322. 06521

12、21 在有在有3个变量个变量的情况下的情况下,符号符号xi、yj 、 zk之间的之间的互互信息量信息量。 1、符号、符号xi与符号对与符号对(yj , zk)之间的互信息量为之间的互信息量为 (|)( ;)log( )ijkijkip xy zI x y zp x2、在已知事件zk的条件下,接收到yj后获得关于某事件xi的条件互信息为( ;|)ijkI x yz(|)log(|)ijkikp xy zp xz22 在有3个变量的情况下,符号xi与符号yj , zk之间互信息量的关系 )|;();()|;();();(kjikijkijikjizyxIzxIyzxIyxIzyxI说明：一个联合事

13、件(yj zk)出现后所提供的有关xi的信息量I(xi;yj,zk)等于zk事件出现后提供的有关xi的信息量I(xi;zk),加上在给定zk条件下再出现yj事件后所提供的有关xi的信息量 I(xi;yj|zk)。 231( ;) ( ;)( ;)2( ;|)( ;|)ijkijikikjijkI x y zI x yI x zI x zyI x yz ( ;)(;)(;)(;|)ijkjkijikijI x y zI y zxI yxI zxy( ;)( ;)ijkikjI x y zI x z y(1)(2)(3)24 三维联合集XYZ上的平均互信息量 )|;();()|;();();()|

14、;()|;();();()|;();();();()|;();();()|;(),();(YZXIZYIXZYIZXIZXYIZYXIYZXIYXIZXIZYXIZXIZYXIYZXIYXZIXYIXYZIYZXIYXIYZXI25在N维U1 U2 UN联合空间,有： 12312132121121( ;)( ;)( ;)( ;)( ;)NiiNNI u u uuI u uI u u uI u u uuI u uuu 26)()()()|()()|()();(XYHYHXHXYHYHYXHXHYXI 熵只是平均不确定性的描述; 不确定性的消除(两熵之差)才等于接收端所获得的信息量。 获得的信息量

15、不应该和不确定性混为一谈 )()()()|()()|()()(YHXHXYHYXHYHXYHXHXYH27H(X|Y)H(X)H(Y)H(XY)H(Y|X)I(X;Y)()()()|()()|()();(XYHYHXHXYHYHYXHXHYXI)|()()|()()()()()|()()|()()(XYHYHYXHXHYHXHXYHYXHYHXYHXHXYH28 H(X|Y)：信道疑义度，损失熵 信源符号通过有噪信道传输后所引起的信息量的损失。 信源X的熵等于接收到的信息量加上损失掉的信息量。 H(Y|X)：噪声熵，散布熵 它反映了信道中噪声源的不确定性。 输出端信源Y 的熵H(Y)等于接收到

16、关于X的信息量I(X;Y)加上H(Y|X),这完全是由于信道中噪声引起的。( ; )( )(| )( )( |)I X YH XH X YH YH Y X (1) (2)29I(X;Y) H(X) H(Y) H(X/Y)噪声熵噪声熵 H(Y/X)噪声熵噪声熵30 若信道是无噪一一对应信道,信道传递概率： )(1)(0)|(xfyxfyxyp)(1)(0)|(xfyxfyyxp计算得:0)|(; 0)|(XYHYXH)()();(YHXHYXI)()();(YHXHYXI31 若信道输入端X与输出端Y完全统计独立 )()|()()|(xpyxpypxyp则:)()|();()|(YHXYHXHY

17、XH0);(YXI)|()(YXHXH)|()(XYHYH32【例例】已知信源消息集为已知信源消息集为X= 0,1,接收符号集为接收符号集为Y= 0,1 ，通过有，通过有扰信道传输，其传输特性如图所示，这是一个二进制对称信道扰信道传输，其传输特性如图所示，这是一个二进制对称信道BSCBSC。已知先验概率已知先验概率 , , 计算平均互信息量计算平均互信息量I( (X;Y) ) 。 0 1- 0 1 1- 1 图 二进制对称信道记记 q( (x) )为信源输入概率；为信源输入概率；q(0)=q(1)=0.5 ( (y) )为信宿输出概率；为信宿输出概率； p(yx)为信道转移概率；为信道转移概率

18、； (xy)为后验概率。为后验概率。33第一级处理器第二级处理器XYZ输入 级联处理器 数据处理定理 : 当消息通过多级处理器时,随着处理器数目增多,输入消息与输出消息间的平均互信息量趋于变小 假设Y条件下X和Z相互独立 );();();();(ZYIZXIYXIZXI34 数据处理定理说明： 当对信号、数据或消息进行多级处理时,每处理一次,就有可能损失一部分信息,也就是说数据处理会把信号、数据或消息变成更有用的形式，但是绝不会创造出新的信息,这就是所谓的信息不增原理。 351.非负性 H(X)H(p1，p2，pn)0 式中等号只有在pi =1时成立。2.对称性 H(p1，p2，pn) = H(p2，p1，pn) 例如下列信源的熵都是相等的：6 / 12 / 13 / 1321xxxPX2/ 16/ 13/ 1321yyyPY6 / 13 / 12 / 1321zzzPZ363.确定性 H(10)H(100)=H(100)=0 只要信源符号中有一个符号出现概