第二章信息與編碼

1、第二章第二章 離散信源及其信息測度離散信源及其信息測度 第一節(jié)第一節(jié) 信源的數(shù)學(xué)模型及分類信源的數(shù)學(xué)模型及分類 第二節(jié)第二節(jié) 離散信源的信息熵離散信源的信息熵 第三節(jié)第三節(jié) 信息熵的基本性質(zhì)信息熵的基本性質(zhì) 第四節(jié)第四節(jié) 離散無記憶的擴展信源離散無記憶的擴展信源 第五節(jié)第五節(jié) 離散平穩(wěn)信源離散平穩(wěn)信源 第六節(jié)第六節(jié) 馬爾可夫信源馬爾可夫信源 第七節(jié)第七節(jié) 信源剩余度與自然語言的熵信源剩余度與自然語言的熵 n 信源的主要問題信源的主要問題 1 1如何描述信源（信源的數(shù)學(xué)建模問題）描述信源（信源的數(shù)學(xué)建模問題） 2 2怎樣計算信源所含的信息量怎樣計算信源所含的信息量 3 3怎樣有效的表示信源輸出的

2、消息，也就是信源編碼問題怎樣有效的表示信源輸出的消息，也就是信源編碼問題 第一節(jié)第一節(jié) 信源的數(shù)學(xué)模型及分類信源的數(shù)學(xué)模型及分類 在通信系統(tǒng)中，收信者在未收到信息以前，對在通信系統(tǒng)中，收信者在未收到信息以前，對 信源發(fā)出什么樣的消息是不確定的，是隨機的，信源發(fā)出什么樣的消息是不確定的，是隨機的， 所以可以用隨機變量、隨機矢量或隨機過程來描所以可以用隨機變量、隨機矢量或隨機過程來描 述信源輸出的消息，或者說用一個述信源輸出的消息，或者說用一個樣本空間樣本空間及其及其 概率測度概率測度來描述信源。來描述信源。 不同的信源根據(jù)其輸出消息的不同的隨機性質(zhì)不同的信源根據(jù)其輸出消息的不同的隨機性質(zhì) 進行分

3、類。進行分類。 信源的定義及分類信源的定義及分類 n離散信源 n連續(xù)信源 n是指發(fā)出在時間和幅度上都是離散分布的離 是指發(fā)出在時間和幅度上都是離散分布的離 散消息的信源，如文字、數(shù)字、數(shù)據(jù)等符號散消息的信源，如文字、數(shù)字、數(shù)據(jù)等符號 都是離散消息。都是離散消息。 是指發(fā)出在時間和幅度上都是連續(xù)分布的連是指發(fā)出在時間和幅度上都是連續(xù)分布的連 續(xù)消息（模擬消息）的信源，如語言、圖像、續(xù)消息（模擬消息）的信源，如語言、圖像、 圖形等都是連續(xù)消息。圖形等都是連續(xù)消息。 第一節(jié)第一節(jié) 信源的數(shù)學(xué)模型及分類信源的數(shù)學(xué)模型及分類 1 1、離散信源、離散信源 數(shù)學(xué)模型如下：數(shù)學(xué)模型如下： 12 12 . .

4、q n aaxX pppP 1 1 q i i p 集合集合X X中，包含該信源包含的所有可能輸出中，包含該信源包含的所有可能輸出 的消息，集合的消息，集合P P中包含對應(yīng)消息的概率密度，各中包含對應(yīng)消息的概率密度，各 個消息的輸出概率總和應(yīng)該為個消息的輸出概率總和應(yīng)該為1 1。 例：天氣預(yù)報例：天氣預(yù)報 第一節(jié)第一節(jié) 信源的數(shù)學(xué)模型及分類信源的數(shù)學(xué)模型及分類 2 2、連續(xù)信源、連續(xù)信源 數(shù)學(xué)，模型如下：數(shù)學(xué)，模型如下： ( , ) ( )( ) Xa b p xp x ( )1 b a p x dx 每次只輸出一個消息，但消息的可能數(shù)目是無窮每次只輸出一個消息，但消息的可能數(shù)目是無窮 多個。

5、多個。 例：電壓、溫度等。例：電壓、溫度等。 發(fā)出單個符號的無記憶信源 離散無記憶信源 發(fā)出符號序列的無記憶信源 離散信源 發(fā)出符號序列的有記憶信源 離散有記憶信源 發(fā)出符號序列的馬兒可夫信源 離散信源的進一步分類離散信源的進一步分類 指信源每次只發(fā)出指信源每次只發(fā)出 一個符號代表一一個符號代表一 個消息個消息 指信源每次發(fā)出一指信源每次發(fā)出一 組含二個以上符號組含二個以上符號 的符號序列代表一的符號序列代表一 個消息個消息 n根據(jù)隨機變量間是否統(tǒng)計獨立將信源分為有記憶信源有記憶信源和無無 記憶信源記憶信源。 n離散無記憶信源 n離散有記憶信源 所發(fā)出的各個符號是相互獨立所發(fā)出的各個符號是相互

