信息论与编码-第一课.ppt

1、信息论与编码,授课老师：魏平俊 联系电话Email: ,信息论与编码,教学内容 香农信息论的基本概念、基本理论 信息、熵、信道容量、编码定理（无失真信源编码、有 噪信道编码，限失真信源编码等，信道编码理论） 信道编码 基本原理、常用码编译原理和方法 信源编码 密码学简介,信息论与编码,教学重点： 信息度量、信道容量、无失真信源编码、限失真信源编码、信道编码的基本理论及实现原理。,信息论与编码,参考书： 信息论与编码，曹雪虹 张宗橙编，清华大学出版社，2004 信息论基础理论与应用， 傅祖芸编著，电子工业出版社，2001 信息理论基础，周炯槃 信息与编码理论，王育民、梁

2、传甲，西北电讯工程学院出版社 The theory of information and coding, R.J. McEliece 纠错码-原理与方法，王新梅 信道编码，刘玉君,信息论与编码-绪论,第一章 绪论 1.1信息论的基本概念 1.2信息论发展简史 1.3信道编码发展简史 1.4通信系统的基本模型,信息论与编码-绪论,1.1信息论的基本概念,信息论与编码-绪论,1.1信息论的基本概念 信息 如何定义信息、如何度量信息、如何计算信息,信息论与编码-绪论,1.1信息论的基本概念 信息 如何定义信息、如何度量信息、如何计算信息 信息论 如何处理信息、如何传递信息、如何提取信息,信息论与编码

3、-绪论,信息的一般含义,信息论与编码-绪论,信息的一般含义 信息至今无确切定义，但是它是一种人人皆知的抽象概念，是一种不言自明的概念。,信息论与编码-绪论,信息的一般含义 信息至今无确切定义，但是它是一种人人皆知的抽象概念，是一种不言自明的概念。 信息在不同的领域内有不同的定义。,信息论与编码-绪论,信息的一般含义 信息至今无确切定义，但是它是一种人人皆知的抽象概念，是一种不言自明的概念。 信息在不同的领域内有不同的定义。 在通信领域内是指通信时所要告诉对方的某种“内容”。或者说是接受方在接受到一个符号或一个序列后，所获得的“内容”。,信息论的研究范畴,信息论与编码-绪论,信息论的研究范畴 信

4、息论是在信息可以度量的基础上，对如何有效、可靠地传递信息进行研究的科学。,信息论与编码-绪论,信息论的研究范畴 信息论是在信息可以度量的基础上，对如何有效、可靠地传递信息进行研究的科学 狭义信息论：信息度量、信息特征、信息传输速率、信道容量、干扰对信息传输的影响等。,信息论与编码-绪论,信息论的研究范畴 信息论是在信息可以度量的基础上，对如何有效、可靠地传递信息进行研究的科学。 狭义信息论：信息度量、信息特征、信息传输速率、信道容量、干扰对信息传输的影响等 广义信息论：还包括信号设计、噪声理论、信号的检测与估值等。,信息论与编码-绪论,信息论与编码-绪论,本书所要解决的问题 什么是信息、如何度

5、量信息？ 在信息传输中，基本的极限条件是什么？ 对于信息的压缩和恢复的极限条件是什么？ 从环境中抽取信息极限的条件是什么？ 设计什么样的设备才能达到这些极限？ 这些设备是否存在？,信息论与编码-绪论,1.2 信息论发展简史和现状 信息论的奠基人克劳德艾尔伍德香农（Claude Elwood Shannon，1916年4月30日2001年2月26日）美国数学家 于1916年4月30日出生于美国密歇根州的Petoskey 1936年毕业于密歇根大学并获得数学和电子工程学士学位 1940年获得麻省理工学院（MIT）数学博士学位和电子工程硕士学位 1941年他加入贝尔实验室数学部，工作到1972年 1

