信息論與編碼1緒論課件

1、信息理論與編碼 武漢理工大學(xué)理學(xué)院胡國政1課程計(jì)劃1、總學(xué)時(shí)48，其中講課40學(xué)時(shí) ，實(shí)驗(yàn)8學(xué)時(shí)2、交作業(yè)和實(shí)驗(yàn)報(bào)告3、總成績由兩部分組成，平時(shí)成績占30， 考試成績占70 4、計(jì)劃講授教材的一至七章2教材和參考書：參考書：1信息論與編碼， 曹雪虹 張宗橙編，北京郵電大學(xué)出版社，20012信息論基礎(chǔ)理論與應(yīng)用， 傅祖蕓編著，電子工業(yè)出版社，20013信息理論與編碼，姜丹 錢玉美編著4信息論與編碼，吳伯修 歸紹升 祝宗泰 俞槐銓編著，1987教材：信息理論與編碼，呂鋒等編，人民郵電出版社 3課程概述 當(dāng)今的時(shí)代是一個(gè)信息的時(shí)代，信息處理技術(shù)的不斷進(jìn)步極大的影響了我們的生活，使我們的生活質(zhì)量得到很

2、大提高。本課程將介紹信息科學(xué)的基礎(chǔ)理論和基本方法，課程將基于一個(gè)通訊系統(tǒng)的抽象數(shù)學(xué)模型進(jìn)行展開，課程的數(shù)學(xué)基礎(chǔ)為概率論。整個(gè)課程可分為基礎(chǔ)理論和編碼理論兩部分組成4學(xué)習(xí)方法 本課程以概率論為基礎(chǔ)，數(shù)學(xué)推導(dǎo)較多，學(xué)習(xí)時(shí)主要把注意力集中到概念的理解上，不過分追求數(shù)學(xué)細(xì)節(jié)的推導(dǎo)。學(xué)習(xí)時(shí)一定要從始至終注意基本概念的理解，不斷加深概念的把握。學(xué)習(xí)時(shí)注意理解各個(gè)概念的“用處”，結(jié)合其他課程理解它的意義，而不要把它當(dāng)作數(shù)學(xué)課來學(xué)習(xí)，提倡獨(dú)立思考，注重思考在學(xué)習(xí)中的重要性。5第一章 緒論 1 信息的概念2 信息論研究的對(duì)象、目的和內(nèi)容3 信息論的發(fā)展簡史與現(xiàn)狀61 信息的概念 從哲學(xué)的角度上講，信息是構(gòu)成物質(zhì)

3、世界的三大支柱之一，其他兩個(gè)是物質(zhì)和能量。 可以說我們生活在信息的海洋之中，沒有信息就沒有世界，當(dāng)然也就沒有我們?nèi)祟惿鐣?huì)。人類利用信息利用信息的歷史非常悠久，而且隨著人類社會(huì)的發(fā)展而發(fā)展。到了現(xiàn)代，信息的利用已經(jīng)非常重要，以至于我們當(dāng)今生活的社會(huì)被稱作信息社會(huì)?？梢娦畔⒌闹匾?。 但是有史以來，人們都沒有對(duì)信息下過一個(gè)確切的定義。就像對(duì)于物質(zhì)和能量一樣。7 信息雖無確切定義，但是卻具有兩個(gè)明顯的特征：廣泛性與抽象性。 廣泛性客觀世界充滿著信息 人類離不開信息 知識(shí)、書本是有用信息的積累 抽象性三大要素是：物質(zhì)、能量與信息。三要素中物質(zhì)是基礎(chǔ)，是實(shí)體。能量是物質(zhì)運(yùn)動(dòng)的形式，E=mc2，物質(zhì)可轉(zhuǎn)換成

