信息論與編碼第2章

1、信道的通信能力可以度量嗎？在有干擾的信道上可以進(jìn)行無(wú)差錯(cuò)的通信嗎？,2,,第2章 信源及信息度量,信源的數(shù)學(xué)模型和分類 離散信源熵和互信息離散序列信源熵連續(xù)信源熵和互信息冗余度,,,,,,3,,2.1信源的數(shù)學(xué)模型和分類,信源顧名思義是產(chǎn)生消息的源頭，從數(shù)學(xué)的角度，它產(chǎn)生隨機(jī)變量、隨機(jī)序列和隨機(jī)過(guò)程的源。在這里信源指從信源發(fā)出的消息。 信源的基本特性是具有隨機(jī)屬性和概率統(tǒng)計(jì)特性,4,,2.1信源的數(shù)學(xué)模型和分類,分類

2、 按照信源發(fā)出的消息在時(shí)間上和幅度上的分布情況，把信源分為： (1) 連續(xù)信源（continuous source）：發(fā)出在時(shí)間上或幅度上是連續(xù)分布（只要滿足其中之一）的連續(xù)消息的信源，如話音、圖像，可以認(rèn)為是一個(gè)隨機(jī)過(guò)程。(2) 離散信源（discrete source）：發(fā)出在時(shí)間上和幅度上都是離散分布的信源。消息的符號(hào)的取值是有限的或可數(shù)的，且兩兩不相容。如文字、數(shù)據(jù)、電報(bào)。可以認(rèn)為是一個(gè)隨機(jī)變量或者隨機(jī)序列。,

3、5,,2.1信源的數(shù)學(xué)模型和分類,分類 按照信源發(fā)出的消息在時(shí)間上和幅度上的分布情況，把信源分為： (1) 連續(xù)信源（continuous source）：發(fā)出在時(shí)間上或幅度上是連續(xù)分布（只要滿足其中之一）的連續(xù)消息的信源，如話音、圖像，可以認(rèn)為是一個(gè)隨機(jī)過(guò)程。(2) 離散信源（discrete source）：發(fā)出在時(shí)間上和幅度上都是離散分布的信源。消息的符號(hào)的取值是有限的或可數(shù)的，且兩兩不相容。如文字、數(shù)據(jù)、電報(bào)。

4、可以認(rèn)為是一個(gè)隨機(jī)變量或者隨機(jī)序列。,6,,2.1信源的數(shù)學(xué)模型和分類,分類離散信源可以根據(jù)符號(hào)間關(guān)系細(xì)分為：： (1) 離散無(wú)記憶信源（discrete memoryless source）：所發(fā)出的各個(gè)符號(hào)之間是相互獨(dú)立的，發(fā)出的符號(hào)序列中的各個(gè)符號(hào)之間沒(méi)有統(tǒng)計(jì)關(guān)聯(lián)性，各個(gè)符號(hào)的出現(xiàn)概率是它自身的先驗(yàn)概率。(2) 離散有記憶信源（discrete source with memory）：發(fā)出的各個(gè)符號(hào)之間不是相互獨(dú)立的，

5、各個(gè)符號(hào)出現(xiàn)的概率是有關(guān)聯(lián)的。,7,,2.1信源的數(shù)學(xué)模型和分類,分類 也可以根據(jù)信源發(fā)出一個(gè)消息所用符號(hào)的多少，將離散信源分為 ： (1) 離散無(wú)記憶信源（discrete memoryless source）：所發(fā)出的各個(gè)符號(hào)之間是相互獨(dú)立的，發(fā)出的符號(hào)序列中的各個(gè)符號(hào)之間沒(méi)有統(tǒng)計(jì)關(guān)聯(lián)性，各個(gè)符號(hào)的出現(xiàn)概率是它自身的先驗(yàn)概率。(2) 離散有記憶信源（discrete source with memory）：發(fā)

6、出的各個(gè)符號(hào)之間不是相互獨(dú)立的，各個(gè)符號(hào)出現(xiàn)的概率是有關(guān)聯(lián)的。,8,,2.1信源的數(shù)學(xué)模型和分類,分類 將以上兩種分類結(jié)合，主要有下面幾種離散信源： (1) 發(fā)出單個(gè)符號(hào)的無(wú)記憶離散信源；(2) 發(fā)出符號(hào)序列的無(wú)記憶離散信源；(3) 發(fā)出符號(hào)序列的有記憶離散信源。 當(dāng)有記憶信源的相關(guān)性涉及到前面所有符號(hào)的時(shí)候，隨著序列的增加，相關(guān)性的符號(hào)也會(huì)增加，當(dāng)序列可能無(wú)限長(zhǎng)的時(shí)候，記憶的長(zhǎng)度也是無(wú)限

7、的，因此為了簡(jiǎn)化問(wèn)題，一類有限記憶、定長(zhǎng)記憶、記憶是鄰近的離散信源被提出，即馬爾可夫信源：某一個(gè)符號(hào)出現(xiàn)的概率只與前面一個(gè)或有限個(gè)符號(hào)有關(guān)，而不依賴更前面的那些符號(hào)。,9,,2.1信源的數(shù)學(xué)模型和分類,分類,10,,2.1.1 離散無(wú)記憶信源,例2-1 扔骰子每次試驗(yàn)結(jié)果必然是1～6點(diǎn)中的某一個(gè)面朝上?？梢杂靡粋€(gè)離散型隨機(jī)變量X來(lái)描述這個(gè)信源輸出的消息。 并滿足 需要注意的是，大寫字母X代表隨機(jī)變

