Shannon与信息论.ppt

研究生密码学 第三讲：Shannon与信息论 1、信息论概述 1.1　信息的概念 1.2　信息论研究的对象、目的和内容 1.3 信息论的形成与发展 信息的产生与传播 1.3　信息论的形成和发展 信息论的研究对象是广义的通信系统，它把所有的信息流通系统都抽象成以下的模型： 这个通信系统主要分成五个部分： （1）信源。顾名思义，信源是产生消息和消息序列的源。 （2）编码器。编码就是把消息变成适合在信道传输的物理量，这种物理量称为信号。编码器可分为信源编码器、信道编码器。 信源编码的目的为了提高通信系统的有效性和提高信息传输的可靠性。在实际的通信系统中，可靠性和有效性常常相互矛盾 。 （3）信道。信道是指通信系统把载荷消息的信号从发送端送到接收端的媒介或通道，是包括收发设备在内的物理设施。 （4）译码器。译码就是把信道输出的已迭加了干扰的编码信号进行反变换，变成信宿能够接受的消息。译码器也可分成信源译码器和信道译码器。 （5）信宿。信宿是消息传送的对象，即接受消息的人或机器。 信息论研究的是关于这个通信系统的最根本、最本质的问题。例如： ①什么是信息？如何度量信息？ ②怎样确定信源中含有多少信息量？ ③对于一个信道，它传输信息量的最高极限（信道容量）是多少？ ④为了能够无失真的传输信源信息，对信源编码时所需的最少的码符号数是多少？（无失真信源编码即香农第一定理） ⑤在有噪信道中有没有可能以接近信道容量的信息传输率传输信息而错误概率几乎为零？（有噪信道编码即香农第二定理） ⑥如果对信源编码时允许一定量的失真，所需的最少的码符号数又是多少？（限失真信源编码即香农第三定理） 密码学研究的内容 如何隐蔽消息中的信息内容，使它在传输过程中不被窃听，提高通信系统的安全性。 2、Shannon与信息论 2、Shannon与信息论 2、Shannon与信息论 香农系统提出了信息率失真理论 (rate-distortion theory)，给出了在一定允许失真条件下信息压缩和恢复的极限条件。 1961年，香农的 “双路通信信道” (Two-Wag Communication Channels) 一文又将信息论拓展到了多用户领域。 从1951年美国无线电工程师协会(IRE)成立信息论组开始，包括香农本人在内的一些科学家也提出了许多编码理论和编码方法。 2、Shannon与信息论 香农用非常简洁的数学公式定义了信息时代的基本概念：熵。 “熵”的概念起源于热力学，是度量分子不规则热运动的单位。香农的伟大贡献在于，利用概率分布的理论给出“熵”的严格定义。 根据香农的定义，确定发生的事件如“太阳从东边升起”与确定不发生的事件如“太阳从西边升起”，其熵都是零。只有当发生与不发生 的概率相同时，事件的熵才达到极大。 在熵的基础上定义的信道容量也是通讯中一个至关重要的概念。由此，香农推出了一个公式，明确表达了在不同噪声情况下传输速率与失真的定量关系。从这一个公式导出的为达到无失真通讯的传输速 率的极限，现已称为香农极限。打个比方来说，在周围干扰严重的情 况下，要想使对方听清楚，你就只有慢慢地讲，甚至还要不断重复。 如今，这两个原理已广泛应用于信息处理和实际通信中。只要涉及信息的压缩与传递，就要用到香农的理论。 PC机上常用的WinZip (无损压缩算法) 手机通讯 (有损压缩?无损压缩,纠 错) 在因特网上传递多媒体数据 （MP3音乐压缩格式） Shannon必威体育官网网址理论 密码体制的数学模型 随机事件的熵及其性质 通信系统 必威体育官网网址系统 必威体育官网网址系统 设计目的：使得窃听者即使完全准确地接 收带了信道上传输的信号也无 法恢复出原始的信息。 密码体制的数学模型 明文(离散信源)空间的统计特性：无记忆和有记忆 密钥源通常是无记忆的，并且满足均匀分布 密文空间的统计特性由明文空间和密钥空间的统计特性决定 假定信道无干扰，假定分析者能够截获密文，且知道所用的密码体制以及明文空间和密钥空间的统计特性 随机事件的熵及其性质 随机事件和随机变量 定义1：设一个实验有 共n个可能的结果，则每个可能结果都称为一个事件。这个实验也称为一个随机事件。 性质1：设X是一个离散随机变量，它有n个可能的取值　　　　　，设每种取值出现的概率为p(xi),则 熵的数学定义 定义3.1(随机事件的熵):设一个实验X有 共n个可能的结果,则称 的数学期望 为实验X的熵(Entropy). 其中约定 0log0 = 0. 引理3.1(Jensen不等式) 　　设 f 是区间I