信息論與編碼_第一章

1、 主講老師：姚志強(qiáng) (Information theory and coding)學(xué)習(xí)的意義學(xué)習(xí)的意義 信息論與編碼理論是信息科學(xué)的基礎(chǔ)理論，對信息進(jìn)行定量的分析，對信息處理給出理論的指導(dǎo)，是20世紀(jì)后半葉數(shù)字化革命的主要理論和技術(shù)支柱 信息論與編碼的許多思想和方法已廣泛滲透到許多領(lǐng)域：計(jì)算機(jī)，通信技術(shù)，統(tǒng)計(jì)學(xué), 物理學(xué)，生物學(xué)，系統(tǒng)科學(xué), 經(jīng)濟(jì)學(xué), 社會(huì)學(xué), 組成客觀世界的三大基本要素：物質(zhì)、能組成客觀世界的三大基本要素：物質(zhì)、能量和信息，材料科學(xué)、能源科學(xué)、和信息量和信息，材料科學(xué)、能源科學(xué)、和信息科學(xué)一起被稱為當(dāng)代文明的科學(xué)一起被稱為當(dāng)代文明的“三大支柱三大支柱”。 Without ma

2、terials, there is nothing. 沒有沒有物質(zhì)的世界是虛無的世界；物質(zhì)的世界是虛無的世界； Without energy, nothing happens.沒有能源的世界是死寂的世界；沒有能源的世界是死寂的世界； Without information, nothing makes sense沒有信息的世界是混亂的世界。沒有信息的世界是混亂的世界。幾十年來許多優(yōu)秀的學(xué)者，工程師共同努力推動(dòng)了幾十年來許多優(yōu)秀的學(xué)者，工程師共同努力推動(dòng)了該理論和實(shí)踐的發(fā)展該理論和實(shí)踐的發(fā)展美國科學(xué)家Claude Elwood Shannon ，1916年4月30日2001年2月26日，以60多

3、年前Shannon的不朽論文通信的數(shù)學(xué)理論通信的數(shù)學(xué)理論為里程碑信息論的奠基人：信息論的奠基人： 信息論的學(xué)習(xí)有助于對其他學(xué)科的研究,同時(shí)其他相關(guān)學(xué)科的研究也會(huì)促進(jìn)信息論的發(fā)展. 這些理論是屬于21世紀(jì)的工程科學(xué)理論，將對21世紀(jì)新科技產(chǎn)生巨大的作用 國外的一流學(xué)校在20世紀(jì)50年代末就開始設(shè)立信息論與編碼課程 目前國內(nèi)各高校的信息類專業(yè)研究生都已把信息論與編碼作為一門重要的專業(yè)基礎(chǔ)理論課信息論對于不同學(xué)科的重要性 通訊工程師說：當(dāng)受信者對一個(gè)事件出現(xiàn)的先驗(yàn)概率估計(jì)越小時(shí)，他獲得的信息量就越大； 計(jì)算機(jī)科學(xué)家則說：微處理器時(shí)鐘頻率的大小，決定著它處理信息的速度高低； 生物學(xué)家則高呼：脫氧核糖核

4、酸上的信息是控制子代和親代相象的唯一源泉。 不同學(xué)科的信息有著不同的內(nèi)涵，有著不同的研究目的主要參考文獻(xiàn) 信息理論與編碼信息理論與編碼 姜丹、錢玉美編著姜丹、錢玉美編著 中國科技大學(xué)出版中國科技大學(xué)出版 社（第一版，第二版，第三版）；社（第一版，第二版，第三版）； 信息論信息論基礎(chǔ)理論與應(yīng)用基礎(chǔ)理論與應(yīng)用 傅祖蕓編著傅祖蕓編著 電子工業(yè)出版社電子工業(yè)出版社 2001年版；年版； 信息論與編碼方法西南交通大學(xué)勒蕃教授著； 信息論與編碼陳運(yùn)、周亮、陳新編著 電子工業(yè)出版社； 信息論與編碼仇佩亮編著 高等教育出版社；需具備的相關(guān)數(shù)學(xué)知識：需具備的相關(guān)數(shù)學(xué)知識：概率與統(tǒng)計(jì)理論矩陣論需了解的相關(guān)專業(yè)方面

5、知識：需了解的相關(guān)專業(yè)方面知識：通信原理高等數(shù)學(xué)最優(yōu)化理論本課程的主要教學(xué)目標(biāo)：本課程的主要教學(xué)目標(biāo)：信息論基本原理與應(yīng)用第一章、緒論第一章、緒論第一節(jié)、信息論起源和發(fā)展第一節(jié)、信息論起源和發(fā)展第二節(jié)、信息的概念第二節(jié)、信息的概念第三節(jié)、信息論的研究內(nèi)容和核心第三節(jié)、信息論的研究內(nèi)容和核心第一節(jié)、信息論的起源及發(fā)展第一節(jié)、信息論的起源及發(fā)展1、起源、起源 1924年，奈奎斯特（年，奈奎斯特（Nyquist）：信號帶寬和信息）：信號帶寬和信息速率間的關(guān)系。速率間的關(guān)系。 1928年，哈特利（年，哈特利（Hartley）：通訊系統(tǒng)傳遞信息）：通訊系統(tǒng)傳遞信息的能力，并給出了信息度量的方法。的能力，

6、并給出了信息度量的方法。 1948年，年，香農(nóng)香農(nóng)（Shannon）：通訊中的數(shù)學(xué)理論。）：通訊中的數(shù)學(xué)理論。并由此創(chuàng)立了信息論學(xué)科，因此稱他為信息論的并由此創(chuàng)立了信息論學(xué)科，因此稱他為信息論的創(chuàng)始人。創(chuàng)始人。 1956年，布里淵（ Brillouin ）：科學(xué)與信息論，信息就是負(fù)熵。信息定義的概念 1928年，哈特利在 Bell System Technical Journal 上發(fā)表了一篇題為“信息傳輸”的論文。在這篇論文中，他把信息理解為選擇通信符號的方式，并用選擇的自由度來計(jì)量這種信息的大小。他認(rèn)為，發(fā)信者所發(fā)出的信息，就是他在通信符號表中選擇符號的具體方式。哈特利信息定義的局限性 哈

