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

1、來源：網(wǎng)絡(luò)轉(zhuǎn)載來源：網(wǎng)絡(luò)轉(zhuǎn)載1、什么是信息？香農(nóng)對于信息是如何定義的。答：信息是事物運動狀態(tài)或存在方式的不確定性的描述（Informationisameasureofonesfreedomofchoicewhenoneselectsamessage）。2、簡述通信系統(tǒng)模型的組成及各部分的含義。答：（1）、信源：信源是產(chǎn)生消息的源。信源產(chǎn)生信息的速率-熵率。（2）、編碼器：編碼器是將消息變成適合于信道傳送的信號的設(shè)備。包括信源編碼器（提高傳輸效率）、信道編碼器（提高傳輸可靠性）、調(diào)制器。（3）、信道：信道是信息傳輸和存儲的媒介。（4）、譯碼器：譯碼是編碼的逆變換，分為信道譯碼和信源譯碼。（5）、

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

3、出現(xiàn)的不確定性的大小定義為自信息，用這個消息出現(xiàn)的概率的對數(shù)的負(fù)值來表示012q擴(kuò)展性:limH1(p,p,p-,)=H連續(xù)性：遞推性：極值性：上凸性(1)、(2)、(7)、8)、2、熵函數(shù)的性質(zhì)：limHq(p:p；pqst012q-1qH(p1，p2,pn-1H(p,p,p)Xf(x1(p,p,p)-)q=H(p,p；p)TOC o 1-5 h zq-1q12q,q,qq)=H(p,p,p)+pH(片,叱,)121m1112nnppppH(,-)=logn“一：)+m-九)f2(X)2123、聯(lián)合熵：聯(lián)合自信息的H(XY)=工Ep(Xy)I(xy)=-YEp(xy)logp(xy)ijij

4、ij2ij數(shù)學(xué)期望。它是二維隨機(jī)i=1j=1i=1j=1變量XY的不確定性的度量。由于不同的x，H(Y/x)是變化的，對H(Y/x)的所有可能值進(jìn)行統(tǒng)計平均，4、條件熵：iii條件熵就得出給定X時，Y的條件熵5、各類熵之間(的關(guān)系=-EEp(xy)logp(y/x)H(X/Y)=-EEp(xy)logp(x/y)ij2jiij2ijijij(1)、聯(lián)合熵與信息熵、條件熵之間的關(guān)系:H(XY)=H(X)+H(Y/X)。推廣.H(X1X2X“)=H(X1)+H(X2/X1)+H(X“/X1X2X)推丿：12N121N12N-1；當(dāng)二維隨機(jī)變量X,Y相互獨立時，聯(lián)合熵等于X,Y各自熵之和。H(XY)

5、=H(X)+H(Y)。、條件熵與信息熵的關(guān)系：H(X/Y)H(X)；H(Y/X)=H(Y)。(3)、聯(lián)合熵與信息熵的關(guān)系：H(XY)H(X)+H(Y)當(dāng)X、Y相互獨立時等號成立。推廣到N個隨機(jī)變量：H&1X2XN)HG1)+HG2)+-+H&N)。6、例2.5:隨機(jī)變量X，Y的聯(lián)合概率分布如表2.1所示，求聯(lián)合熵H&Y)和條件熵H61X)表2.1X,Y的聯(lián)合概率分布P(XY)0101/41/41/211/201/23/41/41信息1Q；巧)在表2.2條件概率分布P&1X)X0101/21/2110體上表示從一個隨機(jī)變量Y所給出關(guān)于另一個隨機(jī)變量X的信息量，定義互2.3平均互信息1、乂：從整X

6、Y的聯(lián)合空間中的統(tǒng)計平均值為隨機(jī)變量X和Y間的平均互信息。I(X;Y)=X區(qū)p(x.;yj)I(x.;y.)=工區(qū)p(x.;yj)log2=丫區(qū)p(x.;y.)logi=1j=1=H(X)-H(XIY)i=1j=1-工區(qū)p(xi;yj)log1i=1j=1i=1j=1條件熵H(X1Y)表示給定隨機(jī)變量Y后，對隨機(jī)變量X仍然存在的不確定度。所以Y關(guān)于X的平均互信息是收到Y(jié)前后關(guān)于X的不確定度減少的量，也就是從Y獲得的關(guān)于X的平均信息量。2、平均互信息的性質(zhì)：(1)、非負(fù)性：1&；Y)、；、互易性(對稱性)：1&；Y)=1SX)；、平均互信息與各類熵之間的關(guān)系：I(X;Y)=H(X)-H(X/Y)

