信息論信源及信息熵

1、第3章 信源及信源熵 重慶交通大學(xué)計算機(jī)與信息學(xué)院通信工程系李益才2012年8月信息論信源及信息熵第3章 信源及信息熵3.1 信源的分類及其數(shù)學(xué)模型3.2 離散單符號信源 3.3 離散多符號信源 3.4 * 連續(xù)信源 第3章 信源及信息熵信源(Information Source)是信息的來源，是產(chǎn)生消息（符號）、時間離散的消息序列（符號序列）以及時間連續(xù)的消息的來源。信源輸出的消息都是隨機(jī)的，因此可用概率來描述其統(tǒng)計特性。在信息論中，用隨機(jī)變量X、隨機(jī)矢量X、隨機(jī)過程 X(e,t)分別表示產(chǎn)生消息、消息序列以及時間連續(xù)消息的信源。信源的主要問題：p如何描述信源（信源的數(shù)學(xué)建模問題）如何描述信

2、源（信源的數(shù)學(xué)建模問題）p怎樣計算信源所含的信息量怎樣計算信源所含的信息量 p怎樣有效的表示信源輸出的消息，也就是信源編碼問題怎樣有效的表示信源輸出的消息，也就是信源編碼問題 3.1 信源的分類及其數(shù)學(xué)模型信源的分類及其數(shù)學(xué)模型信源的分類由多種方法，我們常根據(jù)信源輸出的消息在時間和取值上是離散或連續(xù)進(jìn)行分類：時間（空間時間（空間)取值取值信源種類信源種類舉例舉例數(shù)學(xué)描述數(shù)學(xué)描述離散離散離散信源（數(shù)字信源）文字、數(shù)據(jù)、離散化圖象 離散隨機(jī)變量序列 離散連續(xù)連續(xù)信號跳遠(yuǎn)比賽的結(jié)果、語音信號抽樣以后 連續(xù)隨機(jī)變量序列 連續(xù)連續(xù)波形信源（模擬信源） 語音、音樂、熱噪聲、圖形、圖象 隨機(jī)過程 連續(xù)離散不

3、常見表表3.1 信源的分類信源的分類3.1 信源的分類及其數(shù)學(xué)模型信源的分類及其數(shù)學(xué)模型我們還可以根據(jù)各維隨機(jī)變量的概率分布是否隨時間的推移而變化將信源分為平穩(wěn)信源和非平穩(wěn)信源，根據(jù)隨機(jī)變量間是否統(tǒng)計獨立將信源分為有記憶信源和無記憶信源。一個實際信源的統(tǒng)計特性往往是相當(dāng)復(fù)雜的，要想找到精確的數(shù)學(xué)模型很困難。實際應(yīng)用時常常用一些可以處理的數(shù)學(xué)模型來近似。隨機(jī)序列，特別是離散平穩(wěn)隨機(jī)序列是我們研究的主要內(nèi)容。( )( ()1HNH XHHmX離散無記憶信源：）記憶長度無限長：離散平穩(wěn)信源平穩(wěn)信源離散有記憶信源記憶長度有限 馬爾可夫信源 ：連續(xù)平穩(wěn)信源非平穩(wěn)信源隨機(jī)序列3.2 離散單符號信源離散單符

4、號信源 輸出單個離散取值的符號的信源稱為離散單符號信源。它是最簡單也是最基本的信源，是組成實際信源的基本單元。它用一個離散隨機(jī)變量表示。信源所有可能輸出的消息和消息對應(yīng)的概率共同組成的二元序?qū),P(X) 稱為信源的概率空間：信源輸出的所有消息的自信息的統(tǒng)計平均值定義為信源的平均自信息量（信息熵），它表示離散單符號信源的平均不確定性： 11()( )()iqiqXXxXxXxp xp xp xP X1()log( )( )log( )qiiiiH XEp xp xp x 3.3 離散多符號信源離散多符號信源 定義3.1：對于隨機(jī)變量序列X1,X2,Xn,，在任意兩個不同時刻i和j(i和j為大于

5、1的任意整數(shù))信源發(fā)出消息的概率分布完全相同，即對于任意的N，N=0,1,2,，XiXi+1Xi+N和XjXj+1Xj+N具有相同的概率分布。也就是 即各維聯(lián)合概率分布均與時間起點無關(guān)的信源稱為離散平穩(wěn)信源。 1111()()()()()()ijiijjiii Njjj NP XP XP X XP X XP X XXP X XX3.3 離散多符號信源離散多符號信源對于離散多符號信源, 我們引入熵率的概念，它表示信源輸出的符號序列中，平均每個符號所攜帶的信息量。 定義3.2 隨機(jī)變量序列中，對前N個隨機(jī)變量的聯(lián)合熵求平均： 稱為平均符號熵。如果當(dāng) 時上式極限存在，則 稱為熵率，或稱為極限熵，記為