7、特利的這種理解能夠在一定程度上解釋通信工程中的一些信息問題，但是它也存在著一些嚴(yán)重時(shí)局限性：p所定義的信息不涉及內(nèi)容和價(jià)值，只考慮選擇的方式，p沒有考慮到信源的統(tǒng)計(jì)性質(zhì)；p把信息理解為選擇的方式，就必須有一個(gè)選擇的主體作為限制條件。這些缺點(diǎn)使它的運(yùn)用范圍受到很大的限制。 美國數(shù)學(xué)家香農(nóng)在美國數(shù)學(xué)家香農(nóng)在Bell System Technical J o u r n a l 發(fā) 表 了 一 篇 題 為發(fā) 表 了 一 篇 題 為 “ A Mathematical Theory of Communication”的長文（的長文（1948）。）。 這篇論文以概率論為工具，深刻闡述了通信這篇論文以概率論

8、為工具，深刻闡述了通信工程的一系列基本理論問題，給出了計(jì)算信工程的一系列基本理論問題，給出了計(jì)算信源信息量和信道容量的方法和一般公式，得源信息量和信道容量的方法和一般公式，得到了一組表征信息傳遞重要關(guān)系的編碼定理。到了一組表征信息傳遞重要關(guān)系的編碼定理。l 香農(nóng)在進(jìn)行信息的香農(nóng)在進(jìn)行信息的定量計(jì)算定量計(jì)算的時(shí)候明確地把的時(shí)候明確地把信息量信息量定義為隨機(jī)不定性程度的減少。這就表明了他對信定義為隨機(jī)不定性程度的減少。這就表明了他對信息的理解：息的理解：信息是用來減少隨機(jī)不確定性的東西信息是用來減少隨機(jī)不確定性的東西。隨機(jī)不確定性是指由于隨機(jī)因素所造成的不能肯定的情形，在數(shù)值上可以用概率熵來計(jì)量。

9、香 農(nóng) 簡 介 1916-2001，信息論及數(shù)字通信時(shí)代的奠基人。美國科，信息論及數(shù)字通信時(shí)代的奠基人。美國科學(xué)院院士、工程院院士，英國皇家學(xué)會(huì)會(huì)員，美國哲學(xué)學(xué)會(huì)學(xué)院院士、工程院院士，英國皇家學(xué)會(huì)會(huì)員，美國哲學(xué)學(xué)會(huì)會(huì)員。會(huì)員。 1936年獲得密西根大學(xué)數(shù)學(xué)與電氣工程學(xué)士學(xué)位。年獲得密西根大學(xué)數(shù)學(xué)與電氣工程學(xué)士學(xué)位。 1938年獲年獲MIT（麻省理工學(xué)院）電氣工程碩士學(xué)位，（麻省理工學(xué)院）電氣工程碩士學(xué)位，繼電器與開關(guān)電路的符號分析繼電器與開關(guān)電路的符號分析。 1940年獲年獲MIT數(shù)學(xué)博士學(xué)位，數(shù)學(xué)博士學(xué)位，理論遺傳學(xué)的代數(shù)論理論遺傳學(xué)的代數(shù)論。 二戰(zhàn)期間：著名的密碼破譯者，在二戰(zhàn)期間：著名的

10、密碼破譯者，在BELL實(shí)驗(yàn)室，主要實(shí)驗(yàn)室，主要跟蹤德國的飛機(jī)和火箭。跟蹤德國的飛機(jī)和火箭。 1948年發(fā)表年發(fā)表通信中的數(shù)學(xué)理論通信中的數(shù)學(xué)理論。 1949年，另一著名論文年，另一著名論文噪聲下的通信噪聲下的通信 根據(jù)這一思想，法裔美國科學(xué)家布里淵（Brillouin，1956）在他的名著科學(xué)與信息論中直接了當(dāng)?shù)刂赋觯盒畔⒕褪秦?fù)熵。并且他還創(chuàng)造了Negentropy這一詞來表示負(fù)熵的概念。 美國數(shù)學(xué)家、控制論的主要奠基人維納在1950年出版的控制論與社會(huì)一書中對信息的理解是： “人通過感覺器官感知周圍世界”， “我們支配環(huán)境的命令就是給環(huán)境的一種信息”，因此，“信息就是我們在適應(yīng)外部世界，并把

11、這種適應(yīng)反作用于外部世界的過程中，同外部世界進(jìn)行交換的內(nèi)容的名稱”。 “接收信息和使用信息的過程，就是我們適應(yīng)外界環(huán)境的偶然性的過程，也是我們在這個(gè)環(huán)境中有效地生活的過程”。維納信息定義的缺陷維納信息定義的缺陷 維納把人與外部環(huán)境交換信息的過程當(dāng)作是一種廣義的通信的過程。這當(dāng)然是沒有問題的；因?yàn)椋瑥V義的通信本來就可以泛指人與人、機(jī)器與機(jī)器、機(jī)器與自然物、人與自然物之間的信息傳遞與交換。 不過，這里所理解的信息仍然不夠確切。這是因?yàn)椋喝伺c環(huán)境之間互相交換的內(nèi)容中不僅有信息，也有物質(zhì)與能量，把它們統(tǒng)統(tǒng)起一個(gè)名字信息，豈不是把信息與物質(zhì)及能量混為一談。信息定義的總結(jié) 信息是人與外界交互的內(nèi)容，是有序

12、程度的度量和負(fù)熵，是用以減少不定性的東西，這些都是Wiener、Brillouin、Shannon等人的理解。這些認(rèn)識比僅僅把信息看作消息或通信內(nèi)容要更深刻。 在數(shù)學(xué)上很容易證明，Hartley的信息概念僅是Shannon信息概念的一種特殊情形。 總起來說，在現(xiàn)有的各種理解中，Shannon的定義比較深刻，而且這種定義還導(dǎo)出了相應(yīng)的算法。香農(nóng)信息定義的概念 信息是事物運(yùn)動(dòng)狀態(tài)或存在形式的不確定性的描述，所謂不確定性就是千變?nèi)f化、不規(guī)則、隨機(jī)性，用概率模型來描述并對其進(jìn)行定量的計(jì)算。 通信系統(tǒng)中接受消息的過程就是消除不確定性的過程。不確定的消除就獲得了信息。信息量與不確定性消除的程度有關(guān)。香農(nóng)信

