YN-信息论与编码理论.ppt

Thomas M.Cover.Elements of Information Thomas M.Cover.Elements of Information Theory.Theory.清华大学出版社影印版清华大学出版社影印版朱雪龙朱雪龙.应用信息论基础应用信息论基础.清华大学出版社清华大学出版社傅祖芸傅祖芸.信息论信息论-基础理论与应用基础理论与应用.电子工业出版电子工业出版社社王育民王育民.信息论与编码理论信息论与编码理论.高等教育出版社高等教育出版社.参考书参考书闭卷闭卷+课程论文课程论文平时成绩平时成绩20%+20%+论文成绩论文成绩20%+20%+考试成绩考试成绩60%60%考核方式考核方式第一章第一章 绪论绪论第一章第一章 绪论绪论什么是信息？什么是信息？信息论研究什么？信息论研究什么？编码研究什么？编码研究什么？如何研究如何研究?2个重要概念个重要概念信息是不确定性的：随机性信息是不确定性的：随机性信息需要用数字信号：信息需要用数字信号：0和和1来传输来传输2个基本理论个基本理论信源编码理论：数据压缩的临界最小值信源编码理论：数据压缩的临界最小值信道编码理论：数据传输的临界最大值信道编码理论：数据传输的临界最大值1.1 1.1 通信系统模型和信息的概念通信系统模型和信息的概念1.2 1.2 信息论研究的中心问题及发展信息论研究的中心问题及发展1.3 shannon1.3 shannon信息论的局限性信息论的局限性1.4 1.4 信息的广义性信息的广义性1.1 通信系统模型和信息的概念通信系统模型和信息的概念1、通信系统模型、通信系统模型信源信源编码器编码器信道信道译码器译码器信宿信宿干扰源干扰源通信系统的基本任务要求通信系统的基本任务要求通信系统的基本任务要求通信系统的基本任务要求可靠可靠可靠可靠:要使信源发出的消息经过传输后，尽可能准确地、要使信源发出的消息经过传输后，尽可能准确地、要使信源发出的消息经过传输后，尽可能准确地、要使信源发出的消息经过传输后，尽可能准确地、不失真或限定失真地再现在接收端不失真或限定失真地再现在接收端不失真或限定失真地再现在接收端不失真或限定失真地再现在接收端有效有效有效有效:用尽可能短的时间和尽可能少的设备来传输最大用尽可能短的时间和尽可能少的设备来传输最大用尽可能短的时间和尽可能少的设备来传输最大用尽可能短的时间和尽可能少的设备来传输最大的消息的消息的消息的消息通信系统模型进一步细分通信系统模型进一步细分信源信源信源信源编码器编码器信道信道编码器编码器调制器调制器信信道道干扰源干扰源解调器解调器信道信道译码器译码器信源信源译码器译码器信宿信宿等效离散信道等效离散信道等效离散信等效离散信源源等效信宿等效信宿信道编码器信道编码器信道译码器信道译码器2、信息的概念：信息、消息和信号、信息的概念：信息、消息和信号信息信息n一个抽象的概念，可以定量的描述。信息、物质和能一个抽象的概念，可以定量的描述。信息、物质和能量是构成一切系统的三大要素。量是构成一切系统的三大要素。消息中的有效内容。消息中的有效内容。消息消息n是信息的载体，相对具体的概念，如语言，文字，数是信息的载体，相对具体的概念，如语言，文字，数字，图像。字，图像。信号信号n表示消息的物理量，电信号的幅度，频率，相位等等。表示消息的物理量，电信号的幅度，频率，相位等等。一般在通信领域表示消息的电信号。一般在通信领域表示消息的电信号。3、香农信息的定义收信者在收到消息前不知道消息的具体内容；收信者在收到消息前不知道消息的具体内容；通信的结果是消除不确定性从而获得信息。通信的结果是消除不确定性从而获得信息。干扰源干扰源信源信源信道信道信宿信宿信息的定义信息的定义信息信息是是事物运动状态或存在方式的不确定事物运动状态或存在方式的不确定性的描述性的描述不仅仅是形式上的消息或情报不仅仅是形式上的消息或情报 ，而且包括，而且包括消息或情报所含的对事物状态或不确定性消息或情报所含的对事物状态或不确定性的描述的描述“母病愈母病愈”1 1、收报人之前不知道任何相关信息，也不、收报人之前不知道任何相关信息，也不知道有人给他发报知道有人给他发报不确定性不确定性2 2、是关于身体健康的描述、是关于身体健康的描述是动态的、是动态的、随机的随机的3 3、收到报文后，报文清楚，则不确定性消、收到报文后，报文清楚，则不确定性消除；报文不清除；报文不清有可能消除一部分不确有可能消除一部分不确定性，不确定性减少，获得一部分信息；定性，不确定性减少，获得一部分信息；或不确定性没有减少，没有获得信息。或不确定性没有减少，没有获得信息。4、香农信息的度量、香农信息的度量天气预测：晴 雪 ；中奖（1）样本空间样本空间：某试验中各种可能出现的状态的集合；或者所有消息的集合（2）概率测度概率测度：每一个可能的离散消息指定的概率（3）概率空间概率空间：一个样本空间和它的消息测度称为一个概率空间（4）自信息自信息：如果事件 ai 发生的概率p(ai),事件 ai 发生所含有的信息量，就称为自信自信息量息量，表示为 平均信息量、熵平均信息量、熵（5）互信息互信息：先验的不确定性减去尚存在的不确定性是两个随机变量相互之间独立程度的度量。先验概率:后验概率例例1.1 假定假定8名运动员参加一场比赛，设名运动员参加一场比赛，设8人的获胜人的获胜概率分布为（概率分布为（1/2，1/4，1/8，1/16，1/64，1/64，1/64，1/64）。求该场比赛的平均信息量）。求该场比赛的平均信息量。解：解：H(X)=-1/2log(1/2)-1/4log(1/4)-1/8log(1/8)-1/16log(1/16)-4*1/64log(1/64)=2比特比特 假设要把某人获胜的消息传出去，可以发送该人假设要把某人获胜的消息传出去，可以发送该人的编号；由于获胜概率不同，获胜可能大的用较短的编号；由于获胜概率不同，获胜可能大的用较短描述，可以获得描述，可以获得2比特的平均信息量。比特的平均信息量。5 Shannon信息论的优点信息论的优点ShannonShannon定定定定理理理理的的的的证证证证明明明明是是是是非非非非构构构构造造造造性性性性的的的的，而而而而且且且且也也也也不不不不够够够够严严严严格格格格，但但但但他他他他的的的的“数学直观出奇地正确数学直观出奇地正确数学直观出奇地正确数学直观出奇地正确”(A.N.Kolmogrov(A.N.Kolmogrov，1963)1963)。已已已已在在在在数数数数学学学学上上上上严严严严格格格格地地地地证证证证明明明明了了了了ShannonShannon编编编编码码码码定定定定理理理理，而而而而且且且且发发发发现现现现了了了了各各各各种种种种具具具具体体体体可可可可构构构构造造造造的的的的有有有有效效效效编编编编码码码码理理理理论论论论和和和和方方方方法法法法，可可可可以以以以实实实实现现现现ShannonShannon指指指指出的极限。出的极限。出的极限。出的极限。n n几乎无错地经由几乎无错地经由几乎无错地经由几乎无错地经由GaussianGaussian信道传信信道传信信道传信信道传信n n对于非白对于非白对于非白对于非白GassianGassian信道，信道，信道，信道，ShannonShannon的注水定理和多载波调的注水定理和多载波调的注水定理和多载波调的注水定理和多载波调制制制制(MCM)(MCM)n nCDMACDMA、MCM(COFDM)MCM(COFDM)、TCMTCM、BCMBCM、各种均衡、各种均衡、各种均衡、各种均衡、对消技术、以及信息存储编码调制技术对消技术、以及信息存储编码调制技术对消技术、以及信息存储编码调制技术对消技术、以及信息存储编码调制技术6 Shannon信息论的局限性信息论的局限性如果实际信源或信道符合所采用的概率模型如果实际信源或信道符合所采用的概率模型描述，这种方法是有效的，否则只能是近似描述，这种方法是有效的，否则只能是近似的，甚至根本无效。的，甚至根本无效。n语言的熵描述是非常困难的，它是非平稳的，语言的熵描述是非常困难的，它是非平稳的，除了确定的信息，还有模糊的信息，比如除了确定的信息，还有模糊的信息，比如“韵韵味味”，“意境意境”n不同的接收者对同一个东西得到的信息可能是不同的接收者对同一个东西得到的信息可能是不同的不同的Shannon信息论适合于能够定量描述的信息，信息论适合于能够定量描述的信息，对难于定量描述的信息则无能为力。对难于定量描述的信息则无能为力。7 信息论的广义性信息论的广义性信息论常被理解为包括更广的领域信息论常被理解为包括更广的领域n语义学语义学n语言学语言学n神经生理学神经生理学n心理学心理学n组织学组织学信息的不同属性的定义产生不同的信息论信息的不同属性的定义产生不同的信息论n模糊信息论模糊信息论n量子信息论量子信息论n生物信息论生物信息论n信息复杂度的信息理论信息复杂度的信息理论1.2 信息论研究的中心问题和发展信息论研究的中心问题和发展1 Shannon信息论的基本目的信息论的基本目的19481948年年shannonshannon发表了发表了“通信的数学理论通信的数学理论”奠定了信息论理论基础奠定了信息论理论基础基本任务是设计基本任务是设计有效有效而而可靠可靠的通信系统的通信系统保密保密性和性和认证认证性性克劳德克劳德艾尔伍德艾尔伍德香农（香农（Claude Elwood Claude Elwood ShannonShannon）美国数学家、信息论的创始人。美国数学家、信息论的创始人。19161916年年4 4月月3030日出生于美国密歇根州的日出生于美国密歇根州的PetoskeyPetoskey，20012001年年2 2月月2626日去世，享年日去世，享年8484岁。岁。19361936年毕业于密歇根大学并获得数学和电子工程学士学位年毕业于密歇根大学并获得数学和电子工程学士学位 19401940年获得麻省理工学院（年获得麻省理工学院（MITMIT）数学博士学位和电子工程硕士学位）数学博士学位和电子工程硕士学位 19411941年他加入贝尔实验室，工作到年他加入贝尔实验室，工作到19721972年。年。19561956年他成为麻省理工学院（年他成为麻省理工学院（MITMIT）客座教授）客座教授 19581958年成为终生教授，年成为终生教授，19781978年成为名誉教授。年成为名誉教授。香农的学术研究香农的学术研究u 香农于香农于19401940年在普林斯顿高级研究所（年在普林斯顿高级研究所（The Institute The Institute for Advanced Study at Princetonfor Advanced Study at Princeton）期间开始思考信息）期间开始思考信息论与有效通信系统的问题。经过论与有效通信系统的问题。经过8 8年的努力，香农在年的努力，香农在19481948年年6 6月和月和1010月在月在贝尔系统技术杂志贝尔系统技术杂志（Bell System Bell System Technical JournalTechnical Journal）上连载发表了他影像深远的论文）上连载发表了他影像深远的论文通讯的数学原理通讯的数学原理。19491949年，香农又在该杂志上发表了年，香农又在该杂志上发表了另一著名论文另一著名论文噪声下的通信噪声下的通信。u 在这两篇论文中，香农阐明了通信的基本问题，给出在这两篇论文中，香农阐明了通信的基本问题，给出了通信系统的模型，提出了信息量的数学表达式，并解决了通信系统的模型，提出了信息量的数学表达式，并解决了信道容量、信源统计特性、信源编码、信道编码等一系了信道容量、信源统计特性、信源编码、信道编码等一系列基本技术问题。两篇论文成为了信息论的奠基性著作。列基本技术问题。两篇论文成为了信息论的奠基性著作。他的工作被称为二十世纪的伟大创造他的工作被称为二十世纪的伟大创造(intellectual(intellectual achievements)achievements)之一。之一。克劳德克劳德艾尔伍德艾尔伍德香农（香农（Claude Elwood Claude Elwood ShannonShannon）信息论在领域内的基本作用信息论在领域内的基本作用2 信息论的研究内容信息论的研究内容狭义信息论（经典信息论）狭义信息论（经典信息论）n研究信息测度，信道容量以及信源和信道编码理论研究信息测度，信道容量以及信源和信道编码理论 香农基本理论香农基本理论 P11 图图1.5一般信息论一般信息论n研究信息传输和处理问题，除经典信息论外还包括噪研究信息传输和处理问题，除经典信息论外还包括噪声理论，信号滤波和预测，统计检测和估值理论，调声理论，信号滤波和预测，统计检测和估值理论，调制理论，信息处理理论和保密理论制理论，信息处理理论和保密理论广义信息论广义信息论n除上述内容外，还包括自然和社会领域有关信息的内除上述内容外，还包括自然和社会领域有关信息的内容，如模式识别，计算机翻译，心理学，遗传学，神容，如模式识别，计算机翻译，心理学，遗传学，神经生理学经生理学Shannon理论Shannon定理的证明是非构造性的，而且也不够严格，但定理的证明是非构造性的，而且也不够严格，但他的他的“数学直观出奇地正确数学直观出奇地正确”(A.N.Kolmogrov，1963)。已在数学上严格地证明了已在数学上严格地证明了Shannon编码定理，而且发现了编码定理，而且发现了各种具体可构造的有效编码理论和方法，可以实现各种具体可构造的有效编码理论和方法，可以实现Shannon指出的极限。指出的极限。n几乎无错地经由几乎无错地经由Gaussian信道传信信道传信n对于非白对于非白Gassian信道，信道，Shannon的注水定理和多载波调制的注水定理和多载波调制(MCM)nCDMA、MCM(COFDM)、TCM、BCM、各种均衡、对消技术、各种均衡、对消技术、以及信息存储编码调制技术以及信息存储编码调制技术消息伴随着可以量化的信息消息伴随着可以量化的信息消息伴随着可以量化的信息消息伴随着可以量化的信息熵、平均互信息熵、平均互信息熵、平均互信息熵、平均互信息信源发出的消息有冗余度，因此可进行信源编码，信源发出的消息有冗余度，因此可进行信源编码，信源发出的消息有冗余度，因此可进行信源编码，信源发出的消息有冗余度，因此可进行信源编码，熵是无失真信源编码的最低极限熵是无失真信源编码的最低极限熵是无失真信源编码的最低极限熵是无失真信源编码的最低极限噪声使信道可靠传输能力受限，提出信道可靠传噪声使信道可靠传输能力受限，提出信道可靠传噪声使信道可靠传输能力受限，提出信道可靠传噪声使信道可靠传输能力受限，提出信道可靠传输能力输能力输能力输能力信道容限信道容限信道容限信道容限为可靠通信，通过增加冗余进行信道纠错编码，为可靠通信，通过增加冗余进行信道纠错编码，为可靠通信，通过增加冗余进行信道纠错编码，为可靠通信，通过增加冗余进行信道纠错编码，信道容限是错误足够小的信道编码的临界上限信道容限是错误足够小的信道编码的临界上限信道容限是错误足够小的信道编码的临界上限信道容限是错误足够小的信道编码的临界上限干扰源干扰源信源信源信道信道信宿信宿1.3信息论几个方面的主要进展信息论几个方面的主要进展信源编码与数据压缩信源编码与数据压缩 信道编码与差错控制技术信道编码与差错控制技术多用户信息论与网络通信多用户信息论与网络通信 多媒体与信息论多媒体与信息论 信息论与密码学和数据安全信息论与密码学和数据安全信息论与概率统计信息论与概率统计信息论与经济学信息论与经济学信息论与计算复杂性信息论与计算复杂性信息论与系统、控制、信号检测和处理信息论与系统、控制、信号检测和处理量子信息论量子信息论Shannon的其它重要贡献的其它重要贡献1信源编码与数据压缩信源编码与数据压缩-关键理论进展关键理论进展的十个里程碑的十个里程碑Kieffer 1993Kieffer 19931.无扰信源编码的诞生无扰信源编码的诞生(1948,C.E.Shannon)。2.Huffman算法的发现算法的发现(1952,D.A.Huffman)。3.建立建立Shannon-McMillan定理定理(1953,B.McMillan)。4.发现发现Lloyd算法算法(1957,S.P.Lloyd,1982年发表年发表,)。5.率失真理论系统化率失真理论系统化(1959,C.E.Shannon,)。6.Kolmogorov Complexity概念诞生概念诞生(1964,A.N.Kolmogorov,)。7.通用信源编码理论系统化通用信源编码理论系统化(1973,L.D.Davission)。8.多端信源编码理论诞生多端信源编码理论诞生(1973,D.Slepian和和J.K.Wolf)。9.第一个实际的算术编码方案第一个实际的算术编码方案(1976,J.Rissannen和和R.Pasco 1976 博士论文博士论文)。10.发现发现Lempel-Ziv码码(1977,J.Ziv和和A.Lempel)。信道编码与差错控制技术信道编码与差错控制技术 1Shannon信道编码定理和信道编码定理和Shannon极限。极限。Shannon编码信道定理编码信道定理:RC 不存在有编码方法实现满足误码率要求的速率为不存在有编码方法实现满足误码率要求的速率为R的的传信。传信。Shannon 证明码长证明码长N大时，随机选择的码以很高概率为好大时，随机选择的码以很高概率为好码。码。问题：问题：Shannon的证明是非构造性，如何构造好码实现定的证明是非构造性，如何构造好码实现定理目标理目标?实现实现ML译码的复杂性随译码的复杂性随N呈指数增长。呈指数增长。3多用户信息论与网络通信多用户信息论与网络通信(1)理论基础。两路通信系统理论基础。两路通信系统(Shannon 1961)。(2)理论进展。理论进展。Cover,Schalkwijk,Van.der Meulen,Alswede,Slepian,Wolf,Wyner Liao(Universty of Hawaii),Han等。等。(3)技术成就。技术成就。nCDMA(Virerbi,Qaulecom)的技术问题：联合检测和译的技术问题：联合检测和译码、均衡、干扰抵消、速率分拆码、均衡、干扰抵消、速率分拆(rate splitting)、功率、功率检测控制等检测控制等(Verdu,Shamai and Rimoldi)。nSTC(Space time code)，源于信息论考虑。，源于信息论考虑。n线性网络编码线性网络编码n合作编码技术合作编码技术