信息理論與編碼期末試卷A及答案

1、題號 題號一二信息論與編碼三四總分統(tǒng)分人題分35102332100得分一、填空題（每空1分，共35分） 得分| |閱卷人| 1、1948年，美國數(shù)學家 發(fā)表了題為“通信的數(shù)學理論”的長篇論文，從而創(chuàng)立了信息論。信息論的基礎理論是 ，它屬于狹義信息論。2、信號是 的載體，消息是 的載體。3、某信源有五種符號，先驗概率分別為，則符號“a”的自信息量為 bit，此信源的熵為 bit/符號。4、某離散無記憶信源X，其概率空間和重量空間分別為和，則其信源熵和加權熵分別為 和 。5、信源的剩余度主要來自兩個方面，一是 ，二是 。6、平均互信息量與信息熵、聯(lián)合熵的關系是 。7、信道的輸出僅與信道當前輸入有關

2、，而與過去輸入無關的信道稱為 信道。8、馬爾可夫信源需要滿足兩個條件：一、 ；二、 。9、若某信道矩陣為，則該信道的信道容量C=_。10、根據(jù)是否允許失真，信源編碼可分為 和 。11、信源編碼的概率匹配原則是：概率大的信源符號用 ，概率小的信源符號用 。（填短碼或長碼）12、在現(xiàn)代通信系統(tǒng)中，信源編碼主要用于解決信息傳輸中的 性，信道編碼主要用于解決信息傳輸中的 性，保密密編碼主要用于解決信息傳輸中的安全性。13、差錯控制的基本方式大致可以分為 、 和混合糾錯。14、某線性分組碼的最小漢明距dmin=4，則該碼最多能檢測出 個隨機錯，最多能糾正 個隨機錯。15、碼字101111101、0111

3、11101、100111001之間的最小漢明距離為 。16、對于密碼系統(tǒng)安全性的評價，通常分為 和 兩種標準。17、單密鑰體制是指 。18、現(xiàn)代數(shù)據(jù)加密體制主要分為 和 兩種體制。19、評價密碼體制安全性有不同的途徑，包括無條件安全性、 和 。20、時間戳根據(jù)產(chǎn)生方式的不同分為兩類：即 和 。二、選擇題（每小題1分，共10分） 得分| |閱卷人| 1、下列不屬于消息的是（ ）。A. 文字 B. 信號 C. 圖像 D. 語言 2、設有一個無記憶信源發(fā)出符號A和B，已知，發(fā)出二重符號序列消息的信源，無記憶信源熵 為（ ）。A. 0.81bit/二重符號 B. 1.62bit/二重符號 C. 0.9

4、3 bit/二重符號 D . 1.86 bit/二重符號3、 同時扔兩個正常的骰子，即各面呈現(xiàn)的概率都是1/6，若點數(shù)之和為12，則得到的自信息為（ ）。A. log36bit B. log36bit C. log (11/36)bit D. log (11/36)bit4、 二進制通信系統(tǒng)使用符號0和1，由于存在失真，傳輸時會產(chǎn)生誤碼，用符號表示下列事件，x0: 發(fā)出一個0 、 x1: 發(fā)出一個1、 y0 : 收到一個0、 y1: 收到一個1 ，則已知收到的符號，被告知發(fā)出的符號能得到的信息量是（ ）。A. H(X/Y) B. H(Y/X) C. H( X, Y) D. H(XY)5、一個隨

5、即變量x的概率密度函數(shù)P(x)= x /2，則信源的相對熵為（ ）。A . 0.5bit B. 0.72bit C. 1bit D. 1.44bit信息論與編碼6、 下面哪一項不屬于熵的性質(zhì)：（ ）A非負性 B完備性 C對稱性 D確定性7、根據(jù)樹圖法構成規(guī)則，（ ）A在樹根上安排碼字 B在樹枝上安排碼字 C在中間節(jié)點上安排碼字 D在終端節(jié)點上安排碼字8、下列組合中不屬于即時碼的是（ ）。A. 0，01，011 B. 0，10，110 C. 00，10，11 D. 1，01，009、 已知某（6，3）線性分組碼的生成矩陣，則不用計算就可判斷出下列碼中不是該碼集里的碼是（ ）。A. 000000