4、能量，而能量又是改造客觀世界的主要?jiǎng)恿Α?信息：它依附于物質(zhì)和能量，但又不同于物質(zhì)和能量。沒有信息就不能更好地利用物質(zhì)和能量，人類利用信息和知識(shí)改造物質(zhì)，創(chuàng)造新物質(zhì)，提高能量利用效率，發(fā)現(xiàn)新能量形式。信息也是客觀存在的，它是人類認(rèn)識(shí)、改造客觀世界的主要?jiǎng)恿?，是人類認(rèn)識(shí)客觀世界的更高層次。 就狹義而言，在通信中對(duì)信息的表達(dá)分為三個(gè)層次：信號(hào)、消息、信息。 9信號(hào)：是信息的物理表達(dá)層，是三個(gè)層次中最具體的層次。它是一個(gè)物理量，是一個(gè)載荷信息的實(shí)體，可測量、可描述、可顯示。如電信號(hào)、光信號(hào)等。消息：(或稱為符號(hào))是信息的數(shù)學(xué)表達(dá)層，它雖不是一個(gè)物理量，但是可以定量地加以描述，它是具體物理信號(hào)的進(jìn)一步

5、數(shù)學(xué)抽象。10信息：信息是指各個(gè)事物運(yùn)動(dòng)的狀態(tài)及狀態(tài)變化的方式。人們從來自對(duì)周圍世界的觀察得到的數(shù)據(jù)中獲得信息。信息是抽象的意識(shí)或知識(shí)，它是看不見、摸不到的。人腦的思維活動(dòng)產(chǎn)生的一種想法，當(dāng)它仍儲(chǔ)存在腦子中的時(shí)候就是一種信息。信息是信號(hào)與消息的更高表達(dá)層次。三個(gè)層次中，信號(hào)最具體，信息最抽象。它們?nèi)咧g的關(guān)系是哲學(xué)上的內(nèi)涵與外延的關(guān)系。 11信息的主要特征信息來源于物質(zhì)，又不是物質(zhì)本身；它從物質(zhì)的運(yùn)動(dòng)中產(chǎn)生出來，又可以脫離源物質(zhì)而相對(duì)獨(dú)立地存在；信息來源于精神世界，但又不局限于精神領(lǐng)域；信息與能量息息相關(guān)，但又與能量有本質(zhì)的區(qū)別；信息具有知識(shí)的本性，但又比知識(shí)的內(nèi)涵更廣泛；信息可以被主體獲取

6、和利用。12信息論基礎(chǔ)的重要性信息論是信息科學(xué)和技術(shù)的基本理論,信息科學(xué)大廈的地基; 沒有信息論的基礎(chǔ)，從事通信與信息領(lǐng)域的研究和創(chuàng)新是不可能的事情;總之,信息論是高層次信息技術(shù)人才必不可少的基礎(chǔ)知識(shí)。132信息論研究對(duì)象、目的和內(nèi)容通信系統(tǒng)模型信源信道信宿編碼器譯碼器噪聲源14信源信源編碼器信道編碼器調(diào)制器信道干擾源解調(diào)器信道譯碼器信源譯碼器信宿等效離散信道等效離散信源等效信宿信道編碼器信道譯碼器通信系統(tǒng)模型進(jìn)一步細(xì)分15信息論從誕生到今天，已有五十多年歷史，現(xiàn)已成為一門獨(dú)立的理論科學(xué)，回顧它的發(fā)展歷史，我們可以知道理論是如何從實(shí)踐中經(jīng)過抽象、概括、提高而逐步形成的。 信息論是在長期的通信工

7、程實(shí)踐和理論研究的基礎(chǔ)上發(fā)展起來的。 通信系統(tǒng)是人類社會(huì)的神經(jīng)系統(tǒng)，即使在原始社會(huì)也存在著最簡單的通信工具和通信系統(tǒng)，這方面的社會(huì)實(shí)踐是悠久漫長的。16 電的通信系統(tǒng)(電信系統(tǒng))已有100多年的歷史了。在一百余年的發(fā)展過程中，一個(gè)很有意義的歷史事實(shí)是：當(dāng)物理學(xué)中的電磁理論以及后來的電子學(xué)理論一旦有某些進(jìn)展，很快就會(huì)促進(jìn)電信系統(tǒng)的創(chuàng)造發(fā)明或改進(jìn)。這是因?yàn)橥ㄐ畔到y(tǒng)對(duì)人類社會(huì)的發(fā)展，其關(guān)系實(shí)在是太密切了。日常生活、工農(nóng)業(yè)生產(chǎn)、科學(xué)研究以及戰(zhàn)爭等等，一切都離不開消息傳遞和信息流動(dòng)。 17例如，當(dāng)法拉第(MFaraday)于1820年-1830年期間發(fā)現(xiàn)電磁感應(yīng)的基本規(guī)律后，不久莫爾斯(FBMorse)

