信息論與編碼(傅祖云 講義)第一章

1、信息與編碼河南工業(yè)大學(xué)信息科學(xué)與技術(shù)學(xué)院 朱春華Tel:Address: 6408Email: 課程計(jì)劃1、計(jì)劃學(xué)時(shí)54，全部為講課學(xué)時(shí)2、每周結(jié)束進(jìn)行20分鐘的討論；3、總成績?yōu)樵嚲沓煽?0%+平時(shí)成績20%；4、平時(shí)成績滿分20分，少交作業(yè)一次扣2分，無故缺課一次扣2分5、計(jì)劃講授教材的一至九章注意事項(xiàng)1、實(shí)行嚴(yán)格的請(qǐng)假制度，請(qǐng)假必須有請(qǐng)假條且必須加蓋團(tuán)總支公章或有輔導(dǎo)員老師簽字2、保持課堂紀(jì)律，有問題可舉手示意3、歡迎大家及時(shí)提出反饋意見，以便更好的進(jìn)行互動(dòng)教學(xué)。辦公室：院辦公樓4層 目錄第1章 緒論第2章 離散信源及其信息測(cè)度第3章 離散信道及其信道容量第4章

2、 波形信源和波形信道第5章 無失真信源編碼定理第6章 有噪信道編碼定理第7章 保真度準(zhǔn)則下的信源編碼第8章 無失真的信源編碼第9章 信道的糾錯(cuò)編碼第10章 網(wǎng)絡(luò)信息論第11章 保密系統(tǒng)的基本信息理論第12章 信息論與其他學(xué)科的關(guān)系和應(yīng)用 教材： 信息論基礎(chǔ)理論與應(yīng)用(第2版)，傅祖蕓編， 北京 電子工業(yè)出版社，2007 （普通高等教育“十五”國家級(jí)規(guī)劃教材）課程概述當(dāng)今的時(shí)代是一個(gè)信息的時(shí)代，信息處理技術(shù)的不斷進(jìn)步極大的影響了我們的生活，使我們的生活質(zhì)量得到很大提高。本課程將介紹信息科學(xué)的基礎(chǔ)理論和基本方法，課程將基于一個(gè)通訊系統(tǒng)的抽象數(shù)學(xué)模型進(jìn)行展開，課程的數(shù)學(xué)基礎(chǔ)為概率論。整個(gè)課程可分為基

3、礎(chǔ)理論和編碼理論兩部分組成學(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í)中的重要性。偉大的科學(xué)家香農(nóng)Claude E.Shannon 偉大的科學(xué)家香農(nóng)“通信的基本問題就是在一點(diǎn)重新準(zhǔn)確地或近似地再現(xiàn)另一點(diǎn)所選擇的消息”。這是數(shù)學(xué)家克勞德.香農(nóng)（Claude E.Shannon）在他的驚世之著通信的數(shù)學(xué)理論中的一句名言。正是沿著這一思路他應(yīng)用數(shù)理統(tǒng)計(jì)的方法來研

4、究通信系統(tǒng)，從而創(chuàng)立了影響深遠(yuǎn)的信息論。偉大的科學(xué)家香農(nóng)香農(nóng)1916年4月30日出生于美國密歇根州的Petoskey，并且是愛迪生的遠(yuǎn)親戚。1936年畢業(yè)于密歇根大學(xué)并獲得數(shù)學(xué)和電子工程系理學(xué)學(xué)士學(xué)位，在那里他遇到了離散數(shù)學(xué)奠基人喬治布爾，上過他的課程。1940年獲得麻省理工學(xué)院（MIT）數(shù)學(xué)博士學(xué)位和電子工程碩士學(xué)位。1941年他加入貝年實(shí)驗(yàn)室數(shù)學(xué)部，工作到1972年。1956年他成為麻省理工學(xué)院（MIT）客座教授，并于1958年成為終生教授，1978年成為名譽(yù)教授。香農(nóng)博士于2001年2月24日去世，享年84歲。偉大的科學(xué)家香農(nóng)1948年發(fā)表“通信的數(shù)學(xué)理論”，標(biāo)志著信息論的誕生；1949

