第二章-信息論基本概念

1、回顧：回顧：單符號無記憶信源熵：單符號無記憶信源熵：H(X) bit/符號符號符號序列無記憶信源熵：符號序列無記憶信源熵：KH(X) bit/序列序列 符號序列有記憶信源熵：聯(lián)合熵符號序列有記憶信源熵：聯(lián)合熵 H(X1X2XN) bit/序列序列 平均符號熵平均符號熵 極限熵極限熵121lim()lim()bit/NNNNHHH X XXNX符號121() bit/NH X XXN符號121lim()lim(/)bit/NNNNNHHH XX XXX符號平穩(wěn)信源平穩(wěn)信源馬爾可夫信源馬爾可夫信源有記憶的特點：1、有限記憶長度2、信源輸出不僅與符號集有關，而且與狀態(tài)有關3、發(fā)出一個個符號，每發(fā)一個

2、符號狀態(tài)要發(fā)生轉(zhuǎn)移狀態(tài)：狀態(tài)：有限的相關符號組構成的序列馬爾可夫信源：馬爾可夫信源：以信源輸出符號序列內(nèi)各 符號間條件概率來反映記憶特性的一類信源。m階馬爾可夫信源：階馬爾可夫信源：信源輸出的當前符號僅與前面m個符號有關的馬爾可夫信源。1111211()()(,)mmmnimmiiiiix xxXxXPpXXxxsxx此時，狀態(tài)模型階馬爾可夫信源的數(shù)學m121, ,1,2,mi iin馬爾可夫信源的定義馬爾可夫信源的定義：（1）某一時刻信源符號的輸出只與當前的信源狀態(tài)）某一時刻信源符號的輸出只與當前的信源狀態(tài)有關，而與以前的狀態(tài)無關。有關，而與以前的狀態(tài)無關。 (2) 信源狀態(tài)只由當前輸出符號

3、和前一時刻的信源狀信源狀態(tài)只由當前輸出符號和前一時刻的信源狀態(tài)唯一確定。態(tài)唯一確定。llXXXX121輸出符號序列：llSSSS121輸出狀態(tài)序列：符號條件概率:狀態(tài)轉(zhuǎn)移概率:)(iksxp)(ijssp通過引入符號條件概率和狀態(tài)轉(zhuǎn)移概率,馬爾可夫信源可轉(zhuǎn)化為馬爾可夫鏈。一步轉(zhuǎn)移概率：一步轉(zhuǎn)移概率：1( )(|)ijmjmip mp SsSs1( )(|)ijmjmiijp mp SsSsp對于齊次馬爾可夫鏈，有(|)kip xs狀態(tài)轉(zhuǎn)移概率可用條件概率計算。轉(zhuǎn)移概率矩陣和狀態(tài)轉(zhuǎn)移圖轉(zhuǎn)移概率矩陣和狀態(tài)轉(zhuǎn)移圖（香農(nóng)線圖）（香農(nóng)線圖）1111.=.qqqqppPpp狀態(tài)轉(zhuǎn)移圖（香農(nóng)線圖）狀態(tài)轉(zhuǎn)移圖

4、（香農(nóng)線圖）圓圈表示狀態(tài)。圓圈表示狀態(tài)。狀態(tài)之間的有向線段表示狀態(tài)轉(zhuǎn)移。狀態(tài)之間的有向線段表示狀態(tài)轉(zhuǎn)移。有向線段邊的符號和數(shù)字代表發(fā)出的符號和條件概率。有向線段邊的符號和數(shù)字代表發(fā)出的符號和條件概率。 馬爾可夫鏈可以用香農(nóng)線圖表示。馬爾可夫鏈可以用香農(nóng)線圖表示。(a),(b),(c)(a),(b),(c)分別表示信源含兩種字母分別表示信源含兩種字母(D(D2)2)的一的一階、二階和三階馬爾可夫鏈的線圖。階、二階和三階馬爾可夫鏈的線圖。(d),(e)(d),(e)分別表示分別表示D D3 3和和D D4 4的一階馬爾可夫鏈的的一階馬爾可夫鏈的線圖。線圖。AA(A)(B)BB(a)(AAA)(BB

5、B)(ABB)(BAA)(BBA)(AAB)(ABA)(BAB)ABBBAAAABBBAABBA(c)(A)(B)(C)(D)ACBCBDBAAACDDBCD(e)2k.K,4. X ,kkXX XXX12mkiiii112n1 輸出的消息是符號序列： x xx2 發(fā)出的符號序列是順序發(fā)出3 在第 次發(fā)出的符號x 取自單符號信源從而信源模型可以表示為：x xx馬爾可夫信源的特點：馬爾可夫信源的特點：15.)(|)kk mkiiikp xxxkk-mk-m+1k-1iiii在第 次發(fā)出的符號x 與前面m個符號有關。（xxx稱為狀態(tài)這種關聯(lián)性用條件概率表示：111106.)(|)(|)7.(|)(

6、|)(|)kk mkmjmiiiimjmijijikp SsSsp xxxp SsSsp SsSsp sskk-mk-m+1k-1k-m+1k-m+1kiiiiijiii在第 次發(fā)出的符號x ,狀態(tài)改變s =（xxxs =（xxx用狀態(tài)轉(zhuǎn)移概率表示：齊次馬爾可夫信源例：例：(0|00)(1|11)0.8(1|00)(0|11)0.2(0|01)(0|10)0.5(1|01)(1|10)0.5pppppppp設有一個二進制二階馬爾可夫信源，其信源符號集為0,1, 條件概率為求狀態(tài)轉(zhuǎn)移矩陣，并給出香農(nóng)線圖。1234112132421323344400010(|)(0|00)0.8(|)(1|00)

