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

1、信息科學(xué)基礎(chǔ)課程總結(jié)（一）學(xué)習(xí)內(nèi)容：第一章隨機(jī)變量的信息度量1學(xué)習(xí)信息論的發(fā)展歷史，了解信息論的產(chǎn)生、發(fā)展與應(yīng)用；信息的定義與特征；2信息的度量問(wèn)題；3香農(nóng)嫡一一隨機(jī)變量的不確定性度量；4信息量的一些基本性質(zhì)；5熟練進(jìn)行有關(guān)嫡的計(jì)算：香農(nóng)嫡、聯(lián)合嫡、微分嫡等（不要忽視條件嫡、互信息、相對(duì)嫡等概念）；6廣義嫡。第二章隨機(jī)過(guò)程的信息度量和漸近等分性1什么是信源？信源的分類；2什么是隨機(jī)過(guò)程？什么是馬爾可夫信源？3隨機(jī)過(guò)程的信息度量問(wèn)題一嫡率；4 了解冗余度和相對(duì)冗余度；5 了解嫡的基本性質(zhì)，互嫡與互信息；6理解信源編碼定理。7了解什么是最大嫡，記住常用的幾種最大嫡分布：有限區(qū)間上的最大嫡、半開(kāi)直線

2、與全直線上的最大嫡。第三章數(shù)據(jù)壓縮和信源編碼1信源編碼的基本問(wèn)題，了解即時(shí)碼的定義；2等長(zhǎng)碼概念及其碼率；Kraft不等式；3變長(zhǎng)碼編碼及平均碼長(zhǎng)的定義；4熟練進(jìn)行哈夫曼碼與算術(shù)碼的編碼及構(gòu)造碼樹(shù)；5了解通用碼概念，會(huì)編LZW碼和YK碼；16會(huì)計(jì)算通用碼的壓縮率（碼率）。第四章數(shù)據(jù)可靠傳輸和信道編碼1了解離散無(wú)記憶信道和信道容量；2會(huì)用定義、極值法和Lagrange乘子法計(jì)算信道容量;3了解信道編碼的作用和常見(jiàn)類型；4理解信道編碼定理的內(nèi)容。信息科學(xué)基礎(chǔ)習(xí)題課一、填空題（20分）：1 .利用數(shù)字結(jié)構(gòu)進(jìn)行信息處理是當(dāng)今社會(huì)信息社會(huì)的一大特色，因此有人稱當(dāng)今的信息社會(huì)又是一個(gè)數(shù)字化的社會(huì),這就是把

3、現(xiàn)實(shí)世界中的各種不同類型的信息與信號(hào)都設(shè)法用數(shù)字來(lái)表達(dá)，并在數(shù)字化的條件下進(jìn)行處理。2 .信息具有可設(shè)計(jì)、傳遞、復(fù)制、存儲(chǔ)、修改與擴(kuò)展等特性，對(duì)這些特性的處理過(guò)程統(tǒng)稱為信息處理信息科學(xué)為研究信息處理提供理論基礎(chǔ)，其中包括它們的數(shù)學(xué)模型、基本的度量關(guān)系與性質(zhì)、相關(guān)的優(yōu)化算法等。3 .時(shí)間與空間實(shí)際上是信息處理中的最基本的資源，在信息處理中除了加快速度與節(jié)省空間之外，尋找它們的最優(yōu)信息處理方案是信息科學(xué)理論中的重要內(nèi)容與基本目標(biāo)。4 .信息論一般是指在信息的加工、傳遞、存儲(chǔ)等處理問(wèn)題中的基礎(chǔ)理論問(wèn)題。5 .1948年香農(nóng)發(fā)表了具有奠基性的論文通信系統(tǒng)的數(shù)學(xué)理論，拉開(kāi)了信息科學(xué)研究的帷幕。信息的度量

4、問(wèn)題包括：信息能否度量？如何度量？信息度量的內(nèi)在含義是什么？信息度量的基本特征（其中包括信息度量與其他學(xué)科的相互關(guān)系等問(wèn)題）與信息度量的各種應(yīng)用問(wèn)題等。6 .一個(gè)量的引進(jìn)，它的出發(fā)點(diǎn)必須基本合理，對(duì)這個(gè)量的度量對(duì)象、意義和內(nèi)容有一個(gè)較為明確而又合理的解釋；一個(gè)量的引進(jìn)是否有意義，最終還要看它能否解決問(wèn)題，解決了什么樣的問(wèn)題，以及它在這些問(wèn)題中的作用與特征；理解一個(gè)量的意義，既要從它原始定義的出發(fā)點(diǎn)來(lái)理解，又要從它最終解決問(wèn)題的意義上來(lái)理解。信息不可能通過(guò)一種量而確定所有的信息度量問(wèn)題。香農(nóng)嫡是信息的一種最基本與重要的度量。7 .一個(gè)通信系統(tǒng)的數(shù)學(xué)模型由信源、信道、翻碼與譯碼組成，它們可用概率論