13、息定義的缺陷（1） Shannon通信的數(shù)學(xué)理論明確地指出： 通信的任務(wù)是在收端復(fù)制發(fā)端所發(fā)出的波形，至于它的內(nèi)容含義，因與通信工程無關(guān)，所以可以舍去。 可見Shannon理論中的不定性純粹是波形形式上的不定性，與此相應(yīng)的信息概念也是純粹的形式化的概念（稱為語法信息）。 這樣的信息概念排除了信息的含義因素，（即語義信息）和價(jià)值因素（即語用信息），不考慮收信者的主觀特性。因此，其適用范圍受到嚴(yán)重的限制。香農(nóng)信息定義的缺陷（2） 只考慮了隨機(jī)型的不定性，不能解釋與其他型式的不定性（如模糊不定性）有關(guān)的信息問題。 這種信息定義只從功能角度上來表述，還是沒有從根本上回答“信息是什么”的問題。信源編碼與

14、數(shù)據(jù)壓縮信源編碼與數(shù)據(jù)壓縮 信道編碼與差錯(cuò)控制技術(shù)信道編碼與差錯(cuò)控制技術(shù)多用戶信息論與網(wǎng)絡(luò)通信多用戶信息論與網(wǎng)絡(luò)通信 多媒體與信息論多媒體與信息論 信息論與密碼學(xué)和數(shù)據(jù)安全信息論與密碼學(xué)和數(shù)據(jù)安全信息論與概率統(tǒng)計(jì)信息論與概率統(tǒng)計(jì)信息論與經(jīng)濟(jì)學(xué)信息論與經(jīng)濟(jì)學(xué)信息論與計(jì)算復(fù)雜性信息論與計(jì)算復(fù)雜性信息論與系統(tǒng)、控制、信號檢測和處理信息論與系統(tǒng)、控制、信號檢測和處理量子信息論量子信息論Shannon的其它重要貢獻(xiàn)的其它重要貢獻(xiàn)2、發(fā)展、發(fā)展信息論主要幾個(gè)方面的進(jìn)展信息論主要幾個(gè)方面的進(jìn)展2、發(fā)展、發(fā)展 、信道編碼定理，、信道編碼定理，1948，C. E. Shannon。 、發(fā)現(xiàn)、發(fā)現(xiàn)Hamming碼

15、，碼，1950，H. W. Hamming。 、發(fā)現(xiàn)、發(fā)現(xiàn)Golay碼，碼，1954，M. J. E. Golay。 、發(fā)現(xiàn)、發(fā)現(xiàn)Reed-Muller碼，碼，1954，I. S. Reed and D. E.Muller。 、發(fā)現(xiàn)卷積碼，、發(fā)現(xiàn)卷積碼，1955, P. Elias。 、線性碼、群碼的系統(tǒng)描述，、線性碼、群碼的系統(tǒng)描述，1956，D. Slepian。 、發(fā)現(xiàn)循環(huán)碼，、發(fā)現(xiàn)循環(huán)碼，1957, E. Prange。 、卷積碼的序列譯碼算法，、卷積碼的序列譯碼算法，1957, J. M. Wozencraft; 1964, R. M. Fano。 、發(fā)現(xiàn)、發(fā)現(xiàn)BCH碼，碼，1960

16、, R. C. Bose and D. K. Ray-Chaudhuri, 1959, A. Hocquenghem。、 發(fā)現(xiàn)發(fā)現(xiàn)Reed-Solomon碼，碼，1960, I. S. Reed and G. Solomon。 、糾錯(cuò)碼作為信息論的分支出現(xiàn)，第一本書、糾錯(cuò)碼作為信息論的分支出現(xiàn)，第一本書Error-Correcting Codes, W. W. Peterson, MIT Press, 1961。編碼技術(shù)的發(fā)展編碼技術(shù)的發(fā)展編碼技術(shù)的進(jìn)展情況編碼技術(shù)的進(jìn)展情況2、發(fā)展、發(fā)展(12) Berlekamp- Massey譯碼算法譯碼算法分組碼實(shí)用代數(shù)譯碼算法，分組碼實(shí)用代數(shù)譯碼算法

17、，1966, E. R. Berlecamp, 1969, J. L. Massey。(13) 發(fā)現(xiàn)級連碼，發(fā)現(xiàn)級連碼，1966, G. D. Forney。(14) 卷積碼的卷積碼的Viterbi 譯碼算法，譯碼算法，1967, A. J. Viterbi。(15) 發(fā)現(xiàn)發(fā)現(xiàn)Goppa碼和代數(shù)幾何碼，碼和代數(shù)幾何碼，1970, V. C. Goppa。1982, M. A. Tsfasman, S. G. Vladut, and Th. Zink(16) 發(fā)現(xiàn)歐氏幾何碼，發(fā)現(xiàn)歐氏幾何碼，TCM, 1976, G. Ungerboeck；BCM, 1977, H. Imai and S. Hi

18、rakawa。(17) 發(fā)現(xiàn)格碼，發(fā)現(xiàn)格碼，1989，R.deBuda。格。格(lattice)碼可趨近頻帶受限高斯信道碼可趨近頻帶受限高斯信道容量。容量。Loeligerz在在1992年已證明，這是年已證明，這是Zp上的歐氏空間群碼。上的歐氏空間群碼。(18)發(fā)現(xiàn)發(fā)現(xiàn)Turbo碼，迭代自適應(yīng)譯碼算法，碼，迭代自適應(yīng)譯碼算法，1993, C. Berrou and A. Glavieux.(19) LDPC碼，近來又重新被發(fā)現(xiàn)。碼，近來又重新被發(fā)現(xiàn)。信息論發(fā)展中的悲情人物信息論發(fā)展中的悲情人物 諾貝爾經(jīng)濟(jì)學(xué)獲得者： JOHN NASH于1951年發(fā)表非合作博弈論 成就著名的“納什均衡”理論 1

19、958年（30歲）開始癡迷于信息編碼技術(shù)，出現(xiàn)精神失常。直到80年代末，方從癲瘋中蘇醒，繼續(xù)從事經(jīng)濟(jì)學(xué)博弈論研究，1994年獲得諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng) 奧斯卡影片奧斯卡影片美麗心靈美麗心靈第二節(jié)、信息的概念第二節(jié)、信息的概念 消息消息(message) 是信息的載體，相對具體的概念，如語言，文是信息的載體，相對具體的概念，如語言，文字，數(shù)字，圖像字，數(shù)字，圖像; 信號信號(signal) 表示消息的物理量，電信號的幅度，頻率，相表示消息的物理量，電信號的幅度，頻率，相位等等位等等; 信息信息(information) 一個(gè)抽象的概念，可以定量的描述。信息、物一個(gè)抽象的概念，可以定量的描述。信息、物質(zhì)和

