第2章信源與信源熵

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

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

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

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

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

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

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

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

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

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

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

個等概率的可能組合

I=－log2(1/2m)=mbit2m2/1/202332自信息量例：英文字母中“e”出現(xiàn)的概率為0.105，“c”出現(xiàn)的概率為0.023，“z”出現(xiàn)的概率為0.001。分別計算它們的自信息量。解：“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)是非負值當p(xi)=1時，I(xi)=0當p(xi)=0時，I(xi)=∞I(xi)是先驗概率p(xi)的單調(diào)遞減函數(shù)，即當p(x1)＞p(x2)時，I(x1)＜I(x2)兩個獨立事件的聯(lián)合信息量等于它們分別的信息量之和。即：統(tǒng)計獨立信源的信息量等于它們分別的信息量之和。2/1/202334聯(lián)合自信息量兩個消息xi，yj同時出現(xiàn)的聯(lián)合自信息量當xi,yj相互獨立時，有p(xi

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

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

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

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

p(xi)為零。2/1/202339離散信源熵H(X)信源熵的物理含義表示信源輸出前信源的平均不確定性表示信源輸出后每個符號所攜帶的平均信息量例：有兩個信源，其概率空間分別為H(Y)>H(X)：信源Y比信源X的平均不確定性要大2/1/202340離散信源熵H(X)例：電視屏上約有個格點，按每點有10個不同的灰度等級考慮，則共能組成個不同的畫面。按等概率計算，平均每個畫面可提供的信息量為2/1/202341離散信源熵H(X)例：有一篇千字文章，假定每字可從萬字表中任選，則共有不同的千字文N=100001000=104000篇，仍按等概計算，平均每篇千字文可提供的信息量為Apictureisworthathousandwords2/1/202342離散信源熵H(X)例：信源X輸出符號只有兩個，設為0和1。輸出符號發(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ù)曲線如圖所示：如果二元信源的輸出符號是確定的,即p=1或q=1,則該信源不提供任何信息。當二元信源符號0和1以等概率發(fā)生時,信源熵達到極大值,等于1比特信息量。p=1p=q=0.52/1/202344條件熵在給定yj條件下，xi的條件自信息量為I(xi/yj)，X集合的條件熵在給定Y（即各個yj）條件下，X集合的條件熵在給定X（即各個xi）條件下，Y集合的條件熵條件熵是在聯(lián)合符號集合XY上的條件自信息量的聯(lián)合概率加權(quán)統(tǒng)計平均值。2/1/202345條件熵例：考慮下面兩個隨機變量X和Y，其中

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

2/1/202346聯(lián)合熵聯(lián)合熵是聯(lián)合符號集合XY上的每個元素對xiyj的自信息量的概率加權(quán)統(tǒng)計平均值聯(lián)合熵H(XY)表示X和Y同時發(fā)生的不確定度。聯(liá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)比特/符號比特/符號比特/符號2/1/202349例題例：二進制通信系統(tǒng)用符號“0”和“1”，由于存在失真，傳輸時會產(chǎn)生誤碼，用符號表示下列事件：

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

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

p(u0)＝1/2，p(v0/u0)＝3/4，p(v0/u1)=1/2。求：⑴已知發(fā)出一個“0”，求收到符號后得到的信息量；⑵已知發(fā)出的符號，求收到符號后得到的信息量；⑶知道發(fā)出的和收到的符號，求能得到的信息量；⑷已知收到的符號，求被告知發(fā)出的符號得到的信息量。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例題例：一個二進制信源X發(fā)出符號集{0,1}，經(jīng)過離散無記憶信道傳輸，信道輸出用Y表示。由于信道中存在噪聲，接收端除收到0和1的符號外，還有不確定符號，用“2”表示。已知X的先驗概率為:p(x0)=2/3，p(x1)=1/3符號轉(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/符號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/符號2/1/202356例題分析分析H(X)=0.92bit/符號未收到任何消息時，接收者對X的平均不確定度H(X/Y)=0.33bit/符號收到消息Y后，接收者對X的平均不確定度 不確定度的減少量（0.59bit/符號）就是接收者通過信道傳輸收到的信息量，稱為X和Y的互信息I(X;Y)2/1/202357互信息設有兩個隨機事件X和Y，X是信源發(fā)出的離散符號集合，Y是信宿收到的離散符號集合。有擾信道干擾源信源X信宿Y2/1/202358互信息如果信道是無噪的，當信源發(fā)出消息xi后，信宿必能準確無誤地收到該消息，徹底消除對xi的不確定度，所獲得的信息量就是xi的不確定度I(xi)，即xi本身含有的全部信息?！硐肭闆r一般而言，信道中總是存在著噪聲和干擾，信源發(fā)出消息xi，通過信道后信宿只可能收到由于干擾作用引起的某種變型yj?！獙嶋H情況信宿收到y(tǒng)j后推測信源發(fā)出xi的概率p(xi

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

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

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信道傳送的互信息量是用來解除信源符號的不確定度的。2/1/202362例2-10信源消息二進碼字先驗概率后驗概率收到0后收到01后收到011后x10001/8x20011/8x30101/8x40111/8x51001/8x61011/8x71101/8x81111/800001/41/41/41/40000001/21/2000000012/1/202363互信息的性質(zhì)對稱性當X和Y相互獨立時，單符號間互信息量可為正值或負值

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

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

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

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

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

解：X2信源的元素

a1

a2a3a4a5a6a7a8a9對應的符號序列

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

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

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

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

j=1,2,…,q狀態(tài)轉(zhuǎn)移概率當信源符號xj出現(xiàn)后，信源所處的狀態(tài)將發(fā)生變化，并轉(zhuǎn)入一個新的狀態(tài)。這種狀態(tài)的轉(zhuǎn)移可用狀態(tài)轉(zhuǎn)移概率表示2/1/202393轉(zhuǎn)移概率矩陣若信源處于某一狀態(tài)si，當發(fā)出一個符號后，所處狀態(tài)就改變了。任何時候信源處于什么狀態(tài)完全由前一時刻的狀態(tài)和發(fā)出的符號決定。系統(tǒng)在任一時刻可處于狀態(tài)空間S={s1,s2,…,sQ}中的任意一個狀態(tài)，狀態(tài)轉(zhuǎn)移時的轉(zhuǎn)移概率矩陣矩陣中第i行元素對應于從某一個 狀態(tài)si轉(zhuǎn)移到所有狀態(tài)sj的轉(zhuǎn)移概率第j列元素對應于從所有狀態(tài)si轉(zhuǎn)移到同一狀態(tài)sj的轉(zhuǎn)移概率符號條件概率矩陣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)有關，與時刻m無關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)移概率之間的關系當l＝1時，若用矩陣表示，齊次馬爾可夫鏈的一步轉(zhuǎn)移概率完全決定了k步轉(zhuǎn)移概率2/1/202396狀態(tài)轉(zhuǎn)移圖（香農(nóng)線圖）齊次馬爾可夫鏈可以用其狀態(tài)轉(zhuǎn)移圖（香農(nóng)線圖）表示每個圓圈代表一種狀態(tài)

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

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)移圖。