8、量，指的是信源整體。帶下標(biāo)的小寫字母xi代表隨機(jī)事件的某一具體的結(jié)果或信源的某個(gè)元素（符號(hào)）。在信息論教材中一般如此約定,,,11,,2.1.1 離散無(wú)記憶信源,我們可用一維離散型隨機(jī)變量X來(lái)描述這些信息的輸出。這樣的信息稱為離散信源。其數(shù)學(xué)模型就是離散型的概率空間： 0≤p(xi)≤1 其中，p(xi)：信源輸出符號(hào)xi（i =1，2，…，n）的先驗(yàn)概率。當(dāng)信源給定，其相應(yīng)的概率空間就已給定；反之，如果概率空間給定，這

9、就表示相應(yīng)的信源已給定。所以概率空間能表征這離散信源的統(tǒng)計(jì)特性。以上的信息表達(dá)方式存在局限性嗎？對(duì)于具體的信息，經(jīng)過(guò)以上表示中去掉了那些因素？,,,2.1.1 離散無(wú)記憶信源,上式表示信源可能的消息（符號(hào)）數(shù)是有限的，只有n個(gè)：x1， x2， … ，xn，而且每次必定選取其中一個(gè)消息輸出，滿足完備集條件。這是最基本的離散信源。有的信源輸出的消息也是單個(gè)符號(hào)，但消息的數(shù)量是無(wú)限的，如符號(hào)集A的取值是介于a和b之間的連續(xù)值，或者取值為

10、實(shí)數(shù)集R等。連續(xù)信源：輸出在時(shí)間和幅度上都是連續(xù)分布的消息。消息數(shù)是無(wú)限的或不可數(shù)的，且每次只輸出其中一個(gè)消息。我們可用一維的連續(xù)型隨機(jī)變量X來(lái)描述這些消息。其數(shù)學(xué)模型是連續(xù)型的概率空間p(x)是隨機(jī)變量X的概率密度函數(shù)。,2.1.1 離散無(wú)記憶信源,例如：隨機(jī)取一干電池，測(cè)電壓值作為輸出符號(hào)，該信源每次輸出一個(gè)符號(hào)，但符號(hào)的取值是在[0，1.5]之間的所有實(shí)數(shù)，每次測(cè)量值是隨機(jī)的，可用連續(xù)型隨機(jī)變最X來(lái)描述。

11、很多實(shí)際信源輸出的消息是由一系列符號(hào)組成，這種用每次發(fā)出1組含2個(gè)以上符號(hào)的符號(hào)序列來(lái)代表一個(gè)消息的信源叫做發(fā)出符號(hào)序列的信源。需要用隨機(jī)序列(隨機(jī)矢量) X =（X1X2…Xl…XL）來(lái)描述信源輸出的消息，用聯(lián)合概率分布來(lái)表示信源特件。,2.1.2 離散有記憶信源,例2-2 布袋中有100個(gè)球，80個(gè)紅球，20個(gè)白球。先取出一個(gè)球，記下顏色后不放回布袋，接著取另一個(gè)。而在取第二個(gè)球時(shí)布袋中的紅球、白球概率已與取第一個(gè)球時(shí)不同，此時(shí)的

12、概率分布與第1個(gè)球的顏色有關(guān)：若第1個(gè)球?yàn)榧t色，則取第二個(gè)球時(shí)的概率p(a1)= 79/99，p(a2)= 20/99若第1個(gè)球?yàn)榘咨瑒t取第二個(gè)球時(shí)的概率p(a1)=80/99，p(a2)=19/99,2.1.2 離散有記憶信源,即組成消息的兩個(gè)球的顏色之間有關(guān)聯(lián)件，是有記憶的信源，這種信源就叫做發(fā)出符號(hào)序列的有記憶信原。例如由英文字母組成單詞，字母間是有關(guān)聯(lián)性的，不是任何字母的組合都能成為有意義的單詞，同樣不是任問(wèn)單詞的排列都能

13、形成有意義的文章等。這些都是有記憶信源。此時(shí)的聯(lián)合概率表示比較復(fù)雜，需要引入條件概率來(lái)反映信源發(fā)出符號(hào)序列內(nèi)各個(gè)符號(hào)之間的記憶特征表述的復(fù)雜度將隨著序列長(zhǎng)度的增加而增加。,2.1.2 離散有記憶信源,離散信源的統(tǒng)計(jì)特性：（1）離散消息是從有限個(gè)符號(hào)組成的符號(hào)集中選擇排列組成的隨機(jī)序列（組成離消息的信息源的符號(hào)個(gè)數(shù)是有限的）。一篇漢文，盡管文章優(yōu)美，詞匯豐富，一般所用的詞都是從常用 10 000個(gè)漢字里選出來(lái)的。一本英文書，不管

14、它有多厚，總是從26個(gè)英文字母選出來(lái)，按一定詞匯結(jié)構(gòu)，文法關(guān)系排列起來(lái)的。（2）在形成消息時(shí)，從符號(hào)集中選擇各個(gè)符號(hào)的概率不同。對(duì)大量的由不同符號(hào)組成的消息進(jìn)行統(tǒng)計(jì)，結(jié)果發(fā)現(xiàn)符號(hào)集中的每一個(gè)符號(hào)都是按一定的概率在消息中出現(xiàn)的。例如在英文中，每一個(gè)英文字母都是按照一定概率出現(xiàn)的，符號(hào)“e”出現(xiàn)最多，“z”出現(xiàn)最少。（3）組成消息的基本符號(hào)之間有一定的統(tǒng)計(jì)相關(guān)特性。,2.1.3 馬爾可夫信源,我們討論一類相對(duì)簡(jiǎn)單的離散平穩(wěn)信源，該信源在

