信息论与编码课件第一章.ppt

1,开篇寄语,每一次面对新同学，我的内心总是很忐忑，因为不管你们信不信，反正我深深地相信：90后的大学生，伤不起啊！ 你们生长在一个拼爹的年代，如果你没有一个名爹，那就一定要hold住自己！上课的时候尤其要hold住自己的手机，既不要让它上QQ聊天，也不要到农场偷菜！,2,开篇寄语,不要以为老师是什么潮人，因为信息论是枯燥的，因而也非常的干燥，老师怎么可能潮得起来呢！ 中央电视台李咏主持有一档节目叫“非常6+1”，陈景润研究的哥德巴赫猜想被人称为“1+1”，其实信息论也可看作“2+3”。所以，这门课主要是要搞懂“2”和“3”！,3,Fundamentals of Information Theory,信 息 理 论 基 础,4,教师情况,教师：李红莲 副教授 博士 电子信息工程系 （2-513东） E-mail: , Mobile:5,6,授课、考试有关安排,学时数: 讲课 32学时 实验 8学时（10，14周周五9-12节?，计算中心） 上课时间和地点: 第1-4,6-16周一3、4节，1-四阶 第8周二1、2节，3-五阶,7,考试时间： 第17周左右 考试成绩计算： 作业+实验 ：30% ； 期末考试：开卷 70% ； 答疑时间： 每周三第5、6节课（13:30-15:30） 答疑地点： 2-513东,8,信息论基础的重要性,信息论是信息科学和技术的基本理论,是信息科学大厦的地基; 没有信息论的基础，从事通信与信息领域的研究和创新是不可能的事情; 总之,信息论是高层次信息技术人才必不可少的基础知识。,9,信息论基础是通信和信息领域的专业基础课程，只有学好这门课，才能学好后续课程、将来进一步从事通信和信息领域的科研和创新。 要珍惜这个良好的学习机会，认真学习，逐渐培养科研能力，树立完善的人格基础，为将来的进一步学习和科研奠定坚实的基础。,信息论基础的重要性,10,教学目标,充分理解、熟练掌握教材的内容 熟练掌握基本的信息理论概念和定理 熟练掌握通信与信息工程中基本研究对象的数学描述 通过学习和习题练习，具备一定的解决问题分析问题的能力 掌握一定的科学思想方法(用信息论的思想和观点),11,对学习者的要求,三个重要环节 课前预习 课上认真听讲 课后认真复习消化、做作业 经常进行阶段复习 掌握知识的窍诀：反复思维实践,12,其他约定,不得迟到、早退、缺课，有事请假 上课时请关闭手机（或调至振动） 作业不得用纸片信纸之类，必须使用作业本 迟交的作业及纸片做的作业恕不修改，只作记录,13,信息理论基础的内容,信息论的基本问题-信息与信道的度量 无失真信源编码定理-香农第一定理 信道编码定理-香农第二定理 限失真信源编码定理-香农第三定理,14,Shannon信息论的基本任务,1948年shannon发表了“通信的数学理论”奠定了信息论理论基础 基本任务是设计有效而可靠的通信系统 可靠是要使信源发出的消息经过传输后，尽可能准确地、不失真地再现在接收端 有效是用尽可能短的时间和尽可能少的设备来传输一定量的消息,内容安排 第一章 绪论 2学时 第二章 信源和熵 8学时 第三章 信道及其容量 6学时 第四章 离散信源的无失真编码 6学时 第五章 信道编码 4学时 第六章 限失真信源编码 4学时 复习 2学时,16,第一章 绪 论,一、信息的概念 二、信息论产生背景 三、信息论的发展简史 四、信息论的应用 五、信息论研究的内容 六、参考书目,17,在人类的历史长河中，信息传输和传播手段经历了五次变革： 第一次变革：语言的产生 第二次变革：文字的产生 第三次变革：印刷术的发明 第四次变革：电报、电话的发明 第五次变革：计算机技术与通信技术相结合，促进了网络的发展。,历史回顾: 信息传输方式的变迁,18,历史回顾: 信息传输方式的变迁,我国上古时期的“结绳记事”法，史书上有很多记载。 汉朝郑玄的周易注中记载：“古者无文字，结绳为约，事大，大结其绳，事小，小结其绳。”,19,后来，文字的出现解决了这一问题。自从造纸术和印刷术的发明，使文字成为信息记录、储存和传递的有效手段。,历史回顾: 信息传输方式的变迁,20,特别是电报、电话和电视的发明，使信息传送快速、便利，再次体现了信息加工和传输的变革。,历史回顾: 信息传输方式的变迁,21,电子计算机的迅速发展和广泛应用，尤其是个人微型计算机的普及，大大提高了人们处理加工信息、存储信息及控制管理信息的能力。,历史回顾: 信息传输方式的变迁,22,近年来，以计算机为主 体的互联网技术的兴起 和发展，以空前的威力 推动着人类经济和社会 高速发展，将人类社会 推入到高度化的信息时 代。,历史回顾: 信息传输方式的变迁,23,信息是信息论中最基本、最重要的概念，是一个既复杂又抽象的概念。 信息概念十分广泛，由于信息科学比起其他学科（如物理学、化学、数学）还很年轻，人类对信息的认识还很不够。迄今为止，信息并没有形成一个很完整的、系统的概念。 不同的研究学派对信息的本质及其定义还没有形成统一的意见和认识。,一、信息的概念,24,通俗的信息概念,信息是一种消息。 这是一种最普遍的概念，是目前社会上最流行的概念，这个概念好像使人一听就明白，但不准确。确切地说，这种概念把消息认为是信息。 信息消息，同一条消息有不同信息量。 例如: 某人收到一条消息,包含许多原来不知道的新内容信息量大 包含许多原来已知道的旧内容信息量小,25,广义的信息概念,物质、能量和信息是构成客观世界三大要素，信息是物质和能量在空间和时间中分布的不均匀程度。 信息不是物质，信息是事物的表征，是对物质存在状态和运动形式的一般描述。 信息存在于任何事物之中，有物质的地方就有信息，信息充满物质世界。 信息本身看不见、摸不着，它必须依附于一定的物质形式（如文字、声波、电磁波等）。这种运载信息的物质称为信息的载体，一切物质都有可能成为信息的载体。,26,概率信息的概念,概率信息是由美国数学家香农提出来的，故称香农信息或狭义信息。是从不确定性 (Uncertainty) 和概率测度出发定义信息的。 香农从信源具有随机不确定度出发，为信源推出一个与统计力学的熵相似的函数，称为信息熵。 信息熵是信源的信息选择不确定度的测量，但它不等同于不确定度，而是为了消除一定的不确定度，必须获得的、与此不确定度相等的信息量。,27,信息的特征,信息虽无确切定义，但是却具有两个明显的特征：广泛性与抽象性。 广泛性 客观世界充满着信息 人类离不开信息 知识、书本是有用信息的积累 抽象性 信息是组成客观世界并促进社会发展的最基本的三大要素之一。三大要素是：物质、能量与信息。三要素中物质是基础，是实体。能量是物质运动的形式，E=mc2，物质可转换成能量，而能量又是改造客观世界的主要动力。,28,信息的重要性质,存在的普遍性；有序性；相对性；可度量性；可扩充性；可存储、传输与携带性；可压缩性；可替代性；可扩散性；可共享性；时效性。 信息在信息化程度越来越高的社会中将起到越来越重要的作用，是比物质和能量更为宝贵的财富。,29,信息：它依附于物质和能量，但又不同于物质和能量。没有信息就不能更好地利用物质和能量，人类利用信息和知识改造物质，创造新物质，提高能量利用效率，发现新能量形式。信息也是客观存在的，它是人类认识、改造客观世界的主要动力，是人类认识客观世界的更高层次。就狭义而言，在通信中对信息的表达分为三个层次：信号、消息、信息。,信息的重要性质,30,信号：是信息的物理表达层，是三个层次中最具体的层次。它是一个物理量，是一个载荷信息的实体，可测量、可描述、可显示。 消息：(或称为符号)是信息的数学表达层，它虽不是一个物理量，但是可以定量地加以描述，它是具体物理信号的进一步数学抽象，可将具体物理信号抽象为两大类型： 离散(数字)消息，是一组未知量，可用随机序列来描述：U=(U1 Ul UL) 连续(模拟)消息，也是未知量，它可用随机过程来描述：U(t,),信息、消息、信号,31,信息：它是更高层次哲学上的抽象，是信号与消息的更高表达层次。三个层次中，信号最具体，信息最抽象。它们三者之间的关系是哲学上的内涵与外延的关系。 理解：信息可以认为是具体的物理信号、数学描述的消息的内涵，即信号具体载荷的内容、消息描述的含义。而信号则是抽象信息在物理层表达的外延；消息则是抽象信息在数学层表达的外延。同一信息，可以采用不同的信号形式(比如文字、语言、图象等)来载荷；同一信息，也可以采用不同的数学表达形式(比如离散或连续)来定量描述。同样，同一信号形式，比如“0”与“1”可以表达不同形式的信息，比如无与有、断与通、低与高(电平)等等。,信息、消息、信号,信息、消息、信号,信息蕴含在消息中 消息蕴含在信号中,信号中装着消息 消息中装着信息,33,什么是信息论,它是C.E.Shannon四十年代末期，以客观概率信息为研究对象，从通信的信息传输问题中总结和开拓出来的理论。主要研究的问题 ： 信源的描述，信息的定量度量、分析与计算 信道的描述，信道传输的定量度量、分析与计算。 信源、信道与通信系统之间的统计匹配，以及通信系统的优化 Shannon的三个编码定理。 信息论诞生五十多年来，至今，仍然是指导通信技术发展的理论基础，是创新通信体制的源泉 。,34,1. 信息的如何度量？ 2. 需要解决的问题： 通信系统中信息传输的效率。 信息传输的准确性问题。 噪声干扰。 频率特性。 本质为：信息传输的可靠性与有效性问题。,二. 信息论产生背景,信道,通信系统模型,消息,信号,恢复的消息,信号+干扰,通信系统模型,37,信源：产生消息的源。消息可以是文字、语言、图像等。 编码器：将信源发出的消息变换成适于信道传送的信号的设备。包含信源编码器、纠错编码器、调制器。 信道：把载荷消息的信号从发射端传到接收端的媒质或通道。狭义的实际信道有电缆、波导、光纤、无线电波传播空间。,通信系统模型,38,干扰源：系统其他各部分产生的噪声和干扰都等效成信道干扰，集中作用于信道。 译码器：编码的逆变换。它的作用是从受干扰的信号中最大限度地提取出有关信源传出消息的信息。 信宿：信息传送过程中的接收者，即接收消息的人或物。,通信系统模型,39,三.信息论发展简史,电磁理论和电子学理论对通信理论技术发展起重要的促进作用 18201830年，法拉第发现电磁感应 莫尔斯18321835建立电报系统。1876年Bell发明电话 1864麦克斯韦预言电磁波存在，1888年赫兹验证该理论 1895年马可尼发明了无线电通信 微波电子管导致微波通信系统，微波雷达系统 激光技术使通信进入光通信时代,40,信息论发展简史,1832年莫尔斯电码对shannon编码理论的启发 1885年凯尔文研究了一条电缆的极限传信速率 1922年卡逊对调幅信号的频谱结构进行研究 1924年奈奎斯特证明了信号传输速率和带宽成正比 1928年Hartley提出信息量定义为可能消息量的对数 1939年Dudley发明声码器 1940维纳将随机过程和数理统计引入通信与控制系统,41,信息论发展简史,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算法,42,信息论发展简史,1950年汉明码，1960年卷积码的概率译码，Viterbi译码，1982年Ungerboeck编码调制技术，1993年Turbo编译码技术 1959年，Shannon提出率失真函数和率失真信源编码定理 1961年，Shannon的“双路通信信道”开拓了网络信息论的研究，目前是非常活跃的研究领域。,43,语音信号压缩（G.711, GSM, Vocoder） 图象信号的压缩（JPEG, MPEG） 计算机文件压缩（compress, gzip） 模拟话路中数据传输速率的提高 降低信息传输所需的功率,四、信息论的应用,44,计算机网中数据传输可靠性的保证 计算机中的容错问题 图像信号的复原与重建 模式分类问题与树分类器的设计 其他（信息经济学、医学、生物学、管理科学等）,四、信息论的应用,45,五.信息论的研究内容,狭义信息论（经典信息论） 研究信息测度，信道容量以及信源和信道编码理论 一般信息论 研究信息传输和处理问题，除经典信息论外还包括噪声理论，信号滤波和预测，统计检测和估值理论，调制理论，信息处理理论和保密理论 广义信息论 除上述内容外，还包括自然和社会领域有关信息的内容，如模式识别，计算机翻译，心理学，遗传学，神经生理学,46,狭义信息论体系结构,Shannon信息论,压缩理论,有失真编码,无失真编码,等长编码 定理 Shannon 1948 McMillan 1953,变长编码 定理 Shannon 1948 McMillan 1956,Huffman码(1952)、Fano码 算术码(1976,1982) LZ码(1977,1978),率失真理论 Shannon Gallager Berger,压缩编码 JPEG MPEG,传输理论,信道编码定理,网络信息理论,纠错码 编码调制理论,网络最佳码,47,信息用来消除接收者某种认识上不确 定性的东西。 信息论研究信息的本质、描述和度量方法以及传输和处理的基本原理的理论。 信息科学信息科学是研究信息规律和指导信息技术开发及应用的学问。 信息技术运用信息科学为经济和社会发展而共同协作组成的各种工具和规则体系。,信息、材料、能源是现代科学的三大支柱。,有关概念,48,信息论的主要贡献是： （1）把统计信息定义为“用来消除信息接收者某种认识上的不确定性的东西”，并给出了其度量公式-熵和互信息； （2）建立了一些重要的性能界：信源输出的最大可能的信息量，满足一定失真度的要求所必须传递的最小信息量，信道上的最大可能通过能力等； （3）建立了一组重要的编码定理，从理论上指明了为达到上述性能界限应当遵循的信息处理的方法和原则。这就不仅从定性方面而且也从定量方面深刻地揭示了信息传递和处理的规律，使通信的研究从经验的阶段转变为科学。,49,六.参考书目,焦瑞莉，李红莲，冷俊敏，信息论基础教程。机械工业出版社，2008年。 周荫清，信息理论基础。北京航空航天大学出版社，2006年。 曲炜等,信息论基础及应用。清华大学出版社，2005年。 曹雪虹等，信息论与编码，清华大学出版社，2004年。 仇佩亮，信息论与编码。高等教育出版社，2003年。 朱雪龙，应用信息论基础。清华大学出版社，2004年。,50,ROBERT J.MCELIECE，信息论与编码理论。电子工业出版社，2003年。 吴伟陵，信息处理与编码。人民邮电出版社，2003年。 陈运等，信息论与编码。电子工业出版社， 2003年。 吕锋、王虹等，信息理论与编码。人民邮电出版社，2004年。 RANJAN BOSE，信息论、编码与密码学。机械工业出版社，2003年。,51,附. Shannon及其影响和贡献 1. Shannon Claude Elwood,1916年4月30日出生于美国密执安州的加洛德。 早年获得了密执安州大学的数学和电子工程学的学士学位。 1940年获得麻省理工学院博士学位。 1941年至1972年间，在贝尔实验室工作。 从1958年在麻省理工学院任教，至1978年退休。 2001年2月24日在马萨诸塞州的Medford因老年痴呆症与世长辞，享年84岁。,52,2. 贡献 奠定了大型数字计算机构建的理论基础。 1938年：继电器和开关电路的符号分析 首次用布尔代数进行开关电路分析，证明了布尔代数的逻辑运算，可以通过继电器电路来实现，给出了实现加，减，乘，除等运算的电子电路的设计方法。这篇论文成为开关电路理论的开端。 开创了信息论。 1948年：The mathematic