信息论导论.ppt

1、信息论导论(Introduction to Information Theory),主讲人：马思伟 北京大学数字媒体研究所 ,数字媒体技术基础课程,第三讲,背景,当今的时代是一个信息的时代，信息处理技术的不断进步极大的影响了我们的生活，使我们的生活质量得到很大提高。本部分将介绍信息科学的基础理论和基本方法，将基于一个通讯系统的抽象数学模型进行展开，课程的数学基础为概率论。整个课程可分为基础理论和编码理论两部分组成,背景,本部分以概率论为基础，数学推导较多，学习时主要把注意力集中到概念的理解上，不过分追求数学细节的推导。学习时一定要从始至终注意基本概念的理解，不断加深概念的把握。学习时注意理解各

2、个概念的“用处”，结合其他课程理解它的意义，而不要把它当作数学课来学习，提倡独立思考，注重思考在学习中的重要性。,提 纲,绪论 信息的概念 信息论研究的对象、目的和内容 信息论的发展简史与现状 信源熵 单符号离散信源熵 多符号平稳信源熵 马尔可夫信源 连续熵 信源编码 信道编码 率失真理论,一、绪论,信息,信息 从哲学的角度上讲，信息是构成物质世界的三大支柱之一，其他两个是物质和能量 可以说我们生活在信息的海洋之中，没有信息就没有世界，当然也就没有我们人类社会。人类利用信息利用信息的历史非常悠久，而且随着人类社会的发展而发展。到了现代，信息的利用已经非常重要，以至于我们当今生活的社会被称作信息

3、社会。可见信息的重要 一个抽象的概念，人们都没有对信息下过一个确切的定义。就像对于物质和能量一样 三大要素是：物质、能量与信息。三要素中物质是基础，是实体。能量是物质运动的形式，E=mc2，物质可转换成能量，而能量又是改造客观世界的主要动力。,信息,信息：它依附于物质和能量，但又不同于物质和能量。没有信息就不能更好地利用物质和能量，人类利用信息和知识改造物质，创造新物质，提高能量利用效率，发现新能量形式。信息也是客观存在的，它是人类认识、改造客观世界的主要动力，是人类认识客观世界的更高层次。 就狭义而言，在通信中对信息的表达分为三个层次：信号、消息、信息。,信号：是信息的物理表达层，是三个层次

4、中最具体的层次。它是一个物理量，是一个载荷信息的实体，可测量、可描述、可显示。如电信号、光信号等。 消息：(或称为符号)是信息的数学表达层，它虽不是一个物理量，但是可以定量地加以描述，它是具体物理信号的进一步数学抽象。,信息,信息：信息是指各个事物运动的状态及状态变化的方式。人们从来自对周围世界的观察得到的数据中获得信息。信息是抽象的意识或知识，它是看不见、摸不到的。人脑的思维活动产生的一种想法，当它仍储存在脑子中的时候就是一种信息。信息是信号与消息的更高表达层次。三个层次中，信号最具体，信息最抽象。它们三者之间的关系是哲学上的内涵与外延的关系。,信息,信息的特性,信息来源于物质，又不是物质本

5、身；它从物质的运动中产生出来，又可以脱离源物质而相对独立地存在； 信息来源于精神世界，但又不局限于精神领域； 信息与能量息息相关，但又与能量有本质的区别； 信息具有知识的本性，但又比知识的内涵更广泛； 信息可以被主体获取和利用。,信息的特性,信息的特性 广泛性 客观世界充满着信息 人类离不开信息 知识、书本是有用信息的积累 相对性 可扩散性 时效性 可共享性 可度量性 可压缩性 可存储、传输与携带性,信息的分类,按性质分类：语法信息、语义信息、语用信息 按来源分类：语声信息、图像信息、文字信息、数据信息、计算信息 按载体分类：语声信息、图像信息、文字信息、电磁信息、光学信息、生物信息 按传递方

