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

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

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

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

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

6、發(fā)出的m 個(gè)符號(hào)相關(guān)。,16,馬爾可夫信源的組成需要兩個(gè)條件： （1）某時(shí)刻信源輸出的符號(hào)只與之前的m個(gè)符號(hào)相關(guān)，這m個(gè)相關(guān)的符號(hào)稱為”信源前一時(shí)刻所處的狀態(tài)”。 m階馬爾可夫信源在時(shí)刻i發(fā)符號(hào),17,18,（2）某時(shí)刻信源所處的狀態(tài)由該時(shí)刻輸出的符號(hào)和前一時(shí)刻的狀態(tài)唯一確定。,問(wèn)：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,則：,馬爾可夫極限熵的計(jì)算式,22,例：已知一個(gè)二進(jìn)制一階馬爾可夫

7、信源，信源符號(hào)集合為X=(0，1)，符號(hào)間的條件概率為 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)移圖，信源熵。 解：因?yàn)槭嵌M(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,已知一個(gè)二進(jìn)制二階馬爾可夫信源，信源符號(hào)集合為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,解：因?yàn)槭嵌M(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階馬爾可夫信源和消息長(zhǎng)度為m的有記憶信源 m階馬爾可夫信源：盡管該信源的記憶長(zhǎng)度為m，但符號(hào)間的依賴關(guān)系延伸到無(wú)窮，用狀態(tài)轉(zhuǎn)移概率來(lái)描述這種依賴關(guān)系，其熵為極限熵Hm+1。 表示馬爾可夫信源以轉(zhuǎn)移概率發(fā)出每個(gè)符號(hào)提供的信息量。 消息長(zhǎng)度為m的有記憶信源：符號(hào)間的依賴關(guān)系僅限于每一個(gè)長(zhǎng)度為m的消息，而消息之間是統(tǒng)計(jì)獨(dú)立的，故其極限熵記作,32,信源的相關(guān)性和冗余度 不同記憶長(zhǎng)度（例m階馬氏信源的記憶長(zhǎng)度為:m）的離散平穩(wěn)信源的熵 其中n為原始信源集合的符號(hào)個(gè)數(shù)。 說(shuō)明：記憶長(zhǎng)度m越長(zhǎng)，極限熵越小，越接近實(shí)際信源,33,信源熵的相對(duì)率(信源效率)：實(shí)際熵與最大熵的比