多符號離散信源的熵.ppt

1、1,第2章 信源熵 相比一張哈弗大學(xué)的文憑，養(yǎng)成良好的習(xí)慣對一個人的成功更重要。 比爾.蓋茨,2,本章主要內(nèi)容,2.1單符號離散信源 2.2多符號離散平穩(wěn)信源及熵 2.3連續(xù)信源及熵,3,本節(jié)教學(xué)內(nèi)容、基本要求,1、教學(xué)內(nèi)容 多符號離散序列信源及其熵 馬爾可夫信源及其熵 信息的冗余度 2、基本要求 掌握多符號離散序列信源熵的定義、性質(zhì) 掌握馬爾可夫信源熵的模型及其計算 掌握信息冗余度的含義,4,2.2 多符號離散平穩(wěn)信源及熵,實際的信源輸出的消息是時間或空間上離散的一系列隨機變量。這類信源每次輸出的不是一個單個的符號，而是一個符號序列。 如電報系統(tǒng)。 在信源輸出的序列中，每一位出現(xiàn)哪個符號都是

2、隨機的，這種信源稱為多符號離散信源。 二元系統(tǒng)中，我們可以把兩個二元數(shù)字看成一組，會出現(xiàn)四種可能情況：00、01、10和11，我們可以把這四種情況看成一個新的信源稱為二元無記憶信源的二次擴(kuò)展信源; 相應(yīng)的，如果把N個二元數(shù)字看成一組，則新的信源稱為二元無記憶信源的N次擴(kuò)展信源。,5,如信源序列：000、001、.111 稱為二元信源的3次擴(kuò)展信源。 二元信源的N次擴(kuò)展信源： n元信源的N次擴(kuò)展信源（多符號離散信源）的定義： 輸出消息長度為N，消息中的每個符號取自集合X，X中有n個單符號消息，則X的N次擴(kuò)展信源記作：XN，用N維矢量表示：,N位,則該信源XN最多有nN條消息。,6,平穩(wěn)隨機序列：

3、 所謂平穩(wěn)是指序列的統(tǒng)計性質(zhì)與時間的推移無關(guān)。 非平穩(wěn)隨機序列：信源每發(fā)一個符號的概率與時間起點有關(guān)。 離散無記憶信源：信源序列的前后符號之間是統(tǒng)計獨立的。 離散有記憶信源：信源序列的前后符號之間是相關(guān)的。,7,序列信息的熵,序列信息的熵（也稱：離散無記憶信源的N次擴(kuò)展信源的熵） 原始信源X的數(shù)學(xué)模型 XN的數(shù)學(xué)模型：,8,H(XN)=NH(X) 證明：略 例2.2.1：p40頁 求一個信源的二次擴(kuò)展信源及其熵。 注意：單位,9,離散平穩(wěn)有記憶信源的N次擴(kuò)展信源的熵,離散平穩(wěn)有記憶信源的N次擴(kuò)展信源的熵 離散有記憶信源的N次擴(kuò)展信源：信源輸出的符號相關(guān)，且相關(guān)性用N個符號間的聯(lián)合概率表示。 離

4、散平穩(wěn)有記憶信源的N次擴(kuò)展信源（記憶長度為N）的熵滿足：,10,例2.2.2：p44,設(shè)某二維離散信源X2=X1X2的原始信源X的模型為 符號間的相關(guān)性用以下的條件概率（轉(zhuǎn)移概率）表示： 求原始信源熵H(X),條件熵H(X2|X1)，二次擴(kuò)展信源熵及其平均符號熵。,11,解：,12,將計算結(jié)果代入上式： 1.2061.542 驗證說明計算結(jié)果符合以上公式。 說明：多符號消息的平均符號熵=原始單符號信源熵。這是由于符號之間的統(tǒng)計相關(guān)性造成的。 要想提高信源對外提供的平均符號信息量，必須設(shè)法消除符號之間的相關(guān)性（冗余度）。,13,N維離散有記憶信源的極限熵,（也稱為：離散平穩(wěn)有記憶信源的N次擴(kuò)展信

5、源的極限熵）,極限熵：平均符號熵的N取極限值，即原始信源不斷發(fā)符號，符號間的統(tǒng)計關(guān)系延伸到無窮。 極限熵:代表一般離散平穩(wěn)有記憶信源平均每發(fā)一個符號提供的信息量。,14,15,馬爾可夫信源的極限熵,在許多信源的輸出序列中，符號之間的依賴關(guān)系是有限的。 即：任何時刻信源符號發(fā)生的概率只與前面已經(jīng)發(fā)出的若干符號相關(guān)，而與更前面發(fā)出的符號無關(guān)。 如：隨機變量序列中， (m+1)時刻發(fā)出的隨機變量Xm+1只和前面已經(jīng)發(fā)出的m個隨機變量X1 X2 Xm有關(guān)，而與更前面的隨機變量無關(guān)。 Xi取值于單符號信源符號集合X 這類信源稱為m階馬爾可夫信源。 m階馬爾可夫信源每次只發(fā)一個符號，每次發(fā)出的符號只與之前

