信息論與編碼理論習(xí)題答案

第二章信息量和熵2.2八元編碼系統(tǒng)，碼長(zhǎng)為3，第一個(gè)符號(hào)用于同步，每秒1000個(gè)碼字，求它的信息速率。解：同步信息均相同，不含信息，因此每個(gè)碼字的信息量為2=23=6bit因此，信息速率為61000=6000bit/s2.3擲一對(duì)無(wú)偏骰子，告訴你得到的總的點(diǎn)數(shù)為：(a)7;(b)12。問(wèn)各得到多少信息量。解：(1)可能的組合為{1，6},{2，5},{3，4},{4，3},{5，2},{6，1}==得到的信息量===2.585bit(2)可能的唯一，為{6，6}=得到的信息量===5.17bit2.4經(jīng)過(guò)充分洗牌后的一副撲克（52張），問(wèn)：(a)任何一種特定的排列所給出的信息量是多少？(b)若從中抽取13張牌，所給出的點(diǎn)數(shù)都不相同時(shí)得到多少信息量？解：(a)=信息量===225.58bit(b)==信息量==13.208bit2.9隨機(jī)擲3顆骰子，X表示第一顆骰子的結(jié)果，Y表示第一和第二顆骰子的點(diǎn)數(shù)之和，Z表示3顆骰子的點(diǎn)數(shù)之和，試求、、、、。解：令第一第二第三顆骰子的結(jié)果分別為，，，相互獨(dú)立，則，，==6=2.585bit===2(36+18+12+9+)+6=3.2744bit=-=-[-]而=，所以=2-=1.8955bit或=-=+-而=，所以=2-=1.8955bit===2.585bit=+=1.8955+2.585=4.4805bit2.10設(shè)一個(gè)系統(tǒng)傳送10個(gè)數(shù)字，0，1，…，9。奇數(shù)在傳送過(guò)程中以0.5的概率錯(cuò)成另外一個(gè)奇數(shù)，其余正確接收，求收到一個(gè)數(shù)字平均得到的信息量。解：=-因?yàn)檩斎氲雀牛尚诺罈l件可知，即輸出等概，則=10==-=0-=--=25+845==1bit=-=10-1=5=2.3219bit2.11令{}為一等概消息集，各消息相應(yīng)被編成下述二元碼字=0000，=0011，=0101，=0110，=1001，=1010，=1100，=1111通過(guò)轉(zhuǎn)移概率為p的BSC傳送。求：(a)接收到的第一個(gè)數(shù)字0與之間的互信息量。(b)接收到的前二個(gè)數(shù)字00與之間的互信息量。(c)接收到的前三個(gè)數(shù)字000與之間的互信息量。(d)接收到的前四個(gè)數(shù)字0000與之間的互信息量。解：即，，，=+====1+bit=====bit===3[1+]bit==bit2.12計(jì)算習(xí)題2.9中、、、、。解：根據(jù)題2.9分析=2(+++++++)=3.5993bit=-=-=1.0143bit=-=-=0.3249bit=-=-=1.0143bit=-=-=0.6894bit=-=-=0bit2.14對(duì)于任意概率事件集X,Y,Z，證明下述關(guān)系式成立(a)+，給出等號(hào)成立的條件(b)=+(c)證明：(b)=-=-=--=+(c)=-=[-][-]=-=當(dāng)=，即X給定條件下，Y與Z相互獨(dú)立時(shí)等號(hào)成立(a)上式(c)左右兩邊加上，可得++于是+2.28令概率空間，令Y是連續(xù)隨機(jī)變量。已知條件概率密度為，求：(a)Y的概率密度(b)(c)若對(duì)Y做如下硬判決求，并對(duì)結(jié)果進(jìn)行解釋。解：(a)由已知，可得===+=(b)==2.5bit===2bit=-=0.5bit(c)由可得到V的分布律V-101p1/41/21/4再由可知V-101p(V|x=-1)1/21/20p(V|x=1)01/21/2bit=1bit==0.5bit2.29令和是同一事件集U上的兩個(gè)概率分布，相應(yīng)的熵分別為和。(a)對(duì)于，證明=+是概率分布(b)是相應(yīng)于分布的熵，試證明+證明：(a)由于和是同一事件集U上的兩個(gè)概率分布，于是0，0=1，=1又，則=+0=+=1因此，是概率分布。(b)==（引理2）=+

