信息論與編碼理論-習(xí)題答案_姜楠_王健_編著_清華大學(xué)

1、第1章 緒論1.1 信源、編碼器、信道、干擾、譯碼器、信宿1.2 香農(nóng)1.3 通信系統(tǒng)模型1.4 信號是消息的表現(xiàn)形式，是物理的，比如電信號、光信號等。消息是信息的載荷者，是信號的具體內(nèi)容，不是物理的，但是又比較具體，例如語言、文字、符號、圖片等。信息包含在消息中，是通信系統(tǒng)中被傳送的對象，消息被人的大腦所理解就形成了信息。1.5 略第2章 信息的統(tǒng)計度量2.1 少2.2 y的出現(xiàn)有助于肯定x的出現(xiàn)、y的出現(xiàn)有助于否定x的出現(xiàn)、x和y相互獨(dú)立2.3 FTTTF2.4 2.12比特2.5 依題意，題中的過程可分為兩步，一是取出一枚硬幣恰好是重量不同的那一枚，設(shè)其發(fā)生的概率為，由于每枚硬幣被取出的

2、概率是相同的，所以所需要的信息量二是確定它比其他硬幣是重還是輕，設(shè)其發(fā)生的概率為，則總的概率所需要的信息量2.6 設(shè)表示“大學(xué)生”這一事件，表示“身高1.60m以上”這一事件，則故2.7 四進(jìn)制波形所含的信息量為，八進(jìn)制波形所含信息量為，故四進(jìn)制波形所含信息量為二進(jìn)制的2倍，八進(jìn)制波形所含信息量為二進(jìn)制的3倍。2.8故以3為底的信息單位是比特的1.585倍。2.9 （1）J、Z（2）E（3）X2.10 （1）兩粒骰子向上面的小圓點(diǎn)數(shù)之和為3時有(1, 2)和(2, 1)兩種可能性，總的組合數(shù)為，則圓點(diǎn)數(shù)之和為3出現(xiàn)的概率為故包含的信息量為（2）小圓點(diǎn)數(shù)之和為7的情況有(1, 6), (6, 1

3、), (2, 5), (5, 2), (3, 4), (4, 3)，則圓點(diǎn)數(shù)之和為7出現(xiàn)的概率為故包含的信息量為2.11 對于男性，是紅綠色盲的概率記作，不是紅綠色盲的概率記作，這兩種情況各含的信息量為平均每個回答中含有的信息量為對于女性，是紅綠色盲的概率記作，不是紅綠色盲的概率記作，則平均每個回答中含有的信息量為所以2.12 天平有3種狀態(tài)，即平衡，左重，左輕，所以每稱一次消除的不確定性為，12個球中的不等重球（可較輕，也可較重）的不確定性為：，因為,所以3次測量可以找出該球。2.13 （1）當(dāng)最后3場比賽麥克勝的次數(shù)比大衛(wèi)多時，麥克最終才能勝，因此同理麥克最終比賽結(jié)果的熵為因為勝、負(fù)、平這

4、3種結(jié)果接近等概，所以該隨機(jī)變量的熵接近最大熵。（2）假定大衛(wèi)最后3場比賽全部獲勝，那么麥克也必須全部獲勝最后3場比賽最終才能得平，否則就是負(fù)。麥克3場比賽全部獲勝的可能性是，因此在假定大衛(wèi)最后3場比賽全部獲勝的情況下麥克的最終比賽結(jié)果的條件熵是2.14 （1）假定一個家庭里有個女孩，1個男孩，相應(yīng)的概率是，因此女孩的平均數(shù)是，女孩的平均數(shù)和男孩的平均數(shù)相等。（2）2.15 （1）根據(jù)題意，可以得到： 由式可以得到： 將式代入式得到： 由于的取值必須在0到1之間，由式和式可以得到的取值范圍在0.9到0.95之間。(2)就業(yè)情況的熵為它在的取值范圍內(nèi)的曲線如圖所示。（3）當(dāng)時，達(dá)到最大值，這時，

5、。2.16 假設(shè)表示當(dāng)?shù)氐膶嶋H天氣情況，表示氣象臺預(yù)報的天氣情況，表示總是預(yù)報不下雨的天氣情況。，可見氣象臺預(yù)報的確實不好。但是如果總是預(yù)報不下雨的話則會更糟，因為和是相互獨(dú)立的兩個隨機(jī)變量，即，所以因此氣象臺的預(yù)報準(zhǔn)確率雖然比總是預(yù)報不下雨低，但還是傳遞了一些信息，消除了一些不確定性。2.17 由互信息量的定義因為，則有同理，因為，則有2.18 （1）根據(jù)熵的極值性，當(dāng)隨機(jī)變量等概分布時，隨機(jī)變量的熵最大。有7個可能取值的隨機(jī)變量的最大熵為，隨機(jī)變量不是等概分布，所以。（2）根據(jù)熵的遞增性，。（3）（4）因為隨機(jī)變量是的函數(shù)，所以2.19 假定為最大的概率。根據(jù)熵函數(shù)的性質(zhì)，如果，則熵小于2