8、就建立起電報(bào)系統(tǒng)(18321835)。1876年，貝爾(AGBELL)又發(fā)明了電話系統(tǒng)。1864年麥克斯韋(Maxell)預(yù)言了電磁波的存在，1888年赫茲(HHertz)用實(shí)驗(yàn)證明了這一預(yù)言。接著1895年英國的馬可尼(G. Marconi)和俄國的波波夫(ACooB)就發(fā)明了無線電通信。18本世紀(jì)初 (1907年) ，根據(jù)電子運(yùn)動(dòng)的規(guī)律，福雷斯特(1，F(xiàn)orest)發(fā)明了能把電磁波進(jìn)行放大的電子管。之后很快出現(xiàn)了遠(yuǎn)距離無線電通信系統(tǒng)。大功率超高頻電子管發(fā)明以后，電視系統(tǒng)就建立起來了(19251927)。電子在電磁場運(yùn)動(dòng)過程中能量相互交換的規(guī)律被人們認(rèn)識(shí)后，就出現(xiàn)了微波電子管(最初是磁控管，

9、后來是速調(diào)管、行波管)，接著，在三十年代末和四十年代初的二次世界大戰(zhàn)初期，微波通信系統(tǒng)、微波雷達(dá)系統(tǒng)等就迅速發(fā)展起來。五十年代后期發(fā)明了量子放大器，六十年代初發(fā)明的激光技術(shù)，使人類進(jìn)入了光纖通信的時(shí)代。19隨著工程技術(shù)的發(fā)展，有關(guān)理論問題的研究也逐步深入。1832年莫爾斯電報(bào)系統(tǒng)中高效率編碼方法對(duì)后來香農(nóng)的編碼理論是有啟發(fā)的。1885年凱爾文(L. Kelvin)曾經(jīng)研究過一條電纜的極限傳信率問題。1922年卡遜(JRCarson)對(duì)調(diào)幅信號(hào)的頻譜結(jié)構(gòu)進(jìn)行了研究，并建立了信號(hào)頻譜概念。1924年奈奎斯特(HNyquist)指出，如果以一個(gè)確定的速度來傳輸電報(bào)信號(hào)，就需要一定的帶寬。他把信息率與

10、帶寬聯(lián)系起來了。1928年哈特萊(RVHartley)發(fā)展了奈奎斯特的工作，并提出把消息考慮為代碼或單語的序列。他的工作對(duì)后來香農(nóng)的思想是有影響的。 20 1936年阿姆斯特朗(EHArmstrong)認(rèn)識(shí)到在傳輸過程中增加帶寬的辦法對(duì)抑制噪聲干擾肯定有好處。根據(jù)這一思想他提出了寬偏移的頻率調(diào)制方法，該方法是有劃時(shí)代意義的。 信息論作為一門嚴(yán)密的科學(xué)分支，主要?dú)w功于貝爾實(shí)驗(yàn)室的香農(nóng)。他在1948年發(fā)表的論文通信的數(shù)學(xué)理論奠定了信息論的基礎(chǔ)?？刂普摰膭?chuàng)始人維納也對(duì)信息論有不可忽視的貢獻(xiàn)。香農(nóng)和維納的基本思想都是把通信作為統(tǒng)計(jì)過程來處理。他們采用的術(shù)語、方法也主要依靠統(tǒng)計(jì)理論。 21研究通信系統(tǒng)的