第三章信源編碼——離散信源無(wú)失真編碼3.1試證明長(zhǎng)為的元等長(zhǎng)碼至多有個(gè)碼字。證：=1\*GB3①在元碼樹上，第一點(diǎn)節(jié)點(diǎn)有個(gè)，第二級(jí)有QUOTED2，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)碼字，若最長(zhǎng)碼有，則函數(shù)有==，此時(shí)，所有碼字對(duì)應(yīng)碼樹中的所有節(jié)點(diǎn)。=2\*GB3②碼長(zhǎng)為1的個(gè)；碼長(zhǎng)為2的個(gè)，…，碼長(zhǎng)為的個(gè)∴總共=個(gè)3.2設(shè)有一離散無(wú)記憶信源。若對(duì)其輸出的長(zhǎng)為100的事件序列中含有兩個(gè)或者少于兩個(gè)的序列提供不同的碼字。(a)在等長(zhǎng)編碼下，求二元碼的最短碼長(zhǎng)。(b)求錯(cuò)誤概率（誤組率）。解:(a)不含的序列1個(gè)長(zhǎng)為100的序列中含有1個(gè)的序列QUOTEC1001=100個(gè)長(zhǎng)為100的序列中含有2個(gè)的序列=4950個(gè)∴所需提供碼的總數(shù)M=1+100+4950=5051于是采用二元等長(zhǎng)編碼=12.3，故取=13(b)當(dāng)長(zhǎng)度為100的序列中含有兩個(gè)或更多QUOTEa1的時(shí)出現(xiàn)錯(cuò)誤，因此錯(cuò)誤概率為=-=3.3設(shè)有一離散無(wú)記憶信源，U=，其熵為?？疾炱溟L(zhǎng)為的輸出序列，當(dāng)時(shí)滿足下式(a)在=0.05，=0.1下求(b)在=，=下求(c)令是序列的集合，其中試求L=時(shí)情況(a)(b)下，T中元素個(gè)數(shù)的上下限。解：===0.81bitQUOTEa1a21434==-==0.471則根據(jù)契比雪夫大數(shù)定理(a)===1884(b)==4.71(c)由條件可知為典型序列，若設(shè)元素個(gè)數(shù)為，則根據(jù)定理其中，，可知(i)，，下邊界：上邊界：=故(ii)，，=故3.4對(duì)于有4字母的離散無(wú)記憶信源有兩個(gè)碼A和碼B，參看題表。字母概率碼A碼Ba10.411a20.30110a30.2001100a40.100011000(a)各碼是否滿足異字頭條件？是否為唯一可譯碼？(b)當(dāng)收到1時(shí)得到多少關(guān)于字母a的信息？(c)當(dāng)收到1時(shí)得到多少關(guān)于信源的平均信息？解：①碼A是異頭字碼，而B為逗點(diǎn)碼，都是唯一可譯碼。②碼Abit碼Bbit③碼AU=｛｝==1.32bit碼B=0bit（收到1后，只知道它是碼字開頭，不能得到關(guān)于U的信息。）3.5令離散無(wú)記憶信源(a)求最佳二元碼,計(jì)算平均碼長(zhǎng)和編碼效率。(b)求最佳三元碼,計(jì)算平均碼長(zhǎng)和編碼效率。解：(a)=3.234bit平均碼長(zhǎng)=3.26=效率(b)平均碼長(zhǎng)=2.11=3.344效率3.6令離散無(wú)記憶信源(a)求對(duì)U的最佳二元碼、平均碼長(zhǎng)和編碼效率。(b)求對(duì)U的最佳二元碼、平均碼長(zhǎng)和編碼效率。(c)求對(duì)U的最佳二元碼、平均碼長(zhǎng)和編碼效率。解：(a)=0.5×1+0.3×2+2×0.2=1.5bit(b)∵離散無(wú)記憶∴H(UU)=2H(U)=2.97bitp(aa)=0.25,p(aa)=0.15,p(aa)=0.1,p(aa)=0.15,p(aa)=0.09p(aa)=0.06,p(aa)=0.1,p(aa)=0.06,p(aa)=0.04==0.99(c)有關(guān)最佳二元類似略3.7令離散無(wú)記憶信源且0≤P(a)≤P(a)≤….≤P(a)<1。定義Q=,i>1，而Q1=0，今按下述方法進(jìn)行二元編碼。消息a的碼字為實(shí)數(shù)Q的二元數(shù)字表示序列的截短（例如1/2的二元數(shù)字表示序列為1/2→10000…，1/4→0100…）,保留的截短序列長(zhǎng)度n是大于或等于I(a)的最小整數(shù)。(a)對(duì)信源構(gòu)造碼。(b)證明上述編碼法得到的碼滿足異字頭條件，且平均碼長(zhǎng)滿足H(U)≤≤H(U)+1。解：(a)符號(hào)QiLC040000400014001040011401003011210211(b)反證法證明異字頭條件令k<k’，若是的字頭，則又由可知，從而得這與假設(shè)是的字頭（即）相矛盾，故滿足異字頭條件。由已知可得對(duì)不等號(hào)兩邊取概率平均可得即3.8擴(kuò)展源DMC，(a)求對(duì)U的最佳二元碼、平均碼長(zhǎng)和編碼效率。(b)求對(duì)U的最佳二元碼、平均碼長(zhǎng)和編碼效率。(c)求對(duì)U的最佳二元碼、平均碼長(zhǎng)和編碼效率。(d)求對(duì)U的最佳二元碼、平均碼長(zhǎng)和編碼效率。解：(a)，=1，=1bitDMC信道，，(c)=2.944=0.981=98.85%(d)略3.9設(shè)離散無(wú)記憶信源試求其二元和三元Huffman編碼。解：3.11設(shè)信源有K個(gè)等概的字母,其中K=,12。今用Huffman編碼法進(jìn)行二元編碼。（a）是否存在有長(zhǎng)度不為j或j+1的碼字，為什么？（b）利用和j表示長(zhǎng)為j+1的碼字?jǐn)?shù)目。（c）碼的平均長(zhǎng)度是多少？解：Huffman思想：將概率小的用長(zhǎng)碼，大的用短碼，保證↓，當(dāng)?shù)雀艜r(shí)，趨于等長(zhǎng)碼。a)對(duì)時(shí)，K=2j，則用長(zhǎng)度為j碼表示；當(dāng)時(shí)，用K=2j+1，用長(zhǎng)度為j+1碼表示。平均碼長(zhǎng)最短，則當(dāng)12時(shí)，則介于兩者之間，即只存在j，j+1長(zhǎng)的碼字。b)設(shè)長(zhǎng)為j的碼字個(gè)數(shù)為Nj，長(zhǎng)度為j+1的碼字?jǐn)?shù)目為Nj+1，根據(jù)二元Huffman編碼思想（必定占滿整個(gè)碼樹），即從而，c）=3.12設(shè)二元信源的字母概率為，。若信源輸出序列為1011011110110111(a)對(duì)其進(jìn)行算術(shù)編碼并進(jìn)行計(jì)算編碼效率。(b)對(duì)其進(jìn)行LZ編碼并計(jì)算編碼效率。解：(a)根據(jù)遞推公式可得如下表格其中，F(xiàn)(1)=0，F(xiàn)(1)=，p(0)=，p(1)=101011011110110111從而C=(b)首先對(duì)信源序列進(jìn)行分段：1011011110110111然后對(duì)其進(jìn)行編碼，編碼字典如下所示段號(hào)短語(yǔ)ij編碼11010001200000003111100114012101015111310111601141100170111611101bit3.13設(shè)DMS為U=，各a相應(yīng)編成碼字0、10、110和1110。試證明對(duì)足夠長(zhǎng)的信源輸出序列，相應(yīng)的碼序列中0和1出現(xiàn)的概率相等。解：概率信源符號(hào)碼字1/201/4101/81101/81110設(shè)信源序列長(zhǎng)為N，則相應(yīng)碼字長(zhǎng)為（條件是N要足夠長(zhǎng)）相應(yīng)碼序列中0出現(xiàn)的次數(shù)∴p(0)==p(1)=1-p(0)=3.14設(shè)有一DMS,U=采用如下表的串長(zhǎng)編碼法進(jìn)行編碼信源輸出序列0串長(zhǎng)度（或中間數(shù)字）輸出二元碼字101001…0000000100000000012…78000000010010…01111(a)求H(U)。(b)求對(duì)于每個(gè)中間數(shù)字相應(yīng)的信源數(shù)字的平均長(zhǎng)度。(c)求每個(gè)中間數(shù)字對(duì)應(yīng)的平均長(zhǎng)度。(d)說(shuō)明碼的唯一可譯性。解：(a)bit由已知可得下表先驗(yàn)概率信源輸出序列0串長(zhǎng)度（或中間數(shù)字）輸出二元碼字0.11000000.0901100010.081001200100.07290001300110.065600001401000.059000001501010.05310000001601100.047800000001701110.430500000000181(b)bit(c)EQEQEQbit(d)異字碼頭第四章信道及信道容量4.1計(jì)算由下述轉(zhuǎn)移概率矩陣給定的DMC的容量。(a)它是一對(duì)稱信道，達(dá)到C需要輸入等概，即=∴Cbit/符號(hào)(b)它是一對(duì)稱信道∴bit/符號(hào)（c）它是分信道和的和信道由，可知bit/符號(hào)

