信息論與編碼 信源與信息熵2

1、1,2.1 信源的描述和分類2.2 離散信源熵和互信息2.3 離散序列信源熵2.4 連續(xù)信源的熵和互信息2.5 冗余度,內(nèi)容,2,2.3 離散序列信源熵,3,2.3 離散序列信源熵,前面討論了單個消息（符號）的離散信源熵，并較詳細(xì)地討論了它的性質(zhì)。然而實際信源的輸出往往是空間或時間的離散隨機(jī)序列，其中有無記憶的離散信源熵序列，當(dāng)然更多的序列是有記憶的，即序列中的符號之間有相關(guān)性。此時需要用聯(lián)合概率分布函數(shù)或條件概率分

2、布函數(shù)來描述信源發(fā)出的符號間的關(guān)系。這里討論離散無記憶序列信源和兩類較簡單的離散有記憶序列信源(平穩(wěn)序列和齊次遍歷馬爾可夫鏈信源)。,4,離散信源,{,離散無記憶信源,離散有記憶信源,{,{,發(fā)出單個符號的無記憶信源,發(fā)出符號序列的無記憶信源,發(fā)出符號序列的有記憶信源,發(fā)出符號序列的馬爾可夫信源,2.3.1 離散無記憶信源的序列熵,發(fā)出單個符號的信源指信源每次只發(fā)出一個符號代表一個消息；發(fā)出符號序列的信源指信源每次發(fā)出一組含二個

3、以上符號的符號序列代表一個消息。,5,發(fā)出符號序列的信源,發(fā)出單個符號的信源,6,離散無記憶信源的序列熵,隨機(jī)序列的概率為,設(shè)信源輸出的隨機(jī)序列為 X =(X1X2…Xl…XL)序列中的單個符號變量Xl∈{x1,x2,… xn}, l =1,2,…,L. X稱為離散無記憶信源X的L次擴(kuò)展信源,7,離散無記憶信源的序列熵,信源的序列熵為,隨機(jī)序列的概率為,8,離散無記憶信源的序列熵,當(dāng)信源無記憶時,信源的序列熵,9,離

4、散無記憶信源的序列熵,若又滿足平穩(wěn)特性,即與序號l無關(guān)時：,信源的序列熵,平均每個符號(消息)熵為,離散無記憶信源平均每個符號的符號熵HL(X)等于單個符號信源的符號熵H(X),10,例:有一個無記憶信源隨機(jī)變量X∈(0,1),等概率分布,若以單個符號出現(xiàn)為一事件,則此時的信源熵:,即用 1比特就可表示該事件。如果以兩個符號出現(xiàn)(L=2的序列)為一事件，則隨機(jī)序列X∈(00,01,10,11)，信源的序列熵,即用2比特才能表示該事件。

5、信源的符號熵,11,例:有一離散平穩(wěn)無記憶信源,求：二次擴(kuò)展信源的熵,12,平均每個符號(消息)熵為,信源的序列熵,序列熵為,13,2.3.2 離散有記憶信源序列熵,對于有記憶信源,就不像無記憶信源那樣簡單,它必須引入條件熵的概念,而且只能在某些特殊情況下才能得到一些有價值的結(jié)論。對于由兩個符號組成的聯(lián)合信源,有下列結(jié)論:,當(dāng)前后符號無依存關(guān)系時,有下列推論：,14,信源的聯(lián)合熵(即前后兩個符號(X1,X2)同時發(fā)生的不確定度)等于

6、信源發(fā)出前一個符號X1的信息熵加上前一個符號X1已知時信源發(fā)出下一個符號X2的條件熵。對于一般的有記憶信源如文字、數(shù)據(jù)等，它們輸出的不是單個或兩個符號，而是由有限個符號組成的序列，這些輸出符號之間存在著相互依存的關(guān)系。可依照上述結(jié)論來分析序列的熵值。,離散有記憶信源序列熵,15,若信源輸出一個L長序列,則信源的序列熵為,平均每個符號的熵為：,若當(dāng)信源退化為無記憶時:,16,例2-12已知離散有記憶信源中各符號的概率空間為:,設(shè)發(fā)出的符

7、號只與前一個符號有關(guān),這兩個符號的概率關(guān)聯(lián)性用條件概率p(aj|ai)表示,如表.,p(aj|ai),求離散信源的序列熵和平均每個符號熵?,17,由 p(ai,aj) = p(ai) p(aj| ai) 計算得聯(lián)合概率p(ai aj)如表,當(dāng)信源符號之間無依賴性時,信源X的信息熵為,當(dāng)考慮符號之間有依賴性時,計算得條件熵,H(X2| X1)＜H(X)信源的條件熵比無依賴時的熵H(X)減少了0.671比特,這正是因為符號之間有依

8、賴性所造成的結(jié)果。,18,聯(lián)合熵H(X1,X2)表示平均每二個信源符號所攜帶的信息量。我們用1/2H(X1,X2)作為二維平穩(wěn)信源X的信息熵的近似值。那么平均每一個信源符號攜帶的信息量近似為:,符號之間存在關(guān)聯(lián)性,發(fā)二重符號序列的熵,比較,或,19,離散平穩(wěn)信源,對于離散平穩(wěn)信源,有下列結(jié)論：⑴ 條件熵H (XL|XL-1) 隨L的增加是非遞增的條件較多的熵必小于或等于條件較少的熵，而條件熵必小于或等于無條件熵。,平穩(wěn)性，聯(lián)合概率

9、具有時間推移不變性。,20,⑶ HL(X)是L的單調(diào)非增函數(shù) HL(X)≤HL-1(X)⑷,H∞(X)稱為平穩(wěn)信源的極限熵或極限信息量 H0(X)≥H1(X)≥H2(X)≥…≥H∞(X),,⑵ L給定時,平均符號熵≥條件熵： H L(X)≥H (XL|XL-1),推廣結(jié)論3可得：,不等概率無記憶信源單個符號的熵,兩個符號組成的序列平均符號熵,等概率無記憶信

10、源單個符號的熵,21,馬爾可夫信源的信息熵,馬爾可夫信源,齊次、遍歷的馬爾可夫信源的熵,馬爾可夫鏈的穩(wěn)態(tài)分布,22,,,,s2,s3,1/0.6,1/0.2,0/0.5,,s1,,,1/0.5,1/0.1,0/0.9,例2-13 三狀態(tài)馬爾可夫信源,0/0.8,23,24,2.5 冗余度,25,冗余度,冗余度(多余度、剩余度)表示信源在實際發(fā)出消息時所包含的多余信息。冗余度：信源符號間的相關(guān)性。相關(guān)程度越大,信源的實際熵越小

11、信源符號分布的不均勻性。等概率分布時信源熵最大。,26,冗余度,對于有記憶信源,極限熵為H∞(X)。這就是說我們需要傳送這一信源的信息,理論上只需要傳送H∞(X)即可。但必須掌握信源全部概率統(tǒng)計特性,這顯然是不現(xiàn)實的。實際上,只能算出Hm(X)。那么與理論極限值相比,就要多傳送Hm(X)－H∞(X)。,為了定量地描述信源的有效性,定義:,信息效率,冗余度,27,冗余度,由于信源存在冗余度,即存在一些不必要傳送的信息,因此信源也就

12、存在進(jìn)一步壓縮其信息率的可能性。信源冗余度越大,其進(jìn)一步壓縮的潛力越大。這是信源編碼與數(shù)據(jù)壓縮的前提與理論基礎(chǔ)。在實際通信系統(tǒng)中，為了提高傳輸效率，往往需要把信源的大量冗余進(jìn)行壓縮，即所謂信源編碼。但是考慮通信中的抗干擾問題，則需要信源具有一定的冗余度。因此在傳輸之前通常加入某些特殊的冗余度，即所謂信道編碼，以達(dá)到通信系統(tǒng)中理想的傳輸有效性和可靠性。,28,冗余度,例：英文字母： 等概率 H0 = log27

13、 = 4.76比特/符號 不等概率 H1 = 4.03比特/符號 考慮相關(guān)性 H2 = 3.32比特/符號 極限熵 H∞ =1.4比特/符號冗余度,英語文章有71%是由語言結(jié)構(gòu)定好的,只有29%是自由選擇,29,習(xí)題,2-262-30,本章小結(jié),31,信源的描述,一個離散信源發(fā)出的各個符號消息的集合為：,它們的概率分別為,p(xi): xi的先驗概率,單符號離散信源的數(shù)學(xué)模型—概率空間

14、,a,b,c,…z,32,00,01,11,10,,,,,,,狀態(tài)轉(zhuǎn)移概率矩陣,符號條件概率矩陣,(1)1/2,(1)3/4,(0)1/3,(0)1/4,(0)1/2,(0)1/5,(1)2/3,(1)4/5,s2,s1,s4,s3,馬爾可夫信源,33,穩(wěn)態(tài)分布概率,穩(wěn)態(tài)后的符號概率分布,34,離散信源熵和互信息,問題： 什么叫不確定度？ 什么叫自信息量？ 什么叫平均不確定度？ 什么叫信源熵？ 什么叫平均自信息量？ 什么叫條

15、件熵？ 什么叫聯(lián)合熵？ 聯(lián)合熵、條件熵和熵的關(guān)系是什么？,35,離散信源熵和互信息,問題：什么叫后驗概率？什么叫互信息量？什么叫平均互信息量？什么叫疑義度？什么叫噪聲熵（或散布度）？數(shù)據(jù)處理定理是如何描述的？熵的性質(zhì)有哪些？,36,,自信息量,設(shè)離散信源X，其概率空間為,I (xi) 含義:當(dāng)事件xi發(fā)生以前,表示事件xi 發(fā)生的不確定性當(dāng)事件xi發(fā)生以后,表示事件xi所含有的信息量,37,自信息量,不確定度定義

16、：隨機(jī)事件(符號)的不確定度在數(shù)量上等于它的自信息量。 說明:兩者的單位相同，但含義卻不相同。具有某種概率分布的隨機(jī)事件不管發(fā)生與否，都存在不確定度，不確定度表征了該事件的特性，而自信息量是在該事件發(fā)生后給予觀察者的信息量。,38,自信息量,I(xi)的特性：⑴ I (xi)是非負(fù)值⑵ 當(dāng)p(xi) = 1時，I(xi) = 0⑶ 當(dāng)p(xi) = 0時，I(xi) =∞ ⑷ I(xi)是先驗概率p(xi)的單調(diào)遞減函

17、數(shù)，即 當(dāng)p(x1)＞p(x2)時，I (x1)＜I (x2)⑸兩個獨立事件的聯(lián)合信息量等于它們分別的信息量之和。 即統(tǒng)計獨立信源的信息量等于它們分別的信息量之和。,39,自信息量,自信息量,條件自信息量,聯(lián)合自信息量,40,離散信源熵,自信息量I(xi)只是表征信源中各個符號xi的不確定度，而一個信源總是包含著多個符號消息，各個符號消息又按概率空間的先驗概率分布，因而各個符號的自信量就不同。所以，自信息量I(xi)

18、是與概率分布有關(guān)的一個隨機(jī)變量，不能作為信源總體的信息量度。對這樣的隨機(jī)變量只能采取求平均的方法。信息熵：從平均意義上來表征信源的總體信息測度的一個量。,41,,離散信源熵,離散信源熵H(X),信源熵具有以下三種物理含意：信息熵H(X)表示信源輸出后,每個離散消息所提供的平均信息量。信息熵H(X)表示信源輸出前,信源的平均不確定性。信息熵H(X)反映了變量X的隨機(jī)性 。,42,例2－7該信源X輸出符號只有兩個,設(shè)為0和1輸出

19、符號發(fā)生的概率分別為p和q，p＋q=l。即信源的概率空間為,則二元信源熵為 H(X)= －plogp－qlogq = －plogp－ (1－ p)log(1－p) =H(p),43,信源信息熵H(X)是概率p的函數(shù),通常用H(p)表示p取值于[0，1]區(qū)間。 H(p)函數(shù)曲線如圖所示。,如果二元信源的輸出符號是確定的,即p=1或q=1,則該信源不提供任何信息。當(dāng)二元信源符

20、號0和1以等概率發(fā)生時,信源熵達(dá)到極大值,等于1比特信息量。,44,信源熵,無條件熵,條件熵 在給定yj條件下，xi的條件自信息量為I(xi| yj), X 集合的條件熵H(X|yj)為在給定Y(即各個yj )條件下,X集合的條件熵H(X|Y),45,信源熵,H(X,Y)＝H(X)＋H(Y|X)H(X,Y)＝H(Y)＋H(X|Y),無條件熵、條件熵、聯(lián)合熵之間的關(guān)系,聯(lián)合熵 聯(lián)合熵是聯(lián)合符號集合(X,Y)

21、上的每個元素對(xi,yj)的自信息量的概率加權(quán)統(tǒng)計平均值。表示X 和Y同時發(fā)生的不確定度。,46,互信息,互信息定義為 xi的后驗概率與先驗概率比值的對數(shù),,互信息I(xi;yj)表示接收到某消息yj后獲得的關(guān)于事件xi的信息量。,47,,平均互信息,平均互信息定義,信息= 先驗不確定性－后驗不確定性 = 不確定性減少的量,Y未知,X 的不確定度為H(X)Y已知,X 的不確定度變?yōu)镠(X |Y),48,維拉

22、圖,,,H(X|Y),H(X),H(Y),H(XY),H(Y|X),I(X;Y),,,,49,條件熵,H(X|Y)：信道疑義度，損失熵信源符號通過有噪信道傳輸后所引起的信息量的損失。信源X的熵等于接收到的信息量加上損失掉的信息量。 H(Y|X)：噪聲熵，散布熵它反映了信道中噪聲源的不確定性。輸出端信源Y 的熵H(Y)等于接收到關(guān)于X的信息量I(X;Y)加上H(Y|X),這完全是由于信道中噪聲引起的。,50,收發(fā)兩端的熵關(guān)系,5

23、1,數(shù)據(jù)處理定理,數(shù)據(jù)處理定理說明：當(dāng)對信號、數(shù)據(jù)或消息進(jìn)行多級處理時,每處理一次,就有可能損失一部分信息,也就是說數(shù)據(jù)處理會把信號、數(shù)據(jù)或消息變成更有用的形式，但是絕不會創(chuàng)造出新的信息,這就是所謂的信息不增原理。,52,熵的性質(zhì),1.非負(fù)性 H(X)＝H(p1，p2，…，pn)≥0式中等號只有在pi =1時成立。2.對稱性 H(p1，p2，…，pn) = H(p2，p1，…，pn)例如下列信源的熵都是相等的：

24、,53,熵的性質(zhì),3.確定性 H(X)＝H(p1，p2，…，pn)≥0只要信源符號中有一個符號出現(xiàn)概率為1,信源熵就等于零。4.極值性(香農(nóng)輔助定理)對任意兩個消息數(shù)相同的信源,54,熵的性質(zhì),5.最大熵定理 離散無記憶信源輸出M個不同的信息符號,當(dāng)且僅當(dāng)各個符號出現(xiàn)概率相等時即( pi＝1/M)熵最大。,6.條件熵小于無條件熵,55,離散無記憶信源的序列熵,信源的序列熵,平均每個符號(消息)熵為,56,離散有

25、記憶信源的序列熵,若信源輸出一個L長序列,則信源的序列熵為,平均每個符號的熵為：,57,離散平穩(wěn)信源,對于離散平穩(wěn)信源,有下列結(jié)論：⑴ 條件熵H (XL|XL-1) 隨L的增加是非遞增的條件較多的熵必小于或等于條件較少的熵，而條件熵必小于或等于無條件熵。,58,離散平穩(wěn)信源,⑶ HL(X)是L的單調(diào)非增函數(shù) HL(X)≤HL-1(X)⑷,H∞稱為平穩(wěn)信源的極限熵或極限信息量

26、 H0(X)≥H1(X)≥H2(X)≥…≥H∞(X),,⑵ L給定時,平均符號熵≥條件熵： H L(X)≥H (XL|XL-1),推廣結(jié)論3可得：,59,馬爾可夫信源的信息熵,齊次、遍歷的馬爾可夫信源的熵,馬爾可夫信源,60,冗余度,冗余度(多余度、剩余度)表示信源在實際發(fā)出消息時所包含的多余信息。冗余度：信源符號間的相關(guān)性。信源符號分布的不均勻性。,信息效率,冗余度,61,概率論基礎(chǔ),無條件概率、條件概率