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