信息論第一講

1、第_章緒論1.1信息的概念研究信息及信息安全技術所面臨的第一個問題是：什么是信息？在不同的時代，對于不同的研究對象，人們會定義不同的信息概 念。我們可以從文獻中查到幾十個信息定義，其中最有影響的是由美 國科學家香農(C. E. Shannon)和語言學家所定義的信息。香農把問題限定在通信活動之中，因此他所定義的信息概念以通 信模型為基礎。從人類原始的思想情感交流方式發(fā)展到現(xiàn)代通信技術，經歷了漫 長的歷史過程。但是任何通信過程都符合一個基本的模型，即發(fā)送者 發(fā)出的消息經過傳輸后被接收者所接收，正如圖1-1所示。在這個最 簡單的通信模型中，信源是消息之源，通常指提供消息的人或設備， 例如打電話時的

2、說話人、廣播節(jié)日的電視臺等；信道是傳遞消息的通 道，包括電纜、光纖，以及傳輸電磁波的空間等；而信宿則是指消息 的接收者。信源 信道 信宿圖1-1最簡單的通信模型信源發(fā)出的消息可能是符號、文字、圖像或者聲音，傳送它們需 要借助于載體，通過載體的傳輸完成消息的傳遞。對于電子通信來說， 不可能使用物質載體，只能借助于能量載體，后者以電磁信號的形式 完成攜帶消息的任務。接收者從收到的信號中檢測出信源發(fā)出的原始 消息。如果接收者早已知道這個消息，就失去了這次通信的意義，接 收者感興趣的是收到新消息，收到原來不知道的內容。在這個意義上， 把信息定義為：定義1.1接收到的原來不知道的內容叫做信息。這樣定義的

3、信息概念可以進行度量，它在通信技術發(fā)展過程中發(fā) 揮了重要作用。辭海中對信息一詞的解釋顯然受到上述影響：通信 系統(tǒng)傳輸和處理的對象，泛指消息和信號的具體內容和意義，通常需 通過處理和分析來提取。信息、物質和能量被稱為系統(tǒng)的三大要素。 信息的量值與信息的隨機性有關，因此在接收端無法預估消息或者信 號中蘊涵的內容或意義，預估的可能性越小，信息量就越大。然而在網絡時代，通信效率和通信速率不再是人們關心的唯一問 題，人們常說的信息概念也遠遠超出了上述定義。另一方面，對定義 1.1的理解提出了一個問題，即當一個熟記小提琴協(xié)奏曲梁祝的人 再次欣賞那優(yōu)美樂章時，他是否收到了信息？依據(jù)不同的基準會有不同的答案。

4、如果把信息概念限定在“豆芽” 的排列上，則沒有收到信息，這反映在香農信息量H （X ） 0之中（見 第二章）；如果把音色、音質，以及演奏者注入的情感這些樂譜無法表 征的內容也看作是信息，則答案是肯定的。是啊，否則聽音樂（也是 一種通信過程）還有什么意義呢？由于信源發(fā)出的消息總是以某種符號表示（文字、圖像或者聲音都是符號），因此在符號學理論和信息概念之間就有一種不可分割的關 系。語言符號學的創(chuàng)始人之一莫里斯把語言分作三個方面：（1）符號和對象之間的關系叫做符號過程的語義方面，有關研究 叫語義學；（2）符號和解釋者之間的關系叫做符號過程的運用方面，有關研 究叫語用學；（3）符號相互之間的形式關系叫

5、做符號過程的語形方面，有關研 究叫語形學或句法學。語用學、語法學和句法學之間的關系如圖1-2所示。圖1-2語言符號學的關系有人從類似的視角提出了如下的信息定義：定義1.2消息中表達消息實質內容的部分叫做語義信息。定義1.3消息中說明語義信息表現(xiàn)格式的部分叫做語法信息。定義1.4語法信息和語義信息共同構成消息一本征信息。這種類似于語言符號學的定義方法自有其積極意義?，F(xiàn)代的通信 技術中，接收到的消息既包含消息的實質內容，也包含與之有關的語 法說明。例如我們傳輸一幅圖像數(shù)據(jù)時，還必須帶有這幅圖像的格式， 缺少了格式說明，接收端就很難得到應有的畫面。似乎這種定義方法 更適合網絡時代的需求。然而，無論是