6、；如果，則只有一種可能：。如果，則有無數(shù)個解，其中之一為；如果，則沒有解。2.202.21第3章 離散信源3.1 p(x2)3.2 53.3 13.4 23.5 （1）87.81bit（2）1.95bit3.6 Hmax(X)=13.7 （1）消息符合的平均熵（2）自信息量為（3）（2）中的熵為3.8 因為邊沿分布條件分布概率如下：01209/111/8012/113/42/9201/87/9所以信息熵：條件熵：聯(lián)合熵：或可知解釋：（1）信源的條件熵比信源熵少這是由符號之間的相互依存性造成的。（2）聯(lián)合熵表示平均每兩個信源符號所攜帶的信息量。平均每一個信源符號所攜帶的信息量近似為因此原因：略去

7、了和之間的依賴性。3.9 由定義，信源的熵信源的概率分布要求滿足，而此題中。即各種可能發(fā)生的情況下，概率之和大于“1”。在實際情況下這是不可能發(fā)生的。3.10 由題意可知，聯(lián)合概率分布為X Y10101/40101/421/41/4X Y20101/4011/40201/2Y的分布為Y101P(y1)1/21/2Y201P(y2)1/21/2所以由于所以，第二個實驗好。3.11 由定義由于一階馬爾科夫信源之間的相關(guān)性，導(dǎo)致熵減小。3.12 （1）一階馬爾可夫過程的狀態(tài)轉(zhuǎn)移圖如圖所示。一階馬爾可夫過程共有3種狀態(tài)，每個狀態(tài)轉(zhuǎn)移到其他狀態(tài)的概率均為，設(shè)狀態(tài)的平穩(wěn)分布為，根據(jù)可得，3種狀態(tài)等概率分布

8、。一階馬爾可夫信源熵為信源剩余度為（2）二階馬爾可夫信源有9種狀態(tài)（狀態(tài)轉(zhuǎn)移圖略），同樣列方程組求得狀態(tài)的平穩(wěn)分布為二階馬爾可夫信源熵為信源剩余度為由于在上述兩種情況下，3個符號均為等概率分布，所以信源剩余度都等于0。3.13 （1）由題中條件，該信源是離散無記憶信源，對任意和，其中為中0的個數(shù)。故該信源是平穩(wěn)的。（2）由離散無記憶信源的擴(kuò)展信源的性質(zhì)（3）可能發(fā)出的符號有0000，0001，0010，0011，0100，0101，0110，0111，1000，1001，1010，1011，1100，1101，1110，1111。3.14 狀態(tài)轉(zhuǎn)移矩陣故該馬爾科夫信源是遍歷的。設(shè)由即求得所以信

9、源熵為狀態(tài)轉(zhuǎn)移圖略。3.15 （1）狀態(tài)轉(zhuǎn)移矩陣則有可得整理得（2）信源的熵其中狀態(tài)極限概率整理得所以，此信源的熵（3）信源無記憶，符號的概率分布等于平穩(wěn)分布。所以經(jīng)比較，可得到。（4）一階馬爾科夫信源的極值當(dāng)且僅當(dāng)時成立。當(dāng)時，；當(dāng)時，3.16 （1）狀態(tài)轉(zhuǎn)移矩陣由解得整理得，平穩(wěn)后信源的概率分布（2）求信源熵。先求狀態(tài)極限概率又因為可得信源的熵（3）求或時的時時，即信源熵表示的是信源的平均不確定性。此題中和表明某一狀態(tài)轉(zhuǎn)化到另一狀態(tài)的情況一定發(fā)生或一定不發(fā)生，即是確定事件，平均不確定性為零，即信源的熵為零。3.17 可知消息的極大熵，此信源的極限熵為由冗余度計算公式得3.18 （1）由一步

