信息论与编码基础教学课件

信息论与编码基础教学课件第一页，共五十九页，编辑于2023年，星期日信息论与编码基础绪论教学计划内容课时第一章：绪论4第二章：离散信源4第三章：离散信道8第四章：信源压缩编码基础14第五章：信道编码基本原理4第六章：线性分组码14习题讲解与复习2第二页，共五十九页，编辑于2023年，星期日唐朝京、雷菁，《信息论与编码基础》，电子工业出版社RobertJ.McEliece著，《THETHEORYOFINFORMATIONANDCODING》(SECONDEDITION)，电子工业出版社王育民等编著，《信息论与编码理论》，高等教育出版社傅祖芸，《信息论—基础理论与应用》，电子工业出版社姜丹，《信息论与编码》，中国科学技术大学出版社沈连丰，《信息论与编码》，科学出版社仇佩亮，《信息论与编码》，高等教育出版社田宝玉，《工程信息论》，北京邮电大学出版社教材及参考书信息论与编码基础绪论第三页，共五十九页，编辑于2023年，星期日信息论与编码基础绪论课堂:（基本概念、方法，课堂讨论）课后习题（习题和综合拓展题、阅读资料）实验大作业（关键技术的设计与实现）注意事项军网网络课程平台：四院→本科生→信息论与编码基础Email：huangying@gfkd.mtn(军网),inform_huang@(民网)Phone：75707(办公室)、62856(手机)交流方式第四页，共五十九页，编辑于2023年，星期日Withoutmaterialsnothingexists.Withoutenergynothinghappens.Withoutinformationnothingmakessense.欧廷格（美国）信息论与编码基础绪论第五页，共五十九页，编辑于2023年，星期日一、信息概念三、信息论研究的基本问题及内容二、信息论的诞生四、编码技术的发展五、信息论与其它学科的交叉发展信息论与编码基础绪论第六页，共五十九页，编辑于2023年，星期日一、信息概念三、信息论研究的基本问题及内容二、信息论的诞生五、信息论与其它学科的交叉发展四、编码技术的发展信息论与编码基础绪论第七页，共五十九页，编辑于2023年，星期日“梦断美人沉信息，目穿长路依楼台”南唐李中《暮春怀故人》“欲传春信息，不怕雪埋藏。”宋陈亮《梅花》信息论与编码基础绪论第八页，共五十九页，编辑于2023年，星期日信息是谈论的事情、新闻和知识.《英国牛津字典》信息是在观察研究过程中获得的数据情报、新闻和知识.信息是所观察事物的知识.《韦氏字典》《日本广辞苑》信息论与编码基础绪论第九页，共五十九页，编辑于2023年，星期日概念区分知识信息信息情报信息消息信息论与编码基础绪论第十页，共五十九页，编辑于2023年，星期日信息论与编码基础绪论消息用文字、符号、数据、语言、音符、图片、图像等能够被人们感官所感知的形式，把客观物质运动和主观思维活动的状态表达出来，就称为消息。

清明节细雨纷飞。元宵节天气晴朗。信息是事物运动状态或存在方式的不确定性的描述。

通信系统模型信号把消息变换成适合信道传输的物理量，这种物理量就称为信号。

消息是信息的载体，信号是消息的运载工具。是事物运动状态或存在方式的不确定性的描述。

