第2章信源與信源熵

第2章信源及信源熵2.1信源的描述和分類2.2離散信源熵和互信息2.3離散序列信源熵2.4冗余度2.5連續(xù)信源熵和互信息2/1/20231復(fù)習(xí)信息的概念在信息論中，信源是發(fā)出消息的源，信源輸出以符號(hào)形式出現(xiàn)的具體消息。如果符號(hào)是確定的而且預(yù)先是知道的，那么該消息就無信息而言。只有當(dāng)符號(hào)的出現(xiàn)是隨機(jī)的，預(yù)先無法確定，那么一旦出現(xiàn)某個(gè)符號(hào)就給觀察者提供了信息。因此，應(yīng)該用隨機(jī)變量或隨機(jī)矢量來表示信源，運(yùn)用概率論和隨機(jī)過程的理論來研究信息，這就是香農(nóng)信息論的基本點(diǎn)。2/1/20232復(fù)習(xí)信息的概念信息不確定性（隨機(jī)性）隨機(jī)變量隨機(jī)矢量概率論隨機(jī)過程2/1/202332.1信源的描述和分類按信源在時(shí)間和幅度上的分布情況離散信源：文字、數(shù)據(jù)、電報(bào)連續(xù)信源：語音、圖像按發(fā)出符號(hào)的數(shù)量單個(gè)符號(hào)信源：指信源每次只發(fā)出一個(gè)符號(hào)代表一個(gè)消息符號(hào)序列信源：指信源每次發(fā)出一組含二個(gè)以上符號(hào)的符號(hào)序列代表一個(gè)消息按符號(hào)間的關(guān)系無記憶信源有記憶信源信源所發(fā)出的各個(gè)符號(hào)是相互獨(dú)立的，發(fā)出的符號(hào)序列中的各個(gè)符號(hào)之間沒有統(tǒng)計(jì)關(guān)聯(lián)性信源所發(fā)出的各個(gè)符號(hào)的概率是有關(guān)聯(lián)的2/1/20234信源分類信源{無記憶信源有記憶信源{{發(fā)出單個(gè)符號(hào)的無記憶信源發(fā)出符號(hào)序列的無記憶信源發(fā)出符號(hào)序列的有記憶信源發(fā)出符號(hào)序列的馬爾可夫信源馬爾可夫信源：某一個(gè)符號(hào)出現(xiàn)的概率只與前面一個(gè)或有限個(gè)符號(hào)有關(guān)，而不依賴更前面的那些符號(hào)2/1/20235概率空間概率隨機(jī)現(xiàn)象中事件發(fā)生的可能性大小是客觀存在的，因此可以對(duì)它進(jìn)行量度。量度的數(shù)量指標(biāo)就是概率。樣本空間某事物各種可能出現(xiàn)的不同狀態(tài)，即所有可能選擇的消息集合。每個(gè)可能選擇的消息是這個(gè)樣本空間的一個(gè)元素。概率空間對(duì)于離散消息的集合，概率測(cè)度就是對(duì)每一個(gè)可能選擇的消息指定一個(gè)概率。一個(gè)樣本空間和它的概率測(cè)度一起構(gòu)成一個(gè)概率空間。2/1/20236概率空間數(shù)學(xué)定義 一個(gè)離散信源發(fā)出的各個(gè)符號(hào)消息的集合為它們的概率分別為該信源的概率空間為顯然有信源空間先驗(yàn)概率2/1/20237概率論復(fù)習(xí)無條件概率P(xi)又稱先驗(yàn)概率，指基于以往數(shù)據(jù)記錄統(tǒng)計(jì)得到的概率條件概率P(B/A)在已知事件A發(fā)生條件下，事件B發(fā)生的概率又稱后驗(yàn)概率聯(lián)合概率P(AB)事件A和事件B同時(shí)發(fā)生的概率2/1/20238概率論復(fù)習(xí)完備性非負(fù)性2/1/20239概率論復(fù)習(xí)聯(lián)合概率貝葉斯公式2/1/202310單個(gè)符號(hào)的離散無記憶信源有些信源可能輸出的消息數(shù)是有限的或可數(shù)的，而且每次只輸出其中一個(gè)消息。如書信文字、計(jì)算機(jī)的代碼、電報(bào)符號(hào)、阿拉伯?dāng)?shù)字碼等。例如：擲骰子扔一顆質(zhì)地均勻的骰子，每次扔擲的結(jié)果必然是1點(diǎn)～6點(diǎn)中的某一面朝上，哪一面朝上是隨機(jī)的。2/1/202311單個(gè)符號(hào)的離散無記憶信源用一維離散型隨機(jī)變量X來描述這些信息的輸出。數(shù)學(xué)模型當(dāng)信源給定，其相應(yīng)的概率空間就已給定；反之，如果概率空間給定，這就表示相應(yīng)的信源已給定。信源可能的消息（符號(hào)）數(shù)是有限的，而且每次必定選取其中一個(gè)消息輸出，滿足完備集條件。2/1/202312單符號(hào)連續(xù)無記憶信源連續(xù)信源：輸出在時(shí)間和幅度上都是連續(xù)分布的連續(xù)消息的信源。單符號(hào)連續(xù)無記憶信源消息數(shù)無限或不可數(shù)，且每次只輸出其中一個(gè)消息。可用一維的連續(xù)型隨機(jī)變量X來描述這些消息。

數(shù)學(xué)描述例：隨機(jī)取一節(jié)干電池測(cè)其電壓值作為輸出符號(hào)，符號(hào)取值為[0，1.5]之間的所有實(shí)數(shù)。pX(x)是隨機(jī)變量X的概率密度函數(shù)

2/1/202313符號(hào)序列的離散無記憶信源很多實(shí)際信源輸出的消息往往是由一系列符號(hào)組成，這種用每次發(fā)出1組含2個(gè)以上符號(hào)的符號(hào)序列來代表一個(gè)消息的信源叫做發(fā)出符號(hào)序列的信源。設(shè)信源輸出的隨機(jī)序列為X， 序列中的變量 即序列長(zhǎng)為L(zhǎng)扔骰子：以三位二進(jìn)制符號(hào)表示結(jié)果2/1/202314符號(hào)序列的離散無記憶信源最簡(jiǎn)單的符號(hào)序列信源是L＝2的情況，即 信源：

信源空間：當(dāng)信源無記憶時(shí)，2/1/202315符號(hào)序列的離散無記憶信源二元信源｛0,1｝單符號(hào)離散信源二次擴(kuò)展信源三次擴(kuò)展信源三元信源｛0,1,2｝三元二次擴(kuò)展信源樣本N＝3序列長(zhǎng)度L＝22/1/202316符號(hào)序列的離散無記憶信源L次擴(kuò)展信源每個(gè)隨機(jī)變量取值有n種，那么序列長(zhǎng)為L(zhǎng)的隨機(jī)序列，其樣值共有nL種可能取值。這種由信源X輸出的L長(zhǎng)隨機(jī)序列X所描述的信源叫做離散無記憶信源X的L次擴(kuò)展信源。數(shù)學(xué)描述 其中，2/1/202317離散有記憶信源一般情況下，信源在不同時(shí)刻發(fā)出的符號(hào)之間是相互依賴的，也就是信源輸出的平穩(wěn)隨機(jī)序列X中，各隨機(jī)變量xl之間是有依賴關(guān)系的。如：袋中摸球 文字序列的前后關(guān)系表述有記憶信源比表述無記憶信源困難得多離散有記憶信源發(fā)出符號(hào)序列的有記憶信源發(fā)出符號(hào)序列的馬爾可夫信源用信源發(fā)出的一個(gè)符號(hào)序列的整體概率(即聯(lián)合概率)反映有記憶信源的特征一個(gè)符號(hào)出現(xiàn)的概率只與前面一個(gè)或有限個(gè)符號(hào)有關(guān),而不依賴更前面的那些符號(hào)2/1/202318離散有記憶信源例如由英文字母組成單詞，字母間是有關(guān)聯(lián)性的，不是任何字母的組合都能成為有意義的單詞。例如布袋中有100個(gè)球，80個(gè)紅球，20個(gè)白球。先取出一個(gè)球，記下顏色后不放回布袋，接著取另一個(gè)。取第一個(gè)球時(shí)的概率p(紅球)=，p(白球)=若第1個(gè)球?yàn)榧t色，則取第二個(gè)球時(shí)的概率 p(紅球)=，p(白球)=若第1個(gè)球?yàn)榘咨瑒t取第二個(gè)球時(shí)的概率 p(紅球)=，p(白球)=80/10079/9920/9980/9919/9920/1002/1/202319離散有記憶信源有記憶信源的聯(lián)合概率表示比較復(fù)雜，需要引入條件概率來反映信源發(fā)出符號(hào)序列內(nèi)各個(gè)符號(hào)之間的記憶特征。2/1/202320馬爾可夫信源馬爾可夫信源（相對(duì)簡(jiǎn)單的離散平穩(wěn)信源）信源在某一時(shí)刻發(fā)出符號(hào)的概率除與該符號(hào)有關(guān)外，只與此前發(fā)出的有限個(gè)符號(hào)有關(guān)。若把這有限個(gè)符號(hào)記作一個(gè)狀態(tài)S，則信源發(fā)出某一符號(hào)的概率除與該符號(hào)有關(guān)外，只與該時(shí)刻信源所處的狀態(tài)有關(guān)。在這種情況下，信源將來的狀態(tài)及其送出的符號(hào)將只與信源現(xiàn)在的狀態(tài)有關(guān)，而與信源過去的狀態(tài)無關(guān)。m階馬爾可夫信源信源輸出某一符號(hào)的概率僅與以前的m個(gè)符號(hào)有關(guān)，而與更前面的符號(hào)無關(guān)。2/1/202321馬爾可夫信源：條件概率一階馬爾可夫信源m階馬爾可夫信源2/1/202322連續(xù)平穩(wěn)信源連續(xù)平穩(wěn)信源若信源輸出的消息需用L維隨機(jī)矢量來描述，

