第2版前言

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

Thomas M.Cover
Joy A.Thomas

Palo Alto, California
2006年1月

第1版前言

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

Thomas M.Cover
Joy A.Thomas

Palo Alto, California
1990年6月