7、0.2(|)(0|01)0.5(|)(1|01)0.5(|)(0|10)0.5(|)(1|10)0.5(|)(0|11)0.2(|)(1|11)0.8ssssp sspp sspp sspp sspp sspp sspp sspp ssp令 ， ， 1 ， 11，轉(zhuǎn)移概率矩陣P為0.80.P=00000.50.50.50.500000.20.82001001110.80.20.50.50.50.20.50.8m階馬爾可夫信源的極限熵階馬爾可夫信源的極限熵121lim()NNNXHHX XX111)(mmmHXXXH)s/X(H)s (p)/sx(logp)s/x(p)s (p)/sx(logp

8、)s ,x(p)XXX/X(HHHin1iin1in1jijijin1in1jijijm211m1mmmmP(si)為狀態(tài)概率的平穩(wěn)分布，由轉(zhuǎn)移概率矩陣決定，H(X/si)表示信源處于某一狀態(tài)si時發(fā)出某一個消息符號的平均不確定性。遍歷性遍歷性 對于齊次馬爾可夫鏈，若對于所有狀態(tài)si , sj , 均存在不依賴于初始狀態(tài)si 的極限1,0lim)(jjijiijjnijnpppppp且滿足則稱其為具有遍歷性的馬爾可夫鏈。遍歷性的意義遍歷性的意義 無論從哪個狀態(tài)出發(fā)，當轉(zhuǎn)移步數(shù)足夠大時，轉(zhuǎn)移到狀態(tài)sj的概率近似等于一個常數(shù)pj。也就是說：馬爾可夫鏈在初始時刻可以處于任意狀態(tài)，經(jīng)過足夠長時間的狀態(tài)

9、轉(zhuǎn)移后，它所處的狀態(tài)與初始狀態(tài)無關。此時每種狀態(tài)出現(xiàn)的概率已達到一種平穩(wěn)分布。()lim()jjkjkpp sp Ss稱為狀態(tài)的平穩(wěn)分布。jijiiWpWWPW即有對齊次馬爾可夫鏈，例例: 一個二階馬爾可夫信源，其香農(nóng)線圖如下，求其信源熵。001001110.80.20.50.50.50.20.50.81234112132421323344400010(|)(0|00)0.8(|)(1|00)0.2(|)(0|01)0.5(|)(1|01)0.5(|)(0|10)0.5(|)(1|10)0.5(|)(0|11)0.2(|)(1|11)0.8ssssp sspp sspp sspp sspp s

10、spp sspp sspp ssp令 ， ， 1 ， 11，轉(zhuǎn)移概率矩陣P為0.80.P=00000.50.50.50.500000.20.82令平穩(wěn)分布： 4321,spspspspW 則： 41iijijjsspspspW寫成矩陣形式：WPW 145( )()14p sp s232()()14p sp s)5.0log5.05.0log5.0()/()/()2.0log2.08.0log8.0()/()/()/(log)/()/()(8.0)/()(324121413sXHsXHsXHsXHsxpsxpsXHbitsXHspHHijijjiiii這里：符號注意：注意：1、平穩(wěn)信源，即其概率

11、分布具有時間推移不變性。Hnm一、并非在任何情況下都存在，對 元階馬爾可夫信源2()1,2,mjp sjn、存在，二、m階馬爾可夫與發(fā)生長度為m的符號序列的有記憶信源的區(qū)別：1、馬爾可夫信源發(fā)出一個個符號，有限長度有記憶信源發(fā)出一組組符號；2、馬爾可夫信源記憶長度雖然有限，但依賴關系延伸到無窮遠。長為m的有限記憶信源符號間的依賴關系僅限于每組內(nèi)，組與組之間沒有依賴關系；有記憶信源的極限熵是平均符號熵的極限。是條件熵，熵、馬爾可夫信源的極限13mH)(1limXHNN例：設某信源符號例：設某信源符號XA=a1,a2,a3,信源所處的狀態(tài)信源所處的狀態(tài)SE=E1,E2,E3,E4,E5.各狀態(tài)之間

12、的轉(zhuǎn)移情況如下各狀態(tài)之間的轉(zhuǎn)移情況如下圖所示，請判斷這是否是一個馬爾可夫信源？圖所示，請判斷這是否是一個馬爾可夫信源？馬爾可夫信源定義：若一信源滿足下列兩點，即為馬爾可夫信源。輸出符號只與當前狀態(tài)有關；(1) 當前狀態(tài)和輸出唯一決定了下一狀態(tài)。解解：（：（1）信源在）信源在Ei狀態(tài)下輸出符號狀態(tài)下輸出符號ak的條件概率的條件概率p(ak/Ei)用矩陣用矩陣表示為表示為2141410014104321210414121)|(ikEap31(|)1,1,2,3,4,5kikp aEi并且滿足并且滿足（2）該信源在）該信源在l時刻所處的狀態(tài)由當前的輸出符號與前一時刻時刻所處的狀態(tài)由當前的輸出符號與前

13、一時刻(l-1)信源的狀態(tài)唯一決定信源的狀態(tài)唯一決定狀態(tài)的一步轉(zhuǎn)移概率：狀態(tài)的一步轉(zhuǎn)移概率：1 11002 441 100 02 23 1 (|)00 04 40 0 00 13 10 0 04 4jip EE此信源滿足馬爾可夫信源的兩個條件，此信源滿足馬爾可夫信源的兩個條件，是馬爾可夫信源，并且是齊次馬爾可夫信源。是馬爾可夫信源，并且是齊次馬爾可夫信源。 例：例： 設兩位二進制碼所代表的四個狀態(tài)分別為設兩位二進制碼所代表的四個狀態(tài)分別為 0000，0101，1010，1111，其，其符號轉(zhuǎn)移概率和狀態(tài)轉(zhuǎn)移概率由下列兩表給出：符號轉(zhuǎn)移概率和狀態(tài)轉(zhuǎn)移概率由下列兩表給出： 試求穩(wěn)定條件下各狀態(tài)的概

14、率試求穩(wěn)定條件下各狀態(tài)的概率起始狀態(tài)發(fā)出符號S0(00)S1(01)S2(10)S3(11) 011/21/31/41/51/22/33/44/5起始狀態(tài)終止狀態(tài)S0(00)S1(01)S1(01)S2(10)S3(11)S0(00)S2(10) S3(11)1/201/4 01/203/40 01/301/5 02/3 04/5 解：據(jù)題意，可畫出相應的香農(nóng)線圖解：據(jù)題意，可畫出相應的香農(nóng)線圖 設穩(wěn)定狀態(tài)下，各個狀態(tài)的概率為設穩(wěn)定狀態(tài)下，各個狀態(tài)的概率為 P(SP(S0 0) )P P0 0， P(SP(S1 1) )P P1 1， P(SP(S2 2) )P P2 2， P(SP(S3 3

15、) )P P3 3 根據(jù)圖示，可得根據(jù)圖示，可得 P P0 0 1/2P1/2P0 0 1/4P1/4P2 2 P P1 1 1/2P1/2P0 0 3/4P3/4P2 2 P P2 2 1/3P1/3P1 1 1/5P1/5P3 3 P P3 3 4/5P4/5P3 3 2/3P2/3P1 1 P P0 0 P P1 1 P P2 2 P P3 3 1 1 由上面五個方程，可得：由上面五個方程，可得： P P0 03/35 3/35 ， P P1 16/35, P6/35, P2 26/356/35， P P3 34/74/7(01)(10)(11)011110001/21/21/32/31

16、/43/4(00)1/54/5 例：有一個一階馬爾可夫信源，已知例：有一個一階馬爾可夫信源，已知 試畫出該信源的香農(nóng)線圖，并求出信源熵。試畫出該信源的香農(nóng)線圖，并求出信源熵。 解：該信源的香農(nóng)線圖為：解：該信源的香農(nóng)線圖為： 在計算信源熵之前，先用轉(zhuǎn)移概率求穩(wěn)定狀態(tài)下二個狀態(tài)在計算信源熵之前，先用轉(zhuǎn)移概率求穩(wěn)定狀態(tài)下二個狀態(tài)x1和和 x2 的概率的概率 和和 3211)(xxp3112)(xxp1)(21xxp0)(22xxp1/3(x2)(x1)2/31)(2xp)(1xp)()()(21321xpxpxp)(0)()(21312xpxpxp1)()(21xpxp4/ 3)(1xp4/ 1)

