第二章信息的度量

1、第一章第一章 信息科學(xué)及其發(fā)展信息科學(xué)及其發(fā)展l1.1 通信系統(tǒng)的基本概念l1.2 信息科學(xué)的有關(guān)概念l1.3 信息理論的研究內(nèi)容l1.4 香農(nóng)信息論概述通信系統(tǒng)模型通信系統(tǒng)模型信源編碼加密信道編碼信 道信道譯碼解密信源譯碼信宿密鑰源噪 聲密鑰源信源信息、消息和信號信息、消息和信號l信息l一個抽象的概念，可以定量的描述。信息、物質(zhì)和能量是構(gòu)成一切系統(tǒng)的三大要素l消息l是信息的載體，相對具體的概念，如語言，文字，數(shù)字，圖像l信號l表示消息的物理量，電信號的幅度，頻率，相位等等通信系統(tǒng)傳輸?shù)氖切盘?，信號是消息的載體，消息中的未知成分是信息。信息的特征信息的特征l未知性或不確定性。l又不知到知，等效

2、為不確定性的集合的元素的減少。l可以度量。l可以產(chǎn)生、消失，可以被攜帶、存儲和處理。l可以產(chǎn)生動作。信息論要解決的基本問題信息論要解決的基本問題l什么是信息？如何度量？l在給定的信道中，信息傳輸有沒有極限？l信息能否被壓縮和恢復(fù)？極限條件是什么？l從實(shí)際環(huán)境（如干擾，噪聲）中抽取信息，極限條件是什么？l允許一定失真的條件下，信息能否被更大程度地壓縮？極限條件是什么？l設(shè)計(jì)什么樣的系統(tǒng)才能達(dá)到上述極限？l現(xiàn)實(shí)中，接近極限的設(shè)備是否存在？信息量、信道容量、熵、香農(nóng)定理、香農(nóng)公式等。信息論的研究內(nèi)容信息論的研究內(nèi)容l狹義信息論（香農(nóng)信息論）l研究信息測度，信道容量以及信源和信道編碼理論l一般信息論l

3、研究信息傳輸和處理問題，除香農(nóng)信息論外還包括噪聲理論，信號濾波和預(yù)測，統(tǒng)計(jì)檢測和估值理論，調(diào)制理論，信息處理理論和保密理論l廣義信息論l除上述內(nèi)容外，還包括自然和社會領(lǐng)域有關(guān)信息的內(nèi)容，如模式識別，計(jì)算機(jī)翻譯，心理學(xué)，遺傳學(xué)，神經(jīng)生理學(xué)研究通信系統(tǒng)的目的研究通信系統(tǒng)的目的l找到信息傳輸過程的共同規(guī)律，以提高信息傳輸?shù)目煽啃?、有效性、保密性和認(rèn)證性，以達(dá)到信息傳輸系統(tǒng)最優(yōu)化。l可靠性: 使信源發(fā)出的消息經(jīng)過信道傳輸以后，盡可能準(zhǔn)確地、不失真地再現(xiàn)在接收端。l有效性: 經(jīng)濟(jì)效果好，即用盡可能短的時間和盡可能少的設(shè)備來傳送一定數(shù)量的信息。 l保密性: 隱蔽和保護(hù)通信系統(tǒng)中傳送的消息，使它只能被授權(quán)接

4、收者獲取，而不能被未授權(quán)者接收和理解。 l認(rèn)證性: 指接收者能正確判斷所接收的消息的正確性和完整性，而不是偽造的和被篡改的。香農(nóng)信息論香農(nóng)信息論l信息的度量l信息量、熵l無失真信源編碼l香農(nóng)第一定理l信道編碼l香農(nóng)第二定理l帶限信道傳輸能力l信道容量公式（香農(nóng)公式）l信息傳輸失真及差錯l信息率失真理論、香農(nóng)第三定理、信息價值l網(wǎng)絡(luò)信息傳輸l網(wǎng)絡(luò)信息理論l保密通信香農(nóng)信息論體系結(jié)構(gòu)香農(nóng)信息論體系結(jié)構(gòu)Shannon信息論壓縮理論有失真編碼無失真編碼等長編碼定理Shannon1948McMillan1953變長編碼定理Shannon1948McMillan1956Huffman碼(1952)、Fan

