信息论第一讲

第一章 绪论1.1 信息的概念研究信息及信息安全技术所面临的第一个问题是：什么是信息？ 在不同的时代，对于不同的研究对象，人们会定义不同的信息概 念。我们可以从文献中查到几十个信息定义，其中最有影响的是由美 国科学家香农(C. E. Shannon)和语言学家所定义的信息。香农把问题限定在通信活动之中，因此他所定义的信息概念以通 信模型为基础。从人类原始的思想情感交流方式发展到现代通信技术，经历了漫 长的历史过程。但是任何通信过程都符合一个基本的模型，即发送者 发出的消息经过传输后被接收者所接收，正如图 1-1 所示。在这个最 简单的通信模型中，信源是消息之源，通常指提供消息的人或设备， 例如打电话时的说话人、广播节目的电视台等；信道是传递消息的通 道，包括电缆、光纤，以及传输电磁波的空间等；而信宿则是指消息 的接收者。信源 信道 信宿图 1-1 最简单的通信模型信源发出的消息可能是符号、文字、图像或者声音，传送它们需 要借助于载体，通过载体的传输完成消息的传递。对于电子通信来说， 不可能使用物质载体，只能借助于能量载体，后者以电磁信号的形式 完成携带消息的任务。接收者从收到的信号中检测出信源发出的原始 消息。如果接收者早已知道这个消息，就失去了这次通信的意义，接 收者感兴趣的是收到新消息，收到原来不知道的内容。在这个意义上， 把信息定义为：定义11接收到的原来不知道的内容叫做信息。这样定义的信息概念可以进行度量，它在通信技术发展过程中发 挥了重要作用。辞海中对信息一词的解释显然受到上述影响：通信 系统传输和处理的对象，泛指消息和信号的具体内容和意义，通常需 通过处理和分析来提取。信息、物质和能量被称为系统的三大要素。 信息的量值与信息的随机性有关，因此在接收端无法预估消息或者信 号中蕴涵的内容或意义，预估的可能性越小，信息量就越大。然而在网络时代，通信效率和通信速率不再是人们关心的唯一问 题，人们常说的信息概念也远远超出了上述定义。另一方面，对定义1.1 的理解提出了一个问题，即当一个熟记小提琴协奏曲梁祝的人 再次欣赏那优美乐章时，他是否收到了信息？依据不同的基准会有不同的答案。如果把信息概念限定在“豆芽” 的排列上，则没有收到信息，这反映在香农信息量 H （X） 0 之中（见 第二章）；如果把音色、音质，以及演奏者注入的情感这些乐谱无法表 征的内容也看作是信息，则答案是肯定的。是啊，否则听音乐（也是 一种通信过程）还有什么意义呢？由于信源发出的消息总是以某种符号表示（文字、图像或者声音都是符号），因此在符号学理论和信息概念之间就有一种不可分割的关系。语言符号学的创始人之一莫里斯把语言分作三个方面：（1）符号和对象之间的关系叫做符号过程的语义方面，有关研究 叫语义学；（2）符号和解释者之间的关系叫做符号过程的运用方面，有关研 究叫语用学；（3）符号相互之间的形式关系叫做符号过程的语形方面，有关研究叫语形学或句法学。语用学、语法学和句法学之间的关系如图1-2 所示。图 1-2 语言符号学的关系有人从类似的视角提出了如下的信息定义：定义 1.2 消息中表达消息实质内容的部分叫做语义信息。定义 1.3 消息中说明语义信息表现格式的部分叫做语法信息。定义 1.4 语法信息和语义信息共同构成消息本征信息。这种类似于语言符号学的定义方法自有其积极意义。现代的通信 技术中，接收到的消息既包含消息的实质内容，也包含与之有关的语 法说明。例如我们传输一幅图像数据时，还必须带有这幅图像的格式， 缺少了格式说明，接收端就很难得到应有的画面。似乎这种定义方法 更适合网络时代的需求。然而，无论是语义信息、语用信息，还是本 征信息，都没有直接指导信息技术的发展，即使在网络比较充分普及 的今天，也很难看到从符号学的信息定义出发导出的具有理论或实际 意义的结果。在人类社会迈进信息时代的今天，信息已经成为社会生产力的重 要组成部分，人们不再只需要用信息理论研究通信问题，在信息的产 生、存储、传输和应用过程中，都需要有信息理论的支持；人们也不 再只重视传输效率和可靠性问题，许多关于信息的新问题，例如信息 的完整性、有用性、安全性、时效性、可鉴别性等在现实的生产、生 活中已经不可回避。因此，“什么是信息”这个问题重新摆在我们的面.、几前。那么，究竟应该如何定义信息才更符合实际需要？这样的信息具 有什么性质？众说纷纭，尚未统一。我们认为，把香农的信息概念加 以泛化既有利于继承前人的贡献，又能适应当代科学发展的需要。作 为定义，可以表述为：定义1.5关于客观事物的概念、属性、相互关联和运动规律的知 识，以及客观事物属性的自我显现叫做信息。这个定义包含两方面的内容：一是思维活动产生的结果，即所谓 知识，知识的存储和传输就是信息的存储和传输；二是客观事物属性的自我显现，例如我们观察到蓝天下的田野，这个画面算不上什么知 识，却是天空和田野属性的自我显现，观察的过程就是我们通过视觉 系统接收信息的过程。关于第二方面的内容可以参考传统信息论创始 人之一Wiener（维纳）的信息定义：信息是人们在适应外部世界和控制外部世界的过程中，同外部世界进行交换内容的名称。这个定义不强调原来是否知道，可以理解为香农信息论里所说的 消息。比如在因特网上传输的海量信息中，有有用的信息，也有无用 的修饰，对于那些无用的修饰等，也要可靠地传输，不允许马塞克现 象的出现；为提高网络传输效率，人们会采取限失真压缩办法，不一 定要剔除消息中原来意义上的冗余；相互传送邮件时，斟酌字句去除 信息冗余的情况也难于遇到。实际传输的比特率是对消息而言。然而这个定义没有给出信息的定量标准。当我们说信息量的大小 时，往往关注实际的比特数。在信息安全成为众所关心的议题时，这 样的定义具有实际的意义。1.2 信息的性质和信息概念的定义一样，人们总结了许多条信息的性质往往 带有不同应用目的的影响这是无可厚非的。但是，在从应用层面 讨论之前，更应该从信息的物理属性方面观察，因为这方面的性质是 更本质的东西。性质 1 信息是普遍的客观存在。 按照定义 1.5，即使在人类创立知识以前，信息也已经客观存在。 性质 2 信息不守恒，即信息既可以消亡，也可以创生。大脑的思维活动可以创生新的知识，这些知识属于新的信息内容； 独版书籍或者存有某种数据的唯一光盘的销毁意味着有关信息的消 亡。性质 3 信息必须依赖于物质或能量而存在，依赖于物质或能量而 传输，即不存在离开物质和能量而独立存在的信息，它必须以物质或 能量作为载体。性质 4 信息可以复制，从而可以分享。不像物质和能量那样，信息可以无限复制，不同人可以同时拥有 同一份信息。性质 5 对信息的处理不会增加信息的原始内容。这里所说的处理包括滤波、存储、传输等，滤波处理是对原始信 息的修改，存储和传输是对信息的转移，在此过程中增加的所有内容 都不是原始的信息。例如从BMP图像转换成JPG图像（可以归为滤波 处理），且不说图像细节的丢失，JPG格式的语法说明就不是原来的内 容；模糊图像处理的结果本来就含在原来的信息之中；接收端收到的 信息不可能多于信源发出的信息，而且只有在接收灵敏度和感觉灵敏 度都达到一定水平时，二者才可能相等。信息的物理性质反映了信息的本质特征，决定了达到某种应用目 标的可能性。从应用角度阐述的信息性质决定了信息技术的发展方向。从信息安全的角度看，人们关心的是信息的安全性、完整性、有 用性、时效性、可鉴别性等。秘密信息的保密、音像产品的非法复制 牵涉到信息的安全性问题，网络路由的复杂性决定了能否保证信息的 完整性，信息的真实和时效意义是信息有用性的体现，保密性、真实 性和不可抵赖是可鉴别性的动因，等等。有些书上为信息归纳了十几条性质，其中有些基于香农的信息定 义，有些从应用层面考虑，例如：1、新颖性接收者收到信息之前，对其内容是不知道的，所以 信息是新知识、新内容；2、有益性信息是能使认识某一事物的未知性或不确定性减少 的有用知识；3、可测性信息是可度量的，信息量的大小有差别；4、相对性不同的接收者所得到的信息量不同；5、可加工性信息可以产生、消失、携带、存储和处理；6、转移性信息可以在时间上或在空间中从一点转移到另一 点；八、97、变换性信息是可变换的，它可以由不同的载体和不同的 方法来载荷；8、有序性信息可以用来消除系统的不定性，增加系统的有 序性；9、动态性一切活的信息都随时间而变化，因此信息也是有 时效、有寿命的。这些甚至更多的性质，对信息安全的研究实际意义不大，倒是还 有些更加深入的内容值得我们思考，例如用不同的语气讲同样的话表 示不同的意思，“言外之意”、“字里行间”等都反映了信息的复杂性质。 为了避免这些深层次因素的影响，我们不打算用包罗万象的概念来讨 论信息，只局限在消息的层面上讨论问题。1.3 信息理论的发展信息理论是信息科学的基础，强调用数学语言描述信息科学中的 共性问题和解决方案。到目前为止，信息理论一直处在发展之中，新 的研究成果可能仅局限于某个应用领域，也有可能具有广泛的意义。 有人把信息理论划分为狭义信息论、一般信息论和广义信息论三个层 次，以说明其涵盖范围的不同。狭义信息论又称香农信息论，主要总结了香农的研究成果，在信 息可度量的基础上，研究如何有效、可靠地传递信息，重点是各种编 码技术。它是通信问题的理论提升。香农分别于 1948 年和 1949 年 发表了两篇著名文章： “the Mathematical Theory of Communication” 和“ Communication in the Presence of Noise”，这两篇文章讨论了信息的度量、特征、传输速率、 信道容量以及干扰的影响等问题，用概率测度和数理统计方法系统地 阐述了通信的基本问题，奠定了信息科学的基础，对通信技术的发展 做出了重大贡献。尽管在此之前， 奈奎斯特 (H.Nyquist) 已于 1924 年解释了信号带宽和信息率间的关系，但是其影响远不如香农这两篇 文章的作用。一般信息论除了香农对信息科学的贡献以外，还包括其它人的研 究成果，特别是美国科学家N. Wiener（维纳）的微弱信号检测理论。他 在与香农的同一时期出版了两本名著：trapolation ， Interpolation and Smoothing of Stationary Time Series和Control Theory，讨论微弱信 号的检测问题，形成信息理论的另一个分支。信号检测可以分为确知信号检测和具有随机参量的信号检测，重 点研究如何从干扰中提取信息。一般信息论的研究包括噪声理论、信 号的滤波与预测、统计检测与估计理论、调制理论、信号处理与设计 理论等，它是广义通信问题的理论提升。香农和维纳的研究成果为通信和控制理论与技术的发展做出了开 创性的贡献，可以名副其实地称为信息理论的创始人。但是由于通信 技术对人类的影响更大，信息科学的理论成果与通信技术联系更多， 所以人们倾向于把香农叫做信息论的创始人。现代信息科学涉及范围非常广泛，除了传统的感测技术、通信技 术、控制技术、智能技术等以外，还涉及经济学、心理学、语言学、 社会学等其它领域，特别是近年来发展迅猛的信息安全技术，显然也 应该属于信息科学的范畴，摈弃信息安全的信息理论是不完整的信息 理论。信息安全问题是自然科学和社会科学的融合体，广义信息理论 不仅要讨论客观问题，也要涉及人的主观因素，不仅要研究自然科学 问题，也要研究与之关联的社会科学问题。广义信息论的研究需要更一般的信息概念（定义 1.5），目前尚未形成公认的理论体系，处于发 展之中。以上这种划分有一定的方便之处，它使得人们在讨论信息问题时 不至于由于概念的不统一而无谓地争执，同时它也解释了为什么很难 找到集大成的信息论，却到处可见信息论基础、导引等书的原因。信息理论的建立不仅促进了信息技术，也带动了其它学科的发 展。例如，虽然香农理论主要解答通信理论中的两个基本问题：临界 数据压缩的值（熵）和临界传输速率的值（信道容量），但是也在统计 物理（热力学）、计算机科学（Kolmogorov复杂度或算法复杂度）、统 计推断（奥卡姆剃刀）、概率统计（假设检验的错误概率及估计的误差 概率）经济学等学科中发挥了奠基性的作用。信息安全的研究不仅是 信息理论的一个组成部分，也必然促进社会管理方面的进步。图 1-3 揭示了信息科学与其它学科的关系。概率论统计学经济学计算机科学物理学数学密码学香农信息论通信理论一般信息论信息安全噪声理论、信号的滤波与预测、统计检测与估计理论、 调制理论、信号处理与设计理论信息隐藏厂义信息论经济学、心理学、语言学、社会学图 1-3 信息科学包含的内容1.4 本书内容安排本书主要讨论有关信息安全的技术，其中部分章节利用了香农信 息论的知识，因此首先在第二章介绍了香农信息论的基本概念和几个 重要定理。然后进入信息安全的内容。第三章是对信息安全的概述，主张从系统和运动的观点来看待信 息安全问题，其中许多思想来自网络技术，但是并不意味信息安全问 题为网络技术所独有。在这一章里，我们把信息安全概念分为三个层 次，即A1安全、A2安全和A3安全，从而使信息安全问题更加系统 化。此后，我们在第四、五、六章中集中讨论 A1 安全，涉及信息加 密、信息隐藏、认证和签名技术。这一章涉及的内容非常厂泛，要在 有限的篇幅里进行详细的论述是不现实的，因此我们不提倡用对具体 算法的深入取代对全局的宏观了解，这样更有利于思路的开阔。第七、八两章讨论A2安全，涉及访问控制、入侵检测、DoS攻 击、恶意软件和黑客技术。其中许多内容是网上零散信息的归纳。我们在第九章中讨论 A3 安全，主要是对不良信息的处置。由于 最有效的处置不仅限于技术层面，法律约束、行政管理可能具有更大 的威力，但那不是本书的任务。最后，第十章对工作中遇到的某些实际问题进行了讨论。这些内 容具有两个特点，要么对不同的实际情况而没有具体深入讨论，要么 涉及容易忽视的现象而没有什么理论价值。 应该指出，自然科学与社会科学的融合使得信息安全理论难于用 公式进行形式化的描述，对其涵义的分类帮助我们在逻辑上有了一个 系统的看法。第二章：香农信息论基础尽管香农信息理论很难处理近些年来出现的信息及信息安全问 题，但是其基本思想对现代信息技术的发展仍有重大影响，本章将叙述香农信息论的基本概念和几个定理，目的是有助于对第四章、第五章内容的深入理解，而不是对香农信息论的全面介绍。在以下讨论技术问题的章节里，我们将遇到大量的公式，需要读 者静下心来，弄清每个符号、每个公式的物理意义，从中学习定量分 析问题的方法思路，不要死记硬背。2.1 基本概念2.1.1 自信息在阅读这一章内容时，我们要使用香农的信息概念。正如绪论 所述，香农信息和第三章里的信息之间存在差别。香农信息可以度量，为定量地解决通信速率、效率奠定了基础 那么，这个可以度量的信息概念是怎样建立起来的呢？让我们先看一 下实际的例子。假设天气预报只预报明天是否下雨，那么只要给出一个符号就 可以表达清楚了，例如用 1 表示下雨，用 0 表示晴天。假设要发布“嫦 娥一号”月球卫星发射成功与否的消息，也只需要一个符号，例如用 符号 1 表示发射成功，用符号 0 表示发射失败。一般地说，我们可以 用符号 1 或 0 表示一个随机事件（下雨或发射成功）是否发生。和通信过程联系起来，符号来源于消息的发送者，也就是来源 于信息源。我们把这种用一个符号就可以表示一条完整消息的信息源 叫做单符号信源。但是多数情况下，随机事件集合中可能包含多个元 素（例如天气预报有暴雨、大雨、中雨、小雨和雷阵雨之分），这时 仅用一个符号就不能反映发生了哪个具体事件，需要用符号序列来代表各个具体事件，消息源则变成发出符号序列的信息源。正规地，如果信源输出是随机变量 X 所表示的随机事件，其出现概率是P(X)，则它们所构成的集合叫做信源的概率空间，简称信源空间，用如下方式表示：X , P ：X：-y*-y* -y*1 2 nP(X)：P (x1) , P (x2) , , P (xn)(2-1)其中P ( X)满足z n p (x ) = 1，n是自然数。i=1 i干旱地区下雨的可能性是很小的，设其概率为0.1，而晴天的概 率为 0.9。因为我们通常认为在干旱地区不会下雨，一旦气象台发出符号 1，我们就得到了较大的信息量，反之，预报天晴和我们原来的想法一致，就没有太多的信息量。这说明信息量应该是概率的函数， 而且概率越大信息量就越小，即信息量是概率的减函数。考虑到概率 可以在0， 1区间内连续取值，所以信息量是连续函数较为合理。概率等于 1 的必然事件是一定要发生的，它的出现不会给我们带来任何新的信息，信息量应该为0；而对于概率等于0 的不可能事 件，一旦出现将给我们带来极大的震撼，其信息量应该是无穷大。再假设天气预报不仅预报明天是否下雨，而且公布空气污染指 数，那么听众得到的信息就包含两部分互相独立的内容，这时的联合 信息量应该是两个信息量之和。根据上面介绍的信息量应该具有的属性，我们选择对数函数来 度量信息量。定义2.1事件x.的出现所带来的信息I (xi )二 log 1/ P (xi )二- log P (xi )(2-2)称为事件x i的自信息量。可以看到，上述定义完全符合信息量应该具有的属性，因此是 合理的。但是这个结果没有量纲，会为以后的研究带来不便，为此， 我们根据对数的底来规定信息量的量纲：以2为底时用lb表示，信 息量的单位是比特(bit)；以e为底时用In表示，信息量的单位是奈 特(nat)；以10为底时用lg表示，信息量的单位是哈特(Hart)。以下如果不作特殊说明，我们将习惯地使用更具一般性的符号 log,但是以2为底来计算数值。例 2.1 设有一个符号 1 、0 等概率出现的随机信源，求任一码元 的自信息量。解 I(xi)二一l o Pg)二一l o g/2 = 1 (bit), x i = 0 或 1。例22对于2 n进制的数字序列，假设每一符号的出现完全随机 且概率相等，求任一符号的自信息量。解 因为2n进制的数字序列中任一码元X 的出现概率都相等，i所以其信息量为I(x.) = -log P (x.) = -log 1/2n = n (bit)由此例可以看出，一个事件的自信息量只取决于事件出现的概 率，与它的内容或取值无关。212 熵式(2-2)的定义是从通信的角度考虑的，它表示信宿收到一条 消息以后所得到的信息量。现在设想信宿处于尚未收到消息的等待过 程中，那么将来的消息如何对它来说是不确定的，而一旦收到消息，这个不确定量就消失了。所以一个随机事件出现所给出的信息量就应 该等于该随机事件的不确定程度。考虑到某些情况下，事件的不确定 程度不会完全消失，所以一般地说，随机事件出现所给出的信息量是 该事件不确定度减少的数量。随机事件的不确定度也是概率的函数。它与信息量不同之处是 并不要求该随机事件真的发生。公式(2-2)中的I (x)表示的是信源发出某一具体符号x)的自信息量。当随机事件集合中包含多个元素，且每个元素的概率不相等时， 用式(2-2)只能计算每个元素各自的自信息量，不能作为整个随机 事件集合的总体信息测度。下面的例子就是这种情况。例 2.3 假定有 8 匹马参加的一场赛马比赛，它们获胜的概率分 别是 1/2, 1/4, 1/8, 1/16, 1/64, 1/64, 1/64, 1/64, 计算每匹马获胜给出的 自信息量。解 第 1 匹马获胜的信息量是第2匹马获胜的信息量是第3 匹马获胜的信息量是第4 匹马获胜的信息量是I (x 1)= - log (1/2) = 1；I (x2)= - log (1/4) = 2；I (x3)= - log (1/8) = 3；I (x4)= log (1/16) = 4；第58匹马获胜的信息量是I (x 58)= - log (1/64) = 6。5-8例中得到了 5 个不同的结果，其中任何一个都不能代表赛马比 赛的总体信息测度。但是比赛结果的不确定度应该有一个确定的值，显然，我们可以计算其平均值作为不确定程度的测度。但是若如下计算，所得结果是不正确的，因为它没有反映每匹马获胜的概率。I = Q 8 i(x.)/8 = 4.25i=11正确的结果应该是各个自信息量的加权平均。我们把这个加权的平均自信息量叫做熵。定义2.2若随机事件集合X包含n个元素，x2，x,它们的 12n出现概率分别是P (x 1), P (x 2),，P (x n),则随机事件X的熵是: H(X) = X P(x.)I(x.)=工 p(x)log p(x)i=1.X(2-3)考虑到当x - 0时，有x log x -0,今后约定0 log 0 = 0。这个 定义和通信过程没有直接的关联，它具有一般性。有了熵的定义，我们就可以计算例 2.3 中赛马结果的不确定性，或者比赛的总体信息测度了：H (X) = -1/2 log 1/2 - 1/4 log 1/4 -1/8 log 1/8 - 1/16 log 1/16 -4 (1/64 log 1/64 ) = 17/8在概率论中，我们曾用符号E表示统计平均，或叫数学期望：E严 J(x)P(x)(2-4)对比公式(2-3)，也可以把随机事件的熵写成数学期望的形式：H(X)= Eplog1/P(X)(2-5)其中g(x) = log1/ P(x)。这就进一步地强调了熵是统计平均意义上的概念。面来看熵的两条基本性质。性质(2-6)Hb(X)=(logb a)Ha(X) b b a性质(2-7)证明(1 )丁0 W p (x) W 1,.logp (x) W 0,H(X) = Y p(x) log p(x) 0X(2)根据对数换底公式log p (x) = log b a) log p (x),直 bba接得到性质 2.2 的结果。第二个性质使得我们可以改变定义中对数的底,只要乘上适当的常数,熵就可以从一个底换成另一个底了。例2.4设X = 0,1, P (1) = p, P (0) = 1-p,计算随机事件集合x的熵。解 H(X)=plog p (1 p) log(1 p)对式中的概率取不同的值,可以计算出对应的熵,把它绘制成 曲线如图3-1所示。可以看到，当p = 1/2时，H (X) = 1比特，取得 最大值。当p=0或1时，H (X) = 0。这个例子告诉我们，熵是关于概率的凸函数(有的书上叫做凹函数，或者叫上凸函数，其实都在表达同一个意 思：曲线的二阶导数小于 0)。上述结果可以推广到随机事件集合的情况。X = x , x , , x 1 2 m如果X符合均匀分布，则熵取得最大值H(X) = log m。考虑到可以把随机事件集合看作是一个随机变量，集合中各 具体事件是该随机变量的取值，所以也可以把随机事件集合X的熵说成是随机变量X的熵。图 2-1 熵与概率的关系曲线