10、轉(zhuǎn)移概率矩陣與二步轉(zhuǎn)移概率矩陣的公式得（2）設(shè)平穩(wěn)狀態(tài)，馬爾可夫信源性質(zhì)知，即求解得穩(wěn)態(tài)后的概率分布3.19 設(shè)狀態(tài)空間S=，符號空間且一步轉(zhuǎn)移概率矩陣狀態(tài)轉(zhuǎn)移圖設(shè)平穩(wěn)狀態(tài)，由馬爾可夫信源性質(zhì)有即可得馬爾可夫鏈只與前一個符號有關(guān)，則有3.20 消息元的聯(lián)合概率是求得一階馬爾可夫信源的不確定性為3.21 組成的字如下：這種簡單語言平均每個碼字的長度為則平均每個字符攜帶的信息量為所以，其冗余度為3.22 擲次錢幣就使其正面向上的概率為則有第4章 離散信道4.1 （1） （2）（3） （4）4.2 假設(shè)輸入符號取值；輸出符號。且。其中，表示單個符號的無差錯傳輸概率，表示單個符號傳輸?shù)腻e誤概率。信道轉(zhuǎn)

11、移關(guān)系如圖所示。則傳遞概率為并且則信道傳遞矩陣為4.3 信道如圖所示其轉(zhuǎn)移矩陣為這是一個準(zhǔn)對稱信道，信道容量為比特/符號4.4 按定理解釋：（1）此信道每個符號平均能夠傳輸?shù)淖畲笮畔?.0817bit。（2）只有當(dāng)信道輸入符號是等概率分布才能達(dá)到這個最大值。4.5 信道傳遞矩陣為又知所以有故平均互信息量4.6 (1)三元對稱理想（無噪聲）信道的信道模型如圖所示。(2)三元對稱強(qiáng)噪聲信道模型如圖所示。4.7 由圖可知信道1、2的信道矩陣分別為它們串聯(lián)后構(gòu)成一個馬爾科夫鏈，根據(jù)馬氏鏈的性質(zhì)，串聯(lián)后總的信道矩陣為4.8 傳遞矩陣為輸入信源符號的概率分布可以寫成行向量形式，即由信道傳遞矩陣和輸入信源

12、符號概率向量，求得輸出符號概率分布為輸入符號和輸出符號的聯(lián)合概率分布為（1）（2）（3）信源和信源的信息熵（4）信道疑義度 (貌似不對)噪聲熵 （和上者相調(diào)）（5）平均互信息4.9 根據(jù)公式求互信息量，而故應(yīng)求。（1）求聯(lián)合概率（2）求邊沿概率（3）求后驗概率（4）求熵4.10 信道傳輸矩陣如下：可以看出這是一個對稱信道，那么信道容量為4.11 先求輸入端須傳輸?shù)男畔⒘吭偾筝敵龆藘?nèi)傳出的信息量。要求信道傳出的信息量，必須先求信道容量。由 知所以信道容量為，對信道而言內(nèi)共傳輸?shù)姆枖?shù)為15000個。所以輸出端傳出的信息量為，顯然內(nèi)傳出端無法得到輸入序列的全部信息。4.12 （1）信道為準(zhǔn)對稱信道

13、，輸入等概率分布時達(dá)到信道容量，即。設(shè)輸入為計算輸出得所以（2）信道仍為準(zhǔn)對稱信道，輸入等概率分布時達(dá)到信道容量，即。設(shè)輸入為計算輸出得所以比較兩信道容量，得4.13 依題意，阻值的概率空間為功率的概率空間由題意知再設(shè)則由,得又所以通過測阻值可以得到關(guān)于瓦數(shù)的平均信息量為0.187bit。4.14 （1）,由信道傳輸矩陣與信道的傳輸符號的概率分布得到信道輸入與輸出的聯(lián)合分布矩陣為有邊緣概率輸出符號熵為條件熵為（2）顯然。4.15 （1）由信道1的轉(zhuǎn)移概率矩陣可知其為對稱信道所以因為所以有信息熵?fù)p失，信道有噪聲。（2）由信道2的轉(zhuǎn)移概率矩陣可知其為準(zhǔn)對稱信道，輸入為等概分布時達(dá)到信道容量。令此時

14、的輸出分布為所以因為所以信道2無噪聲。4.16 因為是二元對稱信道，根據(jù)信源概率分布：，信道傳輸概率： 得到輸出符號概率分布根據(jù)互信息量的定義，有4.17 （1）這是一個錯誤傳遞概率為0.08的二元對稱信道，它的信道容量為（2）每次顧客點(diǎn)菜時提供的信息為（3）由于需要傳遞的信息量小于信道容量，因此在這個信道上可以正確傳遞顧客點(diǎn)菜的信息。第5章 連續(xù)信源和連續(xù)信道5.1 略5.25.3 略5.4 略第6章 無失真信源編碼6.1 16.2 信源序列6.3 （1）唯一可譯碼有：，。（2）即時碼有：，（3）同理得6.4 1（1）此碼的碼長滿足Kraft-McMillan不等式:（2）根據(jù)碼樹圖可知，此

