信息科學基礎2012B’卷及答案

1、河北科技大學20122013學年第一學期信息科學基礎試卷（B）學院理學院班級 姓名 學號1.得分一、簡答題（共8題，每題5分）設有一離散無記憶信道，其信道矩陣為P =121613131216161312，若 p(x )=，12題號一總分得分p（x ） = p（x ） = 4。試求最佳譯碼時的平均錯誤概率。234設某二元碼書 C=111000，001011，010110，101110，假設碼字等概率分布，計算此碼的編碼效率？采用最小距離譯碼準則，當接收序列為110110時，應譯成什么碼字?解釋等長信源編碼定理和無失真變長信源編碼定理，說明對于等長碼和變長 碼，最佳碼的每符號平均碼長最小為多少？編

2、碼效率最高可達多少？有一信源，它有6個可能的輸出，其概率分布如下表所示，表中給出了對應 的碼 A，B，C，D，E 和 F。消息P (a.)IABCDEFa11/200000000a21/400101101010100a31/160100111101101100101a41/160110111111011101101110a51/16100011111111010111100111a61/1610101111111111011011111011求這些碼中哪些是唯一可譯碼；求哪些是非延長碼(即時碼)；對所有唯一可譯碼求出其平均碼長L求以下三個信道的信道容量:,P3Q.10.20.30.400000

3、000000.30.700000000000.40.20.10.36.設二進制對稱信道的傳遞矩陣為2313（1）若 P（0）=3/4,P（1）二1/4，求 H（X）、H（X/Y）、H（Y/X）和 I（X； Y）；（2）求該信道的信道容量及其達到信道容量的輸入概率分布。7.有一個馬爾可夫信源，已知轉移概率為p (S / S) = -, p(S / S )= 113213p(S /S ) = 1, p(S /S ) = 0。試畫出狀態(tài)轉移圖，并求出信源熵。 12228.居住某一地區(qū)的女孩中有25%是大學生，在女大學生中有75%是身高1.6米以 上的，而女孩中身高1.6米以上的占總數(shù)一半。假如我們得

4、知“身高1.6米以上 的女孩是大學生”的消息，問獲得多少信息量？得分二、綜合題(共6題，每題10分)設消息集合共有7個元素，它們分別被編碼為a,c, ad, abb,bad,deb, bbcde),試利用惟一可譯碼判別準則判定它是否為惟一可譯碼。2、設輸入符號集為X=0,1,輸出符號集為Y=0,1。定義失真函數(shù)為 d(0,0)=d(1,1)=0, d(0,1)=d(1,0)二1,試求失真矩陣 D. TX1 x x 1設有一離散無記憶信源，其概率空間為J、 0.J，它們通過一干擾信道，信道輸出端的接受符號集為K =七,七，信道傳遞概率如圖所示。求：(1)信源X中事件氣和X2分別含有的自信息；收到

5、信息七(j = 1,2)后，獲得的關于(，= 1,2)的信息量;信源X和信源Y的信息熵；（4）信道疑義度H（X/Y）和噪聲熵H（Y/ X）；（5）接收到信息Y后獲得的平均互信息。0 1 2設某齊次馬氏鏈的一步轉移概率矩陣為0勺p 0 1 q 0 p 21_ 0 q p試求：（1）該馬氏鏈的二步轉移概率矩陣；（2）平穩(wěn)后狀態(tài)“0”，“1”，“2”的極限概率。二元平穩(wěn)馬氏鏈，已知P (0/0) =0.8, P (1/1) =0.7，求：每三個符號合 成一個來編二進制Huffman碼,試建立新信源的模型，給出編碼結果。某一信道，其輸入X的符號集為“，2,1；，輸入Y的符號集為0,1 ，信道矩陣一1

6、0 -為P=11，現(xiàn)有4個消息的信源通過這信道傳輸(消息等概率出現(xiàn))，若2 20 1對信源進行編碼，我們選這樣一種碼，C:頃,x U,1)x = 0或1。= 1,2)12 2 2 i其碼長為n = 4。并選取這樣的譯碼規(guī)則f (y , y , y , y ) = (y , y J-J-)1 2 3 41 2 2 2這樣編碼后信息傳輸率等于多少？證明在選用的譯碼規(guī)則下，對所有碼字有Pe = 0河北科技大學20122013學年第一學期信息科學基礎答案（B）、 簡答題（共8題，每題5分）答：用極大似然譯碼規(guī)則譯碼，先寫出輸入輸出的聯(lián)合概率分布122412平均譯碼錯誤概率為偵2412 24答：由定義，