20、能量是構(gòu)成一切系統(tǒng)的三大要素質(zhì)和能量是構(gòu)成一切系統(tǒng)的三大要素;第二節(jié)、信息的概念第二節(jié)、信息的概念 狹義信息論（經(jīng)典信息論）狹義信息論（經(jīng)典信息論） 研究信息測度，信道容量以及信源和信道編碼理論研究信息測度，信道容量以及信源和信道編碼理論 一般信息論一般信息論 研究信息傳輸和處理問題，除經(jīng)典信息論外還包括噪研究信息傳輸和處理問題，除經(jīng)典信息論外還包括噪聲理論，信號濾波和預(yù)測，統(tǒng)計(jì)檢測和估值理論，調(diào)聲理論，信號濾波和預(yù)測，統(tǒng)計(jì)檢測和估值理論，調(diào)制理論，信息處理理論和保密理論制理論，信息處理理論和保密理論 廣義信息論廣義信息論 除上述內(nèi)容外，還包括自然和社會(huì)領(lǐng)域有關(guān)信息的內(nèi)除上述內(nèi)容外，還包括自然

21、和社會(huì)領(lǐng)域有關(guān)信息的內(nèi)容，如模式識別，計(jì)算機(jī)翻譯，心理學(xué)，遺傳學(xué)，神容，如模式識別，計(jì)算機(jī)翻譯，心理學(xué)，遺傳學(xué)，神經(jīng)生理學(xué)經(jīng)生理學(xué)第三節(jié)、信息論的研究內(nèi)容和核心第三節(jié)、信息論的研究內(nèi)容和核心1、研究內(nèi)容：通信系統(tǒng)模型、研究內(nèi)容：通信系統(tǒng)模型信源信源編碼器編碼器信道信道譯碼器譯碼器信宿信宿干擾源干擾源通信系統(tǒng)的基本任務(wù)要求：可靠性、有效性。通信系統(tǒng)的基本任務(wù)要求：可靠性、有效性?？煽靠煽? : 要使信源發(fā)出的消息經(jīng)過傳輸后，盡可能準(zhǔn)確地、不要使信源發(fā)出的消息經(jīng)過傳輸后，盡可能準(zhǔn)確地、不失真或限定失真地再現(xiàn)在接收端。失真或限定失真地再現(xiàn)在接收端。有效有效: : 用盡可能短的時(shí)間和盡可能少的設(shè)備來傳

22、輸最大的消用盡可能短的時(shí)間和盡可能少的設(shè)備來傳輸最大的消息息通信系統(tǒng)模型進(jìn)一步細(xì)分通信系統(tǒng)模型進(jìn)一步細(xì)分信源信源信源信源編碼器編碼器信道信道編碼器編碼器調(diào)制器調(diào)制器信信道道干擾源干擾源解調(diào)器解調(diào)器信道信道譯碼器譯碼器信源信源譯碼器譯碼器信宿信宿等效離散信道等效離散信道等效離散等效離散信源信源等效信宿等效信宿信道編碼信道編碼器器信道譯碼信道譯碼器器第三節(jié)、信息論的研究內(nèi)容和核心第三節(jié)、信息論的研究內(nèi)容和核心2、研究核心、研究核心信息的測度、傳輸與處理信息的測度、傳輸與處理課程作業(yè) 1 信息論的最新研究成果綜述 要求： （1）結(jié)合自己將來的研究方向（- 2）； （2）不容許拷貝文獻(xiàn)，必須綜合多篇文

23、 獻(xiàn)，以自己的語言書寫完成（- 5）； （3） 采用2009年以后的文獻(xiàn)（- 1）； （4） 可以是全面的綜述（難），也可以 是個(gè)別成果。本章介紹本章介紹信源的統(tǒng)計(jì)特性和數(shù)學(xué)模型信源的統(tǒng)計(jì)特性和數(shù)學(xué)模型各類信源的信息測度各類信源的信息測度-熵及其性質(zhì)熵及其性質(zhì)引入信息理論的一些基本概念和重要結(jié)論引入信息理論的一些基本概念和重要結(jié)論第第一章的幾個(gè)推論章的幾個(gè)推論 通信系統(tǒng)模型：通信系統(tǒng)模型：信源編碼器信道譯碼器噪聲源信宿干擾消息信號信號干擾消息n對信息論的學(xué)習(xí)可從信源開始對信息論的學(xué)習(xí)可從信源開始n消息是信息的載荷者。信息是抽象的，消息是消息是信息的載荷者。信息是抽象的，消息是具體的。要研究信息

24、，還得從研究消息入手。具體的。要研究信息，還得從研究消息入手。n由于信源發(fā)送什么消息預(yù)先是不可知的，只能由于信源發(fā)送什么消息預(yù)先是不可知的，只能用概率空間來描述信源用概率空間來描述信源1.1 1.1 信源的數(shù)學(xué)模型及分類信源的數(shù)學(xué)模型及分類 單符號信源單符號信源： 輸出是單個(gè)符號（代碼）的消息輸出是單個(gè)符號（代碼）的消息 離散信源離散信源 連續(xù)信源連續(xù)信源 平穩(wěn)隨機(jī)序列信源平穩(wěn)隨機(jī)序列信源： 信源輸出的消息由一系列符號序列所組成，可用信源輸出的消息由一系列符號序列所組成，可用N維隨機(jī)矢維隨機(jī)矢 量量 X(X1,X2,XN)描述，且隨機(jī)矢量描述，且隨機(jī)矢量的各維概率分布都與時(shí)間起點(diǎn)無關(guān)的各維概率