第十一页，共五十九页，编辑于2023年，星期日信息的特征信息是事物运动状态或存在方式的不确定性的描述。1）未知性或不确定性信息的最基本属性，否则就不是信息。2）由不知到知，等效为不确定性集合元素的减少可以基于集合论和概率论来描述信息的传输。3）可以度量这是信息理论的基础，使得信息可以比较大小、价值等。4）可以产生、消失，可以被携带、存储、处理信息既有物质的某些属性，又不同于物质。5）可以产生动作信息既有能量的某些属性，又不同于能量。信息论与编码基础绪论第十二页，共五十九页，编辑于2023年，星期日例子1、2021年9月11日上午9时，一颗小行星将和地球相撞。2、2022年7月11日上午9时，将发生日食。根据你对信息的理解，谈谈你的看法。信息论与编码基础绪论第十三页，共五十九页，编辑于2023年，星期日一、信息概念三、信息论研究的基本问题及内容二、信息论的诞生五、信息论与其它学科的交叉发展四、编码技术的发展信息论与编码基础绪论第十四页，共五十九页，编辑于2023年，星期日1924年H.Nyguist“影响电报速率的一些因素”1832年F.B.Morse电报系统中的高效编码1885年L.Kelvin电缆极限传信率问题如果以一个确定的速度来传输电报信号，就需要一定的带宽。证明了信号传输速率与信道带宽成正比。1928年R.V.Hartley“信息的传输”信息量等于可能消息数的对数。其缺点是没有统计特性的概念1936年E.H.Armstrong调频实用化提出增加信号带宽可以使抑制噪声干扰的能力增强，给出调制指数大的调频方式，出现调频通信装置1939年H.Dudley声码器通信所需要的带宽至少应与所传送的消息的带宽相同消息是一个确定性的过程信息论与编码基础绪论第十五页，共五十九页，编辑于2023年，星期日20世纪40年代初“平稳时间序列的外推，内插与平滑及其工程应用“引入随机过程和数理统计的观点揭示了信息传输和处理过程的统计本质信息论与编码基础绪论第十六页，共五十九页，编辑于2023年，星期日香农（Claudee.Shannon）1948年，贝尔系统技术杂志《TheMathematicalTheoryofCommunication》《CommunicationinthePresenceofNoise》信息论与编码基础绪论第十七页，共五十九页，编辑于2023年，星期日Born:April30,1916Petoskey,MichiganUnitedStatesDied:February24,2001(aged84)Medford,Massachusetts,UnitedStatesResidence:UnitedStatesNationality:American信息论与编码基础绪论第十八页，共五十九页，编辑于2023年，星期日Fields:ElectronicengineerandmathematicianAlmamater:MITUniversityofMichiganInstitutions:BellLaboratoriesMassachusettsInstituteofTechnologyInstituteforAdvancedStudy

信息论与编码基础绪论第十九页，共五十九页，编辑于2023年，星期日信息论与编码基础绪论第二十页，共五十九页，编辑于2023年，星期日Knownfor:Shannon-FanocodingShannon-HartleylawNyquist-ShannonsamplingtheoremNoisychannelcodingtheoremShannonswitchinggameShannonnumberShannon’ssourcecodingtheoremShannon’sexpansionShannon-WeavermodelofcommunicationNotableawards:AlfredNoblePrizeIEEEMedalofHonor信息论与编码基础绪论第二十一页，共五十九页，编辑于2023年，星期日一、信息概念三、信息论研究的基本问题及内容二、信息论的诞生五、信息论与其它学科的交叉发展四、编码技术的发展信息论与编码基础绪论第二十二页，共五十九页，编辑于2023年，星期日1、信息论研究的基本问题2、信息论研究的内容信息论与编码基础绪论第二十三页，共五十九页，编辑于2023年，星期日信息论研究的基本问题达到不失真信源压缩编码的极限（最低）编码速率是多少？你的爷爷生病了，病得很重，希望你能回来一趟，看望他老人家。爷病重，速归极限速率=该信源的信息熵信道的信息传输速率与错误概率之间矛盾的是否可解决？信息传输速率＜信道容量，错误概率可以任意小信息论与编码基础绪论信源编码信道编码第二十四页，共五十九页，编辑于2023年，星期日2、信息论研究的内容信息论狭义信息论一般信息论广义信息论Shannon信息论：在信息可度量的基础上，研究如何有效、可靠地传输信息Shannon信息论Wiener微弱信号检测理论噪声理论、信号滤波与预测、统计检测和估计理论调制理论、信号处理与信号设计理论心理学、遗传学、神经生理学、语言学、社会学信息论与编码基础绪论第二十五页，共五十九页，编辑于2023年，星期日信息传递信息处理—再生信息传递信息获取信息施用外部世界问题／环境信息运动过程语义信息语法信息语用信息全信息理论信息论与编码基础绪论第二十六页，共五十九页，编辑于2023年，星期日思考题一位朋友不赞同“消息中未知的成分才算是信息”的说法他举例说：我多遍地欣赏梅兰芳大师的同一段表演，百看不厌，大师正在唱的、正在表演的使我愉快，将要唱的和表演的我都知道，照这种说法电视里没给我任何信息，怎么能让我接收呢？请从信息论的角度对此做出解释。第二十七页，共五十九页，编辑于2023年，星期日信息论与编码基础绪论一、信息概念三、信息论研究的基本问题及内容二、信息论的诞生五、信息论与其它学科的交叉发展四、编码技术的发展第二十八页，共五十九页，编辑于2023年，星期日信息论与编码基础绪论1、信源压缩编码的发展1948年Shannon香农编码1952年Fano费诺编码1952年Huffman霍夫曼编码证明其最佳性1956年B.McMillanCraft不等式证明唯一可译变长码无失真信源编码第二十九页，共五十九页，编辑于2023年，星期日信息论与编码基础绪论1、信源压缩编码的发展1968年P.Elias提出算术编码的初步思路发展了香农-费诺码1976年J.Rissanen给出和发展算术编码1982年J.Rissanen将算术编码系统化G.G.Langdon1977年Ziv&Lempel提出通用信源编码(LZ码)Ziv证明此算法可达到信源的熵值1984年T.A.Welch改进LZW码1990年T.C.Bell改进LZ算法与实际应用有关的信源编码PeterEliasLempelZiv第三十页，共五十九页，编辑于2023年，星期日信息论与编码基础绪论1、信源压缩编码的发展1959“保真度准则下的离散信源编码定理”率失真信源编码理论是信源编码的核心问题，是频带压缩、图像和多媒体等数据压缩的理论基础。数据压缩理论与技术第三十一页，共五十九页，编辑于2023年，星期日信息论与编码基础绪论DataCompressionmethodsLosslessEntropyencodingHuffman,Arithmetic,Golomb,Universal(Elias.Fibonacci)DictionaryRLE,LZFamily(LZ77/78,LZW,LZT…..)AudioAudiocodespartsLPC,CELP,ACELP,A-law,u-law,MDCT,FouriertransformOthersSub-bandcoding,SpeechcompressionImageMethodsRLE,DPCM,Wavelet,EZW,SPIHT,DCT,KLTOthersBitrate,Testimages,PSNRqualitymeasure,QuantizationVideoVideocodecpartsMotioncompensation,DCT,QuantizationOthersVideocodecs,Ratedistortiontheory第三十二页，共五十九页，编辑于2023年，星期日信息论与编码基础绪论2、信道纠错编码的发展20世纪50年代~60年代初从无到有的迅速发展年代主要研究各种有效的编、译码方法，奠定了线性分组码的理论基础。HammingdescribesHammingcodes1954ReedandMullerbothpresentRMcodes1957Prangeintroducescycliccodes代数编码理论1955Eliasintroducesconvolutionalcodes

