应用密码学-Shannon信息论

《应用密码学-Shannon信息论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章Shannon理论王滨2004年3月7日香农简介香农(1916-2001),生于美国密执安州的加洛德。1940年获得麻省理工学院数学博士学位和电子工程硕士学位。1941年他加入了贝尔实验室数学部，在此工作了15年。8/31/20212香农简介香农在信息论的领域中钻研了8年之久，终于在1949年在《贝尔系统技术杂志》发表了244页的长篇论著---《保密系统的通信理论》。次年，他又在同一杂志上发表了另一篇名著---《噪声下的通信》。8/31/20213香农理论简介第一篇文章奠定了香农信息基本理论的基础。他在文中用

2、非常简洁的数学公式定义了信息时代的基本概念：熵。“熵”的概念起源于热力学，是度量分子不规则热运动的单位。香农的伟大贡献在于，利用概率分布的理论给出“熵”的严格定义。根据香农的定义，确定发生的事件如“太阳从东边升起”与确定不发生的事件如“太阳从西边升起”，其熵都是零。只有当发生与不发生的概率相同时，事件的熵才达到极大。8/31/20214香农理论简介在熵的基础上定义的信道容量也是通讯中一个至关重要的概念。由此，香农推出了一个公式，明确表达了在不同噪声情况下传输速率与失真的定量关系。从这一个公式导出的为达到无失真通讯的

3、传输速率的极限，现已称为香农极限。打个比方来说，在周围干扰严重的情况下，要想使对方听清楚，你就只有慢慢地讲，甚至还要不断重复。8/31/20215香农理论应用如今，这两个原理已广泛应用于信息处理和实际通信中。只要涉及信息的压缩与传递，就要用到香农的理论。PC机上常用的WinZip(无损压缩算法)手机通讯(有损压缩无损压缩,纠错)在因特网上传递多媒体数据（MP3音乐压缩格式）8/31/20216第三章Shannon保密理论密码体制的数学模型随机事件的熵及其性质8/31/20217通信系统信源编码器解码器接收者干扰源

4、信道设计目的：在信道有干扰的情况下，使得接收者接收到的信息无差错或差错尽可能的小。8/31/20218保密系统8/31/20219保密系统设计目的：使得窃听者即使完全准确地接收带了信道上传输的信号也无法恢复出原始的信息。8/31/202110密码体制的数学模型明文(离散信源)空间的统计特性：无记忆和有记忆密钥源通常是无记忆的，并且满足均匀分布密文空间的统计特性由明文空间和密钥空间的统计特性决定假定信道无干扰，假定分析者能够截获密文，且知道所用的密码体制以及明文空间和密钥空间的统计特性8/31/202111§3.2随

5、机事件的熵及其性质主要内容:如何定量刻划一个随机事件包含的信息量用熵的概念!熵(entropy)这个数学工具自身的理论.8/31/202112何为信息?什么能提供信息?我将你原来不知道的结果告诉你,就是提供了信息!例1当我给你一封信时，你就从我这里获得了信息，因为你事先并不知道其中的内容。例2设电脑彩票由8个10进制数组成.在开奖之前，我们不知道特等奖号码的信息，因为特等奖的号码是不确定。特等奖号码的信息只有在开奖时才获得。一旦开奖，就获得了8个十进制数的信息。这就是说，将未知的变成已知的时就获得了信息！信息寓于不

6、确定之中！8/31/202113信息量我向你提供的信息量的大小就是你事先不知道结果的程度!也即是信息的不确定度。如果你事先全知道了,说明我提供的信息量等于0;如果你事先一无所知,说明我提供的信息量最多.不知道意味着在我告诉你之前你只能猜测!猜测就是按照每个可能结果的出现概率进行猜测!因此,你只知道这个事情的每个结果的发生概率!所以,我提供的信息量就是由你事先知道的每个可能结果的发生概率(即随机事件的概率分布)决定.8/31/202114简单地说,信息就是:(1)当未知的变成已知的之后获取的信息;(2)当未知的还没变

7、成已知之前包含的未知信息.信息寓于不确定之中！谁的信息!通常的信息是指:(1)一个实验提供的信息;(2)一个随机事件包含的信息;(3)一个随机变量包含的信息.其中(1)和(2)的含义相同,它们比(3)的意义更加广泛.8/31/202115随机事件和随机变量定义1：设一个实验有共n个可能的结果，则每个可能结果都称为一个事件。这个实验也称为一个随机事件。性质1：设X是一个离散随机变量，它有n个可能的取值　　　　　，设每种取值出现的概率为p(xi),则8/31/202116一、随机事件的熵一个事件可能发生，也可能不发生！

8、但我们总在每个事件发生的概率都已知的条件下分析！这个实验提供的信息就是：(1)实验前该实验所包含的未知信息；(2)实验后这个实验所提供的信息.如何对信息量的大小进行定量刻划?再看一下彩票的例子.8/31/202117例3设电脑彩票由8个10进制数组成，在开奖之前，108个可能号码成为特等奖的概率相同,都是10-8.一旦开奖,我们就知道了特等奖的8个具体号码,