第2章 離散信源及其信息測度

第二章離散信源及其信息測度通信的根本問題是將信源的輸出信息盡可能快速可靠的傳輸并在接受端盡可能精確的復(fù)現(xiàn)。從本章開始，我們將從有效而可靠地傳輸信息的觀點出發(fā)，對組成信息傳輸系統(tǒng)（通信系統(tǒng)）的各個部分分別進行討論。本章首先討論信源，重點是信源的統(tǒng)計特性和數(shù)學(xué)模型，以及各類離散信源的信息測度——熵及其性質(zhì)，從而引入信息理論的一些基本概念和重要結(jié)論。主要內(nèi)容2.1信源的數(shù)學(xué)模型及分類2.2離散信源的信息熵2.3信息熵的基本性質(zhì)2.4離散無記憶信源的擴展信源2.5離散平穩(wěn)信源2.6信源剩余度2.1信源的數(shù)學(xué)模型及分類2.1信源的數(shù)學(xué)模型及分類通信過程是從信源開始的，信源發(fā)送的是消息或消息序列，通信系統(tǒng)中傳遞的是消息，消息中包含信息。因此，通過研究消息來研究信源。在通信系統(tǒng)中收信者在收到消息之前，對信源發(fā)出的消息是不知道的，是不確定的、隨機的，所以可以用隨機變量、隨機矢量或者隨機過程來描述信源輸出的消息。通常用一個樣本空間及其概率測度——概率空間來描述信源。2.1信源的數(shù)學(xué)模型及分類不同的信源輸出的消息不同，可以根據(jù)消息的不同的隨機性質(zhì)來對信源進行分類。2.1.1信源輸出的消息用隨機變量描述信源的的消息符號是離散的且是有限的，每次信源的輸出為單個的信源符號，且所有符號的概率滿足完備性，這是最基本的離散信源。如書信、文稿、電報、計算機輸出的代碼等。如果信源輸出為連續(xù)信號，如語音、熱噪聲信號，傳感器測得電壓、溫度、壓力、振動信號等，這些信源的輸出都是連續(xù)取值的，稱為連續(xù)信源。其輸出消息是不可數(shù)的。其數(shù)學(xué)模型是連續(xù)型的概率空間，用下面的形式表示。2.1信源的數(shù)學(xué)模型及分類2.1信源的數(shù)學(xué)模型及分類2.1.2信源輸出的消息用隨機矢量描述實際信源每次輸出的消息是按一定概率選取的符號序列，可以看做是時間上或者空間的隨機矢量。用N維隨機矢量X=(X1,X2,…,XN)表示，又稱為隨機序列。若隨機矢量的各維概率分布都與時間起點無關(guān)，這樣的信源稱為平穩(wěn)信源。每個隨機變量Xi都是離散取值且其可能取值是有限的，這樣的信源稱為離散平穩(wěn)信源。每個隨機變量Xi都是連續(xù)取值的連續(xù)型隨機變量，則為連續(xù)平穩(wěn)信源。2.1信源的數(shù)學(xué)模型及分類若信源先后發(fā)出的各個符號彼此統(tǒng)計獨立，則：若隨機變量Xi不同時刻的取值來自于同一個符號集合A：{a1,a2,…aq}.則有：若該信源不同時刻發(fā)出的符號之間無依賴關(guān)系，彼此統(tǒng)計獨立，則為離散無記憶信源。2.1信源的數(shù)學(xué)模型及分類則信源X所輸出的隨機矢量X所描述的信源稱為離散無記憶信源X的N次擴展信源若信源在不同時刻發(fā)出的符號之間是相互依賴的，這種信源為有記憶信源。通常符號之間的依賴關(guān)系（記憶長度）是有限的，若記憶長度為m+1,則稱這種有記憶信源為m階馬爾可夫信源。