其中每個(gè)隨機(jī)變量Xl都是取值為連續(xù)的連續(xù)型隨機(jī)變量，并且滿足隨機(jī)矢量X的各維概率密度函數(shù)與時(shí)間起點(diǎn)無關(guān)，這樣的信源稱為連續(xù)平穩(wěn)信源。例如語音信號(hào)、熱噪聲信號(hào)等在時(shí)間上取樣離散化后的信源，在時(shí)間上是離散的，但每個(gè)隨機(jī)變量Xl的取值都是連續(xù)的。2/1/202323隨機(jī)波形信源隨機(jī)波形信源實(shí)際信源輸出的消息常常是時(shí)間和取值都是連續(xù)的，這類信源稱為隨機(jī)波形信源。這種信源輸出的消息可用隨機(jī)過程來描述。根據(jù)取樣定理對(duì)隨機(jī)過程進(jìn)行取樣，把隨機(jī)過程用一系列時(shí)間（或頻率）域上離散的取樣值來表示，每個(gè)取樣值都是連續(xù)型隨機(jī)變量。這樣，就可以把隨機(jī)過程轉(zhuǎn)換成時(shí)間（或頻率）上離散的隨機(jī)序列來處理。2/1/202324信源分類與描述圖2/1/202325第2章信源及信源熵2.1信源的描述和分類2.2離散信源熵和互信息2.3離散序列信源的熵2.4冗余度2.5連續(xù)信源的熵和互信息2/1/2023262.2離散信源熵和互信息不確定性、先驗(yàn)概率和信息量隨機(jī)事件的不確定性是客觀存在的。只有當(dāng)信源發(fā)出的消息通過信道傳輸給收信者后，才能消除不確定性并獲得信息。隨機(jī)事件的先驗(yàn)概率越小，事件發(fā)生的困難程度就越大，不確定性就越大。收到某消息獲得的信息量＝不確定性減少的量＝（收到此信息前關(guān)于某事件發(fā)生的不確定性）－（收到此信息后關(guān)于某事件發(fā)生的不確定性）2/1/202327自信息量某事件發(fā)生所攜帶的信息量是和該事件出現(xiàn)的概率有關(guān)，概率可以表征自信息量的大小根據(jù)客觀事實(shí)和人們的習(xí)慣概念，自信息量應(yīng)滿足以下條件：自信息量應(yīng)是先驗(yàn)概率的單調(diào)遞減函數(shù)當(dāng)時(shí)，當(dāng)時(shí)，兩個(gè)獨(dú)立事件的聯(lián)合信息量應(yīng)等于它們分別的信息量之和。2/1/202328自信息量隨機(jī)事件的自信息量定義為其概率對(duì)數(shù)的負(fù)值，從多個(gè)角度理解I(xi)的含義:事件xi