6、語義信息、語用信息，還是本 征信息，都沒有直接指導信息技術的發(fā)展，即使在網絡比較充分普及 的今天，也很難看到從符號學的信息定義出發(fā)導出的具有理論或實際 意義的結果。在人類社會邁進信息時代的今天，信息已經成為社會生產力的重 要組成部分，人們不再只需要用信息理論研究通信問題，在信息的產 生、存儲、傳輸和應用過程中，都需要有信息理論的支持；人們也不 再只重視傳輸效率和可靠性問題，許多關于信息的新問題，例如信息 的完整性、有用性、安全性、時效性、可鑒別性等在現(xiàn)實的生產、生 活中已經不可回避。因此，“什么是信息”這個問題重新擺在我們的面 刖。那么，究竟應該如何定義信息才更符合實際需要？這樣的信息具 有什

7、么性質？眾說紛紜，尚未統(tǒng)一。我們認為，把香農的信息概念加 以泛化既有利于繼承前人的貢獻，又能適應當代科學發(fā)展的需要。作 為定義，可以表述為：定義1.5關于客觀事物的概念、屬性、相互關聯(lián)和運動規(guī)律的知 識，以及客觀事物屬性的自我顯現(xiàn)叫做信息。這個定義包含兩方面的內容：一是思維活動產生的結果，即所謂 知識，知識的存儲和傳輸就是信息的存儲和傳輸；二是客觀事物屬性 的自我顯現(xiàn)，例如我們觀察到藍天下的田野，這個畫面算不上什么知 識，卻是天空和田野屬性的自我顯現(xiàn)，觀察的過程就是我們通過視覺 系統(tǒng)接收信息的過程。關于第二方面的內容可以參考傳統(tǒng)信息論創(chuàng)始 人之一Wiener（維納）的信息定義：信息是人們在適應

8、外部世界和 控制外部世界的過程中，同外部世界進行交換內容的名稱。這個定義不強調原來是否知道，可以理解為香農信息論里所說的 消息。比如在因特網上傳輸?shù)暮Ａ啃畔⒅?，有有用的信息，也有無用 的修飾，對于那些無用的修飾等，也要可靠地傳輸，不允許馬塞克現(xiàn) 象的出現(xiàn)；為提高網絡傳輸效率，人們會采取限失真壓縮辦法，不一 定要剔除消息中原來意義上的冗余；相互傳送郵件時，斟酌字句去除 信息冗余的情況也難于遇到。實際傳輸?shù)谋忍芈适菍ο⒍?。然而這個定義沒有給出信息的定量標準。當我們說信息量的大小 時，往往關注實際的比特數(shù)。在信息安全成為眾所關心的議題時，這 樣的定義具有實際的意義。1.2信息的性質和信息概念的定

9、義一樣，人們總結了許多條信息的性質往往 帶有不同應用目的的影響這是無可厚非的。但是，在從應用層面 討論之前，更應該從信息的物理屬性方面觀察，因為這方面的性質是 更本質的東西。，性質1信息是普遍的客觀存在。按照定義1.5,即使在人類創(chuàng)立知識以前，信息也已經客觀存在。，性質2信息不守恒，即信息既可以消亡，也可以創(chuàng)生。大腦的思維活動可以創(chuàng)生新的知識，這些知識屬于新的信息內容; 獨版書籍或者存有某種數(shù)據(jù)的唯一光盤的銷毀意味著有關信息的消 亡。，性質3信息必須依賴于物質或能量而存在，依賴于物質或能量而 傳輸，即不存在離開物質和能量而獨立存在的信息，它必須以物質或 能量作為載體。，性質4信息可以復制，從而