5、模型給以描述，并由信息量確定它們的特征。8 .由消息變信號(hào)，再由信號(hào)還原成消息的運(yùn)算稱為編碼。編碼的數(shù)學(xué)本質(zhì)是一種X，其核心問(wèn)題是碼元的設(shè)計(jì)與選擇。9 .信息的傳遞過(guò)程可歸結(jié)為：首先由信源發(fā)出消息（原始消息），由編碼將原始消息變?yōu)樾盘?hào)，并進(jìn)入信道成為信道的輸入信號(hào)（簡(jiǎn)稱輸入信號(hào)，或入口信號(hào)，輸入信號(hào)經(jīng)信道的編碼通過(guò)信道,經(jīng)過(guò)信道的傳送，到達(dá)另一端，經(jīng)過(guò)信道譯碼形成輸出信號(hào)或出口信號(hào)，再經(jīng)過(guò)信源譯碼運(yùn)算把輸出信號(hào)變?yōu)橄ⅲ@種消息是原始消息的還原；所以又稱還原消息，還原消息最終由接收者接收。10 .由于干擾的存在，信道的輸出信號(hào)可能與輸入信號(hào)不同；從而形成還原消息與原始消息的不同，這種現(xiàn)象稱為通

6、信誤差，是通信系統(tǒng)中需要克服的。通信誤差的克服一般通過(guò)硬件與軟件兩個(gè)途徑來(lái)解決。軟件的改進(jìn)就是信道編碼方式的改進(jìn)。11 .為實(shí)現(xiàn)有效編碼，在編碼理論中同時(shí)從兩方面來(lái)進(jìn)行考慮首先從信源角度考慮，在不丟失信源的原始信息條件下對(duì)信源的數(shù)據(jù)量盡可能精簡(jiǎn)壓縮，這就是信源編碼問(wèn)題。另一方面則從信道角度考慮，主要目的是克服誤差干擾，使數(shù)據(jù)實(shí)現(xiàn)無(wú)誤差或誤差很小的傳遞，這就是信道編碼問(wèn)題。12 .香農(nóng)信息論的主要目的是討論編碼的可行性問(wèn)題。討論在什么樣的條件下信源在信道中的可通過(guò)，或有效編碼的存在性問(wèn)題。信源編碼定理研究的是只要編碼的碼率大于信源的崎，則必存在信源編譯碼方案，使當(dāng)被編碼的信源分組長(zhǎng)度趨于無(wú)窮時(shí)，

7、譯碼誤差概率可以任意小，信道編碼定理研究的是如果編碼速率R小于信道容量、則對(duì)任意小的正數(shù)、存在碼率為R的信道碼、只要分組長(zhǎng)度充分大、就可以使誤差概率任意小百分之百13 .信源編碼問(wèn)題分有失真與無(wú)失真編碼問(wèn)題。所謂無(wú)失真編碼問(wèn)題就是要求編碼運(yùn)算能夠恢復(fù)原來(lái)的數(shù)據(jù)信息，經(jīng)編碼運(yùn)算后不丟失任何信息；而有失真編碼運(yùn)算問(wèn)題就是允許編碼運(yùn)算有一定的誤差發(fā)生，在允許誤差的條件下，尋找信源的最小“信號(hào)體積”。14 .無(wú)失真信源編碼的主要類型分等(或定)長(zhǎng)碼與變長(zhǎng)碼兩種。15 .使用定長(zhǎng)碼的主要優(yōu)點(diǎn)是編碼運(yùn)算簡(jiǎn)單，它可以依據(jù)消息與信號(hào)的長(zhǎng)度自動(dòng)區(qū)分各自所對(duì)應(yīng)的字符但它的缺點(diǎn)是編碼利用率低。16 .無(wú)論是等長(zhǎng)碼還

