信息科學基礎2012A卷及答案概況

1、河北科技大學20122013學年第一學期信息科學基礎試卷（A）學院理學院班級 姓名 學號得分、簡答題（共8題，每題5分）題號一二總分得分.如有6行8列的棋型方格，若有兩個質點 A和B,分別以等概率落入任一方 格內，且它們的坐標分別為（Xa,YA）、（Xb,Yb）,但A, B不能落入同一方格內 試求：（1）若僅有質點A,求A落入任一個格的平均自信息量;（2）若已知A已入，求B落入的平均自信息量;（3）若A, B是可分辨的，求A, B同時落入的平均自信息量.設離散無記憶信源為/十2 I“ 0318 ；16 求信源的嫡，并解釋為什么H（x）a log 6不能滿足信源的極值性。A卷（共14頁）第1頁3

2、.令離散無記憶信源S _ 6 S2 S3 |p，0.5 0.2 0.3_(1)求對S的最佳二元碼、平均碼長和編碼效率;(2)求對S2的最佳二元碼、平均碼長和編碼效率.解釋最小錯誤概率譯碼準則，最大似然譯碼準則和最小距離譯碼準則，說明三者的關系。.一個馬爾可夫過程的基本符號 0,1,2 ,這三個符號以等概率出現(xiàn)，具有相同的 轉移概率，并且沒有固定約束。(1)畫出單純馬爾可夫過程的狀態(tài)圖，并求穩(wěn)定狀態(tài)下的馬爾可夫信源嫡H1 ；A卷(共14頁)第2頁（2）畫出二階馬爾可夫過程狀態(tài)圖，并求穩(wěn)定狀態(tài)下二階馬爾可夫信源嫡H2。.當信源是無記憶時，無記憶的N次擴展信道的平均互信息與原信道平均互信息 的關系如

3、何？.什么是平均自信息（信息嫡）？什么是平均互信息？比較一下兩個概念的異 同之處。- 1|0 0 18. 一個馬爾科夫鏈的狀態(tài)轉移矩陣為p= 11 ,該馬爾可夫鏈是否具有遍2 3 611八0N 2 一歷性？為什么?A卷（共14頁）第3頁得分、綜合題(共6題，每題10分)1.設有一個二進制二階馬爾可夫信源，具信源符號集為0,1,條件概率為p(0|00)=p(1|11)=0.8, p(1|00)=p(0|11)=0.2, p(0|01)=p(0|10)=p(1|01)=p(1|10)=0.5.這個信源的符號數(shù)是q=2,共有四種可能狀態(tài)：S1=0O;S2=01; S3=10 S4=11.(1)給出信

4、源的狀態(tài)轉移矩陣.(2)求出平穩(wěn)分布.(3)該平穩(wěn)分布所對應的信源嫡.2、有一個一階平穩(wěn)馬爾可夫鏈 XX2，X,，各X.取值于集A = a1a2aq,1已知起始概率p(x)為p1 = P(X1 = X1) = , p2 = p3 =，其轉移概率如下表所小。412311/21/41/422/301/332/31/30A卷(共14頁)第4頁(1)求X1X2X3的聯(lián)合嫡和平均符號嫡；(2)求這個鏈的極限平均符號嫡；求H。，匕，也和它們對應的冗余度0.7 0.1 0.2-p =.設有一離散信道，其信道矩陣為1。2 0,1。7，求：(1)最佳概率分布？(2)當雙為)=0一7,聲區(qū))=0/時，求平均互信息

5、1y)=7信道疑義度H(XIY) = ?(3)輸入為等概率分布時，試寫出一譯碼規(guī)則，使平均譯碼錯誤率衣苫最小,并求此.A卷(共14頁)第5頁4.設線性分組碼的生成矩陣為(1)止匕(n, k)碼的 n=? k= ?,寫出此(n, k)碼的所有碼字。1U0100 10 110 0 10 1(2)求其對應的一致校驗矩陣H。(3)確定最小碼距，問此碼能糾幾位錯？列出其能糾錯的所有錯誤圖樣和對應 的伴隨式。(4)若接收碼字為000110,用伴隨式法求譯碼結果。A卷(共14頁)第6頁.某氣象員報告氣象狀態(tài)，有四種可能的消息：晴、云、雨和霧。若每個消息是 等概的，那么發(fā)送每個消息最少需要的二元脈沖數(shù)是多少？

