信息論與編碼基礎(chǔ)教程-課件第2章

信息論與編碼李軒、李玉峰編著第2章單符號(hào)離散信源第2章單符號(hào)離散信源最簡(jiǎn)通信系統(tǒng)由信源、信道和信宿三部分構(gòu)成。離散信源可用離散隨機(jī)矢量來(lái)描述，其中每個(gè)隨機(jī)變量都是取值離散的。當(dāng)隨機(jī)矢量只含一個(gè)離散隨機(jī)變量時(shí)，這種信源就稱為單符號(hào)離散信源。2.1單符號(hào)離散信源的數(shù)學(xué)模型信源的信息熵2.3信源符號(hào)的自信息量2.22.4信息熵的性質(zhì)第2章單符號(hào)離散信源2.1單符號(hào)離散信源的數(shù)學(xué)模型如果信源X符號(hào)集為，r為符號(hào)集大小，信源符號(hào)對(duì)應(yīng)某一概率分布，，稱此信源為單符號(hào)離散信源，信源空間數(shù)學(xué)模型可由下式描述其中，，【例2.1】一個(gè)三元無(wú)記憶信源X，符號(hào)集A={0,1,2}，概率分布為：p(0)=1/2,p(1)=1/3,p(2)=1/6,寫出信源空間模型。解：信源空間模型如下式所示：【例2.2】某箱子中共有32個(gè)質(zhì)地均勻的球，其中，紅球16個(gè)，黃球8個(gè)，藍(lán)球和白球各4個(gè)。每次拿出一個(gè)球，拿出后又放回，各種彩球出現(xiàn)的先驗(yàn)概率分別為：2.1單符號(hào)離散信源的數(shù)學(xué)模型P(紅)=16/32=1/2P(黃)=8/32=1/4P(藍(lán))=4/32=1/8P(白)=4/32=1/8

用隨機(jī)變量X表示這個(gè)信源，其信源空間為：由上述兩個(gè)例子看出：信源空間包含兩個(gè)基本要素：隨機(jī)變量X的狀態(tài)空間和概率空間，而概率空間又是決定性要素。概率可測(cè)是香農(nóng)信息論的基本前提。2.2信源符號(hào)的自信息量設(shè)信源發(fā)出某符號(hào)，由于信道中存在噪聲或其它干擾，收端收到的是的某種變型，收信者收到后，從中獲取關(guān)于的信息量，用表示，則若信道是無(wú)噪無(wú)損信道，即一一對(duì)應(yīng)信道，收信者收到就是本身，那么就完全消除了對(duì)信源符號(hào)的不確定性，即把定義為信源符號(hào)的自信息量，并用表示，即信源符號(hào)的自信息量度量問(wèn)題，相當(dāng)于信源發(fā)符號(hào)的不確定性度量問(wèn)題，是先驗(yàn)概率的函數(shù)：根據(jù)自信息量定義所需的4個(gè)公理性條件，自信息量函數(shù)定義如下：自信息量隨變化的曲線自信息量的單位與對(duì)數(shù)的底有關(guān)若以“2”為底，自信息量單位為“比特”（bit-binaryunit），即若以“e”為底，自信息量單位為“奈特”（nat-natureunit），即若以“10”為底，自信息量單位為“哈特”（Hart-Hartley），即2.2信源符號(hào)的自信息量

2.2信源符號(hào)的自信息量若以正整數(shù)“r”為底，自信息量單位為“r進(jìn)制信息單位”，即不同信息單位之間可以進(jìn)行換算。本書(shū)如不加說(shuō)明，信息度量默認(rèn)為以“2”為底，且略去底數(shù)“2”不寫。香農(nóng)信息量的度量，是信息論發(fā)展史上的里程碑，奠定了信息論發(fā)展成為一門學(xué)科的基礎(chǔ)。【例2.3】箱中80個(gè)紅球，20個(gè)白球，現(xiàn)從箱中隨機(jī)取出兩個(gè)球。求:(1)求解“兩個(gè)球中紅、白各一個(gè)”的不確定性(2)求解“兩個(gè)球都是白球”所提供的信息量(3)求解“兩個(gè)球都是白球”和“兩個(gè)球都是紅球”相比較，哪個(gè)事件發(fā)生的更難測(cè)？2.2信源符號(hào)的自信息量

