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

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

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

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

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

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

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

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

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

聯(lián)合熵和條件熵定義的這種自然性可由一個事實得到體現(xiàn)，它就是一對隨機變量的熵等于其中一個隨機變量的熵加上另一個隨機變量的條件熵。其證明見如下定理。2.4信息熵的性質定理2.1（鏈式法則）【證明】

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

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

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

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

（2.19）【證明】設，那么

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

定義2.4.3若對于任意的及，滿足

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

2.4.3Jensen不等式及其結果

【證明】我們只證明離散分布情形，且對分布點的個數(shù)進行歸納證明。當為嚴格凸函數(shù)時，等號成立條件的證明留給讀者。對于兩點分布，不等式變?yōu)?.4信息熵的性質

這由凸函數(shù)的定義可直接得到。假定當分布點的個數(shù)為k-1時，定理成立，此時記則有2.4.4信息熵的基本性質對稱性

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

（2.24）其中，是1,2，，n的任何一種n級排列。該性質說明熵僅與隨機變量總體概率特性（即概率分布）有關，而與隨機變量的取值及符號排列順序無關。非負性

（2.25）

僅當對某個時，等式成立。

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