第二章-信息論基本概念

1,第二章信息論的基本概念,第一節(jié)信源的描述和分類,第二節(jié)離散信源的信息論概念,第三節(jié)離散信源的熵,2,第一節(jié)信源的描述和分類,一、香農(nóng)信息論的基本點,用隨機變量或隨機矢量來表示信源，運用概率論和隨機過程的理論來研究信息。,二、信源的分類,按照信源發(fā)出的消息在時間上和幅度上的分布情況可將信源分成離散信源和連續(xù)信源兩大類,信源,離散信源,連續(xù)信源,3,連續(xù)信源連續(xù)信源是指發(fā)出在時間和幅度上都是連續(xù)分布的連續(xù)消息（模擬消息）的信源，如語言、圖像、圖形等都是連續(xù)消息。,離散信源離散信源是指發(fā)出在時間和幅度上都是離散分布的離散消息的信源，如文字、數(shù)字、數(shù)據(jù)等符號都是離散消息。,離散信源,離散無記憶信源,離散有記憶信源,發(fā)出單個符號的無記憶信源,發(fā)出符號序列的無記憶信源,發(fā)出符號序列的有記憶信源,發(fā)出符號序列的馬爾可夫信源,4,離散無記憶信源離散無記憶信源所發(fā)出的各個符號是相互獨立的，發(fā)出的符號序列中的各個符號之間沒有統(tǒng)計關(guān)聯(lián)性，各個符號的出現(xiàn)概率是它自身的先驗概率。,離散有記憶信源離散有記憶信源所發(fā)出的各個符號的概率是有關(guān)聯(lián)的。,發(fā)出單個符號的信源發(fā)出單個符號的信源是指信源每次只發(fā)出一個符號代表一個消息；,發(fā)出符號序列的信源發(fā)出符號序列的信源是指信源每次發(fā)出一組含二個以上符號的符號序列代表一個消息。,5,發(fā)出符號序列的有記憶信源發(fā)出符號序列的有記憶信源是指用信源發(fā)出的一個符號序列的整體概率（即聯(lián)合概率）反映有記憶信源的特征。,發(fā)出符號序列的馬爾可夫信源發(fā)出符號序列的馬爾可夫信源是指某一個符號出現(xiàn)的概率只與前面一個或有限個符號有關(guān)，而不依賴更前面的那些符號，這樣的信源可以用信源發(fā)出符號序列內(nèi)各個符號之間的條件概率來反映記憶特征。,6,三、先驗概率及概率空間的形式,一個離散信源發(fā)出的各個符號消息的集合為：,它們的概率分別為：,為符號,的先驗概率。,先驗概率,一般信源可用一個概率空間來描述，信源的不確定程度可用該概率空間的可能狀態(tài)數(shù)目及其概率來描述。,狀態(tài)空間,7,信息論所關(guān)心的就是這種隨機變量的不確定性，驅(qū)使我們對隨機變量進行觀察和測量，從中獲取信息。,8,問題：什么叫自信息量？什么叫不確定度？什么叫互信息量？什么叫平均自信息量？什么叫條件熵？什么叫聯(lián)合熵？聯(lián)合熵、條件熵和熵的關(guān)系是什么？熵的性質(zhì)有哪些？什么叫平均互信息量？什么叫信源熵？如何計算離散信源熵？,第二節(jié)離散信源的信息論概念,9,（一）自信息量,1.信息量？,2.自信息量？,3.不確定度？,4.聯(lián)合自信息量？,5.條件自信息量？,本節(jié)的重點內(nèi)容：,10,I（信息量）不確定程度的減少量,（一）自信息量,1.信息量,定義：一個隨機事件的自信息量定義為其出現(xiàn)概率對數(shù)的負(fù)值:,2.自信息量,即收信者收到一個消息后，所獲得的信息量等于收到信息前后不確定程度減少的量。（舉例）,11,c.因為概率越小，的出現(xiàn)就越稀罕，一旦出現(xiàn)，所獲得的信息量也就較大。由于是隨機出現(xiàn)的，它是X的一個樣值，所以是一個隨機量。而是的函數(shù)，它必須也是一個隨機量。,說明：,a.自信息量是非負(fù)的。,b.對于離散無記憶信源，符號串中各符號統(tǒng)計獨立，符號串自信息量具有可加性：,12,d.自信息量單位的確定在信息論中常用的對數(shù)底是2，信息量的單位為比特（bit），用log2或lb表示；（bit/符號）若取自然對數(shù)，則信息量的單位為奈特（nat），用loge或ln表示；（nat/符號）若以10為對數(shù)底，則信息量的單位為哈脫萊(Hartley)，用log10或lg表示；（hartley/符號）若對數(shù)底為r，則信息量的單位為r進制用單位/符號。這三個信息量單位之間的轉(zhuǎn)換關(guān)系如下：,1natlog2el.433bit，lHartleylog2103.322bit,13,定義：隨機事件的不確定度在數(shù)量上等于它的自信息量說明:兩者的單位相同，但含義卻不相同。具有某種概率分布的隨機事件不管發(fā)生與否，都存在不確定度，不確定度表征了該事件的特性，而自信息量是在該事件發(fā)生后給予觀察者的信息量。,3.不確定度,14,一個出現(xiàn)概率接近于1的隨機事件，發(fā)生的可能性很大，所以它包含的不確定度就很??；反之，一個出現(xiàn)概率很小的隨機事件，很難猜測在某個時刻它能否發(fā)生，所以它包含的不確定度就很大；若是確定性事件，出現(xiàn)概率為1，則它包含的不確定度為0。,15,幾個關(guān)于自信息量的例子：,（1）一個以等概率出現(xiàn)的二進制碼元（0，1）所包含的自信息量為：I（0）=I（1）=-log2（1/2）=log22=1bit/符號,（2）若是一個m位的二進制數(shù)，因為該數(shù)的每一位可從0,1兩個數(shù)字中任取一個，因此有2m個等概率的可能組合。所以I=-log2(1/2m)=mbit/符號，就是需要m比特的信息來指明這樣的二進制數(shù)。,16,（3）具有四個取值符號的隨機變量各符號概率相等，均為1/4，各符號的自信息量：,注：bit的含義是二進制數(shù)字（0、1），自信息量為2（bit/符號），意味著其不確定性可用2位二進制數(shù)字來度量（00、01、10、11）。若取4為對數(shù)底，自信息量為1（四進制單位/符號），意味著其不確定性可用1位四進制數(shù)字來度量（0、1、2、3）。,17,（4）英文字母中“e”出現(xiàn)的概率為0.105，“c”出現(xiàn)的概率為0.023，“o”出現(xiàn)的概率為0.001。分別計算它們的自信息量。解：“e”的自信息量I（e）=-lb0.105=3.25（bit/符號）“c”的自信息量I（c）=-lb0.023=5.44（bit/符號）“o”的自信息量I（o）=-lb0.0019.97（bit/符號）,18,（5）某離散無記憶信源（DMS,DiscreteMemorylessSource）的概率空間為信源發(fā)出消息202120130213001203210110321010021032011223210。求該消息的自信息量以及消息中平均每符號的自信息量？,19,解：信源符號的自信息量：,單位都是bit/符號,信源無記憶，發(fā)出的符號串中各符號統(tǒng)計獨立，由自信息量的可加性，符號串自信息量等于各符號自信息量之和：,平均一個符號的自信息量：,20,（6）同時拋擲一對質(zhì)地均勻的骰子，每個骰子各面朝上的概率均為1/6，試求：(a)事件“3和5同時發(fā)生”的自信息量？(b)事件“兩個1同時發(fā)生”的自信息量？(c)事件“兩個點數(shù)中至少有一個是1”的自信息量？,解:(a)存在兩種情況：甲3乙5，甲5乙3。P(A)=1/362=1/18，I(A)=-lbP(A)=4.17（bit）。(b)存在一種情況：甲1乙1。P(B)=1/36，I(B)=-lbP(B)=5.17（bit）。(c)P(C)=15/65/6=11/36，I(C)=-lbP(C)=1.17（bit）。,21,（7）在布袋中放入81枚硬幣，它們的外形完全相同。已知有一枚硬幣與其它80枚硬幣重量不同，但不知這個硬幣比其它硬幣的重量是重還是輕。問確定隨意取出的一枚硬幣恰好是重量不同硬幣的所獲得的信息量是多少？并進一步確定它比其它硬幣是重還是輕所需要的信息量是多少？,解:(a)P(A)=1/81，I(A)=-lbP(A)=6.34（bit）。(b)P(B)=1/2，PP(A)P(B)1/162;I=-lbP=7.34（bit）。,22,4.聯(lián)合自信息量,bit/二元符號,隨機變量Z是兩個隨機變量X、Y的聯(lián)合，即Z=XY，其概率空間：,二元聯(lián)合符號的自信息量稱為聯(lián)合自信息量：,同理，三元聯(lián)合符號的聯(lián)合自信息量：,bit/三元符號,23,注意:當(dāng)(xi，yj)相互獨立時，有P(xi，yj)=P(xi)P(yj)，那么就有I(xi，yj)=I(xi)+I(yj)。(xi，yj)所包含的不確定度在數(shù)值上也等于它們的自信息量。,24,定義：,注意:在給定yj條件下，隨機事件xi所包含的不確定度在數(shù)值上與條件自信息量相同，但兩者含義不同。,5.條件自信息量,bit/符號,定義兩種條件自信息量：,bit/符號,25,條件自信息量物理意義：,26,幾個關(guān)于條件自信息量的例子：,27,（1）由于棋子落入任一方格都是等可能的，則,棋子落入某方格的不確定性就是自信息量,bit/符號,28,解：設(shè)A表示“大學(xué)生”這一事件，B表示“身高1.6m以上”這一事件，則：P(A)0.25；P(B)0.5；P(B|A)=0.75;因此：P(A|B)P(AB)/P(B)=P(A)P(B|A)/P(B)=0.750.25/0.5=0.375;I(A|B)-lbP(A|B)=1.42(bit)。,2.居住在某地區(qū)的女孩中有25是大學(xué)生，在女大學(xué)生中有75是身高1.6m以上的，而女孩中身高1.6m以上的占女生總數(shù)的一半。假如我們得知“身高1.6m以上的某女孩是大學(xué)生”的消息，問獲得多少信息量？,29,（二）互信息量,30,互信息量,設(shè)觀察輸入為:,設(shè)觀察結(jié)果為:,從yj中得到有關(guān)輸入符號xi的信息稱為xi與yj之間的互信息量（事件信息）（注意與聯(lián)合自信息量符號標(biāo)志不同）。,信息先驗不確定性后驗不確定性,xi在觀察到y(tǒng)j前不確定性xi在觀察到y(tǒng)j后不確定性,31,(1)yj對xi的互信息I(xi;yj)I(xi;yj)=I(xi)-I(xi/yj)含義互信息I(xi;yj)=自信息I(xi)-條件自信息I(xi/yj)I(xi)-信宿收到y(tǒng)j之前，對信源發(fā)xi的不確定度I(xi/yj)-信宿收到y(tǒng)j之后，對信源發(fā)xi的不確定度I(xi;yj)-收到y(tǒng)j而得到(關(guān)于xi)的互信息=不確定度的減少量,p(xi)先驗概率：信源發(fā)xi的概率p(xi/yj)后驗概率：信宿收到y(tǒng)j后，推測信源發(fā)xi的概率,即互信息量為后驗概率與先驗概率比值的對數(shù):,32,(2)xi對yj的互信息I(yj;xi)含義信源發(fā)xi前、后，信宿收到y(tǒng)j的不確定度的減少(3)I(xi;yj)=I(xi)+I(yj)-I(xi，yj)注意I(xi;yj)與I(xi，yj)不同！,33,(4)實在信息：后驗概率p(xi|yj)1，即收到y(tǒng)j時就能完全肯定此時的輸入一定是xi，xi的后驗不確定性完全消除。,即從輸出結(jié)果中得到了輸入實有的全部信息實在信息：,注意a.輸入的先驗不確定性在數(shù)值上等于自身含有的實在信息。b.信息與不確定性是兩個不同的物理概念，不是信息，只是不確定性，互信息量才是信息，把當(dāng)作信息只是說明一種數(shù)量上的相等關(guān)系。胡扯,34,(4)互信息量定義擴展：符號xi與符號對yjzk之間的互信息量定義為,35,2.互信息的性質(zhì)（具體推導(dǎo)可見課本p24）(1)對稱性I(xi;yj)=I(yj;xi)(2)X與Y獨立時I(xi;yj)=0(3)I(xi;yj)可為正、負(fù)、0當(dāng)事件xi和yj統(tǒng)計獨立時，互信息量為零;互信息量為正，說明yj的出現(xiàn)有助于減小xi的不確定性；反之，互信息量為負(fù)說明yj的出現(xiàn)增大了xi的不確定性（比如信道存在干擾）。(4)任何兩個事件之間的互信息量不可能大于其中任意事件的自信息量,36,I(xi;yj)可為正、負(fù)、0的舉例設(shè)yj代表“閃電”，則當(dāng)xi代表“打雷”時，I(xi/yj)=0，I(xi;yj)=I(xi)0當(dāng)xi代表“下雨”時，I(xi/yj)I(xi)，I(xi;yj)0當(dāng)xi代表“霧天”時，I(xi/yj)=I(xi)，I(xi;yj)=0當(dāng)xi代表“飛機正點起飛”時，I(xi/yj)I(xi)，I(xi;yj)0,37,3.條件互信息量給定zk條件下，xi與yj間的互信息量是,另外，還存在xi與yjzk之間的互信息量：,38,（該式推導(dǎo)見p25-26）,由上述兩式得,說明：一個聯(lián)合事件yjzk出現(xiàn)后提供的有關(guān)xi的信息量=zk事件出現(xiàn)后提供的有關(guān)xi的信息量在給定zk條件下再出現(xiàn)yj事件后所提供的有關(guān)xi的信息量,39,4.關(guān)于互信息的例子已知信源發(fā)出兩種消息，且此消息在二進制對稱信道上傳輸，信道傳輸特性為：求互信息量,解：根據(jù)得到：,40,一個布袋內(nèi)放100個球，其中80個球是紅色的，20個球是白色的，若隨機摸取一個球，猜測其顏色，求平均摸取一次所能獲得的自信息量。解:依據(jù)題意，這一隨機事件的概率空間為,（三)平均自信息量-熵,41,其中：x1表示摸出的球為紅球事件，x2表示摸出的球是白球事件。如果摸出的是紅球，則獲得的信息量是I（x1）=-log2p（x1）=-lb0.8=0.322bit如果摸出的是白球，則獲得的信息量是I（x2）=-log2p（x2）=-lb0.2=2.322bit,如果每次摸出一個球后又放回袋中，再進行下一次摸取。如此摸取n次，則紅球出現(xiàn)的次數(shù)為np（x1）次，白球出現(xiàn)的次數(shù)為np（x2）次。隨機摸取n次后總共所獲得的信息量為np（x1）I（x1）+np（x2）I（x2）,42,則平均隨機摸取一次所獲得的信息量為H（X）=1/nnp（x1）I（x1）+np（x2）I（x2）=-p（x1）log2p（x1）+p（x2）log2p（x2）,=0.722比特/次,說明：,自信息量I（x1）和I（x2）只是表征信源中各個符號的不確定度，一個信源總是包含著多個符號消息，各個符號消息又按概率空間的先驗概率分布，因而各個符號的自信息量是一個隨機變量，所以自信息量不能作為整個信源的信息測度。,43,因為X中各符號xi的自信息量I（xi）為非負(fù)值，p（xi）也是非負(fù)值，且0p(xi)1，故信源的平均自信息量H（X）也是非負(fù)量。,定義：離散信源熵H(X)(平均不確定度/平均信息量/平均自信息量/信息熵/熵)定義信源的平均不確定度H(X)為信源中各個符號不確定度的數(shù)學(xué)期望，即,單位為比特/符號或比特/符號序列,平均自信息量H（X）的定義公式與熱力學(xué)中熵的表示形式相同，所以又把H（X）稱為信源X的熵。熵是在平均意義上來表征信源的總體特性的，可以表征信源的平均不確定度。,44,某一信源，不管它是否輸出符號，只要這些符號具有某些概率特性，必有信源的熵值；這熵值是在總體平均上才有意義，因而是一個確定值，一般寫成H（X），X是指隨機變量的整體（包括概率分布）。信息量則只有當(dāng)信源輸出符號而被接收者收到后，才有意義，這就是給予接收者的信息度量，這值本身也可以是隨機量，也可以與接收者的情況有關(guān)。,6）當(dāng)某一符號的概率為零時，在熵公式中無意義，為此規(guī)定這時的也為零。當(dāng)信源X中只含一個符號時，必定有，此時信源熵H（X）為零。,7）平均自信息量H（X）表示集X中事件出現(xiàn)的平均不確定性，即在觀測之前，確定集X中出現(xiàn)一個事件平均所需的信息量；或者說在觀測之后，集X中出現(xiàn)一個事件平均給出的信息量。,45,例：電視屏上約有500600=3105個格點，按每點有10個不同的灰度等級考慮，則共能組成個不同的畫面。按等概率計算，平均每個畫面可提供的信息量為,=31053.32比特/畫面,46,例：有一篇千字文章，假定每字可從萬字表中任選，則共有不同的千字文N=100001000=104000篇仍按等概率1/100001000計算，平均每篇千字文可提供的信息量為H（X）log2N410333213104比特千字文,比較：,“一個電視畫面”平均提供的信息量遠(yuǎn)遠(yuǎn)超過“一篇千字文”提供的信息量。,47,例：設(shè)信源符號集X=x1,x2,x3，每個符號發(fā)生的概率分別為p（x1）=1/2，p（x2）l4，p（x3）14。則信源熵為H（X）=1/2log22+1/4log24+1/4log24=1.5比特/符號,48,例：該信源X輸出符號只有兩個，設(shè)為0和1。輸出符號發(fā)生的概率分別為p和q，pq=l。即信源的概率空間為,則二元信源熵為H（X）=-plbp-qlbq=-plbp-(1-p)lb(1-p)=H(p),49,50,說明：,信源信息熵H（X）是概率p的函數(shù)，通常用H（p）表示。p取值于0，1區(qū)間。H（p）函數(shù)曲線如圖所示。從圖中看出，如果二元信源的輸出符號是確定的，即p=1或q=1，則該信源不提供任何信息。反之，當(dāng)二元信源符號0和1以等概率發(fā)生時，信源熵達(dá)到極大值，等于1比特信息量。,51,幾個概念,定義：在給定yj條件下，xi的條件自信息量為I(xi/yj)，X集合的條件熵H（X/yj）為H（X/yj）=在給定Y（即各個yj）條件下，X集合的條件熵H(X/Y)定義為H（X/Y）=,條件熵,52,相應(yīng)地，在給定X（即各個xi）的條件下，Y集合的條件熵H(Y/X)定義為H(Y/X)=,【注意】：條件熵是在聯(lián)合符號集合XY上的條件自信息量的聯(lián)合概率加權(quán)統(tǒng)計平均值。,53,聯(lián)合熵（共熵）,定義：聯(lián)合熵是聯(lián)合符號集合XY上的每個元素對xiyj的聯(lián)合自信息量的聯(lián)合概率加權(quán)統(tǒng)計平均值。定義為H（XY）=【說明】表示X和Y同時發(fā)生的平均不確定度。,54,聯(lián)合熵H（XY）與熵H（X）及條件熵H（X/Y）之間存在下列關(guān)系：,1）H（XY）H（X）H（YX）H（XY）H（Y）H（XY）2）H（XY）H（X）H（YX）H（Y）即H（XY）H（X）H（Y）（當(dāng)X與Y相互獨立時，等號成立！共熵得到最大值！）,【注】上式表明，從平均意義上講，條件熵在一般情形下總是小于無條件熵。從直觀上說，由于事物總是聯(lián)系的，因此對隨機變量X的了解平均講總能使Y的不確定性減少。同樣，對Y的了解也會減少X的不確定性。,55,證明:,同理:,56,所以,57,同理：,2）的證明見課本p29（略）,三維聯(lián)合符號集合XYZ上的共熵H(XYZ):,存在下列關(guān)系：,1）H（X