6、向分类：前馈信息、反馈信息 .,信息量和信息论,信息量 度量信息多少的一个物理量。它从量上反映具有确定概率的事件发生时所传递的信息 信息论 是研究信息的产生、获取、变换、传输、存贮、处理识别及利用的学科，不仅在通信、广播、计算机等电子领域得到直接应用，且已渗透到医学、经济学、生物学等各个领域,信息论发展简史,信息论基础的重要性,信息论是信息科学和技术的基本理论,信息科学大厦的地基; 没有信息论的基础，从事通信与信息领域的研究和创新是不可能的事情; 总之,信息论是高层次信息技术人才必不可少的基础知识。,信息论发展简史,1832年 莫尔斯电码对shannon编码理论的启发 1885年 凯尔文研究了

7、一条电缆的极限传信速率 1917年 坎贝尔（G.A.Campbell）申请了第一个关于滤波器的专利，为频分复用信道提供了条件。 1922年 卡逊对调幅信号的频谱结构进行研究 1924年 奈奎斯特证明了信号传输速率和带宽成正比 1928年 Hartley提出信息量定义为可能消息量的对数 1936年 阿姆斯特朗（E.H.Armstrong）提出频率调制，指出增加信号带宽可以使抑制噪声干扰的能力增强，使调频实用化，出现了调频通信装置。 1939年 Dudley发明带通声码器 1939年 瑞弗（H.Reeve）提出了具有强干扰能力的脉冲调制。 1940年 维纳将随机过程和数理统计引入通信与控制系统 1

8、946年 柯切尼柯夫提出信号检测理论；,信息论发展简史,1948年shannon“通信中的数学理论” ，信息论奠基 1952年Fano证明了Fano不等式，给出了shannon信道编码逆定理的证明 1957，Wolfowitz，1961 Fano，1968Gallager给出信道编码定理的简介证明并描述了码率，码长和错误概率的关系，1972年Arimoto和Blahut发明了信道容量的迭代算法 1956McMillan证明了Kraft不等式。1952年Fano码，Huffman码。1976 Rissanen算术编码，1977，78 Ziv和Lempel的LZ算法,信息论发展简史,1950年汉明

9、码，1960年卷积码的概率译码，Viterbi译码，1982年Ungerboeck编码调制技术，1993年Turbo编译码技术，1999年LDPC编码技术 1959年，Shannon提出率失真函数和率失真信源编码定理 1961年，Shannon的“双路通信信道”开拓了网络信息论的研究，目前是非常活跃的研究领域 计算机技术与通信技术相结合，促进了网络通信的发展，信息论从香农的单用户信息论扩展到多用户信息论,信息论发展简史,研究内容 信息论基础：香农信息论/狭义信息论，主要研究信息的测度、信道容量、信息率失真函数。代表人物香农。 一般信息论：主要研究信息的传输和处理问题，除香农基本理论外还包括噪声

10、理论、信号滤波和预测、统计检测与估计理论、调制理论。代表人物维纳。 广义信息论：凡是能够用广义通信系统模型描述的过程或系统，都能用信息基本理论来研究,信息传递系统,信源 产生消息的源，消息可以是文字，语言，图像。可以离散，可以连续。随机发生。研究的主要问题是消息的统计特性和产生信息的速率 编码器 信源编码器：对信源输出进行变换，求得有效性 信道编码器：对信源编码输出变换，提高抗干扰性 调制器：将信道编码输出变成适合信道传输的方式 信道 信号从发端传到手段的介质,信息传递系统,干扰源 系统各部分引入的干扰，包括衰落，多径，码间干扰，非线性失真，加性噪声，主要是统计特性 信道的中心问题是研究信道的

11、统计特性和传信能力，即信道容量 译码器 编码器的逆变换 中心问题是研究各种可实现的解调和译码方法 信宿 信息的接收者,信息论发展简史,1948年，香农在通信的数学理论的论文中，用概率测度和数理统计的方法系统地讨论了通信的基本问题，得出了几个重要而带有普遍意义的结论。香农理论的核心是：在通信系统中采用适当的编码后能够实现高效率和高可靠性的信息传输，并得出了信源编码定理和信道编码定理。,从数学观点看，这些定理是最优编码的存在定理。但从工程观点看，这些定理不是结构性的，不能从定理的结果直接得出实现最优编码的具体途径。然而，它们给出了编码的性能极限，在理论上阐明了通信系统中各种因素的相互关系，为人们寻