6、又若4個消息出現(xiàn)的概率分別為1,1,1,1,問在此情況下消息所需的二元脈沖數(shù)是多少？如何編碼？.假定離散矢量信源N=3,輸出矢量序列為X =X1X2X3,其中Xi =1,2,3的取值為0,1;經信源傳輸后的輸出為丫=丫丫2工，其中Y，i =1,2,3的取值為0,1。 定義失真函數(shù)d(0,0)=d(1,1) = 0d(0,1) -d(1,0)-1求矢量失真矩陣dA卷（共14頁）第7頁河北科技大學20112012學年第一學期信息科學基礎答案(A)一、 簡答題(共8題，每題5分)11. (1)答：A洛入任一格的概率為p(aj= = 6 8 48481平均自信息量 H(A)= p(a)10g2 = l

7、og2 48 = 5.58(bit)yP(a)(2)答：A落入后，B再落入的概率p(b) =14747H(B)- p(bj)10g 2j 11p(bj)= log247 = 5.55(bit)(3)答：A, B同時落地的聯(lián)合嫡 48 47H(AB)-% % p(aibj)10g2= log2(47 48) = 11.14(bit)yjmp(aibj).答：由定義，信源的嫡6H(X)=T p(a)10g2 p(aj i 10 -0.2log20.2 0.1910g20.19-0.1810g20.18-0.17log2 0.17-0.161og20.16-0.171og2 0.17= 1ogz6.

8、28= 2.64 10g2 6信源的概率分布要求滿足Z p(a)=1,而此題中工p(a) =1.071。即各種可能發(fā)生的情況下，概率之和大于“ 1”，在實際情況下這是不可能發(fā)生的。3. (1)答：采用霍夫曼方法進行編碼，得s,： 1s2: 00s3 =01A卷(共14頁)第8頁3平均碼長為匚= pJi =1.5(碼元/信源符號) i 3編碼效率為H(S)L= 0.99(2)答:s2 _ 4sP |0.25s2 與4 5與0.15 0.15 0.1S3s10.1S2 s2 s2 s30.09 0.06s3s2s3 s30.06 0.04霍夫曼編碼后s2s2: 10j : 001 s2sl : 0

9、10 5與：110s3s : 111s2s2: 0000 s2s3: 0001s3s2： 0110 s3s3： 01119平均碼長為L= pili =3 (碼元/信源符號)i 19信源嫡為 H(S2)=- Pi log2Pi =2.971 (bit/ 信源符號) i 1編碼效率為=0.99L.答：最小錯誤概率譯碼準則下，將接收序列譯為后驗概率最大時所對應的碼字。最大似然譯碼準則下，將接收序列譯為信道傳遞概率最大時所對應的碼字。最小距離譯碼準則下，將接收序列譯為與其距離最小的碼字。三者關系為：輸入為等概率分布時，最大似然譯碼準則等效于最小錯誤概率譯碼 準則。在二元對稱無記憶信道中，最小距離譯碼準

10、則等效于最大似然譯碼準則。. (1)答：每個狀態(tài)發(fā)出三條轉移線，等概率出現(xiàn)。即每條轉移線的轉移概率為1/3,穩(wěn)定狀態(tài)下，三個狀態(tài)的概率也為 1/3。每一狀態(tài)的嫡3 TOC o 1-5 h z 11Hi - - p( j/i)10gp(j/i) =-3 log2 log23 = 1.585(b)jd3331穩(wěn)止狀態(tài)下的馬爾可夫缶源燧為 Hi=-乙p(i)Hi =3父一Hi = Hi =1.585(bit) T3A卷(共14頁)第9頁(2)答：有九個不同狀態(tài)，27條轉移線。9個不同狀態(tài)分別為00,01,02,10,11,12,20,21,22。每一狀態(tài)的嫡為2Hj =八p(x0j /x00)log

11、j衛(wèi)1.1p(x0j /X00) - -3 -log2-3310g2 3=1.585(bit)H(X/x01) =H(X/x10) =H(X/x02) =H(X /x00) =1.585(bit)又知二階馬爾可夫每一狀態(tài)的概率為 p(xj)=L1=1,所以二階馬爾可夫信源 j 3391嫡為 H2=v p(xij)Hij =91.585 =1.585(bit)j9.答：無記憶的N次擴展信道的平均互信息是原信道平均互信息的 N倍.答：平均自信息為I雙環(huán))表示信源的平均不確定度，也表示平均每個信源消息所提供的信息量。場)()三平均互信息為 表示從Y獲得的關于每個X的平均信息量，也表示發(fā)X前后Y的平均

