内容简介

　　《信息论与编码理论：剑桥大学真题精解》讲解信息论与编码理论，涵盖概率和代数两个方向。书中素材来自剑桥大学本科生课程“信息论”“编码与密码学”以及几门数学方向的研究生课程。全书大的特色是例题丰富，并将Shannon等科学家的学术历程贯穿其中，在透彻讲解基础知识的同时带领读者逐步探讨深层主题。

作者简介

　　Mark Kelbert 英国斯望西大学数学系统计高级教师。

　　Yuri Suhov剑桥大学纯数学和数学统计系荣誉教授。他还是俄罗斯科学院信息传输问题研究所的研究员。

目录

Information Theory and Coding by Example

出版者的话

译者序

前言

第1章　信息论基础1

1.1　基本概念，Kraft不等式，Huffman编码1

1.2　熵：简介11

1.3　Shannon第一编码定理，Markov信源的熵率26

1.4　信道，解码规则，Shannon第二编码定理38

1.5　微分熵及其性质54

1.6　本章附加问题60

第2章　编码理论简介93

2.1　Hamming距离，码字的几何特征，码本规模的基本界93

2.2　Shannon第二编码定理的几何证明，码本规模的精细界104

2.3　线性码：基本构造119

2.4　Hamming码，Golay码，Reed-Muller码129

2.5　循环码和代数多项式，BCH码简介139

2.6　本章附加问题158

第3章　编码理论的深层主题176

3.1　有限域入门176

3.2　Reed-Solomon编码，再论BCH编码191

3.3　再论循环码，BCH解码197

3.4　MacWilliams标识和线性规划界206

3.5　渐近好码216

3.6　本章附加问题224

第4章　信息论的深层主题242

4.1　Gauss信道242

4.2　连续时间集的渐近均分性262

4.3　Nyquist-Shannon公式270

4.4　空间点过程和网络信息论287

4.5　密码学选例与问题298

4.6　本章附加问题316

参考文献330

索引337

前言/序言

　　前　言Information Theory and Coding by Example

　　本书的素材取自剑桥大学数学荣誉学位考试的几门相关课程：本科三年级的“信息论”（该课程已历经40余年的教学与发展，期间仅仅在课程名称上略有调整），“编码与密码学”（一门新开设的简明课程，省去了繁杂的技术细节），以及一些更为前沿的第三部分课程（相当于数学硕士研究生课程）。本书的内容安排围绕以下核心概念：概率分布的熵——一种不确定性的度量（也包括随机过程的熵率——样本轨迹变化率的度量），编码——一种度量及利用随机过程中冗余信息的方法。

　　因此，本书的内容大致涵盖了当前全球范围内与信息论相关的典型教学素材，这些教学内容通常安排在计算机科学、电子工程以及概率与统计等学科中。然而，本书与其他著作的首要不同在于丰富的例题（其模式遵循了我们在剑桥大学出版社推出的本系列图书第一本——《Probability and Statistics by Example》）。书中绝大部分例题来源于剑桥大学数学荣誉学位考试。因此，读者可以通过本书判断自己所达到或者期望达到的学习程度。

　　本书与其他信息论和编码相关著作的第二个不同之处在于，它包含了两个可能的方向：概率和代数。通常而言，这两个方向往往出现在不同的专著、教材或者课程中，所涉及的人员也来自不同的领域。本书的成形得益于两段经历。我们曾经在位于莫斯科的俄罗斯科学院下属的信息传输问题研究所工作。俄罗斯科学院一直具有跨学科研究科学问题的优良传统，特别值得一提的是，Roland Dobrushin、Raphail Khas�搈insky、Mark Pinsker、Vladimir Blinovsky、Vyacheslav Prelov、Boris Tsybakov、Kamil Zigangirov(从事概率和统计研究)、Valentin Afanasiev、Leonid Bassalygo、Serguei Gelfand、Valery Goppa、Inna Grushko、Grigorii Kabatyansky、Grigorii Margulis、Yuri Sagalovich、Alexei Skorobogatov、Mikhail Tsfasman、Victor Zinov�搚ev、Victor Zyablov（从事代数、组合数学、几何和数论研究）等学者都曾经工作或依然工作于俄罗斯科学院(曾经有一段时期，这些学者都在莫斯科中心一幢改建楼同一层的五个房间中工作)。我们也具有在剑桥大学的工作经历，这段经历同样十分重要。剑桥大学教授信息论和编码理论相关课程时，具有与俄罗斯科学院相似的跨学科精神。这种风格主要起始于Peter Whittle(从事概率和最优化研究)及其后的Charles Goldie(从事概率研究)、Richard Pinch(从事代数和几何研究)、Tom K�塺ner和Keith Carne(从事分析研究)，还有Tom Fisher(从事数论研究)。

