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

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

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

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

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

5、統(tǒng)的數(shù)學(xué)模型由信源、信道、翻碼與譯碼組成，它們可用概率論模型給以描述，并由信息量確定它們的特征。8由消息變信號，再由信號還原成消息的運(yùn)算稱為編碼。編碼的數(shù)學(xué)本質(zhì)是一種映射，其核心問題是碼元的設(shè)計(jì)與選擇。9信息的傳遞過程可歸結(jié)為：首先由信源發(fā)出消息（原始消息），由編碼將原始消息變?yōu)樾盘枺⑦M(jìn)入 信道成為信道的輸入信號（簡稱輸入信號，或入口信號，輸入信號經(jīng)信道的編碼 通過信道，經(jīng)過信道的傳送，到達(dá)另一端，經(jīng)過信道譯碼形成輸出信號或出口信號，再經(jīng)過信源譯碼運(yùn)算把輸出信號變?yōu)橄?，這種消息是原始消息的還原；所以又稱還原消息，還原消息最終由接 收者接收。10 由于干擾的存在，信道的輸出信號可能與輸入信號

6、不同；從而形成還原消息與原始消息的不同，這種現(xiàn)象稱為通信誤差，是通信系統(tǒng)中需要克服的。通信誤差的克服一般通過硬件與軟件兩個途徑來解決。 軟件的改進(jìn)就是信道 編碼方式的改進(jìn)。11 為實(shí)現(xiàn)有效編碼，在編碼理論中同時從兩方面來進(jìn)行考慮首先從信源角度考慮，在不丟失信源的原始信息條件下對信源的數(shù)據(jù)量盡可能精簡壓縮，這就是 信源編碼問題。另一方面則從信道角度考慮，主要目的是克服誤差干擾，使數(shù)據(jù)實(shí)現(xiàn)無誤差或誤差很小的傳遞，這就是 信道編碼問題。12 香農(nóng)信息論的主要目的是討論編碼的可行性問題。討論在什么樣的條件下信源在信道中的可通過，或有效編碼的存在性問題。信源編碼定理研究的是 只要編碼的碼率大于信源的熵，

7、則必存在信源編譯 碼方案，使當(dāng)被編碼的信源分組長度趨于無窮時，譯碼誤差概率可以任意小，信道編碼定理研究的是 如 果編碼速率R小于信道容量，則對任意小的正數(shù)，存在碼率為 R的信道碼，只要分組長度充分大，就可以使誤差概率任意小百分之百13 信源編碼問題分有失真與無失真編碼問題。所謂無失真編碼問題就是要求編碼運(yùn)算能夠恢復(fù)原來的數(shù)據(jù)信息，經(jīng)編碼運(yùn)算后不丟失任何信息；而有失真編碼運(yùn)算問題就是允許編碼運(yùn)算有一定 的誤差發(fā)生，在允許誤差的條件下，尋找信源的最小“信號體積”14 無失真信源編碼的主要類型分 等(或定)長碼與變長碼 兩種。15 使用定長碼的主要優(yōu)點(diǎn)是編碼運(yùn)算簡單，它可以依據(jù)消息與信號的長度自動區(qū)

8、分各自所對應(yīng)的字符。 但它的缺點(diǎn)是_編碼利用率低。16 無論是等長碼還是變長碼，它們的編碼原則都必須具有可還原性 。17 .所謂通用碼就是針對以上問題，在不知道信源的_概率分布的情況下，對隨時出現(xiàn)的數(shù)據(jù)序列直接進(jìn)行編碼。常用的通用碼有 LZW碼與YK碼。18 .哈夫曼(Huffman )碼與算術(shù)碼是兩種重要的變長碼。19. H(X),H(Y),H(X,Y),H(X |Y),H(Y|X)與 I(X : Y)的相互關(guān)系可用集合之間的相互關(guān)系來表示：H(X,Y)20 .無記憶離散信源序列的最小可達(dá)速率就是信源的香農(nóng)熵(或熵率)。但這是在n極限意義下的結(jié)論。實(shí)際應(yīng)用時，應(yīng)該在給定有限的 n值的意義下，

