《信息理論與編碼》,答案,考試重點(diǎn)

1、信息理論與編碼習(xí)題參考答案信息是什么信息與消息有什么區(qū)別和聯(lián)系答：信息是對(duì)事物存在和運(yùn)動(dòng)過程中的不確定性的描述。信息就是各種消息符號(hào) 所包含的具有特定意義的抽象內(nèi)容，而消息是信息這一抽象內(nèi)容通過語(yǔ)言、文字、圖像和數(shù) 據(jù)等的具體表現(xiàn)形式。語(yǔ)法信息、語(yǔ)義信息和語(yǔ)用信息的定義是什么三者的關(guān)系是什么答：語(yǔ)法信息是最基本最抽象的類型，它只是表現(xiàn)事物的現(xiàn)象而不考慮信息的內(nèi)涵。語(yǔ)義信息是對(duì)客觀現(xiàn)象的具體描述，不對(duì)現(xiàn)象本身做出優(yōu)劣判斷。語(yǔ)用信息是信息的最高層次。它以語(yǔ)法、語(yǔ)義信息為基礎(chǔ)，不僅要考慮狀態(tài)和狀態(tài)之間關(guān)系以及它們的含義，還要進(jìn)一步考察這種關(guān)系及含義對(duì)于信息使用者的效用和價(jià)值。 三者之間是內(nèi)涵與外延的

2、關(guān)系。第2章一個(gè)布袋內(nèi)放100個(gè)球，其中80個(gè)球是紅色的，20個(gè)球是白色的，若隨機(jī)摸取一 個(gè)球，猜測(cè)其顏色，求平均摸取一次所能獲得的自信息量答：依據(jù)題意，這一隨機(jī)事件的概率空間為-X -xx=12P0.80.2其中：氣表示摸出的球?yàn)榧t球事件，氣表示摸出的球是白球事件。a）如果摸出的是紅球，則獲得的信息量是1 （氣）=一網(wǎng)P（氣）=一1仲.8（比特）b）如果摸出的是白球，則獲得的信息量是/ （%）-1og P （%）=-燮.2 （比特）c）如果每次摸出一個(gè)球后又放回袋中，再進(jìn)行下一次摸取。則如此摸取次，紅球出 現(xiàn)的次數(shù)為（氣）次，白球出現(xiàn)的次數(shù)為“2）次。隨機(jī)摸取n次后總共所獲得信息量為np （

3、x ） I （x ）+ np （x ） I （x ）則平均隨機(jī)摸取一次所獲得的信息量為h ( x)=n np (氣)I (氣)+ np (% ) I (% )=-P (氣)1og p (氣)+ p (x2 )1og p (x2)=0.72比特/次居住某地區(qū)的女孩中有25%是大學(xué)生，在女大學(xué)生中有75%是身高1.6米以上的，而 女孩中身高1.6米以上的占總數(shù)的一半。假如我們得知“身高1.6米以上的某女孩是大學(xué)生” 的消息，問獲得多少信息量答：設(shè)事件A為女孩是大學(xué)生；設(shè)事件B為女孩身高1.6米以上。根據(jù)題意，則知：P（A）= 0.25P（B ） = 0.50P（B|A）= 0.75而“身高1.6米