6、956年他成为麻省理工学院（MIT）客座教授，并于1958年成为终生教授，1978年成为名誉教授 香农博士于2001年2月26日去世，享年84岁,信息论与编码-绪论,1948年在贝尔系统技术杂志上发表了244页的长篇论著，通信的数学理论。 1949年，他又在同一杂志上发表了另一篇名著噪声下的通信。 在这两篇文章中，他解决了过去许多悬而未决的问题：经典地阐明了通信的基本问题，提出了通信系统的模型，给出了信息量的数学表达式，解决了信道容量、信源统计特性、信源编码、信道编码等有关精确地传送通信符号的基本技术问题。 两篇文章成了现在信息论的奠基著作,信息论与编码-绪论,信息论与编码-绪论,1832年莫

7、尔斯电报系统中高效率编码方法对后来香农的编码理论是有启发的。 1885年凯尔文(L. Kelvin)曾经研究过一条电缆的极限传信率问题。 1922年卡逊(JRCarson)对调幅信号的频谱结构进行了研究，并建立了信号频谱概念。 1924年奈奎斯特(HNyquist)指出，如果以一个确定的速度来传输电报信号，就需要一定的带宽。他把信息率与带宽联系起来了。 1928年哈特莱(RVHartley)发展了奈奎斯特的工作，并提出把消息考虑为代码或单语的序列。 1936年阿姆斯特朗(EHArmstrong)认识到在传输过程中增加带宽的办法对抑制噪声干扰肯定有好处。根据这一思想他提出了宽偏移的频率调制方法，

8、该方法是有划时代意义的。,信息论与编码-绪论,Shannon受着前辈的工作的启示，其中最具代表性的是贝尔系统技术杂志上所披露的奈奎斯特的影响电报速率的一些因素和哈特莱的信息的传输。正是他们最早研究了通信系统的信息传输能力，第一次提出了信息量的概念，并试图用教学公式予以描述。而香农则创造性地继承了他们的事业，在信息论的领域中钻研了8年之久，终于创建了信息论。,信息论与编码-绪论,“通信的基本问题就是在一点重新准确地或近似地再现另一点所选择的消息”。通信的数学理论中的一句铭言。正是沿着这一思路他应用数理统计的方法来研究通信系统，从而创立了影响深远的信息论。 不确定性 接收者收到某一消息后所获得的信

9、息，可以用接收者在通信前后“不确定性”的消除量来度量。简而言之，接收者所得到的信息量，在数量上等于通信前后“不确定性”的消除量(或减少量)。-这就是信息理论中度量信息的基本观点。,信息论与编码-绪论,香农信息理论具有崭新的风貌，是通信科学发展史上的一个转折点，它使通信问题的研究从经验转变为科学。因此，它一出现就在科学界引起了巨大的轰动，许多不同领域的科学工作者对它怀有浓厚的兴趣，并试图争相应用这一理论来解决各自领域的问题从此，信息问题的研究，进入了一个新的纪元。,信息论与编码-绪论,广义信息论 信息论的诞生，激起了人们对信息论的巨大热情，它向各门学科冲击，研究规模像滚雪球一样越来越大。不仅在电

10、子学的其他领域，如计算机、自动控制等方面大显身手，而且遍及物理学、化学、生物学、心理学、医学、经济学、人类学、语音学、统计学、管理学等学科。它已远远地突破了香农本人所研究和意料的范畴，即从香农的所谓“狭义信息论”发展到了“广义信息论”,信息论与编码-绪论,信息的定义 Shannon:随机不定性程度的减少 局限性:没有包含信息的内容和价值，只考虑了随机型的不定性，没有从根本上回答“信息是什么”的问题。 1948年维纳（N. Wiener）:信息是人们在适应外部世界，并且这种适应反作用于外部世界的过程中，同外部世界进行互相交换的内容的名称。维纳关于信息的定义包含了信息的内容与价值，从动态的角度揭示

11、了信息的功能与范围，但也有局限性。由于人们在与外部世界的相互作用过程中，同时也存在着物质与能量的交换，维纳关于信息的定义没有将信息与物质、能量区别开来。 1975年，意大利学者朗高（G. Longo）在信息论：新的趋势与未决问题一书的序言中认为信息是反映事物的形式、关系和差别的东西，它包含在事物的差异之中，而不在事物本身。当然，有差异就是信息的观点是正确的，但是反过来说没有差异就没有信息就不够确切。所以，信息就是差异的定义也有其局限性。,信息论与编码-绪论,据不完全统计，有关信息的定义有100多种，它们都从不同的侧面、不同的层次揭示了信息的特征与性质，但同时也都有这样或那样的局限性。 1988