25、分布都與時(shí)間起點(diǎn)無關(guān)-平穩(wěn)！平穩(wěn)！ 離散平穩(wěn)信源離散平穩(wěn)信源 連續(xù)平穩(wěn)信源連續(xù)平穩(wěn)信源 平穩(wěn)隨機(jī)序列信源（續(xù)）平穩(wěn)隨機(jī)序列信源（續(xù)）： 無記憶（獨(dú)立）離散平穩(wěn)信源無記憶（獨(dú)立）離散平穩(wěn)信源 有記憶信源有記憶信源 m階馬爾可夫信源階馬爾可夫信源 隨機(jī)波形信源隨機(jī)波形信源實(shí)際某些信源的輸出常常是時(shí)間和取值都是連續(xù)的消息.例如語音信號,電視信號.這樣的信源成為隨機(jī)波形信源；離散信源離散信源(單符號單符號) 特點(diǎn)特點(diǎn)：輸出是單個(gè)符號（代碼）的消息，符號集輸出是單個(gè)符號（代碼）的消息，符號集的取值的取值A(chǔ):a1,a2,aq是有限的或可數(shù)的，可用一是有限的或可數(shù)的，可用一維離散型隨機(jī)變量維離散型隨機(jī)變量X

26、來描述。來描述。 例：例：投硬幣、書信、電報(bào)符號等等。投硬幣、書信、電報(bào)符號等等。 數(shù)學(xué)模型數(shù)學(xué)模型：設(shè)每個(gè)信源符號設(shè)每個(gè)信源符號ai出現(xiàn)的出現(xiàn)的(先驗(yàn)先驗(yàn))概率概率 p(ai) (i=1,2,q) 滿足：滿足：)(.)()()(.)(則321321qqaPaPaPaPaaaaxPX：1)(1qiiap概率空間概率空間能表征離散信源的統(tǒng)計(jì)特性，因此也稱概率能表征離散信源的統(tǒng)計(jì)特性，因此也稱概率空間為信源空間。空間為信源空間。有記憶信源有記憶信源 信源在不同時(shí)刻發(fā)出的信源在不同時(shí)刻發(fā)出的符號之間是相互依賴的符號之間是相互依賴的，即信源輸出的平穩(wěn)隨機(jī)序列即信源輸出的平穩(wěn)隨機(jī)序列X中，各隨機(jī)變量中，

27、各隨機(jī)變量Xi之之間相互依賴。間相互依賴。 需在需在N維隨機(jī)矢量的聯(lián)合概率分布中，引入維隨機(jī)矢量的聯(lián)合概率分布中，引入條件概條件概率分布率分布來說明它們之間的關(guān)聯(lián)。來說明它們之間的關(guān)聯(lián)。 例：例：漢字組成的中文序列中，只有根據(jù)中文的語法、漢字組成的中文序列中，只有根據(jù)中文的語法、習(xí)慣用語、修辭制約和表達(dá)實(shí)際意義的制約所構(gòu)成的中習(xí)慣用語、修辭制約和表達(dá)實(shí)際意義的制約所構(gòu)成的中文序列才是有意義的中文句子或文章。所以，在漢字序文序列才是有意義的中文句子或文章。所以，在漢字序列中前后文字的出現(xiàn)是有依賴的，不能認(rèn)為是彼此不相列中前后文字的出現(xiàn)是有依賴的，不能認(rèn)為是彼此不相關(guān)的。其他如英文，德文等自然語言

28、都是如此關(guān)的。其他如英文，德文等自然語言都是如此m m階馬爾可夫信源階馬爾可夫信源 不同時(shí)刻發(fā)出的符號間的依賴關(guān)系不同時(shí)刻發(fā)出的符號間的依賴關(guān)系), 2 , 1()|()|(2112112NixxxxPxxxxxxxPmiiiimiiiiii n記憶信源的記憶長度為記憶信源的記憶長度為m+1時(shí)，稱這種有記憶信時(shí)，稱這種有記憶信源為源為m階馬爾可夫信源階馬爾可夫信源n若上述條件概率與時(shí)間起點(diǎn)若上述條件概率與時(shí)間起點(diǎn) i 無關(guān)，信源輸出的無關(guān)，信源輸出的符號序列可看成為時(shí)齊馬爾可夫鏈，則此信源稱符號序列可看成為時(shí)齊馬爾可夫鏈，則此信源稱為為時(shí)齊（平穩(wěn)）馬爾可夫信源時(shí)齊（平穩(wěn)）馬爾可夫信源1.2 1

29、.2 離散信源的信息熵其性質(zhì)離散信源的信息熵其性質(zhì) 討論基本的離散信源討論基本的離散信源(即輸出為單個(gè)符號的消即輸出為單個(gè)符號的消息，且這些消息間兩兩互不相容息，且這些消息間兩兩互不相容) 基本的離散信源可用一維隨機(jī)變量基本的離散信源可用一維隨機(jī)變量X來描述信來描述信源的輸出，信源的數(shù)學(xué)模型可抽象為源的輸出，信源的數(shù)學(xué)模型可抽象為:)(.)()()(.)(321321qqaPaPaPaPaaaaxPX1)(1qiiaP信息的度量信息的度量 考慮：考慮： 信息的度量（信息量）和不確定性消除的程度有關(guān)，信息的度量（信息量）和不確定性消除的程度有關(guān)，消除的不確定性獲得的信息量；消除的不確定性獲得的信

30、息量； 不確定性就是隨機(jī)性，可以用概率論和隨機(jī)過程來測不確定性就是隨機(jī)性，可以用概率論和隨機(jī)過程來測度，概率小度，概率小不確定性大；不確定性大； 推論：推論： 概率小概率小 信息量大，即信息量是概率的單調(diào)遞減函信息量大，即信息量是概率的單調(diào)遞減函數(shù)；數(shù)； 信息量應(yīng)該具有可加性；信息量應(yīng)該具有可加性； 信息量的計(jì)算公式為（香農(nóng)（自）信息量的度量）：信息量的計(jì)算公式為（香農(nóng)（自）信息量的度量）：)(log)(1log)(krkrkaPaPaI一一. . 自信息自信息 設(shè)離散信源設(shè)離散信源X的概率空間為：的概率空間為：)(log)(1log)()(iririiaPaPaPfaII(ai)代表兩種代表

31、兩種含義含義：（1）當(dāng)事件當(dāng)事件ai發(fā)生以前，表示事件發(fā)生以前，表示事件ai發(fā)生的不確定性發(fā)生的不確定性（2）當(dāng)事件）當(dāng)事件ai發(fā)生以后，表示事件發(fā)生以后，表示事件ai所提供的信息量所提供的信息量)(.)()()(.)(321321qqaPaPaPaPaaaaxPX1)(1qiiaPn稱事件稱事件ai發(fā)生所含有的信息量為發(fā)生所含有的信息量為 ai 的的自信息量自信息量。定義為：定義為：一點(diǎn)說明一點(diǎn)說明 計(jì)算自信息量時(shí)要注意有關(guān)事件發(fā)生概率的計(jì)算；計(jì)算自信息量時(shí)要注意有關(guān)事件發(fā)生概率的計(jì)算； 自信息量的自信息量的單位單位取決于對數(shù)的底；取決于對數(shù)的底； 底為底為2，單位為，單位為“比特比特（bi

32、t, binary unit）”； 底為底為e，單位為，單位為“奈特奈特（nat, nature unit）”； 底為底為10，單位為，單位為“哈特哈特（hat, Hartley）”； 根據(jù)換底公式得：根據(jù)換底公式得：aXXbbalogloglogn一般計(jì)算都采用以一般計(jì)算都采用以“2”為底的對數(shù)，為了書寫簡潔，為底的對數(shù)，為了書寫簡潔，常把底數(shù)常把底數(shù)“2”略去不寫略去不寫1 nat = 1.44bit , 1 hat = 3.32 bit；例子例例 8個(gè)串聯(lián)的燈泡個(gè)串聯(lián)的燈泡x1，x2，x8，其損壞的可能性是等概，其損壞的可能性是等概率的，現(xiàn)假設(shè)其中有一個(gè)燈泡已損壞，問每進(jìn)行一次測量可率的

33、，現(xiàn)假設(shè)其中有一個(gè)燈泡已損壞，問每進(jìn)行一次測量可獲得多少信息量？總共需要多少次測量才能獲知和確定哪個(gè)獲得多少信息量？總共需要多少次測量才能獲知和確定哪個(gè)燈泡已損壞。燈泡已損壞。 已知已知8個(gè)燈泡等概率損壞，所以先驗(yàn)概率個(gè)燈泡等概率損壞，所以先驗(yàn)概率P (x1)1/8 ，即，即第二次測量第二次測量獲得的信息量獲得的信息量 = I P (x2) - I P (x3)=1(bit)第三次測量第三次測量獲得的信息量獲得的信息量 = I P (x3) =1(bit)(3)(1log)(121bitxPxPI第一次測量第一次測量獲得的信息量獲得的信息量 = I P (x1) - I P (x2)=1(bi

34、t)經(jīng)過二次測量后，剩經(jīng)過二次測量后，剩2個(gè)燈泡，等概率損壞，個(gè)燈泡，等概率損壞，P (x3)1/2一次測量后，剩一次測量后，剩4個(gè)燈泡，等概率損壞，個(gè)燈泡，等概率損壞，P (x2)1/4)(2)(1log)(222bitxPxPI)(1)(1log)(323bitxPxPI自信息的推導(dǎo)自信息的推導(dǎo) 某事件發(fā)生所含有的信息量應(yīng)該是該事件發(fā)生的先驗(yàn)概率某事件發(fā)生所含有的信息量應(yīng)該是該事件發(fā)生的先驗(yàn)概率的函數(shù)。即：的函數(shù)。即： I (ai) f p(ai) 根據(jù)客觀事實(shí)和人們的習(xí)慣概念，函數(shù)根據(jù)客觀事實(shí)和人們的習(xí)慣概念，函數(shù) f p(ai) 應(yīng)滿足以應(yīng)滿足以下條件：下條件：（1）它應(yīng)是先驗(yàn)概率）它

35、應(yīng)是先驗(yàn)概率p(ai)的單調(diào)遞減函數(shù)，即當(dāng)?shù)膯握{(diào)遞減函數(shù)，即當(dāng) p (a1) p (a2) 時(shí)，有時(shí)，有 f p (a1) f p (a2) ；（2）當(dāng)）當(dāng)p (ai) =1時(shí)，時(shí)， f p (ai) = 0 （3）當(dāng)）當(dāng)p (ai) =0時(shí)，時(shí)， f p (ai) = （4）兩個(gè)獨(dú)立事件的聯(lián)合信息量應(yīng)等于它們分別的信息量之）兩個(gè)獨(dú)立事件的聯(lián)合信息量應(yīng)等于它們分別的信息量之和。即統(tǒng)計(jì)獨(dú)立信源的信息量等于它們分別的信息量之和和。即統(tǒng)計(jì)獨(dú)立信源的信息量等于它們分別的信息量之和。 可以證明可以證明對數(shù)函數(shù)對數(shù)函數(shù)滿足上述條件：滿足上述條件：)(1log)()(iriiaPaPfaI二二. . 信息熵

36、信息熵 對一個(gè)信源發(fā)出不同的消息所含有的信息量也不同。對一個(gè)信源發(fā)出不同的消息所含有的信息量也不同。所以自信息所以自信息I(I(a ai i) )是一個(gè)隨機(jī)變量，不能用它來作為是一個(gè)隨機(jī)變量，不能用它來作為整個(gè)信源整個(gè)信源的信息測度的信息測度 定義自信息的數(shù)學(xué)期望為定義自信息的數(shù)學(xué)期望為平均自信息量平均自信息量Hr(X)，稱為，稱為信息熵信息熵：qiiriirrapapapEXH1)(log)()(1log)(qiiiiapapapEXH1)(log)()(1log)(當(dāng)r2 時(shí)：rXHXHrlog/ )()( 由于這個(gè)表達(dá)式和統(tǒng)計(jì)物理學(xué)中熱熵的表達(dá)式相由于這個(gè)表達(dá)式和統(tǒng)計(jì)物理學(xué)中熱熵的表達(dá)式

37、相似，且在概念上也有相似之處，因此借用似，且在概念上也有相似之處，因此借用“熵熵”這個(gè)詞，把這個(gè)詞，把H(X)稱為信息稱為信息“熵熵”； 信息熵的信息熵的單位單位由自信息量的單位決定，即取決于由自信息量的單位決定，即取決于對數(shù)的底。對數(shù)的底。熵的計(jì)算熵的計(jì)算例例： 有一布袋內(nèi)放有一布袋內(nèi)放l00個(gè)球，其中個(gè)球，其中80個(gè)球是紅色的，個(gè)球是紅色的，20個(gè)球是白色的。隨便摸出一個(gè)球，猜測是什么顏個(gè)球是白色的。隨便摸出一個(gè)球，猜測是什么顏色，那么其概率空間為：色，那么其概率空間為： I (a1)log p(a1) log0.8= 0.32I (a2) log p(a2) log0.2 = 2.32

38、H(X)= p(a1) I (a1) p(a2) I (a2) =0.722 . 08 . 0)(21aaXPX熵的含義熵的含義 熵是熵是從整個(gè)集合的統(tǒng)計(jì)特性從整個(gè)集合的統(tǒng)計(jì)特性來考慮的，它從平均意義上來考慮的，它從平均意義上來表征信源的總體特征。來表征信源的總體特征。 在信源輸出后，信息熵在信源輸出后，信息熵H(X)表示每個(gè)消息提供的平均信表示每個(gè)消息提供的平均信息量；息量； 在信源輸出前，信息熵在信源輸出前，信息熵H(X) 表示信源的平均不確定性；表示信源的平均不確定性； 信息熵信息熵H(X) 表征了變量表征了變量X的隨機(jī)性。的隨機(jī)性。，01. 099. 0)(21aaxPX5 . 05

39、. 0)(21aayPY計(jì)算其熵，計(jì)算其熵，H(Y)H(X)，因此信源，因此信源Y比信源比信源X的平均不確定性要大。的平均不確定性要大。 例例 設(shè)甲地的天氣預(yù)報(bào)為：晴設(shè)甲地的天氣預(yù)報(bào)為：晴(占占48)、陰、陰(占占28)、大雨、大雨(占占18)、小雨、小雨(占占18)。又設(shè)乙地的天氣預(yù)報(bào)為：晴。又設(shè)乙地的天氣預(yù)報(bào)為：晴 (占占78)，小雨小雨(占占18)。試求兩地天氣預(yù)報(bào)各自提供的平均信息量。若。試求兩地天氣預(yù)報(bào)各自提供的平均信息量。若甲地天氣預(yù)報(bào)為兩極端情況，一種是晴出現(xiàn)概率為甲地天氣預(yù)報(bào)為兩極端情況，一種是晴出現(xiàn)概率為1而其余為而其余為0。另一種是晴、陰、小雨、大雨出現(xiàn)的概率都相等為另一種

40、是晴、陰、小雨、大雨出現(xiàn)的概率都相等為14。試求。試求這兩極端情況所提供的平均信息量。又試求乙地出現(xiàn)這兩極端這兩極端情況所提供的平均信息量。又試求乙地出現(xiàn)這兩極端情況所提供的平均信息量。情況所提供的平均信息量。8/18/14/11/2小雨大雨陰晴)(xPX8/18/7小雨晴)(yPY兩個(gè)信源兩個(gè)信源解：甲地天氣預(yù)報(bào)構(gòu)成的信源空間為解：甲地天氣預(yù)報(bào)構(gòu)成的信源空間為:8/18/14/11/2小雨大雨陰晴)(xPX)(log)()(41iiiaPaPXH符號）（/75. 181log8181log8141log4121log21bit乙地天氣預(yù)報(bào)的信源空間為乙地天氣預(yù)報(bào)的信源空間為:8/18/7小雨

41、晴)(yPY)/(544. 07log8781log81log8187log87)(符號bitYH天氣預(yù)報(bào)天氣預(yù)報(bào)甲地極端情況 極端情況極端情況1：晴天概率：晴天概率10001小雨大雨陰晴)(xPX0log00log00log01log1)(XH)/(0)(0loglim0符號bitXH1/41/41/41/4小雨大雨陰晴)(xPX)/(241log4141log4141log4141log41)(符號bitXHn 結(jié)論結(jié)論：等概率分布等概率分布時(shí)信源的不確定性最大，時(shí)信源的不確定性最大，所以所以信息熵信息熵（平均信息量）（平均信息量）最大最大。n極端情況極端情況2：各種天氣等概率分布：各種天

42、氣等概率分布乙地極端情況 極端情況極端情況1：晴天概率：晴天概率1)/(00log01log1)(符號bitYH1/21/2陰晴)(yPY)/( 121log)(符號bitYHn 結(jié)論結(jié)論：在極端情況：在極端情況2下，甲地比乙地提供更多的信息量。下，甲地比乙地提供更多的信息量。 因?yàn)?，甲地可能出現(xiàn)的消息數(shù)比乙地可能出現(xiàn)的消息數(shù)多。因?yàn)椋椎乜赡艹霈F(xiàn)的消息數(shù)比乙地可能出現(xiàn)的消息數(shù)多。01小雨晴)(yPYn極端情況極端情況2：各種天氣等概率分布：各種天氣等概率分布二元信源信息熵與概率空間00.20.40.60.8100.10.20.30.40.50.60.70.80.91 信息熵是信源概率空間的一

43、種特殊信息熵是信源概率空間的一種特殊矩函數(shù)矩函數(shù)。這個(gè)矩函。這個(gè)矩函數(shù)的大小，與信源的符號數(shù)及其概率分布有關(guān)。數(shù)的大小，與信源的符號數(shù)及其概率分布有關(guān)。 我們用我們用概概率矢量率矢量P來表示來表示概概率分布率分布P(x)：三、信息熵的基本性質(zhì)三、信息熵的基本性質(zhì) ),()(,),(),(2121qqpppaPaPaP P), 2 , 1(0, 11qippiqii iqiiiqiippaPaPXH11log)(log)()()(),(21PHpppHq 熵函數(shù)熵函數(shù) H(P)是概率矢量是概率矢量P的函數(shù)，稱為熵函數(shù)。的函數(shù)，稱為熵函數(shù)。 我們用下述表示方法：我們用下述表示方法： 用用H(x)

44、表示以離散隨機(jī)變量表示以離散隨機(jī)變量x描述的描述的信源的信息熵信源的信息熵； 用用H(P) 或或 H(p1, , p2 , , , , pq )表示概率矢量為表示概率矢量為P = (p1, , p2 , , , , pq )的的q個(gè)符號信源的信息熵個(gè)符號信源的信息熵。 若當(dāng)若當(dāng) q =2 時(shí)，因?yàn)闀r(shí)，因?yàn)?p1+p2 = 1, 所以將兩個(gè)符號的熵函所以將兩個(gè)符號的熵函數(shù)寫成數(shù)寫成H(p1)或或H(p2)。 熵函數(shù)熵函數(shù)H(P)是一種特殊函數(shù)，具有以下性質(zhì)。是一種特殊函數(shù)，具有以下性質(zhì)。性質(zhì)：性質(zhì)：1、對稱性、對稱性：H(P) 的取值與分量的取值與分量 p1, , p2 , , , , pq的順