4、以上的某女孩是大學(xué)生”這消息表明是在B事件發(fā)生的條件下，A事件發(fā)生。所以其概率為P G|B）根據(jù)貝葉斯定律可得P （a|b ）=些=P（ A）P A）= 0.25 x 0.75 = 0375 .1P（B）P（B）0.5則得知“身高1.6米以上的某女孩是大學(xué)生”這消息，能獲得的信息量I（A|B）=-logP（A|B）=log0.375 r 1.415 （比特）設(shè)一個(gè)系統(tǒng)傳送10個(gè)數(shù)字：0,1,2, ,9。奇數(shù)在以的概率傳送時(shí)，接收端有可能錯(cuò) 誤地判斷成為另外的奇數(shù)，而其他數(shù)字完全正確地接收。求收到一個(gè)數(shù)字后平均得到的信息 量答：發(fā)送集合X - 0,1,9,接收集合7 - 。,1,9,其中p (y

5、 - i )= 10(i - 0,2,4,6,8 )因?yàn)閜 (y - i|x - j )= 8P (yF 頊-2(i, j = 1,3,5,7,9 i j)(i, j = 1,3,5,7,9 i - j)所以P(y - i) = P (x - j)p (y - i|i，jx - j)= 110(i,j = 1,3,5,7,9 )最后得:H(Y )=一29 p (y = i )log p (y = i)=log10 = 3.232 (比特 /符號(hào)) i=0X10某一無(wú)記憶信源的符號(hào)集為0,1,已知信源的概率空間為* = 3 1P -L 4 4 _求信源熵。求由m個(gè)“0”和(100-m )個(gè)“l(fā)”

6、構(gòu)成的某一特定序列的自信息量的表達(dá)式。答：(1)計(jì)算由100個(gè)符號(hào)構(gòu)成的符號(hào)序列的熵。信源熵為H (X) = 1log4 + 3log4 = 0.8113 比特/符號(hào)443(2)該特定序列用A表示則/ 、( 1、m ( 3 (100-m)k 4 7r 41.5 + 1.585m (bit)I(A )=- log |-k 4 7(3)因?yàn)樾旁词菬o(wú)記憶信源，所以H (X 100)= 100H (X )= 81.13 比特/符號(hào)序列5.有一離散無(wú)記憶信源，其輸出為X e 0,1,2，相應(yīng)的概率為P0 = 1/4，p1 = 1/4， P2 = 1/2，設(shè)計(jì)兩個(gè)獨(dú)立實(shí)驗(yàn)去觀察它，其結(jié)果分別為七e0,1，

7、七0,1。已知條件概率如表2-4所示。 求I(X;”和I(X;七)，并判斷作哪一個(gè)實(shí)驗(yàn)好些。(2)求I(X;Y,Y )，并計(jì)算作Y和Y兩個(gè)實(shí)驗(yàn)比作Y或Y中的一個(gè)實(shí)驗(yàn)各可多得多少 121212關(guān)于X的信息。(3)求I(X;y|y )和I(X;yY )，并解釋它們的含義。1221答：(1) I(X; Y1 )=H (” H(Y1X ),要求 H(Y )和 H(Y1X )需要先求 P(7), P (XY), P (YJ X )已知。I(X; Y)=H (七)H (Y |X ),要求H (七)和H們X )需要先求P (Y), P(XY2) , P(Y /X)已知。由p(xy)= p(x)p(r|x)及

8、聯(lián)合概率分布與邊緣概率分布的關(guān)系可得 P(XY )及P )，如表2-1所示：表2-1p(X%01P( X0101/401/40101/41 1/4021/41/4201/2P (Y )1/21/2P (Y )1/21/212所以 TOC o 1-5 h z H(Y )= -log 2 + -log 2 = 1 比特 / 符號(hào) 122H G | X )=1 logl +1 logl +1 log 2 + -log 2 =-比特/符號(hào)44442I (X; Y )= H (Y )-H (YX )= 1 -=-比特 / 符號(hào)i 12 2同樣可求出P(XY )及P(Y 如表2-2所示：22所以H(Y)=

9、 2log2 + 2log2 = 1 比特/符號(hào)H(Y | X )= 4log1 + |log1 + 2log1 = 0 比特/符號(hào)I(X; Y)= H(Y)-H Y X )=1 比特 / 符號(hào)(xyy,x0001101101/40001001/40201/401/4p (yy )1 21/41/41/41/4H Gj X )= 4log 4 + 4log 4 + 4 log 4 + 4log 4 = 2 比特/符號(hào)因此第二個(gè)實(shí)驗(yàn)好些。(2)I(X;P (XYY)。I1 21p Gx)P Gj x)、;YY )= H(YY )-H Gy|X )1 22 22 2由于Y、七是相互獨(dú)立的實(shí)驗(yàn)，所以