1959A.Hocquenghemand…1960BoseandRay-ChaudhuridescribeBCHcodes

Reed&SolomonproduceeponymouscodesPetersonprovidesasolutiontoBCHdecodingPetersonproduceshisbook,laterextendedandrevisedbyPetersonandWeldomReed第三十三页，共五十九页，编辑于2023年，星期日20世纪60年代~70年代初最为活跃的发展时期不仅提出了许多有效的编译码方法，还注意到纠错码的实用化。与此同时，以代数方法特别以有限域理论为基础的线性分组码理论日趋成熟。GallagerintroducesLDPCcodes信息论与编码基础绪论1967BerlekampintroducesafastalgorithmforBCH/Reed-Solomondecoding1971ViterbiintroducesthealgorithmforMLdecodingofconvolutionalcodes维特比译码1972TheBCJRalgorithmisdescribedintheopenliterature1973ForneyelucidatestheViterbialgorithm2、信道纠错编码的发展第三十四页，共五十九页，编辑于2023年，星期日20世纪70年代初~80年代极其重要的发展时期在理论上以戈帕(Goppa)为首的一批学者，构造了一类Goppa码，其中一类子码能达到香农限。大规模集成电路和微机的迅速发展，为纠错编码的实用打下坚实的物质基础。1977VoyagerdeepspacemissionusesaconcatenatedRS/convolutionalcode信息论与编码基础绪论1980SonyandPhillipsstandardizethecompactdisc,IncludingashortenedReed-Solomoncode1981Goppaintroducesalgebraic-geometrycodes1982Ungerboeckdescribestrellis-codedmodulation198414,400BPSTCMmodemcommerciallyavailable198519,200BPSTCMmodemcommerciallyavailable2、信道纠错编码的发展第三十五页，共五十九页，编辑于2023年，星期日级联码信息论与编码基础绪论第三十六页，共五十九页，编辑于2023年，星期日信息论与编码基础绪论20世纪90年代初~码的性能接近香农限。Berrou,Glavieux,andThitimajshimaannounce