是否發(fā)生的不確定性的大小事件xi的發(fā)生帶給我們的信息量的大小事件xi

是否發(fā)生所需的信息量的大小事件xi的發(fā)生帶給我們的比特?cái)?shù)2/1/202329自信息量和不確定度隨機(jī)事件的不確定度在數(shù)量上等于它的自信息量，兩者的單位相同，但含義不同。具有某種概率分布的隨機(jī)事件不管發(fā)生與否，都存在不確定度，不確定度表征了該事件的特性而自信息量是在該事件發(fā)生后給予觀察者的信息量。

2/1/202330自信息量自信息量的單位在信息論中常用的對(duì)數(shù)底是2，信息量的單位為比特(bit)；若取自然對(duì)數(shù)，則信息量的單位為奈特(nat);若以10為對(duì)數(shù)底,則信息量的單位為笛特(det)。1nat＝log2e≈l.433bit1det＝log210≈3.322bit哈特萊Hartley2/1/202331自信息量二進(jìn)制碼元0,1,當(dāng)符號(hào)概率為p(0)=1/4,p(1)=3/4,則這兩個(gè)符號(hào)的自信息量為：

I(0)=－log2p(0)=－log2(1/4)=log24=2bit

I(1)=－log2p(1)=－log2(3/4)=0.415bit一個(gè)以等概率出現(xiàn)的二進(jìn)制碼元(0,1)所包含的自信息量為：

I(0)=I(1)=－log2(1/2)=log22=1bit一個(gè)m位的二進(jìn)制數(shù),有

個(gè)等概率的可能組合

I=－log2(1/2m)=mbit2m2/1/202332自信息量例：英文字母中“e”出現(xiàn)的概率為0.105，“c”出現(xiàn)的概率為0.023，“z”出現(xiàn)的概率為0.001。分別計(jì)算它們的自信息量。解：“e”的自信息量I(e)=－log20.105=3.25bit “c”的自信息量I(c)=－log20.023=5.44bit “z”的自信息量I(z)=－log20.001=9.97bit2/1/202333自信息量的特性I(xi)是非負(fù)值當(dāng)p(xi)=1時(shí)，I(xi)=0當(dāng)p(xi)=0時(shí)，I(xi)=∞I(xi)是先驗(yàn)概率p(xi)的單調(diào)遞減函數(shù)，即當(dāng)p(x1)＞p(x2)時(shí)，I(x1)＜I(x2)兩個(gè)獨(dú)立事件的聯(lián)合信息量等于它們分別的信息量之和。即：統(tǒng)計(jì)獨(dú)立信源的信息量等于它們分別的信息量之和。2/1/202334聯(lián)合自信息量?jī)蓚€(gè)消息xi，yj同時(shí)出現(xiàn)的聯(lián)合自信息量當(dāng)xi,yj相互獨(dú)立時(shí)，有p(xi

yj)=p(xi)p(yj)，那么就有I(xi

yj)=I(xi)+I(yj)。xi

yj所包含的不確定度在數(shù)值上也等于它們的自信息量。2/1/202335條件自信息量在事件yj出現(xiàn)的條件下，隨機(jī)事件xi發(fā)生的條件概率為p(xi/yj)，則它的條件自信息量定義為條件概率對(duì)數(shù)的負(fù)值：在給定yj條件下，隨機(jī)事件xi所包含的不確定度在數(shù)值上與條件自信息量相同，但兩者含義不同。聯(lián)合自信息量、條件自信息量和自信息量2/1/202336離散信源熵例：一個(gè)布袋內(nèi)放100個(gè)球，其中80個(gè)球是紅色的，20個(gè)球是白色的，若隨機(jī)摸取一個(gè)球，猜測(cè)其顏色，求平均摸取一次所能獲得的自信息量。解:依據(jù)題意，這一隨機(jī)事件的概率空間為如果摸出的是紅球，則獲得的信息量是如果摸出的是白球，則獲得的信息量是2/1/202337離散信源熵每次摸出一個(gè)球后放回袋中，再進(jìn)行下一次摸取。 如此摸取n次，紅球出現(xiàn)的次數(shù)為np(x1)次，白球出現(xiàn)的次數(shù)為np(x2)次。隨機(jī)摸取n次后總共所獲得信息量為平均隨機(jī)摸取一次所獲得的信息量為平均信息量信源X的熵2/1/202338離散信源熵H(X)定義離散信源熵為信源中各個(gè)符號(hào)不確定度的數(shù)學(xué)期望單位為：比特/符號(hào)或者比特/符號(hào)序列。信息熵H(X)表示信源輸出后，每個(gè)消息(或符號(hào))所提供的平均信息量。平均不確定度/平均信息量/平均自信息量當(dāng)某一符號(hào)xi的概率p(xi)為零時(shí)，p(xi)log2

