信息論與編碼第2章習(xí)題解答

1、2.1設(shè)有12枚同值硬幣，其中一枚為假幣。只知道假幣的重量與真幣的重量不同，但不知究竟是重還是輕?，F(xiàn)用比較天平左右兩邊輕重的方法來測量（因無砝碼）。為了在天平上稱出哪一枚是假幣，試問至少必須稱多少次？解：分三組，每組4個，任意取兩組稱。會有兩種情況，平衡，或不平衡。 (1) 平衡：明確假幣在其余的4個里面。從這4個里面任意取3個，并從其余8個好的里面也取3個稱。又有兩種情況：平衡或不平衡。a）平衡：稱一下那個剩下的就行了。b）不平衡：我們至少知道那組假幣是輕還是重。從這三個有假幣的組里任意選兩個稱一下，又有兩種情況：平衡與不平衡，不過我們已經(jīng)知道假幣的輕重情況了，自然的，不平衡直接就知道誰是假

2、幣；平衡的話，剩下的呢個自然是假幣，并且我們也知道他是輕還是重。(2) 不平衡：假定已經(jīng)確定該組里有假幣時候：推論1：在知道該組是輕還是重的時候，只稱一次，能找出假幣的話，那么這組的個數(shù)不超過3。 我們知道，只要我們知道了該組（3個）有假幣，并且知道輕重，只要稱一次就可以找出來假幣了。從不平衡的兩組中，比如輕的一組里分為3和1表示為“輕（3）”和“輕（1）”，同樣重的一組也是分成3和1標(biāo)示為“重（3）”和“重（1）”。在從另外4個剩下的，也就是好的一組里取3個表示為“準(zhǔn)（3）”。交叉組合為： 輕（3） + 重（1） ？=？ 輕（1） + 準(zhǔn)（3）來稱一下。又會有3種情況： (1)左面輕：這說明

3、假幣一定在第一次稱的時候的輕的一組，因為“重（1）”也出現(xiàn)在現(xiàn)在輕的一邊，我們已經(jīng)知道，假幣是輕的。那么假幣在輕（3）里面，根據(jù)推論1，再稱一次就可以了。(2)右面輕：這里有兩種可能：“重（1）”是假幣，它是重的，或者“輕（1）”是假幣，它是輕的。這兩種情況，任意 取這兩個中的一個和一個真幣稱一下即可。(3)平衡：假幣在“重（3）”里面，而且是重的。根據(jù)推論也只要稱一次即可。2.2 同時扔一對骰子，當(dāng)?shù)弥皟慎蛔用娉宵c數(shù)之和為2”或“面朝上點數(shù)之和為8”或“骰子面朝上之和是3和4”時，試問這三種情況分別獲得多少信息量？解：設(shè)“兩骰子面朝上點數(shù)之和為2”為事件A，則在可能出現(xiàn)的36種可能中，只

4、能個骰子都為1，這一種結(jié)果。即：P（A）=1/36，I（A）= P（A）=365.17 比特設(shè)“面朝上點數(shù)之和為8”為事件B，則有五種可能：2、6；6、2；4、4；3、5；5、3；即：P（B）= 5/36，I（B）= P（B）= 36/52.85 比特設(shè)“骰子面朝上之和是3和4”為事件C，則有兩種可能：3、4；4、3；即： P（C）= 2/36，I（C）= P（C）= 36/24.17 比特2.3 如果你在不知道今天是星期幾的情況下問你的朋友“明天是星期幾？”則答案中含有多少信息量？如果你在已知今天是星期四的情況下提出同樣的問題，則答案中你能獲得多少信息量（假設(shè)已知星期一至星期日的排序）解：（

