第2版前言

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

Thomas M.Cover
Joy A.Thomas

Palo Alto, California
2006年1月

第1版前言

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

Thomas M.Cover
Joy A.Thomas

Palo Alto, California
1990年6月