內容簡介

　　《信息論與編碼理論：劍橋大學真題精解》講解信息論與編碼理論，涵蓋概率和代數兩個方嚮。書中素材來自劍橋大學本科生課程“信息論”“編碼與密碼學”以及幾門數學方嚮的研究生課程。全書大的特色是例題豐富，並將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的風格，呈現瞭許多帶有答案的例題。這些例題都以問題的形式齣現（其中很多源自於劍橋數學榮譽學位的考試試捲，其形式和風格均得以保留）。

京東買書，放心，書很值得讀，要花點時間，加油，努力！

內容對我很有用，書本質量也不錯

推薦，非常經典的書，可以更快學習信息論

不錯的書，有難度，專業性強

好書天天看，天天看好書

不錯

專業書籍，正版，物流快。

京東買書，放心，書很值得讀，要花點時間，加油，努力！

京東買書，放心，書很值得讀，要花點時間，加油，努力！