6、 121()()NNHH X XXNXNlim()defNNHHX)(limXNNH3.3.1 離散平穩(wěn)無記憶信源離散平穩(wěn)無記憶信源 離散平穩(wěn)無記憶信源輸出的符號序列是平穩(wěn)隨機(jī)序列，并且符號之間是無關(guān)的，即是統(tǒng)計獨立的。假定信源每次輸出的是N長符號序列，則它的數(shù)學(xué)模型是N維離散隨機(jī)變量序列：X=X1X2XN ，并且每個隨機(jī)變量之間統(tǒng)計獨立。同時，由于是平穩(wěn)信源，每個隨機(jī)變量的統(tǒng)計特性都相同，我們還可以把一個輸出N長符號序列的信源記為：根據(jù)統(tǒng)計獨立的多維隨機(jī)變量的聯(lián)合熵與信息熵之間的關(guān)系，可以推出：離散平穩(wěn)無記憶信源的熵率：12NNX XXXX()()()NHH XN H XX1lim()lim

7、()()NNNHHXNH XH XN3.3.2 離散平穩(wěn)有記憶信源離散平穩(wěn)有記憶信源 實際信源往往是有記憶信源。 對于相互間有依賴關(guān)系的N維隨機(jī)變量的聯(lián)合熵存在以下關(guān)系（熵函數(shù)的鏈規(guī)則） ： 定理3.1 對于離散平穩(wěn)信源，有以下幾個結(jié)論： （1）條件熵）條件熵 隨隨N的增加是遞減的；的增加是遞減的； （2）N給定時平均符號熵大于等于條件熵，即給定時平均符號熵大于等于條件熵，即 （3）平均符號熵）平均符號熵 隨隨N的增加是遞減的；的增加是遞減的； （4）如果）如果 ，則，則 存在，并且存在，并且12121312121()()()(|)(|)(|)NNNHH X XXH XH XXH XX XH

8、XX XXX121(|)NNH XX XX121()(|)NNNHH XX XXX)(XNH1()H X lim()NNHHX121lim()(|)NNNNHHH XX XXX條件熵條件熵 隨隨N的增加是遞減的的增加是遞減的121(|)NNH XX XX)|()|()|()|()|(1222121112121XXHXXXHXXXHXXXHXXXXHLLLLLLLL少的熵條件多的熵不大于條件平穩(wěn)性少的熵條件多的熵不大于條件L給定時平均符號熵大于等于條件熵給定時平均符號熵大于等于條件熵)|()|()(1)|(1)(1)(1211211121LLLiiiLLXXXXHXXHXHLXXHLXXXHLX

9、H結(jié)合結(jié)論1：)|()(1LLLXXHXH平均符號熵平均符號熵 隨隨N的增加是遞減的；的增加是遞減的；)(XNH1212112111()()()(/)(1)()(/)LLLLLLLLLH XH X XXH X XXH XX XXLHXH XX運(yùn)用結(jié)論2得：1()()LLH XHX如果如果 ，則，則)|(lim)|()|()(1lim)(lim:,lim)(1lim:,:,.)|(,)|(.)(,11121213211111NNNNNNNNNNNNNNNNXXHXXHXXHXHNXHaaaaNaaaXXHXXHXHX有因此那么是一個收斂的實數(shù)列如果有以下結(jié)論成立對于收斂的實數(shù)列單調(diào)有界必有極限因

10、此是單調(diào)非增數(shù)列又由于必然有的樣本空間是有限的只要L)|(lim)(lim)(121LLLLLdefXXXXHXHXH3.3.3 馬爾可夫信源馬爾可夫信源有一類信源，信源在某時刻發(fā)出的符號僅與在此之前發(fā)出的有限個符號有關(guān)，而與更早些時候發(fā)出的符號無關(guān)，這稱為馬爾可夫性，這類信源稱為馬爾可夫信源。馬爾可夫信源可以在N不很大時得到 。如果信源在某時刻發(fā)出的符號僅與在此之前發(fā)出的 m個符號有關(guān)，則稱為m階馬爾可夫信源，它的熵率： 通常記作：H12111112lim(|)lim(|)(|)NNNNN mN mNNmmHH XX XXH XXXXH XX XX)|(211mmXXXXH1mH（馬爾可夫性

11、）（平穩(wěn)性）3.3.3 馬爾可夫信源馬爾可夫信源馬爾可夫信源是一類相對簡單的有記憶信源，信源在某一時刻發(fā)出某一符號的概率除與該符號有關(guān)外，只與此前發(fā)出的有限個符號有關(guān)。因此我們把前面若干個符號看作一個狀態(tài)，可以認(rèn)為信源在某一時刻發(fā)出某一符號的概率除了與該符號有關(guān)外，只與該時刻信源所處的狀態(tài)有關(guān)，而與過去的狀態(tài)無關(guān)。信源發(fā)出一個符號后，信源所處的狀態(tài)即發(fā)生改變，這些狀態(tài)的變化組成了馬氏鏈。圖3.1 馬爾可夫信源3.3.3 馬爾可夫信源馬爾可夫信源對于一般的m階馬爾可夫信源，它的概率空間可以表示成： 令 ，從而得到馬爾 可夫信源的狀態(tài)空間： 狀態(tài)空間由所有狀態(tài)及狀態(tài)間的狀態(tài)轉(zhuǎn)移概率組成。通過引入狀

12、態(tài)轉(zhuǎn)移概率，可以將對馬爾可夫信源的研究轉(zhuǎn)化為對馬爾可夫鏈的研究。1121(|)mmiqiiiiXxxxp xx xxP X1212, ,1, 2,miiiimsx xxi iiq)|(1ijmqisspsss3.3.3 馬爾可夫信源馬爾可夫信源遍歷m階馬爾可夫信源的熵率計算p當(dāng)時間足夠長后，遍歷的馬爾可夫信源可以視作平穩(wěn)信當(dāng)時間足夠長后，遍歷的馬爾可夫信源可以視作平穩(wěn)信源來處理，又因為源來處理，又因為m階馬爾可夫信源發(fā)出的符號只與最階馬爾可夫信源發(fā)出的符號只與最近的近的m個符號有關(guān)，所以極限熵個符號有關(guān)，所以極限熵 等于條件熵等于條件熵 。p對于齊次遍歷的馬爾可夫鏈，其狀態(tài)對于齊次遍歷的馬爾可

13、夫鏈，其狀態(tài) 由由 唯一唯一確定，因此有確定，因此有 所以所以 H1mHismiiixxx211121(|)(|)(|)mmmjiiiiiiip ssp xx xxp xs)|(log)|()()|()()|(log)|()()|()|()|(1121111111211ijijijiiiiqiqiiiiiiiiiiiimmmsspsspspsXHspsxpsxpspsxIExxxxIEXXXXHHmmmmmmm 3.3.3 馬爾可夫信源馬爾可夫信源求遍歷的馬爾可夫信源的極限熵需要求狀態(tài)轉(zhuǎn)移概率和狀態(tài)的平穩(wěn)概率分布.設(shè)狀態(tài)的平穩(wěn)分布為:W=(W1 W2 W3 W4 ) 根據(jù)馬爾可夫鏈遍歷的充分條

14、件有WP=W 其中P為狀態(tài)轉(zhuǎn)移概率矩陣,W1+W2+=1例:設(shè)一個二元一階馬爾可夫信源,信源符號集為0,1,信源輸出符號的條件概率為: p(0|0)=0.25;p(0|1)=0.5;p(1|0)=0.75;p(1|1)=0.5求狀態(tài)轉(zhuǎn)移概率矩陣并畫出狀態(tài)轉(zhuǎn)移圖.例:設(shè)有一個二元二階馬爾可夫信源,其信源符號集合為X=0,1,輸出符號的條件概率為: p(0|00)=p(1|11)=0.8; p(0|01)=p(0|10)=p(1|01)=p(0|10)=0.5; p(1|00)=p(0|11)=0.2 1. 求狀態(tài)轉(zhuǎn)移概率矩陣并畫出狀態(tài)轉(zhuǎn)移圖; 2. 求該信源的極限熵.一個三元一階馬爾可夫信源的基

15、本符號為0、1、2，這3個符號等概率出現(xiàn)，并且具有相同的轉(zhuǎn)移概率。(1)寫出狀態(tài)轉(zhuǎn)移矩陣；(2)畫出狀態(tài)圖；(3)求各符號穩(wěn)態(tài)分布；(4)求各狀態(tài)穩(wěn)態(tài)分布；(5)求信源極限熵。有一馬爾可夫信源，已知狀態(tài)轉(zhuǎn)移概率：p(s1|s1)=2/3 p(s2|s1)=1/3 p(s1|s2)=1 p(s2|s2)=0。(1)寫出狀態(tài)轉(zhuǎn)移矩陣；(2)畫出狀態(tài)圖；(4)求各狀態(tài)穩(wěn)態(tài)分布；(5)求信源極限熵。 3.3.4 信源的相關(guān)性和剩余度信源的相關(guān)性和剩余度 根據(jù)定理3.1可得 由此看出，由于信源輸出符號間的依賴關(guān)系也就是信源的相關(guān)性使信源的實際熵減小。信源輸出符號間統(tǒng)計約束關(guān)系越長，信源的實際熵越小。當(dāng)信

16、源輸出符號間彼此不存在依賴關(guān)系且為等概率分布時，信源的實際熵等于最大熵 。 定義3.3 一個信源的熵率（極限熵）與具有相同符號集的最大熵的比值稱為熵的相對率：信源剩余度為： 0121logmqHHHHH0H0HH0111logHHHq 3.3.4 信源的相關(guān)性和剩余度信源的相關(guān)性和剩余度信源的剩余度來自兩個方面，一是信源符號間的相關(guān)性，相關(guān)程度越大，符號間的依賴關(guān)系越長，信源的實際熵越小，另一方面是信源符號分布的不均勻性使信源的實際熵越小。 為了更經(jīng)濟(jì)有效的傳送信息，需要盡量壓縮信源的剩余度，壓縮剩余度的方法就是盡量減小符號間的相關(guān)性，并且盡可能的使信源符號等概率分布。從提高信息傳輸效率的觀點

17、出發(fā)，人們總是希望盡量去掉剩余度。但是從提高抗干擾能力角度來看，卻希望增加或保留信源的剩余度，因為剩余度大的消息抗干擾能力強(qiáng)。 信源編碼是減少或消除信源的剩余度以提高信息的傳輸效率，而信道編碼則通過增加冗余度來提高信息傳輸?shù)目垢蓴_能力。 3.4* 連續(xù)信源連續(xù)信源 3.4.1 連續(xù)信源的微分熵連續(xù)隨機(jī)變量的取值是連續(xù)的，一般用概率密度函數(shù)來描述其統(tǒng)計特征。p單變量連續(xù)信源的數(shù)學(xué)模型為單變量連續(xù)信源的數(shù)學(xué)模型為 ，并滿足，并滿足 是實數(shù)域，表示是實數(shù)域，表示 的取值范圍。的取值范圍。p對于取值范圍有限的連續(xù)信源還可以表示成：對于取值范圍有限的連續(xù)信源還可以表示成： ，并滿足并滿足 ，(a,b)是