turbocodes1995MacKayresuscitatesLDPCcodes1998Alamoutidescribesaspace-timecode2000AjiandMcEliecesynthesizeseveraldecodingalgorithmsusingmessagepassingideas年份½码率BER<10-51948Shannon0dB1967(255,125)BCH5.4dB1977卷积码4.5dB1993Turbo码0.7dB2001LDPC码0.0045dB2、信道纠错编码的发展第三十七页，共五十九页，编辑于2023年，星期日Turbo码与LDPC码性能比较第三十八页，共五十九页，编辑于2023年，星期日信息论与编码基础绪论Turbo码第三十九页，共五十九页，编辑于2023年，星期日信息论与编码基础绪论Turbo码第四十页，共五十九页，编辑于2023年，星期日信息论与编码基础绪论Turbo码迭代第四十一页，共五十九页，编辑于2023年，星期日信息论与编码基础绪论一、信息概念三、信息论研究的基本问题及内容二、信息论的诞生五、信息论与其它学科的交叉发展四、编码技术的发展第四十二页，共五十九页，编辑于2023年，星期日第1阶段：1949年以前。

第2阶段：从1949年到1975年。标志：1949年Shannon发表的《保密系统的通信理论》一文。用信息论的观点对信息保密问题进行了全面的阐述。宣告了科学的密码学时代的到来。第3阶段：1976年至今。标志：1976年Diffie和Hellman发表了《密码学新方向》一文。信息论与编码基础绪论1、密码学第1阶段：1949年以前。

第2阶段：从1949年到1975年。标志：1949年Shannon发表的《保密系统的通信理论》一文。用信息论的观点对信息保密问题进行了全面的阐述。宣告了科学的密码学时代的到来。第3阶段：1976年至今。标志：1976年Diffie和Hellman发表了《密码学新方向》一文。第四十三页，共五十九页，编辑于2023年，星期日信息论与编码基础绪论1、密码学明文密文密钥目的：使窃听者即使在完全准确地收到了接收信号的情况下也无法恢复出原始消息。第四十四页，共五十九页，编辑于2023年，星期日无条件安全或完善保密性（unconditionallysecure）：不论提供的密文有多少，密文中所包含的信息都不足以唯一地确定其对应的明文；具有无限计算资源（诸如时间、空间、资金和设备等）的密码分析者也无法破译某个密码系统。信息论与编码基础绪论1、密码学密码系统安全性问题第四十五页，共五十九页，编辑于2023年，星期日一个保密系统（P，C，K，E，D）其中，P为明文集合，C为密文集合，K为密钥集合，E为加密算法，D为解密算法信息论与编码基础绪论1、密码学从信息角度讨论如果H(P)=H(P|C)则该系统就称为完善的无条件保密系统。完善保密系统存在的必要条件是

H(P)≤H(K)可见，要构造一个完善保密系统，其密钥量的对数（密钥空间为均匀分布的条件下）必须不小于明文集的熵。保密系统的密钥量越小，其密文中含有的关于明文的信息量就越大。第四十六页，共五十九页，编辑于2023年，星期日信息论与编码基础绪论2、金融工程中的信息论问题游戏假设有一种可以不断重复的投资或打赌，其收益由掷硬币确定，硬币两面出现的可能性相同；出A面你投一亏一，出B面你投一赚二；假设你开始只有100元，输了没法再借。你会如何投资？第四十七页，共五十九页，编辑于2023年，星期日信息论与编码基础绪论2、金融工程中的信息论问题第四十八页，共五十九页，编辑于2023年，星期日信息论与编码基础绪论2、金融工程中的信息论问题第四十九页，共五十九页，编辑于2023年，星期日信息论与编码基础绪论2、金融工程中的信息论问题第五十页，共五十九页，编辑于2023年，星期日信息论与编码基础绪论2、金融工程中的信息论问题鸡蛋和篮子问题假设用两个足够大的篮子贩运鸡蛋，运到目的地可赢利200%(增值为原来的3倍)，每个篮子在路上被打翻从而损失100%的概率是0.5，两个篮子是否被打翻是相互无关的，每个篮子各装价值多少资金的鸡蛋，可使多次贩运后，资金平均增值最快?第五十一页，共五十九页，编辑于2023年，星期日实验序号掷币结果张大胆各下50％李糊涂各下25％你各下23％王保守各下12.5％

0

100100100100

1A,B150125123112.5

2A,A062.566.4284.38

3B,A078.1381.797.46

4B,B0156.26156.86155.5

5B,A0195.32192.94174.94

6B,B0390.64370.44262.41

7A,B0488.3455.64295.21

8A,A0244.15246.05221.4

......0.........

16A,A0596.09605.41490.