15、碼是即時碼；（3）由于此碼是即時碼，所以它也是唯一可譯碼。2（1）此碼滿足Kraft-McMillan不等式：（2）此碼不是即時碼，因為碼字00是碼字000的前綴；（3）此碼不是唯一可譯碼，因為碼符號序列000000可以譯碼為00，00，00，也可以譯碼為000，000。3（1）此碼滿足Kraft-McMillan不等式：（2）根據(jù)碼樹圖可知，此碼是即時碼；（3）由于此碼是即時碼，所以它也是唯一可譯碼。4（1）此碼不滿足Kraft-McMillan不等式：（2）因為不滿足Kraft-McMillan不等式，所以此碼不是即時碼；（3）因為不滿足Kraft-McMillan不等式，所以此碼不是唯一

16、可以碼。501，111，011，00，010，110（1）此碼不滿足Kraft-McMillan不等式：（2）此碼不是即時碼，因為碼字01是碼字011的前綴；（3）此碼是唯一可譯碼。根據(jù)唯一可譯碼判決準(zhǔn)則，我們構(gòu)造以下的尾隨后綴序列：6.5 （1）（2）（3）對二重延長消息采用費(fèi)諾方法編碼，結(jié)果為平均碼長：平均信息傳輸速率碼元0和1的概率分別為（4）對三重延長消息采用霍夫曼方法編碼，結(jié)果為平均碼長：平均信息傳輸速率碼元0和1的概率分別為6.6 由香農(nóng)第一定理知顯然當(dāng)時此時的信息傳輸率為編碼后原信源變換成一個新的信源新信源的信道容量，且在輸入信源等概率時達(dá)到此容量。由式知，經(jīng)過霍夫曼編碼后，信心

17、傳輸率達(dá)到信道容量，很難推出此時的信源趨于等概分布，即=。6.7 （1）至少需要二位二進(jìn)制碼元來發(fā)送4個等概發(fā)生的信息晴00，云01，雨10，霧11（2）4個消息的概率恰好是2的負(fù)整數(shù)次冪，根據(jù)得晴2位，云3位，雨3位，霧1位（3）采用霍夫曼方法得霧0，晴10，云110，雨111它們的平均碼長分別為：第一種情況：第二種情況：6.8 （1）采用霍夫曼編碼方法得到最佳二元碼為平均碼長：編碼效率（2）仍采用霍夫曼編碼方法求得最佳三元碼平均碼長：編碼效率6.9 （1）采用霍夫曼方法進(jìn)行編碼，得平均碼長：信源熵為編碼效率（2）霍夫曼編碼后平均碼長：信源熵為編碼效率（3）同理可得的最佳二元碼，計算平均碼長

18、和編碼效率。具體步驟略。6.10 霍夫曼編碼的結(jié)果為：平均碼長：信源熵為平均信息傳輸速率6.11 （1）0，10，11是概率分布1/2,1/4,1/4的Huffman編碼。（2）00，01，10，110可以被改進(jìn)為00，01，10，11而不喪失其即時可譯性，因此原碼不是最佳碼，因此也就不是一個Huffman編碼。另外，此碼中最長的碼長只有一個碼字，這也和Huffman編碼的特性不符。（3）01，10可以被改進(jìn)為0，1而不喪失其即使可譯性，因此原碼不是最佳碼，也就不是一個Huffman編碼。6.12 4位6.13 （1）不存在（2）存在0，1，20，21，220，221，222（3）不存在6.1

19、4 對灰度0，4，5，6，7編碼為10，0，2，11，12，6.15 碼0，010是唯一可譯碼，但是它既不滿足前綴條件也不滿足后綴條件。換句話說，在這個碼中，某些碼字是另外一些碼字的前綴，并且某些碼字是另外一些碼字的后綴。6.16 （1）我們將品嘗次數(shù)看作碼字的碼長，由于只能依次品嘗每一瓶酒，所以對于這個題目而言碼長只能是1，2，3，4，4這樣的分布，所需的平均品嘗次數(shù)就是平均碼長，想要使得平均碼長最小，則應(yīng)該將較短的碼長安排給概率較大的符號，因此所需的最小平均品嘗次數(shù)為（2）應(yīng)該首先品嘗概率為1/3的那瓶酒。（3）這個問題可以轉(zhuǎn)化為求取此概率分布的Huffman編碼，如圖所示品嘗時首先將第一