10、可以分享。不像物質和能量那樣，信息可以無限復制，不同人可以同時擁有 同一份信息。，性質5對信息的處理不會增加信息的原始內容。這里所說的處理包括濾波、存儲、傳輸?shù)龋瑸V波處理是對原始信 息的修改，存儲和傳輸是對信息的轉移，在此過程中增加的所有內容 都不是原始的信息。例如從BMP圖像轉換成JPG圖像（可以歸為濾波 處理），且不說圖像細節(jié)的丟失，JPG格式的語法說明就不是原來的內 容；模糊圖像處理的結果本來就含在原來的信息之中；接收端收到的 信息不可能多于信源發(fā)出的信息，而且只有在接收靈敏度和感覺靈敏 度都達到一定水平時，二者才可能相等。信息的物理性質反映了信息的本質特征，決定了達到某種應用目 標的可

11、能性。從應用角度闡述的信息性質決定了信息技術的發(fā)展方向。從信息安全的角度看，人們關心的是信息的安全性、完整性、有 用性、時效性、可鑒別性等。秘密信息的保密、音像產品的非法復制 牽涉到信息的安全性問題，網絡路由的復雜性決定了能否保證信息的 完整性，信息的真實和時效意義是信息有用性的體現(xiàn)，保密性、真實 性和不可抵賴是可鑒別性的動因，等等。有些書上為信息歸納了十幾條性質，其中有些基于香農的信息定 義，有些從應用層面考慮，例如：1、新穎性一接收者收到信息之前，對其內容是不知道的，所以 信息是新知識、新內容；2、有益性一信息是能使認識某一事物的未知性或不確定性減少 的有用知識；3、可測性一信息是可度量的

12、，信息量的大小有差別；4、相對性一不同的接收者所得到的信息量不同；5、可加工性一信息可以產生、消失、攜帶、存儲和處理；6、轉移性信息可以在時間上或在空間中從一點轉移到另一點；7、變換性一一信息是可變換的，它可以由不同的載體和不同的 方法來載荷；8、有序性信息可以用來消除系統(tǒng)的不定性，增加系統(tǒng)的有 序性；9、 動態(tài)性一切活的信息都隨時間而變化，因此信息也是有 時效、有壽命的。這些甚至更多的性質，對信息安全的研究實際意義不大，倒是還 有些更加深入的內容值得我們思考，例如用不同的語氣講同樣的話表 示不同的意思，“言外之意”、“字里行間”等都反映了信息的復雜性質。 為了避免這些深層次因素的影響，我們不

13、打算用包羅萬象的概念來討 論信息，只局限在消息的層面上討論問題。1.3信息理論的發(fā)展信息理論是信息科學的基礎，強調用數(shù)學語言描述信息科學中的 共性問題和解決方案。到目前為止，信息理論一直處在發(fā)展之中，新 的研究成果可能僅局限于某個應用領域，也有可能具有廣泛的意義。 有人把信息理論劃分為狹義信息論、一般信息論和廣義信息論三個層 次，以說明其涵蓋范圍的不同。狹義信息論又稱香農信息論，主要總結了香農的研究成果，在信 息可度量的基礎上，研究如何有效、可靠地傳遞信息，重點是各種編 碼技術。它是通信問題的理論提升。香農分別于1948年和1949年 發(fā)表了兩篇著名文章：“the Mathematical T

14、heory of Communication” 和“ Communication in the Presence of Noise”，這兩篇文章討論了信息的度量、特征、傳輸速率、 信道容量以及干擾的影響等問題，用概率測度和數(shù)理統(tǒng)計方法系統(tǒng)地 闡述了通信的基本問題，奠定了信息科學的基礎，對通信技術的發(fā)展 做出了重大貢獻。盡管在此之前，奈奎斯特(H.Nyquist)已于1924 年解釋了信號帶寬和信息率間的關系，但是其影響遠不如香農這兩篇 文章的作用。一般信息論除了香農對信息科學的貢獻以外，還包括其它人的研 究成果，特別是美國科學家N. Wiener（維納）的微弱信號檢測理論。他 在與香農的同一時

