信息論與編碼-課件第2章-1

1、信源與信息熵第二章12.1 信源的描述和分類2.2 離散信源熵和互信息2.3 離散序列信源的熵2.4 連續(xù)信源的熵和互信息2.5 冗余度2內(nèi)容本章重點(diǎn)信源熵和離散/連續(xù)互信息3本章難點(diǎn)離散序列有記憶信源的熵42.1 信源的描述和分類信源信源產(chǎn)生消息(符號(hào))、消息序列和連續(xù)消息的來源產(chǎn)生隨機(jī)變量、隨機(jī)序列和隨機(jī)過程的源。在通信系統(tǒng)中收信者在未收到消息以前對(duì)信源發(fā)出什么消息是不確定的,是隨機(jī)的，所以可用隨機(jī)變量、隨機(jī)序列或隨機(jī)過程來描述信源輸出的消息,或者說用一個(gè)樣本空間及其概率測度概率空間來描述信源信源的基本特性：具有隨機(jī)不確定性。5香農(nóng)信息論的基本點(diǎn)用隨機(jī)變量或隨機(jī)矢量來表示信源用概率論和隨機(jī)

2、過程的理論來研究信息6信源的分類按照信源發(fā)出的消息在時(shí)間上和幅度上的分布情況可將信源分成離散信源和連續(xù)信源兩大類 7 信源離散信源: 文字、數(shù)據(jù)、電報(bào)隨機(jī)序列 連續(xù)信源: 話音、圖像隨機(jī)過程 連續(xù)信源指發(fā)出在時(shí)間和幅度上都是連續(xù)分布的連續(xù)消息（模擬消息）的信源，如語言、圖像、圖形等都是連續(xù)消息。 信源的分類離散信源指發(fā)出在時(shí)間和幅度上都是離散分布的離散消息的信源，如文字、數(shù)字、數(shù)據(jù)等符號(hào)都是離散消息。 8離散信源離散無記憶信源離散有記憶信源發(fā)出單個(gè)符號(hào)的無記憶信源發(fā)出符號(hào)序列的無記憶信源發(fā)出符號(hào)序列的有記憶信源發(fā)出符號(hào)序列的馬爾可夫信源2.1.1 無記憶信源離散無記憶信源所發(fā)出的各個(gè)符號(hào)是相互

3、獨(dú)立的，發(fā)出的符號(hào)序列中的各個(gè)符號(hào)之間沒有統(tǒng)計(jì)關(guān)聯(lián)性，各個(gè)符號(hào)的出現(xiàn)概率是它自身的先驗(yàn)概率。9例如扔骰子，每次試驗(yàn)結(jié)果必然是16點(diǎn)中的某一個(gè)面朝上。用一個(gè)離散型隨機(jī)變量X來描述這個(gè)信源輸出的消息。離散無記憶信源發(fā)出單個(gè)符號(hào)的信源指信源每次只發(fā)出一個(gè)符號(hào)代表一個(gè)消息；發(fā)出符號(hào)序列的信源指信源每次發(fā)出一組含二個(gè)以上符號(hào)的符號(hào)序列代表一個(gè)消息10信源的描述一個(gè)離散信源發(fā)出的各個(gè)符號(hào)消息的集合為：11它們的概率分別為p(xi): xi的先驗(yàn)概率單符號(hào)離散信源的數(shù)學(xué)模型概率空間a,b,c,z離散信源的統(tǒng)計(jì)特性離散消息是從有限個(gè)符號(hào)組成的符號(hào)集中選擇排列組成的隨機(jī)序列（組成離散消息的信息源的符號(hào)個(gè)數(shù)是有限

4、的） 在形成消息時(shí)，從符號(hào)集中選擇各個(gè)符號(hào)的概率不同 。組成消息的基本符號(hào)之間有一定的統(tǒng)計(jì)相關(guān)特性 。12信源的描述連續(xù)信源：輸出在時(shí)間和幅度上都是連續(xù)分布的消息 單符號(hào)連續(xù)無記憶信源的概率空間13 隨機(jī)取一節(jié)干電池測其電壓值作為輸出符號(hào),符號(hào)取值為0,1.5之間的所有實(shí)數(shù)。 該信源就是發(fā)出單符號(hào)的連續(xù)無記憶信源信源的描述發(fā)出符號(hào)序列的信源14設(shè)信源輸出的隨機(jī)序列為 X =(X1X2XlXL)序列中的變量Xlx1,x2, xn這種由信源X輸出的L長隨機(jī)序列X所描述的信源稱為離散無記憶信源X的L次擴(kuò)展信源 信源的描述隨機(jī)序列的概率15當(dāng)信源無記憶時(shí) 2.1.2 有記憶信源一般情況下,信源在不同時(shí)

