信息论基础— 绪论ch01.article

信息论基础1~81 绪论与概览2 熵相对熵与互信息2.1 熵H(X)=−∑x∈X p(x)logp(x)H(X)=−∑x∈Xp(x)log⁡p(x)2.2 联合熵H(X,Y)=−∑x∈X∑y∈Y p(x,y)logp(x,y)H(X,Y)=−∑x∈X∑y∈Yp(x,y)log⁡p(x,y)H(Y|X)=∑x∈X p(x)H(Y|X=x)H(Y|X)=∑x∈Xp(x)H(Y|X=x)定理2.2.1(链式法则): H(X,Y)=H(X)+H(Y|X)H(X,Y)=H(X)+H(Y|X) 2.3 相对熵与互信息相对熵(relative entropy): D(p||q)=∑x∈X p(x)logp(x)q(x)=Eplogp(x)q(x)D(p||q)=∑x∈Xp(x)lo g⁡p(x)q(x)=Eplog⁡p(x)q(x)互信息(mutual information): I(X;Y)=∑x∈X∑y∈Y p(x,y)logp(x,y)p(x)p(y)=D(p(x,y)||p(x)p(y))I(X;Y) =∑x∈X∑y∈Yp(x,y)log⁡p(x,y)p(x)p(y)=D(p(x,y)||p(x)p(y))2.4 熵与互信息的关系I(X;Y)=H(X)−H(X|Y)=H(Y)−H(Y|X)I(X;Y)=H(X)−H(X|Y)=H(Y)−H(Y|X)互信息I(X;Y)是在给定Y知识的条件下X的不确定度的缩减量I(X;Y)=H(X)+H(Y)−H(X,Y)I(X;Y)=H(X)+H(Y)−H(X,Y)2.5 熵,相对熵与互信息的链式法则定理 2.5.1(熵的链式法则): H(X1,X2,...,X n)=∑ni=1H(Xi|X i−1,...,X1)H(X1,X2,...,Xn)=∑i=1nH(Xi| Xi−1, (X1)定理 2.5.2(互信息的链式法则): I(X1,X2,...,X n;Y)=∑ni=1I(Xi;Y|X i−1,...,X1)I(X1,X2,...,Xn;Y)=∑i=1nI(Xi ;Y|Xi−1, (X1)条件相对熵: D(p(y|x)||q(y|x))=∑x p(x)∑yp(y|x)logp(y|x)q(y|x)=Ep(x,y)logp(Y|X)q( Y|X)D(p(y|x)||q(y|x))=∑xp(x)∑yp(y|x)log⁡p(y|x)q(y|x)=Ep(x,y)log⁡p (Y|X)q(Y|X)定理 2.5.3(相对熵的链式法则): D(p(x,y)||q(x,y))=D(p(x)||q(x))+D(p(y|x)||q(y|x))D(p(x,y)||q(x,y))=D( p(x)||q(x))+D(p(y|x)||q(y|x))2.6 Jensen不等式及其结果定理2.6.2(Jensen不等式): 若给定凸函数f和一个随机变量X,则Ef(X)≥f(EX)Ef(X)≥f(EX)定理2.6.3(信息不等式): D(p||q)≥0D(p||q)≥0推论(互信息的非负性): I(X;Y)≥0I(X;Y)≥0定理2.6.4: H(X)≤log|X|H(X)≤log⁡|X|定理2.6.5(条件作用使熵减小): H(X|Y)≤H(X)H(X|Y)≤H(X)从直观上讲,此定理说明知道另一随机变量Y的信息只会降低X的不确定度. 注意这仅对平均意义成立. 具体来说, H(X|Y=y)H(X|Y=y) 可能比H(X)H(X)大或者小,或者两者相等.定理 2.6.6(熵的独立界): H(X1,X2,…,X n)≤∑ni=1H(Xi)H(X1,X2,…,Xn)≤∑i=1nH(Xi)2.7 对数和不等式及其应用定理 2.7.1(对数和不等式): ∑ni=1ailogaibi≥(∑ni=1ai)log∑ni=1ai∑ni=1bi∑i=1nailog⁡aibi≥(∑i =1nai)log⁡∑i=1nai∑i=1nbi定理2.7.2(相对熵的凸性): D(p||q)D(p||q) 关于对(p,q)是凸的定理2.7.3(熵的凹性): H(p)是关于p的凹函数2.8 数据处理不等式2.9 充分统计量这节很有意思,利用统计量代替原有抽样,并且不损失信息.2.10 费诺不等式定理2.10.1(费诺不等式): 对任何满足X→Y→X^,X→Y→X^, 设Pe=Pr{X≠X^},Pe=Pr{X≠X^}, 有H(Pe)+Pe log|X|≥H(X|X^)≥H(X|Y)H(Pe)+Pelog⁡|X|≥H(X|X^)≥H(X|Y)上述不等式可以减弱为1+Pe log|X|≥H(X|Y)1+Pelog⁡|X|≥H(X|Y)或Pe≥H(X|Y)−1log|X|Pe≥H(X|Y)−1log⁡|X|引理 2.10.1: 如果X和X’独立同分布,具有熵H(X),则Pr(X=X′)≥2−H(X)Pr(X=X′)≥2−H(X)3 渐进均分性4 随机过程的熵率4.1 马尔科夫链4.2 熵率4.3 例子:加权图上随机游动的熵率4.4 热力学第二定律4.5 马尔科夫链的函数H(Yn|Y n−1,…,Y1,X1)≤H(Y)≤H(Y n|Y n−1,…,Y1)H(Yn|Yn−1,…,Y1,X1)≤H(Y)≤H(Yn|Yn−1,…,Y1)5 数据压缩5.1 有关编码的几个例子5.2 Kraft不等式定理5.2.1(Kraft不等式): 对于D元字母表上的即时码,码字长度l1,l2,…,l m l1,l2,…,lm必定满足不等式∑iD−li≤1∑iD−li≤15.3 最优码l∗i=−log Dpili∗=−logD⁡pi5.4 最优码长的界5.5 唯一可译码的Kraft不等式5.6 赫夫曼码5.7 有关赫夫曼码的评论5.8 赫夫曼码的最优性5.9 Shannon-Fano-Elias编码5.10 香农码的竞争最优性5.11由均匀硬币投掷生成离散分布6 博弈与数据压缩6.1 赛马6.2 博弈与边信息6.3 相依的赛马及其熵率6.4 英文的熵6.5 数据压缩与博弈6.6 英语的熵的博弈估计7 信道容量离散信道: C=maxp(x)I(X;Y)C=maxp(x)I(X;Y)7.1 信道容量的几个例子7.2 对称信道如果信道转移矩阵p(y|x)p(y|x) 的任何两行相互置换,任何两列也相互置换,那么称该信道是对称的.7.3 信道容量的性质7.4 信道编码定理预览7.5 定义7.6 联合典型序列7.7 信道编码定理7.8 零误差码7.9 费诺不等式与编码定理的逆定理7.10 信道编码定理的逆定理中的等式7.11 汉明码7.12 反馈容量7.13 信源信道分离定理8 微分熵8.1 定义h(X)=−∫Sf(x)logf(x)dxh(X)=−∫Sf(x)log⁡f(x)dx均匀分布 h(X)=logah(X)=log⁡a正态分布h(X)=1/2log2πeδ2h(X)=1/2log⁡2πeδ2 8.2 连续随机变量的AEP8.3 微分熵与离散熵的关系8.4 联合微分熵与条件微分熵8.5 相对熵与互信息8.6 微分熵, 相对熵以及互信息的性质。

《信息论基础》教学大纲《信息论基础》教学大纲课程编号：CE6006课程名称：信息论基础英文名称：Foundation of Information Theory学分/学时：2/32 课程性质：选修课适用专业：信息安全，网络工程建议开设学期：6 先修课程：概率论与数理统计开课单位：网络与信息安全学院一、课程的教学目标与任务本课程是信息安全，网络工程专业选修的一门专业基础课。

通过课程学习，使学生能够较深刻地理解信息的表征、存储和传输的基本理论，初步掌握提高信息传输系统可靠性、有效性、保密性和认证性的一般方法，为后续专业课学习打下坚实的理论基础。

本课程的教学目标：本课程对学生达到如下毕业要求有贡献：1.能够将数学、自然科学、工程基础和专业知识用于解决复杂工程问题。

2.能够应用数学、自然科学和工程科学的基本原理，识别、表达，并通过文献研究分析复杂工程问题，以获得有效结论。

完成课程后，学生将具备以下能力：1.能够针对一个复杂系统或者过程选择一种数学模型，并达到适当的精度。

2.能够应用数学、自然科学和工程科学的基本原理分析、识别、表达、处理及扩展信息安全、网络工程专业的复杂问题。

本课程的性质：本课程是一门理论性较强的专业基础课程，在实施过程中以理论为主，共32学时。

二、课程具体内容及基本要求（一）绪论（2学时）1.基本要求（1）掌握消息、信息和信号；噪声和干扰的基本概念（2）掌握通信系统模型（3）明确Shannon信息论要解决的中心问题2.重点与难点（1）重点：掌握通信系统模型的构成及其相应功能（2）难点：理解Shannon信息论要解决的中心问题3.作业及课外学习要求（1）阅读IEEE IT 1998年信息论50年专刊（2）数字化革命进展-纪念shannon信息论诞生50周年http://202.117.112.49/xxl2/dzjiaoan/95shannon50y.ppt（3）信息论与通信、密码、信息隐藏（一）http://202.117.112.49/xxl2/dzjiaoan/信息论与通信、密码、信息隐藏（一）.ppt （4）信息论与通信、密码、信息隐藏（二）http://202.117.112.49/xxl2/dzjiaoan/信息论与通信、密码、信息隐藏（二）.ppt （5）清华大学朱雪龙“从通信与信号处理观点看信息论研究与应用中的若干问题”http://202.117.112.49/xxl2/dzjiaoan/sponit.mht（二）信息量和熵（8学时）1.基本要求（1）掌握离散随机变量的熵、平均互信息的基本概念及其性质（2）掌握平均互信息的凸性（3）理解信息处理定理2.重点与难点（1）重点：对信息量进行定量描述（2）难点：熵和平均互信息的物理含义及其性质，如何应用熵和平均互信息的基本概念解决实际问题3.作业及课外学习要求熵、平均互信息的计算、信息处理定理等应用（三）离散信源无失真编码（8学时）1.基本要求（1）掌握离散无记忆源等长编码、不等长编码基本概念（2）掌握离散无记忆信源无失真编码定理（3）掌握Huffman编码（4）理解算术编码和LZ编码基本原理2.重点与难点（1）重点：掌握离散无记忆信源无失真编码定理（2）难点：典型序列的概念及其性质、最佳不等长编码3.作业及课外学习要求离散无记忆信源无失真编码定理、无失真信源编码方法（四）信道容量（6学时）1.基本要求（1）掌握信道容量的基本概念（2）掌握离散无记忆信道、组合信道的信道容量计算2.重点与难点（1）重点：掌握信道容量的基本概念及一些特殊信道的容量计算（2）难点：信道的描述方法及信道容量的计算3.作业及课外学习要求信道容量的计算（五）离散信道编码定理（4学时）1.基本要求（1）掌握三种译码准则：最小错误概率译码、最大后验概率译码和最大似然译码（2）了解联合典型序列基本概念（3）理解离散信道编码定理2.重点与难点（1）重点：最大后验概率译码与最大似然译码和离散信道编码定理（2）难点：离散信道编码定理3.作业及课外学习要求译码准则的应用、离散信道编码定理的应用（六）信息论在信息安全中的应用（4学时）1.基本要求（1）了解保密系统模型（2）理解保密、认证的信息理论2.重点与难点（1）重点：完善保密性（2）难点：保密的信息理论3.作业及课外学习要求信息论在信息安全中的应用三、教学安排及方式四、本课程对培养学生能力和素质的贡献点信息论是一门运用概率论与数理统计的方法研究通信系统有效性、可靠性、保密性和认证性等问题的基础课程，也是信息与通信工程、计算机科学与技术、网络空间安全等学科的一门专业基础课程，对毕业要求各指标点的达成主要贡献如下：五、考核及成绩评定方式理论课最终成绩由平时成绩和期末考试成绩组成。

第一章 绪论1、什么是信息？香农对于信息是如何定义的。

答：信息是事物运动状态或存在方式的不确定性的描述(Information is a measure of one's freedom of choice when one selects a message )。

2、简述通信系统模型的组成及各部分的含义。

答：（1）、信源：信源是产生消息的源。

信源产生信息的速率---熵率。

（2）、编码器：编码器是将消息变成适合于信道传送的信号的设备。

包括信源编码器（提高传输效率）、信道编码器（提高传输可靠性）、调制器。

（3）、信道：信道是信息传输和存储的媒介。

（4）、译码器：译码是编码的逆变换，分为信道译码和信源译码。

（5）、信宿：信宿是消息的接收者（人或机器）。

3、简述香农信息论的核心及其特点。

答：（1）、香农信息论的核心：在通信系统中采用适当的编码后能够实现高效率和高可靠性的信息传输，并得出了信源编码定理和信道编码定理。

（2）、特点：①、以概率论、随机过程为基本研究工具。

②、研究的是通信系统的整个过程，而不是单个环节，并以编、译码器为重点。

③、关心的是最优系统的性能和怎样达到这个性能（并不具体设计系统）。

④、要求信源为随机过程，不研究信宿。

第二章 信息的度量2.1 自信息和互信息1、自信息（量）：（1）、定义：一个事件（消息）本身所包含的信息量，它是由事件的不确定性决定的。

某个消息i x 出现的不确定性的大小定义为自信息，用这个消息出现的概率的对数的负值来表示： （2）、性质：①、()i x I是()i x p 的严格递减函数。

当()()21x p x p <时()()21x I x I >概率越小，事件发生的不确定性越大，事件发生以后所包含的自信息量越大。

()()()i i i x p x p x I 1loglog =-=②、极限情况下，当()0=i x p 时()∞→i x I ；当()1=i x p 时，()0→i x I 。

第一章绪论主要内容：（1）信息论的形成和发展；（2）信息论研究的分类和信息的基本概念；（3）一般通信系统模型；（4）目前信息论的主要研究成果。

重点：信息的基本概念。

难点：消息、信号、信息的区别和联系。

说明：本堂课作为整本书的开篇，要交待清楚课程开设的目的，研究的内容，对学习的要求；在讲解过程中要注意结合一些具体的应用实例，避免空洞地叙述，以此激发同学的学习兴趣，适当地加入课堂提问，加强同学的学习主动性。

课时分配：2个课时。

板书及讲解要点：“信息”这个词相信大家不陌生，几乎每时每划都会接触到。

不仅在通信、电子行业，其他各个行业也都十分重视信息，所谓进入了“信息时代”。

信息不是静止的，它会产生也会消亡，人们需要获取它，并完成它的传输、交换、处理、检测、识别、存储、显示等功能。

研究这方面的科学就是信息科学，信息论是信息科学的主要理论基础之一。

它研究信息的基本理论(Information theory)，主要研究可能性和存在性问题，为具体实现提供理论依据。

与之对应的是信息技术(Information Technology)，主要研究如何实现、怎样实现的问题。

它不仅是现代信息科学大厦的一块重要基石，而且还广泛地渗透到生物学、医学、管理学、经济学等其他各个领域，对社会科学和自然科学的发展都有着深远的影响。

1．1 信息论的形成和发展信息论理论基础的建立，一般来说开始于香农(C.E．shannon)研究通信系统时所发表的论文。

随着研究的保深入与发展，信息论具有了较为宽广的内容。

信息在早些时期的定义是由奈奎斯持(Nyquist，H．)和哈特莱(Hartley，L.V.R．)在20世纪20年代提出来的。

1924年奈奎斯特解释了信号带宽和信息速率之间的关系；1928年哈特莱最早研究了通信系统传输信息的能力，给出了信息度量方法；1936年阿姆斯特朗(Armstrong)提出了增大带宽可以使抗干扰能力加强。

这些工作都给香农很大的影响，他在1941—1944年对通信和密码进行深入研究，用概率论的方法研究通信系统，揭示了通信系统传递的对象就是信息，并对信息给以科学的定量描述，提出了信息嫡的概念。

《信息论基础》课程教学大纲《信息论基础》课程教学大纲一、《信息论基础》课程说明（一）课程代码：14131054（二）课程英文名称：Information Theory（三）开课对象：信息管理与信息系统专业（四）课程性质：信息论是20世纪40年代后期从长期通讯实践中总结出来的一门学科，是研究信息的有效处理和可靠传输的一般规律的科学。

本课程是信息管理与信息系统本科的专业课。

它应用近代数理统计方法研究信息传输、存贮和处理，并在长期通信工程实践中不断发展。

因而它是一门新兴科学，亦称为通信的数学理论。

建立在通信理论的数学知识基础之上的信息论在数据压缩、调制解调器、广播、电视、卫星通信，计算机存储，因特网通讯，密码学等方面有着广泛的用途。

要使学生领会信息论的基本思想，具备解决实际问题的能力。

从而学习信息论基础，是将信息论渗透到并应用于更广泛的各种科学技术领域的必经之路，也有助于进一步发展和深化信息概念与信息理论。

先修课程为概率论与数理统计（五）教学目的：本课程是信息管理与信息系统本科生的专业课，采用概率论与随机过程等数学方法研究信息的测度、信道容量以及信源与信道编码等理论问题；主要目的是让学生了解Shannon信息论的基本内容，掌握其中的基本公式和基本运算，培养利用信息论的基本原理分析和解决实际问题的能力，为进一步学习通信和信息以及其他相关领域的高深技术奠定良好的理论基础。

（六）教学内容：掌握熵与互信息的概念，性质与计算；掌握离散信源熵的计算；掌握离散信源编码定理与Huffman编码方法；掌握特殊离散无记忆信道与高斯信道容量的计算；掌握信道编码定理；理解R（d）函数与有失真的信源编码定理.（七）学时数、学分数及学时数具体分配学时数： 36分数： 2（八）教学方式：采用多媒体教学方式（九）考核方式和成绩记载说明考试方式将结合平时作业、平时考核(40%)、期末考试(60%)的各个环节。

使学生能够注重平时学习的过程，改变学生从应试型到能力型。

信息论基础发展史信息论( information theory )是运用概率论与数理统计的方法研究信息、信息熵、通信系统、数据传输、密码学、数据压缩等问题的应用数学学科。

是专门研究信息的有效处理和可靠传输的一般规律的科学，是研究通讯和控制系统中普遍存在着信息传递的共同规律以及研究最佳解决信息的获限、度量、变换、储存和传递等问题的基础理论。

信息论将信息的传递作为一种统计现象来考虑，给出了估算通信信道容量的方法。

信息传输和信息压缩是信息论研究中的两大领域。

这两个方面又由信息传输定理、信源－信道隔离定理相互联系。

信息论从诞生到今天，已有五十多年历史，是在20 世纪40 年代后期从长期通讯实践中总结出来的，现已成为一门独立的理论科学，回顾它的发展历史，我们可以知道理论是如何从实践中经过抽象、概括、提高而逐步形成的。

它是在长期的通信工程实践和理论研究的基础上发展起来的。

通信系统是人类社会的神经系统，即使在原始社会也存在着最简单的通信工具和通信系统，这方面的社会实践是悠久漫长的。

电的通信系统( 电信系统) 已有100 多年的历史了。

在一百余年的发展过程中，一个很有意义的历史事实是：当物理学中的电磁理论以及后来的电子学理论一旦有某些进展，很快就会促进电信系统的创造发明或改进。

当法拉第(M . Faraday)于1820年--1830 年期间发现电磁感应的基本规律后，不久莫尔斯(F ．B．Morse) 就建立起电报系统(1832 —1835) 。

1876 年，贝尔(A . G. BELL)又发明了电话系统。

1864 年麦克斯韦(Maxell) 预言了电磁波的存在，1888 年赫兹(H ．Hertz) 用实验证明了这一预言。

接着1895年英国的马可尼(G.Marc oni) 和俄国的波波夫(A . C. n on oB)就发明了无线电通信。

本世纪初(1907 年) ，根据电子运动的规律，福雷斯特(1 ，Forest) 发明了能把电磁波进行放大的电子管。

《信息论基础》课程教学大纲课程编号：（0531305）课程名称：信息论基础参考学时：48 其中实验或上机学时：0先修课及后续课：先修课：概率论、信号与系统后续课：通信原理、数字图像处理、语音信号处理说明部分1．课程性质本课程是电子信息类专业的技术基础课2．课程教学的目的及意义人类社会的生存和发展无时无刻都离不开信息的获取、传递、处理、控制和利用。

特别是迈入21世纪――高度信息化时代，信息的重要性更是不言而喻。

信息业的发展，需要大量从事信息、通信、电子工程类专业的人才，而《信息论基础》课程为电子信息工程学科的基础课，同时也可作为信息科学其它相关学科的选修课，掌握它，可以指导理论研究和工程应用。

本课程注重基本概念、基本理论和基本分析方法的论述，并结合实例建立数学模型，给出推演过程，力求物理概念清晰、数学结构严谨和完整、逐步深入展开。

通过该课程的学习，使学生掌握香农信息论的三个基本概念，与之相应的三个编码定理，以及信源编码、信道编码的基本理论和主要方法，培养学生能够适应数字通信、信息处理、信息安全、计算机信息管理等编码工作的要求。

使学生掌握信息理论的基本概念和信息分析方法及主要结论，为今后从事信息领域的科研和工程工作进一步研究打下坚实的理论基础。

3．教学内容及教学要求教学内容：该课程是电子信息工程、信息安全工程专业的专业基础课。

是为了适应数字通信、信息处理和信息安全等方面的专业需要开设。

该课程着重介绍信息论应用概率论、随机过程和现代数理统计方法，研究信息提取、传输和处理的一般规律，提高信息系统的有效性和可靠性，实现信息系统的最优化。

信息论是现代通信与信息工程的理论基础，主要内容包括：信息的定义和测度；各类离散信源和信息熵；剩余度；信道和互信息；平均互信息和信道容量；数据处理和信息测量理论；信息率失真函数和数据压缩原理；离散信源无失真和限失真信源编码理论和编码方法；离散有噪信道编码理论和编码原则。

教学基本要求：了解通信系统各部分的主要组成以及作用、香农的三大编码定理；掌握各类离散信源和信息熵、信道及其信道容量、信息率失真函数和数据压缩原理、离常用的无失真信源编码方法、纠错码基本思想及常用的纠错编码方法。