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

1、22.1 2.1 信源的描述和分類(lèi)信源的描述和分類(lèi)2.2 2.2 離散信源熵和互信息離散信源熵和互信息2.3 2.3 離散序列信源的熵離散序列信源的熵2.4 2.4 連續(xù)信源的熵和互信息連續(xù)信源的熵和互信息2.5 2.5 冗余度冗余度34第一級(jí)處理器第二級(jí)處理器XYZ輸入 級(jí)聯(lián)處理器 數(shù)據(jù)處理定理 : 當(dāng)消息通過(guò)多級(jí)處理器時(shí),隨著處理器數(shù)目增多,輸入消息與輸出消息間的平均互信息量趨于變小 假設(shè)Y條件下X和Z相互獨(dú)立 );();();();(YXIZXIZYIZXI5 數(shù)據(jù)處理定理說(shuō)明： 當(dāng)對(duì)信號(hào)、數(shù)據(jù)或消息進(jìn)行多級(jí)處理時(shí),每處理一次,就有可能損失一部分信息,也就是說(shuō)數(shù)據(jù)處理會(huì)把信號(hào)、數(shù)據(jù)或消息

2、變成更有用的形式，但是絕不會(huì)創(chuàng)造出新的信息,這就是所謂的信息不增原理。 6 三維聯(lián)合集XYZ上的平均互信息量 )|;();()|;();();()|;()|;();();()|;();();();()|;();();()|;(),();(YZXIZYIXZYIZXIZXYIZYXIYZXIYXIZXIZYXIZXIZYXIYZXIYXZIXYIXYZIYZXIYXIYZXI71.非負(fù)性 H(X)H(p1，p2，pn)0 式中等號(hào)只有在pi =1時(shí)成立。2.對(duì)稱(chēng)性 H(p1，p2，pn) = H(p2，p1，pn) 例如下列信源的熵都是相等的：6 / 12 / 13 / 1321xxxPX2/

3、16/ 13/ 1321yyyPY6 / 13 / 12 / 1321zzzPZ83.確定性 H(X)H(p1，p2，pn)0 只要信源符號(hào)中有一個(gè)符號(hào)出現(xiàn)概率為1,信源熵就等于零。4.極值性(香農(nóng)輔助定理) 對(duì)任意兩個(gè)消息數(shù)相同的信源 niyqYxpX, 2 , 1,)()(iniiniiinqppppppHloglog),(112195.最大熵定理 離散無(wú)記憶信源輸出M個(gè)不同的信息符號(hào),當(dāng)且僅當(dāng)各個(gè)符號(hào)出現(xiàn)概率相等時(shí)即( pi1/M)熵最大。MMMHXH2log1,1)()()()()()|()()|(YHXHXYHYHXYHXHYXH6.條件熵小于無(wú)條件熵 1011離散信源離散無(wú)記憶信源

4、離散有記憶信源發(fā)出單個(gè)符號(hào)的無(wú)記憶信源發(fā)出符號(hào)序列的無(wú)記憶信源發(fā)出符號(hào)序列的有記憶信源發(fā)出符號(hào)序列的馬爾可夫信源 發(fā)出單個(gè)符號(hào)的信源 指信源每次只發(fā)出一個(gè)符號(hào)代表一個(gè)消息； 發(fā)出符號(hào)序列的信源 指信源每次發(fā)出一組含二個(gè)以上符號(hào)的符號(hào)序列代表一個(gè)消息。12 發(fā)出符號(hào)序列的信源6/ 16/ 16/ 16/ 16/ 16/ 1101100011010001000PX6/ 16/ 16/ 16/ 16/ 16/ 1654321PX 發(fā)出單個(gè)符號(hào)的信源13 隨機(jī)序列的概率為 )|()|()|()()|()|()|()(),()(1211312112121312121Liiiiiiiiiiiiiiiiii

5、iixxpxxpxxpxpxxxxpxxxpxxpxpxxxppLLLLX 設(shè)信源輸出的隨機(jī)序列為 X =(X1X2XlXL) 序列中的變量Xlx1,x2, xn X稱(chēng)為離散無(wú)記憶信源X的L次擴(kuò)展信源 14LliiiiiiiilLLxpxpxpxpxpxxxpp1)()()()()(),()(32121X 當(dāng)信源無(wú)記憶時(shí) 信源的序列熵 LlliLliiniiiXHxpxpxpxpHllL)()(log)()(log)()(1X15 若又滿(mǎn)足平穩(wěn)特性,即與序號(hào)l無(wú)關(guān)時(shí)：)()(XLHHXLLlipxppl1)()(X 信源的序列熵 平均每個(gè)符號(hào)(消息)熵為 )()(1)(XHHLHLXX16例例

6、:有一個(gè)無(wú)記憶信源隨機(jī)變量X(0,1),等概率分布,若以單個(gè)符號(hào)出現(xiàn)為一事件,則此時(shí)的信源熵:符號(hào)/12log)(2bitXH序列/24log)X(2bitH符號(hào)/1)(21)(2bitHHXX 即用 1比特就可表示該事件。 如果以?xún)蓚€(gè)符號(hào)出現(xiàn)(L=2的序列)為一事件，則隨機(jī)序列X(00,01,10,11)，信源的序列熵 即用2比特才能表示該事件。 信源的符號(hào)熵17 例:有一離散平穩(wěn)無(wú)記憶信源 414121)(321xxxxpX求：二次擴(kuò)展信源的熵X2信源的元素 a1 a2a3a4a5a6a7a8a9對(duì)應(yīng)的消息序列 x1x1x1x2x1x3x2x1x2x2x2x3x3x1x3 x2x3 x3概

7、率p(ai) 1/4 1/81/81/81/16 1/161/81/16 1/1618序列/3)(log)()()(91bitapapXHHiiiL符號(hào)/5 . 1)(log)()(31bitxpxpXHiii序列/35 . 12)(2)(bitXHH 平均每個(gè)符號(hào)(消息)熵為 信源的序列熵19 對(duì)于有記憶信源,就不像無(wú)記憶信源那樣簡(jiǎn)單,它必須引入條件熵的概念,而且只能在某些特殊情況下才能得到一些有價(jià)值的結(jié)論。 對(duì)于由兩個(gè)符號(hào)組成的聯(lián)合信源,有下列結(jié)論:)|()(),|()()|()()|()()(12221121212121XXHXHXXHXHXXHXHXXHXHXXH)()|(),()|(

8、)()()(2121212121XHXXHXHXXHXHXHXXH 當(dāng)前后符號(hào)無(wú)依存關(guān)系時(shí),有下列推論：20 若信源輸出一個(gè)L長(zhǎng)序列,則信源的序列熵為)()|()|()|()()()(11112121LLlllLLLXHXXHXXXHXXHXHXXXHHX 平均每個(gè)符號(hào)的熵為： )(1)(LLXHLHX 若當(dāng)信源退化為無(wú)記憶時(shí):)()(XLHHXLllXHH)()(X若進(jìn)一步又滿(mǎn)足平穩(wěn)性時(shí) 21a0a1a2a09/112/110a11/83/41/8a202/97/9 例例已知離散有記憶信源中各符號(hào)的概率空間為:41943611210aaaPX 設(shè)發(fā)出的符號(hào)只與前一個(gè)符號(hào)有關(guān),這兩個(gè)符號(hào)的概率

9、關(guān)聯(lián)性用條件概率p(aj|ai)表示,如表p(aj|ai) 求離散信源的序列熵和平均每個(gè)符號(hào)的熵? 22 由 p(ai,aj) = p(ai) p(aj| ai) 計(jì)算得聯(lián)合概率p(ai aj)如表a0a1a2a01/41/180a11/181/31/18a201/187/3631)()(jijiapaap 當(dāng)信源符號(hào)之間無(wú)依賴(lài)性時(shí),信源X的信息熵為符號(hào)/543. 1)(log)()(20bitapapXHiii 當(dāng)考慮符號(hào)之間有依賴(lài)性時(shí),計(jì)算得條件熵符號(hào)/872. 0)|(log)()|(202012bitaapaapXXHiijjij H(X2| X1)H(X)信源的條件熵比無(wú)依賴(lài)時(shí)的熵H

10、(X)減少了0.671比特,這正是因?yàn)榉?hào)之間有依賴(lài)性所造成的結(jié)果。23 聯(lián)合熵H(X1,X2)表示平均每二個(gè)信源符號(hào)所攜帶的信息量。 我們用1/2H(X1,X2)作為二維平穩(wěn)信源X的信息熵的近似值。那么平均每一個(gè)信源符號(hào)攜帶的信息量近似為: 符號(hào)/41. 2),(log),(),(202021bitaapaapXXHijijij符號(hào)之間存在關(guān)聯(lián)性 發(fā)二重符號(hào)序列的熵 符號(hào)/21. 1)(21)(22bitXHHX)()(12XXHH比較24 對(duì)于離散平穩(wěn)信源,有下列結(jié)論： 條件熵H (XL|XL-1) 隨L的增加是非遞增的 條件較多的熵必小于或等于條件較少的熵，而條件熵必小于或等于無(wú)條件熵。

11、)()|()|()|()|()|()|(11231222121112121XHXXHXXXHXXXHXXXHXXXHXXXXHLLLLLLLLLL25 HL(X)是L的單調(diào)非增函數(shù) HL(X)HL-1(X)|(lim)(lim)(121LLLLLXXXXHXHXH H稱(chēng)為平穩(wěn)信源的極限熵或極限信息量 H0(X)H1(X)H2(X)H(X) L給定時(shí),平均符號(hào)熵條件熵： H L(X)H (XL|XL-1)26 馬爾可夫信源)()|()|(lim)(lim)(1211121XHXXXXHXXXXHXHXHmmmLLLLL),|(),|(111mLLLLLxxxpxxxp 齊次、遍歷的馬爾可夫信源的

12、熵iiimsXHspH)|()(1jijijisxpsxpsXH)|(log)|()|(27s2s31/0.61/0.20/0.5s11/0.51/0.10/0.98 . 02 . 005 . 005 . 09 . 001 . 0)|(ijssp59/45,59/9,59/518 . 05 . 09 . 02 . 05 . 01 . 0321321332123121WWWWWWWWWWWWWWWpijjiiWW例三狀態(tài)馬爾可夫信源0/0.828符號(hào)符號(hào)符號(hào)/722. 0) 8 . 0 , 2 . 0(8 . 0log8 . 02 . 0log2 . 0)|(/1) 5 . 0 , 5 . 0(

13、5 . 0log5 . 05 . 0log5 . 0)|(/469. 0) 9 . 0 , 1 . 0(9 . 0log9 . 01 . 0log1 . 0)|(321bitHsXHbitHsXHbitHsXH符號(hào)/743. 0722. 059451599469. 0595)|()(1bitsXHspHiiim2930 冗余度(多余度、剩余度) 表示信源在實(shí)際發(fā)出消息時(shí)所包含的多余信息。 冗余度： 信源符號(hào)間的相關(guān)性。 相關(guān)程度越大,信源的實(shí)際熵越小 信源符號(hào)分布的不均勻性。 等概率分布時(shí)信源熵最大。)()()()(log2102XHXHXHXHn31 對(duì)于有記憶信源,極限熵為H(X)。 這就

14、是說(shuō)我們需要傳送這一信源的信息,理論上只需要傳送H(X)即可。但必須掌握信源全部概率統(tǒng)計(jì)特性,這顯然是不現(xiàn)實(shí)的。 實(shí)際上,只能算出Hm(X)。那么與理論極限值相比,就要多傳送Hm(X)H(X)。 為了定量地描述信源的有效性,定義:)()(XHXHm)()(11XHXHm信息效率冗余度32 由于信源存在冗余度,即存在一些不必要傳送的信息,因此信源也就存在進(jìn)一步壓縮其信息率的可能性。 信源冗余度越大,其進(jìn)一步壓縮的潛力越大。這是信源編碼與數(shù)據(jù)壓縮的前提與理論基礎(chǔ)。 例：英文字母： 等概率 H0 = log27 = 4.76比特/符號(hào) 不等概率 H1 = 4.03比特/符號(hào) 考慮相關(guān)性 H2 = 3

15、.32比特/符號(hào) 極限熵 H =1.4比特/符號(hào) 冗余度71.076.4/)4.176.4(英語(yǔ)文章有71%是由語(yǔ)言結(jié)構(gòu)定好的,只有29%是自由選擇33 2-13 2-16 2-26 2-3035 一個(gè)離散信源發(fā)出的各個(gè)符號(hào)消息的集合為：,21nxxxX)(,),(),(21nxpxpxpP 它們的概率分別為 p(xi): xi的先驗(yàn)概率先驗(yàn)概率 單符號(hào)離散信源的數(shù)學(xué)模型概率空間)()()(2121nnxpxpxpxxxPX1)(0)(1niiixpxpa,b,c,z36000111105/45/14/34/13/23/12/12/1)|(432110sssssapaaij 狀態(tài)轉(zhuǎn)移概率矩陣

16、符號(hào)條件概率矩陣5/45/100004/34/13/23/100002/12/1)|(43214321sssssspssssij(1)1/2(1)3/4(0)1/3(0)1/4(0)1/2(0)1/5(1)2/3(1)4/5s2s1s4s337 穩(wěn)態(tài)分布概率154325131432121214321442342231131WWWWWWWWWWWWWWWWpijjiiWW74,356,356,3534321WWWW 穩(wěn)態(tài)后的符號(hào)概率分布35267454356433563235321)()|()(3597451356413563135321)()|()(2211iiiiiispsapapspsap

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

18、(iixpxI 條件自信息量 聯(lián)合自信息量)|(log)|(jijiyxpyxI)(log)(jijiyxpyxI42 離散信源熵H(X)iiiiiixpxpxIxpXH)(log)()()()( 信源熵具有以下三種物理含意： 信息熵H(X)表示信源輸出后,每個(gè)離散消息所提供的平均信息量。 信息熵H(X)表示信源輸出前,信源的平均不確定性。 信息熵H(X)反映了變量X的隨機(jī)性 。43 無(wú)條件熵?zé)o條件熵)|(log)|()|(jiijijyxpyxpyXH)|(log),()|(jiijjiyxpyxpYXH),(log),(),(jiijjiyxpyxpYXH 條件熵條件熵 聯(lián)合熵聯(lián)合熵iii

19、xpxpXH)(log)()(44 互信息 定義為 xi的后驗(yàn)概率與先驗(yàn)概率比值的對(duì)數(shù))()|(log);(2ijijixpyxpyxI 互信息I(xi;yj)表示接收到某消息yj后獲得的關(guān)于事件xi的信息量。45 平均互信息定義 信息= 先驗(yàn)不確定性后驗(yàn)不確定性 = 不確定性減少的量)|()();(YXHXHYXI Y未知,X 的不確定度為H(X) Y已知,X 的不確定度變?yōu)镠(X |Y)ijijijixpyxpyxpYXI)()|(log)();(46H(X|Y)H(X)H(Y)H(XY)H(Y|X)I(X;Y)()()()|()()|()();(XYHYHXHXYHYHYXHXHYXI)

20、|()()|()()()()()|()()|()()(XYHYHYXHXHYHXHXYHYXHYHXYHXHXYH47I(X;Y) H(X) H(Y) H(X/Y)疑義度疑義度 H(Y/X)噪聲熵噪聲熵48 齊次、遍歷的馬爾可夫信源的熵iiimsXHspH)|()(1jijijisxpsxpsXH)|(log)|()|(49 無(wú)條件概率、條件概率、聯(lián)合概率的性質(zhì)和關(guān)系1)()/()/()()(0jijiijjiyxpyxpxypypxp， mjnijimjijnijimjjniiyxpxypyxpypxp1111111)(, 1)/(, 1)/(, 1)(, 1)()()(),()(11imj

21、jijnijixpyxpypyxp50 無(wú)條件概率、條件概率、聯(lián)合概率的性質(zhì)和關(guān)系)/()()/()()(jijijijiyxpypxypxpyxp，相互獨(dú)立時(shí)，與當(dāng))()/()()/()()()(ijijijjijixpyxpypxypypxpyxpYXmjjijiijnijijijiyxpyxpxypyxpyxpyxp11)()()/()()()/(，51 例 一個(gè)二元二階馬爾可夫信源,其信源符號(hào)集為0,1信源開(kāi)始時(shí)：p(0) = p(1) = 0.5發(fā)出隨機(jī)變量X1。 下一單位時(shí)間：輸出隨機(jī)變量X2與X1有依賴(lài)關(guān)系x2x10100.30.410.70.6p(x2|x1)再下一單位時(shí)間：輸出隨機(jī)變量X3與X2X1有依賴(lài)關(guān)系x3x1 x200011010.40.6p(x3|x1x2)52 從第四單位時(shí)間開(kāi)始，隨機(jī)變量Xi只與前面二個(gè)單位時(shí)間的隨機(jī)變量Xi-2Xi-1有依賴(lài)關(guān)系: p(xi| xi-1 xi-2x2 x1) = p(xi| xi-1 xi-2) (i3) 且 p(xi| xi-1 xi-2) = p(x3| x2x1) (i3) 解: 設(shè)信源開(kāi)始處于s0狀態(tài),并以等概率發(fā)出符號(hào)0和1,分別到達(dá)狀態(tài)s1和s2 : 若處于s1 ,以0.3和0.7的概率發(fā)出0和1到達(dá)s3和