6、B. 110001 C. 011101 D. 11111110、下列保密編碼中屬于現(xiàn)代密碼體制的是（ ）A. 凱撒密碼 B. Vigenere密碼 C. 韋維納姆密碼 D. DES加密算法三、簡答題（四小題，共23分） 得分| |閱卷人| 1、請簡述現(xiàn)代密碼系統(tǒng)應當滿足的條件。(4分)2、請簡述連續(xù)信源最大熵定理的主要內(nèi)容。（6分）3、請解釋最小錯誤概率譯碼準則，最大似然譯碼準則和最小距離譯碼準則的含義，并說明三者的關系。（5分）答： 4、已知密鑰為yes，請利用多表代換密碼中的Vigenere（維吉尼亞）密碼原理分別對下列明文和密文進行編碼和譯碼。明文：A Mathematical Theo

7、ry of Communication； 密文：G ee y hgaxgp (需給出碼表或編譯碼過程，8分)信息論與編碼四、計算題（四小題，共32分） 得分| |閱卷人| 1、居住在某地區(qū)的女孩中有25%是大學生，在女大學生中有75%是身高1.6米以上的，而女孩中身高1.6米以上的占總數(shù)的一半。假如我們得知“身高1.6米以上的某女孩是大學生”的消息，問獲得多少信息量？（5分） 2、設離散符號信源為，試求：（1）信源的熵、熵的相對效率以及剩余度；（2）求二次擴展信源的概率空間及其信源熵。(10分)3、已知6符號離散信源的出現(xiàn)概率為，試寫出Huffman編碼的碼字并求其平均碼長。（7分）4、已知一

8、個(5, 3)線性分組碼C的生成矩陣為：,（1）求系統(tǒng)生成矩陣及校驗矩陣；（2）列出C的信息位與系統(tǒng)碼字的映射關系；（3）求收到r=11101時的譯碼步驟與譯碼結果。(10分)2015-2016年第2學期信息論與編碼期末考試A卷參考答案一、填空題（每空1分，共35分）1、 香農(nóng)、香農(nóng)信息論； 2、 消息、信息； 3、1、15/8； 4、7/4、9/4； 5、信源符號間的相關性、信源符號的統(tǒng)計不均勻性； 6、I(X;Y)=H(X)+H(Y)-H(XY)；7、無記憶；8、某一時刻信源符號的輸出只與此時刻信源狀態(tài)有關，與之前的狀態(tài)和輸出符號無關；信源在t時刻的狀態(tài)由當前輸出符號及t-1時刻信源的狀態(tài)

9、唯一確定；9、2bit/符號；10、無失真信源編碼和限失真信源編碼; 11、短碼、長碼；12、有效性、可靠性；13、前向糾錯 、 反饋重發(fā) ；14、3、1；15、2；16、理論保密性、實際保密性； 17、在加密和解密過程中，加、解密密鑰相同或從一個容易得出另一個的密碼體制； 18、公鑰體制、私鑰體制；填單鑰體制、雙鑰體制）或（對稱加密體制、非對稱加密體制）也可； 19、計算安全性、可證明安全性； 20、自建時間戳、具有法律效力的時間戳二、選擇題（每小題1分，共10分）B B B A C B D A D D三、簡答題（四小題，共23分）1、請簡述現(xiàn)代密碼系統(tǒng)應當滿足的條件。(4分)答：一個安全的

10、現(xiàn)代密碼系統(tǒng)應當滿足以下幾點要求：(每小點1分)（1） 系統(tǒng)即使達不到理論上不可破譯，也應當是實際上不可破譯的。（2） 系統(tǒng)的保密性不依賴于對加密、解密算法和系統(tǒng)的保密，而僅僅依賴于密鑰的保密性。、（3） 加密、解密算法適用于所有密鑰空間的元素。（4） 加密、解密運算簡單快捷，易于實現(xiàn)。2、請簡述連續(xù)信源最大熵定理的主要內(nèi)容。（6分）答：連續(xù)信源最大熵定理主要內(nèi)容如下：（每小點2分）（1）峰值功率受限條件下信源的最大熵定理：若某信源輸出信號的峰值功率受限，即信號的取值被限定在某一有限范圍（假設為a,b）內(nèi)，則在限定的范圍內(nèi)，當輸出信號概率密度分布為均勻分布時，該信源具有最大熵，且為。（2）平均