10、p(YY2x)=p(|x)p(r|X)。P (YY X )n P (XYY2)n P (YY),因此要求出P(YY2) , P(YYX)和1 2I?(見表*和表2-3)表2-3 TOC o 1-5 h z H Gy |X)= ilog1 + ilog1 + log2 + log2 =-比特/符號(hào)1 244442I(X; YY )= H (YY )-H (YY X )= 2- i = 3 比特/符號(hào)1 21 21 222可以看到：做Y和Y兩個(gè)實(shí)驗(yàn)比做Y一個(gè)實(shí)驗(yàn)可多得到的信息為 121I(X;YY )-1(X;Y)= 3-上=1 比特/符號(hào)12122可以看到：做Y和Y兩個(gè)實(shí)驗(yàn)比做Y一個(gè)實(shí)驗(yàn)可多得到

11、的信息為 122I（x；yy ）-1（x；y ）= 31=1 比特/符號(hào)1 2222（3）I（x；y y ）= I（x；yy ）-i（x；y ）= 3-1=-比特/符號(hào)，它表示做完 y 實(shí)1 21 22222驗(yàn)以后，從、實(shí)驗(yàn)可得到關(guān)于x的信息量。I （x； y y ）= I（x；yy ）-i （x；y ）=3 - 1=1比特/符號(hào)，它表示做y完實(shí)驗(yàn)以 1 21 21221后，從七實(shí)驗(yàn)可得到關(guān)于x的信息量。6.設(shè)信源J ） = ；1通過一干擾信道，接收符號(hào)為y = y, y ，信道傳遞概P（x）0.6 0.41 2率如圖2-7所示。求：（1）信源x中事件七和七分別攜帶的自信息量。（2）收到消息y

12、.（j = 1,2）后，獲得的關(guān)于x （i = 1,2）的信息量。（3）信源x和信源y的信息熵。（4）損失熵h（x|y）和噪聲熵HQ|x）。（5）接收到消息y后獲得的平均互信息。5/6圖2-7 習(xí)題6圖答：（1）因?yàn)樗訮 (氣)=0.6P (x2 )= 0.4(x ) = -log0.6 n 0.737 (比特)1I (x ) = -log0.4 n 1.322 (比特)2（2）收到消息y的概率為:= 0.6* %+ 0.4以= 0.8P（y ）=2? TOC o 1-5 h z i=lIP（y ）=1-尸（y ）=0.2 21所以收到消息y 后獲得的關(guān)于x的信息量即/ , y）為:Jii

13、j/G,y ） = log。= log 吝 0.059 （比特 / 符號(hào)）i i PVy ）0.81l（x,y ） = log ）= log M R 一史63 （比特 / 符號(hào)）2Py ）0.22（ P（y /x ） /a/ G , y ） = log , -0.093 （比特/符號(hào)）i Py ）0.81X772/G ,y ） = log 2 址=log史 0.322 （比特/符號(hào)）2 2P（V f 0.2（3）H（X ） = -X P （x ）logP G ） = -（0.6*log 0.6 + 0.4*log 0.4） 0.971 （比特/符號(hào)） iii=lH（Y）=-Xp（y ）logP

14、（y ）= （0.8*log 0.8 + 0.2*log 0.2）q 0.722 （比特/符號(hào)） iii=l（4）（x）=z p（x,y）iogx,r其中 TOC o 1-5 h z P（x ,y ） = P（x ）p（y /x ） = 0.6* = 0.5iiiii6P（x , y ） = P（x）F（y /x ） = 0.6* = 0.121216P（x , y ） = P（x）F（y jx ） = 0.4* = 0.312124P G , y ） = P（x）F（y lx ） = 0.4* = 0.1222224所以噪聲炳:H (; X ) = 0.5*log + 0.1*log + 0