5、刻發(fā)出的符號(hào)之間是相互依賴的，也就是信源輸出的平穩(wěn)隨機(jī)序列X中，各隨機(jī)變量Xl之間是有依賴的。如在漢字序列中前后文字的出現(xiàn)是有依賴的，不能認(rèn)為是彼此不相關(guān)的。表述有記憶信源要比表述無記憶信源困難得多離散有記憶信源所發(fā)出的各個(gè)符號(hào)的概率是有關(guān)聯(lián)的。發(fā)出符號(hào)序列的有記憶信源發(fā)出符號(hào)序列的馬爾可夫信源16用信源發(fā)出的一個(gè)符號(hào)序列的整體概率(即聯(lián)合概率)反映有記憶信源的特征一個(gè)符號(hào)出現(xiàn)的概率只與前面一個(gè)或有限個(gè)符號(hào)有關(guān),而不依賴更前面的那些符號(hào)概率論基礎(chǔ)無條件概率、條件概率、聯(lián)合概率的性質(zhì)和關(guān)系17概率論基礎(chǔ)無條件概率、條件概率、聯(lián)合概率的性質(zhì)和關(guān)系182.1.3 馬爾可夫信源馬爾可夫信源一類相對(duì)簡單

6、的離散平穩(wěn)信源該信源在某一時(shí)刻發(fā)出字母的概率除與該字母有關(guān)外,只與此前發(fā)出的有限個(gè)字母有關(guān)m階馬爾可夫信源：信源輸出某一符號(hào)的概率僅與以前的m個(gè)符號(hào)有關(guān)，而與更前面的符號(hào)無關(guān)。條件概率19馬氏鏈的基本概念 一階馬爾可夫信源：20若把有限個(gè)字母記作一個(gè)狀態(tài)S，則信源發(fā)出某一字母的概率除與該字母有關(guān)外，只與該時(shí)刻信源所處的狀態(tài)有關(guān)。信源將來的狀態(tài)及其送出的字母將只與信源現(xiàn)在的狀態(tài)有關(guān)，而與信源過去的狀態(tài)無關(guān)。馬氏鏈的基本概念 令si = (xi1, xi2, xim) xi1,xi2, xim (a1, a2, an)狀態(tài)集S = s1,s2,sQ Q = nm信源輸出的隨機(jī)符號(hào)序列為：x1, x

7、2,x i-1, x i信源所處的隨機(jī)狀態(tài)序列為：s1,s2,si-1 ,si,例：二元序列為01011100考慮m = 2，Q = nm =22= 4s1 = 00 s2 = 01 s3 = 10 s4 = 11變換成對(duì)應(yīng)的狀態(tài)序列為 s2 s3 s2 s4 s4 s3 s121馬爾可夫信源設(shè)信源在時(shí)刻m處于si狀態(tài),它在下一時(shí)刻(m+1)狀態(tài)轉(zhuǎn)移到sj的轉(zhuǎn)移概率為： pij(m) = pSm+1=sj| Sm= si=psj | sipij(m)：基本轉(zhuǎn)移概率（一步轉(zhuǎn)移概率）若pij(m)與m 的取值無關(guān),則稱為齊次馬爾可夫鏈 pij= pSm+1=sj| Sm= si= pS2=sj|

