信息論基礎(chǔ)復(fù)習(xí)提綱

1、WOR格式哈爾濱醫(yī)科大學(xué)生物信息科學(xué)與技術(shù)學(xué)院第一章 緒論1、什么是信息？香農(nóng)對于信息是如何定義的。答：信息是事物運(yùn)動狀態(tài)或存在方式的不確定性的描述（Information isameasureofone'sfreedomofchoicewhenoneselectsamessage）。2、簡述通信系統(tǒng)模型的組成及各部分的含義。答：（ 1）、信源：信源是產(chǎn)生消息謬屆"編訊器；fe道的源。信源產(chǎn)生信息的速率-熵率。十?dāng)_（2）、編碼器： 編碼器是將消、信道編碼器（提高傳輸可靠性）息變成適合于信道傳送的信號的設(shè) 備。包括信源編碼器（提高傳輸效率） 調(diào)制器。3）、信道：信道是信息傳輸和

2、存儲的媒介。4）、譯碼器：譯碼是編碼的逆變換，分為信道譯碼和信源譯碼。5）、信宿：信宿是消息的接收者（人或機(jī)器）。3、簡述香農(nóng)信息論的核心及其特點(diǎn)。答：（1）、香農(nóng)信息論的核心: 輸，并在通信系統(tǒng)中采用適當(dāng)?shù)木幋a后能夠?qū)崿F(xiàn)高效率和高可靠性的信息傳得出了信源編碼定理和信道編碼定理。（2）、特點(diǎn)：、以概率論、隨機(jī)過程為基本研究工具。 、研究的是通信系統(tǒng)的整個過程，而不是單個環(huán)節(jié)，并以編、譯碼器為重點(diǎn)。 、關(guān)心的是最優(yōu)系統(tǒng)的性能和怎樣達(dá)到這個性能（并不具體設(shè)計系統(tǒng)） 、要求信源為隨機(jī)過程，不研究信宿。第二章信息的度量2.1自信息和互信息（1）、定義：一個事件（消息）本身所包含的信 息量，它Ixilo

