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

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

2、變成更有用的形式，但是絕不會創(chuàng)造出新的信息,這就是所謂的信息不增原理。 6 三維聯(lián)合集XYZ上的平均互信息量 )|;();()|;();();()|;()|;();();()|;();();();()|;();();()|;(),();(YZXIZYIXZYIZXIZXYIZYXIYZXIYXIZXIZYXIZXIZYXIYZXIYXZIXYIXYZIYZXIYXIYZXI71.非負性 H(X)H(p1，p2，pn)0 式中等號只有在pi =1時成立。2.對稱性 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 只要信源符號中有一個符號出現(xiàn)概率為1,信源熵就等于零。4.極值性(香農(nóng)輔助定理) 對任意兩個消息數(shù)相同的信源 niyqYxpX, 2 , 1,)()(iniiniiinqppppppHloglog),(112195.最大熵定理 離散無記憶信源輸出M個不同的信息符號,當且僅當各個符號出現(xiàn)概率相等時即( pi1/M)熵最大。MMMHXH2log1,1)()()()()()|()()|(YHXHXYHYHXYHXHYXH6.條件熵小于無條件熵 1011離散信源離散無記憶信源

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

5、iixxpxxpxxpxpxxxxpxxxpxxpxpxxxppLLLLX 設信源輸出的隨機序列為 X =(X1X2XlXL) 序列中的變量Xlx1,x2, xn X稱為離散無記憶信源X的L次擴展信源 14LliiiiiiiilLLxpxpxpxpxpxxxpp1)()()()()(),()(32121X 當信源無記憶時 信源的序列熵 LlliLliiniiiXHxpxpxpxpHllL)()(log)()(log)()(1X15 若又滿足平穩(wěn)特性,即與序號l無關時：)()(XLHHXLLlipxppl1)()(X 信源的序列熵 平均每個符號(消息)熵為 )()(1)(XHHLHLXX16例例

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

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

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

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

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

11、)()|()|()|()|()|()|(11231222121112121XHXXHXXXHXXXHXXXHXXXHXXXXHLLLLLLLLLL25 HL(X)是L的單調(diào)非增函數(shù) HL(X)HL-1(X)|(lim)(lim)(121LLLLLXXXXHXHXH H稱為平穩(wěn)信源的極限熵或極限信息量 H0(X)H1(X)H2(X)H(X) L給定時,平均符號熵條件熵： 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符號符號符號/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符號/743. 0722. 059451599469. 0595)|()(1bitsXHspHiiim2930 冗余度(多余度、剩余度) 表示信源在實際發(fā)出消息時所包含的多余信息。 冗余度： 信源符號間的相關性。 相關程度越大,信源的實際熵越小 信源符號分布的不均勻性。 等概率分布時信源熵最大。)()()()(log2102XHXHXHXHn31 對于有記憶信源,極限熵為H(X)。 這就

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

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

16、符號條件概率矩陣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)后的符號概率分布35267454356433563235321)()|()(3597451356413563135321)()|()(2211iiiiiispsapapspsap

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

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

19、xpxpXH)(log)()(44 互信息 定義為 xi的后驗概率與先驗概率比值的對數(shù))()|(log);(2ijijixpyxpyxI 互信息I(xi;yj)表示接收到某消息yj后獲得的關于事件xi的信息量。45 平均互信息定義 信息= 先驗不確定性后驗不確定性 = 不確定性減少的量)|()();(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 無條件概率、條件概率、聯(lián)合概率的性質(zhì)和關系1)()/()/()()(0jijiijjiyxpyxpxypypxp， mjnijimjijnijimjjniiyxpxypyxpypxp1111111)(, 1)/(, 1)/(, 1)(, 1)()()(),()(11imj

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