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

1、第一章 緒論1、什么是信息？香農(nóng)對(duì)于信息是如何定義的。答：信息是事物運(yùn)動(dòng)狀態(tài)或存在方式的不確定性的描述(Information is a measure of ones freedom of choice when one selects a message)。2、簡述通信系統(tǒng)模型的組成及各部分的含義。答：（1）、信源：信源是產(chǎn)生消息的源。信源產(chǎn)生信息的速率-熵率。（2）、編碼器：編碼器是將消息變成適合于信道傳送的信號(hào)的設(shè)備。包括信源編碼器（提高傳輸效率）、信道編碼器（提高傳輸可靠性）、調(diào)制器。（3）、信道：信道是信息傳輸和存儲(chǔ)的媒介。（4）、譯碼器：譯碼是編碼的逆變換，分為信道譯碼和信源譯碼

2、。（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)的整個(gè)過程，而不是單個(gè)環(huán)節(jié)，并以編、譯碼器為重點(diǎn)。、關(guān)心的是最優(yōu)系統(tǒng)的性能和怎樣達(dá)到這個(gè)性能（并不具體設(shè)計(jì)系統(tǒng)）。、要求信源為隨機(jī)過程，不研究信宿。第二章 信息的度量2.1 自信息和互信息1、自信息（量）：（1）、定義：一個(gè)事件（消息）本身所包含的信息量，它是由事件的不確定性決定的。某個(gè)消息出現(xiàn)的不確定性的大小定義為自

3、信息，用這個(gè)消息出現(xiàn)的概率的對(duì)數(shù)的負(fù)值來表示：（2）、性質(zhì)：、是的嚴(yán)格遞減函數(shù)。當(dāng)時(shí)概率越小，事件發(fā)生的不確定性越大，事件發(fā)生以后所包含的自信息量越大。、極限情況下，當(dāng)時(shí)；當(dāng)時(shí)，。 、兩個(gè)相對(duì)獨(dú)立的不同的消息所提供的信息量應(yīng)等于它們分別提供的信息量之和，即自信息論滿足可加性。（3）、例2.1：、英文字母中“a”出現(xiàn)的概率為0.064，“c”出現(xiàn)的概率為0.022，分別計(jì)算他們的自信息量。、假定前后字母出現(xiàn)是互相獨(dú)立的，計(jì)算“ac”的自信息。、假定前后字母出現(xiàn)不是互相獨(dú)立的，當(dāng)“a”出現(xiàn)以后， “c”出現(xiàn)的概率為0.04，計(jì)算“a”出現(xiàn)以后， “c”出現(xiàn)的自信息量。2、互信息：一個(gè)事件所給出關(guān)于

4、另一個(gè)事件的信息定義為互信息，用表示：2.2 平均自信息1、定義：隨機(jī)變量X的每一個(gè)可能取值的自信息的統(tǒng)計(jì)平均值定義為隨機(jī)變量X的平均自信息量。2、熵函數(shù)的性質(zhì)：（1）、對(duì)稱性：（2）、確定性：（3）、非負(fù)性：（4）、擴(kuò)展性：（5）、連續(xù)性：（6）、遞推性：（7）、極值性：（8）、上凸性：3、聯(lián)合熵：聯(lián)合自信息的數(shù)學(xué)期望。它是二維隨機(jī)變量XY的不確定性的度量。4、條件熵： 5、各類熵之間的關(guān)系： （1）、聯(lián)合熵與信息熵、條件熵之間的關(guān)系：。 推廣：;當(dāng)二維隨機(jī)變量X,Y相互獨(dú)立時(shí)，聯(lián)合熵等于X,Y各自熵之和。 （2）、條件熵與信息熵的關(guān)系：; 。 （3）、聯(lián)合熵與信息熵的關(guān)系：當(dāng)X、Y相互獨(dú)立

5、時(shí)等號(hào)成立。推廣到N個(gè)隨機(jī)變量：。6、例2.5：隨機(jī)變量X，Y的聯(lián)合概率分布如表2.1所示，求聯(lián)合熵和條件熵。表2.1 X,Y的聯(lián)合概率分布YX0 1011/4 1/41/2 0 1/2 1/23/4 1/4 1表2.2 條件概率分布 YX0 1011/2 1/21 02.3 平均互信息1、定義：從整體上表示從一個(gè)隨機(jī)變量Y所給出關(guān)于另一個(gè)隨機(jī)變量X的信息量，定義互信息在XY的聯(lián)合空間中的統(tǒng)計(jì)平均值為隨機(jī)變量X和Y間的平均互信息。條件熵表示給定隨機(jī)變量Y后，對(duì)隨機(jī)變量X仍然存在的不確定度。所以Y關(guān)于X的平均互信息是收到Y(jié)前后關(guān)于X的不確定度減少的量，也就是從Y獲得的關(guān)于X的平均信息量。2、平均