12、找最佳通信系统提供了重要的理论依据。,信息论发展简史,对于确定概率分布的新源编码 1948年，香农在论文中提出并给出了简单的编码方法(香农编码)，1952年,费诺(Fano)提出了一种费诺码，同年霍夫曼(DAHuffman)构造了一种霍夫曼编码方法，并证明了它是最佳码。,信息论发展简史,算术码，是从整个序列的概率的匹配来进行编码的。其实此概念也是香农首先提出的，后经许多学者改进，已进入实用阶段。1968年前后，埃利斯(PElias)发展了香农费诺码，提出了算术编码的初步思路。而里斯桑内(JRissanen)在1976年给出和发展了算术编码，1982年他和兰登(GGLangdon)一起将算术编码

13、系统化，并省去了乘法运算，使其更为简化、易于实现。,信息论发展简史,在研究信源编码的同时，另外一部分科学家从事信道编码(纠错码)的研究工作。这一工作已取得了很大的进展，并已经形成一门独立的分支纠错码理论。1950年汉明(RWHamming)发表的论文检错码与纠错码是开拓编码理论研究的第一篇论文。这篇论文主要考虑在大型计算机中如何纠正所出现的单个错误。,信息论发展简史,密码编码学是信息安全技术的核心，密码编码学的主要任务是寻求产生安全性高的有效密码算法和协议，以满足对消息进行加密或认证的要求。 密码分析学的主要任务是破译密码或伪造认证信息，实现窃取机密信息或进行诈骗破坏活动。 这两个分支既相互对

14、立又相互依存，正是由于这种对立统一关系，才推动了密码学自身的发展。 香农在1949年发表的保密通信的信息理论论文中，首先用信息论的观点对信息保密问题作了全面的论述。,信息论发展简史,由于保密问题的特殊性，直至1976年迪弗(Diffe)和海尔曼(Hellman)发表了密码学的新方向一文，提出了公开密钥密码体制后，保密通信问题才得到广泛研究。 尤其当今，信息的安全和保密问题更加突出和重要。人们把线性代数、初等数论、矩阵等引入保密问题的研究，已形成了独树一帜的分支密码学理论。,信息论发展简史,信息论研究的内容和目的 研究通信系统的目的就是要找到信息传输过程的共同规律，以提高信息传输的可靠性、有效性

15、、保密性和认证性，以达到信息传输系统最优化。 所谓可靠性高，就是要使信源发出的消息经过信道传输以后，尽可能准确地、不失真地再现在接收端。而所谓有效性高，就是经济效果好，即用尽可能短的时间和尽可能少的设备来传送一定数量的信息。提高可靠性和提高有效性常常会发生矛盾，这就需要统筹兼顾。,信息论发展简史,信息论研究的内容和目的 所谓保密性就是隐蔽和保护通信系统中传送的消息，使它只能被授权接收者获取，而不能被未授权者接收和理解。 所谓认证性是指接收者能正确判断所接收的消息的正确性和完整性，而不是伪造的和被篡改的。,信息论发展简史,二、信源熵,提 纲,信源的数学模型 单符号离散信源 自信息、信源熵 信源熵

16、的基本性质和定理 互信息 多符号离散平稳信源 马尔可夫信源 连续信源 连续信源的熵,信源的数学模型及分类,在通信系统中，收信者在未收到信息以前，对信源发出什么样的消息是不确定的，是随机的，所以可以用随机变量、随机矢量或随机过程来描述信源输出的消息，或者说用一个样本空间及其概率测度来描述信源。,信源是产生消息的源，根据X的不同情况，信源可分为以下类型：,根据信源的统计特性，离散信源又分为两种，：,离散信源 消息集X为离散集合。,连续信源 时间离散而空间连续的信源。,无记忆信源 X的各时刻取值相互独立。,有记忆信源 X的各时刻取值互相有关联。,信源的数学模型及分类,根据信源的统计性质与时间的推移是

