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