15、某一時(shí)刻發(fā)出字母的概率除與該字母有關(guān)外，只與此前發(fā)出的有限個(gè)字母有關(guān)。若把這有限個(gè)字母記作一個(gè)狀態(tài)S，則信源發(fā)出某一字母的概率除與該字母有關(guān)外，只與該時(shí)刻信源所處的狀態(tài)有關(guān)。在這種情況下，信源將來(lái)的狀態(tài)及其送出的字母將只與信源現(xiàn)在的狀態(tài)有關(guān)，而與信源過(guò)去的狀態(tài)無(wú)關(guān)。 這種信源的一般數(shù)學(xué)模型就是馬爾可夫過(guò)程（Markov Process），所以稱這種信源為馬爾可夫信源（Markov source）?？梢杂民R爾可夫鏈（Mark

16、ov chain）來(lái)描述。,2.1.3 馬爾可夫信源,定義：信源輸出某一符號(hào)的概率僅與以前的m個(gè)符號(hào)有關(guān)，而與更前面的符號(hào)無(wú)關(guān)稱為m階馬爾可夫信源。即有：,2.1.3 馬爾可夫信源,最簡(jiǎn)單的馬爾可夫信源是一階馬爾可夫信源，如果是高階馬爾可夫信源，處理起來(lái)較為復(fù)雜。所以解決的辦法是，將m個(gè)可能影響下一步的信源符號(hào)作為一個(gè)整體，我們將m階馬爾可夫信源的m個(gè)符號(hào)組成的序列稱為狀態(tài)。,2.1.3 馬爾可夫信源,具體的轉(zhuǎn)換方法如下：令 i1

17、，i2…im ∈(1，2， …， q)狀態(tài)集,信源輸出的隨機(jī)符號(hào)序列為：信源輸出的隨機(jī)狀態(tài)序列為：例如二元序列…01011100…為二階馬爾可夫信源，考慮m = 2，Q = qm =22= 4s1 = 00 s2 = 01 s3 = 10 s4 = 11最開(kāi)始是01，對(duì)應(yīng)s2，然后將首位的0擠出，移入后面的0，即為10，對(duì)應(yīng)s3 ，接著擠出1，移入1，得到01，對(duì)應(yīng)s2，接著是11，對(duì)應(yīng)s4，接著又是11對(duì)應(yīng)s4，

18、接著是10，對(duì)應(yīng)s3，最后是00，對(duì)應(yīng)s1，所以變換成對(duì)應(yīng)的狀態(tài)序列為…s2 s3 s2 s4 s4 s3 s1…設(shè)信源在時(shí)刻m處于si狀態(tài)（即Sm= si），這里的m指時(shí)刻，而不是前面的階數(shù)，它在下一時(shí)刻(m+1)狀態(tài)轉(zhuǎn)移到sj（即Sm+1=sj）的轉(zhuǎn)移概率為：稱為基本轉(zhuǎn)移概率，也稱為一步轉(zhuǎn)移概率。若與時(shí)刻m 的取值（也可以理解為在序列中的位置）無(wú)關(guān)，則稱為齊次(時(shí)齊)馬爾可夫鏈。,,,,2.1.3 馬爾可夫信源,具有下列性質(zhì)

19、： ≥0類似地，定義k步轉(zhuǎn)移概率為,,,,2.1.3 馬爾可夫信源,由于系統(tǒng)在任一時(shí)刻可處于狀態(tài)空間中的任意一個(gè)狀態(tài)，因此狀態(tài)轉(zhuǎn)移時(shí)，轉(zhuǎn)移概率是一個(gè)矩陣,,2.1.3 馬爾可夫信源,齊次馬爾可夫鏈可以用馬爾可夫狀態(tài)轉(zhuǎn)移圖(因?yàn)槭窍戕r(nóng)提出，所以又稱香農(nóng)線圖)表示，圖中每個(gè)圓圈代表一種狀態(tài)，狀態(tài)之間的有向線代表某一狀態(tài)向另一狀態(tài)的轉(zhuǎn)移，有向線一側(cè)的符號(hào)和數(shù)字分別代表發(fā)出的符號(hào)和條件概率。,2.1.3 馬爾可夫信源,例2-3

20、設(shè)信源符號(hào)，信源所處的狀態(tài)。各狀態(tài)之間的轉(zhuǎn)移情況如圖:,,2.1.3 馬爾可夫信源,將圖中信源在狀態(tài)下發(fā)符號(hào)的條件概率用矩陣表示為 由矩陣可明顯看 出,,,,2.1.3 馬爾可夫信源,另從圖還可得,,2.1.3 馬爾可夫信源,所以信源某時(shí)刻l所處的狀態(tài)，由當(dāng)前的輸出符號(hào)和前一時(shí)刻l-1信源的狀態(tài)唯一確定。由圖還可得狀態(tài)的進(jìn)

21、一步轉(zhuǎn)移概率該信源是時(shí)齊的馬爾可夫信源。,,,2.1.3 馬爾可夫信源,齊次馬爾可夫鏈中的狀態(tài)可以根據(jù)其性質(zhì)進(jìn)行分類：如狀態(tài)si經(jīng)若干步后總能到達(dá)狀態(tài)sj，即存在k，使pij(k)＞0，則稱si可到達(dá)sj; 若兩個(gè)狀態(tài)相互可到達(dá)，則稱此二狀態(tài)相通；過(guò)渡態(tài)：一個(gè)狀態(tài)經(jīng)過(guò)若干步以后總能到達(dá)某一其他狀態(tài)，但不能從其他狀態(tài)返回；吸收態(tài)：一個(gè)只能從自身返回到自身而不能到達(dá)其他任何狀態(tài)的狀態(tài)；常返態(tài)：經(jīng)有限步后遲早要返回的狀

22、態(tài)；周期性的：在常返態(tài)中，有些狀態(tài)僅當(dāng)k能被某整數(shù)d＞1整除時(shí)才有pij(k)＞0；非周期性的：對(duì)于pij(k)＞0的所有k值，其最大公約數(shù)為1。遍歷狀態(tài)：非周期的、常返的狀態(tài)。閉集：狀態(tài)空間中的某一子集中的任何一狀態(tài)都不能到達(dá)子集以外的任何狀態(tài)。不可約的：閉集中除自身全體外再?zèng)]有其他閉集的閉集。,2.1.3 馬爾可夫信源,約的、非周期的、狀態(tài)有限的馬爾可夫鏈其k步轉(zhuǎn)移概率pij(k)在k→∞時(shí)趨于一個(gè)和初始狀態(tài)無(wú)關(guān)的極限概率

