信息论与编码(第1章).ppt

1,信息理论与编码,朱仁祥,电子与信息工程学院,2,考核方式,考查课(48学时)，全部为讲课学时 总评成绩=平时成绩占40+测验成 绩占60,3,注意事项,1、实行请假制度2、保持课堂纪律3、欢迎提出反馈意见,4,本课程以概率论为基础，数学推导较多，学习时主要把注意力集中到概念的理解上，不过分追求数学细节的推导。学习时一定要从始至终注意基本概念的理解，不断加深概念的把握。学习时注意理解各个概念的“用处”，结合其他课程理解它的意义，而不要把它当作数学课来学习，提倡独立思考，注重思考在学习中的重要性。,学习方法,5,课程概述,当今的时代是一个信息的时代，信息处理技术的不断进步极大的影响了我们的生活，使我们的生活质量得到很大提高。本课程将介绍信息科学的基础理论和基本方法，课程将基于一个通讯系统的抽象数学模型进行展开，课程的数学基础为概率论。整个课程可分为基础理论和编码理论两部分组成,6,第一章 绪论,1.1 信息论的形成和发展1.2 通信系统的模型本章重点信息、消息、信号的联系与区别通信系统模型及其各部件的功能作用,7,1.1 信息论的形成和发展,什么叫信息？信息的主要特征是什么？什么叫消息？什么叫信号？什么叫数据？信息、消息、信号三者之间的联系是什么？,8,一、信息的概念,1.信息 从哲学的角度上讲，信息是构成物质世界的三大支柱之一，其他两个是物质和能量。美国安东尼.欧廷教授:没有物质,就什么东西也不存在.没有能量,就什么事情也不发生.没有信息,就什么东西也无意义.可以说我们生活在信息的海洋之中，没有信息就没有世界，当然也就没有我们人类社会。人类利用信息利用信息的历史非常悠久，而且随着人类社会的发展而发展。到了现代，信息的利用已经非常重要，以至于我们当今生活的社会被称作信息社会。可见信息的重要。,9,但是有史以来，人们都没有对信息下过一个确切的定义。就像对于物质和能量一样。信息虽无确切定义，但是却具有两个明显的特征：广泛性与抽象性。广泛性客观世界充满着信息 人类离不开信息 知识、书本是有用信息的积累 抽象性 三大要素是：物质、能量与信息。三要素中物质是基础，是实体。能量是物质运动的形式，E=mc2，物质可转换成能量，而能量又是改造客观世界的主要动力。,10,信息：它依附于物质和能量，但又不同于物质和能量。没有信息就不能更好地利用物质和能量，人类利用信息和知识改造物质，创造新物质，提高能量利用效率，发现新能量形式。信息也是客观存在的，它是人类认识、改造客观世界的主要动力，是人类认识客观世界的更高层次。就狭义而言，在通信中对信息的表达分为三个层次：信号、消息、信息。,11,信号：是信息的物理表达层，是三个层次中最具体的层次。它是一个物理量，是一个载荷信息的实体，可测量、可描述、可显示。如电信号、光信号、生物信号等。消息：(或称为符号)是信息的数学表达层，它虽不是一个物理量，但是可以定量地加以描述，它是具体物理信号的进一步数学抽象。（消息是指包含有信息的语言、文字和图像等）,12,信息：是指各个事物运动的状态及状态变化的方式。人们从来自对周围世界的观察得到的数据中获得信息。信息是抽象的意识或知识，它是看不见、摸不到的。人脑的思维活动产生的一种想法，当它仍储存在脑子中的时候就是一种信息。信息是信号与消息的更高表达层次。三个层次中，信号最具体，信息最抽象。它们三者之间的关系是哲学上的内涵与外延的关系。,13,信息来源于物质，又不是物质本身；它从物质的运动中产生出来，又可以脱离源物质而相对独立地存在；信息来源于精神世界，但又不局限于精神领域；信息与能量息息相关，但又与能量有本质的区别；信息具有知识的本性，但又比知识的内涵更广泛；信息可以被主体获取和利用。(P3)接收者在收到信息之前，对它的内容是不知道的，所以信息是新知识、新内容；信息是能使认识主体对某一事物的未知性或不确定性减少的有用知识；信息可以产生，也可以消失，同时信息可以被携带、贮存及处理；信息是可以量度的，信息量有多少的差别。,2.信息的主要特征,14,信息的基本概念在于它的不确定性，任 何已经确定的事物都不含有信息。,例.如果你问你的同学“明天是星期几”，则答案中含有多少信息量？情况一.你不知道今天是星期几 情况二.你知道今天是星期一,例.同学对你说”你编码原理考试通过了”,你得到了消息,获得了信息吗?,通信过程是一种消除不确定性的过程,不确定性的消除,就获得了信息。,15,3.信息、消息和信号?,信息是事物运动状态或存在方式的不确定性的描述消息是信息的载体，相对具体的概念，如语言，文字，数字，图像信号是把消息变换成适合信道传输的物理量例.收到一封E-mail:”北京成功申办2008年奥运会”是北京申办2008年奥运会具体情况的描述(信息)用中文:”北京成功申办2008年奥运会”来表述(消息)中文不能直接在Internet的传输信道中传输,中文-二进制码-适合信道传输的物理量(信号),才能在信道中传输,在通信系统中形式上传输的是消息,但实质上传输的是信息,16,什么叫数据？,载有信息的可观测、可传输、可存储及可处理的信号均称为数据。,17,语义信息：事物运动状态及方式的具体含义，研究信息的主体含义。语法信息：事物的状态和状态改变方式本身。研究事物运动出现的各种可能状态和这些状态之间的联系。是抽象的。（各种信息要素出现的可能性及各要素之间的相互关系）。语用信息：事物运动状态、方式及其含义对观察者的效用，研究信息客观价值。,4.信息的分类,18,人们对客观世界运动规律 和存在状态的认识结果,语义信息,语法信息,语用信息,19,二、信息论的形成和发展,信息论的奠基人是谁？信息论的开创文章是什么？编码理论的开创文章是什么？香农的三大定理是什么？,20,信息论的发展历史,1924年，奈奎斯特Nyquist提出信息传输理论；1928年，哈特莱Hartley提出信息量关系；1932年，莫尔斯Morse发明电报编码；1946年，柯切尼柯夫提出信号检测理论；1948年，Shannon提出信息论，“通信中的数学理论,21,无失真信源编码,1948年，香农在通信的数学理论的论文中，用概率测度和数理统计的方法系统地讨论了通信的基本问题，得出了几个重要而带有普遍意义的结论。香农理论的核心是：在通信系统中采用适当的编码后能够实现高效率和高可靠性的信息传输，并得出了信源编码定理和信道编码定理。,22,标志着信息论的正式诞生,在前人工作基础上，用概率统计方法研究通信 系统 揭示：通信系统传递的对象信息 提出：信息熵、信息量 指出：通信系统的中心问题 噪声背景下如何有效、可靠地传递信息 实现的主要方法编码,23,提出了无失真信源编码定理、信道编码定理,给出了编码的性能极限 提供了最佳通信系统的理论依据 从数学观点看都是最优编码的存在性定理 从工程观点看，信道编码定理不是结构性的 无失真信源编码定理是结构性的码的平均 长度信源统计特性相匹配,24,无失真信源编码的方法,1948年，香农提出香农编码 1952年，费诺(Fano)提出费诺编码 1952年，霍夫曼(DAHuffman)提出霍夫 曼编码，并证明它是最佳码有限长度的 分组码中，平均码长最短 1982年，里斯桑内(JRissanen)在多年研究 的基础上，与兰登(GGLangdon)一起将 算术码（非分组码）实用化 1977年，齐弗(JZiv)和兰佩尔(ALempel)提出了LZ算法一种通用编码方法,25,1959年，香农发表“保真度准则下的离散信源编码定理”Coding theorems for a discrete source at the fidelity criterion,限失真信源编码,提出率失真函数和率失真信源编码定理 贡献信源编码的核心，压缩编码的理论基础,连续信源在编成代码后不可能无失真地复原 量化有失真最佳量化问题 对于有记忆信源，条件熵必不大于无条件熵 解除符号间的相关性可进一步压缩码率,26,在研究信源编码的同时，另外一部分科学家从事信道编码(纠错码)的研究工作。这一工作已取得了很大的进展，并已经形成一门独立的分支纠错码理论。1950年汉明(RWHamming)发表的论文检错码与纠错码是开拓编码理论研究的第一篇论文。这篇论文主要考虑在大型计算机中如何纠正所出现的单个错误。,27,密码编码学是信息安全技术的核心，密码编码学的主要任务是寻求产生安全性高的有效密码算法和协议，以满足对消息进行加密或认证的要求。密码分析学的主要任务是破译密码或伪造认证信息，实现窃取机密信息或进行诈骗破坏活动。这两个分支既相互对立又相互依存，正是由于这种对立统一关系，才推动了密码学自身的发展。香农在1949年发表的保密通信的信息理论论文中，首先用信息论的观点对信息保密问题作了全面的论述。,28,由于保密问题的特殊性，直至1976年迪弗(Diffe)和海尔曼(Hellman)发表了密码学的新方向一文，提出了公开密钥密码体制后，保密通信问题才得到广泛研究。尤其当今，信息的安全和保密问题更加突出和重要。人们把线性代数、初等数论、矩阵等引入保密问题的研究，已形成了独树一帜的分支密码学理论。,29,1.2 通信系统的模型,通信系统的模型是什么？各部件的功能作用是什么？通信系统的性能指标有哪些？,30,信息论基础的重要性,信息论是信息科学和技术的基本理论，信息科学大厦的地基；没有信息论的基础，从事通信与信息领域的研究和创新是不可能的事情；总之，信息论是高层次信息技术人才必不可少的基础知识。,31,本质信息的传输系统把接收方不知道的信息及时、可靠、完整、安全、经济地传送给指定的接收方,1、通信系统,一、信息论研究的对象,32,2、通信系统的物理模型,33,加密密钥,窃听,信源,信源编码,加密编码,信道,信道编码,信道译码,解密译码,信源译码,信宿,解密密钥,干扰,主要实体：信源和信宿 信道及干扰源 编码器 译码部分编码部分的逆过程,包括：信源、编码器、信道、译码器、信宿五部分,34,加密密钥,窃听,信源,信源编码,加密编码,信道,信道编码,信道译码,解密译码,信源译码,信宿,解密密钥,干扰,包括：信源、信道、信宿三部分,等效无干扰信道,等效信宿,等效信源,35,3、模型中各个部分的作用及 需要研究的核心问题,（1）信源信源是向通信系统提供消息u的人和机器 信源输出的是以符号形式出现的具体消息，它载荷信息。信源输出的消息可归纳为两类离散消息，例如由字母、文字、数字等符号组成的符号序列或者单个符号；连续消息，例如话音、图像、在时间上连续变化的电参数等。信源的核心问题它包含的信息到底有多少，怎样将信息定量地表示出来，即如何确定信息量。,36,（2）信宿信宿是接收消息v的人和机器 信宿的核心问题信宿需要研究的问题是能收到或提取多少信息（3）信道信号从发端传到收端的介质,信道是传递消息的通道，又是传送物理信号的设施信道的中心问题主要是它能够传送多少信息的问题，即信道容量的大小(即研究信道的统计特性和传信能力)狭义信道信号的传输媒质(介)例 明线、电缆、波导、光纤、无线电波空间等.广义 信道除狭义信道外，还包括通信系统某些部分,37,（4）干扰源是整个通信系统中各个干扰的集中反映，用以表示消息在信道中传输时遭受干扰的情况。包括衰落，多径，码间干扰，非线性失真，加性噪声，主要是统计特性对于任何通信系统而言，干扰的性质、大小是影响系统性能的重要因素。（5）密钥源是产生密钥k的源 信源编码器输出信号x经过密钥k的加密运算后，就把明文x变换为密文y,38,（6）编码器信源编码器：对信源输出进行变换，求得有效性 如“奥林匹克运动会”-“奥运会”信道编码器：对信源编码输出变换，提高抗干扰性(例)调制器：将信道编码输出变成适合信道传输的信号（7）译码器 编码器的逆变换中心问题是研究各种可实现的解调和译码方法,说明 不是所有的通信系统都采用这么全面的技术p6对实际通信系统，还应包括换能、调制、发射等各种变换处理上述模型只针对1对1单向通信系统。还有1对多单向系统（广播），1对1双向系统（电话），多对多双向系统（会议电视）等,39,研究通信系统的目的就是要找到信息传输过程的共同规律，以提高信息传输的可靠性、有效性、保密性和认证性，以达到信息传输系统最优化。所谓可靠性高，就是要使信源发出的消息经过信道传输以后，尽可能准确地、不失真地再现在接收端。（首要目标）所谓有效性高，即用尽可能短的时间和尽可能少的设备来传送尽可能多的信息量，或在每一个传送符号内携带尽可能多的信息量。(占用资源少，时间、空间、频率等)（重要目标）以后会看到，提高可靠性和提高有效性常常会发生矛盾，这就需要统筹兼顾。,二、信息论研究的目的,40,所谓保密性就是隐蔽和保护通信系统中传送的消息，使它只能被授权接收者获取，而不能被未授权者接收和理解。所谓认证性是指接收者能正确判断所接收的消息的正确性和完整性，而不是伪造的和被篡改的。,41,信息论所要解决的问题,可靠性有效性保密性认证性,42,研究某一性能时的简化框图,有效性研究,把保密编码、信道编码并入信道。,43,可靠性研究,把信源编码、保密编码并入信源。,44,保密性、认证性研究,把信源编码并入信源，信道编码并入信道。,45,三、通信系统的性能指标及相应的编码 问题,通信系统主要性能指标主要是:有效性、可靠性、安全性和经济性。通信系统优化就是使这些指标达到最佳。根据信息论的各种编码定理和上述通信系统的指标，编码问题可分解为三类：信源编码、信道编码和密码编码。,46,1、信源编（译）码器 信源编码器的作用是把信源发出的消息变换成由二进制码元（或多进制码元）组成的代码组，这种代码组就是基带信号；同时通过信源编码可以压缩信源的冗余度（即多余度），以提高通信系统传输消息的效率。信源编码器分为两类一类是无失真信源编码，适用于离散信源或数字信号；另一类是限失真信源编码，用于连续信源或模拟信号，如语音、图像等信号的数字处理。,47,信源编码器的主要指标是它的编码效率，即理论上能达到的码率与实际达到的码率之比。一般来说，效率越高，编译码器的代价也将越大。信源译码器的作用是把信道译码器输出的代码组变换成信宿所需要的消息形式，它的作用相当于信源编码器的逆过程。2、信道编（译）码器 信道编码器的作用在信源编码器输出的代码组上有目的地增加一些监督码元，使之具有检错或纠错的能力(举例),48,信道编码的主要方法增大码率或频带，即增大所需的信道容量,这恰与信源编码相反。信道译码器的作用具有检错或纠错的功能，它能将落在其检错或纠错范围内的错传码元检出或纠正，以提高传输消息的可靠性。3、密码（编码）学研究的内容如何隐蔽消息中的信息内容，使它在传输过程中不被窃听，提高通信系统的安全性；将明文变换成密文，通常不需要增大信道容量，例如在二进码信息流上叠加一密钥流；但也有些密码要求占用较大的信道容量。,49,例.如果发电报“奥运会”,当收到电报“X运会”时,无法判断所发电报是奥运会、亚运会、大运会、农运会。如果发电报“奥林匹克运动会”，当收到电报“X林匹克运动会”时,很容易纠正错误，译为“奥林匹克运动会”说明信源的冗余度对于抵抗信道的干扰是有益的,50,提高有效性必须去掉信源符号中的冗余部分，此时信道误码会使接收端不能恢复原来的信息，也就是必须相应提高传送的可靠性，不然会使通信质量下降；反之，为了可靠而采用信道编码，往往需扩大码率，也就降低了有效性。安全性也有类似情况编成密码，有时需扩展码位，这样就降低有效性；有时也会因失真而使授权用户无法获得信息，必须重发而降低有效性，或丢失信息而降低可靠性。从理论方面来说，若能把三种码合并成一种码来编译，即同时考虑有效、可靠和安全，可使编译码器更理想化，在经济上可能也更优越。这种三码合一的设想是当前众所关心的课题，但因理论上和技术上的复杂性，要取得有用的结果，还是相当困难。,问题：能否将三种码（信源编码、信道编码和密码）合成一种码进行编译？,51,四、信息论研究的内容,狭义信息论（香农信息论）信息的测度、信道容量、信源和信道编码理论一般信息论 噪声、滤波与预测、估计、保密等广义信息论 所有与信息相关的邻域,52,狭义信息论（经典信息论）指香农信息理论，研究信息测度，信道容量以及信源和信道编码理论，是基础理论一般信息论泛指通信理论，通信的数学理论，广泛研究信息传输和处理的问题，除经典信息论外还包括噪声理论，信号滤波和预测，统计检测和估值理论，调制理论，信息处理理论和保密理论广义信息论除上述内容外，还包括自然和社会领域里所有与信息有关的内容，如模式识别，计算机翻译，心理学，遗传学，神经生理学,53,狭义信息论体系结构,