解：設(shè)x為紅球數(shù)，y為白球數(shù)，則：

從上述計(jì)算結(jié)果來(lái)看，1.416bit大于0.195bit,顯然,事件“兩個(gè)球都是白球”要比事件“兩個(gè)球都是紅球”更難測(cè)?！纠?.4】設(shè)二元隨機(jī)矢量，矢量中每個(gè)變量（i=1,2，...，N）為獨(dú)立同分布隨機(jī)變量，且0符號(hào)的概率。求序列x=101100100的自信息量。解：2.3信源的信息熵自信息量是針對(duì)具體的特定事件在發(fā)生前存在的不確定度的度量，或發(fā)生后，提供給接收者的信息量。自信量的度量具有個(gè)體差異性，不具備對(duì)信源總體不確定度的度量能力。對(duì)信源X總體進(jìn)行信息度量，即信源熵，它表征信源平均每個(gè)符號(hào)所含有的不確定性或平均輸出一個(gè)符號(hào)提供給觀測(cè)者的信息量，是自信息量的統(tǒng)計(jì)均值，即有熵的單位即自信息量的單位，取決于對(duì)數(shù)的底?！纠?.5】（a）設(shè)有一信源X由兩個(gè)事件，組成，其概率空間如下則其信源熵為（b）設(shè)有另一信源Y如下則2.3信源的信息熵可見(jiàn)有，即信源Y的平均不確定性要大于信源X的平均不確定性。直觀地分析也易得出這樣一個(gè)結(jié)論：信源中各事件的出現(xiàn)概率越接近，則事先猜測(cè)某一事件發(fā)生的把握性越小，即不確定性越大。從后述信息熵的極值性質(zhì)，我們可知：當(dāng)信源各事件等概率出現(xiàn)時(shí)具有最大的信源熵，也即信源的平均不確定性最大?！纠?.6】設(shè)二元信源X的信源空間為其中，（1）試計(jì)算當(dāng)p=1/2；p=0（或p=1）時(shí)信息熵的值；（2）信息熵是概率分量p的函數(shù)。畫出的函數(shù)曲線，并指明函數(shù)的特性。解：信源X的信息熵這表明，二元信源X的信息熵H(X)是概率分量p的函數(shù)。（1）當(dāng)p=(1-p)=1/2時(shí)，二元信源X稱為二維等概信源，其信息熵2.3信源的信息熵這表明，二元等概信源X，每一個(gè)符號(hào)（不論是“0”還是“1”）含有的平均信息量是1比特，每發(fā)一個(gè)符號(hào)（不論是“0”還是“1”）提供的平均信息量是1比特；每一個(gè)符號(hào)（不論是“0”還是“1”）存在的平均不確定性是1比特；收信者能確切無(wú)誤的收到信源X的“0”或“1”時(shí)，收信者每收到信源X的一個(gè)符號(hào)，獲取的平均信息量是1比特。（2）當(dāng)p=0（p=1）時(shí)，二元信源X是一個(gè)確知信源，其信息熵因?yàn)?，?duì)任意小的正數(shù)，以“e”為底的對(duì)數(shù)可展開(kāi)成級(jí)數(shù)當(dāng)時(shí)，的極限值等于零，即有所以2.3信源的信息熵這樣，可合理的約定0log0=0則當(dāng)p=0（p=1）時(shí)，信源X的信息熵這表明，以概率1發(fā)符號(hào)“0”或“1”的二元確知信源，不存在任何不確定性，不含有任何信息量。（3）當(dāng)0<p<1時(shí)，取不同的p值，可計(jì)算出二元信源X的信息熵相應(yīng)地，得到H（p）函數(shù)曲線2.3信源的信息熵從圖中可見(jiàn)，若二元信源X發(fā)符號(hào)“0”（或“1”）是確定事件，即p=1（p=0）時(shí)，則H（p）=H（1）（或H（0））=0。這意味著確知信源X不提供任何信息量；若二元信源X以相同概率0.5發(fā)符號(hào)“0”或“1”，即p=1/2時(shí)，H（p）=1比特/信源符號(hào)。這意味著等概信源X每發(fā)一個(gè)符號(hào)提供的平均信息量達(dá)到最大值1比特/信源符號(hào)。若二元信源X發(fā)“0”（或“1”）的概率p（0<p<1）越接近1/2，則發(fā)“1”（或“0”）的概率（1-p）亦越接近1/2.若“0”和“1”的概率越接近則H（p）的值越大。這意味著二元信源X的平均不確定性越大，每符號(hào)（不論是“0”還是“1”）含有的平均信息量越大；相反，二元信源X發(fā)“0”（或“1”）的概率p（0<p<1）越遠(yuǎn)離1/2，則發(fā)“1”（或“0”）的概率（1-p）亦越遠(yuǎn)離1/2.若發(fā)“0”和“1”的概率相差越大，則H（p）的值就越小。這意味著二元信源X的平均不確定性越小，每符號(hào)（不論是“0”還是“1”）含有的平均信息量就越小。這體現(xiàn)出H（p）是概率分量p的上凸形函數(shù)的基本特性。2.3信源的信息熵【例2.7】在一個(gè)箱子中裝有m個(gè)黑球和（n-m）個(gè)白球。設(shè)實(shí)驗(yàn)X：隨機(jī)的從箱子中取出一個(gè)球而不再放回箱子；實(shí)驗(yàn)Y：從箱子中取出第二個(gè)球。（1）計(jì)算實(shí)驗(yàn)X所獲取的平均信息量（2）若實(shí)驗(yàn)X摸取的第一個(gè)球的顏色不知道，計(jì)算實(shí)驗(yàn)Y所獲取的平均信息量。解：令W代表白球；B代表黑球。（1）設(shè)實(shí)驗(yàn)X中取出的球是黑球的概率為PX（B）；實(shí)驗(yàn)X中取出的球是白球的概率為PX（W），則有信源X的信源空間可表示為