5、年發(fā)表“噪聲下的通信”，為信道編碼奠定理論基礎(chǔ)1949年發(fā)表“保密通信的信息理論”，首先用信息論的，觀點(diǎn)對(duì)信息保密問題作了全面的論述；1959年發(fā)表“保真度準(zhǔn)則下的離散信源編碼定理”-提出信息率失真理論，為信源壓縮編碼研究奠定理論基礎(chǔ)；1961年發(fā)表“雙路通信信道”，開拓了多用戶信息理論（網(wǎng)絡(luò)信息論）的研究；第一章 緒論 第一節(jié) 信息的概念第二節(jié) 信息論研究的對(duì)象、目的和內(nèi)容第三節(jié) 信息論的發(fā)展簡(jiǎn)史與現(xiàn)狀第一節(jié) 信息的概念 從哲學(xué)的角度上講，信息是構(gòu)成物質(zhì)世界的三大支柱之一，其他兩個(gè)是物質(zhì)和能量。 可以說我們生活在信息的海洋之中，沒有信息就沒有世界，當(dāng)然也就沒有我們?nèi)祟惿鐣?huì)。人類利用信息利用信

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

7、改造物質(zhì)，創(chuàng)造新物質(zhì)，提高能量利用效率，發(fā)現(xiàn)新能量形式。信息也是客觀存在的，它是人類認(rèn)識(shí)、改造客觀世界的主要?jiǎng)恿?，是人類認(rèn)識(shí)客觀世界的更高層次。 就狹義而言，在通信中對(duì)信息的表達(dá)分為三個(gè)層次：信號(hào)、消息、信息。 信號(hào)：是信息的物理表達(dá)層，是三個(gè)層次中最具體的層次。它是一個(gè)物理量，是一個(gè)載荷信息的實(shí)體，可測(cè)量、可描述、可顯示。如電信號(hào)、光信號(hào)等。消息：(或稱為符號(hào))是信息的數(shù)學(xué)表達(dá)層，它雖不是一個(gè)物理量，但是可以定量地加以描述，它是具體物理信號(hào)的進(jìn)一步數(shù)學(xué)抽象。信息：信息是指各個(gè)事物運(yùn)動(dòng)的狀態(tài)及狀態(tài)變化的方式。人們從來自對(duì)周圍世界的觀察得到的數(shù)據(jù)中獲得信息。信息是抽象的意識(shí)或知識(shí)，它是看不見、摸

8、不到的。人腦的思維活動(dòng)產(chǎn)生的一種想法，當(dāng)它仍儲(chǔ)存在腦子中的時(shí)候就是一種信息。信息是信號(hào)與消息的更高表達(dá)層次。三個(gè)層次中，信號(hào)最具體，信息最抽象。它們?nèi)咧g的關(guān)系是哲學(xué)上的內(nèi)涵與外延的關(guān)系。 信息的主要特征信息來源于物質(zhì)，又不是物質(zhì)本身；它從物質(zhì)的運(yùn)動(dòng)中產(chǎn)生出來，又可以脫離源物質(zhì)而相對(duì)獨(dú)立地存在；信息來源于精神世界，但又不局限于精神領(lǐng)域；信息與能量息息相關(guān)，但又與能量有本質(zhì)的區(qū)別；信息具有知識(shí)的本性，但又比知識(shí)的內(nèi)涵更廣泛；信息可以被主體獲取和利用。 香農(nóng)信息理論的基本思路 三個(gè)基本觀點(diǎn) 非決定論觀點(diǎn)形式化假說不確定性接收者在收到信息之前，對(duì)它的內(nèi)容是不知道的，所以信息是新知識(shí)、新內(nèi)容；信息是

