《信息論與編碼(第二版)》第2章-4

信源與信息熵第二章12.1

信源的描述和分類2.2離散信源熵和互信息2.3離散序列信源的熵2.4連續(xù)信源的熵和互信息2.5冗余度內(nèi)容22.2離散信源熵和互信息3第一級(jí)處理器第二級(jí)處理器XYZ輸入

級(jí)聯(lián)處理器2.2.4

數(shù)據(jù)處理中信息的變化數(shù)據(jù)處理定理:當(dāng)消息通過多級(jí)處理器時(shí),隨著處理器數(shù)目增多,輸入消息與輸出消息間的平均互信息量趨于變小假設(shè)Y條件下X和Z相互獨(dú)立4數(shù)據(jù)處理定理

數(shù)據(jù)處理定理說明：當(dāng)對(duì)信號(hào)、數(shù)據(jù)或消息進(jìn)行多級(jí)處理時(shí),每處理一次,就有可能損失一部分信息,也就是說數(shù)據(jù)處理會(huì)把信號(hào)、數(shù)據(jù)或消息變成更有用的形式，但是絕不會(huì)創(chuàng)造出新的信息,這就是所謂的信息不增原理。5三維聯(lián)合集XYZ上的平均互信息量62.2.5熵的性質(zhì)1.非負(fù)性

H(X)＝H(p1，p2，…，pn)≥0式中等號(hào)只有在pi=1時(shí)成立。2.對(duì)稱性

H(p1，p2，…，pn)=H(p2，p1，…，pn)例如下列信源的熵都是相等的：7熵的性質(zhì)3.確定性

H(X)＝H(p1，p2，…，pn)≥0只要信源符號(hào)中有一個(gè)符號(hào)出現(xiàn)概率為1,信源熵就等于零。4.極值性(香農(nóng)輔助定理)對(duì)任意兩個(gè)消息數(shù)相同的信源8熵的性質(zhì)5.最大熵定理

離散無記憶信源輸出M個(gè)不同的信息符號(hào),當(dāng)且僅當(dāng)各個(gè)符號(hào)出現(xiàn)概率相等時(shí)即(pi＝1/M)熵最大。6.條件熵小于無條件熵

92.3離散序列信源的熵10離散信源{離散無記憶信源離散有記憶信源{{發(fā)出單個(gè)符號(hào)的無記憶信源發(fā)出符號(hào)序列的無記憶信源發(fā)出符號(hào)序列的有記憶信源發(fā)出符號(hào)序列的馬爾可夫信源2.3.1離散無記憶信源的序列熵發(fā)出單個(gè)符號(hào)的信源指信源每次只發(fā)出一個(gè)符號(hào)代表一個(gè)消息；發(fā)出符號(hào)序列的信源指信源每次發(fā)出一組含二個(gè)以上符號(hào)的符號(hào)序列代表一個(gè)消息。11發(fā)出符號(hào)序列的信源發(fā)出單個(gè)符號(hào)的信源12離散無記憶信源的序列熵

隨機(jī)序列的概率為

設(shè)信源輸出的隨機(jī)序列為

X

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

xn}

X稱為離散無記憶信源X的L次擴(kuò)展信源

13離散無記憶信源的序列熵

當(dāng)信源無記憶時(shí)信源的序列熵

14離散無記憶信源的序列熵若又滿足平穩(wěn)特性,即與序號(hào)l無關(guān)時(shí)：信源的序列熵

平均每個(gè)符號(hào)(消息)熵為

15例:有一個(gè)無記憶信源隨機(jī)變量X∈(0,1),等概率分布,若以單個(gè)符號(hào)出現(xiàn)為一事件,則此時(shí)的信源熵:即用1比特就可表示該事件。如果以兩個(gè)符號(hào)出現(xiàn)(L=2的序列)為一事件，則隨機(jī)序列X∈(00,01,10,11)，信源的序列熵即用2比特才能表示該事件。信源的符號(hào)熵16例:有一離散平穩(wěn)無記憶信源求：二次擴(kuò)展信源的熵X2信源的元素

a1

a2a3a4a5a6a7a8a9對(duì)應(yīng)的消息序列

x1x1x1x2x1x3x2x1x2x2x2x3x3x1x3x2x3x3概率p(ai)

1/41/81/81/81/161/161/81/161/1617平均每個(gè)符號(hào)(消息)熵為

信源的序列熵18離散有記憶信源的序列熵對(duì)于有記憶信源,就不像無記憶信源那樣簡(jiǎn)單,它必須引入條件熵的概念,而且只能在某些特殊情況下才能得到一些有價(jià)值的結(jié)論。對(duì)于由兩個(gè)符號(hào)組成的聯(lián)合信源,有下列結(jié)論:當(dāng)前后符號(hào)無依存關(guān)系時(shí),有下列推論：19若信源輸出一個(gè)L長(zhǎng)序列,則信源的序列熵為平均每個(gè)符號(hào)的熵為：若當(dāng)信源退化為無記憶時(shí):若進(jìn)一步又滿足平穩(wěn)性時(shí)20a0a1a2a09/112/110a11/83/41/8a202/97/9例已知離散有記憶信源中各符號(hào)的概率空間為:設(shè)發(fā)出的符號(hào)只與前一個(gè)符號(hào)有關(guān),這兩個(gè)符號(hào)的概率關(guān)聯(lián)性用條件概率p(aj|ai)表示,如表p(aj|ai)求離散信源的序列熵和平均每個(gè)符號(hào)的熵?21由p(ai,aj)=p(ai)p(aj|

ai)計(jì)算得聯(lián)合概率p(ai

aj)如表a0a1a2a01/41/180a11/181/31/18a201/187/36當(dāng)信源符號(hào)之間無依賴性時(shí),信源X的信息熵為當(dāng)考慮符號(hào)之間有依賴性時(shí),計(jì)算得條件熵

H(X2|X1)＜H(X)信源的條件熵比無依賴時(shí)的熵H(X)減少了0.671比特,這正是因?yàn)榉?hào)之間有依賴性所造成的結(jié)果。22聯(lián)合熵H(X1,X2)表示平均每二個(gè)信源符號(hào)所攜帶的信息量。我們用1/2H(X1,X2)作為二維平穩(wěn)信源X的信息熵的近似值。那么平均每一個(gè)信源符號(hào)攜帶的信息量近似為:

