离散信息论基础

出版时间：2010-8  出版社：北京大学出版社  作者：范九伦,谢勰,张雪锋  页数：195  

前言

　　人们通常将Shannon在1948年10月发表于.Bell System Technical Journal上的论文A Mathematical Theory of Communication作为信息论研究的开端。信息论发展至今，可分为狭义信息论和广义信息论，本书则主要介绍狭义信息论的一些基本知识。狭义信息论运用概率论与数理统计方法研究信息的表示、度量、存储、传递等问题，是高等院校很多本科专业的一门专业基础课，我国众多高校也在相关专业开设了信息论课程。　　在为信息安全、信息与计算科学等本科专业讲授信息论课程时，我们深刻体会到，要使大学生较好地理解和领会信息论的基本概念，诸如熵、互信息、熵率、信道容量，有很多困难。在多年的教学中，我们一直被两个问题所困惑：一是鉴于信息论不仅具有理论性，也具有实践性，如何保持信息论基本概念、方法在理论叙述上的严谨性，使得学生对信息论有一个清晰的认识，同时又能使学生通过解决实际问题，达到运用信息论的目的；二是鉴于信息论不仅在本科生阶段开设，也在研究生阶段开设，如何将本科讲授内容和研究生讲授内容进行合理切割，尽量避免教学内容重复，使得知识深度与思想广度在不同阶段有所区别。为了较好地解决上述问题，我们萌发了写作本书的念头。在本书的写作中，我们力求达到以下几点。　　（1）图文并茂、循序渐进。本书按照教学目标、教学要求、教学内容的格式进行编写，以叙事、问题的方式展开，改变工科教材艰深古板的固有面貌，具有较强亲和力，使学生初次翻阅就对其产生浓厚兴趣，不会因其理论的抽象而产生敬畏之感。既加强了学生的融会贯通能力，又提高了学生的人文素养。　　（2）凸显信息论的“离散”内容。信息论的研究和应用丰富多样，为了扩大教材的受益面，避免涉足过多的专业领域知识，本书重点围绕离散随机变量（过程）介绍信息论的基本知识，主线明晰，增强了教材的可读性。考虑到信息论的介绍离不开概率论和数理统计知识，本书弱化了数学证明，强化了来龙去脉的讲授，使之显得通俗易懂，同时又给学有余力者留下充足的探求空问。　　（3）强化学生的实际操作训练。对于内容实用性和技巧性较强的章节，如编码理论部分，本书精心设计了相关实验，以实际操作训练加深对理论知识的理解，激发学生对工程实践的兴趣，全方位锻炼学生对知识的掌握程度。　　在教材写作中，我们努力将最新的知识、内容和理念传授给学生。本书以离散随机变量（过程）为出发点进行展开，力求以亲切易读的面貌，帮助初学者熟悉必要的理论知识，掌握其思想方法，了解其应用前景，为后续课程和进一步深入学习打下坚实基础。本书共分为9章：第1章和第9章由范九伦和谢勰共同编著；第7章由张雪锋编著；其余部分由谢勰编著。全书由范九伦进行统稿和润色。

内容概要

　　《离散信息论基础》从离散概率人手，对离散信息论的基本知识进行了介绍，主要内容包括：绪论，离散信息的度量，数据压缩，离散信源，数据纠错，离散信道，数据保密，算法信息论与通用信源编码，微分熵与最大熵原理。为拓宽读者视野，培养学习兴趣，提高人文素养，《离散信息论基础》融人了一些历史知识，还补充了信息论实验内容。　　《离散信息论基础》可供信息安全、信息与计算科学、计算机科学与技术等本科专业的高年级学生使用，也可供从事相关专业的教学、科研和工程技术人员参考。

书籍目录

