2008-应用信息论基础-张林-Chap-0-95305587

1应用信息论基础FundamentalsofAppliedInformationTheory2008年9月17日©THU2008–Allrightsreserved2008年9月17日清华大学电子系－张林教师信息„教师…姓名：张林…地址：东主楼10区407…电话：62781382…邮件：[e-mail]©THU2008–Allrightsreserved22008年9月17日…网址：~zhanglin„助教…余潇潇[e-mail]…韩峰[e-mail]课程信息„课堂讲授：48学时„平时作业…总共五～六次作业，对应章节…占总成绩的10%„期中考试…10月中下旬闭卷占总成绩的20%©THU2008–Allrightsreserved32008年9月17日…10月中下旬，闭卷，占总成绩的20%„期末考试…考试周（17或18周）中进行…闭卷，占总成绩的70%教材信息„《应用信息论基础》，清华大学出版社朱雪龙编著…经典中文书目…作为主要的教学脉络„T.M.Cover,FundamentalofInformationTheory…最为流行的英文教材，为Stanford、MIT等学校的研究生课程选用©THU2008–Allrightsreserved42008年9月17日…数学推导适中，强调概念，作为参考教材„R.G.Gallager,InformationTheoryandReliableCommunication…数学推导较为艰深…作为提高教材本课程的目的„掌握信息论的基本概念„理解用随机统计方法研究信息及其传输的实质„了解用信息理论的相关知识解决实际问题技术路径和方法„形成以信息的视角分析问题的能力©THU2008–Allrightsreserved52008年9月17日„形成以信息的视角分析问题的能力„了解信息论产生发展的过程，知其然与所以然本课程的主要内容与课时安排第〇章前言2第一章信息论的基本概念6第二章信源与信源无失真编码8第三章信道及其信道容量8第四章信道编码©THU2008–Allrightsreserved62008年9月17日第四章信道编码6第五章信息速率失真函数8第六章最大熵原理与最小鉴别信息原理4第七章多用户与网络信息论4复习22第〇章绪论2008年9月17日©THU2008–Allrightsreserved0.1信息的概念信息是什么？©THU2008–Allrightsreserved82008年9月17日信息是什么？信息是去芜存菁？©THU2008–Allrightsreserved92008年9月17日还是提取必要的特征？©THU2008–Allrightsreserved102008年9月17日符号化的表达？©THU2008–Allrightsreserved112008年9月17日中国诗词中的“意境”，“功夫在诗外”„王维：大漠孤烟直，长河落日圆。„丰子恺：人散后，一钩新月天如水©THU2008–Allrightsreserved122008年9月17日3你从中读出了什么？珠失目中，仰面朝空。零么塞脑，难辨西东。奥词巨典，横竖不通。草埋一世，喝西北风。诫我师友勿效此公©THU2008–Allrightsreserved132008年9月17日诫我师友，勿效此公。婆心苦口，善举德功。——电子系离休教授杨弃疾还是感观之后的连带信息？©THU2008–Allrightsreserved142008年9月17日信息是能量吗？是物质吗？„热力学第二定率„封闭系统的熵可以自发减少吗？„麦克斯韦妖佯谬©THU2008–Allrightsreserved152008年9月17日信息的效用：历史上的有趣占卜„施琅收复台湾之战之前的占卜…康熙二十年（公元1681年），郑经死，其子郑克塽继任王位。此时，康熙帝已彻底平定了“三藩之乱”，中央集权空前巩固，收复台湾、全国统一已成大势所趋，人心所向。据此，康熙决定以武力统一台湾，遴选精于海战的施琅为福建水师提督©THU2008–Allrightsreserved162008年9月17日选精于海战的施琅为福建水师提督。…康熙二十二年（公元1683年）6月14日，清军跨海东征。发兵前，主将施琅取来百枚“康熙通宝”铜钱，告于将士：若神灵佑护清军大捷，将有90枚字面向上，投掷后果然有95枚铜钱为字！士气大振，经过7天激战，先将澎湖攻克，全歼郑军精锐。对于信息与世界的哲学思考„拉普拉斯的宿命论观点…世间一切系统的因果关系都可以包含在确定性的微分方程之中，只要能够给定相应方程的初始条件，就可以唯一地确定这个系统在未来任何时刻的结果©THU2008–Allrightsreserved172008年9月17日…机械唯物主义、近代形而上学唯物主义对于信息与世界的哲学思考„以香农为代表的学者的观点：…事物发展变化的因果关系是复杂的，即具有必然性，又存在偶然性，因而事件的结局存在不定性。正是存在不定性，人们才需要获得信息来消除这样的不定性。…过去已经发生，不可以控制，但是可以观察；未来还没有到来，不可以观察但是可以预测©THU2008–Allrightsreserved182008年9月17日不可以观察，但是可以预测…大量关于这个题材的影视作品。“PayCheck”，“Butterfly”，“Run”，“DeJavu”4DejaVu-byD.Washington©THU2008–Allrightsreserved192008年9月17日对于信息与世界的哲学思考„量子宇宙学…霍金1981年提出…每一次选择都导致世界的分叉…存在无穷多平行宇宙，对应于不同的选择©THU2008–Allrightsreserved202008年9月17日对应于不同的选择…自洽的理论信息的定义„目前为止还没有对于信息的统一的定义„缺乏完整、明确、为世人所普遍公认的概念。„原因：对信息的本质认识还不够。„特点：从不同侧面，层次上揭示信息的特性。…语法信息形式©THU2008–Allrightsreserved212008年9月17日…语法信息：形式…语义信息：含义…语用信息：效用对信息不同层次的感性理解„广义信息…将信息的形式和内容全部包含在内的最广泛意义上的信息。…“语法＋语义＋语用”„技术述语信息…计算机所处理的海量对象，如音频和视频数据、文档资料等©THU2008–Allrightsreserved222008年9月17日…“语法＋语义”„统计信息…可以用数学公式严格定义，反映了信息表达形式在统计方面的性质…“语法”经典信息论研究的内容„针对“统计信息”进行讨论„为什么要使用统计信息？…有明确定义的科学名词，它与内容无关，而且不随信息的具体表达式的变化而变化。…独立于形式，反映了信息表达式中统计方面的性质。是统计学上的抽象概念©THU2008–Allrightsreserved232008年9月17日学上的抽象概念。…恺撒密码„熵（Entropy）∑=−=Nnnnpppf1log)(0.2信息论产生的背景„公元前1775年，希腊字母发明„公元前1400年，中国甲骨文„公元前8世纪，烽火通信（“烽火戏诸侯”）人类通信技术的发展©THU2008–Allrightsreserved242008年9月17日51952年前通信技术„19世纪初，Morse电码发明„1839年，英国开始商业运营„1844年，美国开始商业运营„1850～1866年，洲际海底电缆©THU2008–Allrightsreserved252008年9月17日CharlesWheatstoneGreatEastern号铺设跨大西洋电报线电缆的普及和电话的诞生1865年的电缆洲际海底电缆©THU2008–Allrightsreserved262008年9月17日A.Bell展示其发明的电话，18771865年电缆机房交换、复用技术的产生©THU2008–Allrightsreserved272008年9月17日近代技术的发展及其影响„1927年，NBC开播两套无线节目„1938年，广播剧“世界之战”引发大恐慌„1939年，电视广播开始„1944年，哈佛大学的第一台电子计算机诞生„1957年，苏联发射人造卫星Sputnik„1969年，ARPANet开始运营年木发信©THU2008–Allrightsreserved282008年9月17日„1977年，旅行者从木星发回信号„1981年，蜂窝电话商用（沙特阿拉伯）„1991年，WorldWideWeb发明信息论诞生的技术准备„电报(Morse,1830’s);„电话(Bell,1876);„无线电报(Marconi,1887);„调幅收音机(early1900’s);„单边带调制(Carson,1922);„电视(1925–1927);考虑字母出现频率的编码方案信息传输速率与可靠性是相互依存的两个自由度©THU2008–Allrightsreserved292008年9月17日„电视(1925–1927);„电传(1931);„调频(Armstrong,1936);„脉冲调制(PCM)(Reeves,1937–1939);„声码器(Dudley,1939);„扩频(1940’s).首个用于传输模拟信号的数字系统以降低信号还原度为代价，传输带宽可以小于信号带宽信息论诞生的理论准备„1924年，Nyquist指出，最大传输速率与可用信号数的对数成正比„Morse电码是否是最优的？„如果换成最优的码，能够获得多少增益？„最优的码如何设计？1928年Nit采样定理©THU2008–Allrightsreserved302008年9月17日„1928年，Nyquist采样定理。•H.Nyquist,“Certainfactorsaffectingtelegraphspeed,”BellSyst.Tech.J.,vol.3,pp.324–352,Apr.1924.•H.Nyquist,“Certaintopicsintelegraphtransmissiontheory,”AIEETrans.,vol.47,pp.617–644,Apr.1928.6信息论诞生的理论准备„1928年，Hartley引入了“rateofcommunication”，“inter-symbolinterference”和“capacityofasystemtotransmitinformation”的概念…Thepointofviewdevelopedisusefulinthatitprovidesareadymeansofcheckingwhetherornotclaimsmadeforthetransmissionpossibilitiesofacomplicatedsystemliewithintherangeofphysical©THU2008–Allrightsreserved312008年9月17日pygpypossibility.„Hartley意识到：为了表述”Capacity”，必须定义定量描述信息的指标…H=nlogs…n为选择的次数，s为总共可供选择的符号数目„“信息源于有限可能中的选择”R.V.L.Hartley,“Transmissionofinformation,”BellSyst.Tech.J.,vol.7,pp.535–563,July1928.对于Nyquist和Hartley工作的评价„贡献：…引入了信息量的定义…给出了信息度量的指标„局限性：…没有考虑噪声的影响©THU2008–Allrightsreserved322008年9月17日…没有考虑噪声的影响…没有考虑信源符号的随机性建立通信中数学理论时面临的主要问题„计量信号中信息„通信系统中信息传输效率„信息传输的准确性„噪声干扰©THU2008–Allrightsreser