1、第2章 離散信源及其信息度量,本章內(nèi)容,2.1 信源的分類及描述 2.2 信源的數(shù)學(xué)模型 2.3 信息度量和信源熵 2.4信源熵的基本性質(zhì)和定理 2.5 離散無記憶擴展信源 2.6 離散平穩(wěn)信源 2.7 馬爾可夫信源 2.8 信源的相關(guān)性和剩余度,2.1 信源的分類及描述,信源：是發(fā)出消息的源，信源的輸出的是以符號形式出現(xiàn)的具體消息。,1）信源只輸出一個消息符號 按信源發(fā)出的消息在時間和幅度上的分布來分類： 離散信源：符號集的取值是有限的。 連續(xù)信源：符號集的取值是無限的，即取值是連續(xù)的。,2）信源輸出一系列符號序列 按信源發(fā)出的符號之間的關(guān)系來分類： 無記憶信源：信源發(fā)出的一個個消息符號彼此

2、統(tǒng)計獨立。 有記憶信源：信源發(fā)出的各消息符號之間有關(guān)聯(lián)（比如馬爾可夫信源）。,按信源的概率分布與時間起點的關(guān)系來分類： 平穩(wěn)信源 非平穩(wěn)信源,2.2 信源的數(shù)學(xué)模型,1、單符號離散信源的數(shù)學(xué)模型,2.3 離散信源信息的度量與信源熵,任何一個物理量的定義都應(yīng)當(dāng)符合客觀規(guī)律和邏輯上的合理性，信息的度量也不例外。直觀經(jīng)驗告訴我們： 消息中的信息量與消息發(fā)生的概率密切相關(guān)：出現(xiàn)消息出現(xiàn)的可能性越小，則消息攜帶的信息量就越大。 如果事件發(fā)生是必然的（概率為1），則它含有的信息量應(yīng)為零。如果一個幾乎不可能事件發(fā)生了（概率趨于0），則它含有巨大的信息量。 如果我們得到不是由一個事件而是由若干個獨立事件構(gòu)成的

3、消息，那么我們得到的信息量就是若干個獨立事件的信息量的總和。,一、自信息量I(xi)和信息熵H(X),它的單位取決于上式中對數(shù)的底數(shù)a， 如果取對數(shù)的底a=2，則信息量的單位為比特（bit）， 如果取對數(shù)的底a=e，則信息量的單位為奈特（nat）， 如果取對數(shù)的底a=10，則信息量的單位為哈特（Hart）,例： 已知二元信源輸出“0”、“1”兩種符號， （1）如果“0”、“1”出現(xiàn)概率相等，計算出現(xiàn)“0”的信息量； （2）如果“0”出現(xiàn)概率為1/3，計算出現(xiàn)“1”的信息量。 解：根據(jù)信息量的定義式，可以得到,自信息量的性質(zhì)：,1）非負(fù)性。,2) 單調(diào)遞減性。,3) 可加性。,2、平均自信息量H

4、(X),是一個隨機變量，它不能用來作為整個信源的信息度量。這樣，我們引入平均自信息量來表述信源輸出消息的不肯定性。,如果一個離散信源輸出的消息符號集合為,信源輸出的消息符號不同，所含有的信息量就不相同，因此，自信息量,平均自信息量又稱為信源熵、信息熵 或無條件熵。,平均信息量可以表示為：,2、平均自信息量H(X),1）單位：它的常用單位為bit/符號。,2）性質(zhì) H(X)非負(fù)：H(X)0 等號成立的充要條件是當(dāng)且僅當(dāng)對某i，pi=1，其余pk=0(ki) 可見：確定信源的熵等于0。,最大熵出現(xiàn)在等概情況下。,例題：設(shè)有一個三進(jìn)制信源，每個符號發(fā)生的概率分別為p(x1)=1/2，p(x2)=p(

5、x3)=1/4. 試計算： 符號x1包含的信息量為多少？ 信源中每個符號平均包含的信息量？ 信源每分鐘輸出3600個符號，通過理想信道傳輸，收信者每秒鐘接收到多少信息量？,解：H(X)=H(1/2,1/4,1/4)=1.5bit/符號,等概時（p=0.5)：隨機變量具有最大的不確定性 p=0或1時：隨機變量的不確定性消失。,例題：二元信源，每個符號發(fā)生的概率分別為p(x1)=p，p(x2)=1-p. 試計算信源熵，并畫出熵函數(shù)H(p)和p的曲線圖。,信息熵的物理意義 1）表示了信源輸出前，信源的平均不確定性。 2）表示了信源輸出后，每個消息或符號所提供的平均信息量。 3）信息熵反映了變量X的隨

