本书从工程应用角度，用大量实例，系统地讲述了编码与信息理论。主要内容包括：离散信源和熵、信道和信道容量、游程长度受限码、线性分组纠错码、循环码、卷积码、网格编码调制、信息论和密码学、仙农编码定理等。 作者在讲述深奥理论的过程中，尽量避开以往理论化、形式化、论证式的组织形式，以不拘泥形式的、富于趣味性的、易于接受的陈述方法，紧密结合工程实践，将编码与信息理论的知识呈现在读者面前。 本书适合作为高等院校通信、信息、电子等相关专业的教学用书，也可供相关工程技术人员参考。

出 版 说 明 在人类迈入信息时代的今天，信息技术的应用无处不在，我国对信息技术的重视和鼓励也达到了空前的程度。信息技术的发展速度很快，可谓日新月异，尤其在一些发达的国家更是如此。我国信息技术起步较晚，但发展速度惊人，这正是改革开放的具体体现。在我国大力发展信息产业的今天，为了能融入国际的潮流和掌握最新的技术，从国外引进先进的知识和技术就显得格外重要。为此，我们决定引进一系列国外信息技术领域有代表性的优秀教材，将它们献给我们的学子、教师和IT业的有志之士，藉此为我国的信息产业贡献一份微薄之力。 随着我国加入WTO，国际间的竞争将越来越激烈，而国际间的竞争实际上就是人才的竞争、教育的竞争。为了加快培养具有国际竞争力的高水平技术人才，加快我国教育改革的步伐，使我国的高等教育尽快与国际接轨，这就需要引进先进的教学思想和教学方法，而引进国外优秀的教材无疑是一种很好的途径。同时，引进国外的优秀教材也有利于提高我国自编教材的水平，让我们的教育工作者从中得到启发。 我们这套丛书遵循“新、优、特”的原则，做到知识新、质量优和内容有特点。这套丛书涵盖了计算机、通信、电子技术等领域，每一本书都是精心挑选，在某个领域或学科内具有很强的代表性和很高的价值，很多在国外也被作为大学的教科书，由国际知名的出版公司出版。在引进过程中，我们邀请有关专家对书稿的整体水平进行了评定；在翻译过程中，我们聘请国内相关领域内的有很高学术水平的专家和学者，以保证书籍的水平和质量，做到对读者负责，为读者着想。 相信这套丛书的出版对正在苦读和即将面临挑战的学子们会有很大的帮助和提高，也能让我们的教学工作者从中得到启发，同时对从事IT行业的工程技术和研究人员而言也是很难得的工具书。 译 者 的 话 本书是一本有关编码与信息理论的入门性教科书，与传统的相同体裁的教科书相比有很大不同。本书考虑的读者对象是面向应用的工程师和不具有很多近代代数知识的大学本科高年级学生或者低年级的研究生。本书在写作手法上抛弃了传统的“定理—证明”的讲述方式，而是代之以更多的实际例子，向面向工程的学生们讲述编码与信息理论的基础知识。本书内容较为丰富，涵盖了信源编码、信道编码（分组码、卷积码和TCM码）、数据变换码、密码学和仙农信息论等方面的内容，适合作为相关专业高年级本科生和低年级研究生的学习用书，也可作为工程技术人员的参考工具。 本书由北京邮电大学电信工程学院尹长川副教授主持翻译。其中尹长川负责前言及第1、3章的翻译，罗涛负责第5、9章和习题解答，秦升平负责第2章，吴军力负责第4章，滕勇负责第6、7章，王健康负责第8章的翻译。尹长川、罗涛、吴军力和侯晓林负责全书译稿的校对，并由尹长川负责全书的统稿。乐光新教授审阅了全部译稿并提出了若干改进意见。 由于时间仓促，加之译者水平有限，错误和不当之处在所难免，敬请各位读者批评指正。 译者 前言 欢迎学习信息与编码理论。正如大家所说，我们正生活在信息时代的黎明，这是一个被比作下一次工业革命的时代。虽然这种看法经常被提及，以致于显得有些老生常谈，但是这个新时代对于商业、工业和社会的潜在重要性是不管怎么说都不会夸大的。当工业革命到来的时候，随之带来的新需求要求人们在技术科学、艺术和技能方面都要熟悉。类似的道理，随着信息革命带来的是需要大量的人员通晓和掌握应用于多种用途的信息技能。 本书是为初学者写的。其取材来源于我为电气与计算机工程、计算机科学以及数学专业的本科生所开设的一门课程的课堂讲义。这本书的讲述水平是面向三年级或四年级的在校本科学生和很少或从未接触过本专题的有实践经验的工程师。这本书的目的是帮助大家在信息工程的实践方面开始起步。 近些年来，有关本专题的入门性的教科书实际上已完全绝迹。市场上确实有一些很好的研究生水平的教科书，但是对于那些需要掌握面向市场能力、任务繁重的新学生，或者正在寻找入门性的资料以便可以从紧急的新项目上起步的专业人员来说，这些教科书经常是有点太理论化而较少论及实践了。考虑到这些读者，我故意放弃了在有关本专题的多数课本上所看到的那种传统的“定理—证明”的方式。虽然本教科书的材料里也有定理出现，但是我已经试着以这样的方式组织本书的结构，即将所需的数学推导紧接在“如何”应用这些方法和定理的前面。这样，书中没有浓缩所有数学定理的大章节，各数学专题只有在需要的时候才以“救急”的方式进行介绍。 这本教材里的材料足够用做大学三年级或者四年级一学期的课程。本教材假定读者以前具有初等线性代数和基本概率论方面的知识背景。数字逻辑设计或者初步的通信系统方面的先修课程，对于本课程的学习是有帮助的，但不是必需的。 第1章首先对数字通信系统进行了讲述，并引入了信息的概念。我发现当学生们学到“信息”和“数据”是不同的概念时经常会感到惊奇。本章介绍了离散信源以及熵和联合熵的基本概念，由此引出了用于数据压缩的信源编码的介绍，我们将理论应用于霍夫曼（Huffman）编码、莱姆培尔兹夫（LempelZiv）编码和算术编码。对信源建模和自适应编码的内容只进行了简单介绍，但是为希望深入学习这些重要专题的读者提供了参考文献。 在第2章我们继续进行信息理论的学习，引入了离散无记忆信道的概念。在描述和定义了这些信道之后，我们介绍了互信息和信道容量，描述了用于计算离散无记忆信道的信道容量的阿里莫托布拉哈特（ArimotoBlahut）算法。我们还比较详细地介绍了非常重要的二进制对称信道，由此引出了分组编码的思想和著名的仙农（Shannon）第二定理。本章还介绍了马尔可夫（Markov）过程和有记忆信道，并由此向大家引出了许多重要概念。接下来介绍了受限信道，以及序列的自相关函数和功率谱的重要概念。在本章的最后，我们将理论应用于数据变换码（data translation codes），并介绍了游程受限（d, k）码。 整个第3章都是有关应用方面的内容，如果教学时间有限，教师可以跳过这一章而不影响内容的连续性。本章是有关一类特殊的数据变换码，该类编码具有多种名称，分别被称做线路码、调制码或游程长度受限码。在本章里综述了前置分组编码技术，包括状态独立的固定码率/固定分组码、用于固定长度分组码依赖于状态的编码、可变长度/固定码率的分组码、前视码（lookahead codes）。在本章的最后，简单介绍了无直流电平码。 第4章介绍了线性分组纠错码的一般理论。本章首先讨论了编码问题和有噪信道上的错误概率计算，接下来讨论了使用二进制重复码进行错误纠正以及一些重要的界和线性分组码必须遵循的限制。接着给出了与二元域和二元矢量空间有关的一些简单背景，为更理论化的导出代数编码作准备。随后介绍了汉明（Hamming）距离、汉明重量和汉明立方体的基本思想以及一些重要的数学定义和概念。介绍了采用标准阵的译码方法，定义了系统分组码。由此引出了对汉明码的深入讨论，这是我们最先遇到的“重要的”实用码。在讨论基本汉明码的同时，我们还讨论了一些有用的“变体”，包括对偶码和扩展汉明码。讨论了用于纠错和检错的编码。在本章的最后，讨论了线性分组码的差错率以及用于纠错码和自动请求重传系统的码的性能。 第5章继续讨论线性分组码，介绍了循环分组码。在讨论了基本定义和性质之后，介绍了循环码的多项式表示，并讨论了用于由二元域构造的多项式的求模算术。接着将注意力转移到了用于循环码的产生和译码的有效方法上，给出了许多用于实现编码器和译码器的实用电路。在本章的最后，我们给出了几种有用且重要的标准码，包括汉明码（本章再次提到）、一些简单的BCH码以及一些好的纠突发错误码。本章还讨论了使用循环冗余校验（CRC）码的错误检测以及一些有用的“变体”，包括交织和截短码。 在第6章中，我们从分组码转到介绍卷积码。在讨论了基本编码器之后，我们考察了卷积码的一些结构特征以及这些码的状态图和结构图表示，讨论了码的传递函数表示及其用途。我们还深入讨论了维特比（Viterbi）算法。这里的讲法与多数的课本和文章里的讲法不同，在描述为什么该算法能工作之前，我们首先描述了该算法是什么以及是如何工作的。据我的学生们反映，这种讲法上的次序颠倒比传统的教学法更容易被接受。我们讨论了硬判决和软判决维特比译码，并比较和讨论了这两种方法的性能差异。接着以列表的形式给出了一些已知的好卷积码。我们从维特比算法回到讨论一些实际的实现问题，包括译码的回溯（traceback）方法和使用凿孔（punctured）卷积码以获得更高的码率。 第7章是对网格编码调制的简单介绍。我们介绍了二维IQ信道以及用于这些信道的发送机和接收机，讨论了用于相位调制和正交幅度调制系统的编码信道的错误概率特性。然后介绍了系统递归卷积编码器及其网格图表示，讲述了昂格尔博克（Ungerboeck）的典型编码器，并使用奇偶校验多项式给出了TCM码的八进制表示。接下来讨论了集合分割以及如何使用集合分割来构造使用昂格尔博克编码器的TCM码。在本章的最后扼要地给出了用于相位调制和正交幅度调制的一些好码。 第8章简要介绍了信息论在密码学方面的应用。本章首先介绍了一些基于密码的简单保密系统，并简要描述了一些可以用来攻击保密系统的方法。接下来介绍了仙农（Shannon）的完善保密性的定义，并导出了达到完善保密的条件。随后讨论了自然语言的熵率以及在密码分析学中如何利用自然语言的冗余，由此引出了虚假密钥和惟一解距离的重要概念。接下来讨论了计算安全性问题，描述了仙农的扩散和混淆技术，由此引出了乘积加密系统的重要技术。最后，本章简要描述了编码、公开密钥保密系统以及某些其他问题。公开密钥保密系统虽然很重要，但是因为公开密钥保密系统的理论更牵涉到数论而不是信息论，所以本章并未对其进行深入描述，但是向读者提供了几本好的参考文献，以供随后进一步了解公开密钥加密的理论和实践。 第9章是本书的最后一章。在这一章中，给出了二进制对称信道这一特殊情况下仙农第二定理的证明，介绍了随机编码理论的思想，并讨论了该定理向我们说明和没有说明的内容。接下来我们将注意力转到对仙农无噪声编码定理和用于进行信源压缩的前置码存在性的推导。在本章的最后用几句话对信息论进行了总结，并向读者指出了进一步学习的方向。 虽然在讲述编码与信息理论时一定程度上的循规蹈矩是必要的，但是在本书的讲述中，我尝试着有时使讲解尽可能的不那么正规，读者会不时地读到作者的一些轻松愉快的评注。作者相信，“如果课本写作时有其轻松愉快的时刻，难道阅读的时候就不能也有这样的时刻吗?”在有关此类专题的传统研究生水平的课本中，编码与信息理论的一个更重要的方面是缺少趣味性。在本书对数学理论的陈述中，我已经试着不舍弃这种趣味性。 很显然，作者在本书的编写过程中所起的作用是重要的，但是课本的价值不在于作者，而是在于其所要服务的读者。此外，任何一本教材（特别是本书）的存在都应归功于为其作出过贡献的许多人。想到此处，我首先要感谢我的学生们，他们对手稿、课后练习和题解手册向我提供了大量的反馈意见。我还要感谢艾劳恩·布雷南（Aaron Brennan）先生，感谢他帮助设计了一些课后练习。我要特别感谢滑铁卢（Waterloo）大学的乔治·弗里曼（George Freeman）博士，他富有洞察力的评价和建议在很大程度上提高了本书的质量。最后，我要感谢PrenticeHall出版社快乐班子（merry band）的爱丽丝（Alice）、汤姆（Tom）和其他的人，虽然他们很少被作者提及，但是正是他们的努力使得本书比手稿有了很大提高。 Richard B. Wells