p(xi)在熵公式中無意義，為此規(guī)定這時(shí)的p(xi)log2

p(xi)為零。2/1/202339離散信源熵H(X)信源熵的物理含義表示信源輸出前信源的平均不確定性表示信源輸出后每個(gè)符號(hào)所攜帶的平均信息量例：有兩個(gè)信源，其概率空間分別為H(Y)>H(X)：信源Y比信源X的平均不確定性要大2/1/202340離散信源熵H(X)例：電視屏上約有個(gè)格點(diǎn)，按每點(diǎn)有10個(gè)不同的灰度等級(jí)考慮，則共能組成個(gè)不同的畫面。按等概率計(jì)算，平均每個(gè)畫面可提供的信息量為2/1/202341離散信源熵H(X)例：有一篇千字文章，假定每字可從萬字表中任選，則共有不同的千字文N=100001000=104000篇，仍按等概計(jì)算，平均每篇千字文可提供的信息量為Apictureisworthathousandwords2/1/202342離散信源熵H(X)例：信源X輸出符號(hào)只有兩個(gè)，設(shè)為0和1。輸出符號(hào)發(fā)生的概率分別為p和q，p＋q=l。即信源的概率空間為

二元信源熵為2/1/202343q=1離散信源熵H(X)信源熵H(X)是概率p的函數(shù)，通常用H(p)表示，p取值于[0,1]區(qū)間。H(p)函數(shù)曲線如圖所示：如果二元信源的輸出符號(hào)是確定的,即p=1或q=1,則該信源不提供任何信息。當(dāng)二元信源符號(hào)0和1以等概率發(fā)生時(shí),信源熵達(dá)到極大值,等于1比特信息量。p=1p=q=0.52/1/202344條件熵在給定yj條件下，xi的條件自信息量為I(xi/yj)，X集合的條件熵在給定Y（即各個(gè)yj）條件下，X集合的條件熵在給定X（即各個(gè)xi）條件下，Y集合的條件熵條件熵是在聯(lián)合符號(hào)集合XY上的條件自信息量的聯(lián)合概率加權(quán)統(tǒng)計(jì)平均值。2/1/202345條件熵例：考慮下面兩個(gè)隨機(jī)變量X和Y，其中

計(jì)算條件熵H(X/Y)。解：

2/1/202346聯(lián)合熵聯(lián)合熵是聯(lián)合符號(hào)集合XY上的每個(gè)元素對(duì)xiyj的自信息量的概率加權(quán)統(tǒng)計(jì)平均值聯(lián)合熵H(XY)表示X和Y同時(shí)發(fā)生的不確定度。聯(lián)合熵、信源熵和條件熵之間的關(guān)系2/1/202347定理證明證明：2/1/202348聯(lián)合熵例：令XY具有如下的聯(lián)合分布，求信源熵和聯(lián)合熵XY1234Σ11/81/161/321/321/421/161/81/321/321/431/161/161/161/161/441/40001/4Σ1/21/41/81/81解：p(y1)p(x4)比特/符號(hào)比特/符號(hào)比特/符號(hào)2/1/202349例題例：二進(jìn)制通信系統(tǒng)用符號(hào)“0”和“1”，由于存在失真，傳輸時(shí)會(huì)產(chǎn)生誤碼，用符號(hào)表示下列事件：

u0：一個(gè)“0”發(fā)出；u1：一個(gè)“1”發(fā)出；

v0：一個(gè)“0”收到；v1：一個(gè)“1”收到。 給定下列概率：

p(u0)＝1/2，p(v0/u0)＝3/4，p(v0/u1)=1/2。求：⑴已知發(fā)出一個(gè)“0”，求收到符號(hào)后得到的信息量；⑵已知發(fā)出的符號(hào)，求收到符號(hào)后得到的信息量；⑶知道發(fā)出的和收到的符號(hào)，求能得到的信息量；⑷已知收到的符號(hào)，求被告知發(fā)出的符號(hào)得到的信息量。H(V/u0)H(V/U)H(UV)H(U/V)2/1/202350例題解：⑴p(v1/u0)=1－p(v0/u0)=1/4⑵聯(lián)合概率：

p(u0v0)=p(v0/u0)p(u0)=3/4×1/2=3/8

p(u0v1)=p(v1/u0)p(u0)=1/4×1/2=1/8

p(u1v0)=p(v0/u1)p(u1)=1/2×1/2=1/4

p(u1v1)=p(v1/u1)p(u1)=1/2×1/2=1/42/1/202351例題⑶解法1：解法2：

2/1/202352例題(4)解法1：

p(v0)=p(u0v0)+p(u1v0)=3/8+1/4=5/8

p(v1)=1-p(v0)=3/8 解法2：利用貝葉斯公式

p(u0/v0)=3/5

p(u1/v0)=2/5

p(u0/v1)=1/3p(u1/v1)=2/32/1/202353例題例：一個(gè)二進(jìn)制信源X發(fā)出符號(hào)集{0,1}，經(jīng)過離散無記憶信道傳輸，信道輸出用Y表示。由于信道中存在噪聲，接收端除收到0和1的符號(hào)外，還有不確定符號(hào)，用“2”表示。已知X的先驗(yàn)概率為:p(x0)=2/3，p(x1)=1/3符號(hào)轉(zhuǎn)移概率：p(y0/x0)=3/4，p(y2/x0)=1/4