第1章 绪论1.1 基本概念1.1.1 信息的含义1.1.2 信息的表达1.1.3 信息的处理1.2 信息论概览1.2.1 Shannon与信息论1.2.2 通信系统的数学模型本章小结习题第2章 离散信息的度量2.1 基本概念2.1.1 离散熵的定义2.1.2 联合熵与条件熵2.1.3 相对熵与互信息2.2 离散熵的性质2.2.1 离散熵的基本性质2.2.2 链式法则2.2.3 有关离散熵的不等式2.3 离散熵的形式唯一性本章小结习题第3章 数据压缩3.1 基本概念3.1.1 语言与编码3.1.2 匡一可译码3.1.3 即时码与前缀码3.2 数据压缩的性质3.2.1 前缀码的码长约束3.2.2 唯一可译码的码长约束3.2.3 最佳码3.3 典型编码3.3.1 Huffman编码3.3.2 Fano编码3.3.3 Shanno一Fano-Elias编码本章小结习题第4章 离散信源4.1 基本概念4.1.1 离散信源模型4.1.2 Markov信源4.1.3 Markov链4.2 信源编码4.2.1 随机变量扩展4.2.2 变长信源编码定理4.2.3 熵率4.3 渐近均分性4.3.1 典型集4.3.2 信源编码定理本章小结习题第5章 数据纠错5.1 基本概念5.1.1 离散信道模型5.1.2 典型信道5.1.3 信道扩展5.2 信道纠错5.2.1 译码准则5.2.2 错误概率估计5.2.3 分组码5.3 线性分组码5.3.1 码字距离5.3.2 纠错能力5.3.3 Hamrning码本章小结习题第6章 离散信道6.1 基本概念6.1.1 互信息6.1.2 特殊信道的容量6.1.3 一般信道的容量6.2 数据处理6.2.1 码率6.2.2 数据处理不等式6.2.3 信源信道定理6.3 信道编码6.3.1 联合典型集6.3.2 信道编码定理6.3.3 信道编码逆定理本章小结习题第7章 数据保密7.1 信息的保密传输7.1.1 密码学简介7.1.2 保密系统模型7.1.3 几种典型的密码体制7.2 密码体制的信息论分析7.2.1 完全保密性7.2.2 唯一解距离本章小结习题第8章 算法信息论与通用信源编码8.1 基本概念8.1.1 统计编码8.1.2 自适应编码8.2 描述复杂性8.2.1 Kolmogorov复杂度8.2.2 通用概率8.3 通用信源编码8.3.1 算术编码8.3.2 字典方法本章小结习题第9章 微分熵与最大熵原理9.1 基本概念9.1.1 微分熵9.1.2 信息不等式9.2 信息量最大化9.2.1 最大熵问题9.2.2 最大熵分布本章小结习题信息论实验参考文献

章节摘录

　　由于投掷硬币问题比较简单，可采用此例对信息展开讨论，而其关键在于如何描述该系统。事实上，单次过程无法显露问题的本质，可假设上述过程多次重复。　　直观上看，若有一台摄影装置记录投掷硬币的全过程，即可认为该摄影装置的录像完全描述了投掷硬币系统。为简单起见，可假定投掷人每次投掷动作完全一致，所有落地后硬币正面朝上情况下的硬币运行轨迹完全相同，所有落地后硬币反面朝上情况下的硬币运行轨迹也完全相同。　　问题1对于投掷硬币系统，摄影装置应如何设置才能高效地录制该系统的运行过程？　　由于摄影装置有容量限制，较好的方法是仅录制落地为正面朝上和落地为反面朝上的投掷过程，其后的投掷只需要录制硬币的朝向，便可完全复原硬币投掷过程。当然这仅仅是一个最简单的方案，它仍可改进。注意到此方案每次需要录制硬币朝向形成的图像，即硬币的正面和反面，其实质是利用图像的直观性获取结果。而人类不仅能用图形表示信息，还可用文字表达信息，例如可用“正”、“反”来简单表示硬币的朝向。对于摄影装置而言，还可用数字来简单表示硬币的朝向，即硬币的朝向仅用0和1（分别代表“正”和“反”）来表示。这意味着信息与其载体的形式无关，或者说与编码形式无关，因此可采用数值方式来表示和研究信息。　　由于采用数值化的表达形式，摄影装置中除了每次投掷动作的录像之外，余下的就是一连串的0和1组成的序列。如果录制时间足够长，摄影装置中的大部分内容均为O和1的序列，而投掷动作的录像已不再是主要内容。从复原投掷行为的角度看，摄影装置中存储的内容完全反映了投掷信息，即0-1序列反映了投掷过程的主要信息。那么，如何揭示获得的O一1序列含有的信息？或者说，面对这些0-1序列，能得到投掷过程所含信息的何种结论？为此，可借助物理学的思考方式对信息进行更深入的讨论，注意到大部分物理术语都有度量单位，这提示人们信息也应有度量单位。