12、不確定性減 少的量，還表示通信前后整個系統(tǒng)不確定性減少的量。平均互信息量I (X;Y)是信源概率分布p(x)的上凸函數(shù)，是信道傳遞概率p(y|x) 的下凸函數(shù)。.答：是遍歷的，p*p*p矩陣的所有元素全是正數(shù)，說明這個馬爾可夫鏈存在平 穩(wěn)分布，是遍歷的。二、綜合題(共6題，每題10分)1.答：(1)該信源的狀態(tài)轉移矩陣為0.8 0.2000.5 0.5-00000.5 0.5000.2 0.8(2) W=W1,W2,W3,W4,其中 W1=p(S1), W2=p(S2), W3=p(S3), W4=p(S4),A卷(共14頁)第10頁由平穩(wěn)分布的矩陣方程WP=W,以及p(S1)+p(S2)+p

13、(S3)+p(S4)=1 ,可以得到平 穩(wěn)分布為：p(S1)=p(S4)=5/14, p(S2) =p(S3)=1/7.該平穩(wěn)分布的信源嫡 H=p(S1)*H(0.8,0.2)+ p(S2)*H(0.5,0.5)+ p(S3)*H(0.5,0.5)+ p(S4)*H(0.8,0.2)=0.8 bit/ 符號。2. (1)答：信源是一階馬爾可夫的，所以111H(X1)log2- log2 =1.5(bit)2 24由 P(XiX2)= p(X2 /Xi)p(Xi)知 X1X2 的聯(lián)合概率為P(XiX2)12311/41/81/821/601/1231/61/120因止匕H(X2/X1) p(x1

14、x2)log p(x2/x1) =1.209(bit)X1X2由 P(X2X3) = P(X3 /X2) p(X2)知 X2X3 的聯(lián)合概率為P(X2X3)12317/247/487/4825/3605/7235/365/720XiX2X3 的聯(lián)合嫡為 H (X1, X2,X3) = H(Xi) + H (X2 / X1) + H (X3 / X2) = 3.969(bit)1平均符號嫡為H3(X) = H (Xi,X2,X3)= 1.323(bit / 符號)3WP =W(2)答：設信源穩(wěn)態(tài)符號概率分布 W=w 1 w2 w3,由：w1 w2 w3 = 1A卷(共14頁)第11頁4wi =

15、7解得 w2 =143W3 =14411132 1一信源的極限平均符號燧 HQ0=-H (-,-,-)十一H (一 ,0) M2=1.25(bit /符號) 72 4 4 143 3(3)三個嫡分別為 Ho(X) =log2 3 =1.585(bit)H1(X) = H(X1) = 1.5(bit)1H2(X)H(X1,X2) =1.355( bit)2由冗余度的計算公式R=1-1，得它們的冗余度分別為R0 =0, R =0.054, H。R =0.145.答：1)是準對稱信道，因此其最佳輸入概率分布為P6)=P)= S5。，(乃)=0 55切為)=02)當亞再)=0.了 p5) = Q.3時

16、有25) = 0充則一：H(XfY) = H(X) -I(X/ Y) = 0.7 版謫號上8?)=占3)此時可用最大似然譯碼準則，譯碼規(guī)則為有5=E= 10.2 + 0.1 + 0.2 = 0 25.答：1) n=6, k=3,由C=mGT得所有碼字為：000000, 001011, 010110, 011101, 100101, 101110, 110011, 111000A卷（共14頁）第12頁tor10100Q =110H =卜011010G知，oil ，,則101001 2）此碼是系統(tǒng)碼，由3）由H可知，其任意2列線性無關，而有3列線性相關，故有4 =3,能糾一 位錯。錯誤圖樣E伴隨式S = EHt TOC o 1-5 h z 100000101010000110001000011000100100000010010000001001 4）由 8 產出=0知 E= 010000,則/+ ”010110.答：至少需要二位二進制編碼元來發(fā)送 4個等概率發(fā)生的信息晴-00 云-01 雨-10 霧-114個信息的概率恰好是2的負整數(shù)幕，根據b=-10gpi得 晴-2位 云-3位雨-3位霧-1位采用霍夫曼編碼方法得 霧-0 晴-10 云-110 雨-111它們的平均碼長分別為：第一種情況：