p(y1/x1)=1/2，p(y2/x1)=1/2 求：聯(lián)合熵H(XY)XY010123/41/21/21/42/1/202354例題信源熵：由 得聯(lián)合概率：p(x0y0)=p(x0)p(y0/x0)=2/3×3/4=1/2p(x1y0)=p(x1)p(y0/x1)=0p(x0y1)=p(x0)p(y1/x0)=0 p(x1y1)=p(x1)p(y1/x1)=1/3×1/2=1/6

p(x0y2)=p(x0)p(y2/x0)=2/3×1/4=1/6p(x1y2)=p(x1)p(y2/x1)=1/3×1/2=1/6條件熵：聯(lián)合熵：H(XY)＝H(X)＋H(Y/X)=1.8bit/符號(hào)2/1/202355另一種解法Ｙ的無條件概率 p(y0)=∑p(xiy0)=p(x0y0)+p(x1y0)=1/2+0=1/2p(y1)=∑p(xiy1)=p(x0y1)+p(x1y1)=0+1/6=1/6

p(y2)=∑p(xiy2)=p(x0y2)+p(x1y2)=1/6+1/6=1/3Y的熵X的條件熵同理p(x0/y1)=0，p(x1/y1)=1；p(x0/y2)=1/2，p(x1/y2)=1/2聯(lián)合熵：H(XY)=H(Y)+H(X/Y)=1.8bit/符號(hào)2/1/202356例題分析分析H(X)=0.92bit/符號(hào)未收到任何消息時(shí)，接收者對(duì)X的平均不確定度H(X/Y)=0.33bit/符號(hào)收到消息Y后，接收者對(duì)X的平均不確定度 不確定度的減少量（0.59bit/符號(hào)）就是接收者通過信道傳輸收到的信息量，稱為X和Y的互信息I(X;Y)2/1/202357互信息設(shè)有兩個(gè)隨機(jī)事件X和Y，X是信源發(fā)出的離散符號(hào)集合，Y是信宿收到的離散符號(hào)集合。有擾信道干擾源信源X信宿Y2/1/202358互信息如果信道是無噪的，當(dāng)信源發(fā)出消息xi后，信宿必能準(zhǔn)確無誤地收到該消息，徹底消除對(duì)xi的不確定度，所獲得的信息量就是xi的不確定度I(xi)，即xi本身含有的全部信息?！硐肭闆r一般而言，信道中總是存在著噪聲和干擾，信源發(fā)出消息xi，通過信道后信宿只可能收到由于干擾作用引起的某種變型yj?！獙?shí)際情況信宿收到y(tǒng)j后推測(cè)信源發(fā)出xi的概率p(xi

/yj)稱為后驗(yàn)概率。信源發(fā)出消息xi的概率p(xi)稱為先驗(yàn)概率。2/1/202359互信息事件xi的不確定性用I(xi)度量。接收到符號(hào)yj后，事件xi仍保留的不確定性，用I(xi

/yj)度量。接收到某消息yj后獲得的關(guān)于事件xi的信息量，用I(xi;yj)表示?；バ畔⒌扔诤篁?yàn)概率與先驗(yàn)概率比值的對(duì)數(shù)2/1/202360例題例：設(shè)信源空間為 如果信宿收到消息

y1＝“不是晴天”，求y1分別與xi之間的互信息量。解：自信息量分別為

I(x1)=-logp(x1)=1bitI(x2)=-logp(x2)=2bit

I(x3)=-logp(x3)=3bit I(x4)=-logp(x4)=3bit

y1

無條件概率：p(y1)=1/2

y1和X的聯(lián)合概率：

p(x1y1)=0 p(x2y1)=p(x2)=1/4

p(x3y1)=p(x3)=1/8p(x4y1)=p(x4)=1/8 2/1/202361例題

條件概率為：p(x1/y1)=p(x1y1)/p(y1)=0p(x2/y1)=p(x2y1)/p(y1)=1/2p(x3/y1)=p(x3y1)/p(y1)=1/4p(x4/y1)=p(x4y1)/p(y1)=1/4

互信息量為：

I(x1;y1)=log[p(x1/y1)/p(x1)]=0

I(x2;y1)=log[p(x2/y1)/p(x2)]=1bit

I(x3;y1)=log[p(x3/y1)/p(x3)]=1bit I(x4;y1)=log[p(x4/y1)/p(x4)]=1bit信道傳送的互信息量是用來解除信源符號(hào)的不確定度的。2/1/202362例2-10信源消息二進(jìn)碼字先驗(yàn)概率后驗(yàn)概率收到0后收到01后收到011后x10001/8x20011/8x30101/8x40111/8x51001/8x61011/8x71101/8x81111/800001/41/41/41/40000001/21/2000000012/1/202363互信息的性質(zhì)對(duì)稱性當(dāng)X和Y相互獨(dú)立時(shí)，單符號(hào)間互信息量可為正值或負(fù)值

平均意義上的互信息量一定大于或等于零2/1/202364平均互信息互信息量I(xi;yj)在X集合上的統(tǒng)計(jì)平均值為I(X;yj)在Y集合上的概率加權(quán)統(tǒng)計(jì)平均值平均互信息（量）2/1/202365平均互信息例：某人研究了當(dāng)?shù)氐奶鞖庥涗浐蜌庀笈_(tái)的預(yù)報(bào)記錄后，得到實(shí)際天氣和預(yù)報(bào)天氣的聯(lián)合概率分布，如下表所示。他發(fā)現(xiàn)預(yù)報(bào)只有12/16的準(zhǔn)確率，而只預(yù)報(bào)“明天不下雨”的準(zhǔn)確率卻是13/16。他把這個(gè)想法告訴臺(tái)長(zhǎng)，臺(tái)長(zhǎng)卻說他錯(cuò)了。請(qǐng)問這是為什么？