5、1）P1/7 ILog2PLog27（2）已知今天星期四，問明天是星期幾？ 即：明天是星期五是必然事件，不存在不確定性，I0。2.4地區(qū)的女孩中有25是大學(xué)生，在女大學(xué)生中有75是身高1.6米以上的，而女孩中身高1.6米以上的占半數(shù)一半。假如我們得知“身高1.6米以上的某女孩是大學(xué)生”的消息，問獲得多少信息量？解：設(shè)A為女大學(xué)生,B為1.6米以上的女孩則依題意有: , , 所以信息量為2.5一副充分洗亂了的牌（含52張牌），試問(1) 任一特定排列所給出的信息量是多少？(2) 若從中出去抽取13張牌，所給出的點數(shù)都不相同時得到多少信息量？解：（1）任一排列發(fā)生的概率為1/52!Ilog52!2

6、25.58 bit （2）13張牌點數(shù)都不相同發(fā)生的概率為1/413Ilog41326 bit2. 設(shè)離散無記憶信源=,其發(fā)出的消息為（032 ），求：（1）此消息的自信息是多少？（2）在此消息中平均每個符號攜帶的信息量是多少？ 解：(1) 因為離散信源是無記憶的，所以起發(fā)出的消息序列中各符號是無依賴且統(tǒng)計獨立的。因此，此消息的自信息就為該消息中各符號自信息之和。I（）= log P（） = log= 1.415 比特I（）= log P（）= log=2比特I（）= log P（）= log=2比特I（）= log P（）= log=3比特則此消息的自信息是： I=14I（）+ 13I（）+

7、12 I（）+ 6I（） 141.415+132+122+6387.81比特 (2)此消息中平均每個符號攜帶的信息量是： I=87.81451.95比特/符號2.7如有6行8列的棋型方格，若又二個質(zhì)點A和B，分別以等概率落入任一方格內(nèi)，他們的坐標(biāo)分別為（XA,YA）,(XB,YB),但A.B不能落入同一方格內(nèi)。（1）如僅有質(zhì)點A，求A落入任一個格的平均自信息量是多少？（2）若已知A已落入，求B落入的平均自信息量。（3）若A,B是可分辨的，求A,B同都落入的平均自信息量。解:(1) H(XA)=log24(2) H(XB/XA)=24 (3) H(XAXB)=24*23*log(*)=log24

8、*23=log23+log242.8 從大量統(tǒng)計資料知道，男性中紅綠色盲的發(fā)病率為7，女性發(fā)病率為0.5，如果你問一位男同志：“你是否是紅綠色盲？”他的回答可能是“是”，可能是“否”，問這二個答案中各含多少信息量？平均每個回答中含有多少信息量？如果你問一位女同志，則答案中含有的平均自信息量是多少？解：（1） 若男同志回答“是”：Ilog(1/7%)3.84 bit 回答“否”：Ilog(1/93%)0.1 bit 平均信息量為：I7%log7%93%log93%0.36 bit （2） 若問女同志，平均信息量為：I0.5%log0.5%99.5%log99.5%0.045 bit2.9設(shè)信源求

9、這信源的熵，并解釋為什么，不滿足信源熵的極值性。解：信源的熵為：bit/符號 是因為此信息的,不滿足信息熵極值性的條件。2.10設(shè)離散無記憶信源S其符號集Aa1,a2,.,aq,知其相應(yīng)的概率分布為（P1,P2,.,Pq）。設(shè)另一離散無記憶信源S， 其符號集為S信源符號集的兩倍，A=aii=1,2,.,2q,并且各符號的概率分布滿足：Pi=(1-)Pi (i=1,2,.,q)Pi=Pi-q (i=q+1,q+2,.,2q)試寫出信源S信息熵與信源S的信息熵的關(guān)系。解：S： a1 a2 aq P：p1 p2 pqH（X）qi1PiLogPiqi1Pi1S：a1 a2 aq aq1a2q P ：p

