第一章信息论基础.ppt

信息论与编码,陈运主编电子工业出版社,课程介绍,信息论美国数学家香农(C.E.Shannon)在1948年发表著名论文“通信的数学理论”开创了信息论编码理论信息论的一个重要分支编码理论用概率论、随机过程、数理统计等方法来研究信息的存储、传输、处理过程中一般规律的学科编码含义信号变换，是信息处理的主要手段编码目的提高系统对某一方面的要求优化系统某一方面的性能指标,课程介绍(续),通信系统主要性能指标有效性可靠性安全性编码分类信源编码提高通信系统的有效性信道编码提高通信系统的可靠性保密编码保证通信系统的安全性研究信息的度量(信源熵)、信道容量、信息率失真函数（香农三定理）、密码学,课程内容,第1章信息论基础第2章信息的度量第3章离散信源无失真编码无失真信源编码定理（香农第一定理）第4章信息率失真函数限失真信源编码定理（香农第三定理）第5章信道容量信道编码定理（香农第二定理）第6章有噪信道编码第7章信道编码第8章密码学,参考书,孙丽华等.信息论与编码.电子工业出版社，2005陈运等信息论与编码电子工业出版社，2002戴善荣信息论与编码基础机械工业出版社，2005田丽华编码理论西安电子科技大学出版社，2003曹雪虹等信息论与编码北京邮电大学出版社，2001,第1章信息论基础,第1章信息论基础,内容提要信息论是应用近代概率统计方法研究信息传输、交换、存储和处理的一门学科，也是源于通信实践发展起来的一门新兴应用科学。本章首先引出信息的概念，简述信息传输系统模型的各个组成部分，进而讨论离散信源和离散信道的数学模型，简单介绍几种常见的离散信源和离散信道。,花朵开放时的色彩是一种信息，它可以引来昆虫为其授粉；,成熟的水果会产生香味，诱来动物，动物食后为其传播种子，果香也是一种信息；,药有苦味，让人难以吞咽，药味是一种信息；,听老师讲课可以得到许多知识，知识也是信息。,色彩,视觉,果香,嗅觉,苦药,味觉,知识,听觉,总之，信息处处存在，人的眼、耳、鼻、舌、身都能感知信息。,冷热,触觉,1928年，美国数学家哈特莱(Hartley)在贝尔系统电话杂志上发表了一篇题为信息传输的论文。他认为“信息是选择的自由度”。,事隔20年，另一位美国数学家香农(C.E.Shannon)在贝尔系统电话杂志发表了题为通信的数学理论的长篇论文。他创立了信息论，但是却没有给出信息的确切定义他认为“信息就是一种消息”。,美国数学家、控制论的主要奠基人维纳(Wiener）1950年出版的控制论与社会。,书中写到：“信息既不是物质又不是能量，信息就是信息”。揭示了信息的特质：即信息是独立于物质和能量之外存在于客观世界的第三要素。,信息是人与外界相互作用的过程中所交换的内容的名称。,消息：信息的外壳，信息这是消息的内核，同样多的消息，所包含的信息量可能差异很大；反之，不同形式的消息可能包含同样多的信息。信号：不等同于信息，信号只是信息的载体，信息是信号所载荷的内容。数据：是记录信息的一种形式，且不是唯一的形式。情报：在日常的确是信息，只是一类专门的信息，是信息的一个子集。,信息定义:最高的层次的定义是最普遍的层次，也是无约束条件的层次，定义事物的“信息是该事物运动的状态和状态改变的方式”。我们把它叫做“本体论”层次。在这个层次上定义的信息是最广义的信息，使用范围也最广。,引入一个最有实际意义的约束条件：认识主体。信息定义就转化为“认识论”层次的信息定义。即：信息是认识主体（生物或机器）所感知的或所表述的相应事物的运动状态及其变化方式，包括状态及其变化方式的形式、含义和效用。其中认识主体所感知的东西是外部世界向认识主体输入的信息，而认识主体所表述的东西则是其向外部世界输出的信息。,认识论比本体论的层次要低，因为认识主体具有感觉能力、理解能力和目的性，所以从认识论层次上研究信息“事物的运动状态及其变化方式”就不再像本体论层次上那样简单，他必须考虑到形式、含义和效用。,全信息,同时考虑事物运动状态及其变化方式的外在形式、内在含义和效用价值的认识论层次信息。,语义信息,考虑其中含义因素的部分。,语用信息,考虑其中效用因素的部分。,语法信息,仅仅考虑其中形式因素的部分。,物质、能量和信息是构成客观世界的三大要素。信息是物质和能量在空间和时间上分布的不均匀程度，或者说信息是关于事物运动的状态和规律。,信息存在于自然界，也存在于人类社会，其本质是运动和变化。可以说哪里有事物的运动和变化，哪里就会产生信息。,人类交换信息的形式丰富多彩，使用的信息载体非常广泛。概括起来，有语言、文字和电磁波。,信息必须依附于一定的物质形式存在,这种运载信息的物质，称为信息载体。,信息的主要特征：,根据上述特征和信息的基本定义，可以导出信息的一些重要性质：,信息在信息化程度越来越高的社会中将起到越来越重要的作用，是比物质和能量更为宝贵的资源。,通信系统中形式上传输的是消息，实质上传输的是信息，消息中包含信息，消息是信息的载体。,信息论的研究内容：是研究信息的基本性质及度量方法，研究信息的获取、传输、存储和处理的一般规律的科学。,对于信息论的研究，一般划分为三个不同的范畴：,广义信息论，包括信息论在自然和社会中的新的应用，如模式识别、机器翻译、自学习自组织系统、心理学、生物学、经济学、社会学等一切与信息问题有关的领域。,实用信息论，研究信息传输和处理问题，也就是狭义信息论方法在调制解调、编码译码以及检测理论等领域的应用。,狭义信息论，即通信的数学理论，主要研究狭义信息的度量方法，研究各种信源、信道的描述和信源、信道的编码定理。,亦称香农信息论或狭义信息论。主要研究信息的测度、信道容量、信息率失真函数，与这三个概念相对应的香农三定理以及信源和信道编码。,主要是研究信息传输和处理问题。除了香农基本理论之外，还包括噪声理论、信号滤波和预测、统计检测与估计理论、调制理论。后一部分内容以美国科学家维纳（NWiener）为代表。,虽然维纳和香农等人都是运用概率和统计数学的方法研究准确或近似再现消息的问题，都是通信系统的最优化问题。但他们之间有一个重要的区别。,维纳研究的重点是在接收端。研究消息在传输过程中受到干扰时，在接收端如何把消息从干扰中提取出来，并建立了最佳过滤理论（维纳滤波器）、统计检测与估计理论、噪声理论等。,香农研究的对象是从信源到信宿的全过程，是收、发端联合最优化问题，重点是编码。为此，发展了信息测度理论、信道容量理论和编码理论等等。,1.2信息的分类,在众多的分类原则和方法中，最重要的就是按照信息性质的分类。,按照性质的不同可以把信息划分成语法信息、语义信息和语用信息三个基本类型。其中最基本也是最抽象的类型是语法信息。也是迄今为止在理论上研究得最多的类型。,语法信息考虑的是事物运动状态和变化方式的外在形式。,当然，按照事物运动的方式，还可以把信息进一步细分为概率信息、偶发信息、确定信息和模糊信息。香农信息论主要讨论的是语法信息中的概率信息，本书也以概率信息为主要研究对象。,信息传输和传播手段经历了五次重大变革：,通信的基本问题是在彼时彼地精确地或近似地再现此时此地发出的消息。,各种通信系统，一般可概括的统计模型：,这个模型包括以下五个部分：,3.信道信道是信息传输和存储的媒介。,4.译码器译码是编码的逆变换，分为信道译码和信源译码。,5.信宿信宿是消息的接收者。,2.编码器编码器是将消息变成适合于信道传送的信号的设备。,1.信源信源是产生消息的源。,通信系统模型方框图:,信息度量的方法有：结构度量、统计度量、语义度量、语用度量、模糊度量等等。最常用的方法是统计度量。它用事件统计发生概率的对数描述事物的不确定性，得到消息的信息量，建立熵的概念。熵概念是香农信息论最基本最重要的概念。,信息论是在信息可以度量的前提下，研究有效地、可靠地、安全地传输信息的科学。,50,1948年，香农发表“通信的数学理论”，标志着信息论的正式诞生C.E.Shannon,AMathematicalTheoryofcommunication,BellSystemTech.J,vol.27,PP379-423,July1948在前人工作基础上，用概率统计方法研究通信系统揭示：通信系统传递的对象信息提出：信息熵、信息量指出：通信系统的中心问题噪声背景下如何有效、可靠地传递信息实现的主要方法编码提出了无失真信源编码定理、信道编码定理,1.4编码理论的发展1.4.1无失真信源编码,51,提出了无失真信源编码定理、信道编码定理给出了编码的性能极限提供了最佳通信系统的理论依据从数学观点看都是最优编码的存在性定理从工程观点看，信道编码定理不是结构性的无失真信源编码定理是结构性的码的平均长度信源统计特性相匹配,1.4.1无失真信源编码(续),52,无失真信源编码的方法1948年，香农提出香农编码1952年，费诺(Fano)提出费诺编码1952年，霍夫曼(DAHuffman)提出霍夫曼编码，并证明它是最佳码有限长度的分组码中，平均码长最短1982年，里斯桑内(JRissanen)在多年研究的基础上，与兰登(GGLangdon)一起将算术码（非分组码）实用化1977年，齐弗(JZiv)和兰佩尔(ALempel)提出了LZ算法一种通用编码方法,1.4.1无失真信源编码(续),53,1959年，香农发表“保真度准则下的离散信源编码定理”Codingtheoremsforadiscretesourceatthefidelitycriterion提出率失真函数和率失真信源编码定理贡献信源编码的核心，压缩编码的理论基础连续信源在编成代码后不可能无失真地复原量化有失真最佳量化问题（如A律13折线法）对于有记忆信源，条件熵必不大于无条件熵解除符号间的相关性可进一步压缩码率,1.4.2限失真信源编码,54,解除相关性的编码预测编码利用前几个符号来预测后一符号值，并对差值进行编码（如：DPCM）变换编码样值空间的变换，如从时域变到频域某些情况下，可减弱相关性，取得良好压缩比现代压缩编码方法小波变换、神经网络、模型基编码、分形编码等,1.4.2限失真信源编码(续),55,1950年汉明(RWHamming)发表“检错码与纠错码”论文开拓编码理论研究的第一篇论文,1.4.3信道编码,56,1961年香农发表“双路通信信道”论文开拓了多用户信息理论的研究多用户信息论网络信息论,1.4.4网络信息论,57,保密学一门研究通信安全和保护信息资源的既古老又年青的学科包括：密码编码学、密码分析学密码编码学信息安全技术的核心主要任务对消息进行加密、认证密码分析学与密码编码学相反主要任务破译密码、伪造认证两个分支既相互对立又相互依存,1.4.5保密编码,58,1949年，香农发表论文“保密通信的信息理论”，首次用信息论观点对信息保密问题作了全面论述1976年，迪弗(Diffe)和海尔曼(Hellman)发表“密码学的新方向”，提出了公开密钥密码体制后，保密通信问题才得到广泛研究当今，信息的安全和保密问题更加突出和重要人们把线性代数、初等数论、矩阵等引入保密问题研究，已形成了独树一帜的分支密码学,1.4.5保密编码(续),59,1.5编码理论研究的内容和目的1.5.1通信系统研究的目的,目的寻找信息传输过程的共同规律，以提高信息传输可靠性、有效性、保密性和认证性以达到信息传输系统最优化(1)四性有效性高占用资源少(时间、空间、频率等)可靠性高信源消息尽可能准确地在收端再现保密性对所传送的消息进行隐蔽和保护认证性接收者能正确判断所接收的消息的正确性和完整性,60,1.5.1通信系统研究的目的(续),(2)研究某性能时的简化框图在具体研究某一性能时可将某些功能框合并，以简化有效性研究把保密编码、信道编码并入信道,61,1.5.1通信系统研究的目的(续),可靠性研究把信源编码、保密编码并入信源,62,1.5.1通信系统研究的目的(续),保密性、认证性研究把信源编码并入信源，信道编码并入信道,63,1.5.2信源编码,(1)目标压缩信源码率具体减小平均码长(信源符号的平均比特数)(2)分类经典压缩编码无失真、限失真信源编码现代压缩编码,64,1.5.2信源编码(续),(3)经典信源编码的两种基本途径设法改变信源概率分布，使之尽可能不均匀再用最佳编码方法使平均码长逼近信源熵压缩上界信息熵例霍夫曼编码、算术编码、游程编码等去除、减少信源序列的相关性，使之成为不相关、低相关信源例预测编码、变换编码、混合编码、矢量量化等,65,1.5.2信源编码(续),(4)现代压缩编码经典压缩编码方法依据了信源本身固有的统计特性，并利用了人类视觉系统的某些特性来进行压缩编码，但利用得还不够充分现代压缩编码方法突破了传统香农理论的框架，注重对感知特性的利用，使压缩率极大提高例小波变换、神经网络、模型基编码、分形编码等,66,1.5.3信道编码,(1)目标是提高信息传输的可靠性干扰、噪声使通信质量下降模拟信号信噪比下降数字信号误码率增大(2)方法增大传输所需的信道资源(码率或带宽)模拟信号增大带宽，换取所需信噪比的减小数字信号增高码率（信息位后增设监督位）(3)理论基础信道编码定理内容当信息率R低于信道容量C时，误码可接近零当信息率R高于信道容量C时，必有误码,67,1.5.4保密编码,1949年，香农发表论文“保密通信的信息理论”，首次用信息论观点对信息保密问题作了全面论述1976年，迪弗(Diffe)和海尔曼(Hellman)发表“密码学的新方向”一篇具有里程碑意义的文章，此后保密通信问题才得到广