18、是X的取值范圍。的取值范圍。通過對連續(xù)變量的取值進(jìn)行量化分層，可以將連續(xù)隨機(jī)變量用離散隨機(jī)變量來逼近。量化間隔越小，離散隨機(jī)變量與連續(xù)隨機(jī)變量越接近。當(dāng)量化間隔趨于0時，離散隨機(jī)變量就變成了連續(xù)隨機(jī)變量。通過這種方式，我們來推導(dǎo)連續(xù)隨機(jī)變量的熵。 :( )RXp x( )1Rp x dx ( , ):( )a bXp x( )1bap x dx 3.4.1 連續(xù)信源的微分熵連續(xù)信源的微分熵定義連續(xù)信源的微分熵為：微分熵又稱為差熵。雖然已不能代表連續(xù)信源的平均不確定性，也不能代表連續(xù)信源輸出的信息量，但是它具有和離散熵相同的形式，也滿足離散熵的主要特性，比如可加性，但是不具有非負(fù)性。 同樣，我們可以定義兩個連續(xù)隨機(jī)變量的聯(lián)合熵： 以及條件熵 ()( )log( )Rh Xp xp x dx 2()()log()Rh XYp xyp xy dxdy 22(|)()log( | )(|)()log( | )RRh Y Xp xyp y x dxdyh X Yp xyp x y dxdy 3.4.2 連續(xù)信源的最大熵連續(xù)信源的最大熵離散信源當(dāng)信源符號為等概分布時有最大熵。連續(xù)信源微分熵也有極大值，但是與約束條件有關(guān)，當(dāng)約束條件不同時，信源的最大熵