10、，1 p，2p，qp，q1p，2qH（X）2qi1P，iLogP，i qi1P，iLogP，i2qiq1P，iLogP，i qi1（1）PiLog（1）LogPi2qiq1Piq（LogLogPiq） （1）qi1PiLog（1）（1）qi1PiLogPi2qiq1PiqLog2qiq1PiqLogPiq （1）qi1PiLogPi2qiq1PiqLogPiq（1）Log（1）qi1PiLog2qiq1Piq （1）qi1PiLogPiqj1PjLogPj（1）Log（1）qi1PiLogqj1Pjqi1PiLogPi（1）Log（1）Logqi1PiH（X）（1）Log（1）Logqi1Pi

11、H（X）（1）Log（1）Log即：H,（X）H（X）（1）Log（1）Log2.13 （1）為了使電視圖象獲得良好的清晰度和規(guī)定的適當(dāng)?shù)膶Ρ榷?，需要?*105個象素和10個不同的亮度電平，求傳遞此圖象所需的信息率（比特/秒）。并設(shè)每秒要傳送30幀圖像，所有象素是獨立變化，且所有亮度電平等概率出現(xiàn)。 （2）設(shè)某彩電系統(tǒng)，除了滿足對于黑白電視系統(tǒng)的上述要求外，還必須有30個不同的色彩度，試證明傳輸這彩色系統(tǒng)的信息率要比黑白系統(tǒng)的信息率約大2.5倍。解：（1）因為每幀圖象可以看成是離散的數(shù)字圖象，每個像素的亮度是隨機(jī)而且等概率出現(xiàn)的，則每個像素亮度信源的概率空間為：= =1每個像素亮度含有的信息

12、量為：H(X)=log2103.32比特/像素=1哈特/像素現(xiàn)在，所有的像素是獨立變化的，則每幀圖象可以看成是離散亮度信源的無記憶N次擴(kuò)展信源。故，每幀圖象含有的信息量是：H(XN)=NH(X)=5105log10=5105哈特/幀1.66106比特/幀而每秒傳送30幀圖象，則傳遞這個圖象所需要的信息率為R1=30H(XN)=1. 5106哈特/秒4.98107比特/秒（2）證明：每個像素具有10個不同的亮度和30個色彩度。由上面的計算得亮度等概率出現(xiàn)的情況下，每個像素含有的信息量是：H(X)=log2103.32比特/像素。每個像素的色彩度也是等概率出現(xiàn)的，則色彩度信源的概率空間為：= =1

13、每個像素色彩度含有的信息量：H(Y)=log2304.91比特/像素而亮度和色彩度是相互獨立的，所以亮度和色彩度同時出現(xiàn)，每像素含有的信息量：H(XY)=H(X)+H(Y)=log10+log30=log3008.23比特/像素如果每幀所用的像素數(shù)和每秒傳送的幀數(shù)都相同的情況下，傳輸這彩色系統(tǒng)的信息率與傳輸黑白系統(tǒng)的信息率之比就等于彩色系統(tǒng)每像素含有的信息量與黑白系統(tǒng)每像素含有的信息量之比： =2.5證畢。2.14每幀電視圖像可以認(rèn)為是由3105個像素組成,所以像素均是獨立變化,且每一像素又取128個不同的亮度電平,并設(shè)亮度電平等概率出現(xiàn).問每幀圖像含有多少信息量?現(xiàn)有一廣播員在約10000個

14、漢字的字匯中選1000個字來口述此電視圖像,試問廣播員描述圖像所廣播的信息量是多少(假設(shè)漢字字匯是等概率分布,并彼此無依賴)?若要恰當(dāng)?shù)孛枋鰣D像,廣播員在口述中至少需要多少漢字?解: 亮度電平等概率出現(xiàn)每個像素所含的信息量為 H(X)=log 128=7 bit/像素. 而每個像素均是獨立變化的 每幀電視圖像所包含的信息量為 H(X)= 3105H(X)= 2.1106bit 假設(shè)漢字字匯是等概率分布 每個漢字出現(xiàn)的概率均為從而每個漢字?jǐn)y帶的信息量為log 10000=13.2877 bit/字 漢字間彼此無依賴, 廣播員口述的1000個漢字所廣播的信息量為100013.2877=13287.

