信息论、错误控制编码和密码学是现代数字通信系统中的三大支柱，本书用有限的篇幅将三者中所有重要的概念有机地结合起来，涉及信息论、信源编码、信道编码和密码等方面的知识，不仅内容丰富，而且技术深度适当。

信息论、编码与密码学（第2版）
Information Theory, Coding and
Cryptography Second Edition
(印) Ranjan Bose 著　武传坤 李徽 译

大多数介绍信息论、编码和密码学的书，不是太过数学化，就是太注重基础。本书避免了上述缺点，既考虑到数学的严谨性，又充分考虑了易读性。在第2版中我们收录了许多正在产生的、成熟的或者已经在工业标准和应用中使用的新概念和新想法。

本书特点：
数学论证后面都接有信源编码的直观解释。
涵盖更完整的知识面，包括线性分组码、循环码、BCH码和RS码等。
完整覆盖卷积码、Turbo码和网格编码调制（TCM）。
全面介绍密码学基础、公钥和私钥加密、当前的加密标准及密码学最新趋势。

本版更新内容：
新增关于空时分组码和空时网格码的介绍。
在Turbo码和网格编码方面进行了内容扩展。
新增内容有
·算术编码　　　　　　　　　　·Turbo码的交织器设计
·MIMO信道　　　　　　　　　·椭圆曲线密码学
·低密度奇偶校验（LDPC）码　·量子密码学
·最小距离的界　　　　　　　　·生物加密

作者简介
Ranjan Bose
在美国宾夕法尼亚大学获电气工程博士学位。曾在位于美国加利福尼亚州圣何塞的Alliance半导体公司任高级设计工程师。现任印度理工学院教授。2003年荣获印度国家工程师学会（INAE）颁发的“杰出青年工程师奖”。

第2版前言
　　从2002年本书英文第1版问世以及随后的9次重印中，我收到了许多热情读者的来信以及在各种会议上的信息反馈。他们给了我很大的鼓励和很多的赞美之词。信息论、编码和密码学领域正在不断扩张，并且在过去的六年里，有很多新的思想产生、成熟，然后在行业标准和应用中采用。在第2版中，我们收录了许多新的知识，这能帮助那些从工科学院毕业的学生们和一些工程师们更快更有效地学习这些知识。
　　新版共添加了14个小节、23个新例子以及48个新练习问题。增加这些内容的目的有两个：
　　(1) 可以更加完整地介绍知识。这样的内容有：Shannon-Fano-Elias编码、算术编码、随机过程的熵率、马尔可夫链的熵率、最小距离的界、截短循环码、Reed-Solomon编码器详细的硬件实现、Diffie-Hellman密钥协商协议等。
　　(2) 可以向读者介绍当前研究趋势—那些在实际系统中应用的理论。这样的内容有：多输入多输出（MIMO）信道、MIMO系统的信道容量、低密度奇偶校验（LDPC）码、空时码、Turbo码的交织器设计、量子密码学、生物加密等。
　　本书的读者是电机工程系和计算机科学系的低年级研究生和高年级本科生。同样，本书也可以为那些希望开阔知识面并且掌握新技术的工程师们提供便利。
　　本书的结构非常适合作为研究生阶段的一门完整课。如果针对高年级本科生，下面一些章节可以跳过：1.11，1.13，2.7，2.8，3.14，3.15，4.11，5.8，5.9，5.10，6.13，7.7，7.8，7.9，8.13，8.14，8.15，8.16和8.17。上面所选择的章节同样可以作为研究机构为业界人士提供短期培训的内容。
　　下面是新版中增加的内容：
　　第1章：Shannon-Fano-Elias编码、算术编码、随机过程的熵率和马尔可夫链的熵率。
　　第2章：多输入多输出（MIMO）信道、MIMO系统的信道容量。
　　第3章：低密度奇偶校验（LDPC）码、最小距离的界、空时分组码。
　　第4章：准循环码和截短循环码。
　　第5章：Reed-Solomon编码器详细的硬件实现，实信道上RS码性能。
　　第6章：Turbo码的交织器设计。
　　第7章：空时格码。
　　第8章：素数、复杂性类、椭圆曲线密码学、Diffie-Hellman密钥协商协议、量子密码学、生物加密。
　　所有建议、意见和问题都欢迎发信给作者，E-mail地址是rbose@ee.iitd.ac.in。
祝阅读愉快！