12、年，我国信息论专家钟义信教授在信息科学原理一书中把信息定义为：信息是事物的运动状态和状态变化的方式。并通过引入约束条件推导了信息的概念体系，对信息进行了完整和准确的描述。 信息的这个定义具有最大的普遍性，不仅涵盖所有其他的信息定义，而且通过引入约束条件还能转化为所有其他的信息定义。 也有人对此提出异议，如鲁晨光（广义信息论作者）。,信息论与编码-绪论,钟义信 1940年2月出生, 汉族，北京邮电大学教授、 博士生导师、副校长、校学术委员会主席。 长期从事通信理论、信息理论、信息科学、人工智能、 神经网络、决策学、信息经济学领域的研究和教学工作，在上述领域先后出版学术著作16 部，在国内外学术刊

13、物和学术会议上发表学术论文380多篇。 代表性学术论著包括信息科学原理（1988年）、信息技术通论（1994）、智能理论与技术人工智能与神经网络（1992）、伪随机编码通信：原理与应用（1978）等。 具有重要创新意义的学术贡献主要包括 “知识论”、“全信息理论”、“意识机模型”、“信息科学原理与信息科学方法论”、“信息基础结构理论模型”等。,信息论与编码-绪论,为什么Shannon信息论在解决通信系统的问题方面非常有效，但是在涉及人工智能理论研究的问题是就无能为力？ 信息论只关注信号（信息的载体）的波形，不关心它的内容和价值。通信系统的设计可以只关心信号的波形。 人工智能却必须“理解信息的内

14、容和价值”。 为此，经过长期的研究，提出和建立了“全信息理论”-能够统一考虑信息的形式因素（称为语法信息）、内容因素（称为语义信息）和价值因素（称为语用信息）的全新的信息理论。,信息论与编码-绪论,信息论的研究范畴,基础 信息论,工 程信息论,广义 信息论,信息论与编码-绪论,基础信息论 主要研究通信系统的数学描述与定量分析，研究系统的最优状态与优化理论，即研究通信系统理论上的潜在能力与数学上的极限情况。它是以存在性研究为主体，又称它为数学信息论。 工程信息论 以工程为背景，主要研究通信系统中各部分的最佳工作规律，与最佳设计原则，它以构造性为主体，以工程上技术问题为主。主要包括： 信源编、译码

15、理论及其设计构造方法； 信道编、译码理论及其设计构造方法； 最佳调制与解调理论与实现； 最佳检测、估值与最佳接收理论与实现； 最佳信息处理理论、方法与算法； ,信息论与编码-绪论,广义信息论： 核心问题是拓广，有三重含义： 首先是在信息含义的拓广，以语言信息为例：,仙农信息,语法信息,语义信息,语用信息,信息论与编码-绪论,其次是在描述方法上的拓广： 从定量到定性； 从客观到主观； 从概率到模糊； 从统计到单个实发。,信息论与编码-绪论,最后是用途上的拓广： 从通信领域拓广至相邻自然科学领域； 从自然科学领域拓广至社会科学领域。,信息论与编码-绪论,进入20世纪80年代以来，当人们在议论未来的

16、时候，人们的注意力又异口同声地集中到信息领域。按照国际一种流行的说法，未来将是一个高度信息化的社会。信息工业将发展成头号工业，社会上大多数的人将是在从事信息的生产、加工和流通。 这时，人们才能更正确地估价香农工作的全部含义。信息论这个曾经只在专家们中间流传的学说，将来到更广大的人群之中。香农这个名字也飞出了专家的书斋和实验室，为更多的人所熟悉和了解,信息论与编码-绪论,信息、消息、信号 消息是信息的载体，信息是由消息表达出来的 信号是消息的物理体现，或者说是消息的载体,信息论与编码-绪论,信道编码发展简史 纠错码的主要发展过程大致分以下几个阶段 50年代至60年代初，主要研究各种有效的编、译码