4.3求圖中DMC的容量及最佳輸入分布（a）(b)解：（a）由圖知發(fā)送符號(hào)1時(shí)等概率收到0,1,2,∴傳對(duì)與傳錯(cuò)概率完全相同，即不攜帶任何信息量，于是信道簡(jiǎn)化為二元純刪除信道bit/符號(hào)（b）由圖知為準(zhǔn)對(duì)稱∴當(dāng)輸入等概，即時(shí)達(dá)到信道容量C此時(shí)∴=bit/符號(hào)N個(gè)相同的BSC級(jí)聯(lián)如圖。各信道的轉(zhuǎn)移概率矩陣。令，且為已知。(a)求的表達(dá)式。(b)證明時(shí)有，且與取值無(wú)關(guān)，從而證明時(shí)的級(jí)聯(lián)信道容量解：N個(gè)信道級(jí)聯(lián)后BSC可表示為N個(gè)級(jí)聯(lián)可以看成N-1個(gè)級(jí)聯(lián)后與第N個(gè)級(jí)聯(lián)∴同理可得從而(a)(b)因此與無(wú)關(guān)。由于與無(wú)關(guān)，因此，C=0。4.8一PCM語(yǔ)音通信系統(tǒng)，已知信號(hào)帶寬W=4000Hz，采樣頻率為2W，且采用8級(jí)幅度量化，各級(jí)出現(xiàn)的概率為1/2，1/4，1/8，1/16，1/32，1/32，1/32，1/32。試求所需的信息速率.解：bit∴信息速率bit/s4.9在數(shù)字電視編碼中，若每幀為500行，每行劃分成600個(gè)像素，每個(gè)像素采用8電平量化，且每秒傳送30幀時(shí)，試求所需的信息速率。解：每個(gè)像素信息量為3bit每秒傳輸30幀，即個(gè)像素∴bit/s4.10帶寬為3kHZ，信噪比為30dB的電話系統(tǒng)，若傳送時(shí)間為3分鐘，試估計(jì)可能傳送話音信息的數(shù)目。解：=30dB==1000則Rbit/s=29