信息論第一講

101.1信息的概念爭論信息及信息安全技術(shù)所面臨的第一個(gè)問題是：什么是信息？在不同的時(shí)代，對于不同的爭論對象，人們會定義不同的信息概國科學(xué)家香農(nóng)(C.E.Shannon)和語言學(xué)家所定義的信息。香農(nóng)把問題限定在通信活動(dòng)之中，因此他所定義的信息概念以通信模型為根底。從人類原始的思想情感溝通方式進(jìn)展到現(xiàn)代通信技術(shù)，經(jīng)受了漫長的歷史過程。但是任何通信過程都符合一個(gè)根本的模型，即發(fā)送者1-1所示。在這個(gè)最簡潔的通信模型中，信源是消息之源，通常指供給消息的人或設(shè)備，例如打時(shí)的說話人、播送節(jié)目的電視臺等；信道是傳遞消息的通道，包括電纜、光纖，以及傳輸電磁波的空間等；而信宿則是指消息的接收者。信源信源信道信宿1-1最簡潔的通信模型信源發(fā)出的消息可能是符號、文字、圖像或者聲音，傳送它們需1.1接收到的原來不知道的內(nèi)容叫做信息。不行能使用物質(zhì)載體，只能借助于能量載體，后者以電磁信號的形式完成攜帶消息的任務(wù)。接收者從收到的信號中檢測出信源發(fā)出的原始消息。假設(shè)接收者早道這個(gè)消息，就失去了這次通信的意義，接1.1接收到的原來不知道的內(nèi)容叫做信息。這樣定義的信息概念可以進(jìn)展度量，它在通信技術(shù)進(jìn)展過程中發(fā)揮了重要作用系統(tǒng)傳輸和處理的對象，泛指消息和信號的具體內(nèi)容和意義，通常需通過處理和分析來提取。信息、物質(zhì)和能量被稱為系統(tǒng)的三大要素。信息的量值與信息的隨機(jī)性有關(guān)，因此在接收端無法預(yù)估消息或者信號中蘊(yùn)涵的內(nèi)容或意義，預(yù)估的可能性越小，信息量就越大。然而在網(wǎng)絡(luò)時(shí)代，通信效率和通信速率不再是人們關(guān)心的唯一問題，人們常說的信息概念也遠(yuǎn)遠(yuǎn)超出了上述定義。另一方面，對定義的理解提出了一個(gè)問題，即當(dāng)一個(gè)熟記小提琴協(xié)奏曲《梁?！返娜嗽俅钨p識那美麗樂章時(shí)，他是否收到了信息？依據(jù)不同的基準(zhǔn)會有不同的答案。假設(shè)把信息概念限定在“豆芽”的排列上，則沒有收到信息，這反映在香農(nóng)信息量H(X) 0之中〔見其次章；假設(shè)把音色、音質(zhì)，以及演奏者注入的情感這些樂譜無法表征的內(nèi)容也看作是信息，則答案是確定的。是啊，否則聽音樂〔也是一種通信過程〕還有什么意義呢？由于信源發(fā)出的消息總是以某種符號表示〔文字、圖像或者聲音都是符號系。語言符號學(xué)的創(chuàng)始人之一莫里斯把語言分作三個(gè)方面：叫語義學(xué)；爭論叫語用學(xué)；爭論叫語形學(xué)或句法學(xué)。1-2所示。語用學(xué)語義學(xué)句法學(xué)1-2語用學(xué)語義學(xué)句法學(xué)號學(xué)的關(guān)系有人從類似的視角提出了如下的信息定義：1.2消息中表達(dá)消息實(shí)質(zhì)內(nèi)容的局部叫做語義信息。1.3消息中說明語義信息表現(xiàn)格式的局部叫做語法信息。1.4語法信息和語義信息共同構(gòu)成消息—本征信息。這種類似于語言符號學(xué)的定義方法自有其樂觀意義?，F(xiàn)代的通信技術(shù)中，接收到的消息既包含消息的實(shí)質(zhì)內(nèi)容，也包含與之有關(guān)的語缺少了格式說明，接收端就很難得到應(yīng)有的畫面。似乎這種定義方法更適合網(wǎng)絡(luò)時(shí)代的需求。然而，無論是語義信息、語用信息，還是本征信息，都沒有直接指導(dǎo)信息技術(shù)的進(jìn)展，即使在網(wǎng)絡(luò)比較充分普及的今日，也很難看到從符號學(xué)的信息定義動(dòng)身導(dǎo)出的具有理論或?qū)嶋H意義的結(jié)果。在人類社會邁進(jìn)信息時(shí)代的今日，信息已經(jīng)成為社會生產(chǎn)力的重要組成局部，人們不再只需要用信息理論爭論通信問題，在信息的產(chǎn)生、存儲、傳輸和應(yīng)用過程中，都需要有信息理論的支持；人們也不再只重視傳輸效率和牢靠性問題，很多關(guān)于信息的問題，例如信息的完整性、有用性、安全性、時(shí)效性、可鑒別性等在現(xiàn)實(shí)的生產(chǎn)、生活中已經(jīng)不行回避。因此前。定義1.5定義1.5關(guān)于客觀事物的概念、屬性、相互關(guān)聯(lián)和運(yùn)動(dòng)規(guī)律的知識，以及客觀事物屬性的自我顯現(xiàn)叫做信息。識，以及客觀事物屬性的自我顯現(xiàn)叫做信息。這個(gè)定義包含兩方面的內(nèi)容：一是思維活動(dòng)產(chǎn)生的結(jié)果，即所謂學(xué)問，學(xué)問的存儲和傳輸就是信息的存儲和傳輸；二是客觀事物屬性的自我顯現(xiàn)，例如我們觀看到藍(lán)天下的田野，這個(gè)畫面算不上什么學(xué)問，卻是天空和田野屬性的自我顯現(xiàn)，觀看的過程就是我們通過視覺系統(tǒng)接收信息的過程。關(guān)于其次方面的內(nèi)容可以參考傳統(tǒng)信息論創(chuàng)始人之一——Wiener(維納)的信息定義：信息是人們在適應(yīng)外部世界和掌握外部世界的過程中，同外部世界進(jìn)展交換內(nèi)容的名稱。這個(gè)定義不強(qiáng)調(diào)原來是否知道，可以理解為香農(nóng)信息論里所說的消息。比方在因特網(wǎng)上傳輸?shù)暮Ａ啃畔⒅?，有有用的信息，也有無用的修飾，對于那些無用的修飾等，也要牢靠地傳輸，不允許馬塞克現(xiàn)象的消滅；為提高網(wǎng)絡(luò)傳輸效率，人們會實(shí)行限失真壓縮方法，不肯定要剔除消息中原來意義上的冗余；相互傳送郵件時(shí)，斟酌字句去除信息冗余的狀況也難于遇到。實(shí)際傳輸?shù)谋忍芈适菍ο⒍?。然而這個(gè)定義沒有給出信息的定量標(biāo)準(zhǔn)。當(dāng)我們說信息量的大小時(shí)，往往關(guān)注實(shí)際的比特?cái)?shù)。在信息安全成為眾所關(guān)心的議題時(shí)，這樣的定義具有實(shí)際的意義。信息的性質(zhì)和信息概念的定義一樣，人們總結(jié)了很多條信息的性質(zhì)——往往帶有不同應(yīng)用目的的影響——這是無可厚非的。但是，在從應(yīng)用層面爭論之前，更應(yīng)當(dāng)從信息的物理屬性方面觀看，由于這方面的性質(zhì)是更本質(zhì)的東西。1信息是普遍的客觀存在。1.5，即使在人類創(chuàng)立學(xué)問以前，信息也已經(jīng)客觀存在。2信息不守恒，即信息既可以消亡，也可以創(chuàng)生。獨(dú)版書籍或者存有某種數(shù)據(jù)的唯一光盤的銷毀意味著有關(guān)信息的消亡。3信息必需依靠于物質(zhì)或能量而存在，依靠于物質(zhì)或能量而傳輸，即不存在離開物質(zhì)和能量而獨(dú)立存在的信息，它必需以物質(zhì)或能量作為載體。4信息可以復(fù)制，從而可以共享。不像物質(zhì)和能量那樣，信息可以無限復(fù)制，不同人可以同時(shí)擁有同一份信息。5對信息的處理不會增加信息的原始內(nèi)容。這里所說的處理包括濾波、存儲、傳輸?shù)?，濾波處理是對原始信息的修改，存儲和傳輸是對信息的轉(zhuǎn)移，在此過程中增加的全部內(nèi)容BMPJPG〔可以歸為濾波處理JPG容；模糊圖像處理的結(jié)果原來就含在原來的信息之中；接收端收到的信息不行能多于信源發(fā)出的信息，而且只有在接收靈敏度和感覺靈敏度都到達(dá)肯定水尋常，二者才可能相等。信息的物理性質(zhì)反映了信息的本質(zhì)特征，打算了到達(dá)某種應(yīng)用目標(biāo)的可能性。從應(yīng)用角度闡述的信息性質(zhì)打算了信息技術(shù)的進(jìn)展方向。從信息安全的角度看，人們關(guān)心的是信息的安全性、完整性、有用性、時(shí)效性、可鑒別性等。隱秘信息的保密、音像產(chǎn)品的非法復(fù)制牽涉到信息的安全性問題，網(wǎng)絡(luò)路由的簡單性打算了能否保證信息的完整性，信息的真實(shí)和時(shí)效意義是信息有用性的表達(dá)，保密性、真實(shí)性和不行抵賴是可鑒別性的動(dòng)因，等等。有些書上為信息歸納了十幾條性質(zhì)，其中有些基于香農(nóng)的信息定義，有些從應(yīng)用層面考慮，例如：1、穎性—接收者收到信息之前，對其內(nèi)容是不知道的，所以信息是學(xué)問、內(nèi)容；2、有益性—信息是能使生疏某一事物的未知性或不確定性削減的有用學(xué)問；3、可測性—信息是可度量的，信息量的大小有差異；4、相對性—不同的接收者所得到的信息量不同；5、可加工性—信息可以產(chǎn)生、消逝、攜帶、存儲和處理；6、轉(zhuǎn)移性——信息可以在時(shí)間上或在空間中從一點(diǎn)轉(zhuǎn)移到另一點(diǎn)；7、變換性——信息是可變換的，它可以由不同的載體和不同的方法來載荷；8、有序性——信息可以用來消退系統(tǒng)的不定性，增加系統(tǒng)的有序性；9、動(dòng)態(tài)性——一切活的信息都隨時(shí)間而變化，因此信息也是有時(shí)效、有壽命的。這些甚至更多的性質(zhì)，對信息安全的爭論實(shí)際意義不大，倒是還有些更加深入的內(nèi)容值得我們思考，例如用不同的語氣講同樣的話表示不同的意思為了避開這些深層次因素的影響，我們不打算用包羅萬象的概念來爭論信息，只局限在消息的層面上爭論問題。信息理論的進(jìn)展信息理論是信息科學(xué)的根底，強(qiáng)調(diào)用數(shù)學(xué)語言描述信息科學(xué)中的共性問題和解決方案。到目前為止，信息理論始終處在進(jìn)展之中，的爭論成果可能僅局限于某個(gè)應(yīng)用領(lǐng)域，也有可能具有廣泛的意義。有人把信息理論劃分為狹義信息論、一般信息論和廣義信息論三個(gè)層次，以說明其涵蓋范圍的不同。狹義信息論又稱香農(nóng)信息論，主要總結(jié)了香農(nóng)的爭論成果，在信息可度量的根底上，爭論如何有效、牢靠地傳遞信息，重點(diǎn)是各種編碼技術(shù)。它是通信問題的理論提升。香農(nóng)分別于1948年和1949theMathematicalTheoryofCommunication”和“CommunicationinthePresenceofNois信道容量以及干擾的影響等問題，用概率測度和數(shù)理統(tǒng)計(jì)方法系統(tǒng)地闡述了通信的根本問題，奠定了信息科學(xué)的根底，對通信技術(shù)的進(jìn)展做出了重大奉獻(xiàn)。盡管在此之前，奈奎斯特(H.Nyquist)已于1924年解釋了信號帶寬和信息率間的關(guān)系，但是其影響遠(yuǎn)不如香農(nóng)這兩篇文章的作用。一般信息論除了香農(nóng)對信息科學(xué)的奉獻(xiàn)以外，還包括其它人的爭論成果，特別是美國科學(xué)家N.Wiener(維納)的微弱信號檢測理論。他在與香農(nóng)的同一時(shí)期出版了兩本名著trapolation，InterpolationandSmoothingofStationaryTimeSeriesControlTheory號的檢測問題，形成信息理論的另一個(gè)分支。信號檢測可以分為確知信號檢測和具有隨機(jī)參量的信號檢測，重點(diǎn)爭論如何從干擾中提取信息。一般信息論的爭論包括噪聲理論、信號的濾波與推測、統(tǒng)計(jì)檢測與估量理論、調(diào)制理論、信號處理與設(shè)計(jì)理論等，它是廣義通信問題的理論提升。香農(nóng)和維納的爭論成果為通信和掌握理論與技術(shù)的進(jìn)展做出了開創(chuàng)性的奉獻(xiàn)，可以名副其實(shí)地稱為信息理論的創(chuàng)始人。但是由于通信技術(shù)對人類的影響更大，信息科學(xué)的理論成果與通信技術(shù)聯(lián)系更多，所以人們傾向于把香農(nóng)叫做信息論的創(chuàng)始人?，F(xiàn)代信息科學(xué)涉及范圍格外廣泛，除了傳統(tǒng)的感測技術(shù)、通信技術(shù)、掌握技術(shù)、智能技術(shù)等以外，還涉及經(jīng)濟(jì)學(xué)、心理學(xué)、語言學(xué)、社會學(xué)等其它領(lǐng)域，特別是近年來進(jìn)展迅猛的信息安全技術(shù)，明顯也應(yīng)當(dāng)屬于信息科學(xué)的范疇，擯棄信息安全的信息理論是不完整的信息理論。信息安全問題是自然科學(xué)和社會科學(xué)的融合體，廣義信息理論不僅要爭論客觀問題，也要涉及人的主觀因素，不僅要爭論自然科學(xué)問題，也要爭論與之關(guān)聯(lián)的社會科學(xué)問題。廣義信息論的爭論需要更密碼學(xué)香農(nóng)信息論通信理論一般信息論噪聲理論、信號的濾波與推測、統(tǒng)計(jì)檢測與估量理論、調(diào)制理論、信號處理與設(shè)計(jì)理論信息安全一般的信息概念〔定義1.密碼學(xué)香農(nóng)信息論通信理論一般信息論噪聲理論、信號的濾波與推測、統(tǒng)計(jì)檢測與估量理論、調(diào)制理論、信號處理與設(shè)計(jì)理論信息安全以上這種劃分有肯定的便利之處，它使得人們在爭論信息問題時(shí)不至于由于概念的不統(tǒng)一而無謂地爭吵，同時(shí)它也解釋了為什么很難計(jì)算機(jī)科學(xué)信息理論的建立不僅促進(jìn)了信息技術(shù)，也帶動(dòng)了其它學(xué)科的發(fā)展。例如，雖然香農(nóng)理論主要解答通信理論中的兩個(gè)根本問題：臨界數(shù)據(jù)壓縮的值〔熵〕和臨界傳輸速率的值〔信道容量，但是也在統(tǒng)計(jì)物理〔熱力學(xué)、計(jì)算機(jī)科學(xué)〔Kolmogorov簡單度或算法簡單度、統(tǒng)計(jì)推斷〔奧卡姆剃刀、概率統(tǒng)計(jì)〔假設(shè)檢驗(yàn)的錯(cuò)誤概率及估量的誤差概率〕經(jīng)濟(jì)學(xué)等學(xué)科中發(fā)揮了奠基性的作用。信息安全的爭論不僅是信息理論的一個(gè)組成局部，也必定促進(jìn)社會治理方面的進(jìn)步。圖1-3提醒了信息科學(xué)與其它學(xué)科的關(guān)系。計(jì)算機(jī)科學(xué)概率論統(tǒng)計(jì)學(xué)經(jīng)濟(jì)學(xué)物理學(xué)數(shù)學(xué)概率論統(tǒng)計(jì)學(xué)經(jīng)濟(jì)學(xué)物理學(xué)數(shù)學(xué)信息隱蔽信息隱蔽廣義信息論廣義信息論經(jīng)濟(jì)學(xué)、心理學(xué)、語言學(xué)、社會學(xué)1-3信息科學(xué)包含的內(nèi)容本書內(nèi)容安排重要定理。然后進(jìn)入信息安全的內(nèi)容。A1A2A3化。A1密、信息隱蔽、認(rèn)證和簽名技術(shù)。這一章涉及的內(nèi)容格外廣泛，要在算法的深入取代對全局的宏觀了解，這樣更有利于思路的開闊。A2DoS擊、惡意軟件和黑客技術(shù)。其中很多內(nèi)容是網(wǎng)上零散信息的歸納。A3的威力，但那不是本書的任務(wù)。涉及簡潔無視的現(xiàn)象而沒有什么理論價(jià)值。系統(tǒng)的看法。其次章：香農(nóng)信息論根底盡管香農(nóng)信息理論很難處理近些年來消滅的信息及信息安全問章內(nèi)容的深入理解，而不是對香農(nóng)信息論的全面介紹。析問題的方法思路，不要死記硬背。根本概念自信息在閱讀這一章內(nèi)容時(shí)，我們要使用香農(nóng)的信息概念。正如緒論所述，香農(nóng)信息和第三章里的信息之間存在差異。香農(nóng)信息可以度量，為定量地解決通信速率、效率奠定了根底。下實(shí)際的例子。假設(shè)天氣預(yù)報(bào)只預(yù)報(bào)明天是否下雨，那么只要給出一個(gè)符號就101010表示一個(gè)隨機(jī)大事〔下雨或放射成功〕是否發(fā)生。和通信過程聯(lián)系起來，符號來源于消息的發(fā)送者，也就是來源素〔例如天氣預(yù)報(bào)有暴雨、大雨、中雨、小雨和雷陣雨之分，這時(shí)表各個(gè)具體大事，消息源則變成發(fā)出符號序列的信息源。X所表示的隨機(jī)大事，其消滅概率是PX)空間，用如下方式表示：[X,P]: X： x1, x2,, ?, xnP(X): P (x) , P (x) , ?, P (x)1 2 n(2-1)P(X)滿足

