第1講-信息論的對象與方法

信息論基礎(chǔ)王子龍

Office：老校區(qū)老科技樓A405E-mail：zlwang@教材

信息論與編碼理論，

王育民、李暉編，高等教育出版社參考書1.ElementsofInformationTheory,ThomasM.Cover,JoyA.Thomas著2.信息論—基礎(chǔ)理論與應(yīng)用,傅祖蕓編,電子工業(yè)出版社3.應(yīng)用信息論基礎(chǔ)，朱雪龍編，清華大學出版社信息論的對象

與方法第一講什么是信息?科學名詞：統(tǒng)計數(shù)學、通信技術(shù)

用嚴格的數(shù)學公式定義的科學名詞，它與內(nèi)容無關(guān)，而且不隨信息具體表現(xiàn)形式的變化而變化，因而也獨立于形式。情報、知識、消息計算機處理中的數(shù)據(jù)、文字廣義信息：技術(shù)術(shù)語：是事物運動狀態(tài)或存在方式不確定性的描述。情報知識消息信源輸出碼字輸出消息先驗概率消息后驗概率收到0收到01收到011x1x2x3x4x5x6x7x80000010100111001011101111/81/81/81/81/81/81/81/8√√√√××××××√√×××××××√××××信息、消息和信號信息是事物運動狀態(tài)或存在方式不確定性的描述。消息是指包含有信息的語言、文字和圖像等。信號是消息的物理體現(xiàn)。信源輸出碼字輸出消息先驗概率消息后驗概率收到0收到01收到011x1x2x3x4x5x6x7x80000010100111001011101111/81/81/81/81/81/81/81/8√√√√××××××√√×××××××√××××消息信號Shannon信息定義信源信道信宿噪聲或干擾簡單通信系統(tǒng)框圖不知、不確定消除或部分消除不知、不確定信息的特征不確定性，接收者在收到信息之前，對它的內(nèi)容是不知道的；信息能使認識主體對某一事物的未知性或不確定性減少；信息是可以量度的不確定性【例】摸球試驗

甲袋共100個球，紅球白球各50個；乙袋共100個球，紅、白、藍、黑球各25個；現(xiàn)隨意從甲袋或乙袋中取出一球，并猜測取出球的顏色？事物出現(xiàn)某狀態(tài)不確定性的大小，與該狀態(tài)出現(xiàn)的概率大小有關(guān)不確定性度量【例】氣象預報甲地：乙地：事物出現(xiàn)某狀態(tài)不確定性的大小，與該狀態(tài)出現(xiàn)的概率大小有關(guān)不確定性度量輸入消息碼字輸出消息先驗概率消息后驗概率收到0收到01收到011x1x2x3x4x5x6x7x80000010100111001011101111/81/81/81/81/81/81/81/81/41/41/41/40000001/21/2000000010000概率空間樣本空間信源所有可能發(fā)送的消息符號先驗概率p(xi)選擇符號xi作為發(fā)送消息的概率不確定性大小不確定性大小信息定義應(yīng)該滿足以下3個條件是單調(diào)減函數(shù)獨立可加性1.2.3.自信息條件自信息

信息定義先驗概率p(xi)

－選擇符號xi作為發(fā)送消息的概率后驗概率p(xi|yj)

－接收端收到消息yj后而發(fā)送端發(fā)的是xi

的概率輸入消息碼字輸出消息先驗概率消息后驗概率收到0收到01收到011x1x2x3x4x5x6x7x80000010100111001011101111/81/81/81/81/81/81/81/81/41/41/41/40000001/21/2000000010000香農(nóng)定義的信息的優(yōu)缺點

優(yōu)點有明確的數(shù)學模型和定量計算公式與日常用語中的信息含意一致排除了對信息一詞某些主觀上的含意局限性沒有考慮收信者的主觀特性和主觀意義定義的出發(fā)點假定事物狀態(tài)可以用一個概率模型來描述信息論研究對象信道信源信源編碼加密信道編碼干擾源信宿信源譯碼解密信道譯碼加密密鑰解密密鑰信息論研究目的尋找信息傳輸過程中的共同規(guī)律，以提高信息傳輸?shù)目煽啃?、有效性、保密性和認證性，使達到信息傳輸系統(tǒng)最優(yōu)化數(shù)字通信系統(tǒng)模型信道信源信源編碼加密信道編碼干擾源信宿信源譯碼解密信道譯碼加密密鑰解密密鑰信源信源編碼信道信道編碼信息論研究的內(nèi)容狹義信息論（香農(nóng)基本理論）主要研究信息的測度、信道容量以及信源和信道編碼理論等問題。一般信息論除香農(nóng)信息論，還包括噪聲理論、信號濾波和預測、統(tǒng)計檢測和估計等。廣義信息論不僅包括上述兩方面內(nèi)容，而且包括所有與信息有關(guān)的自然和社會領(lǐng)域，如模式識別、心理學等本課程研究的主要內(nèi)容信源信道信宿噪聲源編碼器譯碼器消息干擾信號＋干擾消息信息論基礎(chǔ)：信息量和熵（第2章）信源編碼（第3章）信道及其容量（第4章）信道編碼定理（第5章）線性分組碼（第6章）率失真初步（第9章）ClaudeShannon(1916-2001)1916年生于美國密歇根州的加洛德鎮(zhèn)，