45、序無關(guān)。的順序無關(guān)。 說明：說明： 從數(shù)學(xué)角度：從數(shù)學(xué)角度： H(P)= pi log pi 中的和式滿足交換率；中的和式滿足交換率；從隨機(jī)變量的角度：熵只與隨機(jī)變量的總體統(tǒng)計(jì)特性有關(guān)。從隨機(jī)變量的角度：熵只與隨機(jī)變量的總體統(tǒng)計(jì)特性有關(guān)。 一個(gè)例子：一個(gè)例子：6/ 12/ 13/ 1)( ,3/ 12/ 16/ 1)( ,2/ 16/ 13/ 1)(321321321aaazPzaaayPyaaaxPx)/(459. 1)21,61,31()(SymbolBitHXH)/(459. 1)31,21,61()(SymlobBitHYH)/(459. 1)61,21,31()(SymbolBitH

46、ZH)()()(ZHYHXH2、確定性、確定性：H(1,0)=H(1,0,0)=H(1,0,0,0)=0 性質(zhì)說明性質(zhì)說明：從總體來看，信源雖然有不同的輸出符號，：從總體來看，信源雖然有不同的輸出符號，但它只有一個(gè)符號幾乎必然出現(xiàn)，而其它符號則是幾但它只有一個(gè)符號幾乎必然出現(xiàn)，而其它符號則是幾乎不可能出現(xiàn)，那么，這個(gè)信源是一個(gè)確知信源，其乎不可能出現(xiàn)，那么，這個(gè)信源是一個(gè)確知信源，其熵等于零。熵等于零。 3、非負(fù)性、非負(fù)性： H(P) 0 說明說明：4、擴(kuò)展性、擴(kuò)展性 性質(zhì)說明：性質(zhì)說明：信源的取值數(shù)增多時(shí)，若這些取值對應(yīng)的概率信源的取值數(shù)增多時(shí)，若這些取值對應(yīng)的概率很小很小(接近于零接近于零

47、)，則信源的熵不變。，則信源的熵不變。),.,(),.,(lim212110qqqqpppHpppH),(log211qqqiiipppHpp log)log()(loglim110qiqqiipppp所以，上式成立所以，上式成立),(lim2110 qqpppH因?yàn)橐驗(yàn)? 5、可加性、可加性 統(tǒng)計(jì)獨(dú)立統(tǒng)計(jì)獨(dú)立信源信源X和和Y的的聯(lián)合信源的熵聯(lián)合信源的熵等于信源等于信源X和和Y各自的熵之和。各自的熵之和。 H(XY) = H(X)+ H(Y) l可加性是熵函數(shù)的一個(gè)重要特性，正因具有可加性，可加性是熵函數(shù)的一個(gè)重要特性，正因具有可加性，才使熵函數(shù)的形式是唯一的。才使熵函數(shù)的形式是唯一的。jij