符號(hào)之間存在關(guān)聯(lián)性發(fā)二重符號(hào)序列的熵比較23離散平穩(wěn)信源對(duì)于離散平穩(wěn)信源,有下列結(jié)論：⑴條件熵H(XL|XL-1)隨L的增加是非遞增的條件較多的熵必小于或等于條件較少的熵，而條件熵必小于或等于無條件熵。24⑶HL(X)是L的單調(diào)非增函數(shù)

HL(X)≤HL-1(X)⑷H∞稱為平穩(wěn)信源的極限熵或極限信息量

H0(X)≥H1(X)≥H2(X)≥…≥H∞(X)⑵L給定時(shí),平均符號(hào)熵≥條件熵：

H

L(X)≥H(XL|XL-1)25馬爾可夫信源的信息熵馬爾可夫信源齊次、遍歷的馬爾可夫信源的熵26s2s31/0.61/0.20/0.5s11/0.51/0.10/0.9例三狀態(tài)馬爾可夫信源0/0.827282.5冗余度29冗余度冗余度(多余度、剩余度)表示信源在實(shí)際發(fā)出消息時(shí)所包含的多余信息。冗余度：信源符號(hào)間的相關(guān)性。相關(guān)程度越大,信源的實(shí)際熵越小信源符號(hào)分布的不均勻性。等概率分布時(shí)信源熵最大。30冗余度對(duì)于有記憶信源,極限熵為H∞(X)。這就是說我們需要傳送這一信源的信息,理論上只需要傳送H∞(X)即可。但必須掌握信源全部概率統(tǒng)計(jì)特性,這顯然是不現(xiàn)實(shí)的。實(shí)際上,只能算出Hm(X)。那么與理論極限值相比,就要多傳送Hm(X)－H∞(X)。為了定量地描述信源的有效性,定義:信息效率冗余度31冗余度由于信源存在冗余度,即存在一些不必要傳送的信息,因此信源也就存在進(jìn)一步壓縮其信息率的可能性。信源冗余度越大,其進(jìn)一步壓縮的潛力越大。這是信源編碼與數(shù)據(jù)壓縮的前提與理論基礎(chǔ)。例：英文字母：等概率H0=log27=4.76比特/符號(hào)不等概率H1=4.03比特/符號(hào)考慮相關(guān)性H2

=3.32比特/符號(hào)極限熵H∞=1.4比特/符號(hào)冗余度英語文章有71%是由語言結(jié)構(gòu)定好的,只有29%是自由選擇32習(xí)題2-132-162-262-3033本章小結(jié)34信源的描述一個(gè)離散信源發(fā)出的各個(gè)符號(hào)消息的集合為：它們的概率分別為p(xi):xi的先驗(yàn)概率單符號(hào)離散信源的數(shù)學(xué)模型—概率空間a,b,c,…z3500011110狀態(tài)轉(zhuǎn)移概率矩陣符號(hào)條件概率矩陣(1)1/2(1)3/4(0)1/3(0)1/4(0)1/2(0)1/5(1)2/3(1)4/5s2s1s4s3馬爾可夫信源36穩(wěn)態(tài)分布概率穩(wěn)態(tài)后的符號(hào)概率分布37離散信源熵和互信息問題：