23、p(sj)，它是滿足方程組 的唯一解；,,2.1.3 馬爾可夫信源,例2-4,2.1.3 馬爾可夫信源,上圖的周期為2，因?yàn)閺腟1出發(fā)再回到S1所需的步數(shù)必為2，4，6，…，。,,,當(dāng)k為奇數(shù)時(shí)：當(dāng)k為偶數(shù)時(shí)：,,,,,2.1.3 馬爾可夫信源,2.1.3 馬爾可夫信源,所以雖

24、然方程組 是有解的，為 ，但是達(dá)不到穩(wěn)定狀態(tài)。為使馬氏鏈最后穩(wěn)定，成為遍歷的馬氏鏈，還必須有不可約性（可達(dá)性）和非周期性。,,,2.1.4 連續(xù)信源,當(dāng)信源在時(shí)間（或頻率之類）和幅度上有其中之一是連續(xù)的時(shí)候，稱為連續(xù)信源（continuous source）。如果進(jìn)一步，兩者都連續(xù)，則稱為隨機(jī)波形信源，比如模擬信號(hào)。,2.2 離散

25、信源熵和互信息,信息量與不確定性消除的程度有關(guān)。消除多少不確定性，就獲得多少信息量 ?？梢詰?yīng)用研究隨機(jī)事件的數(shù)學(xué)工具——概率論和隨機(jī)過(guò)程來(lái)度量不確定性的大小。 簡(jiǎn)單地說(shuō)，不確定性的大小可以直觀地看成是事先猜測(cè)某隨機(jī)事件是否發(fā)生的難易程度。,2.2 離散信源熵和互信息,例2-5 足球比賽的結(jié)果是不確定的。如果實(shí)力接近的兩個(gè)隊(duì)進(jìn)行比賽，在比賽之前，我們很難預(yù)測(cè)誰(shuí)能獲得勝利，所以這個(gè)事件的不確定性很大，當(dāng)?shù)弥荣惤Y(jié)果時(shí)，我們

26、就會(huì)獲得較大的信息量。如果實(shí)力相差懸殊的兩個(gè)隊(duì)進(jìn)行比賽，一般結(jié)果是強(qiáng)隊(duì)取得勝利，所以當(dāng)?shù)弥荣惤Y(jié)果是強(qiáng)隊(duì)獲勝時(shí)，我們并不覺(jué)得奇怪，因?yàn)榻Y(jié)果與我們的猜測(cè)是一致的，所以消除的不確定性較小，獲得的信息量也較?。划?dāng)?shù)弥荣惤Y(jié)果是弱隊(duì)取勝時(shí)，我們會(huì)感到非常驚訝，認(rèn)為出現(xiàn)了“黑馬”，這時(shí)將獲得很大的信息量。,2.2 離散信源熵和互信息,1. 樣本空間 把某事物各種可能出現(xiàn)的不同狀態(tài)，即所有可能選擇的消息的集合，稱為樣本空間。每個(gè)可能選擇的

27、消息是這個(gè)樣本空間的元素。在離散情況下，X的樣本空間可寫成,,2.2 離散信源熵和互信息,2. 概率測(cè)度對(duì)于離散消息的集合，概率測(cè)度就是對(duì)每一個(gè)可能選擇的消息指定一個(gè)概率（非負(fù)的，且總和為1。設(shè)樣本空間中選擇任意元素 的概率表示為 ，其腳標(biāo)X表示所考慮的概率空間是X。如果不會(huì)引起混淆，腳標(biāo)可以略去，寫成 。,,,,2.2 離散信源熵和互信息,3. 概率空間 定義：一個(gè)樣本空間和它的

28、概率測(cè)度統(tǒng)稱為一個(gè)概率空間，在離散情況下，概率空間描述為,,,,2.2.1 自信息量,信息應(yīng)該如何度量呢？從上面的分析中，我們已經(jīng)發(fā)現(xiàn)了一些線索，我們可以得出以下結(jié)論。（1）信源的不確定程度與其概率空間的消息數(shù)和消息的概率分布有關(guān)系。（2）信源的消息為等概率分布時(shí)，不確定度最大。（3）信源的消息為等概率分布，且其消息數(shù)目越多，其不確定度越大。（4）只發(fā)送一個(gè)消息的信源，其不確定度為0，不發(fā)送任何信息。（5）不確定性隨著概率增

29、加而遞減，概率越小，信息量越大。,2.2.1 自信息量,設(shè)信息量為I，我們已經(jīng)肯定I是的函數(shù)，即，根據(jù)前面的歸納做進(jìn)一步引申，可以得出以下性質(zhì)：,,2.2.1 自信息量,信息量應(yīng)具有可加性：對(duì)于兩個(gè)獨(dú)立事件，其信息量應(yīng)等于各自信息量之和，即,,,2.2.1 自信息量,我們可以發(fā)現(xiàn)對(duì)數(shù)具有這樣的性質(zhì)，由于信息量和概率具有反比關(guān)系，所以應(yīng)該取倒數(shù)后再取對(duì)數(shù).我們也可以從另外一個(gè)角度來(lái)考慮信息量，既然概率不等的時(shí)候信息量不一樣，那么我們