3、gp xilog是由事件的不確定性決定的。某個消息xi出現(xiàn)的不確定性的大小定義為自信息，用這個消息出現(xiàn)的概率的對數(shù)的負(fù)值來表示:pxi信息論基礎(chǔ)第-1- 頁共11頁專業(yè)資料整理(2)、性質(zhì)：、(Ipx1 px2 時1x1 )儀2彳概率越小，事件發(fā)生的不確定性越大，事件發(fā)生以后所包含的自信息量越大。pxi )=1 時Txi(戶 0。二 pxi ( I 辺 0 時 Ixi；當(dāng)、兩個相對獨(dú)立的不同的消息所提供的信息量應(yīng)等于它們分別提供的信息量之和，即自信息論滿足可加性。(戶卩心2 )()()=pX1 pxiix 1X2Ix )Ix 2。(3)、例 2.1 : 、英文字母計算他們的自信息量。 、假定前

4、后字母出現(xiàn)是互相獨(dú)立的，計算a”出現(xiàn)的概率為0.064，c”出現(xiàn)的概率為0.022，分別ac ”的自信息。、假定前后字母出現(xiàn)不是互相獨(dú)立的，當(dāng) 算“ a”出現(xiàn)以后，“c ”出現(xiàn)的自信息量。a”出現(xiàn)以后，“出現(xiàn)的概率為0.04，計2、互信息：(ij )=( i )-(i件個事yJ所給出關(guān)于另一個 事件J尸Ix;yIx Ix|ylogpxi的信息定義為互信息， 用I()(' J 丿 * JiIy Iy|x1、定義：隨機(jī)變量 X的每一個可能取值的自信息Ixi()xi;yJ J 表示:丿py( |x)iIi(pxy () i I的統(tǒng)計平均值定義為隨機(jī)變量 X的平均自信息量。2、熵函數(shù)的性質(zhì):&

5、quot;對稱性:1)、(2)、確定性：(3)、非負(fù)性：4)、"擴(kuò)展性：(5)、連續(xù)性：(6)、遞推性：H1, p2，pq)H( P2/)H(1,0)H(1,0 , 0) _H(P)H(P 1,P喲P q)0limH (p,p,< pPq1,Pq0. q1 >12 limH(p 1,p0H(p1,p2,H(p 1, P2,2,-£ £-W H(您厲二 0)=0pn1,q1,q2 iqm)pn) pH(1,1,極值性:、fx 1(1)x 2nnf(xlogpyJH(X)i1logpxi pyJEI(x i)p(Xi)log 2p(Xi)H(Pq, P1,

6、 Pq1)! +p)2 q(P1，P2,Pq)H(p1,p2,1)(11)p前q2,一 PnPnlog 2 n)f(x 2)mpn(8)、上凸性：3、聯(lián)合熵：聯(lián)合自信 息的H(XY)mP (Xiyj)I(xJ-uln mp(Xiyj)log 2p(Xiyj)數(shù)學(xué)期望。它是二維隨機(jī)變量XY的不確定性的度 量。i1 j1i1 j1由于不同的4、條件熵：就得出給定是變化的，對H(Y/x i)XX時，丫的條件熵H(Y/X)P(Xiyjlog 2 i j信息論基礎(chǔ)的所有可能值進(jìn)行統(tǒng)計平均，p(yj/Xi)H(X/Y)第-2-頁共11頁p(Xiyj)log 2p(Xi/yj) i I5、各類熵之間的關(guān) 系

7、：（1）、聯(lián)合熵與信息熵、條件熵之間 的關(guān)系H(XY) H(X)+H(Y/X) o推廣：H ' X1X2 XN)一 hX1 )hX 2/X 1 嚴(yán)"HxN/X1X2XN1?)當(dāng)二維隨機(jī)X,Y相互獨(dú)立時，聯(lián)合熵變量（2）、條件熵與信息熵的關(guān) 系：等于X,Y各自熵之和。H(XY) H(X)<H(X/Y)H(X); H(Y/X)H(Y)H(Y)。（3）、聯(lián)合熵與信息熵的關(guān)系:<H(XY)H(X)+ H（Y）當(dāng)X、Y相互獨(dú)立時等號成、亠立 o推廣到N個隨機(jī)變量：HX1X2( 戶(戶豐(HX1 HX2HXN的聯(lián)合概率（）表2.1X,丫分布PXY()X0 11/pxi0()4

8、1/41/1/216、例2.5 :隨機(jī)變量X，丫的聯(lián)合概率分 布如表2 O3/41/4（ ）表2 2條件概率分布_PYIX丫 X0 10222.1所示，求聯(lián)合熵（HXY和條件熵HY|Xpyj2.3平均互信息輕義:）從整體上表示從一第機(jī) 在XY的聯(lián)合空間中的統(tǒng)計平均值為 隨機(jī)變量厶 亙）所給出關(guān)于另一個隨 _X的 二 二 變量（信丿X和丫間的平均互信（息。n - mnmIX;丫 px;yij Ix;y ipx；y j logi1i1j1pxi|yjipxi1px;yij1log 1ipxP xiyjlogX|Yi1j1條件熵 信息是收 到pxiX|Y表示給定隨機(jī)變量|yj量后'對隨機(jī)變X

9、仍然存在的不確定度。丫前后關(guān)于X的不確定度減少的量，也就是從所 丫關(guān)于X的平均 互Y獲得的關(guān)于X的平均信息量。2、平均互信息的性質(zhì):(1)、非負(fù)性：IX;丫0信息論基礎(chǔ)第-3- 頁共11頁；當(dāng)X,Y統(tǒng)計獨(dú)立時，QX;丫 )= 0。(請補(bǔ)充完善右圖)(4(5)、極值性：(IX;丫H (X,IX；YHY )<();)、凸函數(shù)性:、當(dāng)條件概率分布給定時，平均互py|x 信息IX；丫是輸入分布Px(的上凸函數(shù)。 I i、對于固定的輸入 分布()(X；丫是條件概率分pyj|xi的下凸函數(shù)。pxi，平均互信息量I 布3、例2.15 :給定X,Y的聯(lián)合概率分布，如表所示。、H(X),H(Y) ； (2

10、)、H(X|Y),H(Y|X)； (3)、(4)、H(Y)-H(Y|X)、l(X;Y)H(X工 11*0r1.1i1/3求:第三章信源及信源熵3.1信源的分類(弄清楚以下信源分類的標(biāo)準(zhǔn))離散無記憶信源離散平穩(wěn)信源，記憶長度無限二離散有記憶信源隨機(jī)過程：波形信源記憶長度有限( )馬爾科夫信源連續(xù)平穩(wěn)信源上非平穩(wěn)信 源3.3離散多符號信源1、離散平穩(wěn)信源的特征：統(tǒng)計特性不隨時間推移而變化。2、熵率：隨機(jī)變量序列 求平均：N個隨機(jī)變量的聯(lián)合熵(HX)F(1HXX2N)xN稱為平均符號熵。如果當(dāng) N時上式極限存在，則lim HN*NX稱為熵率，或稱為極限熵，記為(2)、互易性(對稱性)：Ij=X(丫

11、lYjX ；(3)、平均互信息與各類熵之間的關(guān)系:PY )- HXY )IX；Y ) = HX )-HX/Y戶 hy )-hy(x)=hx )HlimHNX。N3、離散平穩(wěn)信源的幾點(diǎn)結(jié)論 (小題)信息論基礎(chǔ)第-4-頁共11頁(1)、條件熵Hxn IX1X2XN1隨'N的增i加是遞減的(即已知條件越多，不確定性越少)(2)、N給定時平均符號熵大于等于條件熵NXH即X1X2()> (Xn1；)(3)、平均符號熵Hn(X隨N的增加是遞減的;(4)、如果HxH 筈limNXN=limH nX (Xn|X 1X2)存在，并且號有關(guān)爾科夫信源(2Hli產(chǎn)N信源在某一時刻發(fā)出某一符號的概率除與

