中南大學信息論與編碼課件Inf-T-C-1.3N講課稿

信息論與編碼(biānmǎ)張祖平/ZhangZuping電子信息工程系SchoolofInformationScienceandEngineering,CentralSouthUniversity,zpzhang@InformationTheory&Coding第一章單符號(fúhào)離散信源第一頁，共40頁。信息熵的代數(shù)性質(zhì)信源的數(shù)學模型信源符號的自信量信源的信息熵本章(běnzhānɡ)主要內(nèi)容(MainContent)信息熵的解析性質(zhì)最大離散熵定理熵函數(shù)的唯一性定理2013秋季(qiūjì)信息112*第二頁，共40頁。信源的數(shù)學模型2013秋季(qiūjì)信息113*第三頁，共40頁。什么(shénme)是信源信源就是信息的來源，是產(chǎn)生消息、消息序列以及連續(xù)消息的來源。信源可以是人、機器、自然界的物體等等。信源發(fā)出信息的時候，一般以某種方式的消息表現(xiàn)出來，可以是符號，如文字、語言等，也可以是如圖像、聲響等等。什么(shénme)是單符號離散信源信源信道信宿2013秋季(qiūjì)信息114*第四頁，共40頁。信源的分類連續(xù)(liánxù)信源：發(fā)出在時間上或幅度上都是連續(xù)(liánxù)分布的連續(xù)(liánxù)消息的信源(1)時間連續(xù)(liánxù)，幅度離散(2)時間離散，幅度連續(xù)(liánxù)(3)時間連續(xù)(liánxù)，幅度連續(xù)(liánxù)離散信源：發(fā)出在時間上和幅度上都是離散分布的離散消息的信源什么是單符號(fúhào)離散信源2013秋季(qiūjì)信息115*第五頁，共40頁。信源的分類無記憶信源：信源不同時刻發(fā)出的消息之間互不干擾、互相(hùxiāng)獨立有記憶信源：信源不同時刻發(fā)出的消息相互依賴什么(shénme)是單符號離散信源無記憶信源和有記憶信源誰比較常見(chánɡjiàn)？舉例2013秋季信息116*第六頁，共40頁。信源的分類單符號信源：信源每次只發(fā)出一個符號代表一個消息多符號信源：信源每次發(fā)出一組含兩個(liǎnɡɡè)以上符號的符號序列代表一個消息什么是單符號(fúhào)離散信源單符號信源和多符號信源屬于(shǔyú)離散信源嗎？2013秋季信息117*第七頁，共40頁。信源的分類結(jié)合單符號與多符號、無記憶和有記憶的離散信源，有四種(sìzhǒnɡ)：（1）發(fā)出單個符號的無記憶離散信源；（2）發(fā)出符號序列的無記憶離散信源；（3）發(fā)出單個符號的有記憶離散信源；（4）發(fā)出符號序列的有記憶離散信源。什么(shénme)是單符號離散信源本章主要討論：單符號離散信源（無記憶）2013秋季(qiūjì)信息118*第八頁，共40頁。信源的狀態(tài)空間信源的可能取值的集合。對單符號(fúhào)離散信源而言，是所有可能輸出的單個符號(fúhào)的消息的集合?？捎梅?fúhào)集合A={a1,a2,…,aq}來表示，取值是有限或可數(shù)的。更常見的是用數(shù)學中一維離散型隨機變量X來表示。信源的數(shù)學模型2013秋季(qiūjì)信息119*第九頁，共40頁。

信源的數(shù)學模型先驗概率：是指根據(jù)以往經(jīng)驗(jīngyàn)和分析得到的概率2013秋季(qiūjì)信息1110*第十頁，共40頁。