9、能使認(rèn)識(shí)主體對(duì)某一事物的未知性或不確定性減少的有用知識(shí)；信息可以產(chǎn)生，也可以消失，同時(shí)信息可以被攜帶、貯存及處理； 信息是可以量度的，信息量有多少的差別。從不確定性的角度，信息的特征有(1) 通信過程是一種消除不確定地過程。不確定性的消除就獲得了信息。原先的不確定性消除的越多，獲得的信息就越多： (2) 在通信系統(tǒng)中，形式上傳遞的是消息，但實(shí)質(zhì)上傳遞的是信息。 接收者收到某一消息后所獲得的信息，可以用接收者在通信前后“不確定性”的消除量來度量。簡(jiǎn)而言之，接收者所得到的信息量，在數(shù)量上等于通信前后“不確定性”的消除量或減少量。這就是信息理論中度量信息的基本觀點(diǎn)。 (3) 不確定性”與概率的大小存

10、在著一定聯(lián)系，“不確定性”應(yīng)該是概率的某一函數(shù)。那么，“不確定性”的消除量（或減少量），也就是狹義的信息量，也一定可以由概率的某一函數(shù)表示。這樣，就完全解決了作為“通信的消息”來理解的狹義信息的度量問題。(4) 1928年，哈特萊(Hartley)首先提出了用對(duì)數(shù)度量信息的概念。一個(gè)消息所含有的信息量用它的可能值的個(gè)數(shù)的對(duì)數(shù)來表示。信息論基礎(chǔ)的重要性信息論是信息科學(xué)和技術(shù)的基本理論,信息科學(xué)大廈的地基; 沒有信息論的基礎(chǔ)，從事通信與信息領(lǐng)域的研究和創(chuàng)新是不可能的事情;總之,信息論是高層次信息技術(shù)人才必不可少的基礎(chǔ)知識(shí)。信源編碼器信道譯碼器信宿噪聲源信息論研究的對(duì)象、目的和內(nèi)容通信系統(tǒng)模型向通信

11、系統(tǒng)提供消息的人和機(jī)器。消息傳遞的對(duì)象，即接收消息的人或機(jī)器。傳遞消息的通道，又是傳送物理信號(hào)的設(shè)施。整個(gè)通信系統(tǒng)中各個(gè)干擾的集中反映，用以表示消息在信道中傳輸時(shí)遭受干擾的情況。產(chǎn)生密鑰k源。信源編碼器輸出信號(hào)x經(jīng)過k的加密運(yùn)算后，就把明文x變換為密文y。信息論研究的對(duì)象、目的和內(nèi)容信源：消息的來源編碼器：把消息變換成信號(hào)信道：傳遞信號(hào)的媒介譯碼器：把信道輸出的信號(hào)反變換信宿：信息的接受端噪聲：信道中的干擾信息論所要解決的問題可靠性有效性保密性認(rèn)證性信息論的理解狹義信息論（香農(nóng)信息論） 信息的測(cè)度、信道容量、信源和信道編碼理論一般信息論 噪聲、濾波與預(yù)測(cè)、估計(jì)、保密等廣義信息論 所有與信息相關(guān)

12、的鄰域信息論的發(fā)展歷史1924年，Nyquist提出信息傳輸理論；1928年，Hartley提出信息量關(guān)系；1932年，Morse發(fā)明電報(bào)編碼；1946年，柯切尼柯夫提出信號(hào)檢測(cè)理論；1948年，Shannon提出信息論，“通信中的數(shù)學(xué)理論 1.3 信息論的形成和發(fā)展 1948年，香農(nóng)在通信的數(shù)學(xué)理論的論文中，用概率測(cè)度和數(shù)理統(tǒng)計(jì)的方法系統(tǒng)地討論了通信的基本問題，得出了幾個(gè)重要而帶有普遍意義的結(jié)論。香農(nóng)理論的核心是：在通信系統(tǒng)中采用適當(dāng)?shù)木幋a后能夠?qū)崿F(xiàn)高效率和高可靠性的信息傳輸，并得出了信源編碼定理和信道編碼定理。 從數(shù)學(xué)觀點(diǎn)看，這些定理是最優(yōu)編碼的存在定理。但從工程觀點(diǎn)看，這些定理不是結(jié)構(gòu)性