15、期出版了兩本名著：trapolation，Interpolation and Smoothing of Stationary Time Series和Control Theory，討論微弱信 號的檢測問題，形成信息理論的另一個分支。信號檢測可以分為確知信號檢測和具有隨機參量的信號檢測，重 點研究如何從干擾中提取信息。一般信息論的研究包括噪聲理論、信 號的濾波與預測、統(tǒng)計檢測與估計理論、調制理論、信號處理與設計 理論等，它是廣義通信問題的理論提升。香農和維納的研究成果為通信和控制理論與技術的發(fā)展做出了開 創(chuàng)性的貢獻，可以名副其實地稱為信息理論的創(chuàng)始人。但是由于通信 技術對人類的影響更大，信息科學

16、的理論成果與通信技術聯(lián)系更多， 所以人們傾向于把香農叫做信息論的創(chuàng)始人?，F(xiàn)代信息科學涉及范圍非常廣泛，除了傳統(tǒng)的感測技術、通信技 術、控制技術、智能技術等以外，還涉及經濟學、心理學、語言學、 社會學等其它領域，特別是近年來發(fā)展迅猛的信息安全技術，顯然也 應該屬于信息科學的范疇，挨棄信息安全的信息理論是不完整的信息 理論。信息安全問題是自然科學和社會科學的融合體，廣義信息理論 不僅要討論客觀問題，也要涉及人的主觀因素，不僅要研究自然科學 問題，也要研究與之關聯(lián)的社會科學問題。廣義信息論的研究需要更般的信息概念（定義1.5）,日前尚未形成公認的理論體系，處于發(fā) 展之中。以上這種劃分有一定的方便之處

17、，它使得人們在討論信息問題時 不至于由于概念的不統(tǒng)一而無謂地爭執(zhí)，同時它也解釋了為什么很難 找到集大成的信息論，卻到處可見信息論基礎、導引等書的原因。信息理論的建立不僅促進了信息技術，也帶動了其它學科的發(fā) 展。例如，雖然香農理論主要解答通信理論中的兩個基本問題：臨界 數(shù)據(jù)壓縮的值（熵）和臨界傳輸速率的值（信道容量）但是也在統(tǒng)計 物理（熱力學）、計算機科學（Kolmogorov復雜度或算法復雜度）、統(tǒng) 計推斷（奧卡姆剃刀）、概率統(tǒng)計（假設檢驗的錯誤概率及估計的誤差 概率）經濟學等學科中發(fā)揮了奠基性的作用。信息安全的研究不僅是 信息理論的一個組成部分，也必然促進社會管理方面的進步。圖1-3 揭示了

18、信息科學與其它學科的關系。概率論統(tǒng)計學經濟學計算機科學物理學數(shù)學密碼學信息安全香農信息論 通信理論一般信息論噪聲理論、信號的濾波與預測、統(tǒng)計檢測與估計理論、 調制理論、信號處理與設計理論信息隱藏廠義信息論經濟學、心理學、語言學、社會學圖1-3信息科學包含的內容1.4本書內容安排本書主要討論有關信息安全的技術，其中部分章節(jié)利用了香農信 息論的知識，因此首先在第二章介紹了香農信息論的基本概念和幾個 重要定理。然后進入信息安全的內容。第三章是對信息安全的概述，主張從系統(tǒng)和運動的觀點來看待信 息安全問題，其中許多思想來自網絡技術，但是并不意味信息安全問 題為網絡技術所獨有。在這一章里，我們把信息安全概

19、念分為三個層 次，即A1安全、A2安全和A3安全，從而使信息安全問題更加系統(tǒng) 化。此后，我們在第四、五、六章中集中討論A1安全，涉及信息加 密、信息隱藏、認證和簽名技術。這一章涉及的內容非常廣泛，要在 有限的篇幅里進行詳細的論述是不現(xiàn)實的，因此我們不提倡用對具體 算法的深入取代對全局的宏觀了解，這樣更有利于思路的開闊。第七、八兩章討論A2安全，涉及訪問控制、入侵檢測、DoS攻 擊、惡意軟件和黑客技術。其中許多內容是網上零散信息的歸納。我們在第九章中討論A3安全，主要是對不良信息的處置。由于 最有效的處置不僅限于技術層面，法律約束、行政管理可能具有更大 的威力，但那不是本書的任務。最后，第十章對