什么叫不確定度？什么叫自信息量？什么叫平均不確定度？什么叫信源熵？什么叫平均自信息量？什么叫條件熵？什么叫聯(lián)合熵？聯(lián)合熵、條件熵和熵的關(guān)系是什么？38離散信源熵和互信息問題：什么叫后驗(yàn)概率？什么叫互信息量？什么叫平均互信息量？什么叫疑義度？什么叫噪聲熵（或散布度）？數(shù)據(jù)處理定理是如何描述的？熵的性質(zhì)有哪些？39自信息量設(shè)離散信源X，其概率空間為I

(xi)含義:當(dāng)事件xi發(fā)生以前,表示事件xi發(fā)生的不確定性當(dāng)事件xi發(fā)生以后,表示事件xi所含有的信息量40自信息量自信息量條件自信息量聯(lián)合自信息量41離散信源熵離散信源熵H(X)信源熵具有以下三種物理含意：信息熵H(X)表示信源輸出后,每個(gè)離散消息所提供的平均信息量。信息熵H(X)表示信源輸出前,信源的平均不確定性。信息熵H(X)反映了變量X的隨機(jī)性。42信源熵?zé)o條件熵條件熵聯(lián)合熵43互信息互信息定義為

xi的后驗(yàn)概率與先驗(yàn)概率比值的對(duì)數(shù)互信息I(xi;yj)表示接收到某消息yj后獲得的關(guān)于事件xi的信息量。44平均互信息平均互信息定義

信息=先驗(yàn)不確定性－后驗(yàn)不確定性=不確定性減少的量Y未知,X的不確定度為H(X)Y已知,X的不確定度變?yōu)镠(X|Y)45維拉圖H(X|Y)H(X)H(Y)H(XY)H(Y|X)I(X;Y)46收發(fā)兩端的熵關(guān)系I(X;Y)

H(X)

H(Y)

H(X/Y)疑義度

H(Y/X)噪聲熵47馬爾可夫信源的信息熵齊次、遍歷的馬爾可夫信源的熵48概率論基礎(chǔ)無條件概率、條件概率、聯(lián)合概率的性質(zhì)和關(guān)系⑴⑵⑶49概率論基礎(chǔ)無條件概率、條件概率、聯(lián)合概率的性質(zhì)和關(guān)系⑷⑸⑹50例

一個(gè)二元二階馬爾可夫信源,其信源符號(hào)集為{0,1}信源開始時(shí)：p(0)=p(1)=0.5發(fā)出隨機(jī)變量X1。

下一單位時(shí)間：輸出隨機(jī)變量X2與X1有依賴關(guān)系x2x10100.30.410.70.6p(x2|x1)再下一單位時(shí)間：輸出隨機(jī)變量X3與X2X1有依賴關(guān)系x3x1x20001101100.40.20.30.410.60.80.70.6p(x3|x1x2)51從第四單位時(shí)間開始，隨機(jī)變量Xi只與前面二個(gè)單位時(shí)間的隨機(jī)變量Xi-2Xi-1有依賴關(guān)系:

p(xi|xi-1

xi-2…x2

x1)=p(xi|xi-1

xi-2)(i＞3)且

p(xi|xi-1

xi-2)=p(x3|x2x1)(i＞3)解:設(shè)信源開始處于s0狀態(tài),并以等概率發(fā)出符號(hào)0和1,分別到達(dá)狀態(tài)s1和s2

:若處于s1,以0.3和0.7的概率發(fā)出0和1到達(dá)s3和s4若處于s2,以0.4和0.6的概率發(fā)出0和1到達(dá)s5和s600011011(0)0.5(1)0.5(0)0.3(0)0.4(1)0.7(1)0.6s1s2s0s6s5s4s352信源發(fā)完第2個(gè)符號(hào)后再發(fā)第3個(gè)及以后的符號(hào)。從第3單位時(shí)間以后信源必處在s3

s4s5

s6四種狀態(tài)之一。在i≥3后,信源的狀態(tài)轉(zhuǎn)移可用下圖表示:10110100(0)0.3(0)0.4(1)0.7(0)0.2(1)0.8(1)0.6(0)0.4(1)0.6狀態(tài)s1和s5功能是完全相同狀態(tài)s2和s6功能是完