信息論與編碼2012

1、,信息論與編碼基礎(chǔ),學而不思則罔， 思而不學則殆。 孔子,信息論與編碼基礎(chǔ),離散信源,一、信源的數(shù)學模型及分類,二、離散信源的信息熵及其性質(zhì),三、離散無記憶的擴展信源,四、離散平穩(wěn)信源,五、信源的剩余度,信息論與編碼基礎(chǔ),離散信源,一、信源的數(shù)學模型及分類,二、離散信源的信息熵及其性質(zhì),三、離散無記憶的擴展信源,四、離散平穩(wěn)信源,五、信源的剩余度,信息論與編碼基礎(chǔ),離散信源,信源的分類,離散信源：電報、文字、代碼,07314575707,連續(xù)信源：模擬語音、模擬視頻,概念,樣本空間,概率空間,事物所有可能選擇的消息的集合。,一個樣本空間和它的概率測度。,信息論與編碼基礎(chǔ),離散信源,信息論與編碼

2、基礎(chǔ),離散信源,1) 信源輸出的消息由隨機變量描述,信息論與編碼基礎(chǔ),離散信源,定義2.1 若信源輸出的消息數(shù)是有限的或可數(shù)的，而且每次只輸出符號集中的一個消息，這樣的信源稱為簡單的離散信源。,信源空間,信息論與編碼基礎(chǔ),離散信源,樣本,概率,紅(100) 黃(50) 藍(25) 白(25),信息論與編碼基礎(chǔ),離散信源,定義2.2 若信源輸出的是單個符號的消息，但是其可能出現(xiàn)的消息數(shù)是不可數(shù)的無限值，即輸出消息的取值是連續(xù)的，這樣的信源稱為簡單的連續(xù)信源。,或,或,例如：語音信號；遙控系統(tǒng)中測得的電壓、溫度、壓力等連續(xù)數(shù)據(jù)。,信息論與編碼基礎(chǔ),離散信源,復雜信源,例1：中文自然語言文字信源,牛

3、,氣,沖 天,例2：離散化的平面灰度圖像信源,信息論與編碼基礎(chǔ),離散信源,2) 信源輸出的消息由隨機矢量描述,定義2.3 若離散信源輸出的消息是由一系列符號所組成的（不妨假設(shè)由N個符號組成，其中N為有限正整數(shù)或可數(shù)的無限值），這樣的信源稱為多維的離散信源。,信息論與編碼基礎(chǔ),離散信源,其中,1)離散無記憶信源,2)離散有記憶信源,馬爾可夫信源,擴展信源,信息論與編碼基礎(chǔ),離散信源,定義2.4 若連續(xù)信源輸出的消息是由一系列符號所組成的，這樣的信源稱為多維的連續(xù)信源。,2) 信源輸出的消息由隨機矢量描述,連續(xù)平穩(wěn)信源： 隨機矢量的各維概率密度都與時間起點無關(guān),信息論與編碼基礎(chǔ),離散信源,3) 信

4、源輸出的消息由隨機過程描述,隨機波形信源,只要是時間上或頻率上為有限的過程，就可以把隨機過程用一系列 時間離散的取樣值來表示，而每個取樣值都是連續(xù)型隨機變量。,隨機過程,隨機序列,離散信源,信息論與編碼基礎(chǔ),離散信源,一、信源的數(shù)學模型及分類,二、離散信源的信息熵及其性質(zhì),三、離散無記憶的擴展信源,四、離散平穩(wěn)信源,五、信源的剩余度,信息論與編碼基礎(chǔ),離散信源,1、自信息,2、信源的信息熵,3、熵的基本性質(zhì),信息論與編碼基礎(chǔ),離散信源,簡單的離散信源模型,信息論與編碼基礎(chǔ),離散信源,期末考試中，我擠進了班級十強。,期末考試中，我擠進了年級十強。,603教學樓已經(jīng)開始使用。,小明體育經(jīng)常不及格，