6、機性。,二、聯(lián)合自信息量I(xi,yj)和聯(lián)合熵H(X,Y),物理意義：一對元素（xi，yj）所含的信息量。,物理意義：每對元素（xi，yj）所含的平均信息量。,例題：聯(lián)合符號集合（X，Y）上的每個元素對的聯(lián)合概率如下，試計算： 符號對（x1，y2)包含的信息量為多少？ 聯(lián)合信源中平均每個符號對所包含的信息量？,解： I(x1,y2)=-log0.25=2bit H（X，Y）=H（0.25,0.25,0.25,0.25）=2bit/符號對,思考： 如何計算三個元素（xi,yj,zk）所含的信息量？ 聯(lián)合信源（X，Y，Z）平均每組符號包含的信息量？ 更多元素包含的信息量？,三、條件自信息量I(x

7、i/yj)和條件熵H(X/Y),性質(zhì)： 非負(fù) 當(dāng)且僅當(dāng)p(xi/yj)=1時，I(xi/yj)=0 I(xi,yj)=I(yj)+I(xi/yj),物理意義： 表示在yj已知的條件下，出現(xiàn)符號xi所提供的信息量。 表示在給定yj條件下，仍對符號xi是否出現(xiàn)存在的不確定性。 如果信道輸入為xi，信道輸出為yj。 條件自信息量 表示收到消息yj之后，收信者仍對發(fā)送信源消息xi存在的不肯定性。 收信者通過信道傳輸收到y(tǒng)j得到關(guān)于xi的信息量 I(xi；yj)=I(xi)-I(xi/yj),H(X/Y)性質(zhì)：非負(fù) H(X,Y)=H(Y)+H(X/Y)=H(X)+H(Y/X),2、條件熵,當(dāng)X表示信道輸

8、入，Y表示信道輸出時，H(X/Y)表示信道損失，表示信宿收到Y(jié)后，對信源X仍然存在的不確定性，所以它又稱為信道疑義度.,物理意義：,P（x=0）=2/3，信道模型如圖所示。,解：,（3）已知發(fā)出的和收到的符號，求能得到的信息量。 （4）已知收到的符號，求被告知發(fā)出的符號得到的信息量。,例題：二進(jìn)制通信系統(tǒng)等概使用符號0和1，由于存在失真，傳輸時會產(chǎn)生誤碼，無記憶信道模型如下。試計算（1）已知發(fā)出一個0，求收到符號后得到的信息量。（2）已知發(fā)出的符號，求收到符號后得到的信息量。,解：,四、各種熵的關(guān)系,1) H(X,Y)=H(X)+H(Y/X)=H(Y)+H(X/Y) H(X,Y)H(X)+H(

9、Y); X和Y統(tǒng)計獨立時，取等號。 H(X/Y) H(X) ; X和Y統(tǒng)計獨立時，取等號。 條件熵總是小于或等于無條件熵。,例題,已知兩個獨立的隨機變量x、y的分布律如下，計算,計算H（X）、 H（Z）、 H（X/Y）、 H（XY）、 H（YZ）,五、互信息和平均互信息,3、平均互信息量（詳見第3章）,當(dāng)信道輸入用X表示，信道輸出用Y表示，則 條件熵H（X/Y）稱為信道損失或者疑義度。,物理意義：收信者收到一個消息后所獲得的平均信息量。,例題：二進(jìn)制通信系統(tǒng)等概使用符號0和1，由于存在失真，傳輸時會產(chǎn)生誤碼，無記憶信道模型如下。試計算（1）H（X）、H（Y）、H（X，Y）、H（X/Y）、H（Y

10、/X）。 （2）信宿收到一個符號后得到關(guān)于信源的平均信息量。,2.4 信息熵的基本性質(zhì),熵函數(shù)的性質(zhì):,2.5離散無記憶的擴展信源,1、離散無記憶擴展信源的定義,2、離散無記憶擴展信源的熵,序列熵：（單位為bit/序列）,平穩(wěn)序列中平均每個符號的熵為： （單位為bit/符號）,離散無記憶信源的序列熵（離散無記憶擴展信源熵）,總 結(jié)：,例題：,某一無記憶信源的符號集為0，1，已知p(0)=1/4, p(1)=3/4。 （1）求符號的平均熵； （2）由100個符號構(gòu)成的序列，求某一特定序列（例如有m個0和100-m個1）的自信息量的表達(dá)式； （3）計算（2）中的序列的熵。,解：（1）因為信源是無記