12、該符XN1；的m個符號有關(guān)，1階馬爾可夫 信源只與前面一個符號有關(guān)。xl符號有xl加2!90x2IJB3/4I庖02/119/11只與此前發(fā)出的有限個關(guān)。M階馬爾可夫信源只與前面發(fā)出5、例題3.3 :信源X的信源模型為x1x211P(X)36輸出符號序列中；只有前后兩個符號有記憶，條件概率P X2|X1給出，求熵率，并比較HX|X1、11HX2和HX的大小。第五章無失真信源編碼5.1信源編碼的相關(guān)概念1、各種碼的分類：(1)、分組碼和非分 組碼：、分組碼：將信源符號集中的每個信 源符號彳非分組碼奇異碼si固定地射 成一個碼字wi。(一個信源符號T一個碼字)、非分組石廠又稱樹碼，編碼器輸出的碼符

13、號通常與 編碼碼'分組碼非奇異 碼U非唯一可譯碼及時碼唯一可譯碼非及時碼器的所有信源符號都有 關(guān)。(2) 、奇異碼與非奇異碼：定義若一種分組碼中的所有碼字都不相同異碼。非奇異碼是分組碼能夠正確譯碼的必要條件，而不是充分條件。(3) 、唯一可譯碼與非唯一可譯碼：，則稱此分組碼為非奇異碼，否則稱為奇唯一可譯碼。N,其N次擴(kuò)展碼均為非定義任意有限長的碼元序列，如果只能唯一地分割成一個個碼字，便稱為 條件：、此碼本身是非奇異的；、對于任意有限的整數(shù)奇異的。唯一可譯碼首 先是非奇異碼，且任意有限長的碼字序列不會雷同信息論基礎(chǔ)第-5- 頁共11頁（4）、即時碼與非即時碼:定義無需考慮后續(xù)的碼符號就

14、可以從碼符號序列中譯出碼字，這樣的唯一可譯碼稱為即 時碼。條件：、此碼是唯一可譯碼；、不需要通過接收到后面的碼字才能譯出前面 的碼字，在收到一個完整的碼字后即可以及時譯出。一個唯一可譯碼成為即時碼的充要 條件是其中任何一個碼字都不是其他碼字的前綴。5.3、變長碼及變長信源編碼定理1、Kraft不等式McMillan不等 式：（1 ）、Kraft不等式：設(shè)信源符 號集為S=s1,s2, ?sq，碼符號集為X=x1,x2,?xr,對信源進(jìn)行編 碼，得到的碼為C=w1,w2, ?wq，碼長分別為l1，l2 ?lq.即時碼存在的充要條件 是zqr l i 1這稱為Kraft不等式（其r的葉子節(jié)點(diǎn) 處。