15、7 bit若要恰當(dāng)?shù)孛枋鰣D像,廣播員在口述中至少需要的漢字?jǐn)?shù)為15841個漢字。2.15 為了傳輸一個由字母A、B、C、D組成的符號集，把每個字母編碼成兩個二元碼脈沖序列，以00代表A，01代表B，10代表C，11代表D。每個二元脈沖寬度為5ms。（1）不同字母等概率出現(xiàn)時，計算傳輸?shù)钠骄畔⑺俾?？?）若每個字母出現(xiàn)的概率分別為pA=1/5,pB=1/4,pC=1/4,pD=3/10，試計算傳輸?shù)钠骄畔⑺俾?？解：?）由題可知，當(dāng)不同字母等概率出現(xiàn)時，平均自信息量為： H(x)=log4=2(比特/字母) 又因為每個二元脈沖寬度為5ms,故一個字母的脈沖寬度為10ms 則字母的傳輸速率為

16、100字母/秒 故傳輸?shù)钠骄畔⑺俾蕿椋?00 比特/秒 (2) 當(dāng)每個字母分別以題中的概率出現(xiàn)時，平均自信息量為： H(x)=P(ai)logP(ai)=(1/5)*log5+2*(1/4)*log4+(3/10)*log(10/3)=1.98(比特/字母) 同樣字母的傳輸速率為 100個/秒 故傳輸?shù)钠骄畔⑺俾蕿椋?98 比特/秒2.18 設(shè)有一個信源,它產(chǎn)生0,1序列的消息.它在任意時間而且不論以前發(fā)生過什么符號,均按P(0)=0.4,P(1)=0.6的概率發(fā)出符號.(1) 試問這個信源是否平穩(wěn)的?(2) 試計算H(X2),H(X3|X1X2)及.(3) 試計算H(X4)并寫出X4信源

17、中可能有的所有符號.解：(1) 因為信源發(fā)出符號的概率分布與時間平移無關(guān),而且信源發(fā)出的序列之間也是彼此無依賴的.所以這個信源是平穩(wěn)信源,是離散無記憶信源. (2) ,計算H(X)0.971 bit/符號 因為信源是平穩(wěn)無記憶信源,所以H(X2)=2H(X)1.942 bit/兩個符號 H(X3|X1X2)=H(X3)=H(X)0.971 比特/符號 =H(X)0.97 bit/符號 (3) H(X4)=4H(X)3.884 bit/四個符號 可能的所有16個符號:0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100

18、1101 1110 11112.19 有一個元無記憶信源，其發(fā)0的概率為p，而p約等于1，所以在發(fā)出的二元序列中經(jīng)常出現(xiàn)的是那些一串為0的序列（稱為高概率序列）。對于這樣的信源我們可以用另一新信源來代替，新信源中只包含這些高概率序列。這時新信源Sn=S1 , S2 , S3 , , Sn , Sn+1,共有n+1個符號，它與高概率的二元序列的對應(yīng)關(guān)系如下：二元序列：001,01,0001,1 ,0001(n位),00000(n位)新信源符號：S3,S2, S4, S8, S1, Sn, Sn+1(1) 求H（Sn）(2) 當(dāng) 時求信源的熵解：依題意，因為是二元無記憶信源，在發(fā)出的二元序列中符號

19、之間彼此是無依賴的，統(tǒng)計獨立的，所以有： 1, 2由此可得新信源Sn為：證明滿足完備性： 因為 所以，則：2.21有一信源，它在開始時以P(a)=0.6,P(b)=0.3,P(c)=0.1的概率發(fā)出X1。如果X1為a時，則X2為a、b、c的概率為1/3；如果X1為b，X2為a、b、c的概率為1/3；如果X1為c，X2為a、b的概率為1/2，為c的概率為0，而且后面發(fā)出Xi的概率只與Xi-1有關(guān)，又P(Xi|Xi-1)=P(X2|X1) i3。是利用馬爾可夫信源的圖示法畫出狀態(tài)轉(zhuǎn)移圖，并計算信源熵H。解：由題可得，狀態(tài)轉(zhuǎn)移圖為：a:0.6b:0.3c:0.1b:1/2a:1/2c:1/3a:1/