實(shí)驗(yàn)X所獲取的平均信息量，就是信源X的信息熵（2）若實(shí)驗(yàn)X中取出的第一個(gè)球是白球，令實(shí)驗(yàn)Y中取出的白球的概率為PY（W/W）；取出黑球的概率為PY（B/W），則有若實(shí)驗(yàn)X中取出的第一個(gè)球是黑球，令實(shí)驗(yàn)Y中取出白球的概率為PY（W/B）；取出黑球的概率為PY（B/B），則有設(shè)實(shí)驗(yàn)Y中出現(xiàn)白球的概率為PY（W）；出現(xiàn)黑球的概率為PY（B），則有2.3信源的信息熵信源Y的信源空間可表示為實(shí)驗(yàn)Y所獲取的平均信息量，就是信源Y的信息熵這說(shuō)明，實(shí)驗(yàn)X和實(shí)驗(yàn)Y的平均不確定性或獲取的平均信息量是相等的。2.3信源的信息熵定義2.4.1

對(duì)于服從聯(lián)合分布為p(x,y)的一對(duì)離散隨機(jī)變量(X,Y)，其聯(lián)合熵H(X,Y)（jointentropy）定義為

上式亦可表示為也可以定義一個(gè)隨機(jī)變量在給定另一隨機(jī)變量下的條件熵，先求條件分布熵H(Y|X=x)；然后對(duì)條件分布熵再求統(tǒng)計(jì)均值既得條件熵。2.4.1聯(lián)合熵與條件熵2.4信息熵的性質(zhì)定義2.4.2若，條件熵（conditionalentropy）定義為：

