《信息论》.doc

信息论讲稿第一章 绪论本章主要讲述三个问题：1信息的基本概念2信息论研究的对象、目的和内容3发展简史与现状通过本章的学习，力求使学生对信息论的一些基本情况有所了解。一有关信息的一些基本概念1信息：对事物运动状态（或存在方式）不确定性的描述。通过“911”事件、乒乓球赛事改革等事件的讲解，使学生加深对此概念的理解。2消息：利用能为人的感官所感知的物理现象，将客观事物的运动和主观思维活动的状态表达出来，就成为消息。消息应具备的条件：1) 能为通信的双方所理解。2) 可以传递。如：文字，语声，图像等。由此可见，信息是抽象的，消息是具体的，消息是信息的载体，信息是消息的内涵，信息通过消息表现出来。3信源、信宿、信道（构成通信系统的三大要素）信道信宿1) 信源：产生消息或消息序列的源，信源即发出消息的发送端。2) 信宿：消息传送的对象（人或机器），即接收消息的接收端。3) 信道：连接信源与信宿的通道。4信息量：对信息的定量描述。实例1： 消息：及格不及格 p(x)： 1/2 1/2 两个消息的信息量相等实例2：消息：录取 未录取 面试 p(x)： 1/6 3/6 2/6 第一个消息的信息量最大由此可见，信息量的大小是与事件的不确定性有关的。不确定性越大，信息量也越大。即：信息量f(不确定性)不确定性随机性5概率空间：由样本空间与概率测度给出的空间，记为X,P。Xx1,x2,.xq Pp(x1),p(x2),.p(xq) x1, x2, . xq X,P=p(x1), p(x2),. p(xq)如： 及格不及格录取 未录取 面试1/2 1/2 1/6 3/6 2/66自信息（量）、信源的平均信息量（熵）1) 自信息量：指信源中某一消息所含有的信息量。是对信源微观特性的描述。I(xi)=log1/p(xi)由此可见，输出的消息不同，自信息量也不同，因此该值是一个随机量。2) 信源的平均信息量（信源熵）：指信源每输出一个消息所给出的平均信息量，是对信源宏观特性的描述。H(x)=EI(xi)=p(xi)log1/p(xi)可见，只要给定信源的概率分布，就可求出信源熵，它是一个确知量。7互信息：是指通过间接的手段，所获取的关于信源方面的信息量。互信息已经消除的不确定性 xiyj信道先验的不确定性尚存在的不确定性I(xi;yj)=log1/p(xi)log1/p(xi/yj)log1/p(xi)-消息xi的自信息，记为I(xi)。log1/p(xi/yj)-收到yj后对发送端的符号是否为xi仍存在的不确定性。若：p(xi/yj)1 （理想信道）则：I(xi;yj)=I(xi)即自信息是互信息的特例。若：p(xi/yj)1 （有噪信道）则：I(xi;yj)I(xi) 说明信息通过信道传输后信息量会有所损失，损失的多少与信道特性有关。8信息量定义的优点1) 是一个科学的定义，与实际生活不矛盾。例如：p(xi)1 （必然事件）I(xi)=0 无任何信息量p(xi)0 （小概率事件）I(xi) 爆炸性新闻2) 排除了日常生活中对信息量理解的一些主观因素。9信息量定义的局限性1) 只适用于可用概率空间模型描述的这类信源。2) 与实际情况并不完全一致，未考虑含义、重要程度及后果。二信息论研究的对象、目的和内容1研究对象：广义通信系统（即消息传输系统或信息传输系统）。狭义通信系统电话、电报、卫星通讯等，即电信。广义通信系统所有的信息流通系统。包括狭义的，还有神经系统、生物遗传系统、人类社会的管理系统。通信系统模型：噪声源 信源编码信道译码信宿 2研究目的：总结通信系统共有规律，使设计出来的系统具有更高的可靠性和有效性。3研究的内容：1) 信息论基础（香侬基本理论）a) 信息测度信源统计特性，传统熵b) 信道容量c) 信源、信道编码定理2) 一般信息论（通讯的一般理论）a) 香侬理论b) 信号与噪声理论c) 信号滤波和预测d) 统计检测与估计理论e) 调制和信息理论其中后三项是由接收端恢复有干扰的信息。以美国维纳为代表。3) 广义信息论a) 上述两方面的内容b) 所有有关信息的领域和有关问题，包括心理学、遗传学、神经心理学、语言学和语义学。三发展简史与现状1.发展简史：18201830年：法拉第，电磁感应定律。18321835年：莫尔斯，电报系统。1864年：麦克斯韦，电磁波的存在。1876年：贝尔，电话系统。1888年：赫兹，证明了电磁波的存在。1895年：（英）马可尼、（俄）波波夫，无线电通信。1907年：福雷斯特，电子管。19251927年：电视系统。19301940年：微波电子管及雷达系统，在二战期间发挥了巨大作用。19501960年：量子放大器、激光技术，从而产生光纤通信技术。以上均为技术发明工作。理论创新工作如下：1832年：莫尔斯，电报系统中高效率编码方法研究，对香农编码有启示。1885年：凯尔文，电缆的极限传信率问题。1922年：卡逊，调幅信号的频谱结构，产生频谱概念。1924年：奈奎斯特，信息率与带宽的关系。1928年：哈特莱，H=NlogS, SN：可能的消息数。1936年：阿姆斯特朗，增加带宽可抑制噪声，如：宽频移的调频方法。1939年：达德利，声码器，指出通信所需带宽消息的带宽。1948年：香农，通信的数学理论，奠定了现代信息论的基础。1950年以后：理论完善，范恩斯坦、香农提出信息率失真理论，从而产生频带压缩、数据压缩、纠错编码理论。1960年：卡尔曼滤波理论（递推算法），卫星轨道、导弹制导的测量。2现状 信息论的发展正在以下三个方面展开：1) 香农信息论-信息概念的深化（多址多用户信道、多重相关信源 编码、信息率失真理论）2) 纠错码理论-最优编码3) 维纳信息论-利用光纤通信技术，研究成像雷达和二维图像信息 处理问题。第二章 基本信息论本章主要讲述：信息度量、离散信源的熵、二元联合信源的共熵与条件熵、连续信源的熵、熵速率和信道容量、离散有噪信道的熵速率和信道容量、连续有噪信道的熵速率与信道容量、编码定理等内容。通过本章内容的讲解，力求使学生能够掌握基本信息论的内容。2-1 信息的度量一研究信息度量的必要性误码率、信噪比、传信率（单位时间内信道所传送的信息量）是衡量通信系统的三个关键指标，而这三个指标均与信息量的大小有关。由此可见，研究信息的度量是十分必要的。二信源的不确定性（不肯定性）1研究不肯定性的目的由于信息量的多少与信源的不肯定性有关，因此欲研究信息量就必须先研究信源的不肯定性。2不肯定程度：可以简单地理解为猜测信源输出某个消息的难易程度。例：1. 红 99，白 1，猜颜色？2红 50，白 50，猜颜色？3红 25，白 25，黑 25，黄 25，猜颜色？上述实例可以看成是离散信源，其概率空间分别为： x1 , x2 , , xN X,P(x)= p(x1) , p(x2) , ,p(xN) x1 , x2 1) X,P(x)= 0.99 , 0.01 x1 , x2 2) X,P(x)= 0.5 , 0.5 x1 , x2 , x3 , x43) X,P(x)= 0.25 , 0.25 ,0.25 ，0.25 结论：1) 不肯定程度=fN,p(x), N状态数2) 等概分布时，不肯定程度最大。3) 在等概时，N愈大p(x) 愈小，不肯定程度愈大。 H3(1/4,1/4,1/4,1/4)H2(1/2,1/2)H1(0.99,0.01)3.自信息（量）1) 定义：对于离散信源，其概率空间如下： x1 , x2 , , xN X,P(x)= p(x1) , p(x2) , ,p(xN) 定义自信息量：I(xi)=log1/p(xi)=-logp(xi)2) 含义：描述信源的微观特性，是指消息集中某一消息所含有的信息量。在xi发生前-描述xi发生的不确定性大小。在xi发生后-描述xi所含有的（提供的）信息量。3) 采用对数定义的合理性设：I(xi)=fp(xi), fp(xi)应满足：a) f(pi)应是pi的单调递减函数，即p1p2时，则f(p1)1) 单位2 bite nat10 Hart1 nat=1.44 bit 1 Hart=3.32 bit例：试求例1的I(x1),I(x2) I(x1)=log21/0.99=0.014 bit I(x2)=log21/0.01=6.63 bit5) 等概率分布离散信源的平均信息量 x1 , x2 , , xq X,P(x)= 1/q , 1/q , , 1/q H(X)=1/qlogq =logq三互信息（量）（指收信者获得的信息量）1.定义互信息量不确定性的减小量（已经消除的不确定性）（收到此消息前关于某事件发生的不确定性）-信道（收到此消息后关于某事件发生的不确定性）（发出xi的不确定性）（信道损失的信息量） xi yjI(xi;yj)=I(xi)-I(xi/yj) 2.过程发送端： x1 , x2 , , xn X;P= p1 , p2 , , pn I(xi)=-logpi 接收端：后验概率p(xi/yj): p(x1/yj), p(x2/yj), , p(xn/yj) p(xi/yj)=1对无损信道： p(xi/yji=j) =1 p(xi/yjij)=0I(xi;yj)=I(xi)=-logpi 自信息是互信息的特例。对有损信道：I(xi;yj)=I(xi)-logp(xi/yj) =-logpi+logp(xi/yj) =log后验概率先验概率 2-2 离散信源的熵一离散信源1定义： x1 , x2 , xnX,P= p(x1), p(x2),，p(xn) X: 离散型随机变量。 如：掷硬币，数字通信，英文字母等。2分类：1) 离散平稳信源p(xi)t=t1= p(xi)t=t2 = p(xi) 一维平稳 p(xi,xi+1)t=t1 = p(xi,xi+1)t=t2 = p(xi,xi+1) 二维平稳p(xi,xi+1,xi+N)t=t1 = p(xi,xi+1, xi+N)t=t2= p(xi,xi+1,xi+N) 完全平稳2) 离散无记忆信源和离散有记忆信源离散无记忆信源：p(xixj)=p(xi)p(xj/xi)=p(xi)p(xj)离散有记忆信源：组成信源的各随即变量相互关联时。3) 马尔可夫信源记忆长度有限的有记忆信源，如：一阶马氏源，m阶马氏源。二信源熵1. 定义：H(X)=Elog1/p(xi)=-p(xi)logp(xi)2. 单位：与I(xi)相同。3物理意义：1) 等概率分布情况：一个符号含有的信息量。2) 非等概率分布情况：一个符号所含有的统计平均信息量，是对信源宏 观特性的描述。结论：1) H(X)表征信源的总体特性-提供的统计平均信息量/符号2) 信源输出前的平均不确定性。3) H(X)表征了信源的随机性。例: x1 , x2 X;P= 0.99 , 0.01 H(X)=0.08 bit/符号 y1 , y2 Y;P= 0.5 , 0.5 H(Y)=1 bit/符号可见：H(Y)H(X)注意：I(X,Y)=H(X)- H(X/Y) 4.计算举例：贾书，P25,例1，2三熵的性质1.对称性：H(P1, P2, Pn)=H(P2, P1, Pn)=如: x1, x2, x3 X,P= 1/3, 1/6, 1/2 y1, y2, y3 Y,P= 1/6, 1/2, 1/3z1, z2, z3 Z,P= 1/3, 1/2, 1/6H(X)=H(Y)=H(Z) ，可见，熵与随机变量的取值无关，这一点充分反映了熵是对信源宏观特性的描述。 2非负性（仅适用于离散信源）:H(X)0 3扩展性: lim H(P1, P2,Pi-,Pn,)=H(P1, P2,Pi,Pn) 0 说明小概率消息对信源熵的贡献可以忽略（尽管他的自信息很大）。 4确定性:H(1,0)=H(0,1)=H(1,0,0)=0说明确定事件不含有任何信息量。 5可加性:若X、Y统计独立，则：H(XY)=H(X)+H(Y) p(xixj)=p(xi)p(xj)若X、Y不独立，则：H(XY)=H(X)+H(Y/X) 此公式被称为强可加性。 6极值性： nHn(P1, P2,Pi,Pn)-pilogqi 该公式没有任何物理意义。 i=1若qi1/n （等概分布）则：Hn(P1, P2,Pi,Pn)logn 该公式说明等概分布的信源具有最大熵。 7上凸性：该性质决定了熵具有最大值。 Hax+(1-a)yaH(x)+(1-a)H(y)0a12-3 二元联合信源的共熵与条件熵一二元联合信源的共熵1二元联合信源x1 , x2 ,. xN X,P=p(x1), p(x2),. p(xN)y1 , y2 ,. yM Y,P=p(y1), p(y2),. p(yM) p(xi)=1 p(yj)=1x1y1 ,x1yM,xiy1,xiyM,xNy1 ,xNyMXY,p(xy)= p(x1y1), p(xiyM),p(xNyM) xiyj：为XY的样本值。P(xiyj)= p(xi)p(yj/xi)=p(yj)p(xi/yj)若X、Y相互独立，则：p(yj/xi)=p(yj), p(xi/yj)=p(xi)p(xiyj)= p(xi)p(yj) 2二元联合信源的共熵 N M H(XY)=-p(xiyj)logp(xiyj) i=1 j=1二二元联合信源的条件熵-兼证熵函数的可加性1.条件熵H(XY)=-p(xiyj)logp(xiyj) =-p(xiyj)logp(xi)p(yj/xi) =-p(xiyj)logp(xi)-p(xiyj)logp(yj/xi) =-p(xi)logp(xi)-p(xi)p(yj/xi)logp(yj/xi) =H(X)-p(xi)p(yj/xi)logp(yj/xi) =H(X)+H(Y/X) （强可加性）同理：H(XY)=H(Y)+H(X/Y)H(Y/X)、H(X/Y)-条件熵H(Y/X)=-p(xi)p(yj/xi)logp(yj/xi) =-p(xiyj)logp(yj/xi)H(X/Y)=-p(yi)p(xj/yi)logp(xj/yi) =-p(xiyj)logp(xj/yi)2条件熵H(Y/X)的物理意义H(Y/X)：在给定X的情况下，信源Y的统计平均信息量。是对信道特性的描述。H(Y/X)：在给定Y的情况下，信源X的统计平均信息量。是对信道特性的描述。H(Y/X)-散布度H(X/Y)-疑惑度或可疑度3当X、Y相互独立时即p(yj/xi)=p(yj)信道 H(XY)=H(X)-p(xi)p(yj)logp(yj) =H(X)+H(Y) X Y三H(XY)H(X)+H(Y)的证明1证明：H(XY)=H(X)+H(Y/X)只需证明：H(Y/X)H(Y)H(Y/X)=-p(xi)p(yj/xi)logp(yj/xi)现令 qj=p(xi)p(yj/xi)=p(yj)根据熵的极值性应有：H(Y/X)-p(xi)p(yj/xi)logqj =-qjlogqj =H(Y) H(XY)H(X)+H(Y)独立时: H(XY)=H(X)+H(Y)2结论：1) 相关两信源的共熵小于单独熵之和，不相关时，二者相等，相关性使熵减小。2) 条件熵必不大于无条件熵。3) 多元信源的共熵具有同样的结论。 H(XYZ)H(X)+H(Y)+H(Z) 此式说明有相关性时信源的熵将减小。3N次扩展信源及其熵的概念 a1 , a2 ,. aq X,P(x)=p(a1), p(a2),. p(aq)N次扩展信源定义为：x1 , x2 , . xqN XN,P(xN)=p(x1), p(x2),. p(xqN)xi:对应N个ai组成的序列，共有qN项。对无记忆信源： P(xi)=P(ai)=组成xi的N个ai的P(ai)的乘积。 H(XN)=NH(X)例:1. 贾书 p35 例1 2贾书 p38 例2 3付书 p22 例2 设离散无记忆信源: a1 , a2 , a3 X,P(x)=1/2, 1/4, 1/4 试求扩展信源X2的H(X2)。解：P(xi)=Pi1Pi2 (i=1,2,3)X2 X2的样本值X1(a1a1)X2(a1a2)X3(a1a3)X4(a2a1)X5(a2a2)X6(a2a3)X7(a3a1)X8(a3a2)X8(a3a3)概率P(Xi)1/4 1/8 1/8 1/8 1/16 1/16 1/8 1/16 1/16H(X)=1.5 bit/符号H(X2)=3 bit/符号 指每个ai =2H(X) 指每个xi (即两个ai)4平均互信息互信息： I(xi;yj)=I(xi)-I(xi/yj) 是一个随机变量平均互信息：I(X;Y)=EI(xi;yj) =EI(xi)-EI(xi/yj) =H(X)-H(X/Y)0同理: I(Y;X)=H(Y)-H(Y/X)0H(X) - X的熵。H(X/Y)-条件熵，已知Y时关于X的不定度（熵）。I(X;Y)-Y已知后，所获得的关于X的平均信息量。结论：1) I(X;Y)的取值范围：I(X;Y)=0-H(X)2) 经过处理后会损失互信息（周书p201）I(X;Y)I(X;DY) 此问题可通过磁带翻录讲清楚。H(X/Y)H(X/DY) YDY:对Y进行分组处理。3) 重复处理可增加互信息I(X;Y1)I(X;Y1Y2)I(X;Y1Y2Yn)H(X/Y1)H(X/Y1Y2)H(X/Y1Y2Yn)n时， H(X/Y1Y2Yn)0 此问题可通过警察破案过程讲清楚。即：I(X;Y1Y2Yn)H(X) 多次测量可以得到H(X)。5几种信息量之间的关系（孟书P12-P13）1) 一般关系： H(XY)=H(X)+H(Y)-I(X;Y) I(X;Y)=I(Y;X)=H(X)-H(X/Y)=H(Y)-H(Y/X)2) 相互独立时： H(XY)=H(X)+H(Y) I(X;Y)=I(Y;X)=0H(X/Y)=H(X)H(Y/X)=H(Y)3) 一一对应时： H(XY)=H(X)+H(Y/X)=H(X)=H(Y) I(X;Y)=I(Y;X)=H(X)=H(Y) H(X/Y)=H(Y/X)=06. 散布度与可疑度-加深对互信息的理解 X Y X Y信道 1/4 x1-y1 1/4 x2-y21/4 x3-y3 1/4 x4-y4 P(y1)=1/4*1/2+1/4*1/3=5/24 P(y2)=1/4*2/3 =4/24 P(y3)=1/4*1+1/4*1/2 =9/24 P(y4)=1/4*1 =6/24显然：H(X)H(Y)， H(Y)H(X)x1y1 x1的散布用P(y1/x1), P(y2/x1)表示。 y2 若无散布，P(yj/xi)=1, H(Y/X)=0, H(X)=H(Y),信息无损失。 有散布，H(Y/X)0,则 I(Y;X)=H(Y)-H(Y/X) H(Y/X)-信道造成的信息损失，以散布度形式出现。同理：I(X;Y)=H(X)-H(X/Y) H(X/Y)-信道造成的信息损失，以疑惑度形式出现。 四消息的剩余度1剩余:由于不等概或相关性使信源熵值减小，欲输出相同信息量，必须增加位数，此为剩余。 例1信源输出四个符号A、B、C、D，各符号独立且等概分布，求输出10个符号序列所含有的最大信息量。解： A, B, C, D X,P(x)=1/4, 1/4, 1/4, 1/4 Hmax(X)=-1/4log1/4=2 bit/符号 10个符号的总信息量：Imax=10*2=20 bit 例2信源同上，概率分布非均匀。 A, B, C, D X,P(x)=4/5, 1/10, 1/10, 1/20 求H(X)，欲获得20 bit信息量，需要接收多少个符号？ 解：H(X)=-p(xi)logp(xi)=1 bit/符号n=20/1=20个符号2剩余度的定义1) 熵的相对率（相对熵）=H(X)/Hmax(X)H(X)：信源输出的实际熵Hmax(X)：最大可能的熵可见，越大，信源的剩余越小，即每个消息的“含金量”越高。2) 剩余度E=1-H(X)/Hmax(X)=1-E-熵的剩余度可见，E越小，信源的剩余越小，即每个消息的“含金量”越高。3) 内熵内熵=Hmax(X)-H(X)可见，内熵越小，信源的剩余越小，即每个消息的“含金量”越高。例1 试求上例中的、E、内熵?解： =H(X)/Hmax(X)=1/2=50%E=1-=50%内熵=1 bit/符号例2贾书P42,例2，英文字母信源的剩余度。4) 剩余度与效率（有效性）及抗干扰性（可靠性）的关系存在剩余意味着具有提高效率的前途，但并未指明具体方法。如电报：“母病愈，身体健康” “母病愈”“母病X” “中华人民共和国”“中国”“X国” 以上两例抗干扰能力差。再如：“母病X，身X健康” “中X人X共X国” 抗干扰能力强。可见，有效性（E）信源编码抗干扰能力剩余度信道编码 通信系统先是对信源进行有效性编码，以去除剩余。然后再进行信道编码，以便按一定规律增加剩余，提高系统的可靠性。2-4 连续信源的熵 一连续信源熵的定义 1连续信源 信源X的输出值是连续型随机变量。 2连续信源的熵 dv:量化分辨率。 H绝=lim-p(vi)dvlogp(vi)dv =lim-p(vi)logp(vi)dv-p(vi)dvlogdv dv0 =-p(vi)logp(vi)dv-limp(vi)dvlogdv p(vi)dv1 limlogdv- 后一项 定义：H(X)=-p(x)logp(x)dx-连续信源相对熵3.连续信源熵的特点1) 连续信源的熵是一个相对量，是比无穷大大多少的一个相对量，此定义仅对研究熵的差值问题时才有意义（如信道容量，传信率等）。2) 可加性、极值性仍成立，但非负性已不存在了。 例：求在a,b区间呈均匀分布的连续信源的熵。 解： 1/(b-a) axb p(x)= 0 其他 H(X)=1/(b-a)log(b-a)dx=log(b-a) 若：(b-a)1，则：H(X)0 可见，连续信源的熵值已不能代表信源输出的平均信息量，连续信源输出的平均信息量应为无穷大。二连续信源的最大熵 1两个特例熵的计算1) p(x)为均匀分布一维情况：H(X)=log(b-a)N维情况:设：X=(x1,x2,xN)在(a1,b1)x(a2,b2)x(aN,bN)区域均匀分布，即： 1/(br-ar) x(br-ar) p(x)= 0 其他 H(X)=-1/(br-ar)log1/(br-ar)dx1dx2dxN =log(br-ar)=log(br-ar)H(X)是N维体积的对数值，与各变量的数学期望及均方差值无关。2) p(x)为正态分布p(x)=1/(22)1/2e-(x-m)2/22H(X)=-p(x)logp(x)dx =-p(x)log1/(22)1/2e-(x-m)2/22dx =-log1/(22)1/2p(x)dx-p(x)loge-(x-m)2/22dx =log(22)1/2+loge/22(x-m)2p(x)dx =log(22)1/2+loge/22*2=log(2e2)1/2H(X)只与2有关，若m=0, 2平均功率。 2最大熵定理1) 输出范围受限的信源-限峰值功率最大熵定理定理内容：对于定义域有限的随机变量X,当其均匀分布时具有最大熵。证明： 设x(a,b), 1/(b-a) axb q(x)= 0 其他 对任意的p(x),在p(x)dx=1的条件下有： H(X)=-p(x)lnp(x)dx =p(x)ln1/p(x)q(x)/q(x)dx =p(x)lnq(x)/p