11、目的就是要找到信息傳輸過程的共同規(guī)律，以提高信息傳輸?shù)目煽啃?、有效性、保密性和認(rèn)證性，以達(dá)到信息傳輸系統(tǒng)最優(yōu)化。所謂可靠性高，就是要使信源發(fā)出的消息經(jīng)過信道傳輸以后，盡可能準(zhǔn)確地、不失真地再現(xiàn)在接收端。而所謂有效性高，就是經(jīng)濟(jì)效果好，即用盡可能短的時(shí)間和盡可能少的設(shè)備來傳送一定數(shù)量的信息。 22 以后會(huì)看到，提高可靠性和提高有效性常常會(huì)發(fā)生矛盾，這就需要統(tǒng)籌兼顧。所謂保密性就是隱蔽和保護(hù)通信系統(tǒng)中傳送的消息，使它只能被授權(quán)接收者獲取，而不能被未授權(quán)者接收和理解。 所謂認(rèn)證性是指接收者能正確判斷所接收的消息的正確性和完整性，而不是偽造的和被篡改的。23信息論研究的對(duì)象、目的和內(nèi)容信源：消息的來源

12、編碼器：把消息變換成信號(hào)信道：傳遞信號(hào)的媒介譯碼器：把信道輸出的信號(hào)反變換信宿：信息的接受端噪聲：信道中的干擾24信息論所要解決的問題可靠性有效性保密性認(rèn)證性25信息論的理解狹義信息論（香農(nóng)信息論） 信息的測度、信道容量、信源和信道編碼理論一般信息論 噪聲、濾波與預(yù)測、估計(jì)、保密等廣義信息論 所有與信息相關(guān)的鄰域26狹義信息論體系結(jié)構(gòu)Shannon信息論壓縮理論有失真編碼無失真編碼等長編碼定理Shannon1948McMillan1953變長編碼定理Shannon1948McMillan1956Huffman碼(1952)、Fano碼算術(shù)碼(1976,1982)LZ碼(1977,1978)率失

13、真理論ShannonGallagerBerger壓縮編碼JPEGMPEG傳輸理論信道編碼定理網(wǎng)絡(luò)信息理論糾錯(cuò)碼編碼調(diào)制理論網(wǎng)絡(luò)最佳碼27信息論的發(fā)展歷史1924年，Nyquist提出信息傳輸理論；1928年，Hartly提出信息量關(guān)系；1946年，柯切尼柯夫提出信號(hào)檢測理論；1948年，Shannon提出信息論，“通信中的數(shù)學(xué)理論 28電磁理論和電子學(xué)理論對(duì)通信理論技術(shù)發(fā)展起重要的促進(jìn)作用18201830年，法拉第發(fā)現(xiàn)電磁感應(yīng)莫爾斯18321835建立電報(bào)系統(tǒng)。1876年Bell發(fā)明電話1864麥克斯韋預(yù)言電磁波存在，1888年赫茲驗(yàn)證該理論1895年馬可尼發(fā)明了無線電通信微波電子管導(dǎo)致微波通

14、信系統(tǒng)，微波雷達(dá)系統(tǒng)激光技術(shù)使通信進(jìn)入光通信時(shí)代291948年shannon信息論奠基1952年Fano證明了Fano不等式，給出了shannon信道編碼逆定理的證明1957，Wolfowitz，1961 Fano，1968Gallager給出信道編碼定理的簡介證明并描述了碼率，碼長和錯(cuò)誤概率的關(guān)系，1972年Arimoto和Blahut發(fā)明了信道容量的迭代算法1956McMillan證明了Kraft不等式。1952年Fano碼，Huffman碼。1976 Rissanen算術(shù)編碼，1977，78 Ziv和Lempel的LZ算法301950年漢明碼，1960年卷積碼的概率譯碼，Viterbi譯