出版说明
译者的话
前言
第1章 离散信源和熵
1.1 数字通信和存储系统概述
1.2 离散信源和熵
1.3 信源编码
1.4 霍夫曼（Huffman）编码
1.5 词典码和莱姆培尔-兹夫（Lempel-Ziv）编码
1.6 算术编码
1.7 信源模型和自适应信源编码
1.8 小结
1.9 习题
参考文献
第2章 信道和信道容量
2.1 离散无记忆信道模型
2.2 信道容量和二进制对称信道
2.3 分组编码和仙农（Shannon）第二定理
2.4 马尔可夫（Markov）过程和有记忆信源
2.5 马尔可夫链和数据处理
2.6 受限信道
2.7 序列的自相关和功率谱
2.8 数据变换码
2.9 （d,k）序列
2.10 小结
2.11 习题
第3章 游程长度受限码
3.1 数据变换码的一般考虑
3.2 前缀码和分组码
3.3 状态依赖固定长度分组码
3.4 可变长度固定码率码
3.5 前视（look-ahead）码
3.6 无直流码
3.7 小结
3.8 习题
参考文献
第4章 线性分组纠错码
4.1 一般考虑
4.2 二元域和二元矢量空间
4.3 线性分组码
4.4 线性分组码的译码
4.5 汉明码
4.6 线性分组纠错码的差错率性能界
4.7 采用请求重传的限定距离译码器的性能
4.8 小结
4.9 习题
参考文献
第5章 循环码
5.1 循环码的定义和性质
5.2 循环码的多项式表示
5.3 多项式模运算
5.4 循环码的生成和译码
5.5 错误捕获（Error-Trapping）译码器
5.6 一些标准循环分组码
5.7 循环码的简单改进
5.8 小结
5.9 习题
参考文献
第6章 卷积码
6.1 卷积码的定义
6.2 卷积码的结构特性
6.3 维特比（Viterbi）算法
6.4 维特比算法的工作原理I-硬判决译码
6.5 一些已知的好卷积码
6.6 维特比算法的工作原理II-软判决译码
6.7 维特比译码的回溯（Traceback）方法
6.8 凿孔（Punctured）卷积码
6.9 小结
6.10 习题
参考文献
第7章 网格编码调制
7.1 多幅度/多相位离散无记忆信道
7.2 系统递归卷积编码器
7.3 信号映射与集合分割
7.4 已知PSK和QAM的好网格码
7.5 小结
7.6 习题
参考文献
第8章 信息论与密码学
8.1 密码系统
8.2 对密码系统的攻击
8.3 完善保密性
8.4 语言熵和成功密文攻击
8.5 计算安全性
8.6 扩散与混淆
8.7 乘积加密系统
8.8 编码
8.9 公共密钥系统
8.10 其他问题
8.11 小结
8.12 习题
参考文献
第9章 仙农编码定理
9.1 随机编码
9.2 平均随机码
9.3 对仙农第二定理的讨论
9.4 仙农-费诺编码
9.5 仙农无噪声编码定理
9.6 最后的话
参考文献
附录 部分习题答案