　　需要补充的是，作为训练有素的数学家(并且骨子里也是数学基因)，尽管我们也有很强的应用背景，但在完成本书的过程中依然经历着这样一些折磨：表述模糊不清，不精确，真假可疑（这包含了个人因素），当然还有将完美的数学思想付诸实践所需要的代价。然而，我们依然坚定地认为数学思维依然是在当今充满竞争的世界上生存并自我完善的主要途径。因此，数学需要被认真地对待并加以学习（或许不需要理由）。

　　作为面向随机过程的信息论方法基础，上述两个概念(熵和编码)已由Shannon在20世纪40年代发表的代表性论文［139，141］中完整地引入。当然，熵的概念早在一个世纪前就已被Boltzmann和Gibbs在热力学中使用，而编码已被（高效地）应用在实际生活当中很久了。但是，Shannon是第一个充分意识到这些概念在信息领域的作用并用现代数学框架加以阐述的开创者，尽管Shannon从未经历成为数学家的训练，也并不总能完整地给出关于自己的理论的一些证明（或许他并不觉得有任何不妥）。在本书的相关章节中，我们会点评一些Shannon与数学界的关系发展中非常引人注目的场景。幸运的是，这些纷杂并没有给Shannon造成困扰（Shannon和Boltzmann不同，后者对外界的评论十分敏感且十分在意）。Shannon一定知道他所发现的理论背后的巨大价值；在我们的眼中，他的地位与伟大的数学家Wiener和von Neumann相当。

　　客观地说，Shannon的名字依然主导着当前信息与编码理论中概率和代数的方向。这样强大的影响力是非同寻常的，特别是当我们意识到Shannon的学术活跃期已过去40多年时。（虽然在一些先进的话题方面，Shannon或许会沿用Einstein的话：“数学家们已经涌入通信理论，现在连我自己都搞不清楚这理论了。”）在Shannon的创建及发明之后，数学、电子工程、计算机科学等学科都经历了巨大的变化。谁又能预见在20世纪40～50年代，原本相互对立的Shannon信息论与Wiener控制论能够融合？事实上，后者包含造福全人类的宏伟（甚至是不切实际的）愿景，而前者仅仅设定了一个谦虚的目标以将信息传输中的误差控制在某些极限当中。Wiener的著作［171］塑造了20世纪50～60年代思想家们所开展智力活动的几乎所有维度。特别地，控制论在苏联及其卫星国成为严肃的政治议题：最初它被认为是“一个资产阶级的反科学理论”，然后又被过度狂热地追捧。（1953年发表在苏联主要意识形态期刊《哲学问题》上的关于控制论的评价是：“帝国主义者没有办法消除摧毁资本主义社会的根本矛盾，他们不能阻止即将发生的经济危机。所以，他们尝试从狂热的军备竞赛和意识形态战争中寻找答案。在深层的绝望中，他们寻求伪科学带来的一线希望以苟延残喘。”在1954年版的苏联《简明哲学词典》中有成百上千条关于控制论的定义：“反动的伪科学，首先出现在二战后的美国，后广泛传播于资本主义国家，是一种现代的机械论。”然而，受压于参与苏联核试验且掌握实权的一些顶尖物理学家，之前反对控制论的《哲学问题》期刊在1955年发表了鼓吹控制论积极面的文章。该文章的作者包括Alexei Lyapunov和Sergei Sobolev等苏联卓越的数学家。）奇怪的是，最近关于Wiener的自传［35］显示，曾经存在“秘密的（美国）文档指出FBI和CIA如何在冷战期间追踪Wiener以阻挠他的社会激进主义并压制控制论在国内外的巨大影响”。文献［65］中也提到了这种有趣的对比。

　　然而，历史总是以自己的脚步前进。如Freeman Dyson在对文献［35］的评述［41］中指出：“（Shannon的理论）在数学方面是优雅和清晰的，它能够应对通信所涉及的许多实际问题。它比控制论更易于使用。它奠定了一门崭新的学科——信息论……（在当代）电子工程师将学习Shannon创建的信息论作为基本训练，而控制论逐渐被遗忘。”