30、假設(shè)事件都是等概率的，取概率為p，則事件數(shù)為N=1/p，采用k進(jìn)制表示這些事件，需要的符號(hào)數(shù)為,,,2.2.1 自信息量,稱為消息(符號(hào)) ai的自信息（量）。以2為底，單位為比特（bit：binary unit)以e為底，單位為奈特（nat： nature unit) 1nat=1.433比特以10為底，單位為笛特（det：Decimal Unit)或哈特(Hart，Hartley) 1det=3.322比特,,,,,2

31、.2.1 自信息量,以下是自信息量與先驗(yàn)概率的關(guān)系,,,,,2.2.1 自信息量,如信源發(fā)某一符號(hào)ai ，假定信道中沒(méi)有噪聲的隨機(jī)干擾 ，I(ai)也就是ai本身所含有的信息量，即能提供的全部信息量，我們稱之為ai 的“自信息量”。,,,2.2.1 自信息量,由于在信道中存在干擾，假設(shè)接收端收到的消息(符號(hào))為bj，這個(gè)bj可能與相同，也可能與ai不同，則條件概率反映接收端收到消息bj而發(fā)送端發(fā)出的是ai的概率，此概率稱為后驗(yàn)概率

32、。這樣，接收端收到bj后，發(fā)送端發(fā)送的符號(hào)是否為ai尚存在的不確定性應(yīng)是后驗(yàn)概率的函數(shù)，即 稱為條件自信息量。,,,,2.2.1 自信息量,于是，收信者在收到消息bj后，已經(jīng)消除的不確定性為先驗(yàn)的不確定性減去尚存在的不確定性。這就是收信者獲得的信息量：,,,,2.2.1 自信息量,定義為發(fā)送接收bj的互信息（mutual information）。如果信道沒(méi)有干擾，信道的統(tǒng)計(jì)特性使定義為發(fā)送接收bj的互信息（mutua

33、l information）。如果信道沒(méi)有干擾，信道的統(tǒng)計(jì)特性使ai以概率1傳送到接收端。這時(shí)，收信者接到消息后尚存在的不確定性就等于0，即以概率1傳送到接收端。這時(shí)，收信者接到消息后尚存在的不確定性就等于0，即不確定性全部消除。此時(shí)互信息,,,,,,2.2.1 自信息量,例2-6 （1）一個(gè)以等概率出現(xiàn)的二進(jìn)制碼元（0，1）所包含的自信息量為：,,,,,2.2.1 自信息量,（2）若是一個(gè)m位的二進(jìn)制數(shù)，因?yàn)樵摂?shù)的每

34、一位可從0， 1兩個(gè)數(shù)字中任取一個(gè)，因此有2m個(gè)等概率的可能組合，所以，就是需要m比特的信息來(lái)指明這樣的二進(jìn)制數(shù)。類似地，也可以得出聯(lián)合自信息量。涉及兩個(gè)隨機(jī)事件的離散信源，其信源模型為,,,,,2.2.1 自信息量,,,,2.2.1 自信息量,,,,上式說(shuō)明兩個(gè)隨機(jī)事件相互獨(dú)立時(shí)，同時(shí)發(fā)生得到的自信息量，等于這兩個(gè)隨機(jī)事件各自獨(dú)立發(fā)生得到的自信息量之和。聯(lián)合自信息量和條件自信息量也滿足非負(fù)和單調(diào)遞減性，同時(shí)，它們也都是

35、隨機(jī)變量，其值隨著變量，的變化而變化。容易證明，自信息量、條件自信息量和聯(lián)合自信息量之間有如下關(guān)系：,,,2.2.2 信源熵,,,,香農(nóng)理論的重要特征是熵(entropy)的概念。香農(nóng)引用它來(lái)描述信源的平均不確定性。 計(jì)算信息熵H的公式 :,,2.2.2 信源熵,,,,信源各個(gè)離散消息的自信息量（即不確定度）的數(shù)學(xué)期望(即概率加權(quán)的統(tǒng)計(jì)平均值)為信源的信源熵，簡(jiǎn)稱熵，為了區(qū)別于熱力熵，也稱為信息熵，又由于是香農(nóng)得來(lái)，又稱香農(nóng)熵，記

36、為。計(jì)算信息熵H的公式 :,,,2.2.2 信源熵,,,,信源熵H(X)的幾種物理含義：表示信源輸出后，每個(gè)離散消息所提供的平均信息量。表示信源輸出前，信源的平均不確定度。反映了變量X的隨機(jī)性。以后我們還可以證明，熵為信源無(wú)損壓縮的極限。,,2.2.3 條件熵,,,,信源熵也稱為無(wú)條件熵，是在沒(méi)有其他的條件下的熵，當(dāng)存在某些條件影響事件的概率分布時(shí)，會(huì)影響事件的不確定度，所以存在條件熵（conditional entropy）。

37、,,2.2.3 條件熵,,,,定義：在給定某個(gè)yj條件下，xi的條件自信息量為I(xi|yj)，X集合的條件熵H（X|yj）為條件自信息量的期望，即,,,2.2.3 條件熵,,,,在給定Y條件下，X集合的條件熵為不同下條件熵的期望（加權(quán)平均），即,,,,2.2.3 條件熵,,,,相應(yīng)地，在給定X（即各個(gè)xi）的條件下，Y集合的條件熵H(Y|X)定義為：,,,2.2.3 條件熵,,,,條件熵是一個(gè)確定值，在通信中，可以表示信宿在收到Y(jié)后，

38、信源X仍然存在的不確定度。這是傳輸失真所造成的。有時(shí)我們稱為信道的疑義度（equivocation），顧名思義是在接受到消息后對(duì)發(fā)送的消息依然存在的疑義（不確定性），也稱為損失熵。即通過(guò)信道后損失的關(guān)于信源的不確定性。條件熵可以視為是噪聲造成的，所以也稱為噪聲熵。,,2.2.4 聯(lián)合熵,,,,定義：聯(lián)合熵是聯(lián)合符號(hào)集合XY上的每個(gè)元素對(duì)xiyj的自信息量的概率加權(quán)統(tǒng)計(jì)平均值，表示X和Y同時(shí)發(fā)生的不確定度。,,,2.2.4 聯(lián)合熵,,,,