13、的，不能從定理的結(jié)果直接得出實(shí)現(xiàn)最優(yōu)編碼的具體途徑。然而，它們給出了編碼的性能極限，在理論上闡明了通信系統(tǒng)中各種因素的相互關(guān)系，為人們尋找最佳通信系統(tǒng)提供了重要的理論依據(jù)。 對(duì)于確定概率分布的信源編碼 1948年，香農(nóng)在論文中提出并給出了簡(jiǎn)單的編碼方法(香農(nóng)編碼)，1952年,費(fèi)諾(Fano)提出了一種費(fèi)諾碼，同年霍(哈)夫曼(DAHuffman)構(gòu)造了一種霍夫曼編碼方法，并證明了它是最佳碼。 算術(shù)碼就是一種非塊碼，它是從整個(gè)序列的概率的匹配來進(jìn)行編碼的。其實(shí)此概念也是香農(nóng)首先提出的，后經(jīng)許多學(xué)者改進(jìn)，已進(jìn)入實(shí)用階段。1968年前后，埃利斯(PElias)發(fā)展了香農(nóng)費(fèi)諾碼，提出了算術(shù)編碼的初步

14、思路。而里斯桑內(nèi)(JRissanen)在1976年給出和發(fā)展了算術(shù)編碼，1982年他和蘭登(GGLangdon)一起將算術(shù)編碼系統(tǒng)化，并省去了乘法運(yùn)算，使其更為簡(jiǎn)化、易于實(shí)現(xiàn)。 在研究信源編碼的同時(shí)，另外一部分科學(xué)家從事信道編碼(糾錯(cuò)碼)的研究工作。這一工作已取得了很大的進(jìn)展，并已經(jīng)形成一門獨(dú)立的分支糾錯(cuò)碼理論。1950年漢明(RWHamming)發(fā)表的論文檢錯(cuò)碼與糾錯(cuò)碼是開拓編碼理論研究的第一篇論文。這篇論文主要考慮在大型計(jì)算機(jī)中如何糾正所出現(xiàn)的單個(gè)錯(cuò)誤。 密碼編碼學(xué)是信息安全技術(shù)的核心，密碼編碼學(xué)的主要任務(wù)是尋求產(chǎn)生安全性高的有效密碼算法和協(xié)議，以滿足對(duì)消息進(jìn)行加密或認(rèn)證的要求。密碼分析學(xué)

15、的主要任務(wù)是破譯密碼或偽造認(rèn)證信息，實(shí)現(xiàn)竊取機(jī)密信息或進(jìn)行詐騙破壞活動(dòng)。這兩個(gè)分支既相互對(duì)立又相互依存，正是由于這種對(duì)立統(tǒng)一關(guān)系，才推動(dòng)了密碼學(xué)自身的發(fā)展。香農(nóng)在1949年發(fā)表的保密通信的信息理論論文中，首先用信息論的觀點(diǎn)對(duì)信息保密問題作了全面的論述。 由于保密問題的特殊性，直至1976年迪弗(Diffe)和海爾曼(Hellman)發(fā)表了密碼學(xué)的新方向一文，提出了公開密鑰密碼體制后，保密通信問題才得到廣泛研究。尤其當(dāng)今，信息的安全和保密問題更加突出和重要。人們把線性代數(shù)、初等數(shù)論、矩陣等引入保密問題的研究，已形成了獨(dú)樹一幟的分支密碼學(xué)理論。1.4 信息論研究的內(nèi)容和目的 研究通信系統(tǒng)的目的就是要找到信息傳輸過程的共同規(guī)律，以提高信息傳輸?shù)目煽啃?、有效性?/p>