1.（1）列出如下表所示信源符號(hào)與碼字的對(duì)應(yīng)表：信源符號(hào)碼字110111100（2）平均碼長(zhǎng)：2.假設(shè)信源符號(hào)集為，采用霍夫曼編碼得到相應(yīng)的代碼組。其中，碼字按碼長(zhǎng)從小到大的順序排列，即碼字最短、碼字最長(zhǎng)。記最大碼長(zhǎng)和最小碼長(zhǎng)分別為和，則根據(jù)Huffman編碼的性質(zhì)，對(duì)應(yīng)的碼字的長(zhǎng)度為，對(duì)應(yīng)的碼字的長(zhǎng)度也為。采用反證法，假設(shè)?，F(xiàn)對(duì)代碼組組對(duì)應(yīng)的碼樹做如下調(diào)整：（1）將代表碼字和碼字的葉節(jié)點(diǎn)去掉，其父節(jié)點(diǎn)（長(zhǎng)度為）成為樹葉，分配給信源符號(hào)的碼字；（2）對(duì)代表碼字的節(jié)點(diǎn)延伸出2個(gè)葉節(jié)點(diǎn)（長(zhǎng)度為），分配給信源符號(hào)和的碼字。調(diào)整后與調(diào)整前的平均碼長(zhǎng)之差為 這表明，調(diào)整之后的平均碼長(zhǎng)更短，也說明原先的霍夫曼編碼結(jié)果不是最優(yōu)的。顯然與霍夫曼編碼一定為緊致碼的結(jié)論矛盾。因此，對(duì)于該信源而言，霍夫曼編碼得到的代碼組中，最大和最小的碼字長(zhǎng)度至多相差1。3.（1）將該幅特殊的撲克牌視作信源，構(gòu)建相應(yīng)的概率空間。牌總數(shù)：各點(diǎn)的概率：，，，…，信源熵為：乙平均每輪得知抽取牌的點(diǎn)數(shù)后所獲得的信息量即為信源的熵。（2）可將乙每輪提問的過程視作一個(gè)搜索問題：將不同的點(diǎn)數(shù)布置在二元碼樹（回答只有“是”或“否”兩種情況）的葉節(jié)點(diǎn)上，以平均最快的速度搜索出被隨機(jī)抽取的點(diǎn)數(shù)。為了回答這一問題，可以采用霍夫曼編碼，實(shí)現(xiàn)撲克牌點(diǎn)數(shù)在二元碼樹上的最佳布置。對(duì)13個(gè)符號(hào)進(jìn)行二元Huffman編碼，結(jié)果如下圖所示。依據(jù)Huffman編碼結(jié)果，得到如下圖最佳策略：（3）采用最佳策略后，平均每輪提問題的次數(shù)等于編碼結(jié)果的平均碼長(zhǎng)： 4.（1）根據(jù)唯一可譯碼的判別準(zhǔn)則，可知A、B、C、E是唯一可譯碼。（2）根據(jù)即時(shí)碼的判別準(zhǔn)則，在上述唯一可譯碼中，A、C、E是即時(shí)碼。5.（1）需要編碼的信源序列的數(shù)目為： 假設(shè)二元定長(zhǎng)碼的長(zhǎng)度為l，則可用碼字的數(shù)目應(yīng)大于待編碼的對(duì)象的數(shù)目，即 。（2）由于部分序列沒有進(jìn)行編碼，所以當(dāng)這些序列出現(xiàn)的時(shí)候，會(huì)產(chǎn)生譯碼錯(cuò)誤。正確譯碼概率為已編碼序列的出現(xiàn)概率，為 則錯(cuò)誤概率為 6.（1）根據(jù)克拉夫特-麥克米倫不等式，因?yàn)?，所以不存在碼長(zhǎng)分布為1、2、2、2、2、2、3、3、3、3的唯一可譯二元碼。（2）根據(jù)克拉夫特-麥克米倫不等式，因?yàn)?，所以可以?gòu)造碼長(zhǎng)為1、2、2、2、2、2、3、3、3的三元即時(shí)碼，例如：0，10，11，12，20，21，220，221，222。（3）依據(jù)碼樹和即時(shí)碼的意義映射關(guān)系，可以由碼樹構(gòu)建即時(shí)碼。依題意，符合1、2、2、2、2、2、3、3、3碼長(zhǎng)分布的碼樹是這樣生成的：一個(gè)根節(jié)點(diǎn)延伸出3個(gè)一階節(jié)點(diǎn)；其中2個(gè)一階節(jié)點(diǎn)要各自延伸出3個(gè)二階節(jié)點(diǎn)，由3個(gè)一階節(jié)點(diǎn)中選2個(gè)的方法有3種；再從6個(gè)二階節(jié)點(diǎn)中選擇1個(gè)，延伸出3個(gè)三階節(jié)點(diǎn)，選擇的方法有6種。綜上所述，可以構(gòu)建的碼樹共有3×6=18棵，其中的一棵碼樹如下圖所示。將這顆碼樹的9個(gè)葉節(jié)點(diǎn)分配給9個(gè)信源符號(hào)，有9!種分配方式?；诖a樹的數(shù)目和葉節(jié)點(diǎn)的分配方式，符合1、2、2、2、2、2、3、3、3碼長(zhǎng)分布的即時(shí)碼共有18×9!種。7.天平稱重會(huì)出現(xiàn)三種情況：左傾（重）、右傾（重）、平衡。利用天平稱重，從8枚硬幣中找出1枚假幣，并使得尋找假幣的平均次數(shù)最少，類似于構(gòu)造平均碼長(zhǎng)最短的緊致碼。8枚硬幣的出現(xiàn)概率相等，構(gòu)建的三元霍夫曼碼樹如下圖所示。記8枚硬幣為s1、s2、s3、s4、s5、s6、s7、s8，并將碼樹的葉節(jié)點(diǎn)從左至右依次分配給8枚硬幣?；舴蚵幋a得到的代碼組平均碼長(zhǎng)為2，因此平均最少2次能夠把這枚假幣找出來。根據(jù)霍夫曼編碼結(jié)果，具體稱重步驟如下：第一步：在天平左側(cè)放置s1、s2、s3，在天平右側(cè)放置s4、s5、s6。第二步：（1）若天平左傾，表明s1、s2、s3中有假幣。在天平左側(cè)放置s1，在天平右側(cè)放置s2。若天平左傾，則s1為假幣；若天平右傾，則s2為假幣；若天平平衡，則s3為假幣。（2）若天平右傾，表明s4、s5、s6中有假幣。在天平左側(cè)放置s4，在天平右側(cè)放置s5。若天平左傾，則s4為假幣；若天平右傾，則s5為假幣；若天平平衡，則s6為假幣。（3）若天平平衡，表明s7、s8中有假幣。在天平左側(cè)放置s7，在天平右側(cè)放置s8。若天平左傾，則s7為假幣；若天平右傾，則s8為假幣。8.（1）采用霍夫曼編碼方法，得到最佳二元碼為 平均碼長(zhǎng)： 編碼效率： （2）采用霍夫曼編碼方法，得到最佳三元碼為 平均碼長(zhǎng)： 編碼效率： 9.采用霍夫曼編碼方法。第一種： 第二種： 第一個(gè)代碼組的方差較小，質(zhì)量更好。10.在符號(hào)等概率出現(xiàn)的條件下，對(duì)符號(hào)集進(jìn)行二元霍夫曼編碼，得到的代碼組中最大和最小的碼字長(zhǎng)度至多相差1。（1）當(dāng)每個(gè)碼字的長(zhǎng)度均為，可推出平均碼長(zhǎng)（2）當(dāng)+1，由霍夫曼編碼過程可推出2個(gè)碼字的長(zhǎng)度為，其余碼字的長(zhǎng)度為。平均碼長(zhǎng)為 11.（1）如果每次品嘗一瓶酒，按照概率從大到小進(jìn)行排列，那么合理的品嘗順序應(yīng)該是1、2、3、4。至多品嘗到第四次時(shí)，就可以判斷哪瓶酒變質(zhì)了。因此，第四次品嘗的概率應(yīng)當(dāng)是最后兩瓶酒的概率之和，即。若將品嘗次數(shù)看作碼字的長(zhǎng)度，品嘗次數(shù)的均值就是平均碼長(zhǎng)。平均品嘗次數(shù)為： （2）若允許將數(shù)瓶酒混合起來一起品嘗，尋找使平均品嘗次數(shù)最少的策略，類似于最佳編碼問題。按照概率分布，對(duì)上述5瓶酒進(jìn)行霍夫曼編碼，得到代碼組：。根據(jù)編碼結(jié)果，具體品嘗過程如下：第一步，品嘗第二和第三瓶酒的混合，或者其他三瓶酒的混合。第二步，取決于第一步的結(jié)果：若壞酒在第二和第三瓶酒中，則第二步品嘗第二瓶或第三瓶酒，可找到壞酒；若壞酒在第一、第四和第五瓶酒中，則第二步品嘗第一瓶或第四瓶和第五瓶的混合酒。若壞酒是第一瓶，則終止品嘗；若壞酒在第四瓶和第五瓶中，還需進(jìn)行第三次品嘗，才能找到壞酒。綜上所述，平均品嘗次數(shù)為由于霍夫曼編碼結(jié)果不是唯一的，所以還存在另外的方案，比如。此時(shí)，第一步應(yīng)先品嘗第一和第二瓶的混合酒，或者其他三瓶酒的混合。12．（1）可以這樣編碼：805門電話要占用1000個(gè)3位數(shù)中的805個(gè)，即要占用首位為0～7的所有數(shù)字及以8為首的5個(gè)數(shù)字。因?yàn)橐缶用耠娫捥?hào)碼等長(zhǎng)，以9為首的數(shù)字5位長(zhǎng)可定義10000個(gè)號(hào)碼，6位長(zhǎng)可定義100000個(gè)號(hào)碼。所以，?；蛴蒏raft不等式，有 解得 即 （2）在問題（1）的基礎(chǔ)上，將80為首的數(shù)字用于最后5個(gè)公務(wù)電話，81～86為首的6位數(shù)用于B區(qū)51000個(gè)號(hào)碼，以9為首的5位數(shù)用于A區(qū)9000個(gè)號(hào)碼。所以，?；蛴蒏raft不等式，有 解得 即 13.二次擴(kuò)展信源的霍夫曼編碼如下：二次拓展信源的輸出序列序列的輸出概率碼字0.25010.20100.20110.160010.05000010.05000100.04000110.040000000.01000001編碼效率為 14.由已知條件可知聯(lián)合隨機(jī)變量的概率分布如下：000001010011100101110111 霍夫曼編碼的結(jié)果如下：碼字0001000111000101110110110100001011101110010111011115.霍夫曼編碼得到的代碼組必然是平均碼長(zhǎng)最短的即時(shí)碼。因此，可以將題目中的代碼組用碼樹表示，并分析是否有縮短平均碼長(zhǎng)的可能性。（1）是概率分布的霍夫曼編碼。（2）可以被改進(jìn)為。無論信源具有何種概率分布，都可以縮短平均碼長(zhǎng)。因此，不是霍夫曼編碼的結(jié)果。（3）可以被改進(jìn)為。與第（2）問類似，不是霍夫曼編碼的結(jié)果。16.代碼組的譯碼延時(shí)為3。即，若接收序列為0000，那么收到第一個(gè)碼符號(hào)0后不能直接譯碼，必須等后續(xù)三個(gè)碼元符號(hào)收到之后才能譯碼。17.對(duì)這八匹馬進(jìn)行霍夫曼編碼，結(jié)果如下：贏率碼字101001000100000000000100001000001118.（1）二進(jìn)制費(fèi)諾編碼如下：第一次分組第二次分組第三次分組第四次分組碼字000010010I01110010011011011010111011111（2）平均碼長(zhǎng)為 編碼效率為 碼方差為 19.20.（1）信源熵為二元無噪信道的信道容量為則每秒信源產(chǎn)生的信息量為比特、信道可以傳輸?shù)男畔⒘繛?比特。每秒信源產(chǎn)生的信息量小于信道可以傳輸?shù)男畔⒘?。因此，通過適當(dāng)?shù)木幋a實(shí)現(xiàn)無失真?zhèn)鬏?，是有可能的。?）對(duì)信源的2次擴(kuò)展信源進(jìn)行Huffman編碼，編碼結(jié)果如下：2次擴(kuò)展信源概率碼字0.6400.16100.161100.04111計(jì)算可得：信源符號(hào)對(duì)應(yīng)的平均碼長(zhǎng)為，信源編碼器每秒輸出符號(hào)數(shù)為。因?yàn)?，所以傳輸滿足無失真要求。21.依題意，新信源各個(gè)符號(hào)的出現(xiàn)概率為 （1）新信源的熵為 其中，因此，有 （2）當(dāng)時(shí)，，所以22.（1）以隨機(jī)變量代表信源的輸出符號(hào)。信源的符號(hào)熵為 （2）平均碼長(zhǎng) 則平均每個(gè)二進(jìn)碼的自信息量為比特/碼元23.依題意，所有碼字如下：平均每個(gè)碼字的長(zhǎng)度為 則平均每個(gè)碼元攜帶的信息量為 所以，其編碼效率為 24.狀態(tài)集合狀態(tài)轉(zhuǎn)移矩陣平穩(wěn)分布極限熵對(duì)此馬爾可夫信源進(jìn)行二元霍夫曼編碼，有兩種方案可供選擇：（1）將進(jìn)入平穩(wěn)狀態(tài)的馬爾可夫信源視作無記憶信源，依據(jù)平穩(wěn)分布進(jìn)行二元霍夫曼編碼，結(jié)果為：平均碼長(zhǎng)：編碼效率：（2）充分考慮符號(hào)之間的相關(guān)性，在考慮前一個(gè)符號(hào)的條件下，對(duì)下一個(gè)符號(hào)進(jìn)行編碼，如下表所示。概率碼字概率碼字概率碼字0.00—0.5000.5010.25100.5000.25110.00—1.00—0.00—表中表明：若上一個(gè)字母為“a”，則下一個(gè)字母“a”不編碼，“b”、“c”的編碼分別為“0”、“1”；若上一個(gè)字母為“b”，則下一個(gè)字母“a”、“b”、“c”的編碼分別為“10”、“0”、“11”；若上一個(gè)字母為“c”，則無論下一個(gè)字母是“a”、“b”或“c”，均不編碼?？傻茫籂顟B(tài)下平均碼長(zhǎng)狀態(tài)下平均碼長(zhǎng)狀態(tài)下平均碼長(zhǎng)總平均碼長(zhǎng)編碼效率對(duì)比兩種編碼方法，可以看出：在充分挖掘信源的相關(guān)性并加以利用后，可以顯著提升編碼效率。假若信源輸出原始序列為“bbabcbacbbcbacbac”，第一種編碼方案形成的碼字序列為“00110100111000100111001110”，第二種編碼方案形成的碼字序列為“b010011101011101101”。25.該信源的實(shí)際情況為二階馬爾可夫信源狀態(tài)集合狀態(tài)轉(zhuǎn)移矩陣平穩(wěn)分布（1）若將該信源視作一階馬爾可夫信源一維平穩(wěn)分布一維條件概率分布一階馬爾可夫信源極限熵次擴(kuò)展信源的輸出序列的發(fā)生