7、=H(Y)-H(Y/X)=H(X+H&)-H(XY)-+4呻-+*;當(dāng)X,Y統(tǒng)計獨立時，1G；Y)=。(請補(bǔ)充完善右圖)、極值性：I&;Y)H(X)I(X;Y)H(XN1X1X2XN_)；（3）、平均符號熵HN在，并且（4）、如果H&丿“，則H=limH18N*NH=limH（X）=limH（XIXXX）8NN12N-14、馬爾科夫信源：信源在某一時刻發(fā)出某一符號的概率除與該符號有關(guān)外，只與此前發(fā)出的有限個符號有關(guān)。M階馬爾可夫信源只與前面發(fā)出的m個符號有關(guān)，1階馬爾可夫信源只與前面一個符號有關(guān)。5、例題3.3:信源X的信源模型為輸出符號序列中，只有前后兩個符號有記憶，條件概率P(XIX21求

8、熵率，并比較H（X21X1）、2H（XiX2）和H（X）的大小第五章無失真信源編碼5.1信源編碼的相關(guān)概念非分組碼1、各種碼的分類：（1）、分組碼和非分組碼：、分組碼:將信源符號集中的每個信源符號si固定地射成碼一個碼字Wi（個信源符號一一個碼字）、非分組碼:又稱樹碼，編碼器輸出的碼符號通常與編碼器的所有信源符號都有關(guān)。（2）、奇異碼與非奇異碼：定義若一種分組碼中的所有碼字都不相同，則稱此分組碼為非奇異碼，否則稱為奇異碼。非奇異碼是分組碼能夠正確譯碼的必要條件，而不是充分條件。（3）、唯一可譯碼與非唯一可譯碼：定義任意有限長的碼元序列，如果只能唯一地分割成一個個碼字，便稱為唯一可譯碼。條件：、

9、此碼本身是非奇異的；、對于任意有限的整數(shù)N,其N次擴(kuò)展碼均為非奇異的。唯一可譯碼首先是非奇異碼，且任意有限長的碼字序列不會雷同。（4）、即時碼與非即時碼：定義無需考慮后續(xù)的碼符號就可以從碼符號序列中譯出碼字，這樣的唯一可譯碼稱為即時碼。條件：、此碼是唯一可譯碼；、不需要通過接收到后面的碼字才能譯出前面的碼字，在收到一個完整的碼字后即可以及時譯出。一個唯一可譯碼成為即時碼的充要條件是其中任何一個碼字都不是其他碼字的前綴。奇異碼非奇異碼丫非唯一可譯碼唯一可譯碼4及時碼非及時碼5.3、變長碼及變長信源編碼定理1、Kraft不等式McMillan不等式：（1）、Kraft不等式：設(shè)信源符號集為S=sl

10、,s2,sq，碼符號集為X=x1,x2,xr,對信源進(jìn)行編碼，得到的碼為C=w1,w2,-wq，碼長分別為11，12,Tq.即時碼存在的充要條件是為rli1這稱為Krafti=1不等式（其中r是被編碼的符號個數(shù)；q是信源個數(shù)；*是碼的長度）。這也就意味著即時碼存在于二叉樹的葉子節(jié)點處。（2）、McMillan不等式：判斷唯一可譯碼的條件與即時碼條件一致，都是工r1，條件并不比即時i=1碼判斷條件寬松。2、唯一可譯碼的判別準(zhǔn)則：定理一個碼是唯一可譯碼的充要條件是F1,F2,的并集中沒有C中的碼字。設(shè)C為碼字集合，我們要構(gòu)造尾隨后綴的集合Fl,F2,和F。（1）、F1是C中所有碼字尾隨后綴的集合：

11、若C中的碼字w.是碼字w的前綴，即w=wA，則將尾jiij隨后綴A列為F1中的元素，所有這樣的尾隨后綴構(gòu)成了F1；（2）、考查C和Fi兩個集合，若C中任意碼字是Fi中元素的前綴，或者Fi中任意元素是C中碼字的前綴則將其相應(yīng)的尾隨后綴放入集合F.$（3）、F=UF（即F為碼C的尾隨后綴集合）；ii（4）、若F中出現(xiàn)了C中的元素，則算法終止，判斷C不是唯一可譯碼；若出現(xiàn)F,為空集或F,中的i+1i+1元素在F中已經(jīng)全部存在了，則算法終止，判斷C是唯一可譯碼?？偠灾?，判斷一個碼是唯一可譯碼的充要條件是F中不含有C中的碼字。3、例5.4:設(shè)消息集合共有7個元素s1,s2,s3,s4,s5,s6,s7

12、,他們分別被編碼為a，c，ad，abb，bad，deb，bbcde，判斷是否為唯一可譯碼。5.4變長碼的編碼方法1、香農(nóng)編碼的方法：、信源的q個消息概率從大到小排序，PPC2工PV；（2）計算各個信源符號的累加概率FCpC）i=1,2,q；ikk=1(3)按公式I.=ilog1ii=1,2,，q計算第i個消息的碼長1；i（4）將累加概率FC.）變換成二進(jìn)制小數(shù)得到其碼字。將累加概率FC.）變換成二進(jìn)制小數(shù)，取小數(shù)點ii后p(s)p12(s)oq3、二元霍夫曼編碼的方法：（2）、0,1碼分別代表概率最小的兩個信源符號，并將這兩個概率最小的信源符號合并成一個，從而得到只包括q-1個符號的新信源。（

13、3）、將新信源仍按概率從大到小排序，再將最后兩個概率最小的信源符號分別用0和1碼符號表示，合并成一個新符號，這樣形成了q-2個符號的新信源。（4）、依次繼續(xù)下去，直至信源最后只剩下兩個信源符號為止。將這最后兩個信源符號用0和1表示。（5）、從最后一級縮減信源開始，進(jìn)行回溯，將每次標(biāo)注的碼符號連接起來就得到各信源符號所對應(yīng)的碼符號序列，即相應(yīng)的碼字。（1）、信源的q個消息概率從大到小排序。即p(s)p(S)p12(s)oq4、例5.7:以例5.6為例編制二元霍夫曼碼?；舴蚵幋a碼字信源符號編碼過程碼長10S10.2007200.260.35090.610/丿j211s20.190.190.200

14、.263500.39/丁丫2000s30.1807180.190.2000/2613001s40.170.170.1800.了3010s50.150TT500.171430110s60.1000TX140111s70.01145、費諾編碼的過程：（2）、將依次排列的信源符號以概率分為兩組，使兩組的概率和基本相等。并賦予符號0和1。（3）、再分組，使劃分后的兩組的概率和基本相等，并賦予符號0和1。4）、重復(fù)，直至每組只剩下一個信源符號為止。5）、信源符號對應(yīng)的碼符號序列即為費諾碼。6、例5.9：信源與例5.6和例5.7相同，請編制費諾碼。費諾碼信源符號概率第1次分組第2次分組第3次分組第4次分組

15、二元碼碼長S10.2000002S20.19100103S30.1810113S40.1710102S50.15101103S60.101011104S70.011111147、總結(jié)：霍夫曼碼是即時碼，他的兩個特點：（1）保證了概率大的信源符號對應(yīng)的碼長小，概率小的信源符號對應(yīng)的碼長大，充分利用了短碼（2）每次縮減信源的最長兩個碼字有相同的碼長，最后一位碼符號不同。（碼長相差的?。┚幋a最短，傳輸效率最高。&習(xí)題5.8:下面是4種不同的編碼:000,10,00,11；100,101,0,11；01,100,011,00,111,1010,1011,1101；01,111,011,00,010,1

16、10；請計算：（1）、此碼的碼長分布是否滿足Kraft-McMillan不等式？（2）、此碼是否為即時碼？如果不是，請說明。（3）、此碼是否為唯一可譯碼？如果不是，請說明（可以畫出樹圖說明）。5.5實用的無失真編碼方法各種編碼的應(yīng)用（小題）：（1）、游程編碼（REL,REC）應(yīng)用于：BMPTIFAVI；（2）、LZW碼應(yīng)用于：GIFZIPARC；（3）、算術(shù)編碼應(yīng)用于：JPEG2000；參考答案I（a）log0.0643.96bit例2.1:、2I（c）log0.0225.51bit、由于前后字母出現(xiàn)是互相獨立的，“ac”出現(xiàn)的概率為0.064*0.022,所以I（ca）=-log20.04=

17、4.64bit即兩個相對獨立的事件的自信息量滿足可加性，也就是由兩個相對獨立的事件的積事件所提供的信息量應(yīng)等于他們分別提供的信息量之和。、“a”出現(xiàn)的條件下，“c”出現(xiàn)的頻率變大，它的不確定性變小。例2.5:H（XY）=log+log+log二log4+log2二x2+x1比特/聯(lián)合符號41/441/421/242422由聯(lián)合概率分布得x的邊緣概率分布：PX02,px12和條件概率分布p（旳丨xi）（如表2.2所示），得到H（YIX0）1,H（YIX1）0和H（YIX）2x1+2x02。注意到H（Y）二OW2二H（Y1x）例2.15:由X,Y的聯(lián)合概率分布求出X,Y的邊緣概率分布如下圖表所示：

18、來源：網(wǎng)絡(luò)轉(zhuǎn)載來源：網(wǎng)絡(luò)轉(zhuǎn)載例3.3：(1)、熵率：H=H2=HC2IX1)=0.870比特/符號；2)、如果不考慮符號間的相關(guān)性，則信源熵為H(X)=-log4+-log9+11log36=1.542比特/符號4943611由此可見，H&21x丿H&)=H&2)，這是由于Xx2之間存在統(tǒng)計依賴關(guān)系，在x1已知的情況下，x2的不確定性減少，即條件熵HG21x)小于無條件熵hG)。因此在考慮序列符號之間相關(guān)性之后，序列的熵減小。如果信源輸出的符號序列看成是分組發(fā)出的，每兩個符號作為一組，這樣可以把符號序列看成是由一個新信源發(fā)出的，新信源每次發(fā)出的是由兩個符號構(gòu)成的消息。新信源的數(shù)學(xué)模型是一個二維的隨機(jī)變量，新信源的熵為HC1X2)=HC1LHC2IX1)=1.542+0.870=2.41