聯(lián)合熵和條件熵定義的這種自然性可由一個(gè)事實(shí)得到體現(xiàn)，它就是一對(duì)隨機(jī)變量的熵等于其中一個(gè)隨機(jī)變量的熵加上另一個(gè)隨機(jī)變量的條件熵。其證明見(jiàn)如下定理。2.4信息熵的性質(zhì)定理2.1（鏈?zhǔn)椒▌t）【證明】

等價(jià)地記為：等式的兩邊同時(shí)取對(duì)數(shù)期望，即得本定理。

推論2.4信息熵的性質(zhì)2.4.2相對(duì)熵若P和Q為定義在同一概率空間的兩個(gè)概率測(cè)度，定義P相對(duì)于Q的相對(duì)熵為相對(duì)熵又稱散度、鑒別信息、方向散度、交叉熵、Kullback_leibler距離等。注意，在上式中，概率分布的維數(shù)不限，可以是一維，也可以是多維，也可以是條件概率。

對(duì)于任意正實(shí)數(shù)x，下面不等式成立：（2.16）實(shí)際上，設(shè)，可求得函數(shù)的穩(wěn)定點(diǎn)為x=1，并可求得在該點(diǎn)的二階導(dǎo)數(shù)小于0，從而可得x=1為f(x)取極大值的點(diǎn)，即，僅當(dāng)x=1時(shí)，上式（2.16）右邊等號(hào)成立。令y=1/x，可得,再將y換成x，就得到左邊的不等式。定理2.2如果在一個(gè)共同有限字母表概率空間上給定兩個(gè)概率測(cè)度P(x)和Q(x)，那么（2.17）僅當(dāng)對(duì)所有x，P(x)=Q(x)時(shí)，等式成立?！咀C明】因，，所以根據(jù)式（2.16），有

僅當(dāng)對(duì)所有x，P(x)=Q(x)時(shí)，等式成立。式（2.17）稱為散度不等（divergenceinequality），該式說(shuō)明，一個(gè)概率測(cè)度相對(duì)于另一個(gè)概率測(cè)度的散度是非負(fù)的，僅當(dāng)兩測(cè)度相同時(shí)，散度為零。散度可以解釋為兩個(gè)概率測(cè)度之間的“距離”，即兩概率測(cè)度不同程度的度量。不過(guò)，散度并不是通常意義下的距離，因?yàn)樗粷M足對(duì)稱性，也不滿足三角不等式?！纠?.8】設(shè)一個(gè)二元信源的符號(hào)集為{0,1}，有兩個(gè)概率分布p和q，并且p(0)=1-r,p(1)=r,q(0)=1-s,q(1)=s,求散度D(p||q)和D(q||p)，并分別求當(dāng)r=s和r=2s=1/2時(shí)散度的值。解：當(dāng)r=s時(shí)，有D(p||q)=D(q||p)=0當(dāng)r=2s=1/2時(shí)，有2.4信息熵的性質(zhì)2.4信息熵的性質(zhì)定理2.3（熵的不增原理）

（2.19）【證明】設(shè)，那么

上面利用了散度不等式，僅當(dāng)X，Y相互獨(dú)立時(shí)，等式成立。式（2.19）表明，條件熵總是不大于無(wú)條件熵，這就是熵的不增原理：在信息處理過(guò)程中，已知條件越多，結(jié)果的不確定性越小，也就是熵越小。

定義2.4.3若對(duì)于任意的及，滿足