第1版前言
　　信息论、错误控制编码和密码学是现代数字通信系统中的三大支柱。这三个课题都很大，而且针对其中的任何一个课题，都有很多好书加以讨论。本书试图用有限的篇幅将信息论、错误控制编码和密码学中所有重要的概念有机地结合起来，而不需要将书写得很厚。本书的意图就是使之成为一本简洁而生动的书。
　　本书是我在印度理工学院（Indian Institute of Technology, IIT）教授有关信息论和编码的不同课题的成果。在写本书的时候，我必须决定数学在本书中应占的分量。引用Richard W. Hamming的话：“数学就是一种有趣的智力运动，但它不应该挡住获取物理过程中合理信息的路。”一本书若是太数学化就有吓倒缺乏强大数学功底的学生的危险。另一方面，如果需要把信息论和错误控制编码中的概念学到一定深度，那么数学的应用也不能无限度地减少。这样一来，就要掌握好分寸。我在本书中努力达到极好的折中：只有在非用不可的时候才用到数学。在可能的情况下都用直观的解释。我也相信借助实例来教学是很有效的方法，因此，当引入一个新概念时，我总试图给出至少一个例子。
如何阅读本书
　　本书不但是对信息论、编码和密码学这一令人着迷的领域的生动介绍，而且还涉及相当有深度的详细内容。全书共分三个逻辑部分：
　　第一部分：信息论和信源编码
　　第二部分：错误控制编码（信道编码）
　　第三部分：安全通信编码
　　第一部分包括两章—第1章讨论信息的概念及其有效的表示方式。信息的有效表示引起数据压缩。本章还介绍了游程编码的概念、率失真函数和优化量化器的设计。本章最后简单介绍了图像压缩。
　　第2章讨论通信信道和信道容量的概念。本章试图回答这样的问题：给定一个已知带宽和信噪比的信道，该信道每秒可传递多少比特的信息呢？这同时也提出了错误控制编码的必要性。
　　第二部分包括五章内容，都是关于错误控制编码的—第3章介绍线性分组码。线性分组码是很有实用价值、指导性强而且简单的一类码。我们将讨论这类码的编码和译码策略，同时还将介绍完备码、最优线性码和最大距离可分（MDS）码的概念。
　　第4章讨论的是循环码，这是线性分组码的子类。循环码对纠正突发性错误特别有用。Fire码、Golay码和循环冗余校验（CRC）码都是特殊类型的循环码，本章对它们也进行了讨论。本章以循环码的电路实现结束。
　　第5章将读者带到BCH（Bose-Chaudhuri Hocquenghem）码的世界，这是一类可纠正多个错误的功能极强的码。本章还讨论了Reed-Solomon码—BCH码的子类。
　　第6章讨论的是卷积码，这是一类本质上带记忆的码。本章将介绍网格码的概念并详细讨论维特比译码技术。还探讨了一些已知的好卷积码。最后介绍的是Trubo码，这是一类还不太旧的码。
　　第7章讨论网格编码调制（TCM），这是一种将编码和调制相结合的方案。本章将讨论TCM的编码和译码方法。读者将学到如何为加性高斯白噪声信道（additive white Gaussian noise channel）及衰退信道设计TCM方案。
　　第三部分仅包含关于密码学的一章—第8章，将介绍编码的另一种用法，即在安全通信方面的编码。本章将通过实例分别讨论保密密钥和公钥加密技术。还将讨论单向散列和应用浑沌函数进行加密等其他技术。本章在结尾时给出了关于密码学政治因素的一个注解。
　　我试图在所有需要的地方引入实例。每章在结束时都有一个结论性的评论，包含描述重要结果和贡献来源的简单历史性评注。每章最后还有一个简单总结，可作为概括性参考或对某一特殊公式或定义的快速查找工具，也可直接为读者考试前的准备增加信心。每章后面的练习题能帮助读者将文中讨论的概念具体化。每章后面还加进了基于计算机的练习题，建议将这些练习题变成学习本课程的一部分。
　　我尽了最大努力使书中没有错误，遗憾的是没有一种简单易行的错误控制技术。我试图包括所有与本领域有关的重要的、实际的和有趣的概念。欢迎读者将发现的错误、遗漏及其他建设性建议发送到rbose@ee.iitd.ac.in。
　　最后，我引用Blaise Pascal的话作结，他说：“一个人在写书过程中了解到的最后一件事是把什么内容作为开始。”
致谢
　　我想感谢印度理工学院电机工程系提供的令人振奋的学术环境，特别感谢S. C. Dutta Roy教授、Surendra Prasad教授、H. M. Gupta教授、V. K. Jain教授、Vinod Chandra教授、Santanu Chaudhury教授、S. D. Joshi教授、Sheel Aditya教授、Devi Chadha教授、D. Nagchoudri教授、G. S. Visweswaran教授、R. K. Patney教授、V. C. Prasad教授、S. S. Jamuar教授和R. K. P. Bhatt教授。对与Subrat Kar博士、Ranjan K. Mallik博士和Shankar Prakriya博士的友好讨论也很感激。我很庆幸有几批杰出的学生，他们的反馈对改善本书内容很有帮助。每章后面的许多练习题都曾作为学生作业或考试题使用过。
　　我从内心感激宾夕法尼亚大学的Bernard D. Steinberg教授，他一直引领着我，是我的良师益友，也是我博士论文的指导教师。对每当我请求帮助时总是给予支持和建议的Tel Aviv大学的Avraham Freedman教授我也心存感激。感谢德国Darmstadt理工大学的Rolf Jakoby教授就各种主题所做的令人鼓舞的讨论。我想感谢印度科学学院（Indian Institute of Science）电子通信工程小组的B. Sundar Rajan教授，我们曾就撰写此书做了初步的讨论。
　　K. Vasudevan IIT电机工程系，Kanpur
　　Pankaj Joshi Jodhpur工程学院及研究中心电子与通信工程系，Jodhpur
　　Tanveer Hassan 阿里格尔穆斯林大学工学院，Aligarh
　　S. L. Maskara Jaypee科技信息研究所，Noida
　　Azizar　Rahaman 未来信息职业技术学院计算机工程与科学系，Kolkata
　　Indrajit Das 梅格纳德萨哈技术学院计算机工程与科学系，Kolkata
　　Anindya Jyoti　Pal Heritage技术研究所，Kolkata
　　B. P. Pati ETCE部门马哈拉施特拉邦工程院院士，Pune
　　M. Murugan VIIT ETCE部门，Pune
　　J. N. Sarvaiya SVNIT电机工程系，Surat
　　Vikram Gadre IIT电机工程系，Mumbai
　　M. Padmini MVJ工程学院，Bangalore
　　Suresh Kuri Gogte技术研究所，Belgaum
　　Mandi V. Mahalinga 安贝德卡技术研究所，Bangalore
　　Prakasa Rao 政府工程学院ECE部门，Warangal
　　C. R. Nataraj Sri Jayachamarajendra技术学院（VTU），Mysore
　　我深深感激我的父母，因为他们给了我一生的爱和精神支持。我也感谢我的祖父母给我的祝福，和我弟弟Shantanu关于某些题目的无尽的讨论。
　　最后，我想感谢我的妻子也是最好的朋友，Aloka，她在我写本书的每一阶段都给予鼓励。她那建设性的意见和恰当的批评使本书更具有可读性。是她那无限的耐心、永久的支持、理解、爱、牺牲精神和幽默感才使我写这本书的梦想得以实现。
作者简介
　　Ranjan Bose　 印度理工学院（IIT）电机工程系的教授。他在IIT（Kanpur分校）的电机工程系获得工学学士学位，在美国宾夕法尼亚大学电机工程系获得硕士和博士学位。之后在Alliance半导体公司任高级设计工程师。自1997年11月，他成为印度理工学院的教员。他在1999年获得URSI青年科学家奖，在2000年7月获得Humboldt研究奖金，在2003年获得印度国家科学院青年工程师奖，在2004年获得青年教师AICTE事业奖和2005年由印度科技部颁发的BOYSCAST奖金。