5、昨天測試成績排名第一。,現(xiàn)在正在進行信息論與編碼基礎(chǔ)課程學習。,北京天安門前有游客在照相。,1、自信息,度量信息的基本思路,若信源中事件xi的出現(xiàn)所帶來的信息量用I(xi)來表示并稱之為事件xi的自信息量， 則概率為p(xi)的信源輸出xi所包含的信息量I(xi)必須滿足以下幾個條件：,信息論與編碼基礎(chǔ),離散信源,度量信息的基本思路,1. 信源輸出xi所包含的信息量僅依賴于它的概率，而與它的取值無關(guān)。 2. I (xi)是p(xi)的連續(xù)函數(shù)。 3. I (xi )是p(xi)的減函數(shù)，即： 如果p(xi) p(xj)，則I(xi) I(xj)。 極限情況，若p(xi) = 0, 則 I(xi

6、) ； 若 p(xi) = 1, 則I(xi) = 0。 4.若兩個單符號離散信源（符號集合X, Y ）統(tǒng)計獨立, 則X中出現(xiàn)xi 、Y中出現(xiàn)yj的聯(lián)合信息量 I (xi , yj) = I (xi) + I (yj) 問題：什么函數(shù)能夠同時滿足以上條件呢？,信息論與編碼基礎(chǔ),離散信源,自信息含義,信息論與編碼基礎(chǔ),自信息,r = 2 bit,r = e nat,r = 10 hart,含義,離散信源,驗證(獨立相加性),信息論與編碼基礎(chǔ),離散信源,自信息量計算舉例,舉例 一個0, 1等概的二進制隨機序列，求任一碼元的自信息量。 解：任一碼元不是為0就是為1 因為 p(0) = p(1) =

7、1/2 所以 I (0) = I (1) = log (1/2) = 1(bit),信息論與編碼基礎(chǔ),離散信源,自信息量計算舉例,舉例,對于2n進制的數(shù)字序列, 假設(shè)每一符號的出現(xiàn)完全隨機且概率相等，求任一符號的自信息量。 解：設(shè)2n進制數(shù)字序列任一碼元xi的出現(xiàn)概率為p (xi)，根據(jù)題意， p(xi) = 1/2n I (xi ) = log(1/2n) = n (bit) 事件的自信息量只與其概率有關(guān)，而與它的取值無關(guān)。,信息論與編碼基礎(chǔ),離散信源,信息量與不確定性的關(guān)系,信源中某一消息發(fā)生的不確定性越大，一旦它發(fā)生，并為收信者收到后，消除的不確定性就越大，獲得的信息也就越大。 由于種種

8、原因（例如噪聲太大），收信者接收到受干擾的消息后，對某信息發(fā)生的不確定性依然存在或者一點也未消除時，則收信者獲得較少的信息或者說一點也沒有獲得信息。,信息論與編碼基礎(chǔ),離散信源,信息量的直觀定義： 收到某消息獲得的信息量不確定性減少的量 (收到此消息前關(guān)于某事件發(fā)生的不確定性) (收到此消息后關(guān)于某事件發(fā)生的不確定性) 在無噪聲時，通過信道的傳輸，可以完全不失真地收到所發(fā)的消息，收到此消息后關(guān)于某事件發(fā)生的不確定性完全消除，此項為零。因此得 收到某消息獲得的信息量 收到此消息前關(guān)于某事件發(fā)生的不確定性 信源輸出的某消息中所含有的信息量,信息量與不確定性的關(guān)系,信息論與編碼基礎(chǔ),離散信源,信息量

9、與不確定性的關(guān)系,信宿端收到某一消息后所得到的信息量，可以等效為接收者在通信前后“不確定”因素的減少或消除。 事件的不確定性可用不確定度描述，它同樣是事件概率的函數(shù)，在數(shù)值和量綱上和自信息量相等，因此都可以用右式來計算： 某一隨機事件的出現(xiàn)所給出的信息量（自信息量），在數(shù)值上與該隨機事件的不確定度不但相關(guān)而且相等，即事件的出現(xiàn)等效成事件不確定集合的元素的減少，或簡稱為事件不確定度的減少。,信息論與編碼基礎(chǔ),離散信源,信息量與不確定性,自信息量和該事件的不確定度的含義有本質(zhì)的區(qū)別。 不確定度只與事件的概率有關(guān)，是一個統(tǒng)計量，在靜態(tài)狀態(tài)下也存在； 自信息量只有該隨機事件出現(xiàn)時才給出，不出現(xiàn)時不給出