17、否有关又可区分为平稳信 源、非平稳信源,单符号离散信源,单符号离散信源 对信源的描述可以转化为用概率空间描述信源输出的消息，对于单符号离散信源，可用离散型随机变量X，取值集合x1, x2, xi， xn, 每个元素的取值概率为p(xi) 自信息量 一个随机事件发生某一结果后所带来的信息量称为自信息量，简称自信息，定义为其发生概率对数的负值。若随机事件xi发生的概率为p(xi)，它的自信息I(xi)为： 条件自信息量 条件概率对数的负值。设yj条件下发生xi的条件概率为p(xi/yj)，那么它的条件自信息量I(xi/yj),单符号离散信源,互信息量 信源发出消息xi，信宿端接收到消息yj， xi

18、的后验概率和先验概率比值的对数为yj对xi的互信息量，表示为I(xi; yj): 互信息与自信息、条件自信息的关系 物理意义：xi的自信息可以理解为对yj一无所知的情况下xi存在的不确定度，条件自信息 I(xi/yj)为在已知yj的条件下xi依然存在的不确定度，二者之差为消除已知的确定度，即从yj得到关于xi的信息量度,信源熵 信源的平均信息量，信源各个离散消息的自信息量的数学期望，简称熵，标记为H(X),信源熵,例：天气预报，有两个信源,则：,说明第二个信源的平均不确定性更大一些,信源熵,条件熵 已知随机变量Y的条件下，随机变量X的条件熵H(Y/X),信源熵,信源熵的特性,非负性 信息熵是自

19、信息的数学期望，自信息是非负值 对称性 任意调换p(xi) , p(xj)的顺序上式仍成立，说明熵只与信源的总体结构有关，而不在乎个别消息的概率，甚至与消息的取值无关 扩展性 一个随机变量取值有n种，另一种有n+1种，如后者中有一种取值的概率趋于零，且其他概率均与前者在总体上相等，则两者的熵值相同 物理意义：信源的消息数可以很多，但如果某些离散消息对应的概率很小，可以忽略其对熵的贡献,信源熵的特性,确定性 可加性 极值性,上式表明，对于具有q个符号的离散信源，只有在q个信源符号等可能出现的情况下，信源熵才能达到最大值，这也表明等概分布的信源的平均不确定性最大，这是一个很重要得结论，称为最大离散

20、熵定理,例：对于一个二元信源 H(X)=H(1/2,1/2)=log2=1bit,各类熵的关系,条件熵不大于信息熵 证明： 上式也叫做熵的不增原理：在信息处理过程中，条件越多，熵就越小。,各类熵的关系（续）,联合熵不大于各个信息熵的和，即 证明：,互信息量 从通信的角度引出互信息量的概念 信源符号X=x1，x2，xI ，xia1,a2,ak，i = 1, 2 , I。 经过信道传输，信宿方接收到符号 Y = y1，y2，yJ，yjb1,b2,bD，j = 1, 2, ,J。,简单的通信模型,互信息量,事件xi是否发生具有不确定性，用I(xi)度量。 接收到符号yj后，事件xi是否发生仍保留有一

21、定的不确定性，用I(xiyj)度量。 观察事件前后，这两者之差就是通信过程中所获得的信息量，称为事件xi和事件yj之间的互信息量， 用I(xi ; yj )表示： 。,注：I(xi ；yj ) 和I(xiyj )的区别在于： 前者是事件xiX和事件yjY之间的互信息量，后者是二维空间XY 上元素xi yj 的自信息量。,互信息量,对于无扰信道，I(X ; Y)=H(X)。,对于强噪信道，I(X ; Y)= 0。,根据概率互换公式p(xi yj) = p(yjxi)q(xi)=(xiyj)(yj) 互信息量I(xi ;yj )有多种表达形式: (2-7) (2-8),将事件互信息量的概念推广至多

22、维空间： 在三维X Y Z联合集中，有： I(xi ; yj zk)= I(xi ; yj )+ I(xi; zkyj) （2-9）,类似，在N维U1 U2 UN联合空间,有： I (u1; u2u3 uN ) = I (u1; u2 )+ I (u1; u3u2) + + I (u1; uiu2 u i-1)+ + I (u1; uNu2 uN -1) （2-10）,平均互信息量的性质,(1) 非负性：,(2)互易性： I(X ; Y)= I(Y ; X) 由 的对称性可得到。,(3),例 二进制对称信道BSC如图2-10所示，输入符号集X =x1,x2=0,1，输出符号集Y =y1,y2=