15、.3*log + 0.1*log ,5 61 63 41 4=0.715 (比特/符號(hào))損失熵：H (X/Y )= H (X )+ H (：X )-H(Y ) = 0.971 + 0.715 - 0.722=0.964 (比特/符號(hào))(5)接收到消息Y后所獲得的平均互信息量為：I(X,Y)= H(X)-H(XY)= 0.971 -0.964 = 0.007 (比特/符號(hào))7.某信源的消息符號(hào)集的概率分布和二進(jìn)制代碼如題表2-5所示。表2-5 習(xí)題7表信源符號(hào)uuu概率01/21/41/8代碼010110u1/8111試求：消息的符號(hào)熵。平均每個(gè)消息符號(hào)所需要的二進(jìn)制碼元的個(gè)數(shù)或平均代碼長(zhǎng)度結(jié)果

16、求碼序列中的 一個(gè)二進(jìn)制碼元的熵。消息是由符號(hào)序列組成的，若各符號(hào)之間相互獨(dú)立，假設(shè)其對(duì)應(yīng)的二進(jìn)碼序列中出 現(xiàn)的”和“1”的無(wú)條件概率為p(0)和p(1)，求相鄰碼間的條件概率p(0I1)、pGm)、pGD、p (0I0)。答：信源熵為H(U)= 1log2 + 1log4 + 1log8 =-比特/符號(hào)2444設(shè)平均代碼長(zhǎng)度為E，則L = Lx1 + x2 + x3 + x3 = 7 二進(jìn)制碼兀/符號(hào)24884二進(jìn)制碼元的熵為W)= 1比特/二進(jìn)制碼元L由于符號(hào)間相互獨(dú)立，因此1 1 1p(0)= 2 4 8 = , p(1) = 1-p(0)=-L 22為求相鄰碼元間的條件概率,先求相鄰碼

17、元間的聯(lián)合概率:p (1,1) =所以Gn)= p(1P1p 叫p (1) 2p (o|1)=1p G|1)=-2同理111111x+x+x.p (0,0 )= 2 2 4_2 8 2 =1L4p (0|0 )=留=11p(0)2p G|0 )= 1 p(0|0 )=-2二次擴(kuò)展信源的熵為H(X2)，而一階馬爾可夫信源的熵為H (XJ%)，試比較兩者的大小，并說明原因。答：H (X2 )= 2H (X) H (X) H (XJ氣)二次擴(kuò)展信源的熵是一個(gè)聯(lián)合熵，其值應(yīng)該大于單符號(hào)信源熵，而馬爾可夫信 源的熵是一個(gè)條件熵，其值小于單符號(hào)信源熵。馬爾可夫信源符號(hào)間的依賴關(guān)系提 供了額外的信息量，從而

18、減小了信源的不確定性。設(shè)有一個(gè)馬爾可夫信源，它的狀態(tài)集為s ,s ,s ，符號(hào)集為 ,a ,a ，及在某狀態(tài)123123下發(fā)出符號(hào)的概率為P(as ) (i,k = 1,2,3)，如圖2-8所示。圖2-8 習(xí)題9圖試求：求出圖2-8中馬爾可夫信源的狀態(tài)極限概率，并找出符號(hào)的極限概率。計(jì)算信源處在某一狀態(tài)下輸出符號(hào)的條件熵H (%|S = j)(j = s , s , s )。 TOC o 1-5 h z 123求出馬爾可夫信源熵H0答：(1)由狀態(tài)圖得： 1p()= p()+ p (S3)p (s )=1 p (s )+1 p (s )L%11%1VE P CxIx )p (xIxx )log

19、 E P CxIx )p Xxx)11 231 1 211 231 1 2X1X1所以 P(xxx )= P(xx ) TOC o 1-5 h z 1 2 32 3 HYPERLINK l bookmark100 o Current Document iXP (x x |x )P(x ) = P (x |x )P (x )X1上式對(duì)所有x ,x ,x的取值都成立，所以 123所以 P (xx1 3x2 )= P (x3x2)x1P(x x )P(x xx )= P(x2x113123x2)-P(xx lx )logP(x xx )-P(x I1 3231 232-3, 12J x2)log P

