【安全课件】第4讲--shannon信息论精编版

《【安全课件】第4讲--shannon信息论精编版》由会员分享，可在线阅读，更多相关《【安全课件】第4讲--shannon信息论精编版（43页珍藏版）》请在金锄头文库上搜索。

1、第三章 Shannon 理论,王 滨 2004年3月7日,1,香农简介,香农(1916-2001),生于美国密执安州的加洛德。1940年获得麻省理工学院数学博士学位和电子工程硕士学位。1941年他加入了贝尔实验室数学部，在此工作了15年。,2,香农简介,香农在信息论的领域中钻研了8年之久，终于在1949年在贝尔系统技术杂志发表了244页的长篇论著-保密系统的通信理论。次年，他又在同一杂志上发表了另一篇名著-噪声下的通信。,3,香农理论简介,第一篇文章奠定了香农信息基本理论的基础。他在文中用非常简洁的数学公式定义了信息时代的基本概念：熵。 “熵”的概念起源于热力学，是度量分子不规则热运动的单位。

2、香农的伟大贡献在于，利用概率分布的理论给出“熵”的严格定义。 根据香农的定义，确定发生的事件如“太阳从东边升起”与确定不发生的事件如“太阳从西边升起”，其熵都是零。只有当发生与不发生 的概率相同时，事件的熵才达到极大。,4,香农理论简介,在熵的基础上定义的信道容量也是通讯中一个至关重要的概念。由此，香农推出了一个公式，明确表达了在不同噪声情况下传输速率与失真的定量关系。从这一个公式导出的为达到无失真通讯的传输速 率的极限，现已称为香农极限。打个比方来说，在周围干扰严重的情 况下，要想使对方听清楚，你就只有慢慢地讲，甚至还要不断重复。,5,香农理论应用,如今，这两个原理已广泛应用于信息处理和实际

3、通信中。只要涉及信息的压缩与传递，就要用到香农的理论。 PC机上常用的WinZip (无损压缩算法) 手机通讯 (有损压缩无损压缩,纠 错) 在因特网上传递多媒体数据 （MP3音乐压缩格式）,6,第三章 Shannon保密理论,密码体制的数学模型 随机事件的熵及其性质,7,通信系统,设计目的：在信道有干扰的情况下，使得接收者接 收到的信息无差错或差错尽可能的小。,8,保密系统,9,保密系统,设计目的：使得窃听者即使完全准确地接 收带了信道上传输的信号也无 法恢复出原始的信息。,10,密码体制的数学模型,明文(离散信源)空间的统计特性：无记忆和有记忆 密钥源通常是无记忆的，并且满足均匀分布 密文

4、空间的统计特性由明文空间和密钥空间的统计特性决定 假定信道无干扰，假定分析者能够截获密文，且知道所用的密码体制以及明文空间和密钥空间的统计特性,11,3.2 随机事件的熵及其性质 主要内容: 如何定量刻划一个随机事件包含的信息量 用熵的概念! 熵(entropy)这个数学工具自身的理论.,12,何为信息? 什么能提供信息? 我将你原来不知道的结果告诉你,就是提供了信息! 例1 当我给你一封信时，你就从我这里获得了信息，因为你事先并不知道其中的内容。 例2 设电脑彩票由8个10进制数组成.在开奖之前，我们不知道特等奖号码的信息，因为特等奖的号码是不确定。特等奖号码的信息只有在开奖时才获得。一旦开

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

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

7、) 实验前该实验所包含的未知信息； (2) 实验后这个实验所提供的信息. 如何对信息量的大小进行定量刻划?,再看一下彩票的例子.,17,例3 设电脑彩票由8个10进制数组成，在开奖之前，108个可能号码成为特等奖的概率相同,都是10-8.一旦开奖,我们就知道了特等奖的8个具体号码,因而就获得了8个十进制数的信息。 我们获得的信息量与开奖前每个可能号码成为特等奖的概率10-8有何关系? 显然,有 8 = - log10 10-8 信息量的定量刻划:,定义2 设 是一个实验中事件 发生的概率,则称 为事件 包含的自信息量.,18,熵的数学定义,定义3.1(随机事件的熵):设一个实验X有 共n个可能

8、的结果,则称 的数学期望 为实验X的熵(Entropy). 其中约定 0log0 = 0.,19,因此,一个实验的熵就是该实验的每个可能结果包含的自信息量的平均值! 熵的单位与对数的底有关! 约定对数的底大于1! 当以2为底时,其单位称为比特(bit); 当以10为底时,其单位称为迪特(Det);,20,例5设一个实验有a和b两个可能的结果,且实验结果是a和b的概率分别为1/4和3/4,试计算该实验的熵.,解:,根据熵的定义,有,解毕,21,下面介绍熵的性质.,定义3.4 一个实值函数 f 称为在区间I上是凸 的,则称 f 称为在区间I上是严格凸的.,22,引理3.1(Jensen不等式),设