39、聯(lián)合熵與條件熵有下列關(guān)系式：(1) (2),,,,2.2.5 熵函數(shù)的性質(zhì),,,,(1) 非負(fù)性信源熵是自信息的數(shù)學(xué)期望，自信息是非負(fù)值，所以信源熵一定滿足非負(fù)性。(2) 對(duì)稱性這是由于熵函數(shù)只涉及到概率，這些概率在公式中是對(duì)稱的，累加的。(3) 確定性,,,,,2.2.5 熵函數(shù)的性質(zhì),,,,(4) 香農(nóng)輔助定理（極值性）定理2-1 對(duì)于任意兩個(gè)n維概率矢量P=（p1，p2，…，pn）和Q=（q1，q2

40、，…，qn），如下不等式成立：,,,2.2.5 熵函數(shù)的性質(zhì),,,,(5) 最大熵定理,,,2.2.5 熵函數(shù)的性質(zhì),,,,定理2-2 信源X中包含n個(gè)不同離散消息時(shí)，信源熵有,,,,2.2.5 熵函數(shù)的性質(zhì),,,,(5) 最大熵定理,,,2.2.5 熵函數(shù)的性質(zhì),,,,定理2-2 信源X中包含n個(gè)不同離散消息時(shí)，信源熵有當(dāng)且僅當(dāng)X中各個(gè)消息出現(xiàn)的概率全相等時(shí)，上式取等號(hào)。,,,,2.2.6 互信息與平均互信息量,,,,前面

41、我們已經(jīng)提及互信息量等概念。在通信的一般情況下，收信者所獲取的信息量，在數(shù)量上等于通信前后不確定性的消除(減少)的量。,,,2.2.6 互信息與平均互信息量,,,,定義： 互信息 所以有：類似于條件熵，我們可以對(duì)互信息量取期望（加權(quán)平均），得到平均互信息量。,,,,,,2.2.6 互信息與平均互信息量,,,,互信息量 I (xi;yj) 在隨機(jī)變量X集合上的期望為,,,,,2.2.6 互信息與平均互信息量,,,

42、,進(jìn)一步求上述I（X; yj）在隨機(jī)變量Y集合上的概率加權(quán)統(tǒng)計(jì)平均值：,,,,,,2.2.7互信息與平均互信息量的性質(zhì),,,,互信息的性質(zhì)：（1）對(duì)稱性 （2）當(dāng)X和Y相互獨(dú)立時(shí)，互信息為0。（3）互信息量可為正值或負(fù)值。,,,2.2.8 數(shù)據(jù)處理中信息的變化,,,,定理2-3 數(shù)據(jù)處理定理： 當(dāng)消息通過(guò)多級(jí)處理器（串聯(lián)）時(shí)，隨著處理器數(shù)目的增多，輸人消息與輸出消息之間的平均互信息量趨于變小。注意：這里蘊(yùn)含一定的假設(shè)，信息在處理

43、過(guò)程中的噪聲是隨機(jī)的，與在其前面的原始信源、中間信源是相互獨(dú)立的，因此有在條件Y下X和Z獨(dú)立。,,,2.3 離散序列信源的熵,,,,前面討論的是單符號(hào)離散信源(即信源每次輸出單個(gè)符號(hào))及其各種熵。然而實(shí)際信源往往輸出的消息是時(shí)間和空間上的一系列符號(hào)。例如電報(bào)系統(tǒng)，發(fā)出的是一串有、無(wú)脈沖的信號(hào)序列。這類信源每次輸出的不是一個(gè)單個(gè)的符號(hào)，而是一個(gè)符號(hào)序列。通常一個(gè)消息序列的每一位出現(xiàn)哪個(gè)符號(hào)都是隨機(jī)的，而且一般前后符號(hào)之間的出現(xiàn)是有統(tǒng)計(jì)依賴

44、關(guān)系的，這種信源稱為離散序列信源（多符號(hào)離散信源）。,,,2.3.1 離散無(wú)記憶信源的序列熵,,,,設(shè)信源輸出的隨機(jī)序列（隨機(jī)矢量）為，＝（X1 X2…Xl…XL），序列中的單個(gè)符號(hào)變量，即序列長(zhǎng)為L(zhǎng)。設(shè)隨機(jī)序列的概率為：,,,,2.3.1 離散無(wú)記憶信源的序列熵,,,,其中我們分類討論其序列熵。為了簡(jiǎn)化問(wèn)題，假設(shè)信源無(wú)記憶（符號(hào)之間無(wú)相關(guān)性），p()=p(xi1xi2…xiL) =,,,,,2.3.1 離散無(wú)記憶信源的序列熵,,,,

45、其中，在以上條件的基礎(chǔ)上，進(jìn)一步假設(shè)信源的序列滿足平穩(wěn)特性（與序號(hào)l無(wú)關(guān)）時(shí)，有p(xi1)=p(xi2)=… =p(xiL)=p，p(xi)＝pL，則信源的序列熵又可表示為。平均每個(gè)符號(hào)熵為可見(jiàn)，對(duì)于平穩(wěn)無(wú)記憶信源平均每個(gè)符號(hào)的符號(hào)熵等于單個(gè)符號(hào)的信源熵。,,,,,2.3.2離散有記憶信源的序列熵,,,,對(duì)于有記憶信源，就不像無(wú)記憶信源那樣簡(jiǎn)單，它必須引入條件嫡的概念，而且只能在某些特殊情況下才能得到一些有價(jià)值

