信息论、编码与密码学(第2版)

.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

.　　信息论、错误控制编码和密码学是现代数字通信系统中的三大支柱。这三个课题都很大，而且针对其中的任何一个课题，都有很多好书加以讨论。本书试图用有限的篇幅将信息论、错误控制编码和密码学中所有重要的概念有机地结合起来，而不需要将书写得很厚。本书的意图就是使之成为一本简洁而生动的书。
　　本书是我在印度理工学院（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，她在我写本书的每一阶段都给予鼓励。她那建设性的意见和恰当的批评使本书更具有可读性。是她那无限的耐心、永久的支持、理解、爱、牺牲精神和幽默感才使我写这本书的梦想得以实现。