信息論信源及信息熵

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

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

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

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

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

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

7、()()NNNHHXNH XH XN3.3.2 離散平穩(wěn)有記憶信源離散平穩(wěn)有記憶信源 實(shí)際信源往往是有記憶信源。 對(duì)于相互間有依賴關(guān)系的N維隨機(jī)變量的聯(lián)合熵存在以下關(guān)系（熵函數(shù)的鏈規(guī)則） ： 定理3.1 對(duì)于離散平穩(wěn)信源，有以下幾個(gè)結(jié)論： （1）條件熵）條件熵 隨隨N的增加是遞減的；的增加是遞減的； （2）N給定時(shí)平均符號(hào)熵大于等于條件熵，即給定時(shí)平均符號(hào)熵大于等于條件熵，即 （3）平均符號(hào)熵）平均符號(hào)熵 隨隨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給定時(shí)平均符號(hào)熵大于等于條件熵給定時(shí)平均符號(hào)熵大于等于條件熵)|()|()(1)|(1)(1)(1211211121LLLiiiLLXXXXHXXHXHLXXHLXXXHLX

9、H結(jié)合結(jié)論1：)|()(1LLLXXHXH平均符號(hào)熵平均符號(hào)熵 隨隨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有因此那么是一個(gè)收斂的實(shí)數(shù)列如果有以下結(jié)論成立對(duì)于收斂的實(shí)數(shù)列單調(diào)有界必有極限因

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

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

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

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è)一個(gè)二元一階馬爾可夫信源,信源符號(hào)集為0,1,信源輸出符號(hào)的條件概率為: p(0|0)=0.25;p(0|1)=0.5;p(1|0)=0.75;p(1|1)=0.5求狀態(tài)轉(zhuǎn)移概率矩陣并畫(huà)出狀態(tài)轉(zhuǎn)移圖.例:設(shè)有一個(gè)二元二階馬爾可夫信源,其信源符號(hào)集合為X=0,1,輸出符號(hào)的條件概率為: 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)移概率矩陣并畫(huà)出狀態(tài)轉(zhuǎn)移圖; 2. 求該信源的極限熵.一個(gè)三元一階馬爾可夫信源的基

15、本符號(hào)為0、1、2，這3個(gè)符號(hào)等概率出現(xiàn)，并且具有相同的轉(zhuǎn)移概率。(1)寫(xiě)出狀態(tài)轉(zhuǎn)移矩陣；(2)畫(huà)出狀態(tài)圖；(3)求各符號(hào)穩(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)寫(xiě)出狀態(tài)轉(zhuǎn)移矩陣；(2)畫(huà)出狀態(tài)圖；(4)求各狀態(tài)穩(wěn)態(tài)分布；(5)求信源極限熵。 3.3.4 信源的相關(guān)性和剩余度信源的相關(guān)性和剩余度 根據(jù)定理3.1可得 由此看出，由于信源輸出符號(hào)間的依賴關(guān)系也就是信源的相關(guān)性使信源的實(shí)際熵減小。信源輸出符號(hào)間統(tǒng)計(jì)約束關(guān)系越長(zhǎng)，信源的實(shí)際熵越小。當(dāng)信

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

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

18、是X的取值范圍。的取值范圍。通過(guò)對(duì)連續(xù)變量的取值進(jìn)行量化分層，可以將連續(xù)隨機(jī)變量用離散隨機(jī)變量來(lái)逼近。量化間隔越小，離散隨機(jī)變量與連續(xù)隨機(jī)變量越接近。當(dāng)量化間隔趨于0時(shí)，離散隨機(jī)變量就變成了連續(xù)隨機(jī)變量。通過(guò)這種方式，我們來(lái)推導(dǎo)連續(xù)隨機(jī)變量的熵。 :( )RXp x( )1Rp x dx ( , ):( )a bXp x( )1bap x dx 3.4.1 連續(xù)信源的微分熵連續(xù)信源的微分熵定義連續(xù)信源的微分熵為：微分熵又稱為差熵。雖然已不能代表連續(xù)信源的平均不確定性，也不能代表連續(xù)信源輸出的信息量，但是它具有和離散熵相同的形式，也滿足離散熵的主要特性，比如可加性，但是不具有非負(fù)性。 同樣，我們可以定義兩個(gè)連續(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)信源符號(hào)為等概分布時(shí)有最大熵。連續(xù)信源微分熵也有極大值，但是與約束條件有關(guān)，當(dāng)約束條件不同時(shí)，信源的最大熵