46、的結(jié)論。對(duì)于由兩個(gè)符號(hào)組成的聯(lián)合信源，有下列結(jié)論：,,,,,,,2.3.2離散有記憶信源的序列熵,,,,當(dāng)前后符號(hào)無(wú)依存關(guān)系時(shí)，有下列推論：,,,,,,,,2.3.2離散有記憶信源的序列熵,,,,為了便于研究，假設(shè)隨機(jī)矢量中隨機(jī)變量的各維聯(lián)合概率分布均不隨時(shí)間的推移而變化，換句話說(shuō)，信源所發(fā)出的符號(hào)序列的概率分布與時(shí)間的起點(diǎn)無(wú)關(guān)。這種信源稱為離散平穩(wěn)序列信源。,,,,,,,,2.3.2離散有記憶信源的序列熵,,,,對(duì)離散平穩(wěn)序列信源，

47、有下列性質(zhì)：（1）時(shí)間不變性 p{Xi1=x1,Xi2=x2,…,XiL=xL}= p{Xi1+h=x1,Xx2+h=x2, …,XiL+h=xL }（2）H(XL|XL-1) 是L的單調(diào)遞減函數(shù)（3）HL() ≥H(XL|XL-1)（4）HL() 是L的單調(diào)遞減函數(shù)（5）稱為極限熵或者極限信息量，注意，它是序列的平均符號(hào)熵，而不是序列熵。,,,,,

48、,,,,,2.3.3馬爾可夫信源的序列熵,,,,設(shè)一馬爾可夫信源處在某一狀態(tài)ei，當(dāng)它發(fā)出一個(gè)符號(hào)后，所處的狀態(tài)就變了，即從狀態(tài)ei變到了另一狀態(tài)。任何時(shí)刻信源處在什么狀態(tài)完全由前一時(shí)刻的狀態(tài)和此刻發(fā)出的符號(hào)決定 。,,,,,,,,2.3.3馬爾可夫信源的序列熵,,,,定理2-5 各態(tài)遍歷定理 對(duì)于有限齊次馬爾可夫鏈。若存在一個(gè)正整數(shù)，對(duì)一切i,j=1,2，…，nm都有pr(ej|ei)大于0，則對(duì)每一個(gè)j都存在不依賴于i的極限稱

49、這種馬爾可夫鏈?zhǔn)歉鲬B(tài)遍歷的。其極限概率是方程組滿足條件的惟一解。這就是有限齊次馬爾可夫鏈的各態(tài)遍歷定理。,,,,,,,,2.4 連續(xù)信源的熵和互信息,,,,連續(xù)信源是一類比較難于處理的信源，如何來(lái)求解呢？逐步分解和簡(jiǎn)化是解決這類問(wèn)題的常用方法，我們可以先將連續(xù)信源在時(shí)間上離散化，再對(duì)連續(xù)變量進(jìn)行量化分層，并用離散變量來(lái)逼近連續(xù)變量。量化間隔越小，離散變量與連續(xù)變量越接近，當(dāng)量化間隔趨近于零時(shí)，離散變量就等于連續(xù)變量。,,,,

50、,,,,2.4.1幅度連續(xù)的單個(gè)符號(hào)的信源熵,,,,連續(xù)信源熵(也叫相對(duì)熵、差熵)定義為 我們可以看到相對(duì)熵和絕對(duì)熵（信息量）相差一個(gè)無(wú)窮。我們可以這樣理解：連續(xù)信源采樣點(diǎn)需要無(wú)窮多，才能變?yōu)殡x散信源，每一個(gè)點(diǎn)都帶有信息量，所以差一個(gè)無(wú)窮。好像沒(méi)有意義了。工程上我們主要是比較信源熵，將無(wú)窮項(xiàng)約掉，就有意義了。一般我們將相對(duì)熵簡(jiǎn)稱為熵。,,,,,,,,,2.4.2 波形信源熵,,,,波形信源在概念上與離散信源是不同的，但也有不少

51、類似之處。對(duì)連續(xù)信源的分析，也可以類似于離散信源從單個(gè)連續(xù)消息（變量）開(kāi)始，在推廣至連續(xù)消息序列。對(duì)于連續(xù)隨機(jī)變量可采用概率密度來(lái)描述：對(duì)連續(xù)隨機(jī)序列可采用相應(yīng)的序列概率密度來(lái)描述；而對(duì)于連續(xù)的隨機(jī)過(guò)程一般也可以按照取樣定理分解為連續(xù)隨機(jī)變量序列來(lái)描述。取樣之后還要對(duì)取值的離散化。取樣加量化才使隨機(jī)過(guò)程變換成時(shí)間的取值都是離散的隨機(jī)序列。量化必然帶來(lái)量化噪聲，引起信息損失。,,,,,,,,2.4.2 波形信源熵,,,,就統(tǒng)計(jì)特性的區(qū)別來(lái)

52、說(shuō)，隨機(jī)過(guò)程大致可分為平穩(wěn)隨機(jī)過(guò)程和非平穩(wěn)過(guò)程兩大類。如果是平穩(wěn)的隨機(jī)過(guò)程的熵也可以轉(zhuǎn)換為平穩(wěn)隨機(jī)序列的熵。對(duì)于平穩(wěn)隨機(jī)過(guò)程，其 {x(t)}和{y(t)}可以通過(guò)取樣，分解成取值連續(xù)的無(wú)窮平穩(wěn)隨機(jī)序列來(lái)表示，所以平穩(wěn)隨機(jī)過(guò)程的熵就是無(wú)窮平穩(wěn)隨機(jī)序列的熵。,,,,,,,,2.4.3 最大熵定理,,,,離散信源在等概率的時(shí)候，熵值最大，那么在連續(xù)信源中，當(dāng)概率密度函數(shù)滿足什么條件時(shí)才能使連續(xù)信源相對(duì)熵最大？我們考慮通常我們最感興趣的是兩種