20、 (x3| x2)x1因?yàn)?P(x2)1, xx2 e X2所以上式兩邊相乘，等號(hào)不變。有-P(x )P(xx x )logPCx xx )-P(x )PCx x )logPCx x )23122323x1上式對(duì)所有x ,x都成立，所以對(duì)所有x ,x求和下式也成立2323- P(xxx )logP(x |xx )- P(x x )logP(x lx )12331 22 332x1x2x3x2 x3因?yàn)镠 (X3|X 1X2) H (X3|X2)所以是平穩(wěn)信源只有當(dāng)PWxx )= P(xH (XJ X2) H (X2|%)21H (X3IX1X2 ) H (X2| X1)(對(duì)所有x , x ,

21、x)時(shí)等式成立。123證畢12.在一個(gè)3X3的國(guó)際象棋棋盤上，試求：(1) “王”隨機(jī)行走的熵率。相同情況下“車”、“象”和“后”對(duì)應(yīng)的熵率(“象”分為兩種)。答：(1)由于“王”不能停在當(dāng)前格上，必須走一步，所以就9個(gè)狀態(tài)的穩(wěn)態(tài)分布w = p （s ）= EJE其中Ej是從第i格出發(fā)能夠到達(dá)的格子數(shù)，E = Z E。通過簡(jiǎn)單的計(jì)算可得:iw = w = w = w = ，w = w = w = w = ，w =1379402468405 40再根據(jù)“隨機(jī)行走”的意義可得log3 i = 1,3,7,9H（X|s.）= 0的微分熵為h (X )= -f (x)log f (x)dx0=-J 2

22、中(x)log 2中(x)dx0=-J 2里(x)log2dx-J 2中(x)log中(x)dx00=log 2 - j 8 甲(x)log甲(xlx (因?yàn)榧?一x) = (x)-3=1 log(2ne。2)- log 2 (比特/樣值)14.連續(xù)隨機(jī)變量X和/的聯(lián)合概率密度為 N)一1x 21 + 二-2 xy + y 2 k S Jp (xy )=-= exp 23 SNI 2 N試求h(x), h(Y), hG|x)和 I(X;Y)0答:p (x ) = J+8 p (xy )dy = J+8 exp-8-8 2n、；SN r n、一一x 21 + 2 xy + y 2k S Jdy1