20、比特為0的酒混合起來品嘗，分出好壞后再按照第二比特來混合，直到找到壞酒，因此品嘗的平均次數(shù)為（4）根據(jù)上述編碼，首先應(yīng)該品嘗第一和第二瓶酒的混合，或者第三，四，五瓶酒的混合。由于Huffman編碼不是唯一的，所以還存在另外的方案，其對應(yīng)的編碼如下：概率1/31/41/61/61/12碼字001011010011在這種方案的指導(dǎo)下，首先應(yīng)該品嘗第一、四、五瓶酒的混合。6.17 序列SF(S)p(S)碼長碼字計算過程Æ01-b0.30.7-F(Æb)F(Æ)+p(Æ)F(b)0+1*0.3=0.3bb0.510.49-p(bb)p(b)p(b)0.7*0.7

21、0.49bba0.510.147-F(bba)F(bb)+p(bb)F(a)0.51+0.49*00.51bbaa0.510.0441510001F(bbaa)F(bba)+p(bba)F(a)0.51+0.147*00.51p(bbaa)p(bba)p(a)0.147*0.30.0441(0.51)10=(0.100000)2因此碼字為10001第7章 限失真信源編碼7.1 e7.2 大于7.3 相關(guān)性7.4 （1）在題設(shè)失真度定義下，失真矩陣是一個方陣，并有是階矩陣。（2）以二進(jìn)制信源為例信源符號集 接收符號集 其失真矩陣為7.5 在這種情況下，意味著若把信源信號再現(xiàn)為刪除信號時，其失真程

22、度要比再現(xiàn)為其他接收符號的失真程度少一半。以二進(jìn)制刪除信源為例，此時,則失真度為失真矩陣為7.6 （1）信源，每秒鐘發(fā)出2.66個信源符號。此信源的熵信源輸出的信息傳輸速率將此信源輸出符號送入二元無噪無損信道中進(jìn)行傳輸，此信道每秒鐘只傳送兩個二元符號。此信道的最大信息傳輸速率因為根據(jù)有噪信道編碼定理（香農(nóng)第二定理），不論進(jìn)行任何編碼此信源都不可能在此信道中實現(xiàn)無錯誤地傳輸，所以信源在此信道中傳輸會引起錯誤和失真。（2）若此信源的失真度為漢明失真。因為是二元信源，輸入是等概分布，則該信源的信息率失真函數(shù)若當(dāng)則此信源在此信道中傳輸時不會引起錯誤，也就是不會因信道而增加信源新的失真?？偟男旁吹氖д媸?/p>

23、信源壓縮編碼所造成的允許失真。所以有故所以，允許信源平均失真時，此信源就可以在此信道中傳輸。7.7 由已知條件可以求得（1）達(dá)到的信道為（2）達(dá)到的信道為7.8 根據(jù)最大失真度的定義，有而最小平均失真達(dá)到的信道為達(dá)到的信道為7.9 因為有失真，所以不為零。根據(jù)率失真函數(shù)的定義域，可以得到7.10 由和可以定出曲線的兩個端點(diǎn)。再根據(jù)在其定義域內(nèi)非負(fù)、下凸和嚴(yán)格遞減，可以得到曲線圖如圖和圖所示。因為的物理意義為滿足失真度不大于的最小信息速率，而信息速率一定是非負(fù)的，所以整個曲線非負(fù)。允許的失真門限越大，信息速率就可以降得越低，所以曲線是嚴(yán)格遞減的。7.11 （1）為了使得失真為0，必須有，即，所以

24、有。（2）平均失真為如果失真是有限的，則并且。如果信息率為0，則與統(tǒng)計獨(dú)立，即。因此，使得信息率為0的平均失真為，即是使得信息率為0的最小失真。7.12第8章 信道編碼8.1 2，1，08.2 8，3，100，0008.3 0101101008.4 根據(jù)極大似然譯碼規(guī)則選擇譯碼函數(shù)又設(shè)輸入符號為等概率分布則有若按下述譯碼函數(shù)計算平均錯誤概率得8.5 用極大似然譯碼規(guī)則譯碼，先寫出輸入輸出的聯(lián)合概率分布平均譯碼錯誤概率為8.6 （1）信道輸入有4個序列，因此編碼后信息傳遞率為（2）信道矩陣如下：因此聯(lián)合概率分布為所以有。8.7 （1）根據(jù)離散對稱信道的性質(zhì)，其信道容量為（2）用簡單的二次重復(fù)碼發(fā)送符