23、0,1，信道转移概率矩阵 ，信源分布为： ，计算平均互信 息量 I(X;Y)= H（Y）-H（YX）,平均互信息量,先由 算出： (0) = q(0) p(00) + q(1) p(01) =(1-) + (1-) (1) = = 1-(0),再计算熵和条件熵 = H2 (1-) + (1-) = - (1-) log (1-)-log= H2 (),则平均互信息量 I(X;Y)= H（Y)-H（YX）= H2 (1-) + (1-) - H2 (),平均互信息量,各种熵之间的关系,H(X),H(Y),I(X;Y),H(Y|X),H(X|Y),I(X,Y),离散无记忆信源,实际信源输出的消息往

24、往是时间上或空间上的一系列符号，若信源序列的前后符号之间是统计独立的，不存在统计依赖关系的，则称为离散无记忆信源。 如在二元系统中，我们可以把两个二元数字看成一组，会出现四种可能情况：00、01、10和11，我们可以把这四种情况看成一个新的信源称为二元无记忆信源的二次扩展信源，相应的，如果把N个二元数字看成一组，则新的信源称为二元无记忆信源的N此扩展信源。,离散平稳信源,一般来说，信源的前后消息之间有前后依赖关系，可以用随机矢量描述：,信源在某一时刻发出什么样的值取决于两方面 1、这一时刻该变量的分布概率 2、这一时刻以前发出的消息 如一个人讲话 我们现在讨论平稳的随机序列，所谓平稳是指序列的

25、统计性质与时间的推移无关（俩个任意时刻信源发出符号的概率分布完全相同）。,离散平稳信源的数学定义,多符号离散平稳信源,定义 对于随机变量序列X=X1X2.XN, 若任意两个不同时刻i和j(大于1的任意整数)，信源发出消息的概率分布完全相同，即 P(Xi=x1)=P(Xj=x1)=P(x1) P(Xi=x2)=P(Xj=x2)=P(x2) P(Xi=xn)=P(Xj=xn)=P(xn) 则称这种信源为一维平稳信源，同理，若联合概率分布P(XiXi+1)也与时间起点无关，即P(XiXi+1)=P(XjXj+1), 则称为二维平稳信源。进一步，在各维联合概率均与时间起点无关的完全平稳信源称为离散平稳

26、信源一般指有记忆信源，即发出的各个符号之间具有统计关联关系的一类信源。,多符号离散平稳信源,根据信息熵的定义，可得： （1）联合熵,可以表征信源输出长度为2的平均不确定性，或所含有的信息量。因此可以用 作为二维平稳信源的信息熵的近似值,(2)条件熵,则：,多符号离散平稳信源,可以证明：,多符号离散平稳信源,例2-15 设某二维离散信源的原始信源的信源空间 X=x1,x2,x3; P(X)=1/4, 1/4, 1/2, 一维条件概率为： p(x1/x1)=1/2; p(x2/x1)=1/2; p(x3/x1)=0; p(x1/x2)=1/8; p(x2/x2)=3/4; p(x3/x2)=1/8

27、; p(x1/x3)=0; p(x2/x3)=1/4; p(x3/x3)=3/4; 原始信源的熵为： H(X)=1.5 bit/符号 条件熵： H(X2/X1)=1.4 bit/符号 可见： H(X2/X1)H(X) 二维信源的熵：H(X1,X2)=H(X1)+H(X2/X1)=2.9 bit/消息 每个信源符号提供的平均信息量为： H2(X1,X2)=H(X1,X2)/2=1.45 bit/符号。,多符号离散平稳信源,离散平稳信源的极限熵,平均符号熵,条件熵,有以下几点性质,（1）条件熵随N的增加是非递增的 （2）N给定时，平均符号熵大于等于条件熵 （3）平均符号熵随N的增加是非递增的 （4）,称 为极限熵。,多符号