第4次课--Shannon信息论幻灯片.pptVIP

* 例：密码体制 M={a,b}，p(a)=1/4，p(b)=3/4 K={k1,k2,k3}，p(k1)=1/2，p(k2)=p(k3)=1/4 C={1,2,3,4} a b k1 1 2 k2 2 3 k3 3 4 计算：明文熵、密文熵、密钥熵。 解： 明文熵： 密钥熵： 密文熵： * 对给定的Y，X的条件熵 称为疑义度 1）给定C，K的疑义度： 2）给定C，M的疑义度： 密码分析时，从密文中提取有关明文的信息，即： 从密文中提取有关密钥的信息，即： H(M|C)、H(K|C)越大，窃听者从密文能提取的有关明文和密钥的信息就越小。 * 对于合法的接收者： H(M|CK)=0 即 I(M;CK)=H(M) －H(M|CK)=H(M) 又设： H(K|C)=H(K|C)+H(M|CK) =H(KC)-H(C)+H(MCK)-H(CK) =H(MCK)-H(C) =H(MK|C) =H(M|C)+H(K|CM) ≥H(M|C) 说明： 已知密文后，密钥的疑义度总大于等于明文的疑义度。 可能满足c=Ek(m)的k不止一个，但用同一个k对不同的m加密得到相同的c，较难。 H(XY)=H(Y)+H(X|Y) =H(X)+H(Y|X) * 又因为 H(K) ≥H(K|C) ≥H(M|C) 那么从C中获得M的信息为： I(M;C)=H(M)-H(M|C) ≥H(M)-H(C) 说明： 若k的数量少，则H(K)小，则密文中含有关明文的信息量I(M;C)大。所以k不能太少，且应概率均匀。 * 香农简介 香农(1916-2001),生于美国密执安州的加洛德。1940年获得麻省理工学院数学博士学位和电子工程硕士学位。1941年他加入了贝尔实验室数学部，在此工作了15年。 * 香农简介 香农在信息论的领域中钻研了8年之久，终于在1949年在《贝尔系统技术杂志》发表了244页的长篇论著---《必威体育官网网址系统的通信理论》。次年，他又在同一杂志上发表了另一篇名著---《噪声下的通信》。 * 香农理论简介 第一篇文章奠定了香农信息基本理论的基础。他在文中用非常简洁的数学公式定义了信息时代的基本概念：熵。 　　 “熵”的概念起源于热力学，是度量分子不规则热运动的单位。香农的伟大贡献在于，利用概率分布的理论给出“熵”的严格定义。 根据香农的定义，确定发生的事件如“太阳从东边升起”与确定不发生的事件如“太阳从西边升起”，其熵都是零。只有当发生与不发生 的概率相同时，事件的熵才达到极大。 * 香农理论简介 在熵的基础上定义的信道容量也是通讯中一个至关重要的概念。由此，香农推出了一个公式，明确表达了在不同噪声情况下传输速率与失真的定量关系。从这一个公式导出的为达到无失真通讯的传输速 率的极限，现已称为香农极限。打个比方来说，在周围干扰严重的情 况下，要想使对方听清楚，你就只有慢慢地讲，甚至还要不断重复。 * 香农理论应用 如今，这两个原理已广泛应用于信息处理和实际通信中。只要涉及信息的压缩与传递，就要用到香农的理论。 PC机上常用的WinZip (无损压缩算法) 手机通讯 (有损压缩?无损压缩,纠 错) 在因特网上传递多媒体数据 （MP3音乐压缩格式） * 第三章 Shannon必威体育官网网址理论 密码体制的数学模型 随机事件的熵及其性质 * 通信系统 * 信源 编码器 解码器 接收者 干扰源 信道 设计目的：在信道有干扰的情况下，使得接收者接 收到的信息无差错或差错尽可能的小。 必威体育官网网址系统 * 设计目的：使得窃听者即使完全准确地接收带了信道上传输的信号也无法恢复出原始的信息。 密码体制的数学模型 明文(离散信源)空间的统计特性：无记忆和有记忆 密钥源通常是无记忆的，并且满足均匀分布 密文空间的统计特性由明文空间和密钥空间的统计特性决定 假定信道无干扰，假定分析者能够截获密文，且知道所用的密码体制以及明文空间和密钥空间的统计特性 * * §3.2 随机事件的熵及其性质 主要内容: 如何定量刻划一个随机事件包含的信息量 用熵的概念! 熵(entropy)这个数学工具自身的理论. * 何为信息? 什么能提供信息? 我将你原来不知道的结果告诉你,就是提供了信息!