计算机科学及应用

大多数介绍信息论、编码和密码学的书，不是太过数学化，就是太注重基础。本书避免了上述缺点，既考虑到数学的严谨性，又充分考虑了易读性。在第二版中我们收录了许多正在产生的、成熟的或者已经在工业标准和应用中使用的新概念和新想法。
本书特点：
数学论证后面都接有信源编码的直观解释
涵盖更完整的知识面，包括线性分组码、循环码、BCH码和RS码等
完整覆盖卷积码、Turbo码和网格编码调制（TCM）
全面介绍密码学基础、公钥和私钥加密、当前的加密标准及密码学最新趋势

本版更新内容：
新增关于空时分组码和空时网格码的介绍
在Turbo码和网格编码方面进行了内容扩展
新增内容有
·算术编码　　　　　　　　　· Turbo码的交织器设计

·MIMO信道　　　　　　　　　· 椭圆曲线密码学

·低密度奇偶校验（LDPC）码　· 量子密码学

·最小距离的界　　　　　　　· 生物加密

(印度) Ranjan Bose 著：Ranjan Bose 在美国宾夕法尼亚大学获电气工程博士学位。曾在位于美国加利佛尼亚州圣何塞的Alliance半导体公司任高级设计工程师。现任印度理工学院教授。2003年荣获印度国家工程师学会（INAE）颁发的“杰出青年工程师奖”。