11、憶信源，所以符號的平均熵,（2）某一特定序列（例如：m個0和100-m個1）出現(xiàn)的概率為,所以，自信息量為,（3）序列的熵,2.6 離散平穩(wěn)信源,一般來說，信源輸出的隨機序列的統(tǒng)計特性比較復(fù)雜，分析起來也比較困難。為了便于分析，我們假設(shè)信源輸出的是平穩(wěn)的隨機序列，也就是序列的統(tǒng)計性質(zhì)與時間的推移無關(guān)。很多實際信源也滿足這個假設(shè)。,2、序列中平均每個符號的熵（即平均符號熵）為：,1、序列熵（單位為bit/序列）,二、離散平穩(wěn)信源的序列熵,當(dāng)N=2時，可以證明,3、關(guān)于“離散平穩(wěn)信源”的幾個結(jié)論,例如：,例如：,即：當(dāng)N給定時，平均符號熵不小于條件熵。,推廣結(jié)論3可得：,4、實際應(yīng)用中如何計算極限

12、熵？,特別地，如果信源序列只是前后兩個符號之間有關(guān)聯(lián)性，則極限熵為,實際極限熵的近似值：,對于一般的平穩(wěn)信源，按定義式來計算極限熵很困難。,1）有限N下的條件熵,2）有限N下的平均符號熵,思考的問題,寫出離散平穩(wěn)信源的序列熵和平均符號熵的計算式。它們是否適用于離散無記憶信源？ 極限熵的含義是什么？當(dāng)消息符號只與前面m個符號有依賴關(guān)系，而與更前面發(fā)出的符號無依存關(guān)系時，此時的極限熵如何表達(dá)？,2.7 馬爾可夫信源,實際中信源發(fā)出的消息符號往往只與前面若干個（比如m個）符號有較強的依賴關(guān)系，而與更前面發(fā)出的符號依存關(guān)系較弱，為此可限制隨機序列的記憶長度（m+1），稱為有限記憶信源（即階馬爾可夫信源

13、）。,一、馬爾可夫信源（即：有限記憶長度信源）,m階馬爾可夫信源,將該時刻以前出現(xiàn)的m個符號組成的序列定義為狀態(tài)Ei,當(dāng)信源符號xj出現(xiàn)后，信源所處的狀態(tài)將發(fā)生變化，轉(zhuǎn)入一個新的狀態(tài)，可用狀態(tài)轉(zhuǎn)移概率 來表示。馬爾可夫信源可用狀態(tài)轉(zhuǎn)移概率來描述, 也可以用狀態(tài)轉(zhuǎn)移圖來表示。,例題：有一個二階馬爾科夫鏈X 0，1，其條件概率如下表所示，狀態(tài)變量E=00，01，10，11,可得狀態(tài)的一步轉(zhuǎn)移概率,信源在Ei狀態(tài)下輸出符號ak的條件概率：,狀態(tài)轉(zhuǎn)移圖？,1. 馬爾可夫特性(無后效性) 已知系統(tǒng)的現(xiàn)在狀態(tài)，那么系統(tǒng)的將來與過去無關(guān)。,2. 馬爾可夫信源 某一時刻信源輸出的符號只與此刻信源所處的狀態(tài)有關(guān)

14、，而與以前的狀態(tài)和以前的輸出符號無關(guān)。 信源在某一時刻所處的狀態(tài)只由當(dāng)前輸出的符號和前一時刻信源的狀態(tài)唯一決定。,3.馬爾可夫信源的狀態(tài)轉(zhuǎn)移概率,性質(zhì),在 時刻系統(tǒng)處于狀態(tài)i的條件下，在下一時刻系統(tǒng)處于狀態(tài)j的條件概率,一步：,性質(zhì)：,k步：,平穩(wěn)信源的概率分布特性具有時間推移不變性，而齊次馬爾可夫鏈只要求轉(zhuǎn)移概率具有推移不變性，因此，一般說來，平穩(wěn)包含齊次；但齊次不包含平穩(wěn)。,4、 齊次馬爾可夫鏈,如果狀態(tài)轉(zhuǎn)移概率具有時間推移不變性，則此信源稱為齊次馬爾可夫信源。,1)轉(zhuǎn)移概率,2）轉(zhuǎn)移概率矩陣,一步轉(zhuǎn)移概率矩陣,性質(zhì)：每個元素非負(fù)，每行之和為1。,k步轉(zhuǎn)移概率矩陣,4）如何確定無條件概率