15、碼，1982年Ungerboeck編碼調(diào)制技術(shù)，1993年Turbo編譯碼技術(shù)1959年，Shannon提出率失真函數(shù)和率失真信源編碼定理1961年，Shannon的“雙路通信信道”開拓了網(wǎng)絡(luò)信息論的研究，目前是非常活躍的研究領(lǐng)域。311832年莫爾斯電碼對(duì)shannon編碼理論的啟發(fā)1885年凱爾文研究了一條電纜的極限傳信速率1922年卡遜對(duì)調(diào)幅信號(hào)的頻譜結(jié)構(gòu)進(jìn)行研究1924年奈奎斯特證明了信號(hào)傳輸速率和帶寬成正比1928年Hartley提出信息量定義為可能消息量的對(duì)數(shù)1939年Dudley發(fā)明聲碼器1940維納將隨機(jī)過程和數(shù)理統(tǒng)計(jì)引入通信與控制系統(tǒng)323 信息論的形成和發(fā)展 1948年，香

16、農(nóng)在通信的數(shù)學(xué)理論的論文中，用概率測度和數(shù)理統(tǒng)計(jì)的方法系統(tǒng)地討論了通信的基本問題，得出了幾個(gè)重要而帶有普遍意義的結(jié)論。香農(nóng)理論的核心是：在通信系統(tǒng)中采用適當(dāng)?shù)木幋a后能夠?qū)崿F(xiàn)高效率和高可靠性的信息傳輸，并得出了信源編碼定理和信道編碼定理。 33“通信的基本問題就是在一點(diǎn)重新準(zhǔn)確地或近似地再現(xiàn)另一點(diǎn)所選擇的消息”。34從數(shù)學(xué)觀點(diǎn)看，這些定理是最優(yōu)編碼的存在定理。但從工程觀點(diǎn)看，這些定理不是結(jié)構(gòu)性的，不能從定理的結(jié)果直接得出實(shí)現(xiàn)最優(yōu)編碼的具體途徑。然而，它們給出了編碼的性能極限，在理論上闡明了通信系統(tǒng)中各種因素的相互關(guān)系，為人們尋找最佳通信系統(tǒng)提供了重要的理論依據(jù)。 35對(duì)于確定概率分布的信源編碼

17、1948年，香農(nóng)在論文中提出并給出了簡單的編碼方法(香農(nóng)編碼)，1952年,費(fèi)諾(Fano)提出了一種費(fèi)諾碼，同年霍夫曼(DAHuffman)構(gòu)造了一種霍夫曼編碼方法，并證明了它是最佳碼。 36算術(shù)碼就是一種非塊碼，它是從整個(gè)序列的概率的匹配來進(jìn)行編碼的。其實(shí)此概念也是香農(nóng)首先提出的，后經(jīng)許多學(xué)者改進(jìn)，已進(jìn)入實(shí)用階段。1968年前后，埃利斯(PElias)發(fā)展了香農(nóng)費(fèi)諾碼，提出了算術(shù)編碼的初步思路。而里斯桑內(nèi)(JRissanen)在1976年給出和發(fā)展了算術(shù)編碼，1982年他和蘭登(GGLangdon)一起將算術(shù)編碼系統(tǒng)化，并省去了乘法運(yùn)算，使其更為簡化、易于實(shí)現(xiàn)。 37在研究信源編碼的同時(shí)，另外一部分科學(xué)家從事信道編碼(糾錯(cuò)碼)的研究工作。這一工作已取得了很大的進(jìn)展，并已經(jīng)形成一門獨(dú)立的分支糾錯(cuò)碼理論。1950年漢明(RWHamming)發(fā)表的論文檢錯(cuò)碼與糾錯(cuò)碼是開拓編碼理論研究的第一篇論文。這篇論文主要考慮在大型計(jì)算機(jī)中如何糾正所出現(xiàn)的單個(gè)錯(cuò)誤。 38密碼編碼學(xué)是信息安全技術(shù)的核心，密碼編碼學(xué)的主要任務(wù)是尋求產(chǎn)生安全性高的有效密碼算法和協(xié)議，以滿足對(duì)消息進(jìn)行加密或認(rèn)證的要求。密碼分析