第2章離散信源及其信息度量本章內(nèi)容2.1離散信源的分類2.2離散信源的統(tǒng)計特性2.3離散隨機(jī)變量的信息度量2.4離散信源的N次擴(kuò)展信源2.5離散平穩(wěn)信源2.6馬爾可夫信源2.7離散信源的相關(guān)性和剩余度2.1

離散信源的分類離散信源的分類?按照離散信源輸出的是一個消息符號還是消息符號序列，可分為單符號離散信源和多符號離散信

源。按輸出符號之間依賴關(guān)系分類，多符號離散信源可分為無記憶信源和有記憶信源。?按照信源輸出的符號序列的統(tǒng)計特性是否隨時間變化，多符號離散信源可分為平穩(wěn)信源和非平穩(wěn)信

源

。離散信源的N

次擴(kuò)展信源：對信源輸出的符號序列進(jìn)行分組，每N個符號一組，只考慮組內(nèi)各符號之間的關(guān)聯(lián)性，而假定

組與組之間是統(tǒng)計獨(dú)立的；馬爾可夫信源：只考慮到信源發(fā)出的消息符號與前面有限

個符號的依賴關(guān)系，不考慮與更前面發(fā)出符號的依賴關(guān)系，

即用有限記憶源去近似實際信源。離散信源的N次擴(kuò)展信源馬爾可夫信源無記憶離散信源有記憶離散信源單符號離散信源多符號離散信源離散信源2.2離散信源的統(tǒng)計特性如果信源輸出的消息符號為時間離散、取值有限或可數(shù)的隨機(jī)序列

，此時信源就是離散信源。①

單符號離散信源這是最簡單、最基本的一類信源，信源只輸出一個取值離散的消

息符號，稱為單符號離散信源?？梢杂靡粋€離散隨機(jī)變量來表示。假設(shè)離散信源輸出的消息符號集合為{a,a?,

…

,ag},

相應(yīng)符號

的概率分別為P(a),P(a?),

…

,P(ag),則該信源可以用離散隨機(jī)變

量X的概率空間來描述。離散信源的統(tǒng)計特性單符號離散信源概率空間描述0≤P(a;)≤1,

實際信源發(fā)出的消息符號，往往不止一個符號，而是由多個符號組成的離散隨機(jī)序列，可用離散隨機(jī)變量序列(或隨機(jī)矢量)來描述信源發(fā)出的消息，即X=X?X?X?…X,此時的信源稱為多符號離散信源。一般的多符號離散信源輸出的隨機(jī)序列的統(tǒng)計特性比較復(fù)雜，分析起來也比較困難。將在第3章中詳細(xì)討論。

多符號離散信源簡便起見，先考慮信源輸出兩個符號的情況，可以用兩個隨機(jī)變量X?X?來表示。設(shè)兩個隨機(jī)變量的二維聯(lián)合概率為

P(x?x?),x?和X?

取值于同

一

集合{a,a?,

…

,a?},則

二

維

聯(lián)

合

集X?X?的

概

率

空

間

為其中

，P(x?x?)有如下關(guān)系式：①②P(x?x?)≥0,x,x?∈(a,a?,…,a?)(2.2.2)(2.2.3)類似地，如果信源輸出長度為L的符號序列，可用L維離散隨機(jī)矢量X=(X?X?…X,)來描述，其中每個分量X,(l=1,2,…,L)都是隨機(jī)變量，它們都取值于同一集合{a,42,…,4},則該信源的統(tǒng)計特性可以表示為其中

,

P(a,)(i=1,2,…,q2)表示序列α?

的概率,其中α?=

(x?x?…x?),

每個分量x,∈(a?,a?,…a),1=1,2,…,L。(2.2.4)如果各個分量之間統(tǒng)計獨(dú)立，則稱為離散P(x?X?…xz)=P(x?)P(x?)…P(x)2.3離散隨機(jī)變量的信息度量定義：

