答案~信息論與編碼練習(xí)

1、有一個(gè)二元對(duì)稱信道，其信道矩陣如下圖所示。設(shè)該信道以1500個(gè)二元符號(hào)/秒的速度傳輸輸入符號(hào)?，F(xiàn)有一消息序列共有14000個(gè)二元符號(hào)，并設(shè)在這消息中P(0)=P(1)=1/2。問從信息傳輸?shù)慕嵌葋?lái)考慮，10秒鐘內(nèi)能否將這消息序列無(wú)失真地傳送完？0 098 *00.020.021 0.98 1解答：消息是一個(gè)二元序列，且為等概率分布，即P(0)=P(1)=1/2，故信源的熵為H(X)=1(bit/symbol)。則該消息序列含有的信息量=14000(bit/symbol)。下面計(jì)算該二元對(duì)稱信道能傳輸?shù)淖畲蟮男畔鬏斔俾剩盒诺纻鬟f矩陣為： 「0.980.02]P=0.020.98信道容量(最大信息傳輸率)為：C=1-H(P)=1-H(0.98)e0.8586bit/symbol得最大信息傳輸速率為：Rt^1500符號(hào)/秒X0.8586比特/符號(hào)^1287.9比特/秒^1.288X103比特/秒此信道10秒鐘內(nèi)能無(wú)失真?zhèn)鬏數(shù)米畲笮畔⒘?10XRt^1.288X104比特可見，此信道10秒內(nèi)能無(wú)失真?zhèn)鬏數(shù)米畲笮畔⒘啃∮谶@消息序列所含有的信息量，故從信息傳輸?shù)慕嵌葋?lái)考慮，不可能在10秒鐘內(nèi)將這消息無(wú)失真的傳送完。2、若已知信道輸入分布為等概率分布，且有如下兩個(gè)信道，其轉(zhuǎn)移概率矩陣分別為：120■120100120■120010100000000P=020211Pp=0020201.1001L2020212000020201212試求這兩個(gè)信道的信道容量，并問這兩個(gè)信道是否有噪聲？解答：由信道1的信道矩陣可知為對(duì)稱信道故C=log4-H(++00)=1bit/symbolH(X)=log4=2bit/symbol>C有嫡損失，有噪聲。 1為對(duì)稱信道，輸入為等概率分布時(shí)達(dá)到信道容量C=log8-H(+士000000)=2bit/symbolH(X)=C,無(wú)噪聲23、已知隨即變量2X和Y的聯(lián)合分布如下所示：