2001年在馬薩諸塞州辭世，享年85歲。阿爾茨海默癥（退化性老年癡呆癥）

父親是加洛德鎮(zhèn)的法官，母親是鎮(zhèn)里中學校長，他生長在一個有良好教育的環(huán)境，不過父母給他的科學影響好像還不如祖父的影響大。香農(nóng)的祖父是一位農(nóng)場主兼發(fā)明家，發(fā)明過洗衣機和許多農(nóng)業(yè)機械。香農(nóng)心目中的英雄是愛迪生，后來才知道他與愛迪生還有遠親關(guān)系。ClaudeShannon(1916-2001)1936年在密歇根大學獲數(shù)學與電氣工程學士學位。1938年在MIT獲得電氣工程碩士學位，碩士論文題目是《ASymbolicAnalysisofRelayandSwitchingCircuits》(繼電器與開關(guān)電路的符號分析)。他把布爾代數(shù)的真與假和電路系統(tǒng)的開與關(guān)對應(yīng)起來,用布爾代數(shù)分析并優(yōu)化開關(guān)電路，奠定了數(shù)字電路的理論基礎(chǔ)。哈佛大學的Gardner教授說“這可能是本世紀最重要、最著名的一篇碩士論文”。1940年在MIT獲數(shù)學博士學位，博士論文關(guān)于人類遺傳學的，題目是《AnAlgebraforTheoreticalGenetics》(理論遺傳學的代數(shù)學)。

ClaudeShannon(1916-2001)

就職于貝爾電話研究所，他受著前輩的工作的啟示,在信息論的領(lǐng)域中鉆研了8年之久，終于在1948年也在《貝爾系統(tǒng)技術(shù)雜志》上發(fā)表了244頁的長篇論著《通信的數(shù)學理論》,次年,他又在同一雜志上發(fā)表了另一篇名著《噪聲下的通信》，這兩篇文章成了信息論的奠基著作。在這兩篇論文中，香農(nóng)解決了過去許多懸而未決的問題：闡明了通信的基本問題，給出了通信系統(tǒng)的模型，提出了信息量的數(shù)學表達式，并解決了信道容量、信源統(tǒng)計特性、信源編碼、信道編碼等一系列基本技術(shù)問題。兩篇論文成為了信息論的基礎(chǔ)性理論著作。那時，他才不過剛剛?cè)鲱^。

ClaudeShannon(1916-2001)

Shannon所給出的編碼定理的證明是非構(gòu)造性的，所給出的證明也不夠嚴格，但“他的數(shù)學直觀出奇地正確”(A.N.Kolmogrov，1963)

，他是“最近幾十年最偉大的工程師之一，同時是最偉大的數(shù)學家之一?！苯?jīng)過無數(shù)科技工作者50年來的努力奮斗，人們不僅在數(shù)學上已嚴格地證明了Shannon編碼定理，而且發(fā)現(xiàn)了各種具體可構(gòu)造的有效編碼理論和方法，可以實現(xiàn)Shannon指出的極限。文章曾遭受到數(shù)學家的抨擊，責難Shannon的一些結(jié)果未經(jīng)證明，在數(shù)學上不嚴格，靠不大住。Shannon對此評論說，“我不喜歡他的評論，他并未仔細看這篇文章。我確信我是正確的，我清楚地知道我所做的?！盋laudeShannon(1916-2001)

為了表彰Shannon的偉大功績，IEEEInformationSociety的25名成員于2000年10月6日在兒童時代的老家Gaylord鎮(zhèn)舉行了Shannon塑像的落成典禮。著名信息論和編碼學者Dr.RichardBlahut在Shannon塑像的落成典禮時的題詞說：“在我看來，兩三百年之后，當人們回過頭來看我們這個時代的時候，他們可能不會記得誰曾是美國的總統(tǒng)。他們也不會記得誰曾是影星或搖滾歌星。但是仍然會知曉Shannon的名字。學校里仍然會講授信息論。”ClaudeShannon(1916-2001)