23、2N= exp82nS(x2-| exp2S J 72nN.1dy= exp 2nSp(y|x)= P(y = .-1exp p (x )寸 2 nN(y - x )22 Ndxdxh (x ) = - j+8 p (x )ln p (x )dx = - j+8 p (x)ln lexp-8-82nS=-j+8 p (x)ln | dx - j+8 p (x)lnl exp-8 U/2nS J -8 I=ln 2 nS + j+8 p (x )蘭 dx-82S=ln (2 nS + S = ln v2neS 2Sh(Y|X )= -f+8f+8 p (xy)ln p (y x)dxdy-8 -

24、8= -j+8j+8 p (xy )-8 -8l-上 2nN 2 N(y - x)2 dxdy=ln 2 nN + !J+8【exp 2N -8 2nSf-當(dāng) j+exp2S J -8很應(yīng)(y - x)2 dydx=ln、2nN + 上=ln、2neN2h (XY )=-f+8f+8 p (xy )ln p (xy )dxdy-8 -8=J+8+8exp-8 -8 2nSx 2 |1 I expV 2S J 盾NIn 2nSN 2Sdxdy=ln 2n. SN + f+8f+8 擋 一 exp-8 -8 2S v2nSdxdy+ J+-x)21+8J+8exp-8 -82N2nSx 2 |1I

25、 expV 2S J 岳Ndxdy=In 2n D = XX p(x y )d(x, y ) = 1 - A n A = 1 Di =1 j = 1又因?yàn)镻(y.) = 1/3( j = 1,2,3)，由(3-13)可得率失真函數(shù)R(D)為R(D) = min I(X; Y) = h(Y) H(Y / X)p (yj 氣)ePD=log + D 1華5 + (1 D )log(1 D)(2)當(dāng)信源 X = 0,1,，D = 1/2 時(shí)，R( D) = 1 H (D,1 D) = 03.設(shè)一個(gè)符號(hào)等概率輸出的離散無(wú)記憶信源X的失真函數(shù)矩陣為d (x., y)=112 1試求：率失真函數(shù)R(D)

26、； (2)信道轉(zhuǎn)移概率P(X/y) 0答：由失真函數(shù)可知通過的信道為對(duì)稱信道，故可設(shè)對(duì)稱性可設(shè)信道的轉(zhuǎn)移概率A A 1 - 2A P =ji 1 - 2 A A A則由信源概率分布和信道轉(zhuǎn)移概率分布可得到信宿接收信號(hào)的概率分布p(yj) = z p亳吃，得 iP(y ) = 1 xA +1 x(1 2A),1 xA +1 xA,1 x(1 2A) +1 xAj L 222222_=2x(1-A), a,2 x(1-A)則最大限定失真度DD = ZZ p P d = p P d + p P d + p P d + p P d + p P d + p P d i ji ij 1 11 111 21

27、 121 31 132 12 212 22 222 32 23i j=2 a x1 + A x 1 + (1-2 A) x 2 + (1-2 A) x 2 + A x1 + A x1=1 La + A + 2 - 4 A + 2 - 4 A + A + A= 1 4 - 4 A= 2 - 2 A22n A = (2-D)/2因?yàn)樾潘薜男畔㈧貫镈 2 - D D D D 2 - D 2 - D D DH (Y) = H p( yj) = H(, 了 = -alog 彳-FlogTlog J,2 - D 2 - D ,H(Y / X) = H(PJ = H(-2- ,-2-, D -1)2 - D

28、 2 - D=-2 xlog- (D - 1)log( D -1)=-(2 - D) log(2 - D) - (D - 1)log( D -1)可以求出信息率失真函數(shù)R (D)R(D) = I (X; Y) = H (Y) - H (Y / X)=(D - 1)log( D -1) - D log D + 2D log 2D2422信道轉(zhuǎn)移概率矩陣為P =ji2 - D22 - D4.設(shè)一等概率離散無(wú)記憶信源X = 0,1,2,3,信宿接收符號(hào)y = 0,1,2,3，其失真函數(shù)2矩陣為d 3, y.)0111101111011110試求最大失真度D 、最小失真度D.和率失真函數(shù)R(D)。答:

29、由已知對(duì)稱信源和失真函數(shù)矩陣d( X, y.)可知，它的平均失真度D = p(x., y ) i。j= PXY再根據(jù)最大失真度的定義，有1 3D = min p(x )d(x , y ) = 1 -=y Xn根據(jù)率失真函數(shù)定義可得3R(D) = log4 - D log3 - H(D) 0 D 彳5.設(shè)一個(gè)n進(jìn)制離散無(wú)記憶信源X的失真函數(shù)為試證明：R(D) = logb (1- 2)log n1-(D / a)。a 1 - (1/ n)a證:由失真函數(shù)d(氣,y)的對(duì)稱性和信道轉(zhuǎn)移概率矩陣七的歸一性可以求得可以求得AIP = n -1JI1 - An - 1A1 - An -11 - An -1 a M三 A n - 1 n -1D = ZZ p(x )P d (x , j ) = (1- A)a n A = 1 - D / a。i Jp (y,) = ip (七 n( j=1,2,n)進(jìn)一步可求得率失真函數(shù)R (D)R( D) = H p (y) - H P”=log n + A log A + (1- A)log(1 - A) + (A - 1)log n(1-上) n=A log nA + (1- A)log1 - A1-1/ nD D / a D=log、+ (1一)log n1-(D/a)a1 - (1/