YN第1章 信息论与编码理论.ppt

信息论与编码信息论与编码通信学院通信学院: :应娜应娜 1377756382813777563828 yingna@yingna@•Thomas M. Cover.Elements of Information Theory. 清华大学出版社影印版 •朱雪龙. 应用信息论基础. 清华大学出版社 •傅祖芸. 信息论-基础理论与应用.电子工业出版 社 •王育民.信息论与编码理论. 高等教育出版社.参考书•闭卷+课程论文 •平时成绩20%+论文成绩20%+考试成绩60%考核方式考核方式第一章 绪论第一章 绪论•什么是信息？ •信息论研究什么？ •编码研究什么？ •如何研究?2 2个重要概念个重要概念•信息是不确定性的：随机性•信息需要用数字信号：0和1来传输2 2个基本理论个基本理论•信源编码理论：数据压缩的临界最小值•信道编码理论：数据传输的临界最大值•1.1 通信系统模型和信息的概念 •1.2 信息论研究的中心问题及发展 •1.3 shannon信息论的局限性 •1.4 信息的广义性1.1 通信系统模型和信息的概念1、通信系统模型信源编码器信道译码器信宿干扰源通信系统的基本任务要求通信系统的基本任务要求 可靠可靠: : 要使信源发出的消息经过传输后，尽可能准确地要使信源发出的消息经过传输后，尽可能准确地 、不失真或限定失真地再现在接收端、不失真或限定失真地再现在接收端 有效有效: : 用尽可能短的时间和尽可能少的设备来传输最大用尽可能短的时间和尽可能少的设备来传输最大 的消息的消息通信系统模型进一步细分信源信源 编码器信道 编码器调制器信 道干扰源解调器信道 译码器信源 译码器信宿等效离散信道等效离散信 源等效信宿信道编码器信道译码器2、信息的概念：信息、消息和信号•信息n一个抽象的概念，可以定量的描述。

信息、物质和能 量是构成一切系统的三大要素 消息中的有效内容 •消息n是信息的载体，相对具体的概念，如语言，文字，数 字，图像 •信号n表示消息的物理量，电信号的幅度，频率，相位等等 一般在通信领域表示消息的电信号3、香农信息的定义收信者在收到消息前不知道消息的具体内容收信者在收到消息前不知道消息的具体内容 ；； 通信的结果是消除不确定性从而获得信息通信的结果是消除不确定性从而获得信息干扰源信源信道信宿信息的定义•信息是事物运动状态或存在方式的不确定 性的描述•不仅仅是形式上的消息或情报 ，而且包括 消息或情报所含的对事物状态或不确定性 的描述•“母病愈” •1、收报人之前不知道任何相关信息，也不 知道有人给他发报——不确定性 •2、是关于身体健康的描述——是动态的、 随机的 •3、收到报文后，报文清楚，则不确定性消 除；报文不清——有可能消除一部分不确 定性，不确定性减少，获得一部分信息； 或不确定性没有减少，没有获得信息4 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 Shannon5 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信息论的基本目的•1948年shannon发表了“通信的数学理论”奠 定了信息论理论基础 •基本任务是设计有效而可靠的通信系统 •保密性和认证性克劳德·艾尔伍德·香农（Claude Elwood Shannon ）美国数学家、信息论的创始人。

1916年4月30日出生于美国密歇根州的Petoskey，2001年2月26日去世，享年84岁1936年毕业于密歇根大学并获得数学和电子工程学士学位1940年获得麻省理工学院（MIT）数学博士学位和电子工程硕士学位1941年他加入贝尔实验室，工作到1972年1956年他成为麻省理工学院（MIT）客座教授1958年成为终生教授，1978年成为名誉教授香农的学术研究u 香农于1940年在普林斯顿高级研究所（The Institute for Advanced Study at Princeton）期间开始思考信息 论与有效通信系统的问题经过8年的努力，香农在1948 年6月和10月在《贝尔系统技术杂志》（Bell System Technical Journal）上连载发表了他影像深远的论文《 通讯的数学原理》1949年，香农又在该杂志上发表了另 一著名论文《噪声下的通信》 u 在这两篇论文中，香农阐明了通信的基本问题，给出 了通信系统的模型，提出了信息量的数学表达式，并解决 了信道容量、信源统计特性、信源编码、信道编码等一系 列基本技术问题两篇论文成为了信息论的奠基性著作 他的工作被称为二十世纪的伟大创造(intellectual achievements)之一。

克劳德·艾尔伍德·香农（Claude Elwood Shannon ）信息论在领域内的基本作用信息论在领域内的基本作用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 1993]1.无扰信源编码的诞生(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)信道编码与差错控制技术1．Shannon信道编码定理和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)的技术问题：联合检测和译 码、均衡、干扰抵消、速率分拆(。