5、o碼算術(shù)碼(1976,1982)LZ碼(1977,1978)率失真理論ShannonGallagerBerger壓縮編碼JPEGMPEG傳輸理論信道編碼定理網(wǎng)絡(luò)信息理論糾錯碼編碼調(diào)制理論網(wǎng)絡(luò)最佳碼第二章第二章 信息的度量信息的度量l2.1 度量信息的基本思路l2.2 信源熵和條件熵l2.3 互信息量和平均互信息量l2.4 多維隨機(jī)變量的熵單消息（符號）信源單消息（符號）信源l它是最簡單也是最基本的信源，是組成實(shí)際信源的基本單元。它可以用信源取值隨機(jī)變量的范圍X和對應(yīng)概率分布P(X)共同組成的二元序?qū),P(X)來表示。l當(dāng)信源給定，其相應(yīng)的概率空間就已給定；反之，如果概率空間給定，這就表示相應(yīng)

6、的信源已給定。所以，概率空間能表征這離散信源的統(tǒng)計(jì)特性，因此有時也把這個概率空間稱為信源空間。 單符號離散信源單符號離散信源l這些信源可能輸出的消息數(shù)是有限的或可數(shù)的，而且每次只輸出其中一個消息。因此，可以用一個離散型隨機(jī)變量X來描述這個信源輸出的消息。這個隨機(jī)變量X的樣本空間就是符號集A；而X的概率分布就是各消息出現(xiàn)的先驗(yàn)概率，信源的概率空間必定是一個完備集。l在實(shí)際情況中，存在著很多這樣的信源。例如投硬幣、書信文字、計(jì)算機(jī)的代碼、電報(bào)符號、阿拉伯?dāng)?shù)字碼等等。這些信源輸出的都是單個符號(或代碼)的消息，它們符號集的取值是有限的或可數(shù)的。我們可用一維離散型隨機(jī)變量離散型隨機(jī)變量X來描述這些信源

7、的輸出。它的數(shù)學(xué)模型就是離散型的概率空間：單符號離散信源單符號離散信源例：對于二進(jìn)制數(shù)據(jù)、數(shù)字信源：X=0,1，則有 011p201010,10,11 1,2 2pxxUppP當(dāng)1212:,.,.,( ):( ),( ), .,( ), .,( )iNiNXxxxxXPXPxPxPxPxP 1( ) 1niiPx信息的度量信息的度量l信息的度量（信息量）和不確定性消除的程度有關(guān)，消除了多少不確定性，就獲得了多少信息量；l不確定性就是隨機(jī)性，可以用概率論和隨機(jī)過程來測度不確定性的大小，出現(xiàn)概率小的事件，其不確定性大，反之，不確定性??；l由以上兩點(diǎn)可知：概率小 信息量大，即信息量是概率的單調(diào)遞減函

8、數(shù)；l此外，信息量應(yīng)該具有可加性；信息量的特點(diǎn)信息量的特點(diǎn) l事件（或消息）輸出的信息量僅依賴于它的概率，而與它的取值無關(guān)。l信息量是概率分布的連續(xù)函數(shù)。l信息量是概率分布的減函數(shù)。l統(tǒng)計(jì)獨(dú)立的兩個信源產(chǎn)生的兩個事件，其聯(lián)合信息量應(yīng)為各事件信息量之和。對數(shù)函數(shù)！自信息量自信息量l由于信息量與概率成反比，并且具有可加性，可以證明，信息量的計(jì)算式為 其中Pk是事件Xk發(fā)生的概率，這也是先農(nóng)關(guān)于(自)信息量的度量(概率信息)；l自信息量 I(xk) 的含義l當(dāng)事件 xk發(fā)生以前，表示事件xk發(fā)生的不確定性；l當(dāng)事件 xk發(fā)生以后，表示事件xk所提供的信息量；kkkPpxI22log1log)( 自信

9、息量自信息量l計(jì)算信息量主要要注意有關(guān)事件發(fā)生概率的計(jì)算；l例：從26個英文字母中，隨即選取一個字母，則該事件的自信息量為 I = -log2 (1/26) = 4.7 比特l例：設(shè)m比特的二進(jìn)制數(shù)中的每一個是等概率出現(xiàn)的(這樣的數(shù)共有2m個)，則任何一個數(shù)出現(xiàn)的自信息為: I = -log2 (1/ 2m) = m 比特/符號自信息量自信息量l自信息量的單位l自信息量的單位取決于對數(shù)的底；l底為2，單位為“比特（bit）”；l底為e，單位為“奈特（nat）”；l底為10，單位為“哈特（hat）”；l1 nat = 1.44bit , 1 hat = 3.32 bit；仙農(nóng)關(guān)于信息定義和度量的

10、優(yōu)點(diǎn)仙農(nóng)關(guān)于信息定義和度量的優(yōu)點(diǎn)l優(yōu)點(diǎn)l它是一個科學(xué)的定義，有明確的數(shù)學(xué)模型和定量計(jì)算；l它與日常生活中關(guān)于信息的理解不矛盾；l它排除了對信息一詞某些主觀性的含義，是純粹形式化的概念；仙農(nóng)關(guān)于信息定義和度量的局限仙農(nóng)關(guān)于信息定義和度量的局限l局限l這個定義的出發(fā)點(diǎn)是假設(shè)事物的狀態(tài)可以用一個以經(jīng)典集合論為基礎(chǔ)的概率模型來描述，然而實(shí)際存在的某些事物運(yùn)動狀態(tài)很難用一個合適的經(jīng)典概率模型來描述，甚至在某些情況下不存在這樣的模型；l這個定義和度量沒有考慮收信者的主觀性和主觀意義，也拋開了事物本身的具體含義、用途、重要程度和引起的后果等，這與實(shí)際不完全一致。條件自信息、聯(lián)合自信息、互信息量條件自信息、聯(lián)

11、合自信息、互信息量)|(log)|(2121uupuuI)(log)(jkjkyxpyxI)|()()|()();(kjjjkkjkxyIyIyxIxIyxI(|)(;)log()kjkjkp xyI x yp x自信息、條件自信息和互信息自信息、條件自信息和互信息)()()();(jkjkjkyxIyIxIyxII(xk)I(yj)I(xk ;yj)互信息量的性質(zhì)互信息量的性質(zhì)l對稱性。l值域?yàn)閷?shí)數(shù)（可以小于0）。l不大于其中任一事件的自信息量。條件互信息量條件互信息量(|)( ;|)log(|)ijkijkikp xy zI x yzp xz熵熵(Entropy)的概念的概念l通常研究單獨(dú)