20、工作中遇到的某些實際問題進行了討論。這些內 容具有兩個特點，要么對不同的實際情況而沒有具體深入討論，要么 涉及容易忽視的現(xiàn)象而沒有什么理論價值。應該指出，自然科學與社會科學的融合使得信息安全理論難于用 公式進行形式化的描述，對其涵義的分類幫助我們在邏輯上有了一個 系統(tǒng)的看法。第二章：香農信息論基礎盡管香農信息理論很難處理近些年來出現(xiàn)的信息及信息安全問 題，但是其基本思想對現(xiàn)代信息技術的發(fā)展仍有重大影響，本章將敘 述香農信息論的基本概念和幾個定理，目的是有助于對第四章、第五 章內容的深入理解，而不是對香農信息論的全面介紹。在以下討論技術問題的章節(jié)里，我們將遇到大量的公式，需要讀 者靜下心來，弄清

21、每個符號、每個公式的物理意義，從中學習定量分 析問題的方法思路，不要死記硬背。2.1基本概念2.1.1自信息在閱讀這一章內容時，我們要使用香農的信息概念。正如緒論 所述，香農信息和第三章里的信息之間存在差別。香農信息可以度量，為定量地解決通信速率、效率奠定了基礎。 那么，這個可以度量的信息概念是怎樣建立起來的呢？讓我們先看一 下實際的例子。假設天氣預報只預報明天是否下雨，那么只要給出一個符號就 可以表達清楚了，例如用1表示下雨，用0表示晴天。假設要發(fā)布“嫦 娥一號”月球衛(wèi)星發(fā)射成功與否的消息，也只需要一個符號，例如用 符號1表示發(fā)射成功，用符號0表示發(fā)射失敗。一般地說，我們可以 用符號1或0表

22、示一個隨機事件（下雨或發(fā)射成功）是否發(fā)生。和通信過程聯(lián)系起來，符號來源于消息的發(fā)送者，也就是來源 于信息源。我們把這種用一個符號就可以表示一條完整消息的信息源 叫做單符號信源。但是多數(shù)情況下，隨機事件集合中可能包含多個元 素（例如天氣預報有暴雨、大雨、中雨、小雨和雷陣雨之分），這時 僅用一個符號就不能反映發(fā)生了哪個具體事件，需要用符號序列來代 表各個具體事件，消息源則變成發(fā)出符號序列的信息源。正規(guī)地，如果信源輸出是隨機變量X所表示的隨機事件，其出 現(xiàn)概率是尸(X)，則它們所構成的集合叫做信源的概率空間，簡稱信源 空間，用如下方式表示：X, P : X：% 1,% 2，% nP(X): P (x

23、i), P (x2),，P (xn) (2-1)其中P (X)滿足 n P(x ) = , n是自然數(shù)。干旱地區(qū)下雨的可能性是很小的，設其概率為0.1，而晴天的概 率為0.9。因為我們通常認為在干旱地區(qū)不會下雨，一旦氣象臺發(fā)出 符號1，我們就得到了較大的信息量，反之，預報天晴和我們原來的 想法一致，就沒有太多的信息量。這說明信息量應該是概率的函數(shù)， 而且概率越大信息量就越小，即信息量是概率的減函數(shù)?？紤]到概率 可以在0，1區(qū)間內連續(xù)取值，所以信息量是連續(xù)函數(shù)較為合理。概率等于1的必然事件是一定要發(fā)生的，它的出現(xiàn)不會給我們 帶來任何新的信息，信息量應該為0;而對于概率等于0的不可能事 件，一旦出