8、S1= sipij具有下列性質(zhì)： pij022若信源處于某一狀態(tài)si ,當(dāng)它發(fā)出一個(gè)符號(hào)后,所處狀態(tài)就變了,任何時(shí)候信源處于什么狀態(tài)完全由前一時(shí)刻的狀態(tài)和發(fā)出符號(hào)決定。 系統(tǒng)在任一時(shí)刻可處于狀態(tài)空間S = s1,s2,sQ中的任意一個(gè)狀態(tài),狀態(tài)轉(zhuǎn)移時(shí),轉(zhuǎn)移概率矩陣23符號(hào)條件概率矩陣?yán)?-1，如圖所示是一個(gè)相對(duì)碼編碼器,輸入的碼Xr(r=1,2,)是相互獨(dú)立的，取值0或1，且已知P(X=0)=p, P(X=1)=1p=q，輸出的碼是Yr，顯然24TXrYrYr-1+Yr是一個(gè)馬氏鏈,Yr確定后,Yr+1概率分布只與Yr有關(guān),與Yr-1 、Yr-2 等無關(guān),且知Yr序列的條件概率p00= P(Y

9、2=0/Y1=0)= P(X=0)= p p01= P(Y2=1/Y1=0)= P(X=1)= q p10= P(Y2=0/Y1=1)= P(X=1)= q p11= P(Y2=1/Y1=1)= P(X=0)= p 25sos1pqqp馬爾可夫信源狀態(tài)轉(zhuǎn)移圖齊次馬爾可夫鏈可以用其狀態(tài)轉(zhuǎn)移圖(香農(nóng)線圖)表示每個(gè)圓圈代表一種狀態(tài) 狀態(tài)之間的有向線代表某一狀態(tài)向另一狀態(tài)的轉(zhuǎn)移有向線一側(cè)的符號(hào)和數(shù)字分別代表發(fā)出的符號(hào)和條件概率26sos11/0.60/0.30/0.4s21/0.20/0.81/0.727s3s2s4s5s1s6周期性的：在常返態(tài)中,有些狀態(tài)僅當(dāng)k能被某整數(shù)d1整除時(shí)才有pij(k)0

10、,圖中的周期為2；x5:1非周期性的：對(duì)于pij(k)0的所有k值，其最大公約數(shù)為1。 常返態(tài)：經(jīng)有限步后遲早要返回的狀態(tài)，x4:1x3:1/2x2:1/2x3:1/2x2:1/2x2:1/2x4:1/4x1:1/4x6:1x6:1/4馬爾可夫信源遍歷狀態(tài)：非周期的、常返的狀態(tài),如圖中的狀態(tài)s2和s3閉集：狀態(tài)空間中的某一子集中的任何一狀態(tài)都不能到達(dá)子集以外的任何狀態(tài)不可約的：閉集中除自身全體外再?zèng)]有其他閉集的閉集28馬爾可夫信源一個(gè)不可約的、非周期的、狀態(tài)有限的馬爾可夫鏈其k步轉(zhuǎn)移概率pij(k)在k時(shí)趨于一個(gè)和初始狀態(tài)無關(guān)的極限概率Wj，它是滿足方程組 的唯一解；Wj ：馬爾可夫鏈的一個(gè)平

11、穩(wěn)分布， Wj p(sj)就是系統(tǒng)此時(shí)處于狀態(tài)sj的概率。29例30sos11/0.60/0.30/0.4s21/0.20/0.81/0.7例2-2：有一個(gè)二元二階馬爾可夫信源,其信源符號(hào)集為0，1，已知符號(hào)條件概率： p(0|00) = 1/2 p(1|00)=1/2 p(0|01) = 1/3 p(1|01)=2/3 p(0|10) = 1/4 p(1|10)=3/4 p(0|11) = 1/5 p(1|11)=4/5求：信源全部狀態(tài)及狀態(tài)轉(zhuǎn)移概率畫出完整的二階馬爾可夫信源狀態(tài)轉(zhuǎn)移圖。 求平穩(wěn)分布概率 3132狀態(tài)轉(zhuǎn)移概率矩陣符號(hào)條件概率矩陣(1)1/2(0)1/2(0)1/3(1)2/3

12、00011110s2s1s4s3(1)3/4(0)1/4(0)1/5(1)4/533穩(wěn)態(tài)分布概率穩(wěn)態(tài)后的符號(hào)概率分布例 一個(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.634p(x2|x1)再下一單位時(shí)間：輸出隨機(jī)變量X3與X2X1有依賴關(guān)系x3x1 x20001101100.40.20.30.410.60.80.70.6p(x3|x1x2)從第四單位時(shí)間開始，隨機(jī)變量Xi只與前面二個(gè)單位時(shí)間的隨機(jī)變量Xi-2Xi-1有依賴關(guān)系: p(xi| xi

13、-1 xi-2x2 x1) = p(xi| xi-1 xi-2) (i3) 且 p(xi| xi-1 xi-2) = p(x3| x2x1) (i3) 35解:設(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.6s1s2s0s6s5s4s3信源發(fā)完第2個(gè)符號(hào)后再發(fā)第3個(gè)及以后的符號(hào)。從第3單位時(shí)間以后信源必處在s3 s4 s5 s6四種狀態(tài)之一。在i3后,信源的狀態(tài)轉(zhuǎn)移可用下圖表示:3610110100(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功能是完全相同可將二圖合并成s3s4s5s6s0(0)0.5(1)0.5s0是過渡狀態(tài)s3 s