15、是被編碼的符號個數(shù)；q是信源個數(shù); 于二叉樹i1li是碼的長度）。這也就意味著即時碼存在(2)、McMillan不等式：判斷唯一可譯碼的條件與即時碼條件一致， 都是1, r li時 1條件并不比即碼判斷條件寬松。2、唯一可譯碼的判別準(zhǔn)則： 定理一個碼是唯一可譯碼的充要條件是 碼字。設(shè)C為碼字集合，我們要構(gòu)造尾隨后綴的 集合F1,F2, ?的并集中沒有C中的F1，F(xiàn)2，?和 F。（1 ）、F1是C中所有碼字尾隨后綴的集 合：若后綴A列為F1中的元素，所有這樣的尾隨后綴 構(gòu)成了F1 ；（2）、考查小和Fi兩個集合，若 C中任意碼字是Fi中 中任意元素是C中的碼字w是碼字w的前綴，即w=wA則將尾隨

16、元素的前綴，或者 FiC中碼字的前綴，則將其相應(yīng)的尾隨后綴放入集合Fi1 ；（3） 、FFi （即F為碼C的尾隨后綴集合）；i（4）、若F中出現(xiàn)了 C中的元素，則算法終 止，判斷 素在F中已經(jīng)全部存在了，則算法終止， 判斷 總而言之，判斷一個碼是唯一可譯碼的充 要條件是3、例5.4 :設(shè)消息集合共有7個元素 s1,s2,s3,s4,s5,s6,s7,C不是唯一可譯碼；若 出現(xiàn)C是唯一可譯碼。Fi1為空集或Fi1中的元F中不含有C中的碼字。他們分別被編碼為a，c，ad，abb， bad，deb， bbcde，判斷是否為唯一可譯碼。5.4（） （ （）變長碼的編碼方法1、香農(nóng)編碼的方法:(1)、信

17、源的q個消息概率從大到小排序，psiPS2 psq；信息論基礎(chǔ)第-6- 頁共11頁i1.計算各個信源符號的累加概率pSki1,2,qkllog （） -i1,2,q 計算第i個消息的碼長l ipSi.將累加概率（變換成Si Fsi.按公式li進(jìn)制小數(shù)得到其碼字。將累加概率（）小換點(diǎn)二進(jìn)制小數(shù)，取7個信源符號的信源進(jìn)行編碼。4時，先求第四個信后li位數(shù)作為第i個信源符號的碼字。元霍夫曼編碼的方法:2、列5.6 :參照下表按以上步驟對一個有 例如當(dāng)（1）、信源的q個消息概率從大到小排序psips2PSq。（2）、0，1碼分別代表概率最小的兩個信源符 合并成一個，從而得到只包括q-1個符號的新信源。

18、（）、將新信源仍按概率從大到小排序，再將最后兩個概率最小的信源符 3號分別用 并成一個新符號，這樣形 成了q-2個符號的新信源。（）、依次繼續(xù)下去，直至信源最后只剩下兩個信源符號為止。將這最后 4兩個信源符號用號,并將這兩個概率最小的信源符號0和1碼符號表 示，合號,0和1表示。到各信源符號所對應(yīng)的碼符號序列，即相應(yīng)的碼字。4、例5.7 :以例5.6為例編制兀霍夫曼碼。碼字信源符號_、霍夫曼編碼 '斜 Q碼過程環(huán)廠1碼長(5)、從最后一級縮減信源開始，進(jìn)行回溯，將每次標(biāo)注的碼符號連接起來就得10S10.200.200.26 f9350.390.61 0211s20.190.190.20