武传坤 李徽 译：暂无简介

自从Shannon在1948年发表了一篇关于通信的数学理论的论文之后，人们开始了对信息理论的系统研究。Shannon在第二年（即1949年）又发表了一篇关于安全系统的通信理论的论文，于是又引发了对信息安全的系统研究。现代信息论除了一般的信息理论部分外，它的重要组成部分还包括信源编码、信道编码和密码学。这些部分既有信息理论上的描述，又有它们自己独特的设计技术和方法。在研究上，信源编码、信道编码和密码学都相对较独立，但又有不少将它们相结合的研究。因此，有必要对这些内容进行全面了解。
　　目前在市场上可以见到大量关于信息论和编码方面的书，也有许多专门研究密码和信息安全的书，但将它们融为一体的书却不多见。有些书的内容过于庞杂，对需要了解这方面知识的读者来说不够简洁易懂。Bose的这本书用较短的篇幅覆盖了信息论、信源编码、信道编码和密码学部分，不仅覆盖面超出了许多大部头的书，而且也有一定的技术深度，即使这方面的专家读起来也不乏味。这种精湛的概括和有机结合是本书的主要特色，使它成为一本很好的简明参考书。因此我们组织翻译出版了本书的第1版。
　　随着信息科学持续高速的发展，作为信息科学领域的一些专著文献也很快表现出与最新科技发展的差距。一本负责任的科技著作应该随所涉及领域的科学技术发展而及时更新其内容。本书作者本着对读者负责的态度，及时对本书内容进行了更新，因此出版了第2版。为了让读者阅读到最新的内容，我们也相应地对新版进行了翻译。
　　新版的翻译工作是在第1版翻译工作的基础上进行的。新版新添加内容和更新内容的翻译工作主要由李徽完成，武传坤做了一些校对工作。武传坤将校对时发现的问题反馈给李徽，李徽进行修改后再传给武传坤，这样的校对工作反复进行了4次，其中第5章更是进行了多次修改。即便如此，我们对翻译的准确性仍没有完全的把握，欢迎读者批评指正。
　　最后感谢机械工业出版社对我们工作的信任，希望读者喜欢本书。
译　 者