15、？,說明：確定該概率，齊次馬爾可夫鏈需要知道初始概率和轉(zhuǎn)移概率。,5. 齊次遍歷馬爾可夫信源,如果齊次馬爾可夫信源還滿足遍歷性，即當(dāng)轉(zhuǎn)移步數(shù)足夠大時，達(dá)到平穩(wěn)分布后，狀態(tài)概率與起始狀態(tài)無關(guān)，就稱該信源為齊次遍歷馬爾可夫信源。,穩(wěn)態(tài)分布：不管起始狀態(tài)Ei是什么，馬爾可夫鏈最后達(dá)到穩(wěn)態(tài)。,如何計算齊次遍歷馬爾可夫鏈的狀態(tài)極限概率？,求解方程組：,符號的極限概率？,m階馬爾可夫信源 記憶長度為m+1的有限記憶信源，稱為m階馬爾可夫信源。 將該時刻以前出現(xiàn)的m個符號組成的序列定義為狀態(tài)Si,狀態(tài)轉(zhuǎn)移概率,符號條件概率,穩(wěn)態(tài)后的符號的極限概率：,復(fù) 習(xí),如何計算m階齊次遍歷的馬爾可夫鏈的極限概率？,例題

16、：有一個二階馬爾科夫鏈X 0，1，其條件概率如下表所示，狀態(tài)變量E=00，01，10，11,計算： （1）穩(wěn)定后的狀態(tài)概率分布； （2）穩(wěn)定后的符號概率分布。,P（ak|Ei）,P（Ej|Ei）,對于m階馬爾科夫信源，極限熵為,復(fù)習(xí)：極限熵的定義,二、m階齊次遍歷的馬爾可夫鏈的極限熵,概率 是馬爾可夫鏈的狀態(tài)的極限概率。,條件熵函數(shù) 表示信源處于某一狀態(tài) 時， 發(fā)出一個消息符號的平均不確定性。,其中，,2）m階齊次遍歷的馬爾可夫鏈的極限熵,m階齊次遍歷的馬爾可夫鏈的極限熵,特殊地，對于一階馬爾可夫鏈的極限熵,一階馬爾可夫信源的狀態(tài)空間Ei就等于信源符號集ai,1、根據(jù)狀態(tài)轉(zhuǎn)移圖，寫出一步轉(zhuǎn)移概

17、率矩陣，計算信源所處狀態(tài)的穩(wěn)態(tài)分布；,時齊遍歷的馬爾可夫信源極限熵的求解步驟,3、計算信源的極限熵。,一階馬爾可夫信源的狀態(tài)空間Si就等于信源符號集ai,例題：有一個二階馬爾科夫鏈X 0，1，其條件概率如下表所示，狀態(tài)變量S=00，01，10，11,計算馬爾可夫信源的極限熵。,P（ak|Ei）,P（Ej|Ei）,例題：,一階馬爾可夫信源，狀態(tài)空間就等于信源符號集合a,b,c,其狀態(tài)轉(zhuǎn)移圖為,解：由狀態(tài)轉(zhuǎn)移圖可知：該馬爾可夫鏈具有遍歷性，平穩(wěn)后狀態(tài)的極限分布存在。一步轉(zhuǎn)移矩陣為,可得方程組,解方程組得到各狀態(tài)的穩(wěn)態(tài)分布概率,因為信源為一階馬爾可夫信源，所以信源的熵,（2）,例題：,2.8 信源的

18、相關(guān)性和剩余度,冗余度也稱為多余度或剩余度。如果一個消息所包含的符號比表達(dá)這個消息所需要的符號多，那么這樣的消息就存在冗余度。,當(dāng)信源輸出符號間彼此不存在依賴關(guān)系且為等概分布時，信源實際熵就為最大熵H0。,冗余度來自兩個方面：一是信源符號間的相關(guān)性。信源輸出符號間的依賴關(guān)系使得信源熵減小，相關(guān)程度越大，則信源的實際熵越小。二是信源符號分布的不均勻性，當(dāng)?shù)雀怕史植紩r，信源熵最大。,為了衡量信源符號間的依賴程度，我們把離散平穩(wěn)有記憶信源的極限熵（實際熵）與把這個信源當(dāng)作離散無記憶等概信源達(dá)到最大熵值的比值，定義為這個離散平穩(wěn)有記憶信源的相對熵率 。 1減去相對熵率所得之差定義為離散平穩(wěn)有記憶信源的剩余度 。,H1H0是由于各個符號出現(xiàn)的概率不均勻， H3H2H1表示信源的記憶長度越