前　言Information Theory and Coding by Example本書的素材取自劍橋大學數(shù)學榮譽學位考試的幾門相關課程：本科三年級的“信息論”（該課程已歷經40余年的教學與發(fā)展，期間僅僅在課程名稱上略有調整），“編碼與密碼學”（一門新開設的簡明課程，省去了繁雜的技術細節(jié)），以及一些更為前沿的第三部分課程（相當于數(shù)學碩士研究生課程）。本書的內容安排圍繞以下核心概念：概率分布的熵——一種不確定性的度量（也包括隨機過程的熵率——樣本軌跡變化率的度量），編碼——一種度量及利用隨機過程中冗余信息的方法。 因此，本書的內容大致涵蓋了當前全球范圍內與信息論相關的典型教學素材，這些教學內容通常安排在計算機科學、電子工程以及概率與統(tǒng)計等學科中。然而，本書與其他著作的首要不同在于豐富的例題（其模式遵循了我們在劍橋大學出版社推出的本系列圖書第一本——《Probability and Statistics by Example》）。書中絕大部分例題來源于劍橋大學數(shù)學榮譽學位考試。因此，讀者可以通過本書判斷自己所達到或者期望達到的學習程度。 本書與其他信息論和編碼相關著作的第二個不同之處在于，它包含了兩個可能的方向：概率和代數(shù)。通常而言，這兩個方向往往出現(xiàn)在不同的專著、教材或者課程中，所涉及的人員也來自不同的領域。本書的成形得益于兩段經歷。我們曾經在位于莫斯科的俄羅斯科學院下屬的信息傳輸問題研究所工作。俄羅斯科學院一直具有跨學科研究科學問題的優(yōu)良傳統(tǒng)，特別值得一提的是，Roland Dobrushin、Raphail Khas�搈insky、Mark Pinsker、Vladimir Blinovsky、Vyacheslav Prelov、Boris Tsybakov、Kamil Zigangirov(從事概率和統(tǒng)計研究)、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（從事代數(shù)、組合數(shù)學、幾何和數(shù)論研究）等學者都曾經工作或依然工作于俄羅斯科學院(曾經有一段時期，這些學者都在莫斯科中心一幢改建樓同一層的五個房間中工作)。我們也具有在劍橋大學的工作經歷，這段經歷同樣十分重要。劍橋大學教授信息論和編碼理論相關課程時，具有與俄羅斯科學院相似的跨學科精神。這種風格主要起始于Peter Whittle(從事概率和最優(yōu)化研究)及其后的Charles Goldie(從事概率研究)、Richard Pinch(從事代數(shù)和幾何研究)、Tom K�塺ner和Keith Carne(從事分析研究)，還有Tom Fisher(從事數(shù)論研究)。 需要補充的是，作為訓練有素的數(shù)學家(并且骨子里也是數(shù)學基因)，盡管我們也有很強的應用背景，但在完成本書的過程中依然經歷著這樣一些折磨：表述模糊不清，不精確，真假可疑（這包含了個人因素），當然還有將完美的數(shù)學思想付諸實踐所需要的代價。然而，我們依然堅定地認為數(shù)學思維依然是在當今充滿競爭的世界上生存并自我完善的主要途徑。因此，數(shù)學需要被認真地對待并加以學習（或許不需要理由）。 作為面向隨機過程的信息論方法基礎，上述兩個概念(熵和編碼)已由Shannon在20世紀40年代發(fā)表的代表性論文［139，141］中完整地引入。當然，熵的概念早在一個世紀前就已被Boltzmann和Gibbs在熱力學中使用，而編碼已被（高效地）應用在實際生活當中很久了。但是，Shannon是第一個充分意識到這些概念在信息領域的作用并用現(xiàn)代數(shù)學框架加以闡述的開創(chuàng)者，盡管Shannon從未經歷成為數(shù)學家的訓練，也并不總能完整地給出關于自己的理論的一些證明（或許他并不覺得有任何不妥）。在本書的相關章節(jié)中，我們會點評一些Shannon與數(shù)學界的關系發(fā)展中非常引人注目的場景。幸運的是，這些紛雜并沒有給Shannon造成困擾（Shannon和Boltzmann不同，后者對外界的評論十分敏感且十分在意）。Shannon一定知道他所發(fā)現(xiàn)的理論背后的巨大價值；在我們的眼中，他的地位與偉大的數(shù)學家Wiener和von Neumann相當。 客觀地說，Shannon的名字依然主導著當前信息與編碼理論中概率和代數(shù)的方向。這樣強大的影響力是非同尋常的，特別是當我們意識到Shannon的學術活躍期已過去40多年時。（雖然在一些先進的話題方面，Shannon或許會沿用Einstein的話：“數(shù)學家們已經涌入通信理論，現(xiàn)在連我自己都搞不清楚這理論了�！保┰赟hannon的創(chuàng)建及發(fā)明之后，數(shù)學、電子工程、計算機科學等學科都經歷了巨大的變化。誰又能預見在20世紀40～50年代，原本相互對立的Shannon信息論與Wiener控制論能夠融合？事實上，后者包含造福全人類的宏偉（甚至是不切實際的）愿景，而前者僅僅設定了一個謙虛的目標以將信息傳輸中的誤差控制在某些極限當中。Wiener的著作［171］塑造了20世紀50～60年代思想家們所開展智力活動的幾乎所有維度。特別地，控制論在蘇聯(lián)及其衛(wèi)星國成為嚴肅的政治議題：最初它被認為是“一個資產階級的反科學理論”，然后又被過度狂熱地追捧。（1953年發(fā)表在蘇聯(lián)主要意識形態(tài)期刊《哲學問題》上的關于控制論的評價是：“帝國主義者沒有辦法消除摧毀資本主義社會的根本矛盾，他們不能阻止即將發(fā)生的經濟危機。所以，他們嘗試從狂熱的軍備競賽和意識形態(tài)戰(zhàn)爭中尋找答案。在深層的絕望中，他們尋求偽科學帶來的一線希望以茍延殘喘�！痹�1954年版的蘇聯(lián)《簡明哲學詞典》中有成百上千條關于控制論的定義：“反動的偽科學，首先出現(xiàn)在二戰(zhàn)后的美國，后廣泛傳播于資本主義國家，是一種現(xiàn)代的機械論�！比欢�，受壓于參與蘇聯(lián)核試驗且掌握實權的一些頂尖物理學家，之前反對控制論的《哲學問題》期刊在1955年發(fā)表了鼓吹控制論積極面的文章。該文章的作者包括Alexei Lyapunov和Sergei Sobolev等蘇聯(lián)卓越的數(shù)學家。）奇怪的是，最近關于Wiener的自傳［35］顯示，曾經存在“秘密的（美國）文檔指出FBI和CIA如何在冷戰(zhàn)期間追蹤Wiener以阻撓他的社會激進主義并壓制控制論在國內外的巨大影響”。文獻［65］中也提到了這種有趣的對比。 然而，歷史總是以自己的腳步前進。如Freeman Dyson在對文獻［35］的評述［41］中指出：“（Shannon的理論）在數(shù)學方面是優(yōu)雅和清晰的，它能夠應對通信所涉及的許多實際問題。它比控制論更易于使用。它奠定了一門嶄新的學科——信息論……（在當代）電子工程師將學習Shannon創(chuàng)建的信息論作為基本訓練，而控制論逐漸被遺忘�！� 事實上控制論并未被遺忘，在蘇聯(lián)依然有至少七個研究院或機構以控制論命名：其中俄羅斯的莫斯科和白俄羅斯的明斯克分別有兩所，愛沙尼亞的塔林、烏茲別克斯坦的塔什干和烏克蘭的基輔（蘇聯(lián)計算機科學的中心）也分別坐落著一所。在英國，至少有四所大學設置了控制論相關的院系，分別是波爾頓大學、布拉德福德大學、赫爾大學和瑞丁大學，這項統(tǒng)計事實上不包括其他相關的學術組織和學會。在全球范圍內來看，控制論相關的學會看起來非常繁榮，具有長短不一、各式各樣的名字，比如瑞士的方法研究所、意大利的控制論學會、阿根廷布宜諾斯艾利斯的普適系統(tǒng)理論和控制論學會。我們也十分欣喜地發(fā)現(xiàn)劍橋控制論協(xié)會坐落于美國加州的貝爾蒙。與控制論情形不同，以信息論命名的研究機構屈指可數(shù)。顯然，關于Shannon和Wiener的經典爭論還會繼續(xù)。 無論如何，Wiener在數(shù)學領域的個人聲譽依然堅實，我們能夠說出好幾個他理論中的珍寶，比如Paley-Wiener定理（在Wiener無數(shù)次到訪劍橋的過程中創(chuàng)造）和Wiener-Hopf方法，當然還有Wiener過程——代表他在科學研究及應用方面的重要地位。然而，當前針對這位科學巨擘的一些回憶錄展示出他復雜而困惑的人格。（從關于Wiener的傳記［35］題名不難發(fā)現(xiàn)這種特點，但是這些觀點仍然有爭議，比如文獻［107］的評論。而在本書中，我們嘗試采用文獻［75］中第386～391頁關于Wiener的溫和口吻加以闡述。）另一方面，關于Shannon的生平記錄（這些論述來自其他信息和編碼理論創(chuàng)始人，如Richard Hamming）則給出了一致的描繪——他是一位安靜、睿智和幽默的人。我們希望現(xiàn)有這些說法不要成為人們描寫Shannon傳記的障礙，也希望未來能有更多關于Shannon的書，正如現(xiàn)在關于Wiener的書那樣。 如前所述，本書的目的是雙重的：一方面通過豐富的例題和例子對信息論中概率與幾何方面的知識做系統(tǒng)的介紹，另一方面討論一些很少在其他主流教材中涉及的有益話題。本書第1～3章介紹信息論和編碼理論的基礎知識并對一些相關前沿話題展開討論。內容組織安排方面，我們主要關注具有代表性的問題和例題（其中很多源自劍橋大學的課程），而不對背后的理論做過于細致的闡述。第4章對信息論相關的一系列深層主題進行介紹，其表述風格十分簡潔，因此一些重要的結論并未給出證明。 本書的很大一部分內容源自課堂講義和對課堂習題或考試題的解答，所以某種程度上的內容重復難以避免，并且有可能出現(xiàn)符號的多重定義或者非規(guī)范的語言表述。對此，我們順其自然，我們覺得這些不完美恰好營造了教學和考試過程中的真實氛圍。 本書行文安排深受兩部優(yōu)秀著作［52，36］的影響。我們與Charles Goldie長久的友誼以及同Tom Cover和睦的交往均對本書產生了有益的幫助。我們同樣受益于對文獻［18］、［110］、［130］和［98］的閱讀及借鑒。此外，感謝劍橋大學牛頓研究院2002～2010年的一系列課程，特別是通信科學中的隨機過程（2010年1～7月）。本書中的諸多內容都經過與來自不同研究機構的同行的交流和討論，其中最為重要的就是位于莫斯科的信息傳輸問題研究所和數(shù)學地理及地震預測研究所（我們曾經是其中忠誠的一員）。我們還要感謝來自劍橋大學Statslab的James Lawrence為本書提供了圖片。 本書中PSE I和PSE II分別代表本書作者所著由劍橋大學出版社出版的《Probability and Statistics by Example》第1卷和第2卷。我們采用PSE II的風格，呈現(xiàn)了許多帶有答案的例題。這些例題都以問題的形式出現(xiàn)（其中很多源自于劍橋數(shù)學榮譽學位的考試試卷，其形式和風格均得以保留）。