6、互信息的性質(zhì)：（1）、非負(fù)性：；（2）、互易性（對(duì)稱性）：；（3）、平均互信息與各類熵之間的關(guān)系：；當(dāng)X,Y統(tǒng)計(jì)獨(dú)立時(shí)，。（請(qǐng)補(bǔ)充完善右圖）（4）、極值性：；（5）、凸函數(shù)性：、當(dāng)條件概率分布給定時(shí)，平均互信息是輸入分布的上凸函數(shù)。、對(duì)于固定的輸入分布，平均互信息量是條件概率分布的下凸函數(shù)。3、例2.15：給定X,Y的聯(lián)合概率分布，如表所示。求：(1)、H(X),H(Y)； (2)、H(X|Y),H(Y|X)； (3)、H(XY)；(4)、H(Y)-H(Y|X)；(5)、I(X;Y)；第三章 信源及信源熵3.1信源的分類（弄清楚以下信源分類的標(biāo)準(zhǔn)） 3.3 離散多符號(hào)信源1、離散平穩(wěn)信源的特征

7、：統(tǒng)計(jì)特性不隨時(shí)間推移而變化。2、熵率：隨機(jī)變量序列中，對(duì)前N個(gè)隨機(jī)變量的聯(lián)合熵求平均：稱為平均符號(hào)熵。如果當(dāng)時(shí)上式極限存在，則稱為熵率，或稱為極限熵，記為。3、離散平穩(wěn)信源的幾點(diǎn)結(jié)論（小題）：（1）、條件熵隨N的增加是遞減的（即已知條件越多，不確定性越少）；（2）、N給定時(shí)平均符號(hào)熵大于等于條件熵，即；（3）、平均符號(hào)熵隨N的增加是遞減的；（4）、如果，則存在，并且；4、馬爾科夫信源：信源在某一時(shí)刻發(fā)出某一符號(hào)的概率除與該符號(hào)有關(guān)外，只與此前發(fā)出的有限個(gè)符號(hào)有關(guān)。M階馬爾可夫信源只與前面發(fā)出的m個(gè)符號(hào)有關(guān)，1階馬爾可夫信源只與前面一個(gè)符號(hào)有關(guān)。5、例題3.3：信源X的信源模型為輸出符號(hào)序列中

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

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

10、對(duì)信源進(jìn)行編碼，得到的碼為C= w1,w2,wq,碼長分別為l1，l2，lq.即時(shí)碼存在的充要條件是這稱為Kraft不等式（其中r是被編碼的符號(hào)個(gè)數(shù)；q是信源個(gè)數(shù)；li是碼的長度）。這也就意味著即時(shí)碼存在于二叉樹的葉子節(jié)點(diǎn)處。（2）、McMillan不等式：判斷唯一可譯碼的條件與即時(shí)碼條件一致，都是，條件并不比即時(shí)碼判斷條件寬松。2、唯一可譯碼的判別準(zhǔn)則：定理 一個(gè)碼是唯一可譯碼的充要條件是F1,F2,的并集中沒有C中的碼字。設(shè)C為碼字集合，我們要構(gòu)造尾隨后綴的集合F1，F(xiàn)2，和F。（1）、F1是C中所有碼字尾隨后綴的集合：若C中的碼字是碼字的前綴，即=，則將尾隨后綴A列為F1中的元素，所有這

11、樣的尾隨后綴構(gòu)成了F1；（2）、考查C和Fi兩個(gè)集合，若C中任意碼字是Fi中元素的前綴，或者Fi中任意元素是C中碼字的前綴，則將其相應(yīng)的尾隨后綴放入集合；（3）、（即F為碼C的尾隨后綴集合）；（4）、若F中出現(xiàn)了C中的元素，則算法終止，判斷C不是唯一可譯碼；若出現(xiàn)為空集或中的元素在F中已經(jīng)全部存在了，則算法終止，判斷C是唯一可譯碼?？偠灾?，判斷一個(gè)碼是唯一可譯碼的充要條件是F中不含有C中的碼字。3、例5.4：設(shè)消息集合共有7個(gè)元素s1,s2,s3,s4,s5,s6,s7,他們分別被編碼為a，c，ad，abb，bad，deb，bbcde，判斷是否為唯一可譯碼。5.4 變長碼的編碼方法1、香農(nóng)編

12、碼的方法：（1）、信源的q個(gè)消息概率從大到小排序，；（2）.計(jì)算各個(gè)信源符號(hào)的累加概率 ；（3）.按公式計(jì)算第個(gè)消息的碼長；（4）.將累加概率變換成二進(jìn)制小數(shù)得到其碼字。將累加概率變換成二進(jìn)制小數(shù)，取小數(shù)點(diǎn)后位數(shù)作為第個(gè)信源符號(hào)的碼字。2、列5.6：參照下表按以上步驟對(duì)一個(gè)有7個(gè)信源符號(hào)的信源進(jìn)行編碼。例如當(dāng)時(shí)，先求第四個(gè)信源符號(hào)的二元碼碼長：，因此碼長取3.香農(nóng)編碼信源符號(hào)概率累加概率碼長 二元碼S1S2S3S4S5S6S70.200.190.180.170.150.100.0100.200.390.570.740.890.992.342.412.482.562.743.346.663333

