第1講-信息論的對(duì)象與方法

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

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

信息論與編碼理論，

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

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

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

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

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

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

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

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

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

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

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

ClaudeShannon(1916-2001)

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

ClaudeShannon(1916-2001)

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

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

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

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

1.

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

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

探索股市，變得富有

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

心靈手巧，善制機(jī)器

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

酷愛雜技，樂在其中

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

Shannon的大師風(fēng)范1924年奈奎斯特“影響電報(bào)速率的一些因素”1928年哈特萊“信息的傳輸”－信息速率與信道帶寬成正比－給出了信息度量方法1936年阿姆斯特朗－增大帶寬可以提高抗干擾能力1948年Shannon“通信的數(shù)學(xué)理論”－用概率論的方法研究通信系統(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)實(shí)現(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ā)表的“保密通信的信息理論”論文中，首先用信息論的觀點(diǎn)對(duì)信息保密問題作了全面的論述。1976年迪弗(Diffe)和海爾曼(Hellman)發(fā)表了“密碼學(xué)的新方向”一文，提出了公開密鑰密碼體制，保密通信問題才得到廣泛研究。人們把初等數(shù)論、矩陣、近世代數(shù)等引入保密問題的研究，已形成了獨(dú)樹一幟的分支——密碼學(xué)理論。密碼學(xué)發(fā)展1.4目前信息論的

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

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