7、信源的熵h( x)= p( a/% p(a)i=1=0.2log 0.2 - 0.19log 0.19 - 0.18log 0.18 0.17log 0.17 - 0.16log 0.16 - 0.17log 0.17 =log 6.282=2.64 墮6 信源的概率分布要求滿足 p（氣）=1，而此題中 p（a）=1.07 1。即各種可能發(fā)生的情況下，概率之和大于“ 1”，在實際情況下這是不可能發(fā)生的。答：等長信源編碼定理：對于任意e0,S。，只要墮酬上丑）+ ，則勺箜1當L足夠長時必可使譯碼差錯亍。變長信源編碼定理：只要一 陀好，一定丑(X)存在一種無失真編碼。等長碼和變長碼的最小平均碼長均

8、為1%酬，編碼效率最高可達100%。答：（1）惟一可譯碼有A,B和（2）即時碼有A和C（3）L =3（碼元/信源符號） A17同理得可f碼元/信源符號）,-17 一 Lc=疽碼元/信源付答：P1為一一對應確定信道，因此有宓H透）=1性4=2況/符號。P2為具有歸并性能的信道，因此有C2 H（Y）Mog23=1.5995切計符號P3為具有發(fā)散性能的信道，因此有GFaxH頃）=1箜技=1.5995切”符號6.答：聯(lián)合概率矩陣P =：XV 1214，邊緣概率分布為Px=p（0）6P (1)71212(1) H(X)= -p(0)log 2 p(0) - p(1)log1 p(1) = 0.811(b

9、it)，又因為信道傳遞矩陣 TOC o 1-5 h z 134 2P = 1 c ，故 H(Y / X) = -*p(xy )log p(y / x ) = 0.918(bit)Y / X12i ii i-一i=1 J =13 3H(Y) = 0.98(bit)，H(X / Y) = H(X, Y) H(Y) = 0.749(bit)I(X; Y) = H (X) - H(X / Y) = 0.06(bit)(2)設 P = w w 其中 H(Y/ X) = -* 2 p(x y )log p(y /x ) = 0.918(bit)X，i ii ii=1 J =1又由最大熵定理得H(Y) lo

10、gM = log2 2 = 1(bit)，所以有I(X; Y) = H(Y) - H (Y / X) 0.082(bit)故C = max/(X;Y) = 0.082(bit)，而上述等號成立的條件為p(y ) = p(打)P (x)又因為P =Y21 _w + w 332112所以須 w + w = w + w一 333因此達到信道容量時，信道輸入概率為P =|上 x I 2設 W = w wW = 34W =141- 一-72 -2133P 2 =9921101_ 33 _7.答：狀態(tài)轉移矩陣P 二，故該馬爾可夫信源是遍歷的。-W + W = W3 121W = W3 12W + W2 =

11、 1所以信源熵為 H(X) = f p(S)H(X / S)=0.688(bit/符號)i =18.答：設A表示“大學生”這一事件，B表示“身高1.60m以上”這一事件，則 p(A) = 0.25，p(B) = 0.5，p(B / A) = 0.75心 A B)= P( B)些=冬* = 0.375 ，p( B)= log = 1.420.375(bit)二、綜合題（共6題，每題10分）1.答：S0S1S2 S3 S4 S5S6 S7ebebbb cde de bad abbbadaddebbbcdebcdeS1到S7中都不包含S0中的元素，因此，S0是惟一可譯碼。2.答： 3.答：答:)-l

12、ogP(x= 0.737(騷)口 口I(x ) = -log p(x ) = 1.322(bit)22(2)I(x ; y ) = log P(七/ 氣)=0.059(bit)1 1 P(y)1I(x ; y ) = log P(y2/ x= 0.263(bit)2P( y2)I(x ; y ) = log P(J 切=0.093(bit)1p(y)1I(x ; y ) = log P(y2/ %)= 0.322(bit)2 2P( y2)(3)信源X 和信源r 的信息熵H(X) = -22 P(x)log p(x) = 0.97(bit)i=1H(Y)=-費 P(y .)log P(y.)

13、= 0.722(bit)j=1(4)信道疑義度H(X / Y) = H (X, Y) H(Y) = H(X) + H(Y / X) H(Y) = 0.963(bit)(5)平均互信息 I(X, Y) = H(X) = H(X / Y) = 0.007(bit)4.答：（1）由一步轉移概率矩陣與二步轉移概率矩陣的公式P2 = PxP得q 2 + pqpqp2q 22 pqp2q2pqp 2 + pqP 2 =（2）設平穩(wěn)狀態(tài)W = W1,W2,W3，馬爾可夫信源性質知WP = W，即qW + qW = WpW + qW = W132pW + pW = W233、W+ W + W3 = 1求解得穩(wěn)

14、態(tài)后的概率為/W =q21 - p + p 2W = pq1 - p + p 2P（O） = P（O）P（O/O） + P（1）P（O/1）5.答：由尹（）+ 只1）=1P（0/0）=0.8，P（1/1）=0.7,得極新信源共8個序列，各序列的概率為皿5） = Pg）皿/茶）汽圣/站趴）信源模型為000 001 010 011 100 101 110 1110.3840.0960.0360.0840.0960.0240.0840.196一種編碼結果（依信源模型中的序列次序）為0，001，10101, 1101，1011，00101， 0011,111.6.答：（1）對信源四個消息進行編碼，選擇

15、碼長n = 4，這組碼為C:（x ,x ,1,1） x = 0或 1（i = 1,2）1 2 2 2 i1 1)1 1)* 1 1)1 1 ,01 ,10 ,11 2云V2 2)V2 2)V2 2)（所以，碼子為C: 0 0V編碼后信息傳輸率R =丑炊)=J_ (bit/碼兀符號)L 2(2)設接收序列& = (yy yy ), y e0,1(i = 1,2,3,4)，根據(jù)信道的傳輸特性，1 2 3 4 i接受序列&共有16個，正好分成4個互不相交的子集，每一個碼字只傳輸?shù)狡渲袑囊粋€子集：a =100I12-(00 y y，以2 =r0 1I121、2 /一-(01 y3 y4)，a3=1I1 0 -2 J-(10，3，4)a 4 =r1 1I12/-(11y3y4)y3,y4 引0,1具體傳輸信道如下:m 1 1000000010010001101000101011001111000100110101011110011011110111100一2 20