6、獨立 的，發(fā)出的符號序列中的各個的，發(fā)出的符號序列中的各個 符號之間沒有統(tǒng)計關(guān)聯(lián)性，各符號之間沒有統(tǒng)計關(guān)聯(lián)性，各 個符號的出現(xiàn)概率是它自身的個符號的出現(xiàn)概率是它自身的 先驗概率。先驗概率。 所發(fā)出的各個符號所發(fā)出的各個符號 的概率是有關(guān)聯(lián)的。的概率是有關(guān)聯(lián)的。 有記憶信源符號間的概率關(guān)聯(lián)性可用兩種方式：有記憶信源符號間的概率關(guān)聯(lián)性可用兩種方式： n一種是用信源發(fā)出的一個符號序列的整體概率（即聯(lián)合概率）一種是用信源發(fā)出的一個符號序列的整體概率（即聯(lián)合概率） 反映有記憶信源的特征反映有記憶信源的特征 n一種限制記憶長度，即某一個符號出現(xiàn)的概率只與前面一個一種限制記憶長度，即某一個符號出現(xiàn)的概率只與

7、前面一個 或有限個符號有關(guān)，而不依賴更前面的那些符號，這樣的信或有限個符號有關(guān)，而不依賴更前面的那些符號，這樣的信 源可以用信源發(fā)出符號序列內(nèi)各個符號之間的條件概率來反源可以用信源發(fā)出符號序列內(nèi)各個符號之間的條件概率來反 映記憶特征，這就是發(fā)出符號序列的映記憶特征，這就是發(fā)出符號序列的馬爾可夫信源馬爾可夫信源 n根據(jù)各維隨機變量的概率分布是否隨時間的推移而變化將根據(jù)各維隨機變量的概率分布是否隨時間的推移而變化將 信源分為平穩(wěn)信源和非平穩(wěn)信源信源分為平穩(wěn)信源和非平穩(wěn)信源 ( )( () 1 HNH X H H m X離散無記憶信源：） 記憶長度無限長： 離散平穩(wěn)信源 平穩(wěn)信源離散有記憶信源 記憶

8、長度有限馬爾可夫信源： 連續(xù)平穩(wěn)信源 非平穩(wěn)信源 離散信源分類 離散信源分類 離散信源分類 一個實際信源的統(tǒng)計特性往往是相當復(fù)雜 的，要想找到精確的數(shù)學(xué)模型很困難。實際應(yīng) 用時常常用一些可以處理可以處理的數(shù)學(xué)模型來近似。 隨機序列，特別是離散平穩(wěn)隨機序列是我們研 究的主要內(nèi)容。 第二節(jié)第二節(jié) 離散信源的信息熵離散信源的信息熵 1 1、自信息、自信息 我們認為，一個字符它所攜帶的信息量是和該字符出我們認為，一個字符它所攜帶的信息量是和該字符出 現(xiàn)的概率有關(guān)，概率可以表征自信息量的大小現(xiàn)的概率有關(guān)，概率可以表征自信息量的大小 ( ) ( ) ii I af P a 根據(jù)客觀事實和人們的習(xí)慣概念，應(yīng)

9、滿足根據(jù)客觀事實和人們的習(xí)慣概念，應(yīng)滿足 以下條件以下條件: : 第二節(jié)第二節(jié) 離散信源的信息熵離散信源的信息熵 （2 2）當）當( )1 i P a 時時( )0 i f P ( ) i f P （3 3）當）當 時時()0 i P a （4 4）兩個獨立事件的聯(lián)合信息量應(yīng)等于它們分別的信息量）兩個獨立事件的聯(lián)合信息量應(yīng)等于它們分別的信息量 之和。之和。 (1) (1) 應(yīng)是先驗概率的單調(diào)遞減函數(shù)，即當應(yīng)是先驗概率的單調(diào)遞減函數(shù)，即當 時時 () i f p 1122 ()()P aP a 12 ( )()f Pf P 第二節(jié)第二節(jié) 離散信源的信息熵離散信源的信息熵 根據(jù)上述條件可以從數(shù)學(xué)上

10、證明這種函數(shù)形式是對根據(jù)上述條件可以從數(shù)學(xué)上證明這種函數(shù)形式是對 數(shù)函數(shù)，即：數(shù)函數(shù)，即： 1 ( )log ( ) i i I a P a ( ) i I a有有兩個含義兩個含義： 1 1、當事件發(fā)生前，表示該事件發(fā)生的不確定性；、當事件發(fā)生前，表示該事件發(fā)生的不確定性； 2 2、當事件發(fā)生后，標是該事件所提供的信息量、當事件發(fā)生后，標是該事件所提供的信息量 自信息 第二節(jié)第二節(jié) 離散信源的信息熵離散信源的信息熵 例：設(shè)天氣預(yù)報有兩種消息，晴天和雨天，出現(xiàn)的概率例：設(shè)天氣預(yù)報有兩種消息，晴天和雨天，出現(xiàn)的概率 分別為分別為1/41/4和和3/43/4，我們分別用，我們分別用 來表示晴天，以來

11、表示晴天，以 來表示來表示 雨天，則我們的信源模型如下：雨天，則我們的信源模型如下： 1 a 2 a 1,2 ( )1/ 4,3/ 4 aaX p x 1 ( )log42I a 2 4 ()log0.415 3 I a 第二節(jié)第二節(jié) 離散信源的信息熵離散信源的信息熵 我們定義自信息的數(shù)學(xué)期望為信源的平均信息量我們定義自信息的數(shù)學(xué)期望為信源的平均信息量 1 1 ()log( )log( ) ( ) q ii i i H XEP aP a p a 信息熵具有以下兩種物理含義：信息熵具有以下兩種物理含義： 1 1、表示信源輸出前信源的平均不確定性、表示信源輸出前信源的平均不確定性 2 2、表示信源

12、輸出后，每個符號所攜帶的、表示信源輸出后，每個符號所攜帶的 平均信息量平均信息量 2 2、信息熵、信息熵 例：天氣預(yù)報，有兩個信源例：天氣預(yù)報，有兩個信源 1,21 ( )1/4,3/4 aaX p x 1,22 ( )1/2,1/2 aaX p x 1 134 ()log4log0.809 443 H X 2 11 ()log2log21 22 H X 則：則： 說明第二個信源的平均不確定性更大一些說明第二個信源的平均不確定性更大一些 第二節(jié)第二節(jié) 離散信源的信息熵離散信源的信息熵 第三節(jié)第三節(jié) 信息熵的基本性質(zhì)信息熵的基本性質(zhì) 熵函數(shù)可以表示為：熵函數(shù)可以表示為： HXHppppp nii

13、 i n ()(,)lo g 12 1 ppin i i n i 1 101 2,(, ,.,) 第三節(jié)第三節(jié) 信息熵的基本性質(zhì)信息熵的基本性質(zhì) 性質(zhì)性質(zhì)1 1：非負性：非負性 H(X)0H(X)0 由于由于0pi1,0pi1,所以所以logpi0logpi0， logpi0logpi0，則總有，則總有H(X)0H(X)0。 性質(zhì)性質(zhì)2 2：對稱性：對稱性 H pppH pppp nnn (,.)(,.) 12121 根據(jù)加法交換律可以證明，當變量交換順序時熵函數(shù)的根據(jù)加法交換律可以證明，當變量交換順序時熵函數(shù)的 值不變。值不變。 信源的熵只與概率空間的總體結(jié)構(gòu)有關(guān)，而與個概率分信源的熵只與概

14、率空間的總體結(jié)構(gòu)有關(guān)，而與個概率分 量對應(yīng)的狀態(tài)順序無關(guān)；量對應(yīng)的狀態(tài)順序無關(guān)； 第三節(jié)第三節(jié) 信息熵的基本性質(zhì)信息熵的基本性質(zhì) 性質(zhì)性質(zhì)3 3：確定性；：確定性； HHH( , )( , )( , , ,. )1 00 11 0 000 當信源當信源X X的信源空間的信源空間XX，PP中。任一個概率分量等于中。任一個概率分量等于1 1， 根據(jù)完備空間特性，其它概率分量必為根據(jù)完備空間特性，其它概率分量必為0 0，這時信源為，這時信源為 一個確知信源，其熵為一個確知信源，其熵為0 0。 如果一個信源的輸出符號幾乎必然為某一狀態(tài)，那么這如果一個信源的輸出符號幾乎必然為某一狀態(tài)，那么這 個信源沒有

15、不確定性，信源輸出符號后不提供任何信息個信源沒有不確定性，信源輸出符號后不提供任何信息 量。量。 第三節(jié)第三節(jié) 信息熵的基本性質(zhì)信息熵的基本性質(zhì) 性質(zhì)性質(zhì)4 4：擴展性：擴展性 11212 0 lim(,., )(,.,) qqqq Hp ppHp pp 這說明信源空間中增加某些概率很小的符號，雖這說明信源空間中增加某些概率很小的符號，雖 然當發(fā)出這些符號時，提供很大的信息量，但由于其然當發(fā)出這些符號時，提供很大的信息量，但由于其 概率接近于概率接近于0 0，在信源熵中占極小的比重，使信源熵，在信源熵中占極小的比重，使信源熵 保持不變。保持不變。 第三節(jié)第三節(jié) 信息熵的基本性質(zhì)信息熵的基本性質(zhì)

16、 性質(zhì)性質(zhì)5 5 ：極值性：極值性 12 ( ,.,)(1/ ,1/ ,.,1/ )log q H p ppHqqqq 上式表明，對于具有上式表明，對于具有q q個符號的離散信源，只有在個符號的離散信源，只有在 q q個信源符號等可能出現(xiàn)的情況下，信源熵才能達到個信源符號等可能出現(xiàn)的情況下，信源熵才能達到 最大值，這也表明等概分布的信源的平均不確定性最最大值，這也表明等概分布的信源的平均不確定性最 大，這是一個很重要得結(jié)論，稱為大，這是一個很重要得結(jié)論，稱為最大離散熵定理最大離散熵定理 例：對于一個二元信源例：對于一個二元信源 H(X)=H(1/2,1/2)=log2=1bitH(X)=H(1

17、/2,1/2)=log2=1bit 第四節(jié)第四節(jié) 離散無記憶的擴展信源離散無記憶的擴展信源 實際信源輸出的消息往往是時間上或空間上的一系實際信源輸出的消息往往是時間上或空間上的一系 列符號，如電報系統(tǒng)，序列中前后符號間一般是有統(tǒng)列符號，如電報系統(tǒng)，序列中前后符號間一般是有統(tǒng) 計依賴關(guān)系的。計依賴關(guān)系的。 我們先討論離散無記憶信源，此時，信源序列的前我們先討論離散無記憶信源，此時，信源序列的前 后符號之間是統(tǒng)計獨立的后符號之間是統(tǒng)計獨立的 如在二元系統(tǒng)中，我們可以把兩個二元數(shù)字看成一如在二元系統(tǒng)中，我們可以把兩個二元數(shù)字看成一 組，會出現(xiàn)四種可能情況：組，會出現(xiàn)四種可能情況：0000、0101、

18、1010和和1111，我們可，我們可 以把這四種情況看成一個新的信源稱為以把這四種情況看成一個新的信源稱為二元無記憶信二元無記憶信 源的二次擴展信源源的二次擴展信源，相應(yīng)的，如果把，相應(yīng)的，如果把N N個二元數(shù)字看個二元數(shù)字看 成一組，則新的信源稱為成一組，則新的信源稱為二元無記憶信源的二元無記憶信源的N N此擴展此擴展 信源。信源。 第四節(jié)第四節(jié) 離散無記憶的擴展信源離散無記憶的擴展信源 一般情況一般情況 設(shè)一個離散無記憶信源為：設(shè)一個離散無記憶信源為： pi i n 1 1 12 12 . ()().() N N N q q X pppP 則該信源的則該信源的N N次擴展信源為：次擴展信源

19、為： 12 12 . . q n aaxX pppP 第四節(jié)第四節(jié) 離散無記憶的擴展信源離散無記憶的擴展信源 其中：其中： 12 ()() (). () iiiiN PP aP aP a 根據(jù)信息熵的定義：根據(jù)信息熵的定義： ()()log() N NNN X H XP XP X 可以證明，對于離散無記憶的擴展信源可以證明，對于離散無記憶的擴展信源 ()() N H XNH X 例例: : 離散無記憶信源的離散無記憶信源的N N次擴展信源次擴展信源 離散無記憶信源為：離散無記憶信源為：X:a1,a2,a3; P(X):1/4, 1/2, 1/4X:a1,a2,a3; P(X):1/4, 1/2

20、, 1/4 2 2次擴展信源為：次擴展信源為： 2 X :A1A9:A1A9 信源的信源的9 9個符號為：個符號為： 第四節(jié)第四節(jié) 離散無記憶的擴展信源離散無記憶的擴展信源 第四節(jié)第四節(jié) 離散無記憶的擴展信源離散無記憶的擴展信源 其概率關(guān)系為其概率關(guān)系為 : : 計算可知計算可知 2 ()3H Xbit ()1.5H Xbit 2 ()2()H XH X 第五節(jié)第五節(jié) 離散平穩(wěn)信源離散平穩(wěn)信源 一般來說，信源的前后消息之間有前后依賴關(guān)系，一般來說，信源的前后消息之間有前后依賴關(guān)系， 可以用隨機矢量描述：可以用隨機矢量描述： 12 (.,.,.) i XXXX 信源在某一時刻發(fā)出什么樣的值取決于

21、兩方面信源在某一時刻發(fā)出什么樣的值取決于兩方面 1 1、這一時刻該變量的分布概率、這一時刻該變量的分布概率 2 2、這一時刻以前發(fā)出的消息、這一時刻以前發(fā)出的消息 如一個人講話如一個人講話 我們現(xiàn)在討論我們現(xiàn)在討論平穩(wěn)的平穩(wěn)的隨機序列，隨機序列，所謂平穩(wěn)是指序所謂平穩(wěn)是指序 列的統(tǒng)計性質(zhì)與時間的推移無關(guān)列的統(tǒng)計性質(zhì)與時間的推移無關(guān)（倆個任意時刻（倆個任意時刻 信源發(fā)出符號的概率分布完全相同）。信源發(fā)出符號的概率分布完全相同）。 1 1、離散平穩(wěn)信源的數(shù)學(xué)定義、離散平穩(wěn)信源的數(shù)學(xué)定義 第五節(jié)第五節(jié) 離散平穩(wěn)信源離散平穩(wěn)信源 2 2、二維平穩(wěn)信源及其信息熵、二維平穩(wěn)信源及其信息熵 最簡單的平穩(wěn)信源

22、最簡單的平穩(wěn)信源二維平穩(wěn)信源，信源發(fā)出序列二維平穩(wěn)信源，信源發(fā)出序列 中只有前后兩個符號間有依賴關(guān)系，我們可以對其二維中只有前后兩個符號間有依賴關(guān)系，我們可以對其二維 擴展信源進行分析。擴展信源進行分析。 信源的概率空間信源的概率空間: : 連續(xù)兩個信源符號出現(xiàn)的聯(lián)合概率分布為：連續(xù)兩個信源符號出現(xiàn)的聯(lián)合概率分布為： 12 12 , ()1 (),(),()() q i q aaaX p a p ap ap aP X q i=1 且 1 ()()1 qq ijij j P a aP a a i=1 且 第五節(jié)第五節(jié) 離散平穩(wěn)信源離散平穩(wěn)信源 已知符號已知符號 出現(xiàn)后，緊跟著出現(xiàn)后，緊跟著 出現(xiàn)

23、的條件概率為：出現(xiàn)的條件概率為： i a j a () (|) () ij ji i Pa a Paa Pa 由二維離散信源的發(fā)出符號序列的特點可以把其分由二維離散信源的發(fā)出符號序列的特點可以把其分 成每兩個符號一組，每組代表新信源成每兩個符號一組，每組代表新信源 中的一個中的一個 符號。并假設(shè)組與組之間是統(tǒng)計獨立的，互不相關(guān)的。符號。并假設(shè)組與組之間是統(tǒng)計獨立的，互不相關(guān)的。 12 XX X 得到一個新的離散無記憶信源得到一個新的離散無記憶信源 ，其聯(lián)合概率空間為：，其聯(lián)合概率空間為： 12 X X 12 12 () X X P x x 11121 ,., ()() (|) qqqq iji

24、ji a a a aaaa a P a aP a P aa 第五節(jié)第五節(jié) 離散平穩(wěn)信源離散平穩(wěn)信源 12 11 ()()log () qq ijij ij H X XP a aP a a 根據(jù)信息熵的定義，可得：根據(jù)信息熵的定義，可得： （1 1）聯(lián)合熵聯(lián)合熵 可以表征信源輸出長度為可以表征信源輸出長度為2 2的平均不確定性，或所含的平均不確定性，或所含 有的信息量。因此可以用有的信息量。因此可以用 作為二維平穩(wěn)作為二維平穩(wěn) 信源的信息熵的近似值信源的信息熵的近似值 12 1/2()H X X 第五節(jié)第五節(jié) 離散平穩(wěn)信源離散平穩(wěn)信源 (2)(2)條件熵條件熵 21 1 (|)(|)log(|)

25、 q ijiji j H XXaP aaP aa 則：則： 2121 1 (|)()(|) q ii i H XXP a H XXa 11 () (|)log(|) qq ijiji ij P a P aaP aa 11 ()log(|) qq ijji ij P a aP aa 第五節(jié)第五節(jié) 離散平穩(wěn)信源離散平穩(wěn)信源 另外還可以得到：另外還可以得到： 21 (|)()H XXH X 1212 ()()()2()H X XH XH XH X 只有信源統(tǒng)計獨立時等號成立。只有信源統(tǒng)計獨立時等號成立。 可以證明：可以證明： 12121 ()()(|)H X XH XH XX 例例2-15 2-15

26、 設(shè)某二維離散信源的原始信源的信源空間設(shè)某二維離散信源的原始信源的信源空間 X=x1,x2,x3; P(X)=1/4, 1/4, 1/2, X=x1,x2,x3; P(X)=1/4, 1/4, 1/2, 一維條件概率為：一維條件概率為： p(x1/x1)=1/2; p(x2/x1)=1/2; p(x3/x1)=0;p(x1/x1)=1/2; p(x2/x1)=1/2; p(x3/x1)=0; p(x1/x2)=1/8; p(x2/x2)=3/4; p(x3/x2)=1/8;p(x1/x2)=1/8; p(x2/x2)=3/4; p(x3/x2)=1/8; p(x1/x3)=0; p(x2/x3

27、)=1/4; p(x3/x3)=3/4;p(x1/x3)=0; p(x2/x3)=1/4; p(x3/x3)=3/4; 原始信源的熵為：原始信源的熵為： H(X)=1.5 bit/H(X)=1.5 bit/符號符號 條件熵：條件熵： H(X2/X1)=1.4 bit/H(X2/X1)=1.4 bit/符號符號 可見：可見： H(X2/X1)H(X)H(X2/X1)H(X) 二維信源的熵：二維信源的熵：H(X1,X2)=H(X1)+H(X2/X1)=2.9 bit/H(X1,X2)=H(X1)+H(X2/X1)=2.9 bit/消息消息 每個信源符號提供的平均信息量為：每個信源符號提供的平均信息

28、量為： H2(X1,X2)=H(X1,X2)/2=1.45 bit/H2(X1,X2)=H(X1,X2)/2=1.45 bit/符號。符號。 第五節(jié)第五節(jié) 離散平穩(wěn)信源離散平穩(wěn)信源 第五節(jié)第五節(jié) 離散平穩(wěn)信源離散平穩(wěn)信源 我們現(xiàn)在有兩種方法去近似信源的實際熵，一種是我們現(xiàn)在有兩種方法去近似信源的實際熵，一種是 為為1.45bit1.45bit，但這種方法不太準確，因為它把兩個消息，但這種方法不太準確，因為它把兩個消息 看成一組，認為兩組之間是統(tǒng)計獨立的，實際上它們看成一組，認為兩組之間是統(tǒng)計獨立的，實際上它們 之間是有關(guān)聯(lián)的；另一種是我們可以用條件熵來近似，之間是有關(guān)聯(lián)的；另一種是我們可以用條

29、件熵來近似， 為為1.4bit1.4bit，到底那一種正確呢？我們可以通過對一般離，到底那一種正確呢？我們可以通過對一般離 散平穩(wěn)信源的分析來找到這個答案。散平穩(wěn)信源的分析來找到這個答案。 12 1/2()H X X 分析：我們用分析：我們用 2( )HX來近似信源的實際熵來近似信源的實際熵 第五節(jié)第五節(jié) 離散平穩(wěn)信源離散平穩(wěn)信源 3 3、離散平穩(wěn)信源的極限熵、離散平穩(wěn)信源的極限熵 平均符號熵平均符號熵 12 1 ()(.) NN HXH X XX N 條件熵條件熵 121 (|.) NN H XX XX 有以下幾點性質(zhì)有以下幾點性質(zhì) （1 1）條件熵隨）條件熵隨N N的增加是非遞增的的增加是

30、非遞增的 （2 2）N N給定時，平均符號熵大于等于條件熵給定時，平均符號熵大于等于條件熵 （3 3）平均符號熵隨）平均符號熵隨N N的增加是非遞增的的增加是非遞增的 （4 4） 121 lim()lim(|.) NNN NN HHXH XX XX H稱稱 為為極限熵極限熵。 第五節(jié)第五節(jié) 離散平穩(wěn)信源離散平穩(wěn)信源 可以證明，對于二維離散平穩(wěn)信源，條件熵等于極可以證明，對于二維離散平穩(wěn)信源，條件熵等于極 限熵，因此條件熵就是二維離散平穩(wěn)信源的真實熵限熵，因此條件熵就是二維離散平穩(wěn)信源的真實熵 對于一般信源，求出極限熵是很困難的，然而，一對于一般信源，求出極限熵是很困難的，然而，一 般來說，取般

31、來說，取N N不大時就可以得到與極限熵非常接近的條不大時就可以得到與極限熵非常接近的條 件熵和平均符號熵，因此可以用條件熵和平均符號熵件熵和平均符號熵，因此可以用條件熵和平均符號熵 來近似極限熵來近似極限熵 第六節(jié)第六節(jié) 馬爾可夫信源馬爾可夫信源 在很多信源的輸出序列中，符號之間的依賴關(guān)系是在很多信源的輸出序列中，符號之間的依賴關(guān)系是 有限的，任何時刻信源符號發(fā)生的概率只與前邊已經(jīng)發(fā)有限的，任何時刻信源符號發(fā)生的概率只與前邊已經(jīng)發(fā) 出的若干個符號有關(guān)，而與更前面的符號無關(guān)。出的若干個符號有關(guān)，而與更前面的符號無關(guān)。 為了描述這類信源除了信源符號集外還要引入狀態(tài)為了描述這類信源除了信源符號集外還

32、要引入狀態(tài) 集。這時，信源輸出消息符號還與信源所處的狀態(tài)有關(guān)。集。這時，信源輸出消息符號還與信源所處的狀態(tài)有關(guān)。 若一個信源滿足下面兩個條件，則稱為馬爾可夫信源：若一個信源滿足下面兩個條件，則稱為馬爾可夫信源： （1 1）某一時刻信源輸出的符號的概率只與當前所處的）某一時刻信源輸出的符號的概率只與當前所處的 狀態(tài)有關(guān)，而與以前的狀態(tài)無關(guān)；狀態(tài)有關(guān)，而與以前的狀態(tài)無關(guān)； （2 2）信源的下一個狀態(tài)由當前狀態(tài)和下一刻的輸出唯）信源的下一個狀態(tài)由當前狀態(tài)和下一刻的輸出唯 一確定。一確定。 設(shè)某二階馬爾可夫信源所處的狀態(tài) E=E0,E1,E2,E3=00，01，10，11 ，在每一狀 態(tài)下可能輸出的符

33、號0，1。 0 0 1 0 1 1 0 0 1 1 0 1 0 E0=00 1 E1=01 0 E2=10 1 E1=01 1 E3=11 0 E2=10 P(1/E0)= P(E1/E0)=P01 第六節(jié)第六節(jié) 馬爾可夫信源馬爾可夫信源 （1 1）某一時刻信源輸出的符號的概率只與當前所處的狀態(tài)有）某一時刻信源輸出的符號的概率只與當前所處的狀態(tài)有 關(guān)，而與以前的狀態(tài)無關(guān)。即關(guān)，而與以前的狀態(tài)無關(guān)。即 1 11 (|, )(|) lklilkljlkli P xa sE xa sEP xa sE 當符號輸出概率與時刻當符號輸出概率與時刻L L無關(guān)，稱為具有時齊性。即無關(guān)，稱為具有時齊性。即 (|

34、)(|),(|)1 k lklikiki aA P xasEP aEP aE 第六節(jié)第六節(jié) 馬爾可夫信源馬爾可夫信源 （2 2）信源的下一個狀態(tài)由當前狀態(tài)和下一刻的輸出唯一確定。）信源的下一個狀態(tài)由當前狀態(tài)和下一刻的輸出唯一確定。 條件（條件（2 2）表明，若信源處于某一狀態(tài)）表明，若信源處于某一狀態(tài) ，當它發(fā)出，當它發(fā)出 一個符號后，所處的狀態(tài)就變了，一定轉(zhuǎn)移到另一狀態(tài)。一個符號后，所處的狀態(tài)就變了，一定轉(zhuǎn)移到另一狀態(tài)。 狀態(tài)的轉(zhuǎn)狀態(tài)的轉(zhuǎn) 移依賴于發(fā)出的信源符號，因此任何時刻信源處移依賴于發(fā)出的信源符號，因此任何時刻信源處 在什么狀態(tài)完全由前一時刻的狀態(tài)和發(fā)出的符號決定。在什么狀態(tài)完全由前一

35、時刻的狀態(tài)和發(fā)出的符號決定。 i E 第六節(jié)第六節(jié) 馬爾可夫信源馬爾可夫信源 例：二階馬爾可夫信源，原始符號集為例：二階馬爾可夫信源，原始符號集為1,01,0， 條件概率定為：條件概率定為：P(0|00)=P(1|11)=0.8P(0|00)=P(1|11)=0.8 P(1|00)=P(0|11)=0.2 P(1|00)=P(0|11)=0.2 P(0|01)=P(0|10)=P(1|01)=P(1|10)=0.5 P(0|01)=P(0|10)=P(1|01)=P(1|10)=0.5 由此可見，信源共有由此可見，信源共有22=422=4種狀態(tài)種狀態(tài) E E：e1=00,e2=01,e3=10

36、,e4=11e1=00,e2=01,e3=10,e4=11 第六節(jié)第六節(jié) 馬爾可夫信源馬爾可夫信源 狀態(tài)之間有轉(zhuǎn)移概率，狀態(tài)之間有轉(zhuǎn)移概率， p(e2/e1)=p(e3/e4)=0.2p(e2/e1)=p(e3/e4)=0.2 p(e2/e4)=p(e1/e3)=p(e2/e3)=p(e3/e2)=0.5p(e2/e4)=p(e1/e3)=p(e2/e3)=p(e3/e2)=0.5 P(e1/e1)=p(e4/e4)=0.8P(e1/e1)=p(e4/e4)=0.8 其狀態(tài)轉(zhuǎn)移圖如下頁。在狀態(tài)轉(zhuǎn)換圖中，把信源的每一種狀其狀態(tài)轉(zhuǎn)移圖如下頁。在狀態(tài)轉(zhuǎn)換圖中，把信源的每一種狀 態(tài)用圓圈表示，用有向箭

37、頭表示信源發(fā)出某一符號后由一種態(tài)用圓圈表示，用有向箭頭表示信源發(fā)出某一符號后由一種 狀態(tài)到另一狀態(tài)的轉(zhuǎn)移。狀態(tài)到另一狀態(tài)的轉(zhuǎn)移。 第六節(jié)第六節(jié) 馬爾可夫信源馬爾可夫信源 01 01 10 10 0:0.50:0.5 1:0.21:0.2 0:0.20:0.2 00 00 0:0.80:0.8 11 11 1:0.81:0.8 1:0.51:0.5 0:0.50:0.5 1:0.51:0.5 由上例可知，由上例可知，m m階馬爾可夫信源符號集共有階馬爾可夫信源符號集共有q q個符號，則個符號，則 信源共有信源共有 個不同狀態(tài)。信源在某一時刻時，必然處于某一個不同狀態(tài)。信源在某一時刻時，必然處于某

38、一 種狀態(tài)，等到下一個字符輸出時，轉(zhuǎn)移到另外一個狀態(tài)。種狀態(tài)，等到下一個字符輸出時，轉(zhuǎn)移到另外一個狀態(tài)。 m q 舉舉 例例 例例2.2.3 2.2.3 設(shè)信源符號設(shè)信源符號 X Xx x1 1, , x x2 2, , x x3 3 ，信源所處的狀態(tài)，信源所處的狀態(tài)S Se e1 1, , e e2 2, , e e3 3, , e e4 4, , e e5 5 。各狀態(tài)之間的轉(zhuǎn)移情況由圖。各狀態(tài)之間的轉(zhuǎn)移情況由圖2.2.12.2.1給出。給出。 將圖中信源在將圖中信源在e ei i狀態(tài)下發(fā)符號狀態(tài)下發(fā)符號x xk k 的條件概率的條件概率p p( (x xk k / /e ei i) )用

39、矩陣表示用矩陣表示 由矩陣看出：由矩陣看出： 由圖中看出：由圖中看出： 由圖中可得狀態(tài)的一步轉(zhuǎn)移概率：由圖中可得狀態(tài)的一步轉(zhuǎn)移概率： 該信源滿足馬爾可夫信源定義。該信源滿足馬爾可夫信源定義。 2 1 4 1 2 1 4 1 4 1 4 3 2 1 4 1 4 1 2 1 5 4 3 2 1 321 001 0 0 e e e e e xxx 3 1 5 , 4 , 3 , 2 , 1, 1)/( k ik iexp 0),/( 1),/( 1),/( 0),/( 1123 1122 1111 1112 eSxXeSP eSxXeSP eSxXeSP eSxXeSP lll lll lll ll

40、l 4 1 4 3 4 1 4 3 2 1 2 1 4 1 4 1 2 1 5 4 3 2 1 000 00000 000 000 00 54321 e e e e e eeeee 第六節(jié)第六節(jié) 馬爾可夫信源馬爾可夫信源 定義定義 為各狀態(tài)的極限概率，則時齊、遍歷的馬爾可為各狀態(tài)的極限概率，則時齊、遍歷的馬爾可 夫信源的熵為夫信源的熵為 () i Q E 1 ()(|) J ii i HQ E H X E 11 () (|)log(|) qJ ikiki ik Q E P aEP aE 第六節(jié)第六節(jié) 馬爾可夫信源馬爾可夫信源 馬爾可夫信源的熵：馬爾可夫信源的熵： 這里這給出結(jié)論：這里這給出結(jié)論

41、： 112 (|.) mm HHXX XX 表明表明m m階馬爾可夫信源的極限熵等于階馬爾可夫信源的極限熵等于m m階條件熵。階條件熵。 根據(jù)求條件熵公式還可得到根據(jù)求條件熵公式還可得到 1 11 ( ) (| )log ( | ) mm qq mijiji ij HHp e p e ep e e (3) (3) 舉舉 例例 例例2.2.4 2.2.4 二元二元2 2階馬爾可夫信源，原始信號階馬爾可夫信源，原始信號X X的符號集為的符號集為 X X1 1=0, =0, X X2 2=1=1，其狀態(tài)空間共有，其狀態(tài)空間共有n nm m=2=22 2=4=4個不同的狀態(tài)個不同的狀態(tài)e e1 1,

42、,e e2 2, ,e e3 3, ,e e4 4，即，即 E E： e e1 1=00,=00,e e2 2=01,=01,e e3 3=10,=10,e e4 4=11=11 狀態(tài)轉(zhuǎn)移圖見右圖所示。狀態(tài)轉(zhuǎn)移圖見右圖所示。 解：解：p p( (e e1 1/ /e e1 1)= )= p p( (x x1 1/ /e e1 1)=)=p p(0/00)=0.8(0/00)=0.8 p p( (e e2 2/ /e e1 1)= )= p p( (x x2 2/ /e e1 1)=)=p p(1/00)=0.2(1/00)=0.2 p p( (e e3 3/ /e e2 2)= )= p p(

43、 (x x1 1/ /e e2 2)=)=p p(0/01)=0.5(0/01)=0.5 p p( (e e4 4/ /e e2 2)= )= p p( (x x2 2/ /e e2 2)=)=p p(1/01)=0.5(1/01)=0.5 p p( (e e1 1/ /e e3 3)= )= p p( (x x1 1/ /e e3 3)=)=p p(0/10)=0.5(0/10)=0.5 p p( (e e2 2/ /e e3 3)= )= p p( (x x2 2/ /e e3 3)=)=p p(1/10)=0.5(1/10)=0.5 p p( (e e3 3/ /e e4 4)= )=

44、p p( (x x1 1/ /e e4 4)=)=p p(0/11)=0.2(0/11)=0.2 p p( (e e4 4/ /e e4 4)= )= p p( (x x2 2/ /e e4 4)=)=p p(1/11)=0.8(1/11)=0.8 由二元信源由二元信源X X0,10,1得到的狀態(tài)空間得到的狀態(tài)空間( (e e1 1, ,e e2 2, ,e e3 3, ,e e4 4) )和相應(yīng)的一和相應(yīng)的一 步轉(zhuǎn)移概率構(gòu)成的步轉(zhuǎn)移概率構(gòu)成的2 2階馬爾可夫信源模型為階馬爾可夫信源模型為 求出穩(wěn)定狀態(tài)下的求出穩(wěn)定狀態(tài)下的p p( (e ej j) ) ，稱為，稱為狀態(tài)極限概率狀態(tài)極限概率。

45、將一步轉(zhuǎn)移概率代入上式得將一步轉(zhuǎn)移概率代入上式得 p p( (e e1 1)=0.8 )=0.8 p p( (e e1 1)+0.5 )+0.5 p p( (e e3 3) ) p p( (e e2 2)=0.2 )=0.2 p p( (e e1 1)+0.5 )+0.5 p p( (e e3 3) ) p p( (e e3 3)=0.5 )=0.5 p p( (e e2 2)+0.2 )+0.2 p p( (e e4 4) ) p p( (e e4 4)=0.5 )=0.5 p p( (e e2 2)+0.8 )+0.8 p p( (e e4 4) ) 4 , 3 , 2 , 1)/()()