用條件概率倆描述隨機序列中各隨機變量之間依賴關(guān)系：2.1信源的數(shù)學(xué)模型及分類若上述條件概率與時間起點無關(guān)，及條件概率也是平穩(wěn)的，則此信源為時齊馬爾可夫信源。在連續(xù)平穩(wěn)信源情況下，也分為無記憶信源和有記憶信源。若信源輸出的連續(xù)型隨機矢量中，各隨機變量之間無依賴且統(tǒng)計獨立，則稱此信源為連續(xù)平穩(wěn)無記憶信源。若信源輸出的連續(xù)型隨機矢量中，各隨機變量之間有依賴，則稱此信源為連續(xù)有記憶信源。2.1.3信源輸出的消息用隨機矢量描述很多實際信源的輸出消息常常是時間和取值都是連續(xù)的，例如語音信號、熱噪聲信號、電視信號等時間連續(xù)函數(shù)。同時在某一具體時間t0,它們的可能取值又是連續(xù)的和隨機的。對于這種信源的輸出消息，可用隨機過程來描述。稱這類信源為隨機波形信源（也稱隨機模擬信源）。按照取樣定理，隨機過程也可以用一系列離散的取樣值來表示，即離散隨機序列。2.1信源的數(shù)學(xué)模型及分類2.2離散信源的信息熵2.2離散信源的信息熵▼討論和研究最基本的離散信源(即輸出為單個符號的消息，且這些消息間兩兩互不相容)。▼基本的離散信源可用一維隨機變量X來描述信源的輸出，信源的數(shù)學(xué)模型可抽象為:問題：這樣的信源能輸出多少信息?每個消息的出現(xiàn)攜帶多少信息量?2.2.1自信息▼緒論中我們已經(jīng)知道，通信時信源發(fā)出的消息常常是隨機的，不確定的，只有當(dāng)消息通過信道傳輸給收信者以后，才能消除這種不確定性。▼因此，通信中獲取的信息與不確定性消除的程度有關(guān)，消除的不確定性＝獲得的信息量；▼不確定性就是隨機性，可以用概率論和隨機過程來測度，概率小→不確定性大→信息量大，即信息量是概率的單調(diào)遞減函數(shù)；2.2離散信源的信息熵設(shè)離散信源X的概率空間為：事件ai發(fā)生所含有的自信息量為：I(ai)代表兩種含義：▼事件ai發(fā)生前，表示事件ai發(fā)生的不確定性；▼事件ai發(fā)生后，表示事件ai所提供的信息量。2.2離散信源的信息熵{{★本書(以及通信理論中)當(dāng)中,如無特殊說明,信息量的單位均默認為比特.★由以上定義可以看出：（1）自信息是關(guān)于事件發(fā)生概率P的減函數(shù)；（2）當(dāng)P=1，自信息為0；（3）當(dāng)P=0，自信息為無窮大；（4）兩個獨立的事件的聯(lián)合自信息為它們各自自信息的和。2.2離散信源的信息熵[例2-1]8個串聯(lián)的燈泡x1，x2，…，x8，其損壞的可能性是等概率的，現(xiàn)假設(shè)其中有一個燈泡已損壞，問每進行一次測量可獲得多少信息量？總共需要多少次測量才能確定哪個燈泡已損壞。解：已知8個燈泡等概率損壞，所以先驗概率P(x1)＝1/8，即總的不確定性為：2.2離散信源的信息熵第一次測量后，剩4個燈泡。同樣等概率損壞，P(x2)＝1/4，因為前面的判斷，不確定性減少拉，還剩余的不確定為：第三次測量后，即可判斷出哪個燈泡是壞的，則剩余不確定性減少為零。第二次測量后，剩2個燈泡，P(x3)＝1/2，不確定性進一步減少，還剩余的不確定為：2.2離散信源的信息熵[例2-2]若從裝有n個不同阻值電阻的袋中隨機取出一個并猜測所取得的阻值，困難程度是多少？解：這相當(dāng)于求事件的不確定性事件等概[例2-3]袋中有n(n+1)/2個電阻，其中1Ω的1個，2Ω的2個，…，nΩ的n個，隨機取出一個，則“取出阻值為i的電阻”所獲得的信息量。解：“取出阻值為i的電阻”的概率是多少？2.2離散信源的信息熵2.2.2信息熵★對一個信源發(fā)出不同的消息所含有的信息量也不同。所以自信息I(ai)是一個隨機變量，不能用它來作為整個信源的信息測度★定義自信息的數(shù)學(xué)期望為平均自信息量Hr(X)，稱為信息熵:2.2離散信源的信息熵▼因和統(tǒng)計物理學(xué)中熱熵的表達式相似，因此借用“熵”這個詞，把H(X)稱為信息“熵”；▼H(X)表示信源輸出前的平均不確定性；▼H(X)表示信源平均每個符號攜帶的信息量；▼H(X)表示信源X的隨機性。2.2離散信源的信息熵[例2-3]信源X的符號集為{0，1}，其中“0”符號出現(xiàn)的概率為p，求信源的熵?解：[例2-4]電視屏幕的格點數(shù)為500×600=300000，每點有10個灰度等級，若每幅畫面等概率出現(xiàn)，求每幅畫面平均所包含的信息量。解：可能的畫面數(shù)為10300000

幅2.2離散信源的信息熵[例2-5]一布袋內(nèi)放l00個球，其中80個紅球，20個白球，如果從中隨機取出一個球，設(shè)a1為取出紅球，a2為取出白球，則其概率空間為：

解：如果摸出的是紅球，那么獲得的信息量是：

I(a1)＝-logp(a1)

＝-log0.8=0.32比特）如果摸出來的是白球，所獲得的信息量應(yīng)為：I(a2)＝-logp(a2)

＝-log0.2=2.32（比特）平均摸取一次所能獲得的信息量為：

H(X)=p(a1)I(a1)+p(a2)I(a2)=0.72（比特/符號）2.2離散信源的信息熵[例2-6]有甲、乙兩箱球，甲箱中有紅球50、白球20、黑球30；乙箱中有紅球90、白球10。現(xiàn)做從兩箱中分別隨機取一球的實驗，問從哪箱中取球的結(jié)果隨機性更大？。解:設(shè)甲、乙分別用AB代表所以，從甲箱中取球的結(jié)果隨機性更大。2.2離散信源的信息熵[例2-7]A、B兩城市天氣情況概率分布如下表：晴陰雨A城0.80.150.05B城0.40.30.3問哪個城市的天氣具有更大的不確定性？解:A、B城市天氣情況的平均不確定性如下:所以，B城市的天氣具有更大的不確定性。2.2離散信源的信息熵2.3信息熵的基本性質(zhì)2.3信息熵的基本性質(zhì)設(shè)離散信源X的概率空間為：信息熵是信源概率空間的一種特殊矩函數(shù)。其大小與信源的符號數(shù)及其概率分布有關(guān)。用概率矢量P來表示概率分布，H(P)為熵函數(shù)。2.3信息熵的基本性質(zhì)引理若f(x)是定義在[a、b]上的實值連續(xù)上凸函數(shù),則對于任意一組x1,x2,…,xq∈[a、b]和任意一組非負實數(shù)λ1,λ2,…λq且滿足:則有:稱此為詹森不等式用數(shù)學(xué)歸納法即可證明此引理，這是一個很重要的引理，我們對它做一個簡單的推廣：也可以簡寫成:2.3信息熵的基本性質(zhì)1、對稱性：H(P)的取值與分量p1,p2,···,pq的順序無關(guān)。從數(shù)學(xué)角度:H(P)=pilogpi中的和式滿足交換律；從隨機變量的角度:熵只與隨機變量的總體統(tǒng)計特性有關(guān)。例如：2.3信息熵的基本性質(zhì)2、確定性：H(1,0)=H(1,0,0)=H(1,0,0…,0)=0說明：總體來看，雖然有不同的輸出符號，但只有一個符號幾乎必然出現(xiàn)，而其它符號則是幾乎不可能出現(xiàn)，信源是確知信源，其熵等于零。3、非負性：H(P)0說明：隨機變量X的概率分布滿足0＜pi＜1，當(dāng)對數(shù)底大于1時，log(pi)＜0，-pilog(pi

)＞0，即熵為正值。當(dāng)隨機變量是一確知量時熵等于零。非負性只適合于離散信源的熵，對連續(xù)信源來說這一性質(zhì)并不存在。相對熵可能出現(xiàn)負值。非負性也說明信息是非負的。4、連續(xù)性2.3信息熵的基本性質(zhì)說明:熵函數(shù)是概率pi的連續(xù)函數(shù),同時表明,信源空間中概率分量的微小波動不會引起總體信息熵的巨大變化.2.3信息熵的基本性質(zhì)說明：信源的取值數(shù)增多時，若這些取值對應(yīng)的概率很小(接近于零)，則信源的熵不變。5、擴展性2.3信息熵的基本性質(zhì)6可加性隨機變量X、Y構(gòu)成聯(lián)合事件集合XY,則二維隨機變量(X,Y)的熵等于多少呢？或者:其中:聯(lián)合集概率空間為:2.3信息熵的基本性質(zhì)2.3信息熵的基本性質(zhì)同理可以證明：推論：當(dāng)各個變量統(tǒng)計獨立時，有：2.3信息熵的基本性質(zhì)幾個關(guān)系的證明:2.3信息熵的基本性質(zhì)(2)熵的不增原理(條件熵不大于信息熵)2.3信息熵的基本性質(zhì)[例2-7]如，甲信源為它們的聯(lián)合信源是可計算得聯(lián)合信源的聯(lián)合熵：H(XY)=log(nm)=logm+logn=H(X)+H(Y)乙信源為2.3信息熵的基本性質(zhì)7、遞增性若原信源X中有一個符號分割成了m個元素(符號)，這m個元素的概率之和等于被分割符號的概率，而其他符號的概率不變，則新信源的熵增加。熵的增加量等于由分割而產(chǎn)生的不確定性量。可以由熵的定義式直接證明，也可以由聯(lián)合熵的強可加性來證明。下面進行直接證明：2.3信息熵的基本性質(zhì)證明：遞增性的推廣：2.3信息熵的基本性質(zhì)它表示n個元素的信源熵可以遞推成(n-1)個二元信源的熵函數(shù)的加權(quán)和。這樣，可使多元信源的熵函數(shù)的計算簡化成計算若干個二元信源的熵函數(shù)。因此，熵函數(shù)的遞增性又可稱為遞推性。[例2-8]：運用熵函數(shù)的遞增性(遞推性)，計算熵函數(shù)H(1/3，1/3，1/6，1/6)的值。2.3信息熵的基本性質(zhì)2.3信息熵的基本性質(zhì)8極值性利用前面的詹森公式：條件(1)(2)λk為非負實數(shù)；(3)f(x)為上凸函數(shù)。當(dāng)且僅當(dāng)每個事件等概率出現(xiàn)時等號成立。00.51.0ω1.0

0.5H(ω)2.3信息熵的基本性質(zhì)H(X)=-log-(1-)log(1-)=H()

[例2-9]該信源符號只有二個，設(shè)為“0”和“1”。符號輸出的概率分別為“”和“1-”，即信源的概率空間為：即信息熵H(x)是關(guān)于的函數(shù)。取值于[0，1]區(qū)間，可畫出熵函數(shù)H()的曲線來，如右圖所示。2.3信息熵的基本性質(zhì)8上凸性熵函數(shù)H(P)是概率矢量P的嚴(yán)格∩型凸函數(shù)。設(shè)概率矢量P=(p1,p2,…,pr)和Q=(q1,q2,…,qr)。其中：0≤pi≤1，0≤qi≤1，Σpi=1,Σqi=1，0≤a≤1。2.3信息熵的基本性質(zhì)9熵函數(shù)的唯一性(證明略!)則熵函數(shù)具有唯一性.2.4離散無記憶信源2.4離散無記憶信源2.4.1單符號離散無記憶信源信源X的符號集X={x1,x2…,xq}，每個符號的發(fā)生概率為p(xi)，信源每次發(fā)出一個符號，且符號發(fā)生的概率相互獨立，稱為單符號離散無記憶信源，簡稱離散無記憶信源。2.4離散無記憶信源2.4.2離散無記憶信源的擴展信源1離散無記憶二進制信源的二次擴展信源二次擴展信源擴展后的信源符號集合新概率的計算:舉例p(00)=p(0)p(0)…2.4離散無記憶信源2離散無記憶二進制信源的三次擴展信源三次擴展信源擴展后的信源符號集合新概率的計算:舉例p(000)=p(0)p(0)p(0)…2.4離散無記憶信源3任意進制離散無記憶信源的N次擴展信源N次擴展信源2.4離散無記憶信源2.4.3N次擴展信源的熵證明:離散無記憶信源X的N次擴展信源XN的熵等于信源X的熵值的N倍.2.4離散無記憶信源2.4離散無記憶信源[例2-10]已知離散無記憶信源模型如下:解:已知二元信源X={0,1},其二次擴展源X2=X1X2。則二次擴展源X2的符號集為{00,01,10,11}.其信源模型如下:求其二次擴展信源。2.4離散無記憶信源[例2-11]求離散無記憶信源的二次擴展信源及其熵。解：二次擴展信源的概率空間為X2123456789序列a1a1a1a2a1a3a2a1a2a2a2a3a3a1a3a2a3a3P(i)1/41/81/81/81/161/161/81/161/162.5離散平穩(wěn)信源2.5離散平穩(wěn)信源2.5.1離散平穩(wěn)信源

在實際應(yīng)用中，信源不是一個簡單的無記憶信源。其輸出往往是時間或者空間上的離散隨機序列，而且序列中各符號之間存在一定的依賴（有記憶）關(guān)系。一般信源輸出是雙邊序列：…X-1X0X1X2…Xi…其中Xi是隨機變量,且其取值xi∈X={a1,a2,…aq}，i表示符號xi發(fā)送所對應(yīng)的時刻，信源發(fā)送符號之間的依賴關(guān)系關(guān)系可以用聯(lián)合概率來表示。2.5離散平穩(wěn)信源在一般情況下，信源在t=i時刻將要發(fā)出什么樣的符號決定于兩方面：

(1)與信源在t=i時刻隨機變量Xi的取值xi的概率分布p(xi)有關(guān)。一般t不同，概率分布也不同；(2)與t=i時刻以前信源已經(jīng)發(fā)出的信源符號有關(guān)，即與條件概率p(xi|xi-1xi-2…)有關(guān)。通常該條件概率也是時間t的函數(shù)，即：當(dāng)i≠j時

p(xi|xi-1xi-2…xi-N…)≠p(xj|xj-1xj-2…xj-N…)可以看出實際信源相對比較復(fù)雜，我們必須將復(fù)雜的問題簡單化，下面只討論平穩(wěn)信源：2.5離散平穩(wěn)信源若發(fā)送序列中，一維概率分布不隨時間改變而改變，即：P(Xi=x)=P(Xj=x)=p(x)，則稱為一維離散平穩(wěn)信源；若一到N維聯(lián)合概率分布都不隨時間變化而改變，則信源為N維離散平穩(wěn)信源。即：若發(fā)送序列各維聯(lián)合概率都是平穩(wěn)的，由此還可以推論出相應(yīng)的條件概率也是平穩(wěn)的:2.5離散平穩(wěn)信源………………即對于平穩(wěn)信源，其條件概率均與時間起點無關(guān)，只與關(guān)聯(lián)長度N有關(guān)。即平穩(wěn)信源發(fā)出的平穩(wěn)隨機序列前后的依賴關(guān)系與時間起點無關(guān)。2.5離散平穩(wěn)信源2.5.2二維平穩(wěn)信源的熵

離散平穩(wěn)信源實際是一種有記憶信源，最簡單的有記憶平穩(wěn)信源是二維平穩(wěn)信源，可看作是單符號離散信源的二次擴展信源，是有記憶的擴展信源。擴展后的二維聯(lián)合概率空間為：2.5離散平穩(wěn)信源如何對離散二維平穩(wěn)信源進行信息測度？

已知擴展后的二維信源概率空間，根據(jù)信息熵的定義可以計算二維聯(lián)合熵：聯(lián)合熵表示平均每兩個信源符號所攜帶的平均不確定性，與信源熵的定義——平均每個信源符號所攜帶的信息量不一致，近似表示為：2.5離散平穩(wěn)信源[例2-12]

某一離散二維平穩(wěn)信源其發(fā)出的符號只與前一個符號有關(guān)，即可用聯(lián)合概率P(aiaj)給出它們的關(guān)聯(lián)程度，如下表所示:P(aiaj)ajai01201/41/18011/181/31/18201/187/36求信源熵H(X)、條件熵H(X2/X1)和聯(lián)合熵H(X1X2)。2.5離散平穩(wěn)信源解：根據(jù)概率關(guān)系可計算得條件概率P(aj/ai),計算結(jié)果列表如下：ajai01201/41/18011/181/31/18201/187/36ajai01209/111/8012/113/42/9201/87/9到底選取哪一個值更能接近實際二維平穩(wěn)信源的熵?2.5離散平穩(wěn)信源2.5.3離散平穩(wěn)信源的極限熵一般的平穩(wěn)有記憶信源，輸出符號之間的相互依賴關(guān)系不僅存在于相鄰倆個符號之間，而且存在于更多(N>2)的符號之間。如何N長信源序列的熵值？若離散有記憶信源概率空間為：N長信源序列可以看作是單符號信源的N次擴展信源，即：X=X1X2…XN中各符號Xi，(i=1,2,…,N)均取自同一符號集合A=(a1,a2,…,aq)。2.5離散平穩(wěn)信源信源發(fā)出的符號序列為(X1,X2,…,XN,…)，假設(shè)信源符號之間的依賴長度為N，各維概率分布為：簡記為滿足：2.5離散平穩(wěn)信源已知聯(lián)合概率分布可求得離散平穩(wěn)信源的聯(lián)合熵：定義N長的信源符號序列中平均每個信源符號所攜帶的信息量(平均符號熵)為：同時,若已知前N-1個符號，第N個符號的平均不確定性(平均信息量)，可從條件熵定義得出：2.5離散平穩(wěn)信源對離散平穩(wěn)信源若H1(X)＜，則有以下性質(zhì)：(1)條件熵H(XN/X1X2…XN-1)隨N的增加是遞減的；(2)HN(X)H(XN/X1X2…XN-1)；(3)HN(X)也是隨N增加而遞減的；(4)H存在，并且:稱為平穩(wěn)信源的極限熵或者極限信息量，也有的稱此為平穩(wěn)信源的熵率。同時上式表明，有記憶信源的符號熵也可通過計算極限條件熵得到。2.5離散平穩(wěn)信源現(xiàn)在簡單證明這幾個性質(zhì):(1)根據(jù)信源的平穩(wěn)性和熵的不增原理，得：即對于平穩(wěn)信源，條件越多，條件熵越不增加。(2)證明N個的和不小于 即平均符號熵不小于條件熵。2.5離散平穩(wěn)信源(3)HN(X)隨N增加而遞減；證明:由于根據(jù)平均符號熵的定義和(2)的結(jié)果，有上式表明，平均符號熵不隨序列的長度而增加。

2.5離散平穩(wěn)信源(4)由前面的證明我們可以得出:是存在的。計算:利用(1)的結(jié)果與平穩(wěn)性，有：2.5離散平穩(wěn)信源先令 后令，得: 另外，由(2)的結(jié)果，當(dāng) 時，有所以:2.5離散平穩(wěn)信源定理的注釋：(1)該定理提供了計算信源符號熵的方法，即通過計算極限條件熵得到。這樣，當(dāng)信源為有限記憶時，極限條件熵的計算要比極限平均符號熵的計算容易得多。例如：當(dāng)平穩(wěn)信源的記憶長度為有限m個符號長度時（及某時刻發(fā)生的符號只與其前面的m個符號有關(guān)），則得離散平穩(wěn)信源的極限值：(2）極限熵等于最小的平均符號熵。[例2-13]：有兩個同時輸出的信源X和Y，其中X:{A，B，C}，Y:{D，E，F(xiàn)，G}，已知P(X)和P(Y/X)，求聯(lián)合信源的聯(lián)合熵和條件熵。2.5離散平穩(wěn)信源XABCP(x)1/21/31/6P(y/x)D1/43/101/6E1/41/51/2F1/41/51/6G1/43/101/6解：信源