12、一個事件或單獨(dú)一個符號的信息量是不夠的，往往需要研究整個事件集合或符號序列(如信源)的平均的信息量(總體特征)，這就需要引入新的概念；熵熵(Entropy)的概念（續(xù)）的概念（續(xù)）l假設(shè)離散事件集合的概率特性由以下數(shù)學(xué)模型表示： 則如果將自信息量看為一個隨機(jī)變量，其平均信息量為自信息量的數(shù)學(xué)期望，其定義為：l由于這個表達(dá)式和統(tǒng)計(jì)物理學(xué)中熱熵的表達(dá)式相似，且在概念上也有相似之處，因此借用“熵”這個詞，把H(X)稱為信息“熵”； )(.)()(.)(2121nnaPapapaaaxpX niiaP11)( niiiiapapapEXH1)(log*)()(1log)(熵的計(jì)算熵的計(jì)算l例：設(shè)某信源

13、輸出四個符號，其符號集合的概率分布為： 則其熵為：81814121432143214321ssssppppssssS符號比特/75. 18log824log412log21log)(41iiippSH熵的含義熵的含義l熵是從整個集合的統(tǒng)計(jì)特性來考慮的，它是從平均意義上來表征集合的總體特征的。 l熵表示事件集合中事件發(fā)生后，每個事件提供的平均信息量；l熵表示事件發(fā)生前，集合的平均不確定性；l例：有2個集合，其概率分布分別為： 分別計(jì)算其熵，則：H(X)=0.08 bit /符號, H(Y)=1bit / 符號01. 099. 0)(21aaXPX5 . 05 . 0)(21aaYPY熵的性質(zhì)熵的

14、性質(zhì)l連續(xù)性: 當(dāng)某事件Ek的概率Pk稍微變化時，H函數(shù)也只作連續(xù)的不突變的變化；l對稱性: 熵函數(shù)對每個Pk 對稱的。該性質(zhì)說明熵只與隨機(jī)變量的總體結(jié)構(gòu)有關(guān)，與事件集合的總體統(tǒng)計(jì)特性有關(guān)；l非負(fù)性: H=0；l確定性，即：H(1,0)=H(1,0,0)=H(1,0,0,0)=0，即當(dāng)某一事件為確定事件時，整個事件集合的熵為0；熵的性質(zhì)（續(xù)）熵的性質(zhì)（續(xù)）l極值性，即當(dāng)所有事件等概率出現(xiàn)時，平均不確定性最大，從而熵最大，即：nnnnHPPPHnlog)1,.,1,1(),.,(21 熵的性質(zhì)（續(xù)）熵的性質(zhì)（續(xù)）l可加性: 設(shè)有一事件的完全集合E1,E2,En,其熵為H1(p1,p2,pn)?，F(xiàn)

15、設(shè)其中一事件En又劃分為m個子集，即： 這時構(gòu)成的三個概率空間分別具有熵函數(shù)： 這說明對集合的進(jìn)一步劃分會使它的不確定性增加，即熵總是往大增加。1.,2111nmkkmkmkknknpqqqqFpqpFE則有；111221113213(,.,);(,.,;,.,);(.)*mnnmnnnqqHp ppHppqqHppHHpH它們之間具有關(guān)系：熵的性質(zhì)（續(xù)）熵的性質(zhì)（續(xù)）l例子: 設(shè)事件A1, A2構(gòu)成全集，p(A1)=p1=3/15, p(A2)=p2=12/15. 現(xiàn)將事件A2又進(jìn)一步劃分為2個子集B和C，且p(B)=q1=4/15, p(C)=q2=8/15,則：3122221321122

16、11*1512)103log15(151),()323log125log15(151),;()245log15(151)1512log1512153log153(),(HHHpqpqHqqpHppH顯然，其結(jié)果滿足：剩余度剩余度Hl剩余度刻畫了事件集合中符號的相關(guān)性程度，其定義為： H=H0 - H 其中：H0為熵的最大值，H為熵的實(shí)際值；剩余度剩余度H (續(xù)續(xù))l例：英文字母表l由27個元素構(gòu)成的集合的熵的最大值為：H0=log27=4.75 bit/符號 (當(dāng)27個元素等概率分布時)l對于實(shí)際的有意義英文來說，由于受到英語構(gòu)詞法等規(guī)則的限制，其字母不是等概率出現(xiàn)的，而呈現(xiàn)一定的分布（如下表

17、）。由此可以計(jì)算出實(shí)際英文字母表(26字母+1空格)的熵為: H(x)=4.03bits/字母；l因此，英文字母表的剩余度H=4.75-4.03=0.72l以上結(jié)論僅僅從英文字母的概率分布得出。一般認(rèn)為，如果考慮到英語的所有特點(diǎn)，則實(shí)際英文字母表的熵為 H=1.4bits/字母；也就是說，英語的冗余是很大的。剩余度剩余度H (續(xù)續(xù))l正是因?yàn)樵嫉男畔⒍加腥哂啵庞锌赡軐π畔⑦M(jìn)行壓縮，以盡量減少冗余，提高每個符號攜帶的信息量；但另一方面，冗余信息可以提高信息的抗干擾能力，如果信息的某部分在傳輸中被損壞，則通過冗余有可能將其恢復(fù)。 (冗余小,有效) (冗余大,可靠) 中國 中華人民共和國l從提高