實(shí)際預(yù)報(bào)下雨不下雨下雨1/83/16不下雨1/1610/162/1/202366平均互信息解：設(shè)X表示實(shí)際天氣情況，Y表示預(yù)報(bào)情況，Z表示“預(yù)報(bào)不下雨”的情況I(X;Y)<<H(X)天氣預(yù)報(bào)確實(shí)不準(zhǔn)I(X;Z)=0總是“預(yù)報(bào)不下雨”不傳遞信息2/1/202367平均互信息量的物理意義H(X/Y)：信道疑義度，損失熵信源符號(hào)通過有噪信道傳輸后引起的信息量損失。信源X的熵等于接收到的信息量加損失掉的信息量。

H(Y/X)：噪聲熵，散布度它反映了信道中噪聲源的不確定性。輸出端信源Y的熵H(Y)等于接收到關(guān)于X的信息量I(X;Y)加上H(Y/X)，這完全是由信道中噪聲引起的。2/1/202368平均互信息量的物理意義如果X與Y是相互獨(dú)立的，無法從Y中去提取關(guān)于X的信息，即H(X/Y)=H(X)，故稱為全損離散信道。如果Y是X的確定的一一對(duì)應(yīng)函數(shù)，I(X;Y)＝H(X)，已知Y就完全解除了關(guān)于X的不確定度，所獲得的信息就是X的不確定度或熵。這可看成無擾離散信道。疑義度H(X/Y)為零，噪聲熵也為零。在一般情況下，X和Y既非相互獨(dú)立，也不是一一對(duì)應(yīng)，那么從Y獲得X的信息必在零與H(X)之間，即常小于X的熵。2/1/202369多變量互信息量符號(hào)xi與符號(hào)對(duì)yjzk之間的互信息量為條件互信息量一個(gè)聯(lián)合事件yjzk出現(xiàn)后提供的有關(guān)xi的信息量zk事件出現(xiàn)后提供的有關(guān)xi的信息量給定zk條件下再出現(xiàn)yj事件后提供的有關(guān)xi的信息量2/1/202370三維聯(lián)合集的平均互信息量2/1/202371數(shù)據(jù)處理中信息的變化X是輸入消息集合，Y是第一級(jí)處理器的輸出消息集合，Z為第二級(jí)處理器的輸出消息集合，假設(shè)在Y條件下X與Z相互獨(dú)立。第一級(jí)處理器第二級(jí)處理器XYZ輸入2/1/202372數(shù)據(jù)處理中信息的變化當(dāng)對(duì)信號(hào)、數(shù)據(jù)或消息進(jìn)行多級(jí)處理時(shí)，每處理一次就有可能損失一部分信息，也就是說數(shù)據(jù)處理會(huì)把信號(hào)、數(shù)據(jù)或消息變成更有用的形式，但是絕不會(huì)創(chuàng)造出新的信息，這就是所謂的信息不增性。2/1/202373數(shù)據(jù)處理中信息的變化編碼信道譯碼UXYV信息經(jīng)過編碼或譯碼處理后均不可能增加，只會(huì)減少從測(cè)量結(jié)果Y中獲得更多關(guān)于X的信息量，常用方法是：增加測(cè)量次數(shù)。測(cè)量Y的次數(shù)越多，X的條件熵越小，獲得的信息量就越大。2/1/202374熵的性質(zhì)非負(fù)性H(X)＝H(x1,x2,……,xn)≥0等號(hào)在p(xi)=1時(shí)成立對(duì)稱性H(x1,x2,……,xn)＝H(x2,x1,……,xn)熵函數(shù)只與隨機(jī)變量的總體結(jié)構(gòu)有關(guān)2/1/202375熵的性質(zhì)確定性H(0,1)＝H(1,0,0,……,0)＝0只要信源符號(hào)集中有一個(gè)符號(hào)的出現(xiàn)概率為1，信源熵就等于零擴(kuò)展性如果集合中有一個(gè)或多個(gè)事件的概率相比于其他事件非常小，這些小概率事件可以忽略不計(jì)。如：編寫詞典2/1/202376熵的性質(zhì)最大熵定理離散無記憶信源輸出M個(gè)不同的信息符號(hào)，當(dāng)且僅當(dāng)各個(gè)符號(hào)出現(xiàn)概率相等時(shí)（即等概率分布），熵最大條件熵小于無條件熵條件熵小于無條件熵兩個(gè)條件的條件熵小于一個(gè)條件的條件熵聯(lián)合熵小于信源熵之和2/1/202377互信息量與熵H(X/Y)H(X)H(Y)H(XY)H(Y/X)I(X;Y)維拉圖2/1/202378第2章信源及信源熵2.1信源的描述和分類2.2離散信源熵和互信息2.3離散序列信源的熵2.4冗余度2.5連續(xù)信源的熵和互信息2/1/202379離散序列信源的熵設(shè)信源輸出的隨機(jī)序列為X

=(X1X2…Xl…XL)序列中的變量Xl∈{x1,x2,…

xn}隨機(jī)序列的概率為式中，2/1/202380離散無記憶信源的序列熵當(dāng)信源無記憶時(shí) 信源的序列熵為2/1/202381離散無記憶信源的序列熵當(dāng)信源平穩(wěn)時(shí)，即與序號(hào)l無關(guān)信源的序列熵可以表示為信源序列中，平均每個(gè)符號(hào)的熵為離散無記憶信源平均每個(gè)符號(hào)的符號(hào)熵HL(X)等于單個(gè)符號(hào)信源的符號(hào)熵H(X)平穩(wěn)、無記憶2/1/202382例題有一個(gè)無記憶信源隨機(jī)變量X∈(0,1)，等概率分布，若以單個(gè)符號(hào)出現(xiàn)為一事件，則此時(shí)的信源熵：如果以兩個(gè)符號(hào)出現(xiàn)(L=2的序列)為一事件，則隨機(jī)序列X∈(00,01,10,11)，信源的序列熵信源的符號(hào)熵為用1比特表示該事件用2比特表示該事件信源序列的符號(hào)熵等于單符號(hào)信源熵2/1/202383例題例：有一離散平穩(wěn)無記憶信源 求：二次擴(kuò)展信源的熵