17、方法，奠定了线性分组码的理论基础；提出了BCH码编、译码方法以及卷积码的序列译码；给出了纠错码的基本码限； 第一个分组码是1950年发现的能纠正单个错误的Hamming码； 1954年Golay发现的Golay码以及Reed和Muller发现的RM码 Prange 在1957年发现的循环码等。 最有意义的是Bose和Ray-Chaudhuri在1960年，Hocquenghem在1959年发现的能纠多个错误的BCH码，以及Reed和Solomon在1960年发现的非二进制RS码，并认识到BCH码可以看成某个RS码的子域子码，RS码又可以看作是BCH码的特例,信息论与编码-绪论,60年代至70年

18、代初，这是纠错码发展过程中最为活跃的时期。提出了如门限译码、迭代译码、软判决译码和卷积码的Viterbi译码等有效的编译码方法；同时注意到了纠错码实用化的问题，讨论了如码重量分布、译码错误概率和不可检错误概率的计算、信道的模型化等与实用化有关的各种问题。 发现的分组码主要有1970年的Goppa码和1982年的代数几何码。 在所有这些分组码中，除了Goppa码和代数几何码中存在个别达到GV限的渐进好码外，其它码字都不是渐进的好码。分组码的译码主要采用基于代数的硬判决译码。,信息论与编码-绪论,70年代以来，纠错码在实际应用中得到了更大的发展。大规模集成电路和微机的迅速发展，为纠错码的实用打下了

19、坚实的物质基础。 70年代末、80年代初，G. Ungerboeck把编码与调制相结合提出了网格编码调制（TCM, trellis-coded modulation）技术是编码理论的又一重要里程碑。,信息论与编码-绪论,1993年C. Berrou，A. Glavieux发现的Turbo码是又一重大突破； LDPC码的进一步研究； 空时码的出现。,信息论与编码-绪论,1.3 通信系统的基本模型 详细模型,信息论与编码-绪论,常用模型,信息论与编码-绪论,简化模型,信息论与编码-绪论,信源：是产生消息(或消息序列)的源，消息通常是符号序列或时间函数。 例如在电报系统中，消息是由文字、符号、数字组

20、成的报文(符号序列)，称为离散消息；在电话系统中，消息是语声波形(时间函数)，称为连续消息。 消息取值服从一定的统计规律，故信源的数学模型是一个在信源符号集中取值的随机变量序列或随机过程。 如何由信源产生消息、消息的统计特性，是研究的重点,信息论与编码-绪论,信源编码器 将信源产生的消息变换为一个数字序列(通常为二进制数字序列)，也称基带信号。 压缩信源的冗余度，以提高传输效率。尽量减少各符号之间的相关性。 信源编码分为无失真信源编码（离散信源）和限失真信源编码（连续信源） 主要指标是编码效率，即理论上所需的码率与实际达到的码率之比。 主要作用是增加信息传输的有效性。,信息论与编码-绪论,信源

21、编码理论要回答两个问题： 对给定的信源，可能达到的最小编码速率是多少？ 如何构造实现这一速率的最优编码。 这两个问题在信息论发展的最初年代里就已获得解决。,信息论与编码-绪论,信道 信道是指传输信号的媒质或通道 架空明线、电线、射频波束、人造卫星等都是信道。 广义信道：在信息论的模型里，有时为了研究方便，可以将发送端和接收端的一部分如调制器和解调器归入信道。 信道的主要问题是传送信息的能力，即信道容量,信息论与编码-绪论,干扰源（噪声） 影响信号传输的各种因素 内部噪声（设备的热噪声，变换产生的非线性失真，等）和外噪声（外部环境的影响，有人为的和自然的） 加性噪声、乘性噪声；随机噪声、突发噪声；等 一般是将系统各部分的噪声和干扰都归入信道中考虑。根据噪声和干扰的统计特性对信道进行分类。 最简单的是离散无记忆(恒参)信道。 噪声的特性，尤其是统计特性，是研究的重点。 最常用的噪声是高斯白噪声。,信息论与编码-绪论,信道编码器 增加信息传输的可靠性 基本思想就是通过编码引进多余度以提高信息传送的可靠性。更确切地说，信道译码器利用引入的多余度，是个各符号之间满足某种约束关系，从而达