17、(2xp2211()()log()322111loglog1 log14333340.689ijijiijHp xp x xp x x bit/符號 小結(jié)小結(jié) 兩種有記記憶信源比較兩種有記記憶信源比較類型類型 m階馬氏過程階馬氏過程 m長有記憶信源長有記憶信源 依賴關系依賴關系(相當于相當于)記憶長度為記憶長度為m符號間關系可延伸到無窮符號間關系可延伸到無窮（卷積碼）（卷積碼） m個符號為一組個符號為一組組內(nèi)相關，組間無關組內(nèi)相關，組間無關（分組碼）（分組碼） 描述描述 狀態(tài)轉(zhuǎn)移狀態(tài)轉(zhuǎn)移(條件條件)概率概率 聯(lián)合概率聯(lián)合概率 每符號每符號平均熵平均熵 極限熵極限熵Hm+1 Hm(X)=(1/m

18、)H(X1X2Xm) 總結(jié)總結(jié): :各種離散信源的熵各種離散信源的熵 (1) (1) 發(fā)出單個符號消息的離散無記憶信源熵發(fā)出單個符號消息的離散無記憶信源熵 若信源發(fā)出若信源發(fā)出N N個不同符號個不同符號X1，X2，Xi，XN , 代表代表N N種不種不同的消息，各個符號的概率分別為同的消息，各個符號的概率分別為 P P1 1， P P2 2， P Pi，P PN N 因為這些符號相互獨立，所以該信源熵為：因為這些符號相互獨立，所以該信源熵為： H H（X X） P PiloglogP Pi bit/ bit/符號符號 (2)(2)發(fā)出符號序列消息的離散無記憶信源熵發(fā)出符號序列消息的離散無記憶信

19、源熵 發(fā)出發(fā)出K K重符號序列消息的離散無記憶信源熵為共熵重符號序列消息的離散無記憶信源熵為共熵H(XH(XK K) )，它與，它與單個符號消息信源熵單個符號消息信源熵H(X)H(X)有如下關系：有如下關系： H(XH(XK K) )KH(X)KH(X)KK P PiloglogP Pi bit/ bit/符號序列符號序列 Ni 1Ni 1 (3)(3)發(fā)出符號序列消息的離散有記憶信源熵發(fā)出符號序列消息的離散有記憶信源熵 發(fā)出發(fā)出K K重符號序列消息的離散有記憶信源熵也為共熵重符號序列消息的離散有記憶信源熵也為共熵H(XH(XK K) ) 當當K K2 2時時 H(XH(X2 2) )H(X)

20、H(X)H(X|X)H(X|X) H(X|X) H(X) H(X|X) H(X) H(XH(X2 2) 2H(X) 2H(X) 推廣到推廣到K K重重 H(XH(XK K) )H(X)H(X)H(X|X)H(X|X)H(X|XXX) H(X|XXX) bit/bit/符號序列符號序列 (K1)個個 (4) (4) 發(fā)出符號序列消息的馬爾可夫信源熵發(fā)出符號序列消息的馬爾可夫信源熵 馬爾可夫信源熵是條件熵馬爾可夫信源熵是條件熵 若從前一狀態(tài)若從前一狀態(tài)E Ei轉(zhuǎn)移到后一狀態(tài)轉(zhuǎn)移到后一狀態(tài)E Ej有多種可能性，則信源由狀態(tài)有多種可能性，則信源由狀態(tài)E Ei發(fā)出發(fā)出一個符號的熵一個符號的熵H H（X/

21、X/i）為為 H H（X/X/i） P(xP(xj j|E|Ei i)logP(x)logP(xj j|E|Ei i) ) 再進一步對前一狀態(tài)再進一步對前一狀態(tài)E Ei的全部可能性作統(tǒng)計平均，就得到馬爾可夫信源的全部可能性作統(tǒng)計平均，就得到馬爾可夫信源熵熵 H H 為為 H H P(EP(Ei i) H) H（X/X/i） P(EP(Ei i) P(x) P(xj j|E|Ei i)logP(x)logP(xj j|E|Ei i) bit/) bit/符號符號 jjii 1.5 1.5 各種離散信源的時間熵各種離散信源的時間熵 信源的時間熵信源的時間熵在單位時間內(nèi)信源發(fā)出的平均信息量，單位在單

22、位時間內(nèi)信源發(fā)出的平均信息量，單位 為為bit/s.bit/s. 發(fā)出單個符號消息的離散無記憶信源的時間熵發(fā)出單個符號消息的離散無記憶信源的時間熵 已知離散無記憶信源各符號的概率空間已知離散無記憶信源各符號的概率空間 由于發(fā)出各符號所占有時間是不同的由于發(fā)出各符號所占有時間是不同的 可設符號可設符號X1的長度為的長度為b b1 1，X2為為b b2 2，Xi為為b bi，XN為為b bN 單位均為單位均為s(s(秒秒) ) 則信源各符號的平均長度是各個符號長度的概率加權平均值，則信源各符號的平均長度是各個符號長度的概率加權平均值，即即 X XP(X)P(X)X1，X2， ，Xi，XNP P1

23、1， P P2 2， P Pi， P PNNiiibPb1s/符號 則信源的時間熵則信源的時間熵 H Ht t為：為： 若各符號時間長度相同，均為若各符號時間長度相同，均為b(s)b(s)，則可直接得，則可直接得 又若信源每秒平均發(fā)出又若信源每秒平均發(fā)出 n n個符號，有個符號，有 此時，此時，時間時間熵熵 H Ht t為：為：NiiiNiiitbPPPbXHH11log)(bit/sbit/sbb bn1符號符號/sNiiitPPnXnHH1log)(bit/sbit/s 發(fā)出符號序列消息的離散無記憶信源的時間熵發(fā)出符號序列消息的離散無記憶信源的時間熵 對對K K重符號序列的離散無記憶信源的

24、信源熵為：重符號序列的離散無記憶信源的信源熵為： H(XH(XK K) ) KH(X) bit/KH(X) bit/符號序列符號序列 K K重符號序列消息的平均長度為信源各符號平均長度的重符號序列消息的平均長度為信源各符號平均長度的K K倍，即倍，即 這種信源的時間熵這種信源的時間熵 H Ht t為：為： 可見，它在數(shù)值上與上面一種信源的時間熵相同可見，它在數(shù)值上與上面一種信源的時間熵相同NiiibPKbKB1s/s/符號序列符號序列 NiiiNiiiKtbPPPbXHbKXKHBXHH11log)()()(bit/sbit/s 若該信源每秒內(nèi)平均發(fā)出若該信源每秒內(nèi)平均發(fā)出n n個個K K重符

25、號序列消息，則有：重符號序列消息，則有： 發(fā)出符號序列消息的離散有記憶信源的時間熵發(fā)出符號序列消息的離散有記憶信源的時間熵 計算方法與發(fā)出符號序列無記憶信源的時間熵一致，但計算方法與發(fā)出符號序列無記憶信源的時間熵一致，但 H(XH(XK K) ) KH(X) KH(X) 同樣若信源在每秒內(nèi)平均發(fā)出同樣若信源在每秒內(nèi)平均發(fā)出n n個個K K重符號序列消息，有重符號序列消息，有 )()(XnKHXnHHKtbit/sbit/sbKXHBXHHKKt)()(bit/sbit/s)(KtXnHHbit/sbit/s連續(xù)隨機變量可以看作是離散隨機變量的極限，故可采用離連續(xù)隨機變量可以看作是離散隨機變量的

26、極限，故可采用離散隨機變量來逼近。散隨機變量來逼近。 首先類比概率首先類比概率p pi i與概率密度函數(shù)與概率密度函數(shù)p(x)p(x)： （一）單個連續(xù)隨機變量信源熵（一）單個連續(xù)隨機變量信源熵 連續(xù)信源的熵連續(xù)信源的熵令令xa,b，且，且ab,現(xiàn)將它均勻的劃分為現(xiàn)將它均勻的劃分為n份，每份寬度為份，每份寬度為 ，則，則x處于第處于第i個區(qū)間的概率為個區(qū)間的概率為pi，則則pi= (中值定理中值定理)即當即當p(x)為為x的連續(xù)函數(shù)時，由中值定理，必存在一個的連續(xù)函數(shù)時，由中值定理，必存在一個xi值，值，使上式成立。使上式成立。再按照離散信源的信息熵的定義有：再按照離散信源的信息熵的定義有：

27、nab ( )()(1)iaip x dxp xai( )log()log()()log()logiiniiiiiiiHxppp xp xp xp x 于是我們定義前一項取有限值的項為連續(xù)信源的信息熵，并記為于是我們定義前一項取有限值的項為連續(xù)信源的信息熵，并記為H Hc c( (X X).).也叫相對熵也叫相對熵0lim()lim( )log( )lim( )log( )log( )lim( ) log( )log( )niiinnniibiiabaHXp xp xp xp xp x dxp xp xp x dx 即：即：Hc(X)= 也可記為：也可記為：Hc(X)= 其中其中R1 表示實軸。表示實軸。 ( )log( )bap xp x dx1( )log( )Rp xp x dx),(二二)兩個連續(xù)隨機變量信源熵兩個連續(xù)隨機變量信源熵 聯(lián)合熵聯(lián)合熵條件熵條件熵22()()log()cRHXYp xyp xy dxdy 22(/ )()log( / )cRHX Yp xyp x y dxdy 22( /)()log( / )cRH Y Xp xyp y x dxdy 幾種特殊連續(xù)信源的熵和最大熵定理幾種特殊連續(xù)信源的熵和最大熵定理一、均勻分布信源：一、均勻分布信源： Hc(X)= log2(b-a) 結(jié)論結(jié)論 熵值只與均勻分布