19、/0.260.3500.3912000s30.180.180.190.200 0.2613()香農(nóng)編碼-()信源符號si概率psi累加概率FSiilogps i碼長1 i二元碼S10.2002.343000S20.190.202.413001S30.180.392.483011S40.170.572.563100S50.150.742.743101S60.100.893.3441110S70.010.996.6671111110果符號的二元碼碼長3,因此碼長取3.3、()> (上> ()logps 414：14信息論基礎(chǔ)第-7- 頁共11頁WOR格 式5、費(fèi)諾編碼的過程:( 1(2

20、(3（）>（）士>（）、信源的q個消息概率從大到小排序。即ps1 ps2Psq。）、將依次排列的信源符號以概率分為兩組，使兩組的概率和基本相 等。并賦予符號）、再分組，使劃分后的兩組的概率和基本相等，并 賦予符號4）、重復(fù)，直至每組只剩下一個信源符號為止。5）、信源符號對應(yīng)的碼符號序列即為費(fèi)諾碼。psips20和1。0和1。6、例5.9 :信源與 5.6和例5.7相同，請編制費(fèi)諾 例碼。第1次分組費(fèi)諾碼/Z Z tt馬信源符號概率第2次分組第3次分組第4次分組:一兒碼碼長S10.200002S20.19010010 '3S30.1801013s40.17102S50.151

21、01103S640S70.01111114(哈爾濱醫(yī)科大學(xué)生物信息科學(xué)與技術(shù)學(xué)院001s40.170.170.180 0.19 13010s50.150.15 0 0.17 130110s60.10 £0<11 140111s70.01 1專業(yè)資料整理7、總結(jié)：霍夫曼碼是即時碼，他的兩個特點(diǎn):（1）保證了概率大的信源符號對應(yīng)的碼長小，概率小的信源符號對應(yīng)的碼長大，充分利用了短碼;最長兩個碼字有相同的碼長，最后一位碼符號不同（碼長相差的?。? ）每次縮減信源的編碼最短，傳輸效率最高。&習(xí)題5.8 :下面是4種不同的編碼:；01,111,011,00,010,110不等式

22、？000,10,00,11 ； 100,101,0,11 01,100,011,00,111,1010,1011,1101請計算：（1）、此碼的碼長分布是否滿足Kraft-McMillan(2)、(3)、此碼是否為即時碼？如果不是，請說明。此碼是否為唯一可譯碼？如果不是，請說明（可以畫出樹圖說明）。5.5實(shí)用的無失真編碼方法各種編碼的應(yīng)用（小題）：BMP TIFAVI;1）、游程編碼（REL,REC應(yīng)用于:2）、LZW碼應(yīng)用于：GIFZ IP ARC;3）、算術(shù)編碼應(yīng)用于：JPEG200Q參考答案WOR格式哈爾濱醫(yī)科大學(xué)生物信息科學(xué)與技術(shù)學(xué)院信息論基礎(chǔ)第-8- 頁共11頁專業(yè)資料整理log 2

23、0.064_ 3.96bitI(a)例2.1 :、I(c)亠"log 20.022亠 5.51bit、由于前后字母出現(xiàn)是互相獨(dú)立 的，“l(fā)(ac) log 2(0.064*0.022)即兩個相對獨(dú)立的事件的自信息量滿足可加性， 信息量應(yīng)等于他們分別提供的信息量之和。ac”出現(xiàn)的概率為0.064*0.022(log 20.064log420.022)也就是由兩個相對獨(dú)立的事件的積事件所提供的,所以l(a)+l(c)=9.47bit1(" )log 20.044.64bit例 2.5 :、 變小?！?a”出現(xiàn)的條件下，出現(xiàn)的頻率變大，它的不確定性十一HXY 1log4由聯(lián)合概率分 布得11log11/441/4 2X的邊緣概率分布：1logPX表2.2所示)，得至到HY|X2log44 1log22 二2-401,P X12)=2 112和條件概率分 12)= 0 1,HY|X> =禾n0 和 HY|X比特/聯(lián)合符號2( ipyj|xi (如10。2H1例2.15 :由的聯(lián)合概率分布求 X,Y的邊緣概率分布如下冬表，X,Y出所?。篤r»1)n1尸1 1亠'廠1I1丄丄1hJV111 1 )3 X)5) 1 S Ht r )1注意到HYO40.81131 HY|X2Xi 門二 TH( X