　　事实上控制论并未被遗忘，在苏联依然有至少七个研究院或机构以控制论命名：其中俄罗斯的莫斯科和白俄罗斯的明斯克分别有两所，爱沙尼亚的塔林、乌兹别克斯坦的塔什干和乌克兰的基辅（苏联计算机科学的中心）也分别坐落着一所。在英国，至少有四所大学设置了控制论相关的院系，分别是波尔顿大学、布拉德福德大学、赫尔大学和瑞丁大学，这项统计事实上不包括其他相关的学术组织和学会。在全球范围内来看，控制论相关的学会看起来非常繁荣，具有长短不一、各式各样的名字，比如瑞士的方法研究所、意大利的控制论学会、阿根廷布宜诺斯艾利斯的普适系统理论和控制论学会。我们也十分欣喜地发现剑桥控制论协会坐落于美国加州的贝尔蒙。与控制论情形不同，以信息论命名的研究机构屈指可数。显然，关于Shannon和Wiener的经典争论还会继续。

　　无论如何，Wiener在数学领域的个人声誉依然坚实，我们能够说出好几个他理论中的珍宝，比如Paley-Wiener定理（在Wiener无数次到访剑桥的过程中创造）和Wiener-Hopf方法，当然还有Wiener过程——代表他在科学研究及应用方面的重要地位。然而，当前针对这位科学巨擘的一些回忆录展示出他复杂而困惑的人格。（从关于Wiener的传记［35］题名不难发现这种特点，但是这些观点仍然有争议，比如文献［107］的评论。而在本书中，我们尝试采用文献［75］中第386～391页关于Wiener的温和口吻加以阐述。）另一方面，关于Shannon的生平记录（这些论述来自其他信息和编码理论创始人，如Richard Hamming）则给出了一致的描绘——他是一位安静、睿智和幽默的人。我们希望现有这些说法不要成为人们描写Shannon传记的障碍，也希望未来能有更多关于Shannon的书，正如现在关于Wiener的书那样。

　　如前所述，本书的目的是双重的：一方面通过丰富的例题和例子对信息论中概率与几何方面的知识做系统的介绍，另一方面讨论一些很少在其他主流教材中涉及的有益话题。本书第1～3章介绍信息论和编码理论的基础知识并对一些相关前沿话题展开讨论。内容组织安排方面，我们主要关注具有代表性的问题和例题（其中很多源自剑桥大学的课程），而不对背后的理论做过于细致的阐述。第4章对信息论相关的一系列深层主题进行介绍，其表述风格十分简洁，因此一些重要的结论并未给出证明。

　　本书的很大一部分内容源自课堂讲义和对课堂习题或考试题的解答，所以某种程度上的内容重复难以避免，并且有可能出现符号的多重定义或者非规范的语言表述。对此，我们顺其自然，我们觉得这些不完美恰好营造了教学和考试过程中的真实氛围。

　　本书行文安排深受两部优秀著作［52，36］的影响。我们与Charles Goldie长久的友谊以及同Tom Cover和睦的交往均对本书产生了有益的帮助。我们同样受益于对文献［18］、［110］、［130］和［98］的阅读及借鉴。此外，感谢剑桥大学牛顿研究院2002～2010年的一系列课程，特别是通信科学中的随机过程（2010年1～7月）。本书中的诸多内容都经过与来自不同研究机构的同行的交流和讨论，其中最为重要的就是位于莫斯科的信息传输问题研究所和数学地理及地震预测研究所（我们曾经是其中忠诚的一员）。我们还要感谢来自剑桥大学Statslab的James Lawrence为本书提供了图片。

　　本书中PSE I和PSE II分别代表本书作者所著由剑桥大学出版社出版的《Probability and Statistics by Example》第1卷和第2卷。我们采用PSE II的风格，呈现了许多带有答案的例题。这些例题都以问题的形式出现（其中很多源自于剑桥数学荣誉学位的考试试卷，其形式和风格均得以保留）。

专业书籍，正版，物流快。

精装书本，价廉物美，内容丰富。

包装很好，快递也很快，非常满意

书不错，挺好的！点个赞！

精装书本，价廉物美，内容丰富。

精装书本，价廉物美，内容丰富。

只看书，不说话！！！！

只看书，不说话！！！！

烧脑书，适合码农的进阶阅读。