6、發(fā)出的m 個符號相關(guān)。,16,馬爾可夫信源的組成需要兩個條件： （1）某時刻信源輸出的符號只與之前的m個符號相關(guān)，這m個相關(guān)的符號稱為”信源前一時刻所處的狀態(tài)”。 m階馬爾可夫信源在時刻i發(fā)符號,17,18,（2）某時刻信源所處的狀態(tài)由該時刻輸出的符號和前一時刻的狀態(tài)唯一確定。,問：m階馬爾可夫信源最多有多少種狀態(tài)？,nm,所有的狀態(tài)構(gòu)成狀態(tài)空間S，每種狀態(tài)以一定的概率發(fā)生，則得到的數(shù)學(xué)模型就是m階馬爾可夫信源的數(shù)學(xué)模型。,19,m階馬爾可夫信源的數(shù)學(xué)模型： 且滿足,20,m階馬爾可夫信源的熵： ：,也叫m+1次擴(kuò)展信源,21,則：,馬爾可夫極限熵的計算式,22,例：已知一個二進(jìn)制一階馬爾可夫

7、信源，信源符號集合為X=(0，1)，符號間的條件概率為 P(0/0)=0.25 P(1/0)=0.75 P(0/1)=0.5 P(1/1)=0.5 求狀態(tài)轉(zhuǎn)移概率和狀態(tài)轉(zhuǎn)移圖，信源熵。 解：因為是二進(jìn)制一階馬爾可夫信源 所以狀態(tài)空間Si (或Sj) 共包含nm=21=2種狀態(tài)：s1=0,s2=1,狀態(tài)轉(zhuǎn)移概率為 P(s1/s1)=0.25 P(s2/s1)=0.75 P(s1/s2)=0.5 P(s2/s2)=0.5,23,狀態(tài)轉(zhuǎn)移圖如下：,S1=0,S2=1,0.75,0. 5,0. 5,0.25,24,該一階馬爾可夫信源極限熵為：,25,狀態(tài)概率：,注：狀態(tài)概率一定要列方程組求解。,26,

8、例2.2.4：P48,已知一個二進(jìn)制二階馬爾可夫信源，信源符號集合為X=(0，1)，狀態(tài)轉(zhuǎn)移圖符合： P(0/00)= P(1/11)=0.8 P(1/00)= P(0/11)=0.2 P(0/01)= P(1/01)= P(0/10)=P(1/10)=0.5 求狀態(tài)轉(zhuǎn)移概率和極限熵。,27,P(S1/S1)= P(S4/S4)=0.8P(S2/S1)= P(S3/S4)=0.2P(S3/S2)= P(S4/S2) =P(S1/S3) =P(S2/S3)=0.5,解：因為是二進(jìn)制二階馬爾可夫信源 所以狀態(tài)空間Si共有nm=22=4種狀態(tài)：s1=00,s2=01, s3=10，s4=11狀態(tài)轉(zhuǎn)移

9、概率為 P(0/00)= P(1/11)=0.8 00 00 11 11 P(1/00)= P(0/11)=0.2 00 01 11 10 P(0/01)= P(1/01)= P(0/10)=P(1/10)=0.5 01 10 01 11,發(fā)0,發(fā)1,發(fā)1,發(fā)0,發(fā)0,發(fā)1,P(S1/S1)= P(S4/S4)=0.8,P(S2/S1)= P(S3/S4)=0.2,P(S3/S2)=P(S4/S2)=0.5,P(S1/S3)=P(S2/S3)=0.5,28,狀態(tài)轉(zhuǎn)移圖如下：,29,該二階馬爾可夫信源的極限熵為：,30,31,比較m階馬爾可夫信源和消息長度為m的有記憶信源 m階馬爾可夫信源：盡管該信源的記憶長度為m，但符號間的依賴關(guān)系延伸到無窮，用狀態(tài)轉(zhuǎn)移概率來描述這種依賴關(guān)系，其熵為極限熵Hm+1。 表示馬爾可夫信源以轉(zhuǎn)移概率發(fā)出每個符號提供的信息量。 消息長度為m的有記憶信源：符號間的依賴關(guān)系僅限于每一個長度為m的消息，而消息之間是統(tǒng)計獨立的，故其極限熵記作,32,信源的相關(guān)性和冗余度 不同記憶長度（例m階馬氏信源的記憶長度為:m）的離散平穩(wěn)信源的熵 其中n為原始信源集合的符號個數(shù)。 說明：記憶長度m越長，極限熵越小，越接近實際信源,33,信源熵的相對率(信源效率)：實際熵與最大熵的比