則稱函數(shù)f(x)在區(qū)間上是凸的（convex）。如果僅當(dāng)或，上式成立，則稱函數(shù)f是嚴(yán)格凸的（strictlyconvex）。定義2.4.4如果為凸函數(shù)，則稱函數(shù)是凹的。如果函數(shù)總是位于任何一條弦的下面，則該函數(shù)是凸的；如果函數(shù)總是位于任何一條弦的上面，則該函數(shù)是凹的。定理2.4（Jensen不等式）若給定凸函數(shù)和一個(gè)隨機(jī)變量X，則（2.21）進(jìn)一步，若是嚴(yán)格凸的，那么式（2.21）中的等式蘊(yùn)含X=EX的概率為1（即X是個(gè)常量）。2.4信息熵的性質(zhì)

2.4.3Jensen不等式及其結(jié)果

【證明】我們只證明離散分布情形，且對(duì)分布點(diǎn)的個(gè)數(shù)進(jìn)行歸納證明。當(dāng)為嚴(yán)格凸函數(shù)時(shí)，等號(hào)成立條件的證明留給讀者。對(duì)于兩點(diǎn)分布，不等式變?yōu)?.4信息熵的性質(zhì)

這由凸函數(shù)的定義可直接得到。假定當(dāng)分布點(diǎn)的個(gè)數(shù)為k-1時(shí)，定理成立，此時(shí)記則有2.4.4信息熵的基本性質(zhì)對(duì)稱性

概率矢量中，各分量的次序任意改變，熵不變，即

（2.24）其中，是1,2，，n的任何一種n級(jí)排列。該性質(zhì)說(shuō)明熵僅與隨機(jī)變量總體概率特性（即概率分布）有關(guān)，而與隨機(jī)變量的取值及符號(hào)排列順序無(wú)關(guān)。非負(fù)性

（2.25）

僅當(dāng)對(duì)某個(gè)時(shí)，等式成立。

因?yàn)樽孕畔⒘渴欠秦?fù)的，熵為自信息的平均，所以也是非負(fù)的。不過(guò)，非負(fù)性僅對(duì)離散熵有效，而對(duì)連續(xù)熵來(lái)說(shuō)這一性質(zhì)并不成立。2.4信息熵的性質(zhì)確定性這就是說(shuō)，當(dāng)隨機(jī)變量集合中任一事件概率為1時(shí)，熵就為0。這個(gè)性質(zhì)意味著，從總體來(lái)看，事件集合中雖含有許多事件，但是如果只有一個(gè)事件幾乎必然出現(xiàn)，而其他事件幾乎都不出現(xiàn)，那么，這就是一個(gè)確知的變量，其不確定性為0.擴(kuò)展性利用可得到上面的結(jié)果，其含義是，雖然小概率事件自信息大，但在計(jì)算熵時(shí)所占比重很小，可以忽略。極值性定理2.5（離散最大熵定理）對(duì)于有限離散隨機(jī)變量，當(dāng)符號(hào)集中的符號(hào)等概率發(fā)生時(shí)，熵達(dá)到最大值。注意：離散最大熵定理僅適用于有限離散隨機(jī)變量，對(duì)于無(wú)限可數(shù)符號(hào)集，只有附加其他約束求最大熵才有意義。2.4信息熵的性質(zhì)【證明】設(shè)隨機(jī)變量有n個(gè)符號(hào)，概率分布為P(x);Q(x)為等概率分布，即Q(x)=1/n。根據(jù)散度不等式有即 僅當(dāng)P(x)等概布時(shí)等號(hào)成立。上凸性是概率矢量p的嚴(yán)格的上凸函數(shù)。這就是說(shuō)，若，那么，其中均為n維概率矢量，。該性質(zhì)可用凸函數(shù)性質(zhì)（1）來(lái)證明（提示：先證明是嚴(yán)格上凸的）。2.4信息熵的性質(zhì)一一對(duì)應(yīng)變換下的不變性離散隨機(jī)變量的變換包含兩種含義，一是符號(hào)集中符號(hào)到符號(hào)的映射，二是符號(hào)序列到序列的變換。首先研究第一種情況。設(shè)兩隨機(jī)變量X、Y，符號(hào)集分別為A、B，其中Y是X的映射，可以表示為，。因此有