他的同事D.Slepian寫到：“我們大家都帶著午飯來上班，飯后在黑板上玩玩數(shù)學游戲，但克勞德很少過來。他總是白天關(guān)起門來工作，晚上則騎著他的獨輪車來到貝爾實驗室。但是，如果你要找他，他會非常耐心地幫助你。他能立刻抓住問題的本質(zhì)。他真是一位天才，在我認識的人中，我只對他一人使用這個詞?！?/p>

1.

興趣驅(qū)動，淡漠名利

自述道：“我總是受我的興趣驅(qū)動，不大關(guān)心其經(jīng)濟價值或?qū)τ谑澜绲膬r值?！?.

探索股市，變得富有

思索股票價格起伏的規(guī)律性和信息論應(yīng)用于投資的可能性。在投資股票方面很成功，并變得富有。3.

心靈手巧，善制機器

制作計算器Throbac和玩六連棋的機器Hex。研究計算機下棋、老鼠走迷宮、雜技演員最多能控制多少個球，要拋多高才行？機器解魔方問題以及用計算機研究和進行股票投資等。4.

酷愛雜技，樂在其中

曾制作雜耍機，成為雜耍機器人的先驅(qū)。

Shannon的大師風范1924年奈奎斯特“影響電報速率的一些因素”1928年哈特萊“信息的傳輸”－信息速率與信道帶寬成正比－給出了信息度量方法1936年阿姆斯特朗－增大帶寬可以提高抗干擾能力1948年Shannon“通信的數(shù)學理論”－用概率論的方法研究通信系統(tǒng)，是現(xiàn)代信息論開創(chuàng)性的權(quán)威論文信息論的形成1948年香農(nóng)提出了無失真信源定理，給出了簡單的編碼方法(香農(nóng)編碼)1952年Fano碼，Huffman碼1968年埃利斯(P．Elias)提出了算術(shù)編碼的初步思路;1976Rissanen給出和發(fā)展了算術(shù)編碼1982年他和蘭登(G．G．Langdon)一起將算術(shù)編碼系統(tǒng)實現(xiàn)化1977,1978年Ziv和Lempel的LZ通用信源編算法無失真信源編碼發(fā)展1959年，Shannon提出率失真函數(shù)和率失真信源編碼定理1971年，伯格爾(T．Berger)給出更一般信源的率失真編碼定理率失真信源編碼理論是信源編碼的核心問題，是頻帶壓縮、數(shù)據(jù)壓縮的理論基礎(chǔ)目前，已提出多種限失真編碼方案如音頻、視頻:MPEG,JEPG等率失真信源編碼發(fā)展1950年漢明碼1960年卷積碼的概率譯碼，Viterbi譯碼1982年Ungerboeck編碼調(diào)制技術(shù)1993年Turbo編譯碼技術(shù)目前，已構(gòu)造出性能接近香農(nóng)限的好碼，如Turbo(PCC,SCC,TPC,LDPC)碼信道編碼發(fā)展香農(nóng)在1949年發(fā)表的“保密通信的信息理論”論文中，首先用信息論的觀點對信息保密問題作了全面的論述。1976年迪弗(Diffe)和海爾曼(Hellman)發(fā)表了“密碼學的新方向”一文，提出了公開密鑰密碼體制，保密通信問題才得到廣泛研究。人們把初等數(shù)論、矩陣、近世代數(shù)等引入保密問題的研究，已形成了獨樹一幟的分支——密碼學理論。密碼學發(fā)展1.4目前信息論的

主要研究成果信息論的主要研究成果

語音信號壓縮長途電話網(wǎng)標準1972年CCITTG.711標準中的64kbit/s，1995年CCITTG.723.1標準中的6.3kbit/s。移動通信中1989年GSM標準中語音編碼速率為13.2kbit/s1994年在為半碼速GSM研究的VSELP編碼算法中，碼速率為5.6kbit/s目前在實驗室中已實現(xiàn)600bit/s的低速率語音編碼，特別是按音素識別與合成原理構(gòu)造的聲碼器其速率可低于100bit/s，已接近信息論指出的極限。信息論的主要研究成果圖像信號壓縮1989年CCITT提出電視電話/會議電視的壓縮標準H.261,其壓縮比達到25:1到48:1左右1991年CCITT與ISO聯(lián)合提出的“多灰度靜止圖像壓縮編碼”標準JPEG,其壓縮比為24:1在運動圖像方面,運動圖像專家組繼成功定義了MPEG-1和MPEG-2之后,于1993年7月開始制訂全新的