ni1

P(xi

1n是自然數(shù)。干旱地區(qū)下雨的可能性是很小的，設(shè)其概率為0.1，而晴天的概0.9。由于我們通常認(rèn)為在干旱地區(qū)不會下雨，一旦氣象臺發(fā)出1，我們就得到了較大的信息量，反之，預(yù)報(bào)天晴和我們原來的想法全都，就沒有太多的信息量。這說明信息量應(yīng)當(dāng)是概率的函數(shù)，可以在[0，1]區(qū)間內(nèi)連續(xù)取值，所以信息量是連續(xù)函數(shù)較為合理。1的必定大事是肯定要發(fā)生的，它的消滅不會給我們帶來任何的信息，信息量應(yīng)當(dāng)為0；而對于概率等于0的不行能大事，一旦消滅將給我們帶來極大的震撼，其信息量應(yīng)當(dāng)是無窮大。再假設(shè)天氣預(yù)報(bào)不僅預(yù)報(bào)明天是否下雨，而且公布空氣污染指信息量應(yīng)當(dāng)是兩個(gè)信息量之和。依據(jù)上面介紹的信息量應(yīng)當(dāng)具有的屬性，我們選擇對數(shù)函數(shù)來度量信息量。2.1xi的消滅所帶來的信息II(x)log1/P(x)logP(x)iii(2-2)x的自信息量。i息量的單位是比特bi；以e為底時(shí)用ln息量的單位是比特bi；以e為底時(shí)用ln表示，信息量的單位是奈特特na；以10為底時(shí)用lg表示，信息量的單位是哈特Har。以下假設(shè)不作特別說明，我們將習(xí)慣地使用更具一般性的符號log2為底來計(jì)算數(shù)值。2.110的自信息量。解I(x)log(x)lo/21(bit), x=0或1。i i i例2.2對于2n 進(jìn)制的數(shù)字序列假設(shè)每一符號的消滅完全隨機(jī)且概率相等，求任一符號的自信息量。解由于2nxi的消滅概率都相等，所以其信息量為i I(x)logP(x)log1/2ni 由此例可以看出，一個(gè)大事的自信息量只取決于大事消滅的概率，與它的內(nèi)容或取值無關(guān)。率，與它的內(nèi)容或取值無關(guān)。熵式〔2-2〕的定義是從通信的角度考慮的，它表示信宿收到一條程中，那么將來的消息如何對它來說是不確定的，而一旦收到消息，該大事不確定度削減的數(shù)量。該大事不確定度削減的數(shù)量。隨機(jī)大事的不確定度也是概率的函數(shù)。它與信息量不同之處是并不要求該隨機(jī)大事真的發(fā)生。公式(2-2)I(x〕x的自信i i用式〔2-2〕只能計(jì)算每個(gè)元素各自的自信息量，不能作為整個(gè)隨機(jī)大事集合的總體信息測度。下面的例子就是這種狀況。2.38匹馬參與的一場賽馬競賽，它們獲勝的概率分1/2,1/4,1/8,1/16,1/64,1/64,1/64,1/64,計(jì)算每匹馬獲勝給出的自信息量。解1匹馬獲勝的信息量是I〔x〕=log(1/21；12匹馬獲勝的信息量是I〔x〕=log(1/42；23匹馬獲勝的信息量是I〔x〕=log(1/83；3匹馬獲勝的信息量是I〔x〕=log(1/164；4第5—8匹馬獲勝的信息量是I〔x 5-85個(gè)不同的結(jié)果，其中任何一個(gè)都不能代表賽馬競賽的總體信息測度。但是競賽結(jié)果的不確定度應(yīng)當(dāng)有一個(gè)確定的值，算，所得結(jié)果是不正確的，由于它沒有反映每匹馬獲勝的概率。I[8i1

i(xi

)]/84.25自信息量叫做熵。自信息量叫做熵。2.2Xnx,x,?,x,它們的1 2 n

), P(x1

), ?, P(x2

X的熵是：nH(X)ni1

P(xi

)I(xi

)X

p(x)logp(x)(2-3)x0xlogx→00log0=0。這個(gè)定義和通信過程沒有直接的關(guān)聯(lián)，它具有一般性。2.3中賽馬結(jié)果的不確定性，或者競賽的總體信息測度了：H(X)=-1/2log1/2-1/4log1/4 -1