13、34700000101110010111103、二元霍夫曼編碼的方法：（1）、信源的q個(gè)消息概率從大到小排序。（2）、0，1碼分別代表概率最小的兩個(gè)信源符號(hào)，并將這兩個(gè)概率最小的信源符號(hào)合并成一個(gè)，從而得到只包括q-1個(gè)符號(hào)的新信源。（3）、將新信源仍按概率從大到小排序，再將最后兩個(gè)概率最小的信源符號(hào)分別用0和1碼符號(hào)表示，合并成一個(gè)新符號(hào)，這樣形成了q-2個(gè)符號(hào)的新信源。（4）、依次繼續(xù)下去，直至信源最后只剩下兩個(gè)信源符號(hào)為止。將這最后兩個(gè)信源符號(hào)用0和1表示。（5）、從最后一級(jí)縮減信源開始，進(jìn)行回溯，將每次標(biāo)注的碼符號(hào)連接起來就得到各信源符號(hào)所對(duì)應(yīng)的碼符號(hào)序列，即相應(yīng)的碼字。4、例5.7：

14、以例5.6為例編制二元霍夫曼碼?；舴蚵幋a碼字信源符號(hào)編碼過程碼長101100000101001100111S1s2s3s4s5s6s70.20 0.20 0.26 0.35 0.39 0.61 00.19 0.19 0.20 0.26 0.35 0 0.39 10.18 0.18 0.19 0.20 0 0.26 10.17 0.17 0.18 0 0.19 10.15 0.15 0 0.17 10.10 0 0.11 10.01 122333445、費(fèi)諾編碼的過程：（1）、信源的q個(gè)消息概率從大到小排序。即。（2）、將依次排列的信源符號(hào)以概率分為兩組，使兩組的概率和基本相等。并賦予符號(hào)0和

15、1。（3）、再分組，使劃分后的兩組的概率和基本相等，并賦予符號(hào)0和1。（4）、重復(fù)，直至每組只剩下一個(gè)信源符號(hào)為止。（5）、信源符號(hào)對(duì)應(yīng)的碼符號(hào)序列即為費(fèi)諾碼。6、例5.9：信源與例5.6和例5.7相同，請(qǐng)編制費(fèi)諾碼。費(fèi)諾碼信源符號(hào)概率第1次分組第2次分組第3次分組第4次分組二元碼碼長S10.2000002S20.19100103S30.1810113S40.1710102S50.15101103S60.101011104S70.011111147、總結(jié)：霍夫曼碼是即時(shí)碼，他的兩個(gè)特點(diǎn)：（1）保證了概率大的信源符號(hào)對(duì)應(yīng)的碼長小，概率小的信源符號(hào)對(duì)應(yīng)的碼長大，充分利用了短碼；（2）每次縮減信源的

16、最長兩個(gè)碼字有相同的碼長，最后一位碼符號(hào)不同。（碼長相差的?。┚幋a最短，傳輸效率最高。8、習(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,110；請(qǐng)計(jì)算：（1）、此碼的碼長分布是否滿足Kraft-McMillan不等式？（2）、此碼是否為即時(shí)碼？如果不是，請(qǐng)說明。（3）、此碼是否為唯一可譯碼？如果不是，請(qǐng)說明（可以畫出樹圖說明）。5.5實(shí)用的無失真編碼方法各種編碼的應(yīng)用（小題）：（1）、游程編碼（REL,REC）應(yīng)用于：BMP TIF AVI；（2）、LZ

17、W碼應(yīng)用于：GIF ZIP ARC；（3）、算術(shù)編碼應(yīng)用于：JPEG2000；參考答案例2.1：、 、由于前后字母出現(xiàn)是互相獨(dú)立的，“ac”出現(xiàn)的概率為0.064*0.022，所以 即兩個(gè)相對(duì)獨(dú)立的事件的自信息量滿足可加性，也就是由兩個(gè)相對(duì)獨(dú)立的事件的積事件所提供的信息量應(yīng)等于他們分別提供的信息量之和。 、“a”出現(xiàn)的條件下，“c”出現(xiàn)的頻率變大，它的不確定性變小。例2.5：由聯(lián)合概率分布得X的邊緣概率分布： 和條件概率分布（如表2.2所示），得到和。注意到。例2.15：由X,Y的聯(lián)合概率分布求出X,Y的邊緣概率分布如下圖表所示：例3.3：（1）、熵率：；（2）、如果不考慮符號(hào)間的相關(guān)性，則信源熵為由此可見，這是由于之間存在統(tǒng)計(jì)依賴關(guān)系，在已知的情況下，的不確定性減少，即條件熵小于無條件熵。因此在考慮序列符號(hào)之間相關(guān)性之后，序列的熵減小。如果信源輸出的符號(hào)序列看成是分組發(fā)出的，每兩