隨機(jī)事件的自信息量定義為該事件發(fā)生概率的對數(shù)的負(fù)值。設(shè)集合X

中的事件x=a,

發(fā)生概率為P(a),則它的自信息量定義為一、自信息量/(x;)和信息熵

H(X)簡記為

I(x)=-log.P(x)I(a)代表兩種物理含義：①當(dāng)事件a,發(fā)生以前，I(a)

表示事件a,發(fā)生的不確定性。因為概率小的事件不易發(fā)生，預(yù)料它是否發(fā)生比較困難，因此包含較大的不確定性。而必然事件發(fā)生概率為1,所以不確定性為零。②當(dāng)事件a,發(fā)生以后，

I(a)

表示事件a所提供的信息量。在無干擾信道中，事件a,

發(fā)生后，能正確無誤地傳輸?shù)绞招耪?，所以I(a,)可代表信宿接收到消息a后所獲得的信息量，也是為了消除信宿對事件a,是否發(fā)生不確定性所需要的信息量。自信息量的單位與所用對數(shù)的底有關(guān)。①當(dāng)對數(shù)以2為底時，單位是“比特”(bit—binary

unit);②當(dāng)對數(shù)以e

為底時，單位是“奈特”(nat—nature

unit);③當(dāng)對數(shù)以10為底時，單位是“哈特”(Hart—Hartley)。④

一般情況下，如果以r

為

底(r>1),

則I(a)=-log,P(a)(r

進(jìn)制單位)通常采用“比特”作為信息量的實用單位。在本書中，且為了書寫簡潔，底數(shù)2通常省略不寫?！纠考僭O(shè)有這樣一種彩票，中獎概率為0.0001,不中獎概率為0.9999?，F(xiàn)有一個人買了一注彩票。試計算(1)

事件“彩票中獎”的不確定性；(2)

事件“彩票不中獎”的不確定性；(3)

事件“彩票中獎”和事件“彩票不中獎”相比較，哪個提供的信息量較大?(

2

)

設(shè)a2

表示事件“彩票不中獎”,因為概率

P(a2)=0

.9999,所以I(a?)=-logP(a?)=-log0.9999=0.0001(bit)(3)因為I(a1)>I(a2),

所以事件“彩票中獎”提供的信息量較大。解：(1)設(shè)a1

表示事件“彩票中獎”,因為概率P(a1)=0.0001,所以I(a?)=-log

P(a?)=-log0.0001=13.2877(bit)【例】

對于2n進(jìn)制的數(shù)字序列，假設(shè)每一符號的出現(xiàn)相互獨(dú)立且概率相等，求任一符號的自信息量。解：根據(jù)題意，P(a?)=1/2n,所以I(a)=-log

P(a)=-log(1/2”)=n(bit)特殊地，對于獨(dú)立等概分布的二進(jìn)制符號序列，每一符號的自信息量為1bit。自信息量的性質(zhì)：1)非負(fù)性。2)單調(diào)遞減性。

3)可加性。若兩個符號x?,y,同時出現(xiàn)，可用聯(lián)合概率這時的自信息量為表示，Shannon

將

H(X)

定

義

為

單

符

號

離

散

信

源

的

信

息

熵

(Shannon

熵或無條件

熵

)

,

它

表

示

信

源

輸出的

一

個

符

號

所

含的

平

均

信息

量

。則自信息量的數(shù)學(xué)期

望

定

義

為

信

源的

平均自信息

量，即定義：設(shè)信源的概率空間為(bit/

符

號

)簡

記

為(q-1)

元

函

數(shù)

。當(dāng)

q=2

時，

因P?+

P?=1,所

以

將2

個

符

號

的

熵

函

數(shù)

寫成

H(p)

或