10、，因此它是一個動態(tài)的概念。,信息論與編碼基礎(chǔ),離散信源,自信息含義,當事件xi發(fā)生以前：表示事件xi發(fā)生的不確定性。 當事件xi發(fā)生以后：表示事件xi所含有（或所提供）的信息量。在無噪信道中，事件xi發(fā)生后，能正確無誤地傳輸?shù)绞招耪?，所以I(xi)可代表接收到消息xi后所獲得的信息量。這是因為消除了I(xi)大小的不確定性，才獲得這么大小的信息量。 自信息的測度單位及其換算關(guān)系 信息論中“比特”與計算機術(shù)語中“比特”區(qū)別,信息論與編碼基礎(chǔ),離散信源,自信息的測度單位及其換算關(guān)系,如果取以2為底，則信息量單位稱為比特(binary unit) I(xi)=log2(1/p(xi) 比特 如果取以

11、e為底，則信息量單位稱為奈特(nature unit) I(xi)=ln(1/p(xi) 奈特 如果取以10為底，則信息量單位稱為哈特(Hart unit,以紀念哈特萊首先提出用對數(shù)來度量消息) I(xi)=lg(1/p(xi) 哈特 1奈特1.44比特 1哈特3.32比特 在通信及目前的絕大多數(shù)信息傳輸系統(tǒng)中，都是以二進制為基礎(chǔ)的，因此信息量單位以比特最為常用。因此一般都采用以“2”為底的對數(shù)，為了書寫簡潔，有時把底數(shù)2略去不寫。,信息論與編碼基礎(chǔ),離散信源,信息論中“比特”與 計算機術(shù)語中“比特”區(qū)別,如果p(xi)=1/2，則I(xi)=1比特。所以1比特信息量就是兩個互不相容的等可能事

12、件之一發(fā)生時所提供的信息量。 信息論中“比特”是指抽象的信息量單位； 計算機術(shù)語中“比特”是代表二元數(shù)字； 這兩種定義之間的關(guān)系是：每個二元數(shù)字所能提供的最大平均信息量為1比特。,信息論與編碼基礎(chǔ),離散信源,信息論與編碼基礎(chǔ),離散信源,例 假設(shè)一次擲兩個各自均勻、互相不可區(qū)分又互不相關(guān)的骰子。如事件（A）（B）（C）分別表示：(A)僅有一個骰子是3；（B）至少有一個骰子是4；（C）骰子點數(shù)的總和是偶數(shù)。試計算事件（A）（B）（C）發(fā)生后所提供的信息量。,信息論與編碼基礎(chǔ),離散信源,信息論與編碼基礎(chǔ),離散信源,信息論與編碼基礎(chǔ),離散信源,聯(lián)合自信息,簡記為,信息論與編碼基礎(chǔ),離散信源,條件自信息

13、,簡記為,在事件y=b給定條件下，在x=a發(fā)生前的不確定性；,在事件y=b給定條件下，在事件x=a發(fā)生后所得到的信息量,信息論與編碼基礎(chǔ),離散信源,例2.1,I(xy) = log64 = 6 bit,I(x|y) = log8 = 3 bit,信息論與編碼基礎(chǔ),離散信源,2、信源的信息熵,信息單位/信源符號,信源熵,自信息是一個隨機變量：自信息是指某一信源發(fā)出某一消息所含有的信息量。所發(fā)出的消息不同，它們所含有的信息量也就不同。 信源熵：自信息的數(shù)學期望。也稱為信源的信息熵/信源熵/香農(nóng)熵/無條件熵/熵函數(shù)/熵。 信息熵的單位：取決于對數(shù)選取的底。一般選用以2為底，其單位為比特/符號。 信息

14、熵的意義：信源的信息熵H是從整個信源的統(tǒng)計特性來考慮的。它是從平均意義上來表征信源的總體特性的。對于某特定的信源，其信息熵只有一個。不同的信源因統(tǒng)計特性不同，其熵也不同。,信息論與編碼基礎(chǔ),離散信源,例1,有一布袋內(nèi)放100個球，其中80個球是黃色的，20個球是白色的。隨便摸出一個球，猜測是什么顏色，其概率空間為 x1：表示摸出的是黃球 x2：表示摸出的是白球,信息論與編碼基礎(chǔ),離散信源,信息論與編碼基礎(chǔ),離散信源,例2,三個信源,1 bit事件,信息論與編碼基礎(chǔ),離散信源,信源熵的三種物理含義,信源熵是從平均意義上來表征信源的總體特性的一個量。因此信源熵有以下三種物理含義。 信源熵H(X)是

15、表示信源輸出后每個消息/符號所提供的平均信息量； 信源熵H(X)是表示信源輸出前，信源的平均不確定性； 用信源熵H(X)來表征變量X的隨機性。 如下例，變量Y取y1和y2是等概率的，所以其隨機性大。而變量X取x1的概率比取x2的概率大很多，這時變量X的隨機性就小。因此H(X)反映了變量的隨機性。,信息論與編碼基礎(chǔ),離散信源,信源熵與平均自信息量,信源熵和平均自信息量兩者在數(shù)值上是相等的，但含意并不相同。 信源熵H(X)表征信源的平均不確定度，平均自信息量是消除不確定度所需要的信息的量度； 信源一定，不管它是否輸出離散消息，只要這些離散消息具有一定的概率特性，必有信源的熵值；在離散信源的情況下，

16、信源熵的值是有限的； 信息量只有當信源輸出離散消息并被接收后，才有意義。這就是給予接收者的信息度量。當信源輸出連續(xù)消息時，信息量的值可以是無窮大。,信息論與編碼基礎(chǔ),離散信源,信源熵與平均獲得的信息量,信源熵是信源的平均不確定性的描述。在一般情況下它并不等于平均獲得的信息量。只有在無噪情況下，接收者才能正確無誤地接收到信源所發(fā)出的消息，消除了H(X)大小的平均不確定性，所以獲得的平均信息量就等于H(X)。在一般情況下獲得的信息量是兩熵之差，并不是信源熵本身。,信息論與編碼基礎(chǔ),離散信源,舉 例,有兩個信源，其概率空間分別為 信息熵分別為 H(X)=-0.99log0.99-0.01log0.0

17、1=0.08 比特/符號 H(Y)=-0.5log0.5-0.5log0.5=1 比特/符號 可見 H(Y)H(X) 本例結(jié)論 信源Y的二個輸出消息是等可能性的，所以在信源沒有輸出消息以前，事先猜測哪一個消息出現(xiàn)的不確定性要大； 信源Y比信源X的平均不確定性大； 信源X的二個輸出消息不是等概率的，事先猜測x1和x2哪一個出現(xiàn)，雖然具有不確定性，但大致可以猜出x1會出現(xiàn)，因為x1出現(xiàn)的概率大。所以信源X的不確定性要?。?信息熵反映的就是信源輸出前平均不確定程度的大小。,信息論與編碼基礎(chǔ),離散信源,信息論與編碼基礎(chǔ),離散信源,一、信源的數(shù)學模型及分類,二、離散信源的信息熵及其性質(zhì),三、離散無記憶的

18、擴展信源,四、離散平穩(wěn)信源,五、信源的剩余度,信息論與編碼基礎(chǔ),離散信源,1、自信息,2、信源的信息熵,3、熵的基本性質(zhì),信息論與編碼基礎(chǔ),離散信源,3、熵的基本性質(zhì),概率矢量,熵函數(shù),H(0.3, 0.4, 0.3),H(0.3),信息論與編碼基礎(chǔ),離散信源,1)非負性,3、熵的基本性質(zhì),信息論與編碼基礎(chǔ),離散信源,2)確定性,3、熵的基本性質(zhì),信息論與編碼基礎(chǔ),離散信源,例設(shè)X,Y,Z三個信源,3、熵的基本性質(zhì),節(jié)日上空彩球,學術(shù)會議參與者膚色,天氣情況,信息論與編碼基礎(chǔ),離散信源,4)擴展性,3、熵的基本性質(zhì),信息論與編碼基礎(chǔ),離散信源,5)可加性,信源X,Y統(tǒng)計獨立,極值性,信息論與編

19、碼基礎(chǔ),離散信源,6)極值性,最大離散熵定理,最大離散熵定理,最大離散熵定理,最大離散熵定理,最大離散熵定理,信息論與編碼基礎(chǔ),離散信源,例，二元信源（1，0）的信息熵,H(0,1),確定性,H(0.5,0.5),極值性,計算與思考,計算與思考,計算與思考,信源空間必定是一個完備集,信源空間的描述,7) 香農(nóng)輔助定理,對任意兩個消息數(shù)相同的信源 有 上式含義：任一概率分布p(xi)，它對其它概率分布p(yi)的自信息 取數(shù)學期望時，必不小于p(xi)本身的熵。,信息論與編碼基礎(chǔ),離散信源,由熵的極值性可以證明條件熵不大于信源熵/無條件熵： H(X/Y)H(X) H(Y/X)H(Y) 證明：H(X/Y)H(X) 已知Y時X的不確定度應(yīng)小于一無所知時X的不確定度。因為已知Y后，從Y得到了一些關(guān)于X的信息，從而使X的不確定度下降。,信息論與編碼基礎(chǔ),離散信源,8) 上凸性,HP +(1-)Q H(P )+(1-)H(Q ) 上凸性證明： 設(shè)有一