46、( 0)(, 1)/( 4 , 3 , 2 , 1, )/( 4 1 4 1 4321 jeepepep epeep ji eep eeee i ijij i j ij ij 由 且 解方程組得解方程組得 p p( (e e1 1)= )= p p( (e e4 4)=5/14)=5/14 p p( (e e2 2)= )= p p( (e e3 3)=2/14)=2/14 計算極限熵計算極限熵 )/(8 . 0)/(log)/()( 2 4 1 4 1 12 符號比特 ij ij iji eepeepepHH 第六節(jié)第六節(jié) 馬爾可夫信源馬爾可夫信源 例：一個二元二階馬爾可夫信源，信源符號集例

47、：一個二元二階馬爾可夫信源，信源符號集A=0,1A=0,1。 信源開始時，它以概率信源開始時，它以概率p(0)=p(1)=0.5p(0)=p(1)=0.5發(fā)出隨機變量發(fā)出隨機變量X1X1。 然后，下一單位時間輸出的隨機變量然后，下一單位時間輸出的隨機變量X2X2與與X1X1有依賴關(guān)有依賴關(guān) 系，由條件概率系，由條件概率p(x2|x1)p(x2|x1)表示：表示： 再下一單元時間輸出隨機變量再下一單元時間輸出隨機變量X3X3，而，而X3X3依賴于前面變依賴于前面變 量。依賴關(guān)系由條件概率量。依賴關(guān)系由條件概率p(x3|x1x2)p(x3|x1x2)表示：表示： 第六節(jié)第六節(jié) 馬爾可夫信源馬爾可夫信源 由從第四單位時間開始，任意時刻信源發(fā)出的隨機變量由從第四單位時間