第2版前言

自從本書第1版出版以來，我們希望書中的許多方面能得到改進,如重新編排或者擴充，但是需再版的限制并不允許我們在已經出版的書中實現這樣的愿望。而今在出新版之際，我們終于有機會對原書做些改變，增加一些習題，同時，討論一些在第1版中忽略的專題。
本書主要的變化包括：各章重新編排，使本書更易于教學；增加了200多個新習題。在某些專題中，我們也增加了一些素材，如在普適性投資組合理論、通用信源編碼、高斯反饋信道容量、網絡信息論等方面，并且闡述了數據壓縮和信道容量的對偶性。另外，本書還新增加了一章，同時對原書中大量的證明過程進行簡化，而且更新了參考文獻和歷史回顧點評。
本書可以分成兩個學期學習。建議第一學期學習第1～9章，包括漸近均分性、數據壓縮、信道容量，以及高斯信道等。第二學期學習余下的幾章，包括率失真理論、型方法、科爾莫戈羅夫復雜度、網絡信息論、通用信源編碼和投資組合理論。如果只開一個學期的課，建議將率失真、科爾莫戈羅夫復雜度和網絡信息論加入第一學期的教學中，其中后兩者只需各上一節(jié)課。
自第1版以來，信息論迎來了它的50歲生日（香農的領域開創(chuàng)性文章50周年紀念），源自信息論的許多思想已經廣泛應用于科學技術的眾多問題，如生物信息學、網絡搜索、無線通信、視頻壓縮以及其他等。信息論的應用是無止境的，然而其完美的數學理論始終是該領域最引人注目的地方。我們希望借此書給大家?guī)�來某些共識，使得大家堅信在涉及數學、物理學、統(tǒng)計學和工程學的交叉領域中，信息論是最有趣的領域之一。

Thomas M.Cover
Joy A.Thomas

Palo Alto, California
2006年1月

第1版前言