9、建立盡可能好的編碼方案。、判斷題(10分)：(對的在括號內(nèi)打"，錯的在括號內(nèi)打勺(1) C =0,10,00,01是即時碼；C = 0,10,110,1110,10110,1101是唯一可譯碼;(3 )C=1 ,01 ,001 ,0001是即時碼；()(4) C=0, 100 , 101 , 110 , 111 , 011是唯一可譯碼；()(5) 信源定長碼的編碼問題是求最大可達(dá)速率；()(6) 連續(xù)型隨機(jī)變量的 微分熵具有非負(fù)性；()(7) 全直線上的隨機(jī)變量，其期望和方差固定，則它的最大熵分布為指數(shù)分布；()(8) r =3,h 日2 =13 “4 “5 “6 “7 =38 “9

10、 “10 “11 =4的碼滿足 Kraft 不等式；()(9)信道編碼和信源編碼就是映射關(guān)系，都是一一對應(yīng)的映射關(guān)系;(10)信源輸出符號所攜帶的信息的有效程度即冗余度三、計(jì)算題：1 . X與丫的聯(lián)合分布給定如下計(jì)算 H(X) , H(Y) , H(X,Y),H(X/Y) , l(X,Y)解：計(jì)算邊緣密度、X01Yi01/31/32/311/92/91/3Xi4/95/912H(X) Pi log Pii d根據(jù)熵的定義及H(X),H (Y), H(X,Y),H(XY),I(X;Y)之間的關(guān)系，可得-4ln4 - 51 n二 0.5117(nat)9999同理，H (Y) = 0.6931(n

11、at)2 2H(X,Y)二八' PijlogPij - 1.1996(nat)i T i mH(X Y)二 H(X，丫)- H(Y)二 0.5056(nat)I(X;Y)= H(X) - H(XY) = 0.0052(nat)2 已給信源概率分布S為'X1X2X3X4X5<0.400.200.200.100.10如取碼字母表U =0 , 1，試進(jìn)行二元Huffman編碼，并計(jì)算平均碼長和方差信源概率碼概率碼概率碼概率碼X10.0500000. 150000 . 30000 . 3000X20.100001X30 .150010 . 15001X40 .20100 . 20

12、100 . 20100 . 431X50 .23110 . 23110 . 2311匚Pih =2.45 （ 1 分）i622-ipi（li -L） 0.5475 （2 分）i丄3.設(shè)信源序列為aacdbbaaadc，對其進(jìn)行LZW編碼 4 試構(gòu)造以下序列的YK數(shù)據(jù)壓縮編碼:nX =0001000101 0111110001 0101000111。5 .設(shè)隨機(jī)變量X的概率密度為bx 0蘭x蘭1P其它'求(1)常數(shù)b;微分熵h(x)6.信源的概率分布p= (0.25 , 0.25 , 0.20 , 0.15 , 0.15),在D=2時給出算術(shù)編碼，并計(jì)算平均碼長XiPF（n）F (xi)

13、的二進(jìn)制表示li碼長碼字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)1 ，畫出碼樹圖,并進(jìn)行譯碼，寫出信源消息。8. 根據(jù)教材110頁1)(2)的信道，寫出轉(zhuǎn)移概率矩陣，計(jì)算信道容量。9. 已知M信道的信道轉(zhuǎn)移概率矩陣為：廣0.8002< 0 0.8 0.2計(jì)算信道容量四、證明題1.證明 H(X),H(Y),H(X, Y),H(X |Y ),H(Y|X)與 I (X; Y)之間的鏈法則2. 證明以下結(jié)論：如果Xn是無記憶信源，記 x是由X確定的隨機(jī)變量，Ln是Xn的最優(yōu)不等長編碼的平均長度，那么不等式:H(x)三半 wH(x)+成立，其中H (x)是X的熵。3. 證明：二進(jìn)對稱信道的信道容量為C