信源的數(shù)學模型2013秋季(qiūjì)信息1111*第十一頁，共40頁。練習(liànxí)箱子(xiāngzi)中有32個球，紅球16個，黃球8個，藍球和白球各4個從箱子(xiāngzi)中每次拿一個球，記錄顏色，并放回。把上述看作一個單符號離散信源，請寫出其信源空間。2013秋季(qiūjì)信息1112*第十二頁，共40頁。信源符號的自信量2013秋季(qiūjì)信息1113*第十三頁，共40頁。信息的度量問題信源發(fā)出某一消息后，它到底能提供多少信息量？對單符號離散信源，信源發(fā)出某個符號，此符號能帶來多少信息量？香農(nóng)的第三個論點“不確定性論”香農(nóng)說：在通信中，收信者所獲取的信息量，在數(shù)量上等于通信前后不確定性的消除(減少)的量。信息量=通信前的不確定性–通信后的不確定性信息就是用來消除不確定性的東西(dōngxī)！這為我們度量信息指明了方向！比如：老師講述某題目的解法，有的學生可能聽完就全會了。有的學生可能由于聽音樂、講小話、開小差、玩手機，導致聽得似懂非懂。信源符號(fúhào)的自信量2013秋季(qiūjì)信息1114*第十四頁，共40頁。有噪聲情況信源發(fā)某一符號ai，信道(xìndào)中有隨機噪聲干擾，收信者收到的是ai的某種變型bi。收信者從bi中獲取關(guān)于ai的信息量,以I(ai;bi)表示。I(ai;bi)=收到bi前，收信者對ai存在的不確定性—收到bi后，收信者對ai仍然存在的不確定性無噪聲情況假定無噪聲。有bi＝ai，那么收到bi后，對ai仍存在的不確定性為0，則I(ai;bi)表示為I(ai;ai)，并且簡化的記作I(ai)。I(ai)=收到ai前，收信者對ai存在的不確定性—收到ai后，收信者對ai仍然存在的不確定性(0)=收到ai前，收信者對信源發(fā)ai的不確定性。我們稱I(ai)為信源符號ai的“自信息量”，也就是ai本身所含有的全部信息量，或者說收到ai獲得的全部信息量。信源符號(fúhào)的自信量152013秋季(qiūjì)信息1115*第十五頁，共40頁。自信量I(ai)兩種含義：（1）收到ai前，收信者對信源發(fā)ai的不確定性（2）收到ai后，ai提供的所有信息量自信量自信量與概率公式信源是以一定先驗概率來發(fā)送ai的?！暗絘i前，收信者對信源發(fā)ai的不確定性”就可以表述為“信源發(fā)送符號ai的不確定性”。不確定性和可能性（概率）有關(guān)系(guānxì)的，所以自信息量I(ai)一定可以表達為信源發(fā)符號ai的先驗概率p(ai)的某一函數(shù)信源符號(fúhào)的自信量2013秋季(qiūjì)信息1116*第十六頁，共40頁。I(ai)=f[p(ai)]的推理（1）小概率事件，不確定性大，一旦出現(xiàn)必然使人感到(gǎndào)意外，因而產(chǎn)生的信息量就大；大概率事件，不確定性小，因而信息量小。信源符號(fúhào)的自信量2013秋季(qiūjì)信息1117*第十七頁，共40頁。I(ai)=f[p(ai)]的推理（2）由（1）可以得到I(ai)與p(ai)成反比，也就是單調(diào)遞減（3）分析一下極值情況今天太陽照常從東邊升起今天太陽從西邊(xībian)升起來了?。。⌒旁捶?fúhào)的自信量2013秋季(qiūjì)信息1118*第十八頁，共40頁。自信量的度量公式從前面的推理，香農(nóng)得到了自信量的度量公式自信量的度量公式的單位自信息量的單位取決于對數(shù)的底；底為2，單位為“比特（bit,binaryunit）”；底為e，單位為“奈特（nat,natureunit）”；底為10，單位為“哈特（hat,Hartley）”；根據(jù)(gēnjù)換底公式得：1nat=1.44bit,1hat=3.32bit；一般計算都采用以“2”為底的對數(shù)，為了書寫簡潔，常把底數(shù)“2”略去不寫。信源符號(fúhào)的自信量這里的比特(bǐtè)和計算機二進制數(shù)的比特(bǐtè)有什么區(qū)別和聯(lián)系2013秋季信息1119*第十九頁，共40頁。自信息量的特性１２３非負性；４單調(diào)遞減性；５可加性。關(guān)于可加性兩個相對(xiāngduì)獨立的不同的消息所提供的信息量應等于它們分別提供的信息量之和，即自信息滿足可加性。信源符號(fúhào)的自信量2013秋季(qiūjì)信息1120*第二十頁，共40頁。練習(liànxí)證明自信息量的可加性！兩個相對獨立的不同的消息所提供的信息量應等于(děngyú)它們分別提供的信息量之和，即自信息滿足可加性。條件(tiáojiàn)概率的獨立性:設(shè)A，B為兩隨機事件，A,B相互獨立。那么A,B同時發(fā)生的概率P(AB)=P(A)*P(B),2013秋季信息1121*第二十一頁，共40頁。練習(liànxí)某地二月份天氣的概率分布統(tǒng)計如下，這四種氣候的自信息量分別(fēnbié)為多少？從自信量的數(shù)值可以看出信息背后的事件類型(lèixíng)：晴天的自信量是1bit，那么就可以知道晴天發(fā)生的概率是一半，那當?shù)靥鞖饪梢愿爬ǖ姆譃榍缣旌头乔缣靸煞N，是一個是否問題2013秋季信息1122*第二十二頁，共40頁。信源的信息熵2013秋季(qiūjì)信息1123*第二十三頁，共40頁。自信量I(a)使信息度量成為可能，但I(a)有局限I(a)只能表示具體符號a所提供的信息量，不能反映信源的總體(zǒngtǐ)信息量，因為信源可以發(fā)出多個不同的符號，X={ai;i=1…n}，并且信源發(fā)出不同的符號是有不同概率的。信源中各信息自信息量的數(shù)學期望（統(tǒng)計均值）來度量信源的信息量，這個統(tǒng)計量記作H(X)，即為信源X的“信息熵”，也是信源X的平均自信息量。信源的信息熵單位(dānwèi)：bit/(信源)符號2013秋季(qiūjì)信息1124*第二十四頁，共40頁。信息熵具有以下三種物理含義：1、表示信源輸出前，信源的平均不確定性2、表示信源輸出后，每個符號所攜帶的平均信息量3、反映了變量X的隨機性。信源熵是信源的平均不確定的描述。一般情況下它并不等于平均獲得的信息量。只有在無噪情況下，接收者才能正確無誤地接收到信源所發(fā)出的消息，消除了H(X)大小(dàxiǎo)的平均不確定性，所以獲得的平均信息量就等于H(X)。信源的信息熵2013秋季(qiūjì)信息1125*第二十五頁，共40頁。練習(liànxí)有一布袋內(nèi)放l00個球，其中(qízhōng)80個球是紅色的，20個球是白色的。如果被告知摸出的是紅球，那么獲得的信息量是：I(a1)＝－logp(a1)＝－log0.8=0.32（比特）如被告知摸出來的是白球，所獲得的信息量應為：I(a2)＝－logp(a2)＝－log0.2=2.32（比特）平均(píngjūn)摸取一次所能獲得的信息量為：H(X)=p(a1)I(a1)+p(a2)I(a2)=0.72（比特/符號）2013秋季信息1126*第二十六頁，共40頁。練習(liànxí)同時擲兩個正常的骰子，求(1)“3和5同時出現(xiàn)”這事件的自信息量；(2)“兩個1同時出現(xiàn)”這事件的自信息量；(3)兩個點數(shù)的各種組合(無序?qū)?的熵；(4)兩個點數(shù)之和(即2,3..12構(gòu)成(gòuchéng)的子集)的熵；(5)兩個點數(shù)中至少有一個是1的自信息量(1)4.17(比特/符號(fúhào))，提示：3和5同時出現(xiàn)的概率為=1/6*1/6*2=1/18(2)5.17(比特/符號(fúhào))，提示：兩個1同時出現(xiàn)的概率1/6*1/6=1/36(3)“兩個點數(shù)相同”的概率:1/36,共有6種情況;“兩個點數(shù)不同”的概率:1/18,共有15種情況.故平均信息量為:4.337比特/符號(fúhào)(4)3.274(比特/符號(fúhào))。信源模型(5)1.711(比特/符號(fúhào))。至少有一個1出現(xiàn)的概率為1/6+1/6-1/6*1/6=11/362013秋季信息1127*第二十七頁，共40頁。22013秋季(qiūjì)信息1128*第二十八頁，共40頁。22013秋季(qiūjì)信息1129*第二十九頁，共40頁。信息熵的代數(shù)性質(zhì)2013秋季(qiūjì)信息1130*第三十頁，共40頁。信息熵的代數(shù)(dàishù)性質(zhì)信源的總體(zǒngtǐ)信息測度，解剖數(shù)學性質(zhì)定理1.1熵函數(shù)H(p1,p2,…,pr)中的變量p1,p2,…,pr的順序置換，不會引起(yǐnqǐ)熵函數(shù)值的變化證明：H(p1,p2,…,pr)=-p1logp1-p2logp2-…-prlogpr定理1.2熵函數(shù)H(p1,p2,…,pr)≥0證明：H(p1,p2,…,pr)=-p1logp1-p2logp2-…-prlogpr0≤pi≤1