解：⑴⑵^Y_0101/83/813/81/8試計(jì)算：H(X)解：⑴⑵^Y_0101/83/813/81/8試計(jì)算：H(X)、H(Y)、H(XY)、H(X/Y)、H(Y/X)、I(X；Y)H(X):=1H(Y):=1H(XT]=；比爵8)+^Logl三6 呂\+-LogfS)=l.gllsH(X/Y)=H(XY)--H(Y)=1.811-1=0.811H(Y/X)=H(XY)--H(X)=1.811-1=0.811(5)l(X；Y)=H(X)-H(X/YJ=l-a.Sll=0.1g94、有一個(gè)可以旋轉(zhuǎn)的圓盤，盤面上被均勻的分成38份，用1,2,3,……，38數(shù)字標(biāo)示，其中有2份涂綠色，18份涂黑色，圓盤停轉(zhuǎn)后，盤面上指針指向某一數(shù)字和顏色。若僅對(duì)顏色感興趣，計(jì)算平均不確定度；若對(duì)顏色和數(shù)字都感興趣，計(jì)算平均不確定度；如果顏色已知，計(jì)算條件熵。2 (或'\ 1S [" 13 f33]解.(1)H(色)=—解：(1)H(S)參 W類 IS焚 [1時(shí)P(色數(shù))=藥H(色數(shù))=L■晦鴕)=5邱3凸H(數(shù)/色)=H(色數(shù))-H(色)=5.擦-1.245=4.0035、在一個(gè)二進(jìn)制信道中，信源消息集X={0,1}，且P(0)=P(1),信宿的消息集Y={0,1},信道傳輸概率P(1/2)=1/4,P(0/1)=1/8。求：在接收端收到y(tǒng)=0后，所提供的關(guān)于傳輸消息X的平均條件互信息量I(X；y=0).該情況所能提供的平均互信息量I(X;Y).解：(1)<3 1七七2"'-'44gS7917P(ij)=17P(i/j)=11LIE16；55」7 9a16 16p(玖)=-+ 、一S腌 1百(2)方法1：體Y)=P閩聯(lián)河十")牌M)=7 3—0.40S+—0.236=0.31116 W6某一無(wú)記憶信源的符號(hào)集為{0,1}，已知p0=1/4,p1=3/4求符號(hào)的平均熵由100個(gè)符號(hào)構(gòu)成的序列，求某一特定序列(例如有m個(gè)“0”和(100-m)個(gè)“1”))的自信息量的表達(dá)式。計(jì)算(2)中的序列的熵。

TOC\o"1-5"\h\z3解：po；=-pi:=-3 (4>H(X)=-Lo^+-Lo§T=強(qiáng)14 4 13,lfVvv 叩一叫 rm⑵1*&....茂1知--l□目一?一=2m+(100-m)L.og-=1.58:5-in+41.500\o"CurrentDocument"IE3J '⑶(3)H的&...*g)=H(XJ+H(>y+....+H貨向)=1四成0=1000.311=81.17、一階馬氏鏈信源有三個(gè)符號(hào){u1,u2,u3},轉(zhuǎn)移概率為：P(u1/u2)=1/2, P(u2/u2)=1/2, P(u3/u1)=0, P(u1/u2)=1/3, P(u2/u2)=0,P(u3/u2)=2/3,P(u1/u3)=1/3, P(u2/u3)=2/3, P(u3/u3)=0,畫出狀態(tài)圖并求出各符號(hào)穩(wěn)定概率。解：i22P(j/i)=I012J3130i22P(j/i)=I012J313023<04七求得W=0.368、設(shè)有一信源，它在開始時(shí)以p(a)=0.6,p(b)=0.3,p(c)=0.1的概率發(fā)出X1，如果X1為a時(shí)則X2為a,b,c的概率為1/3;如果X1為b時(shí)則X2為a,b,c的概率為1/3;如果X1為c時(shí)則X2為a,b的概率為1/2,而為c的概率是0;而且后面發(fā)出Xi的概率只與Xi】有關(guān)。又p(X/Xi-1)=p(X2/X1),iN3。試?yán)民R兒可夫信源的圖示法畫出狀態(tài)轉(zhuǎn)移圖，并求出狀態(tài)轉(zhuǎn)移矩商和信源熵H8

P(j/i)=解方程組3L'^W1'W2SW23 3得到W1=「W2=-,W3=S oWl+W2+W3=1H(X2/a)=L□或3)=1.5S5H(X2/b)=H(X3/c>P(j/i)=解方程組3L'^W1'W2SW23 3得到W1=「W2=-,W3=S oWl+W2+W3=1H(X2/a)=L□或3)=1.5S5H(X2/b)=H(X3/c>H戒<)=W[H(X2㈤+形H㈤佝+桐明例3?=--Log(3)十-Log(；3)十^匚口槳)=1.439§ ￡ 49某信源符號(hào)有8個(gè)符號(hào){u1,???u8},概率分別是1/2，1/4，1/8.1/32,1/64,1/128,1/128，編成這樣的碼：000,001,010,011,100,101,110,111。（1） 信源的符號(hào)熵H（U）（2） 出現(xiàn)一個(gè)“1”或一個(gè)“0”的概率；（3） 這樣碼的編碼效率；（4） 相應(yīng)的香農(nóng)碼和費(fèi)諾瑪；（5） 該碼的編碼效率？解：，1/16，求1111111 148163264128128H(U)=?- 八- ~ - … - “、- …、 - … …-Log(2)+- Log(4) +- Log(8) +—Log(16) +—Log(32)+—Log(64)+ —Log(128) +—Log(128)4 8 16 32 64 128 128(2)每個(gè)信源使用3個(gè)二進(jìn)制符號(hào)，出現(xiàn)0的次數(shù)為1632641281281.984121 1 1十2?—十2■-十-4 S 11-十62■—十3211十倒12S1現(xiàn)a1的次數(shù)為111111—十1——F2'—十]1一十1——十2-43 163264123=239S1-—=U5駝12SP(0)=P(1)=2.398 =0.S042.39S+0.^60.5S62.333+0.536=0.1961.9S4 =0.6613（4） 相應(yīng)的香農(nóng)編碼

信源符號(hào)xi符號(hào)概率pi累加概率Pi-Logp(xi)碼長(zhǎng)Ki碼字x11/20110x21/40.52210x31/80.7533110x41/160.875441110x51/320.9385511110x61/640.96966111110x71/1280.984771111110x81/1280.9927711111110相應(yīng)的費(fèi)諾碼信源符號(hào)xi符號(hào)概率pi第一次分組第二次分組地 —*第二次分組第四次分組第五次分組第六次分組第七次分組二元碼x11/200x21/41010x31/810110x41/16101110x51/321011110x61/6410111110x71/128101111110x81/128111111110香農(nóng)碼和費(fèi)諾碼相同——1+—N-I— +—4-I 5+— -+3——1+—N-I— +—4-I 5+— -+3康32 64平均碼長(zhǎng)為123 123□H?□H?編碼效率為：R-=1.9S4, 二11,既抖10已知符號(hào)集10已知符號(hào)集｛x1,x2,x3,…｝為無(wú)限離散集合，p(x1)=1/2,p(x2)=1/4,p(x3)=1/8,p(xi)=1/2i,…。用香農(nóng)編碼方法寫出各個(gè)符號(hào)的碼字；(2)計(jì)算碼字的平均信息傳輸率。(3)計(jì)算信11-1源編碼效率。3解：(1)pjW累加概率為Pj=Z瑋累加概率分別為12 1i=o符號(hào)x1x1x2x3x4x5x6x7…概率1/21/41/81/161/321/641/1281/256…累加概率00.50.750.8750.9380.9690.9840.992…碼長(zhǎng)12345678元碼010110111011110111110111111011111110…

信源的信息量為—Lug-'J'j十—L1?gi'4'1十—Le§i：幻+—Logfl^j十 十一Log(2)+■. 2 """ 4 " 16 " ._i "平均碼長(zhǎng)為：K——-1+—-2+—號(hào)+—4+ + —1+ 4S16碼字的平均信息傳輸率為成為-1R=^^一〔bit/碼K編碼效率11該二進(jìn)制對(duì)稱信道的概率轉(zhuǎn)移矩陣為11該二進(jìn)制對(duì)稱信道的概率轉(zhuǎn)移矩陣為f2/31/3]"1/32/3)若p(x0)=3/4,p(x1)=1/4,求H(X),H(X/Y),H(Y/X)和I(X;Y)。求該信道的信道容量及其達(dá)到信道容量時(shí)的輸入概率分布。(1)p(xO)=3M(1)p(xO)=3MP(m1)=1/433P(M)= ]2玳陌滬<33>H(XY>H(Y>iLcigC幻+'Log(4)+*LogfLZ)+fLo=1.73H(XY>H(Y>7 (12\—Log—=0.9S12I5J—Log—Log—=0.9S12I5JH(WY)=H(XY)-H(Y)=1.73-0.93=0.75H(Y/q=H(XY)-HQg=1.73-O.SH=0.919l(X:Y)=Hp)-H(X7YJ=0.gll-0.75=0.061TOC\o"1-5"\h\z1 (1X(勾C=log(Q)+EpijLog(pij)=Log(2)+-Log-+-Log-=0.0@2\3j3 技J\o"CurrentDocument"PW= =|12、某信源發(fā)送端有2個(gè)符號(hào)，xi,i=1,2,p(xi)=a,每秒發(fā)出一個(gè)符號(hào)。接收端有3種符號(hào)yj,j=1,2,3，轉(zhuǎn)移概率矩陣如下：\o"CurrentDocument"f1/21/2 0]p="1/21/41/4)

計(jì)算接收端的平均不確定度；計(jì)算由于噪聲產(chǎn)生的不確定度H(Y/X);計(jì)算信道容量解：(1)改1改1：=皿 F點(diǎn)：=1一口p(yi)=50■十!(1p(yi)=50■十!(1—oj—? p(必=接收端的不確定度為：/1 1"\H(Y)= —Log(2)-—och——-LogE A)- --上蘭Log(l+0G)-■-CL十_(1一心T-(L+- P(/3)= _(1-CC)2 4 4 4 4—-OCH 3時(shí)Log(l-此)H(Y/X)=：wLq或幻十偵就2)十口十;(1-a)L口或2)十^[1-a)L勺或愈十;U-叫)Lq§(4)1 QC2(3)l(X;Y)=H(Y)-H(Y%=住_1±±l理(1+時(shí)-土l哩(1-時(shí)]-仲-7A 4 J\22JC=m^I(X;Y)R)二0det得到1-hi(l十oc)十ln(l-cc)+2-]ri(Z)口城勾 "3得a:=-C=maM(X;Y)==0.15113發(fā)送端有3種等概率符號(hào)(x1,x2,x3),p(xi)=1/3,接收端收到3種符號(hào)(y1,y2,y3),05如3W信道轉(zhuǎn)移概率矩陣如下：忌:=040.30.3<0.10.90」（1） 求接收端收到一個(gè)符號(hào)后得到的信息量H（Y）;（2） 計(jì)算噪聲熵H（Y/X）;（3） 計(jì)算當(dāng)接收到端收到一個(gè)符號(hào)y2的錯(cuò)誤率；（4） 計(jì)算從接收端看的平均錯(cuò)誤率；（5） 計(jì)算從發(fā)送端看的平均錯(cuò)誤率；（6） 從轉(zhuǎn)移矩陣中你能看出信道的好壞嗎：（7） 計(jì)算發(fā)送端的H（X）和H（X/Y）。解：⑴<1￡廠1.2P610255f0.50.30.2?2 1 1213條件概率忠二040.30.3，聯(lián)合概率L510To，后驗(yàn)概率劉）=5 55<0.10.90」1 3 °13——U—-030LUJU05)TOC\o"1-5"\h\z1 1 1p(y。):=匚，p(yD:=匚，p(y10 \3J 10J 30 10 10 \3J 10J 30 10 A9)(3)當(dāng)接收為y2，發(fā)為x1時(shí)正確，如果發(fā)的是x1和x3為錯(cuò)誤，各自的概率為:,,、1 , ,、1 , ,、3P(x1/y2)=5，P(x2/y2)=5，P(x3/y2)=5其中錯(cuò)誤概率為：Pe=P(x1/y2)+P(x3/y2)=；+|=0.8平均錯(cuò)誤概率為 1 1 3 1 1 …r—+ F—H +—+—=0,73315 30 10 10 15 10（5） 仍為0.733（6） 此信道不好原因是信源等概率分布，從轉(zhuǎn)移信道來(lái)看正確發(fā)送的概率x1-y1的概率0.5有一半失真x2-y2的概率0.3有失真嚴(yán)重x3-y3的概率0完全失真（7）H(X)=Log(3r)=i.535H(Y)=-Log(^+-Log(2)+(今=1.4J92 6(2)1 1 1 2H(Y/X)=