H(P?熵

函

數(shù)

可以

寫

成

概

率

矢

量p=(P?,P?,…Pq記為因

為

概

率

空間的

完

備

性，

即,

所

以H(p)

是)

的函

數(shù)

形

式

，和自信息相似，信息熵H(X)有兩種物理含義：①

信源輸出前，信源的信息熵表示信源的平均

不確定度。②

信源輸出后，信源的信息熵表示信源輸出一

個離散消息符號所提供的平均信息量。如果信道無噪

聲干擾，信宿獲得的平均信息量就等于信源的平均信

息量，即信息熵。需要注意的是，若信道中存在噪聲，

信宿獲得的平均信息量不再是信息熵，而是2.5節(jié)介

紹的平均互信息。計算(1)信源X

中事件

a?

和

a4分別含有的自信息量；(2)信息熵H(X)?！纠?

.

3】

已知某信源的概率空間為求該信源的熵。解：H(X)=H(p,1-p)=-plog

p-(1-p)log(1-p)

(比特/符號)【例2.4】

已知二進(jìn)制通信系統(tǒng)的信源空間為0.90.80.70.6

0.50.40.30.20.1000.1

0.2

0.30.4

0.5

0.60.7

0.80.9圖2.2

二進(jìn)制熵函數(shù)曲線信息熵的性質(zhì)1、對稱性當(dāng)變量p?,P?,…Pq

的順序任意互換時，熵函數(shù)的值不變，即H(p?,P?,…Pq)=H(p?,P?,…Pq,P?)=…=H(Pq,P?…Pq-1)例如，有下面三個不同隨機(jī)變量的信源空間分別為三者的信息熵相等.已知隨機(jī)變量Z=X+Y,

試計算：(1)P(z),P(xz),P(yz),P(xyz);(2)H(X),H(Y),H(Z);(3)H(XY),H(XZ),H(YZ),H(XYZ);(4)H(X|Y),H(Y|X),H(X|Z);(5)H(Z|XY),H(X|YZ),H(Y|XZ)。YXb?=0b?=1a=01/91/2a?=11/62/9【例2

.9】設(shè)隨機(jī)變量X和Y的聯(lián)合概率分布如表2.4所示。表2.4

隨機(jī)變量X和Y的聯(lián)合概率分布XYP(xy)Z=X+Y001/90011/21101/61112/92Z012P(z)1/92/32/9解

：

(1)由已知條件可得到XY和Z的關(guān)系及其概率分布如表2.5所示。表2.5

隨機(jī)變量XY和Z的關(guān)系及其概率分布聯(lián)合概率P(xz),P(yz),P(xyz)分別如表2.7、表2.8和表2.9所示。表2.7

聯(lián)合概率P(xz)所以Z的概率P(z)

如表2.6所示。表2.6

隨機(jī)變量Z的概率ZXYC?=0C?=1C?=2xy=001/900xy=0101/20xy=1001/60xy=11002/9表2.9聯(lián)合概率P(xyz)ZC?=0C?=1C?=2Yb?=01/91/60b?=101/22/9ZXC?=0C?=1C?=2a=01/91/20a?=101/62/9表2.7

聯(lián)合概率P(×z)表2.8聯(lián)合概率P(yz)(4)

H(X|Y)=H(XY)-H(Y)=0.9128(比特/符號)

H(Y|X)=H(XY)-H(X)=0.8011(比特/符號)

H(X|Z)=H(XZ)-H(Z)=0.5408(比特/符號)(5)H(Z|XY)=H(XYZ)-H(XY)=0H(X|YZ)=H(XYZ)-H(YZ)=0

H(Y|XZ)=H(XYZ)-H(XZ)=0由

例

2

.

9

可

知

，

當(dāng)

隨

機(jī)

變

量Z=X+

Y時，H(Z|XY)=0。

可

以

這

樣

理

解

：

當(dāng)X和Y已知時，Z是

確

知

的

，

所

以

不

確

定

性(比特/兩個符號)(比特/兩個符號)(2)(3)(比特/三個符號)(比特/兩個符號)(比特/符號)(比特/符號)(比特/符號)為0。2.4離散信源的N

次擴(kuò)展信源如果由

N

個符號組成的序列代表一條完整的消息，而且序列和序列之間相互獨(dú)立，此時的離散信源可以等效為一個新的信源。

新信源每次輸出長度為N

的符號序列，可用N維離散隨機(jī)矢量

X=(X?X?…Xn)來描述，其中每個分量X,(l=1,2,…,N)都是隨

機(jī)變量，它們都取值于同一集合{a,a?

,

…

,ag},

則由這個隨機(jī)矢

量X表示的新信源稱為離散信源X的

N次擴(kuò)展信源，一般標(biāo)記

為X~。對應(yīng)地，長度為N

的符號序列稱為擴(kuò)展信源符號.離散信源

X

的

N

次擴(kuò)展信源的定義且滿足

則離散信源X

的

N次擴(kuò)展信源X~

是具有

個擴(kuò)展信源符號的離散信源，該信源的數(shù)學(xué)模型用N重概率空間表示1、N

次

擴(kuò)

展

信

源

的

數(shù)

學(xué)

模

型設(shè)單符號離散信源的數(shù)學(xué)模型為其中P(α)(i=1,2,…,q)

表示序列α,的概率。=H(X?)+H(X?|X?)+…+H(XNIX?X?…XN-1)即每個擴(kuò)展信源符號平均包含的信息量，所以稱為擴(kuò)展信源的熵，也稱為序列熵。單位為

“bit/擴(kuò)展信源符號”,或者

“bit/序列”。對

于N

個隨機(jī)變量組成的隨機(jī)矢量X=(X?,X?…XN)的

熵

為2

、

離

散

信

源

的N

次

擴(kuò)

展

信

源

的

熵如果各個分量X,(l=1,2,…,N)之間統(tǒng)計獨(dú)立，則稱為離散無記憶信源的N次擴(kuò)展信源。此時，N維離散隨機(jī)矢量的聯(lián)合概率P(x)=P(x?X?…Xn)=P(x?)P(x?)…P(xn)問題?單符號離散信源的熵為多少??離散無記憶信源的N

次擴(kuò)展信源的熵為多少??離散信源的N

次擴(kuò)展信源的每個符號平均提供的信息量為多3、離散無記憶信源的

N

次擴(kuò)展信源平均符號熵定義為每個信源符號平均包含的信息量，單位為“bit/信源符號”。由于一個序列由N個信源符號構(gòu)成，所以平均符號熵為當(dāng)信源符號序列長度N→

∞時，此時的平均符號熵稱為離散信源的極限熵，定義為4、平均符號熵和極限熵的定義離散無記憶信源的N次擴(kuò)展信源的各個分量相互獨(dú)立。由式(2.4.1)可知，此時N次擴(kuò)展信源的熵為

(2.4.4)如果離散無記憶信源是平穩(wěn)的，則隨機(jī)矢量X=(X?X?…X)中的各分量，X,l=1,2…,N的概率分布相同，即P(x?)=P(x?)=…=P(xn)

(2.4.5)則H(X?)=H(X?)=…=H(Xn)(2.4.6)因此，離散無記憶平穩(wěn)信源X的N次擴(kuò)展信源的熵等于單符號離散信源X的熵的N倍，即

(2.4.7)此時，平均符號熵就是單符號離散信源的平均符號熵，即H(X)=H(X)離散無記憶信源的N

次擴(kuò)展信x?

X2a?a?a?a?1/21/20a?3/41/81/8a?01/43/4(1)假設(shè)該離散信源為無記憶信源，計算二次擴(kuò)展信源的熵。(2)假設(shè)每兩個信源符號組成一個序列，序列與序列之間相互獨(dú)立，序列中第2個

符號與第1個符號之間的條件概率P(x?|x?)如下表所示，試計算該二次擴(kuò)展信源的

熵和平均符號熵。某離散信源的單符號概率空間為2.5

離散平穩(wěn)信源離散平穩(wěn)信源定義：如果對于任意的L,隨機(jī)變量序列X=X?X?…X的概率分布

P(x?x?…x?)

與時

間

起

點(diǎn)

無

關(guān)

，

即

當(dāng)t=1,t=j(i,j為任意整數(shù)，且i≠j)時有P(x,)=P(x;)P(x;xi+1)=P(x,x;+1)··

··P(x:+1xi+2…x;+L)=P(x;+1xj+2…xj+L)則該信源稱為離散平穩(wěn)信源。由于聯(lián)合概率與條件概率有以下關(guān)系：P(x;x;+1)=P(x;)P(x;+1

|x;)P(x;x;+1xi+2)=P(x;)P(x;+1|x;)P(xi+2|x;x;+1)·

··因此，對于任意給定的長度L,

如果滿足P(x;)=P(x;)=P(x?)P(x:+1

|x;)=P(x;+1

|x;)=P(x?|x?)P(x?+2|x?x;+1)=P(x;+2

|x;x;+1)=P(x?|xx?)··

··則該離散信源為離散平穩(wěn)信源。所以，對于平穩(wěn)信源來說，其條件概率也與時間起點(diǎn)無關(guān)。如果離散平穩(wěn)信源某時刻發(fā)出什么符號只與前面發(fā)出的

m個符號有關(guān)聯(lián)，而與更早些時刻發(fā)出的符號無關(guān)聯(lián)，則該信源稱為

(m+1)

維離散平穩(wěn)信源。也就是說，(m+1)

維離散平穩(wěn)信源在滿足

平穩(wěn)的條件下，還滿足一般地，實際信源輸出的隨機(jī)序列的統(tǒng)計特性比較復(fù)雜，分析起來也比較困難。為了便于分析，我們通常假設(shè)信源輸出的是平穩(wěn)

的隨機(jī)序列，而且限定記憶長度。(m+1)

維離散平穩(wěn)信源點(diǎn)無關(guān)，即為離散平穩(wěn)信源。此時信源為一維離散平穩(wěn)信源。(2)對于最具代表性的二維離散平穩(wěn)信源，需要滿足兩個條件：①

平穩(wěn)。即P(x;)=P(x);

②信源發(fā)出的符號只與前一個符號有關(guān)。即(1)對于離散無記憶信源，如果,則對于任意的L,

隨機(jī)變量序列X=X?X?…X,

的概率分布都與時間起一

維離散平穩(wěn)信源和二維離散平穩(wěn)信源根據(jù)離散平穩(wěn)信源的定義，容易理解下面的兩個重要結(jié)論。x1+1X?工23工1/21/2023/41/81/8301/43/4與前一個符號有關(guān)，其條件概率P(x,+1

|x?)(l=1,2,…)具有時間推移的不變性，如下表所示。試問該信源是否為二維離散平穩(wěn)信源?【例】設(shè)有離散信源X,取值于集A={1,2,3},

已

知

起

始概率為假設(shè)信源輸出的符號只由離散平穩(wěn)信源的定義，可以證明二維離散平穩(wěn)信源的條件熵滿足lim

H(XnIX?X?…XN-1)=H(X?|X?)N→0特殊地

，H(X?|X?X?)=H(X?|X?)=H(X?|X?)2)(m+1)

維離散平穩(wěn)信源根據(jù)(m+1)

維離散平穩(wěn)信源的定義，可以證明得到條件熵有限維離散平穩(wěn)信源的條件熵1)二維離散平穩(wěn)信源x?

x1+1a?a?a?a?1/21/20a23/41/81/8a?01/43/4假設(shè)發(fā)出的符號只與前一個符號有關(guān)，其條件概率P(

X?+1

X?(1)

條件熵H(X?|X?)和H(X?|X?);(2)條件熵H(X?

IX?X?

)?！纠吭O(shè)有二維離散平穩(wěn)信源X,

單符號信源的概率空間為如下

.解：(1)