20、3c:1/3a:1/3b:1/3b:1/3abcabcabcaE0E1E2E3E4E5E6E7E8E9E10E11b可見，狀態(tài)E1和E4、E7、E10的功能是完全相同的， 狀態(tài)E2和E5、E8、E11的功能是完全相同的，狀態(tài)E3和E6、E12的功能是完全相同的。其中E0是過渡狀態(tài)，而E1、E2、E3組成一個不可約閉集，具有遍歷性。故有如下的狀態(tài)轉(zhuǎn)移圖A;由于此馬爾可夫信源的狀態(tài)必然會進(jìn)入這個不可約閉集，所以計算信源熵時，可以不考慮過渡狀態(tài)和過渡過程。由此，可得狀態(tài)E1、E2、E3的極限概率：Q(E1)=1/3Q(E1)+1/3Q(E2)+1/2Q(E3)Q(E2)=1/3Q(E1)+1/3Q(

21、E2)+1/2Q(E3)Q(E3)=1/3Q(E1)+1/3Q(E2)Q(E1)+Q(E2)+Q(E3)=1可得： Q(E1)=Q(E2)=3/8， Q(E3)=1/4c:1/3c:1/3b:1/2b:1/3c:0.1b:0.3a:0.6c:1/3b:1/2a:1/3E2E3E0E1a:1/3圖A所以H=H2=Q(E1)H(1/3,1/3,1/3)+Q(E2)H(1/3,1/3,1/3)+Q(E3)H(1/2,1/2) =1.4388(比特/符號)2.22 一階馬爾可夫信源的狀態(tài)圖如圖2.8所示，信源X的符號集為并定義。(1) 求信源平穩(wěn)后的概率分布；(2) 求此信源的熵；(3) 近似認(rèn)為此信

22、源為無記憶時，符號的概率分布等于平穩(wěn)分布。求近似信源的熵并與進(jìn)行比較；(4) 對一階馬爾可夫信源取何值時取最大值，又當(dāng)時結(jié)果如何？解：（1），由圖可得于是得到整理計算得即（2） 據(jù)一階馬爾可夫信源的熵的表達(dá)式可得（3） 信源近似為無記憶信源，符號的概率分布等于平穩(wěn)分布，則此信源得到： 由此計算結(jié)果可知 （4） 求一階馬爾可夫信源的最大值。因為求其對p的一階導(dǎo)數(shù)令，得，所以，所以時，達(dá)到最大值；的最大值等。當(dāng)時當(dāng)時由此可以看出上面的結(jié)論時正確的。2.23 一階馬爾可夫信源的狀態(tài)圖如圖2.9所示，信源X的符號集為0,1,2。（1） 求平穩(wěn)后信源的概率分布。（2） 求信源的熵H。（3） 求當(dāng)p=0和