解：X2信源的元素

a1

a2a3a4a5a6a7a8a9對(duì)應(yīng)的符號(hào)序列

x1x1x1x2x1x3x2x1x2x2x2x3x3x1x3x2x3x3概率p(ai)1/41/81/81/81/161/161/81/161/16信源的序列熵平均每個(gè)符號(hào)的熵單符號(hào)信源熵序列的符號(hào)熵序列信源熵2/1/202384離散有記憶信源的序列熵若信源輸出一個(gè)L長(zhǎng)序列，則信源的序列熵為平均每個(gè)符號(hào)的熵為信源無記憶時(shí)滿足平穩(wěn)時(shí)2/1/202385例題例：已知離散有記憶信源中各符號(hào)的概率空間為: 現(xiàn)信源發(fā)出二重符號(hào)序列消息(ai,aj)，這兩個(gè)符號(hào)的概率關(guān)聯(lián)性用條件概率p(aj/ai)表示，并由下表給出。求信源的序列熵和平均符號(hào)熵。ajaia0a1a2a09/112/110a11/83/41/8a202/97/9ajaia0a1a2a01/41/180a11/181/31/18a201/187/362/1/202386例題解：條件熵

單符號(hào)信源熵 信源的序列熵 平均符號(hào)熵H2(X)<H(X)：符號(hào)序列中的符號(hào)之間存在關(guān)聯(lián)性，導(dǎo) 致符號(hào)的不確定度減小2/1/202387離散平穩(wěn)信源離散平穩(wěn)信源的聯(lián)合概率具有時(shí)間推移不變性即平穩(wěn)信源發(fā)出的符號(hào)序列的概率分布與時(shí)間起點(diǎn)無關(guān)。結(jié)論1：H(XL/XL-1)是L的單調(diào)非增函數(shù)2/1/202388離散平穩(wěn)信源結(jié)論2：HL

(X)≥H(XL/XL-1)結(jié)論3：HL

(X)是L的單調(diào)非增函數(shù)2/1/202389離散平穩(wěn)信源結(jié)論4：當(dāng)L→∞時(shí)，H∞(X)稱為極限熵結(jié)論4在理論上定義了平穩(wěn)離散有記憶信源的極限熵，實(shí)際上如按此公式計(jì)算極限熵是十分困難的。對(duì)于一般離散平穩(wěn)信源，取不太大的L就能得到非常接近H∞(X)的HL(X)，因此實(shí)際應(yīng)用中常取有限L下的條件熵H(XL/XL-1)作為H∞(X)的近似值。2/1/202390馬爾可夫信源在很多信源的輸出序列中，符號(hào)之間的依賴關(guān)系是有限的，信源符號(hào)發(fā)生的概率只與前邊已經(jīng)發(fā)出的若干個(gè)符號(hào)有關(guān)，而與更前面的符號(hào)無關(guān)。為了描述這類信源，除了信源符號(hào)集外還要引入狀態(tài)集。即：信源輸出消息符號(hào)除與符號(hào)本身有關(guān)外，還與信源所處的狀態(tài)有關(guān)。若一個(gè)信源滿足下面兩個(gè)條件，則稱為馬爾可夫信源：某一時(shí)刻信源輸出符號(hào)的概率只與當(dāng)前所處的狀態(tài)有關(guān)，而與以前的狀態(tài)無關(guān)；信源的下一個(gè)狀態(tài)由當(dāng)前狀態(tài)和下一刻的輸出符號(hào)唯一確定。2/1/202391馬爾可夫信源對(duì)于m階馬爾可夫信源X＝(x1,x2,…,xq)，引入符號(hào)條件概率和狀態(tài)轉(zhuǎn)移概率，可以轉(zhuǎn)化為馬爾可夫鏈。令狀態(tài)si

=(xi1xi2…xim)，i1,i2,…,im

∈(1,2,…,q)信源符號(hào)表中的數(shù)目為q，m個(gè)符號(hào)組成的狀態(tài)si共有Q=qm種，這些序列組成狀態(tài)集 S={s1,s2,…,sQ}例：二元序列為…01011100…，若m=2，則Q=qm=22=4，即s1=00s2=01s3=10s4=11 對(duì)應(yīng)的狀態(tài)序列為：…s2s3s2s4s4s3s1…2/1/202392馬爾可夫信源符號(hào)條件概率信源在某一時(shí)刻出現(xiàn)符號(hào)xj的概率與信源此時(shí)所處的狀態(tài)si有關(guān)，用條件概率表示為p(xj/si)i=1,2,…,Q