18、信息傳輸效率的角度出發(fā)，總是希望減少剩余度（壓縮），這是信源編碼的作用；從提高信息抗干擾能力來看，總是希望增加或保留剩余度，這是信道編碼的作用；二維離散概率量的熵二維離散概率量的熵l二維的系統(tǒng)能表達(dá)通信系統(tǒng)發(fā)送和接收的關(guān)系，也能表達(dá)存儲系統(tǒng)的存取關(guān)系，二維的結(jié)果還可以向多維系統(tǒng)推廣，因此這個研究具有重要的意義。聯(lián)合事件集合和概率矩陣聯(lián)合事件集合和概率矩陣邊際概率 mjjiiyxpxP1),()( njjijyxpyP1),()( mnnnmmFEFEFEFEFEFEFEFEFEEF.212221212111兩個事件集合E、F的聯(lián)合事件集合 ),(.)2,()1 ,(.),2(.)2,2()1

19、,2(), 1(.)2, 1()1 , 1(),(mnpnpnpmpppmpppYXP nimjjip111),(用X、Y表示E、F對應(yīng)的隨機(jī)變量，則其聯(lián)合概率矩陣為邊際熵和聯(lián)合熵邊際熵和聯(lián)合熵通過熵的定義，可以得到：邊際熵 niiixpxpXH1)(log)()( mjjjypypYH1)(log)()(聯(lián)合熵),(log),(),(11jinimjjiyxpyxpYXH 條件概率和條件熵條件概率和條件熵條件概率)(),()|(jjijiypyxpyxp 并且1)|(1 nijiyxp當(dāng)已知特定事件 yj 出現(xiàn)時，下一個出現(xiàn)的是 xi 的不確定性為：)|(logjiyxp對集合 X 中所有元

20、素統(tǒng)計(jì)平均，其熵為： nijijijyxpyxpyXH1)|(log)|()|(條件概率和條件熵條件概率和條件熵上述熵值再對集合Y中的元素做統(tǒng)計(jì)平均，得條件熵：mjnijijimjjinijijjinijimjjmjjjyxpyxpyxpyxpypyxpyxpypyXHypYXH1111111)|(log),()|(log)|()()|(log)|()()|()()|(mjnijijimjjinijijjinijimjjmjjjyxpyxpyxpyxpypyxpyxpypyXHypYXH1111111)|(log),()|(log)|()()|(log)|()()|()()|(同理可得：nimjijjixypyxpXYH11)|(log),()|(例子例子l例：擲兩個均勻的六面體，六面體的每一面上分