24、現(xiàn)將給我們帶來極大的震撼，其信息量應該是無窮大。再假設天氣預報不僅預報明天是否下雨，而且公布空氣污染指 數(shù)，那么聽眾得到的信息就包含兩部分互相獨立的內容，這時的聯(lián)合 信息量應該是兩個信息量之和。根據(jù)上面介紹的信息量應該具有的屬性，我們選擇對數(shù)函數(shù)來 度量信息量。定義2.1事件七的出現(xiàn)所帶來的信息I(x.) log 1 / P(x.) - log P(x.)(2-2)稱為事件x |的自信息量?？梢钥吹?，上述定義完全符合信息量應該具有的屬性，因此是 合理的。但是這個結果沒有量綱，會為以后的研究帶來不便，為此， 我們根據(jù)對數(shù)的底來規(guī)定信息量的量綱：以2為底時用lb表示，信 息量的單位是比特(bit)

25、；以e為底時用ln表示，信息量的單位是奈 特(nat)；以10為底時用lg表示，信息量的單位是哈特(Hart)。以下如果不作特殊說明，我們將習慣地使用更具一般性的符號 log，但是以2為底來計算數(shù)值。例2.1設有一個符號1、0等概率出現(xiàn)的隨機信源，求任一碼元 的自信息量。解 I(x.) = -l o P(x.) = -l o g/2 = 1(bit), x i=0 或 1。例2.2對于2 n進制的數(shù)字序列，假設每一符號的出現(xiàn)完全隨機 且概率相等，求任一符號的自信息量。解 因為2n進制的數(shù)字序列中任一碼元x |的出現(xiàn)概率都相等， 所以其信息量為1I (x.) = - log P (x.) = -

26、 log 1/2 n = n (bit)由此例可以看出，一個事件的自信息量只取決于事件出現(xiàn)的概 率，與它的內容或取值無關。2.1.2 熵式(2-2)的定義是從通信的角度考慮的，它表示信宿收到一條 消息以后所得到的信息量。現(xiàn)在設想信宿處于尚未收到消息的等待過 程中，那么將來的消息如何對它來說是不確定的，而一旦收到消息， 這個不確定量就消失了。所以一個隨機事件出現(xiàn)所給出的信息量就應 該等于該隨機事件的不確定程度?？紤]到某些情況下，事件的不確定 程度不會完全消失，所以一般地說，隨機事件出現(xiàn)所給出的信息量是 該事件不確定度減少的數(shù)量。隨機事件的不確定度也是概率的函數(shù)。它與信息量不同之處是 并不要求該隨

27、機事件真的發(fā)生。公式(2-2)中的I (x |)表示的是信源發(fā)出某一具體符號x |的自信 息量。當隨機事件集合中包含多個元素，且每個元素的概率不相等時， 用式(2-2)只能計算每個元素各自的自信息量，不能作為整個隨機 事件集合的總體信息測度。下面的例子就是這種情況。例2.3假定有8匹馬參加的一場賽馬比賽，它們獲勝的概率分 別是 1/2, 1/4, 1/8, 1/16, 1/64, 1/64, 1/64, 1/64,計算每匹馬獲勝給出的 自信息量。解 第1匹馬獲勝的信息量是I (x 1) = - log (1/2) = 1； 第2匹馬獲勝的信息量是I (x 2)= - log (1/4) = 2

28、； 第3匹馬獲勝的信息量是I (x 3)= - log (1/8) = 3； 第4匹馬獲勝的信息量是I (x 4)= - log (1/16) = 4； 第58匹馬獲勝的信息量是I (x 5-8) = - log (1/64) = 6。例中得到了 5個不同的結果，其中任何一個都不能代表賽馬比 賽的總體信息測度。但是比賽結果的不確定度應該有一個確定的值， 顯然，我們可以計算其平均值作為不確定程度的測度。但是若如下計 算，所得結果是不正確的，因為它沒有反映每匹馬獲勝的概率。I = Z 8 i(Xj )/8 = 4.25正確的結果應該是各個自信息量的加權平均。我們把這個加權的平均 自信息量叫做熵。定義2.2若隨機事件集合X包含n個元素X , x，x ,它們的 2n出現(xiàn)概率分別是P (x 1), P (x 2),，P (x n)，則隨機事件X的熵是:H(X) = Zn P(xi)I(xi)= -Z p(x