出版者的话
译者序
第2版前言
第1版前言
第一部分　 信息论和信源编码
第1章　 信源编码 1
1.1　 信息论简介 1
1.2　 不确定性和信息 2
1.3　 平均互信息和熵 6
1.4　 连续随机变量的信息度量 9
1.5　 信源编码定理 10
1.6　 霍夫曼编码 15
1.7　 Shannon-Fano-Elias编码 21
1.8　 算术编码 22
1.9　 Lempel-Ziv算法 23
1.10　 游程编码和PCX格式 25
1.11　 率失真函数 26
1.12　 优化量化器的设计 29
1.13　 随机过程的熵率 30
1.14　 图像压缩简介 31
1.15　 无损压缩的Jpeg标准 32
1.16　 有损压缩的Jpeg标准 33
1.17　 评注 34
1.18　 小结 35
习题 37
上机习题 39
第2章　 信道容量和编码 41
2.1　 引言 41
2.2　 信道模型 42
2.3　 信道容量 43
2.4　 信道编码 45
2.5　 信息容量定理 48
2.6　 Shannon限 50
2.7　 MIMO系统的信道容量 51
2.8　 码的随机选取 52
2.9　 评注 57
2.10　 小结 57
习题 58
上机习题 60
第二部分　 错误控制编码（信道编码）
第3章　 纠错线性分组码 61
3.1　 纠错码简介 61
3.2　 基本定义 62
3.3　 线性分组码的矩阵描述 65
3.4　 等价码 66
3.5　 奇偶校验矩阵 68
3.6　 线性分组码的译码 70
3.7　 伴随式译码 75
3.8　 译码后的错误概率（纠错概率） 75
3.9　 完备码 78
3.10　 汉明码 80
3.11　 低密度奇偶校验（LDPC）码 81
3.12　 最优线性码 83
3.13　 最大距离可分（MDS）码 84
3.14　 最小距离的界 84
3.15　 空时分组码 85
3.16　 评注 87
3.17　 小结 87
习题 88
上机习题 90
第4章　 循环码 91
4.1　 循环码简介 91
4.2　 多项式 91
4.3　 多项式的除法算法 92
4.4　 一种循环码的生成方法 96
4.5　 循环码的矩阵描述 98
4.6　 准循环码和截短循环码 101
4.7　 突发错误纠错 101
4.8　 Fire码 103
4.9　 Golay码 103
4.9.1　 二元Golay码 103
4.9.2　 三元Golay码 104
4.10　循环冗余校验（CRC）码 104
4.11　 循环码的电路实现 106
4.12　 评注 110
4.13　 小结 110
习题 112
上机习题 113
第5章　 BCH码 114
5.1　 BCH码简介 114
5.2　 基本引理 114
5.3　 极小多项式 115
5.4　 极小多项式作为生成多项式 118
5.5　 一些BCH码实例 118
5.6　 BCH码的译码 122
5.7　 Reed-Solomon码 125
5.8　 Reed-Solomon码编码器和译码器的实现 127
5.8.1　 硬件实现 127
5.8.2　 软件实现 128
5.9　 实信道上RS码性能 129
5.10　 嵌套码 131
5.11　 评注 132
5.12　 小结 133
习题 134
上机习题 135
第6章　 卷积码 136
6.1　 卷积码简介 136
6.2　 树码和网格码 136
6.3　 卷积码的多项式描述（解析表示） 140
6.4　 卷积码的距离概念 144
6.5　 生成函数 146
6.6　 卷积码的矩阵描述 148
6.7　 卷积码的维特比译码 150
6.8　 卷积码的距离界 155
6.9　 性能界 157
6.10　 著名的好卷积码 158
6.11　 Turbo码 160
6.12　 Turbo译码 162
6.12.1　 改进的Bahl、Cocke、Jelinek和Raviv（BCJR）算法 162
6.12.2　 迭代MAP译码 163
6.13　 Turbo码的交织器设计 166
6.14　 评注 167
6.15　 小结 167
习题 169
上机习题 171
第7章　 网格编码调制 173
7.1　 网格编码调制(TCM)简介 173
7.2　 编码调制的概念 173
7.3　 通过集合分割的映射 177
7.4　 Ungerboeck的TCM设计准则 180
7.5　 TCM译码器 183
7.6　 Awgn信道性能评估 184
7.7　 dfree的计算 189
7.8　 衰退信道的TCM 190
7.9　 空时网格码 193
7.9.1　 缓慢雷利衰退 194
7.9.2　 快速雷利衰退 195
7.10　 评注 195
7.11　 小结 195
习题 197
上机习题 200
第三部分　 安全通信编码
第8章　 密码学 203
8.1　 密码学简介 203
8.2　 加密技术概述 204
8.3　 加密算法所用到的运算 206
8.4　 对称（保密密钥）密码学 206
8.5　 数据加密标准（DES） 208
8.6　 国际数据加密算法（IDEA） 210
8.7　 RC密码 211
8.8　 非对称（公钥）算法 212
8.9　 RSA算法 212
8.10　 全球电子邮件加密标准 215
8.11　 单向散列变换 216
8.12　 其他技术 217
8.13　 椭圆曲线密码学 218
8.14　 Diffie-Hellman密钥协商协议 219
8.15　 利用混沌理论实现安全通信 221
8.16　 量子密码学 221
8.17　 生物加密 222
8.18　 密码分析 223
8.19　 密码学中的政治因素 224
8.20　 评注 225
8.21　 小结 227
习题 228
上机习题 231