48、ijiqpypxpyxp)()()(11, 11111nimjjimjjniiqpqp),.,.,(1212111mnmnmqpqpqpqpqpH),.,(),.,(2121mmnnqqqHpppH),.,.,(1212111mnmnmqpqpqpqpqpHnimjjijiqpqp11logmjjjniiniiimjjqqpppq1111loglogninimjjjimjijiqqppqp1111loglogmjjjniiiqqpp11loglog),.,(),.,(2121mmnnqqqHpppH它們的聯(lián)合信源是它們的聯(lián)合信源是可計(jì)算得聯(lián)合信源的聯(lián)合熵：可計(jì)算得聯(lián)合信源的聯(lián)合熵：H(Z) =

49、 H(XY) = log (nm) = log m + log n = H(X) + H(Y)nnnaaaxpXn/1./1/1.)(21mmmbbbypYm/1./1/1.)(21nmnmnmccczpZnm1.11.)(216 6、強(qiáng)可加性、強(qiáng)可加性 兩個(gè)互相關(guān)聯(lián)的信源兩個(gè)互相關(guān)聯(lián)的信源X和和Y的聯(lián)合信源的熵等于信的聯(lián)合信源的熵等于信源源X的熵加上在的熵加上在X已知條件下信源已知條件下信源Y的條件熵。的條件熵。 H（XY）=H（X）+ H（Y/X） H（Y/X）表示信源）表示信源 X 輸出一符號的條件下，輸出一符號的條件下，信源信源Y再輸出一符號所能提供的平均信息量，再輸出一符號所能提供的

50、平均信息量，稱為稱為條件熵條件熵。mjniijjimjniijijixypyxpxypxypxpXYH1111)|(log)()|(log)|()()/(H（XY）=H（X）+ H（Y/X）的證明：）的證明：),.,.,(21211121111nmnmnmppppppppppHnimjijiijipppp11logmjijijniimjiiijnipppppp1111loglog)(ninimjijijimjiijipppppp1111loglogmjijijniiniiippppp111loglog),.,(),.,(21121imiimniinnpppHppppH)(XYH H（XY）=

51、H（X）+ H（Y/X） )/(),.,(121iniinnxXYHppppH7、遞增性、遞增性 若原信源若原信源 X 中中有一個(gè)符號分割成了有一個(gè)符號分割成了m個(gè)元素個(gè)元素(符符號號)，這，這m個(gè)元素的概率之和等于原元素的概率，而個(gè)元素的概率之和等于原元素的概率，而其他符號的概率不變，則其他符號的概率不變，則新信源的熵增加新信源的熵增加。 熵的增加量等于由分割而產(chǎn)生的不確定性量。熵的增加量等于由分割而產(chǎn)生的不確定性量。),.,.,(211211mnmnqqqpppH),.,(),.,(21121nmnnmnnnnpqpqpqHpppppHnmjjniipqp11, 1證明證明:遞增性的推廣遞增性的推廣 它表示它表示n個(gè)元素的信源熵可以遞推成個(gè)元素的信源熵可以遞推成(n-1)個(gè)二元信個(gè)二元信源