11、功率受限條件下信源的最大熵定理：若某信源輸出信號的平均功率和均值被限定，則當其輸出信號幅度的概率密度函數(shù)是高斯分布時，該信源達到最大熵值，且最大熵值為。（3）均值受限條件下信源的最大熵定理：若某連續(xù)信源X輸出非負信號的均值被限定，則其輸出信號幅度為指數(shù)分布時，信源X具有最大熵，且其值為。3、請解釋最小錯誤概率譯碼準則，最大似然譯碼準則和最小距離譯碼準則的含義，并說明三者的關系。（5分）答：最小錯誤概率譯碼準則下，將接收序列譯為后驗概率最大時所對應的碼字（1分）。最大似然譯碼準則下，將接收序列譯為信道傳遞概率最大時所對應的碼字。(1分) 最小距離譯碼準則下，將接收序列譯為與其距離最小的碼字。（1

12、分）三者關系為：輸入為等概率分布時，最大似然譯碼準則等效于最小錯誤概率譯碼準則。（1分）在二元對稱無記憶信道中，最小距離譯碼準則等效于最大似然譯碼準則。（1分）4、已知密鑰為yes，請利用多表代換密碼中的Vigenere（維吉尼亞）密碼原理分別對下列明文和密文進行編碼和譯碼。明文：A Mathematical Theory of Communication； 密文：G ee y hgaxgp (需給出碼表或編譯碼過程，8分)答：我們已知26個字母的排列如下表ABCDEFGHIJKLM0123456789101112NOPQRSTUVWXYZ13141516171819202122232425根

13、據(jù)提供的明文，可以得出密文YQSRLWKELGGSJXZCSJWSXASEKYFGGSRMGL,編碼過程如下表所示（5分）A0M12A0T19H7E4M12A0T19I8C2A0L11T19H7E4O14R17Y24O14F5C2O14M12M12U20N13I8C2A0T19I8O14N13Y24E4S18Y24E4S18Y24E4S18Y24E4S18Y24E4S18Y24E4S18Y24E4S18Y24E4S18Y24E4S18Y24E4S18Y24E4S18Y24YQSRLWKELGGSJXZCSJWSXASEKYFGGSRMGL根據(jù)提供的密文，可以得出譯碼后的明文為:I AM A D

14、OCTOR。譯碼過程如下表所示：(3分)G6E4E4Y24H7G6A0X23G6P15Y24E4S18Y24E4S18Y24E4S18Y24I8A0M12A0D3O14C2T19O14R17四、計算題（四小題，共32分）1、居住在某地區(qū)的女孩中有25%是大學生，在女大學生中有75%是身高1.6米以上的，而女孩中身高1.6米以上的占總數(shù)的一半。假如我們得知“身高1.6米以上的某女孩是大學生”的消息，問獲得多少信息量？（5分）解：設A表示“大學生”這一事件，B表示“身高1.60以上”這一事件，則 P(A)=0.25 p(B)=0.5 p(B|A)=0.75 （2分）故 p(A|B)=p(AB)/p

15、(B)=p(A)p(B|A)/p(B)=0.75*0.25/0.5=0.375 （2分） I(A|B)=-log0.375=1.42bit （1分）2、設離散符號信源為，試求：（1）信源的熵、熵的相對效率以及剩余度；（2）求二次擴展信源的概率空間及其信源熵。（10分）解：（1）（4分）（2）二次擴展信源的概率空間為：（3分）XX1/163/163/169/16（3分）3、已知6符號離散信源的出現(xiàn)概率為，試寫出Huffman編碼的碼字并計算平均碼長。（7分）解: Huffman編碼為：（5分）其他正確的Huffman編碼也給分。平均碼長 （2分）4、已知一個(5, 3)線性碼C的生成矩陣為：，（1）求系統(tǒng)生成矩陣及校驗矩陣；（2）列出C的信息位與系統(tǒng)碼字的映射關系；（3）列出譯碼表，求收到r=11101時的譯碼步驟與譯碼結果。（10分）解：（1）線性碼C的生成矩陣經(jīng)如下行變換：得到線性碼C的系統(tǒng)生成矩陣為，對應的校驗矩陣（3分）（2）由c=mG得消息序列m=000,001,010,011,100,101,110,111的系統(tǒng)碼字依次分別為：（3分）c0=00000, c1=00111,c2=01010, c3=01101,c4=10011, c5=10100, c6=11001, c7=11110 (3) 根據(jù)該(5,3)