23、p=1時信源的熵，并說明其理由。ppp10pp2p解：（1）由圖可知一階馬爾可夫信源的狀態(tài)空間E=A=0,1,2.平穩(wěn)后信源的概率分布就等于一階馬爾可夫信源狀態(tài)的極限分布，即Q(Ei)P(ai) i1,2,3EiE,aiA,而EA從狀態(tài)圖中分析可知，這三個狀態(tài)都是正規(guī)常返態(tài)，所以此馬爾可夫鏈具有各態(tài)歷經(jīng)性，平穩(wěn)后狀態(tài)的極限分布存在?？傻脿顟B(tài)一步轉(zhuǎn)移矩陣 得Q(0)Q(1)Q(2)1/3則可得 P(0)P(1)P(2)1/3(2) 一階馬爾可夫信源的熵 HH2I=13Q(Ei)H(XEi) P(0)H(XE)+P(1)H(X1)+P(2)H(X2) 1/3H(P1,0,P)+1/3H(P,P1,

24、0)+1/3H(0,P,P1) -P1P1-PP H(P)(3) 當(dāng)P0 ,H0 當(dāng)P1 ,H1因為信息熵是表示信源的平均不確定性，題中當(dāng)P=1或P=0時表明信源從某一狀態(tài)出發(fā)轉(zhuǎn)移到另一狀態(tài)的情況是一定發(fā)生或一定不發(fā)生，即是確定的事件。當(dāng)P=1時，從0狀態(tài)一定轉(zhuǎn)移到2狀態(tài)，2狀態(tài)一定轉(zhuǎn)移到1狀態(tài)，1狀態(tài)一定轉(zhuǎn)移到0狀態(tài)。所以不論從何狀態(tài)起信源輸出的序列一定是序列，完全確定的。當(dāng)P=0時，0狀態(tài)永遠(yuǎn)處于0狀態(tài)，1狀態(tài)永遠(yuǎn)處于1狀態(tài)，2狀態(tài)用于處于2狀態(tài)。信源輸出的符號序列也是確定的。所以當(dāng)P=1或P=0時，信源輸出什么符號不存在不確定性，完全是確定的，因此確定信源的信息熵等于零。2.24 設(shè)有一

25、個馬爾可夫信源,它的狀態(tài)集為s1,s2,s3,符號集為a1,a2,a3,及在某狀態(tài)下發(fā)符號的概率為P(ak|si)(i,k=1,2,3),如下圖所示.S1S2S3a1:a2:a2:a3:a3:a1:1(1) 求出圖中馬爾可夫信源的狀態(tài)極限概率并找出符號的極限概率(2) 計算信源處在某一狀態(tài)下輸出符號的條件熵H(sj)(j=1,2,3).(3) 求出馬爾可夫信源熵H. 解: (1) 此信源的狀態(tài)集不等于符號集,從狀態(tài)轉(zhuǎn)移圖可知P(a1|s1)=1/2, P(a1|s1)=0, P(a1|s3)=1P(a2|s1)=1/4, P(a2|s2)=1/2, P(a2|s3)=0P(a3|s1)=1/4

26、, P(a3|s2)=1/2, P(a3|s3)=0狀態(tài)轉(zhuǎn)移概率為P(s2|s1)= P(a1|s1)+ P(a2|s1)=3/4 P(s3|s1)= P(a3|s1)=1/4P(s1|s1)=0P(s1|s2)= 0P(s2|s2)= P(a2|s2)=1/2P(s3|s2)= P(a3|s2)=1/2P(s1|s3)= P(a1|s3)=1P(s2|s3)= P(a2|s3)=0P(s3|s4)= P(a3|s3)=0得狀態(tài)轉(zhuǎn)移矩陣: P=從圖可知 此狀態(tài)馬爾可夫鏈?zhǔn)菚r齊的,狀態(tài)數(shù)有限的和是不可約閉集,所以其具有各態(tài)歷經(jīng)性,平穩(wěn)后狀態(tài)的極限概率分布存在.得到如下方程組：Q(s1)= Q(s3)Q(s2)=3/4 Q(s1)+1/2 Q(s2)Q(s3)=1/4 Q(s1)+1/2 Q(s2)Q(s1)+ Q(s2)+ Q(s3)=1解得： Q(s1)=2/7, Q(s2)=2/7, Q(s3)=3/7符號的極限概率 P(ak) =所以P(a1)=Q(s1)P(a1|s1)+ Q(s2)P(a1|s2)+ Q(s3)P(a1|s3)=3/7,P(a2)=2/7, P(a3)=2/7(2) 信源處于某一狀態(tài)下的輸出符號的條件熵 H(X|sj)= - j=1,2,3H(X|s1)= - P(a1|s1)log P(a1|s1) - P(a2|s1)log