2010年信息论讲义1.ppt.ppt

信息论 2011年9月卞静 教材 1 信息论 基础理论与应用 傅祖芸 电子工业出版社2 基础信息论 戴明远 同济大学出版社 前言 什么是信息 information 什么是信息论 informationtheory informatics 什么是信息科学 informationscience 前言 当今的时代是一个信息的时代 信息处理技术的不断进步极大的影响了我们的生活 使我们的生活质量得到很大提高 获取 传递 处理 再生 控制 利用 信息 前言 前言 信息论以信息为研究对象以揭示信息的本质特性和规律为基础以应用概率论 随机过程和数理统计等为方法研究信息的存储 传输 处理 控制和利用目的 提高信息系统的可靠性 有效性 安全性和经济性 使信息系统最优化 信息 前言 1948年c e shannon发表了他的划时代文章 通信的数学理论 提出通信系统的模型 用概率和统计观点描述信源输出 信道干扰和信号的接收 给出了信道容量的定义 并明确地指出了实现有效而可靠通信的必由之路是数字化和编码 它宣告了一门崭新的学科 信息论的诞生 成为通信领域技术革命的思想或理论基础 1946年的计算机和1947年晶体管的诞生和相应技术的发展 是这一革命的物理或物质基础 前言 今天 通信 计算机和半导体技术的发展已将人类社会推进到一个崭新的信息时代 2c 七 八十年代完成了通信与计算机的结合 c c 3c internet出现 九十年代开始通信 计算机和消费电子 communications computers consumerelectronics 三结合 cyberspace 信息高速公路或全球信息基础设施 gii 的提出和建设 构成了人类生存的信息环境 即信息空间 cyberspace 这个虚拟空间的形成和发展将人类社会推进到一个新的发展阶段 即信息化社会阶段 前言 21世纪 高度信息化时代 领域 移动通信 互联网通信 多媒体技术 计算机技术 空间技术 广播电视技术生命科学技术 经济 前言 为表彰shannon的伟大功绩 ieeeinformationsociety的25名成员于2000年在其家乡michigan举行了shannon塑像的落成典礼 shannon于2001年辞世 他所留给人类的思想会永远留在人类的脑海中 前言 1948年 通信的数学理论 shannon 信息论学科成立 信息理论 通信 信息技术 计算机 信息科学 前言 信息论的奠基人克劳德 香农 claudeelwoodshannon 1916 2001 工作于贝尔实验室和mit 麻省理工学院 两大贡献 信息理论 信息熵的概念 符号逻辑和开关理论 经典信息论 以通信理论为核心 前言 香农信息理论 香农极限 无失真通信的传输速率极限数据压缩原理 无失真和限失真信源编码理论纠错编码理论 信道编码理论 课程概述 本课程将介绍信息科学的基础理论和基本方法 课程将基于一个通讯系统的抽象数学模型进行展开 课程的数学基础为概率论 整个课程可分为基础理论和编码理论两部分组成 第一章绪论 第一节信息的概念 第二节信息论研究的对象 目的和内容 第三节信息论的发展简史与现状 第一节信息的概念 信息的一般概念 1 信息是一个古老而现代的话题古老 人类很早就有意识地传递信息 现代 直到现在对信息也没有一个公认的定义 人类社会的生存和发展 每时每刻都离不开接收信息 传递信息 处理信息和利用信息 第一节信息的概念 信息的一般概念 结绳记事 烽火告警 语言文字 电报电话 电报电话电视 电子计算机 互联网 信息时代 花朵开放时的色彩是一种信息 它可以引来昆虫为其授粉 视觉成熟的水果会产生香味 诱来动物 动物食后为其传播种子 果香也是一种信息 嗅觉药有苦味 让人难以吞咽 药味是一种信息 味觉听老师讲课可以得到许多知识 知识也是信息 听觉 信息是事物之间的差异 信息是事物联系的普遍形式 信息是物质和能量在时间和空间中分布的不均匀性 信息是作用于人类感觉器官的东西 数学家认为 信息是使概率分布发生改变的东西 哲学家认为 信息是物质成分的意识成分按完全特殊的方式融合起来的产物 2 信息究竟是什么 信息的多样性客观事物多种多样 五花八门 事物的状态和变化多姿多彩 变幻无穷 属性不同就出现了不同的信息 需要给出不同的信息定义 从而可创建不同的信息理论 信息的不确定性引出概率信息和shannon信息论 信息的模糊性引出模糊信息和模糊信息论 信息的量子属性引出量子信息和量子信息论 信息的复杂性引出信息复杂度和复杂度的信息理论 信息的感知属性引出感知信息和感知的信息理论 信息的美学属性引出美学信息和美学的信息理论 第一节信息的概念 信息的广义概念从哲学的角度上讲 信息是构成物质世界的三大支柱之一 其他两个是物质和能量 没有物质的世界是虚无的世界 没有能源的世界是死寂的世界 没有信息的世界是混乱的世界 世界是物质的 信息是物质的一种普遍属性 物质处于运动和相互作用之中 能量 形成各种事物运动的状态和方式 即信息 信息以物质为载体 以能量为动力 第一节信息的概念 各种信息的定义 1928年 美国数学家hartley在 信息传输 中 提出信息的概念 信息就是在通信符号表中选择符号的具体方式 并用所选择的自由度来度量信息 第一节信息的概念 各种信息定义 美国数学家 控制论的主要奠基人维纳 wiener 在1950年出版的 控制论与社会 一书中写到 信息既不是物质又不是能量 信息就是信息 这句话起初受到批评和嘲笑 但正是这句话揭示了信息的特质 即信息是独立于物质和能量之外存在于客观世界的第三要素 第一节信息的概念 1948年 香农发表了 通信的数学理论 创立了信息论 开始对信息的数量化进行研究 amathematicstheoryofcommunication 第一节信息的概念 claudee shannon1916年4月30日 2001年2月26日享年84岁 第一节信息的概念 第一节信息的概念 第一节信息的概念 claudee shannon 香农通信系统模型消息传递过程的特点 1 收信者在收到消息前不知道消息的具体内容 2 即使收到消息 由于干扰的存在 不能断定所收到的消息是否正确可靠 不知 不确定 疑问 不确定的消除 就获得了信息 信息是事物运动状态或存在方式的不确定性的描述 消息 第一节信息的概念 信道 干扰或噪声 发信者 信源 收信者 信宿 香农信息定义 香农通信系统模型1 某二元信源发送1的概率为0 99 发送0的概率为0 012 信源发更多的消息 数字0 1 9 电报 10个消息等概分布3 信源只发一种消息 消息 第一节信息的概念 信道 干扰或噪声 发信者 信源 收信者 信宿 不确定性 香农信息定义 第一节信息的概念 自行火箭炮 消息 是以语言 文字 图形 图象等能够为人们的感觉器官所直接感知的形式 对客观事物运动状态及人们主观思维活动的一种描述 消息是信息的载体 信息则是消息的内核 信息与消息 从通信的实质意义来讲 如果信宿收到的消息是已知的 则等于没有收到任何消息 因此 人们更感兴趣的是消息中所包含的未知成分 用概率论的术语来讲 就是具有不确定性的成分 香农将该成分称为信息 并进行了数量描述 三者的关系 通信系统传输的是信号 信号承载着消息 消息中的不确定成分是信息 香农信息度量信息量与不确定性消除的程度有关 不确定性 随机性 概率论与随机过程直观上 不确定性的大小可看为事先猜测某随机事件是否发生的难易程度 越是不太可能发生的事件竟然发生了 越是令人震惊 不确定性的大小与可能发生的消息数目及各消息发生的概率有关 出现概率越小 不确定性越大 当概率接近于1时 不确定性接近于0 第一节信息的概念 香农信息度量例事件a 中国足球队3 0力克韩国足球队 则事件a含有的信息量 例事件b 中国足球队0 1负于韩国足球队 则事件b含有的信息量 第一节信息的概念 小概率事件发生了 事件信息量大 大概率事件发生了 事件信息量小 香农信息度量信息的测度1 样本空间某事物各种可能出现的不同状态 即所有可能选择的消息的集合 2 概率测度对离散消息的集合 即对每一个可能选择的消息指定一个概率 非负且总和为1 3 概率空间一个样本空间及其概率测度 其中p ai 是选择符号ai作为消息的概率 成为先验概率 第一节信息的概念 香农信息度量信息的测度4 自信息在接收端 对是否选择这个消息 符号 ai的不确定性是与ai的先验概率成反比的 可表示为先验概率倒数的某一函数 第一节信息的概念 信息量的单位与上述定义式中所用对数的底有关 r 2时 信息量的单位为比特 bit r e时 信息量的单位为奈特 nat r 10时 信息量的单位为哈特 hart 香农信息度量信息的测度5 互信息两个事件的互信息量两个事件越是互相肯定 它们的互信息量就越大 两个事件越是互相否定 它们的互信息量就越小 如果两个事件既不互相肯定 也不互相否定 它们的互信息量就为0 直观含义 这种信息量的大小代表了相互肯定性的大小 例a 广州明日有雨 b 花都明日有雨 bc 花都明日无雨 c 北京明日有雨 d 纽约明日有雨 则a与b互信息量大 a与c互信息量小得多 a与d互信息量几乎为0 a与bc互信息量小 第一节信息的概念 香农信息度量信息的测度5 互信息两个消息为随机变量的互信息量两个消息为随机变量的互相关性越大 它们的互信息量就越大 直观含义 这种信息量的大小代表了相互依赖性的大小 例x 广州明日平均气温 y 花都明日平均气温 z 北京明日平均气温 w 纽约明日平均气温 则x与y互信息量大 x与z互信息量小得多 x与w互信息量几乎为0 第一节信息的概念 第一节信息的概念 事件a的信息量随机变量x的信息量两个事件a与b的互信息量两个随机变量x与y的互信息量 香农信息度量信息的测度5 互信息由于信道干扰 假设接收端收到的消息为 符号 bi 则条件概率p ai bi 称为后验概率 互信息 收信者在收到消息 符号 bi后 已经消除的不确定性 即收信者获得的信息量 先验的不确定性减去尚存的不确定性 第一节信息的概念 香农信息度量信息的测度5 互信息互信息 先验的不确定性减去尚存的不确定性 第一节信息的概念 香农信息度量信息的测度5 互信息若信道无干扰 收信者在收到消息后 尚存的不确定性为0 即 第一节信息的概念 香农信息定义的优点是一个科学的定义 有明确的数学模型和定量计算 与日常信息的含义一致 第一节信息的概念 概率信息 香农信息定义的局限如果实际信源或信道符合所采用的概率模型描述 这种方法是有效的 否则只能是近似的 甚至根本无效 shannon信息论适合于能够定量描述的信息 对难于定量描述的信息则无能为力 第一节信息的概念 语言的熵描述是非常困难的 是非平稳的 除了确定的信息 还有模糊的信息 比如 韵味 意境 不同的接收者对同一个东西得到的信息可能是不同的 第一节信息的概念 信息的广义概念有史以来 没有对信息下过一个确切的定义 就像对于物质和能量一样 信息虽无确切定义 但是却具有两个明显的特征 广泛性与抽象性 广泛性客观世界充满着信息人类离不开信息知识 书本是有用信息的积累抽象性三大要素是 物质 能量与信息 三要素中物质是基础 是实体 能量是物质运动的形式 e mc2 物质可转换成能量 而能量又是改造客观世界的主要动力 信息 它依附于物质和能量 但又不同于物质和能量 没有信息就不能更好地利用物质和能量 人类利用信息和知识改造物质 创造新物质 提高能量利用效率 发现新能量形式 信息也是客观存在的 它是人类认识 改造客观世界的主要动力 是人类认识客观世界的更高层次 就狭义而言 在通信中对信息的表达分为三个层次 信号 消息 信息 信号 通信系统中 对消息进行加工处理 把消息变换成适合信道传输的物理量 该物理量即为信号 信号是信息的物理表达层 是三个层次中最具体的层次 它是一个物理量 是一个载荷信息的实体 可测量 可描述 可显示 如电信号 光信号等 消息 以文字 符号 数据 语言 图片 图像等能被人们感知和理解 把客观物质运动和主观思维活动的状态表达出来 可传递和获取 消息是信息的数学表达层 可以定量描述 是具体物理信号的进一步抽象 信息 信息是指各个事物运动的状态及状态变化的方式 人们从来自对周围世界的观察得到的数据中获得信息 信息是抽象的意识或知识 它是看不见 摸不到的 人脑的思维活动产生的一种想法 当它仍储存在脑子中的时候就是一种信息 信息是信号与消息的更高表达层次 三个层次中 信号最具体 信息最抽象 信息论基础的重要性 信息论是信息科学和技术的基本理论 信息科学大厦的地基 没有信息论的基础 从事通信与信息领域的研究和创新是不可能的事情 信息论是高层次信息技术人才必不可少的基础知识 信息论研究的对象 目的和内容 1 香农信息论的研究内容香农信息论也称为狭义信息论 研究从通信系统引出的基础理论问题 信息熵 信道容量和信息率失真函数 无失真信源编码定理 信道编码定理和保真度准则下的信源编码定理 信源编码 信道编码理论与方法 2 一般信息论的研究内容一般信息论研究从广义通信引出的基础理论问题 几乎在香农创立信息论的同时 另一位美国科学家 控制论的奠基人维纳 n wiener 将人或机器与外部环境所进行的交换看成广义的通信 将信息理解为广义通信的对象 维纳将研究重点放在广义通信的接收端 提出了从噪声中提取信息的微弱信号检测理论 也称为最佳接收理论 形成信息论的一个重要分支 一般信息论的研究内容除香农信息论的研究内容外 还包括维纳的微弱信号检测理论 噪声理论 信号滤波与预测 统计检测与估计理论 调制理论等 3 广义信息论 无论是香农信息论还是一般信息论 都未讨论涉及认识主体主观因素的语义信息和语用信息 要研究信息的内在含义和效用价值 就必然会渗透到如心理学 生物学 神经生理学 语言学 经济学 社会学等有关领域 1977年 美国经济学家波拉特发表 信息经济 一文 用信息论的概念研究经济现象和社会现象 何为广义信息论 至今并无定论 目前比较公认的说法为 广义信息论是从客观和主观两个方面全面研究信息的度量 获取 传递 存储 处理和施用的技术科学 在这个意义上 人们更愿意将广义信息论称为信息科学 信源 编码器 信道 译码器 信宿 噪声源 信息论研究的对象 目的和内容 通信系统模型 研究对象 信息论研究的对象 信源 消息的来源编码器 把消息变换成信号信道 传递信号的媒介译码器 把信道输出的信号反变换信宿 信息的接受端噪声 信道中的干扰 信息论研究的对象 信息传输系统物理模型 主要研究信息的测度 信道容量 信息率失真函数 与这三个概念相对应的香农三定理以及信源和信道编码 香农信息论亦称狭义信息论 应用近代概率统计方法研究信息的基本性质及度量方法 研究信息传输 处理等一般规律的学科 反过来 所有研究信息的识别 控制 提取 变换 传输 处理 存贮 显示 价值 作用 安全以及信息量的大小的一般规律以及实现这些原理的技术手段的工程学科 信息论的完备和延伸 也都属于广义信息论的范畴 概括说来 凡是能够用广义通信系统模型描述的过程或系统 都能用信息基本理论来研究 广义信息论 信息论研究的目的 通信系统性能指标可靠性 要使信源发出的消息经过传输后 尽可能准确地 不失真或限定失真地再现在接收端有效性 用尽可能短的时间和尽可能少的设备来传输最大的消息安全性 隐蔽和保护通信系统中传送的消息 只被授权用户接收 而不能被未授权者接收和理解 接收者能正确判断所接收的消息的正确性和完整性 而不是伪造的和被篡改的 经济性 信息论研究的目的 研究通信系统的目的就是要找到信息传输过程的共同规律 以提高信息传输的可靠性 有效性 保密性 认证性和经济性 以达到信息传输系统最优化 提高可靠性和提高有效性常常会发生矛盾 这就需要统筹兼顾 就通信领域而言 信息论用于回答下述三个基本通信问题 1 对一个信源输出的数据进行数据压缩时 压缩率的极限值是多少 sourcecoding 2 通过一个有噪声的信道能够以多大的速率可靠地传输数据 channelcoding 3 当速率受限时 我们表示一个对象能够实现多大的精度 ratedistortion 信息论的理解 狭义信息论 香农信息论 经典信息论 信息的测度 信道容量 信源和信道编码理论一般信息论 工程信息论 研究信息传输和处理问题 除经典信息论外还包括编码理论 噪声理论 信号滤波和预测 统计检测和估值理论 调制理论 信息处理理论和保密理论广义信息论除上述内容外 还包括自然和社会领域有关信息的内容 如模式识别 计算机翻译 心理学 遗传学 神经生理学 信息论研究的内容 经典 狭义 香农信息论 一般 工程信息论 广义信息论 主要研究信息的测度 信道容量以及信源和信道编码理论等问题 所有与信息有关的自然和社会领域 即新兴的信息科学理论 主要研究信息传输和处理问题 信息论的发展历史 信息论是基于通信工程实践和理论研究的发展而来1924年 nyquist提出信息传输理论如果以一个确定的速度来传输电报信号 就需要一定的带宽 信号传输速率与信道带宽成正比 1928年 hartley提出信息量关系在s个代码中选n个码构成个可能的消息信息量1932年 morse发明电报编码 1946年 柯切尼柯夫提出信号检测理论 1948年 shannon提出信息论 通信中的数学理论 1 3信息论的形成和发展 1948年 香农在 通信的数学理论 的论文中 用概率测度和数理统计的方法系统地讨论了通信的基本问题 得出了几个重要而带有普遍意义的结论 香农理论的核心是 在通信系统中采用适当的编码后能够实现高效率和高可靠性的信息传输 并得出了信源编码定理和信道编码定理 从数学观点看 这些定理是最优编码的存在定理 但从工程观点看 这些定理不是结构性的 不能从定理的结果直接得出实现最优编码的具体途径 然而 它们给出了编码的性能极限 在理论上阐明了通信系统中各种因素的相互关系 为人们寻找最佳通信系统提供了重要的理论依据 1948年 香农在论文中提出并给出了简单的编码方法 香农编码 1952年 费诺 fano 提出了一种费诺码 同年霍夫曼 d a huffman 构造了一种霍夫曼编码方法 并证明了它是最佳码 对于确定概率分布的信源编码 无失真信源编码 算术码 从整个序列的概率匹配来进行编码 此概念由香农首先提出 后经许多学者改进 已进入实用阶段 1968年前后 埃利斯 p elias 发展了香农 费诺码 提出了算术编码的初步思路 里斯桑内 j rissanen 在1976年给出和发展了算术编码 1982年他和兰登 g g langdon 一起将算术编码系统化 并省去了乘法运算 使其更为简化 易于实现 无损压缩编码技术和算法的到迅速发展和应用 对于确定概率分布的信源编码 无失真信源编码 在研究信源编码的同时 另外一部分科学家从事信道编码 纠错码 的研究工作 这一工作已取得了很大的进展 并已经形成一门独立的分支 纠错码理论 1950年汉明 r w hamming 发表的论文 检错码与纠错码 是开拓编码理论研究的第一篇论文 这篇论文主要考虑在大型计算机中如何纠正所出现的单个错误 是线性分组码的基本思想 信道纠错编码的发展 信道纠错编码的发展 关键理论进展 信道纠错编码的发展 关键理论进展 信道纠错编码的发展 关键理论进展 1959年 香农发表 保真度准则下的离散信源编码理论 提出率失真函数和率失真信源编码理论 1971年伯格尔发表 信息率失真理论 率失真信源编码理论是信源编码的核心问题 是频带压缩 图像和多媒体等数据压缩的理论基础 语音压缩编码 ccittg 722 g 723 g 728静态图像压缩 jpeg动态图像压缩 mpeg 2 mpeg 4视频 h 261 h 263 限失真信源编码理论 技术成就 cdma virerbi qaulecom 的技术问题 联合检测和译码 均衡 干扰抵消 速率分拆 功率检测控制等 stc spacetimecode 源于信息论考虑 线性网络编码合作编码技术 多用户 网络信息论 密码编码学是信息安全技术的核心 密码编码学的主要任务是寻求产生安全性高的有效密码算法和协议 以满足对消息进行加密或认证的要求 密码分析学的主要任务是破译密码或伪造认证信息 实现窃取机密信息或进行诈骗破坏活动 这两个分支既相互对立又相互依存 正是由于这种对立统一关系 才推动了密码学自身的发展 香农在1949年发表的 保密通信的信息理论 论文中 首先用信息论的观点对信息保密问题作了全面的论述 信息保密与安全理论 由于保密问题的特殊性 直至1976年迪弗 diffe 和海尔曼 hellman 发表了 密码学的新方向 一文 提出了公开密钥密码体制后 保密通信问题才得到广泛研究 当今 信息的安全和保密问题更加突出和重要 人们把线性代数 初等数论 矩阵等引入保密问题的研究 已形成了独树一帜的分支 密码学理论 1978年 berlekamp证明纠错码中的一般线性分组码的译码问题是np问题 同年 mceliece又构造了基于纠错码的公开密钥密码体制 至此 纠错码和密码学的结合研究迅速发展 信息保密与安全理论 信息科学 信息科学是由一般信息论发展起来的 目前它已渗透到通信与电子 计算机 自动化 微电子与材料 光学与光电子等工程学科以及经济 管理 心理 生物 社会 哲学等非工程学科 可见 信息科学的研究内容极为广泛 是目前最活跃的技术科学之一 未来的趋势 过去50年中shannon信息论已取得巨大 丰富的理论和技术成果 在未来的50年中 shannon信息论将继续繁荣还是趋向衰落和消亡 在过去50年中也曾几次出现过类似的争论 如果信息论继续推动技术的发展 则在未来的几十年中就会继续繁荣下去 否则会象近30年来的物理学所经受的萧条 当前信息论对无线通信的重要作用为信息论的发展提供了契机 无线频带资源的匮乏更趋严重 高效和高可靠性通信愈加依靠信息论的发展 同时需要更多的信息论人才 internet通信 移动通信 光存储 生物等领域将向信息论提出新挑战 补充 信源的不确定性信源是发送消息 又称符号 的一方 信源发出的消息载荷了信息 经过信道传送到接受消息的一方 即信宿 信宿收到了信源发送来的消息 知道了原来不知道的关于信源的情况 即获得了信息 这个过程称为通信 补充 信源的不确定性实际有用的信源应具有不确定性 信源至少应含有两种消息 如二元信源 有0和1两种消息 信宿知道与其通信的信源有0 1两种消息 但不知道信源某时刻发送的是哪个消息 必须通过通信 信宿收到信源发出的某个消息后 经判断 称为译码 才能确认信源发出的是哪个消息 如果信道中没有噪声和干扰 信宿一定判断正确 于是 通信可以无差错地完成 即信源发送什么消息 信宿就收到什么消息 信源的不确定性是指 信宿对信源某时刻发送哪个消息不能确定 补充 信源的不确定性 1 信源的不确定程度与其概率空间的消息数及其概率分布有关 2 信源的消息为等概率分布时 不确定度最大 3 信源的消