j=1,2,…,q狀態(tài)轉(zhuǎn)移概率當(dāng)信源符號(hào)xj出現(xiàn)后，信源所處的狀態(tài)將發(fā)生變化，并轉(zhuǎn)入一個(gè)新的狀態(tài)。這種狀態(tài)的轉(zhuǎn)移可用狀態(tài)轉(zhuǎn)移概率表示2/1/202393轉(zhuǎn)移概率矩陣若信源處于某一狀態(tài)si，當(dāng)發(fā)出一個(gè)符號(hào)后，所處狀態(tài)就改變了。任何時(shí)候信源處于什么狀態(tài)完全由前一時(shí)刻的狀態(tài)和發(fā)出的符號(hào)決定。系統(tǒng)在任一時(shí)刻可處于狀態(tài)空間S={s1,s2,…,sQ}中的任意一個(gè)狀態(tài)，狀態(tài)轉(zhuǎn)移時(shí)的轉(zhuǎn)移概率矩陣矩陣中第i行元素對(duì)應(yīng)于從某一個(gè) 狀態(tài)si轉(zhuǎn)移到所有狀態(tài)sj的轉(zhuǎn)移概率第j列元素對(duì)應(yīng)于從所有狀態(tài)si轉(zhuǎn)移到同一狀態(tài)sj的轉(zhuǎn)移概率符號(hào)條件概率矩陣2/1/202394馬爾可夫信源一步轉(zhuǎn)移概率（基本轉(zhuǎn)移概率）Pij(m,n)中n=m+1，即Pij(m,m+1)，記為Pij(m)pij(m)=p{Sm+1=sj/Sm=si}=p(sj/si)齊次馬爾可夫鏈其轉(zhuǎn)移概率具有推移不變性，即只與狀態(tài)有關(guān)，與時(shí)刻m無關(guān)pij(m)=p{Sm+1=sj/Sm=si}=p(S2=sj/S1=si)=pij性質(zhì)：2/1/202395齊次馬爾可夫鏈切普曼－柯爾莫郭洛夫方程k步轉(zhuǎn)移概率與l(l<k)步和(k-l)步轉(zhuǎn)移概率之間的關(guān)系當(dāng)l＝1時(shí)，若用矩陣表示，齊次馬爾可夫鏈的一步轉(zhuǎn)移概率完全決定了k步轉(zhuǎn)移概率2/1/202396狀態(tài)轉(zhuǎn)移圖（香農(nóng)線圖）齊次馬爾可夫鏈可以用其狀態(tài)轉(zhuǎn)移圖（香農(nóng)線圖）表示每個(gè)圓圈代表一種狀態(tài)

狀態(tài)之間的有向線代表從某一狀態(tài)向另一狀態(tài)的轉(zhuǎn)移有向線一側(cè)的符號(hào)和數(shù)字分別代表發(fā)出的符號(hào)和條件概率sos1x2/0.6x1/0.3x1/0.4s2x2/0.2x1/0.8x2/0.7p(x1/s2)=0.8p(s2/s2)=0.82/1/202397例題例：設(shè)有一個(gè)二進(jìn)制二階馬爾可夫信源，信源符號(hào)集為{0,1}，條件概率為 繪制該信源的狀態(tài)轉(zhuǎn)移圖。S1=00S2=01S3=10S4=11s1s2s3s40/0.81/0.20/0.51/0.50/0.51/0.50/0.21/0.8狀態(tài)轉(zhuǎn)移矩陣符號(hào)條件概率矩陣2/1/202398例題例：如圖所示是一個(gè)相對(duì)碼編碼器。輸入的碼Xr(r=1,2,…)是相互獨(dú)立的，取值0或1，且已知p(X=0)=p,p(X=1)=1－p=q，輸出的碼是Yr，顯然 Yr是一個(gè)一階馬氏鏈，Yr確定后，Yr+1概率分布只與Yr有關(guān)，與Yr-1、Yr-2…等無關(guān) p00=p(Y2=0/Y1=0)=p(X=0)=p p01=P(Y2=1/Y1=0)=p(X=1)=q p10=P(Y2=0/Y1=1)=p(X=1)=q p11=p(Y2=1/Y1=1)=p(X=0)=pTXrYr＋01pqqp2/1/202399穩(wěn)定的馬爾可夫信源不可約性對(duì)任意一對(duì)i和j，都存在至少一個(gè)k，使pij(k)＞0若對(duì)所有k，pij(k)＝0，意味著一旦出現(xiàn)狀態(tài)si就不再可能到達(dá)狀態(tài)sj，無法各態(tài)遍歷非周期性所有pij(n)＞0的n中沒有比1大的公因子非不可約馬氏鏈周期性馬氏鏈2/1/2023100馬爾可夫信源遍歷性的直觀意義不論質(zhì)點(diǎn)從哪一個(gè)狀態(tài)si出發(fā)，當(dāng)轉(zhuǎn)移步數(shù)k足夠大時(shí)，轉(zhuǎn)移到sj的概率pij(k)都近似等于某個(gè)常數(shù)Wj 即：如果轉(zhuǎn)移步數(shù)k充分大，就可以用常數(shù)Wj作為k步轉(zhuǎn)移概率pij(k)的近似值平穩(wěn)馬爾可夫信源的含義經(jīng)過足夠長(zhǎng)時(shí)間之后，信源的每種狀態(tài)出現(xiàn)的概率逐漸穩(wěn)定下來，不再發(fā)生變化。狀態(tài)的穩(wěn)定分布與初始狀態(tài)無關(guān)，即無論信源一開始處在什么狀態(tài)，最終都將達(dá)到同樣的穩(wěn)定分布。2/1/2023101初始狀態(tài)的影響初始狀態(tài)狀態(tài)序列符號(hào)序列信源分布00000000000202222002202210100111122331101123101123非平穩(wěn)2/1/2023102穩(wěn)定的馬爾可夫信源極限概率Wj一個(gè)不可約的、非周期的、狀態(tài)有限的馬爾可夫鏈，其k步轉(zhuǎn)移概率pij(k)在k→∞時(shí)趨于一個(gè)和初始狀態(tài)無關(guān)的概率，即不論起始狀態(tài)如何，這種馬氏鏈都可以最后達(dá)到穩(wěn)定。平穩(wěn)分布Wj可用下列方程組求得2/1/2023103例題例：有一個(gè)二元二階馬爾可夫信源，信源符號(hào)集為{0,1},狀態(tài)變量S={00,01,10,11}。已知符號(hào)條件概率：

p(0/00)=1/2 p(1/00)=1/2

p(0/01)=1/3 p(1/01)=2/3

p(0/10)=1/4 p(1/10)=3/4

p(0/11)=1/5 p(1/11)=4/5求：⑴信源全部狀態(tài)及狀態(tài)轉(zhuǎn)移概率 ⑵畫出完整的二階馬爾可夫信源狀態(tài)轉(zhuǎn)移圖。