logpi≤02013秋季信息1131*第三十一頁，共40頁。信息熵的代數(shù)(dàishù)性質(zhì)定理1.3熵函數(shù)(hánshù)H(p1,p2,…,pr)概率分量pi(i=1,2,…,r)的，連續(xù)函數(shù)(hánshù)定理1.5設(shè)H(X)和H(Y)分別(fēnbié)代表兩個統(tǒng)計獨立的信源X和Y的信息熵，則有：H(XY)=H(X)+H(Y)2013秋季信息1132*第三十二頁，共40頁。信息熵的解析性質(zhì)2013秋季(qiūjì)信息1133*第三十三頁，共40頁。信息熵的解析(jiěxī)性質(zhì)定理(dìnglǐ)1.7設(shè)信源X的概率矢量為p:(p1,p2,…,pr),則熵函數(shù)H(p)是p的∩型凸函數(shù)定理1.8含有(hányǒu)r(r>1的正整數(shù))個概率分量的信源X的熵函數(shù)H(X)=H(p1,p2,…,pr)≤logr2013秋季信息1134*第三十四頁，共40頁。最大離散熵定理2013秋季(qiūjì)信息1135*第三十五頁，共40頁。最大離散(lísàn)熵定理定理1.9在所有(suǒyǒu)符號數(shù)（概率分量數(shù)）為r(r>1的正整數(shù))的信源中，等概率信源的熵達到最大，其最大值為logr直觀地從H(X)=H(p1,p2,…,pr)=-p1logp1-p2log