9、 f 是区间I上的一个连续的严格凸函数,并 且 , 则有 且上述等号成立的充要条件是,23,推论1 f (x)=logb x (b1)在区间x 0时是严格 凸的,因而当实数 满足 且 有：,且等号成立的充要条件是诸pi全相等.,证明：注意此推论中条件与Jensen不等式中 条件不同，故证明如下。,24,证明,(记 , ),不妨设 都0,且,显然,当 时等号不成立;,25,定理3.1 设b1,则有,(1),证明,(1) 由 可知,故(1)成立.,(2) 由Jensen不等式的推论1可知(2)成立.,26,(3)充分性:,此时,必要性:,由于诸,设H(X)=0.,若存在t,使,则,从而,因而必要性

10、成立.,.矛盾!,27,定理3.1说明: (1) 结果确定的随机事件不提供信息量, 因而提供的信息量最少! (2) 可能结果等可能发生的随机事件提供 的包含的信息量最大! 这与我们的直觉是一致的!,28,现实中的事件都不是孤立的! 很多随机事件之间都有相互的联系和影响!那么,如何刻划和研究多个随机事件相互 提供的信息呢? 这就要引入两个实验的 联合熵 条件熵 互信息 等概念！,29,因此,实验X与实验Y的联合熵(Joint Entropy)就是事件(xi ,yj )的自信息量的数学期望. 它反映了联合分布p(x, y )包含的信息量.,定义3.2(联合熵): 实验X与实验Y的可能结果分别为 和

11、 ,定义X与Y的联合熵 为,30,定义3.3(条件熵): 实验X与实验Y的可能结果分别为 和 .定义X与Y的条件熵为,(1) 称 为在实验Y的结果为 yj的条件下,事件xi的条件自信息量.,为在实验Y的结果为yj的条件下,实验X的条件熵.,(2)称,31,(3) 称,为在实验X关于实验Y的条件熵.,反映了,Y的结果是yj条件下,实验X包含的信息量.,反映了,Y的结果已知条件下,实验X平均包含的信息量.,32,联合熵与各自的熵的关系,定理3.2,两个实验提供的信息总量一定不超过这两个实验分别提供的信息量之和;当且仅当两个实验独立时,二者才相等.,直观含义:,33,证明,(1) 因,故有,下证 .

12、,再由,和,得,34,因,故有,即,现分析等号何时成立?,35,将上述推理过程中出现的地方保留,就是,(1) 存在常数c,使对满足 的i, j,都有,第一个变成等号的条件是:,因而有,第二个变成等号的条件是:,(2) 当 时必有 ,即,36,对所有的i, j 都成立,故有,说明对所有的i, j,都有,即,这就证明了:,X与Y独立,现设 成立,则,X与Y独立,证毕,37,联合熵与条件熵的关系,定理3.3,直观含义:,两个实验提供的信息总量等于第一个信息提供的信息量加上在第一个实验的结果已知条件下,第二个实验提供的信息量.,38,联合熵与条件熵的关系,定理3.3,证明：由于,故有,同理可证,证毕,

13、39,联合熵与熵的关系,故有,定理3.2指出:,定理3.3指出:,推论3.1,40,定义3.3(平均互信息): 称,为实验X与实验Y的平均互信息.,结论:,直观的含义：将X包含的未知信息量减去在实验Y的结果已知条件下,X仍具有的未知信息量.,就是实验Y提供的X的信息了.,41,下节内容,分组密码,42,1、有时候读书是一种巧妙地避开思考的方法。20.9.1620.9.16Wednesday, September 16, 2020 2、阅读一切好书如同和过去最杰出的人谈话。20:13:1220:13:1220:139/16/2020 8:13:12 PM 3、越是没有本领的就越加自命不凡。20.

14、9.1620:13:1220:13Sep-2016-Sep-20 4、越是无能的人，越喜欢挑剔别人的错儿。20:13:1220:13:1220:13Wednesday, September 16, 2020 5、知人者智，自知者明。胜人者有力，自胜者强。20.9.1620.9.1620:13:1220:13:12September 16, 2020 6、意志坚强的人能把世界放在手中像泥块一样任意揉捏。2020年9月16日星期三下午8时13分12秒20:13:1220.9.16 7、最具挑战性的挑战莫过于提升自我。2020年9月下午8时13分20.9.1620:13September 16, 2

15、020 8、业余生活要有意义，不要越轨。2020年9月16日星期三8时13分12秒20:13:1216 September 2020 9、一个人即使已登上顶峰，也仍要自强不息。下午8时13分12秒下午8时13分20:13:1220.9.16 10、你要做多大的事情，就该承受多大的压力。9/16/2020 8:13:12 PM20:13:122020/9/16 11、自己要先看得起自己，别人才会看得起你。9/16/2020 8:13 PM9/16/2020 8:13 PM20.9.1620.9.16 12、这一秒不放弃，下一秒就会有希望。16-Sep-2016 September 202020.9.16 13、无论才能知识多么卓著，如果缺乏热情，则无异纸上画饼充饥，无补于事。Wednesday, September 16, 202016-Sep-2020.9.16 14、我只是自己不放过自己而已，现在我不会再逼自己眷恋了。20.9.1620:13:1216 September 202020:13,谢谢大家,