53、情況：一種是信源的輸出值受限；另一種是信源的輸出平均功率受限。,,,,,,,,2.4.3 最大熵定理,,,,1. 峰值功率受限條件下信源的最大值若某信源輸出信號(hào)的峰值功率受限，它等價(jià)于信源輸出的連續(xù)隨機(jī)變量X的取值幅度受限，限于[a，b]內(nèi)取值。在約束條件 下信源的最大相對(duì)熵。定理2-6 若信源輸出的幅度被限定在[a，b]區(qū)域內(nèi)，則當(dāng)輸出信號(hào)的概率密度是均勻分布時(shí)信源具有最大熵。其值等于lo

54、g(b-a)。若當(dāng)N維隨機(jī)矢量取值受限時(shí)，也只有隨機(jī)分量統(tǒng)計(jì)獨(dú)立并均勻分布時(shí)具有最大熵。,,,,,,,,,2.4.3 最大熵定理,,,,2. 平均功率受限條件下信源的最大值定理2-7 若一個(gè)連續(xù)信源輸出信號(hào)的平均功率被限定為P，則其輸出信號(hào)幅度的概率密度分布是高斯分布時(shí)，信源有最大熵，其值為 對(duì)于N維連續(xù)平穩(wěn)信源來(lái)說(shuō)，若其輸出的N維隨機(jī)序列的協(xié)方差矩陣C被限定，則N維隨機(jī)為正態(tài)分布時(shí)信源的熵最大，N維高斯信源的熵最大，其值為

55、這一結(jié)論說(shuō)明，當(dāng)連續(xù)信源輸出信號(hào)的平均功率受限時(shí)，只有信號(hào)的統(tǒng)計(jì)特性與高斯統(tǒng)計(jì)特性一樣時(shí)，才會(huì)有最大的熵值。,,,,,,,,,,2.5 冗余度,,,,冗余度（多余度、剩余度，redundancy）表示給定信源在實(shí)際發(fā)出消息時(shí)所包含的多余信息。,,,,,,,,2.5 冗余度,,,,冗余度來(lái)自兩個(gè)因素，一是信源符號(hào)間的相關(guān)性，由于信源輸出符號(hào)間的依賴關(guān)系使得信源熵減小，這就是信源的相關(guān)性。相關(guān)程度越大，信源的實(shí)際熵越小，趨于極限熵；

56、反之相關(guān)程度減小，信源實(shí)際熵就增大。另一個(gè)方面是信源符號(hào)分布的不均勻性，當(dāng)?shù)雀怕史植紩r(shí)信源熵最大。而實(shí)際應(yīng)用中大多是不均勻分布，使得實(shí)際熵減小。,,,,,,,,2.5 冗余度,,,,我們定義信息效率為,,,,,,,,,2.6 最大熵原理,,,,在投資時(shí)常常講不要把所有的雞蛋放在一個(gè)籃子里，這樣可以降低風(fēng)險(xiǎn)。在信息處理中，這個(gè)原理同樣適用。在數(shù)學(xué)上，這個(gè)原理稱為最大熵原理(the maximum entropy principle)。,

57、,,,,,,,2.6 最大熵原理,,,,最大熵原理的實(shí)質(zhì)就是，在已知部分知識(shí)的前提下，關(guān)于未知分布最合理的推斷就是符合已知知識(shí)最不確定或最隨機(jī)的推斷，這是我們可以做出的唯一不偏不倚的選擇，任何其它的選擇都意味著我們?cè)黾恿似渌募s束和假設(shè)，這些約束和假設(shè)根據(jù)我們掌握的信息無(wú)法作出。,,,,,,,,2.7 關(guān)于熵概念的理解與題意解讀,,,,1. 熵可以從以下角度來(lái)詮釋：猜測(cè)一個(gè)事件需要的信息量；該事件未被告知時(shí)，事件本身的不確定性；知

58、道該事件后消除的不確定性：知道前，具有不確定性H(X)，知道后不確定性為0，所以消除的不確定性即為H(X)。告訴我們某事件后提供的信息量；要告訴我們這個(gè)事件，需要發(fā)送的最短消息長(zhǎng)度。條件熵H(X|Y)， H(X|yi)是在已知某條件（這個(gè)條件可以是具體的yi，也可以是隨機(jī)變量Y）后的平均的不確定性，在以上我們討論X是否已知的前后，yi和Y均為已知的。事件X本身的不確定性H(X)，但是知道事件Y或yi后，X的不確定性減少為H(X|Y

59、)或H(X|yi)。,,,,,,,,2.7 關(guān)于熵概念的理解與題意解讀,,,,2. 條件熵可以從以下角度來(lái)詮釋：在事件X未被告知之前，在知道條件的情況下X的平均不確定度；條件是前提的情況下，告訴你關(guān)于X的信息，獲得的信息量；條件是前提的情況下，告訴你關(guān)于X的信息，消除的平均不確定度。其他的詮釋可以類似于熵，比如猜測(cè)的時(shí)候的信息量，只不過(guò)是增加了一個(gè)條件。平均互信息量是無(wú)條件熵和條件熵之差，類似于條件熵，它這里的兩個(gè)事件可以都是

60、隨機(jī)變量，也可以有一個(gè)是隨機(jī)變量，另外一個(gè)是確定的量。,,,,,,,,2.7 關(guān)于熵概念的理解與題意解讀,,,,3. 平均互信息量可以從以下角度來(lái)詮釋：已知事件Y后，X的不確定性由H(X)減少為H(X|Y)， 所以在知道Y的情況下，告訴你關(guān)于X的信息量為H(X)-H(X|Y)， 這個(gè)量即為平均互信息量；通信中獲得的關(guān)于另一端的信息量。此外，平均互信息量也是冗余的一種體現(xiàn)。和條件熵一樣，對(duì)應(yīng)可以參考對(duì)熵的詮釋來(lái)理解平均互信息量。