8、是變長(zhǎng)碼，它們的編碼原則都必須具有可還原性。17 .所謂通用碼就是針對(duì)以上問(wèn)題，在不知道信源的概率分布的情況下,對(duì)隨時(shí)出現(xiàn)的數(shù)據(jù)序列直接進(jìn)行編碼。常用的通用碼有LZW碼與YK碼。18 .哈夫曼(Huffman)碼與算術(shù)碼是兩種重要的變長(zhǎng)碼。19 .H(X),H(Y),H(X,Y),H(X|Y),H(Y|X)與I(X:Y)的相互關(guān)系可用集合之間的相互關(guān)系來(lái)表示:H(X,Y)H(X)20 .無(wú)記憶離散信源序列的最小可達(dá)速率就是信源的香農(nóng)崎(或幅率)。但這是在nT極限意義下的結(jié)論。實(shí)際應(yīng)用時(shí)，應(yīng)該在給定有限的n值的意義下，建立盡可能好的編碼方案。、判斷題(10分)：(對(duì)的在括號(hào)內(nèi)打錯(cuò)的在括號(hào)內(nèi)打父)

9、(1)C=0,10,00,01是即時(shí)碼;C=0,10,110,1110,10110,1101是唯一可譯碼；(3)C=1,01,001,0001是即時(shí)碼;(4)C=0,100,101,110,111,011是唯一可譯碼;(5)信源定長(zhǎng)碼的編碼問(wèn)題是求最大可達(dá)速率；(6)連續(xù)型隨機(jī)變量的微分嫡具有非負(fù)性；(7)全直線上的隨機(jī)變量，其期望和方差固定，則它的最大嫡分布為指數(shù)分布；(8)=3,l=1/3=I4=I5=h=I7=3,1=I9=l0=l1=4的碼滿足Kraft不等式;(9)信道編碼和信源編碼就是映射關(guān)系，都是對(duì)應(yīng)的映射關(guān)系；(10)信源輸出符號(hào)所攜帶的信息的有效程度即冗余度。三、計(jì)算題:1.

10、X與Y的聯(lián)合分布給定如下計(jì)算H(X),H(Y),H(X,Y),H(X/Y),I(X,Y)2H(X)一PilogPii1解：計(jì)算邊緣密度二01Yi01/31/32/311/92/91/3Xi4/95/91根據(jù)嫡的定義及H(X),H(Y),H(X,Y),H(XY),I(X;Y)之間的關(guān)系，可得4455Inln=0.5117(nat)9999同理，H(Y)=0.6931(nat)22H(X,Y)=J,、pjlogpj=1.1996(nat)iTidH(XY)=H(X,Y)-H(Y)=0.5056(nat)I(X;Y)=H(X)-H(XY)=0.0052(nat)2,已給信源概率分布S為XiX2X3X

11、4X50.400.200.200.100.10如取碼字母表U=0,1,試進(jìn)行二元Huffman編碼，并計(jì)算平均碼長(zhǎng)和方差信源概率碼概率碼概率碼概率碼xi0.0500000.150000.30000.3000x20.100001x30.150010.15001乂40.20100.20100.20100.431乂50.23110.23110.2311匚=pl=2.45(1分)622.仃i=Epi(li-L)=0.5475.(2分)i13 .設(shè)信源序列為aacdbbaaadc,對(duì)其進(jìn)行LZW編碼。4 .試構(gòu)造以下序列的YK數(shù)據(jù)壓縮編碼：nX=00010001010111110001010100011

12、1。、一.、一bx20x1.一5 .設(shè)隨機(jī)變量X的概率密度為,求(1)常數(shù)b;(2)微分燧h(x)00其它6 .信源的概率分布p=(0.25,0.25,0.20,0.15,0.15),在D=2時(shí)給出算術(shù)編碼，并計(jì)算平均碼長(zhǎng)xiPF(x)F(x)的二進(jìn)制表示li碼長(zhǎng)碼字10.250.1250.001300120.250.3750.011301130.200.6000.100114100140.150.7750.11000114110050.150.9250.111011041110(8分)L=3.5(2分)7 .已知LZW碼的碼字集合為：(0,b),(0,a).(1,c),(2,b),(1,a),(5,d),(4,c),畫(huà)出碼樹(shù)圖,并進(jìn)行譯碼，寫出信源消息。8 .根據(jù)教材110頁(yè)1)(2)的信道，寫出轉(zhuǎn)移概率矩陣，計(jì)算信道容量。9 .已知M信道的信道轉(zhuǎn)移概率矩陣為：0.800200.80.2,計(jì)算信道容量四、證明題1 .證明H(X),H(Y),H(X,Y),H(X|Y),H(Y|X)與I(X;Y)之間的鏈法則。2 .證明以下結(jié)論：如果Xn是無(wú)記憶信源，記X是由X確定的隨機(jī)變量，Ln是Xn的最優(yōu)不等長(zhǎng)編碼Ln1的平均長(zhǎng)度，那么不等式：H(x)&一H(x)