本書是一本簡明易懂的信息論教材。正如愛因斯坦所說：“凡事應該盡可能使其簡單到不能再簡單為止�！彪m然我們沒有深入考證過該引語的來源（據說最初是在幸運蛋卷中發(fā)現的），但我們自始至終都將這種觀點貫穿到本書的寫作中。信息論中的確有這樣一些關鍵的思想和技巧，一旦掌握了它們，不僅使信息論的主題簡明，而且在處理新問題時提供重要的直覺。
本書來自使用了十多年的信息論講義,原講義是信息論課程的高年級本科生和一年級研究生兩學期用的教材。本書打算作為通信理論、計算機科學和統(tǒng)計學專業(yè)學生學習信息論的教材。
信息論中有兩個簡明要點。第一，熵與互信息這樣的特殊量是為了解答基本問題而產生的。例如，熵是隨機變量的最小描述復雜度，互信息是度量在噪聲背景下的通信速率。另外，我們在以后還會提到，互信息相當于已知邊信息條件下財富的雙倍增長。第二，回答信息論問題的答案具有自然的代數結構。例如，熵具有鏈式法則，因而，熵和互信息也是相關的。因此，數據壓縮和通信中的問題得到廣泛的解釋。我們都有這樣的感受，當研究某個問題時，往往歷經大量的代數運算推理得到了結果，但此時沒有真正了解問題的全貌，最終是通過反復觀察結果，才對整個問題有完整、明確的認識。所以，對一個問題的全面理解，不是靠推理，而是靠對結果的觀察。要更具體地說明這一點，物理學中的牛頓三大定律和薛定諤波動方程也許是最合適的例子。誰曾預見過薛定諤波動方程后來會有如此令人敬畏的哲學解釋呢？
在本書中，我們常會在著眼于問題之前，先了解一下答案的性質。比如第2章中，我們定義熵、相對熵和互信息，研究它們之間的關系，再對這些關系做一點解釋，由此揭示如何融會貫通地使用各式各樣的方法解決實際問題。同理，我們順便探討熱力學第二定律的含義。熵總是增加嗎？答案既肯定也否定。這種結果會令專家感興趣，但初學者或許認為這是必然的而不會深入考慮。
在實際教學中，教師往往會加入一些自己的見解。事實上，尋找無人知道的證明或者有所創(chuàng)新的結果是一件很愉快的事情。如果有人將新的思想和已經證明的內容在課堂上講解給學生，那么不僅學生會積極反饋“對，對，對”，而且會大大地提升教授該課程的樂趣。我們正是這樣從研究本教材的許多新想法中獲得樂趣的。
本書加入的新素材實例包括信息論與博弈之間的關系，馬爾可夫鏈背景下熱力學第二定律的普遍性問題，信道容量定理的聯合典型性證明，赫夫曼碼的競爭最優(yōu)性，以及關于最大熵譜密度估計的伯格（Burg）定理的證明�？茽柲�戈羅夫復雜度這一章也是本書的獨到之處。而將費希爾信息、互信息、中心極限定理以及布倫-閔可夫斯基不等式與熵冪不等式聯系在一起，也是我們引以為豪之處。令我們感到驚訝的是，關于行列式不等式的許多經典結論，當利用信息論不等式后會很容易得到證明。
自從香農的奠基性論文面世以來，盡管信息論已有了相當大的發(fā)展，但我們還是要努力強調它的連貫性。雖然香農創(chuàng)立信息論時受到通信理論中問題的啟發(fā)，然而我們認為信息論是一門獨立的學科，可應用于通信理論和統(tǒng)計學中。我們將信息論作為一個學科領域從通信理論、概率論和統(tǒng)計學的背景中獨立出來，因為明顯不可能從這些學科中獲得難以理解的信息概念。
由于本書中絕大多數結論以定理和證明的形式給出，所以，我們期望通過對這些定理的巧妙證明能說明這些結論的完美性。一般來講，我們在介紹問題之前先描述問題的解的性質，而這些很有趣的性質會使接下來的證明順理成章。
使用不等式串，中間不加任何文字，最后直接加以解釋，是我們在表述方式上的一項創(chuàng)新。希望讀者學習我們所給的證明過程達到一定數量時，在沒有任何解釋的情況下就能理解其中的大部分步驟，并自己給出所需的解釋。這些不等式串好比模擬測試題，讀者可以通過它們確認自己是否已掌握證明那些重要定理的知識。這些證明過程的自然流程是如此引人注目，以至于導致我們輕視了寫作技巧中的某條重要原則。由于沒有多余的話，因而突出了思路的邏輯性與主題思想。我們希望當讀者閱讀完本書后，能夠與我們共同分享我們所推崇的，具有優(yōu)美、簡潔和自然風格的信息論。
本書廣泛使用弱的典型序列的方法，此概念可以追溯到香農1948年的創(chuàng)造性工作，而它真正得到發(fā)展是在20世紀70年代初期。其中的主要思想就是所謂的漸近均分性（AEP），或許可以粗略地說成“幾乎一切事情都是等可能的”。
第2章闡述了熵、相對熵和互信息之間的基本代數關系。漸近均分性是第3章重中之重的內容，這也使我們將隨機過程和數據壓縮的熵率分別放在第4章和第5章中論述。第6章介紹博弈，研究了數據壓縮的對偶性和財富的增長率。
可作為對信息論進行理性思考基礎的科爾莫戈羅夫復雜度，擁有著巨大的成果，放在第14章中論述。我們的目標是尋找一個通用的最短描述，而不是平均意義下的次佳描述。的確存在這樣的普遍性概念用來刻畫一個對象的復雜度。該章也論述了神奇數Ω，揭示數學上的不少奧秘，這是圖靈機停止運轉概率的推廣。
第7章論述信道容量定理。第8章敘述微分熵的必需知識,它們是將早期容量定理推廣到連續(xù)噪聲信道的基礎�；�本的高斯信道容量問題在第9章中論述。
第11章闡述信息論和統(tǒng)計學之間的關系，20世紀50年代初期庫爾貝克(Kullback)首次對此進行了研究，此后進展不大。由于率失真理論比無噪聲數據壓縮理論需要更多的背景知識，因而將其放置在正文中比較靠后的第10章。
網絡信息論是個大的主題，安排在第15章，主要研究的是在噪聲和干擾情形下的同時可達的信息流。有許多新的思想在網絡信息論中開始活躍起來，其主要新要素有干擾和反饋。第16章講述股票市場，這是第6章所討論的博弈的推廣，也再次表明了信息論和博弈之間的緊密聯系。
第17章講述信息論中的不等式，我們借此一隅把散布于全書中的有趣不等式重新收攏在一個新的框架中，再加上一些關于隨機抽取子集熵率的有趣新不等式。集合和的體積的布倫-閔可夫斯基不等式，獨立隨機變量之和的有效方差的熵冪不等式以及費希爾信息不等式之間的美妙關系也將在此章中得到詳盡的闡述。
本書力求推理嚴密，因此對數學的要求相當高，要求讀者至少學過一學期的概率論課程且有扎實的數學背景，大致為本科高年級或研究生一年級水平。盡管如此，我們還是努力避免使用測度論。因為了解它只對第16章中的遍歷過程的AEP的證明過程起到簡化作用。這符合我們的觀點，那就是信息論基礎與技巧不同，后者才需要將所有推廣都寫進去。
本書的主體是第2、3、4、5、7、8、9、10、11和15章，它們自成體系，讀懂了它們就可以對信息論有很好的理解。但在我們看來，第14章的科爾莫戈羅夫復雜度是深入理解信息論所需的知識。余下的幾章，從博弈到不等式，目的是使主題更加連貫和完美。
任何教程都有它的第一講，目的是給出其主要思想的簡短預覽和概述。本書的第1章就是為這個目的而設置的。

Thomas M.Cover
Joy A.Thomas

Palo Alto, California
1990年6月