信息論習(xí)習(xí)題解答

1、第二章 信息量和熵 八元編碼系統(tǒng)，碼長為3，第一個(gè)符號用于同步，每秒1000個(gè)碼字，求它的信息速率。解：同步信息均相同，不含信息，因此 每個(gè)碼字的信息量為 2=23=6 bit 因此，信息速率為 61000=6000 bit/s 擲一對無偏骰子，告訴你得到的總的點(diǎn)數(shù)為：(a) 7; (b) 12。問各得到多少信息量。 解：(1) 可能的組合為 1，6,2，5,3，4,4，3,5，2,6，1=得到的信息量 = bit (2) 可能的唯一，為 6，6 = 得到的信息量= bit 經(jīng)過充分洗牌后的一副撲克（52張），問：(a) 任何一種特定的排列所給出的信息量是多少(b) 若從中抽取13張牌，所給出

2、的點(diǎn)數(shù)都不相同時(shí)得到多少信息量解：(a) = 信息量= bit (b) = 信息量= bit 隨機(jī)擲3顆骰子，X表示第一顆骰子的結(jié)果，Y表示第一和第二顆骰子的點(diǎn)數(shù)之和，Z表示3顆骰子的點(diǎn)數(shù)之和，試求、。 解：令第一第二第三顆骰子的結(jié)果分別為，相互獨(dú)立，則， =6= bit = =2(36+18+12+9+)+6 = bit =-=- 而=，所以= 2-= bit 或=-=+- 而= ，所以=2-= bit= bit=+=+= bit 設(shè)一個(gè)系統(tǒng)傳送10個(gè)數(shù)字，0，1，9。奇數(shù)在傳送過程中以的概率錯(cuò)成另外一個(gè)奇數(shù)，其余正確接收，求收到一個(gè)數(shù)字平均得到的信息量。 解：=-因?yàn)檩斎氲雀?，由信道條件可

3、知，即輸出等概，則=10= =- =0- = - =25+845 =1 bit=-=10 -1=5= bit 令為一等概消息集，各消息相應(yīng)被編成下述二元碼字 =0000，=0011，=0101，=0110，=1001，=1010，=1100，=1111通過轉(zhuǎn)移概率為p的BSC傳送。求：(a)接收到的第一個(gè)數(shù)字0與之間的互信息量。(b)接收到的前二個(gè)數(shù)字00與之間的互信息量。(c)接收到的前三個(gè)數(shù)字000與之間的互信息量。(d)接收到的前四個(gè)數(shù)字0000與之間的互信息量。解：即， =+= =1+ bit = = bit = =31+ bit = = bit 計(jì)算習(xí)題中、。解：根據(jù)題分析=2(+)

4、 = bit =-=-= bit =-=-= bit =-=-= bit =-=-= bit =-=-=0 bit 對于任意概率事件集X,Y,Z，證明下述關(guān)系式成立 (a)+，給出等號成立的條件 (b)=+ (c) 證明：(b) =- =- =- =+ (c) =- =- - =- = 當(dāng)=，即X給定條件下，Y與Z相互獨(dú)立時(shí)等號成立 (a) 上式(c)左右兩邊加上，可得+于是+ 令概率空間，令Y是連續(xù)隨機(jī)變量。已知條件概率密度為 ，求： (a)Y的概率密度 (b) (c) 若對Y做如下硬判決 求，并對結(jié)果進(jìn)行解釋。 解：(a) 由已知，可得= = =+ = (b) = bit = = =2 b

5、it =-= bit (c) 由可得到V的分布律V-101p1/41/21/4 再由可知V-101p(V|x=-1)1/21/20p(V|x=1)01/21/2 bit =1 bit = bit 令和是同一事件集U上的兩個(gè)概率分布，相應(yīng)的熵分別為和。 (a)對于，證明=+是概率分布 (b)是相應(yīng)于分布的熵，試證明+ 證明：(a) 由于和是同一事件集U上的兩個(gè)概率分布，于是0，0 =1，=1 又，則=+0 =+=1 因此，是概率分布。 (b) = = （引理2） =+第三章 信源編碼離散信源無失真編碼 試證明長為的元等長碼至多有個(gè)碼字。證：在元碼樹上，第一點(diǎn)節(jié)點(diǎn)有個(gè)，第二級有，每個(gè)節(jié)點(diǎn)對應(yīng)一個(gè)碼

6、字，若最長碼有，則函數(shù)有=，此時(shí)，所有碼字對應(yīng)碼樹中的所有節(jié)點(diǎn)。碼長為1的個(gè)；碼長為2的個(gè)，碼長為的個(gè)總共=個(gè) 設(shè)有一離散無記憶信源。若對其輸出的長為100的事件序列中含有兩個(gè)或者少于兩個(gè)的序列提供不同的碼字。 (a) 在等長編碼下，求二元碼的最短碼長。 (b) 求錯(cuò)誤概率（誤組率）。解: (a)不含的序列 1個(gè)長為100的序列中含有1個(gè)的序列 =100個(gè) 長為100的序列中含有2個(gè)的序列 =4950個(gè) 所需提供碼的總數(shù)M=1+100+4950=5051于是采用二元等長編碼 =，故取=13(b)當(dāng)長度為100的序列中含有兩個(gè)或更多的時(shí)出現(xiàn)錯(cuò)誤，因此錯(cuò)誤概率為=-= 設(shè)有一離散無記憶信源，U=，

7、其熵為?？疾炱溟L為的輸出序列，當(dāng)時(shí)滿足下式(a)在=，=下求(b)在=，=下求(c)令是序列的集合，其中 試求L=時(shí)情況(a)(b)下，T中元素個(gè)數(shù)的上下限。解：= bit =-= =則根據(jù)契比雪夫大數(shù)定理(a) =1884(b) =(c) 由條件可知為典型序列，若設(shè)元素個(gè)數(shù)為，則根據(jù)定理其中，可知 (i) ， 下邊界： 上邊界：= 故 (ii) ， =故 對于有4字母的離散無記憶信源有兩個(gè)碼A和碼B，參看題表。字母概率碼A碼Ba111a20110a3001100a400011000(a) 各碼是否滿足異字頭條件是否為唯一可譯碼(b) 當(dāng)收到1時(shí)得到多少關(guān)于字母a的信息(c) 當(dāng)收到1時(shí)得到多

8、少關(guān)于信源的平均信息解：碼A是異頭字碼，而B為逗點(diǎn)碼，都是唯一可譯碼。碼A bit碼B bit碼A U= = bit 碼B =0 bit（收到1后，只知道它是碼字開頭，不能得到關(guān)于U的信息。） 令離散無記憶信源(a) 求最佳二元碼,計(jì)算平均碼長和編碼效率。(b) 求最佳三元碼,計(jì)算平均碼長和編碼效率。解：(a) = bit平均碼長 =效率 (b)平均碼長 =效率 令離散無記憶信源 (a) 求對U的最佳二元碼、平均碼長和編碼效率。(b) 求對U的最佳二元碼、平均碼長和編碼效率。(c) 求對U的最佳二元碼、平均碼長和編碼效率。 解：(a)=×1+×2+2×= bit

9、(b) 離散無記憶 H(UU)=2H(U)= bitp(aa)=, p(aa)=, p(aa)=, p(aa)=, p(aa)= p(aa)=, p(aa)=, p(aa)=, p(aa)=(c) 有關(guān)最佳二元類似 略 令離散無記憶信源且0P(a)P(a). P(a)<1。定義Q=, i>1，而Q1=0，今按下述方法進(jìn)行二元編碼。消息a的碼字為實(shí)數(shù)Q的二元數(shù)字表示序列的截短（例如1/2的二元數(shù)字表示序列為1/210000，1/40100）,保留的截短序列長度n是大于或等于I(a)的最小整數(shù)。(a) 對信源構(gòu)造碼。(b) 證明上述編碼法得到的碼滿足異字頭條件，且平均碼長滿足H(U)H

10、(U)+1。解：(a)符號QiLC040000400014001040011401003011210211 (b) 反證法證明異字頭條件令k<k，若是的字頭，則又由可知， 從而得 這與假設(shè)是的字頭（即）相矛盾，故滿足異字頭條件。由已知可得對不等號兩邊取概率平均可得即 擴(kuò)展源DMC，(a)求對U的最佳二元碼、平均碼長和編碼效率。(b)求對U的最佳二元碼、平均碼長和編碼效率。(c)求對U的最佳二元碼、平均碼長和編碼效率。(d)求對U的最佳二元碼、平均碼長和編碼效率。解：(a) ，=1，=1 bit(b) DMC信道，(c)= =%(d) 略 設(shè)離散無記憶信源 試求其二元和三元Huffman編

11、碼。解： 設(shè)信源有K個(gè)等概的字母,其中K=,12。今用Huffman編碼法進(jìn)行二元編碼。（a）是否存在有長度不為j或j+1的碼字，為什么（b）利用和j表示長為j+1的碼字?jǐn)?shù)目。（c）碼的平均長度是多少 解：Huffman思想：將概率小的用長碼，大的用短碼，保證，當(dāng)?shù)雀艜r(shí)，趨于等長碼。a) 對時(shí)，K=2j，則用長度為j碼表示；當(dāng)時(shí)，用K=2j+1，用長度為j+1碼表示。平均碼長最短，則當(dāng)12時(shí)，則介于兩者之間，即只存在j，j+1長的碼字。b) 設(shè)長為j的碼字個(gè)數(shù)為Nj，長度為j+1的碼字?jǐn)?shù)目為Nj+1，根據(jù)二元Huffman編碼思想（必定占滿整個(gè)碼樹），即從而，c） = 設(shè)二元信源的字母概率為，

12、。若信源輸出序列為 1011 0111 1011 0111 (a) 對其進(jìn)行算術(shù)編碼并進(jìn)行計(jì)算編碼效率。 (b) 對其進(jìn)行LZ編碼并計(jì)算編碼效率。解：(a) 根據(jù)遞推公式 可得如下表格其中，F(xiàn)(1)=0， F(1)= ， p(0)=， p(1)=101011011110110111 從而 C = 0 (b) 首先對信源序列進(jìn)行分段：1 0 11 01 111 011 0111然后對其進(jìn)行編碼，編碼字典如下所示段號短語ij編碼11010001200000003111100114012101015111310111601141100170111611101 bit 設(shè)DMS為U=，各a相應(yīng)編成碼字

13、0、10、110和1110。 試證明對足夠長的信源輸出序列，相應(yīng)的碼序列中0和1出現(xiàn)的概率相等。解：概率信源符號碼字1/201/4101/81101/81110設(shè)信源序列長為N，則相應(yīng)碼字長為（條件是N要足夠長）相應(yīng)碼序列中0出現(xiàn)的次數(shù) p(0)= = p(1)=1-p(0)= 設(shè)有一DMS, U= 采用如下表的串長編碼法進(jìn)行編碼信源輸出序列0串長度（或中間數(shù)字）輸出二元碼字10100100000001000000000127800000001001001111 (a)求H(U)。 (b)求對于每個(gè)中間數(shù)字相應(yīng)的信源數(shù)字的平均長度。 (c)求每個(gè)中間數(shù)字對應(yīng)的平均長度。(d)說明碼的唯一可譯性

14、。解：(a) bit由已知可得下表先驗(yàn)概率信源輸出序列0串長度（或中間數(shù)字）輸出二元碼字100000011000100120010000130011000014010000000150101000000160110000000017011100000000181(b) bit(c) bit(d) 異字碼頭 第四章 信道及信道容量 計(jì)算由下述轉(zhuǎn)移概率矩陣給定的DMC的容量。(a) 它是一對稱信道，達(dá)到C需要輸入等概，即=C bit/符號(b) 它是一對稱信道 bit/符號（c）它是分信道和的和信道由，可知 bit/符號求圖中DMC的容量及最佳輸入分布（a） (b)解：（a）由圖知 發(fā)送符號1時(shí)等

15、概率收到0,1,2,傳對與傳錯(cuò)概率完全相同，即不攜帶任何信息量，于是信道簡化為二元純刪除信道 bit/符號（b）由圖知為準(zhǔn)對稱當(dāng)輸入等概，即時(shí)達(dá)到信道容量C此時(shí) = bit/符號4.5 N個(gè)相同的BSC級聯(lián)如圖。各信道的轉(zhuǎn)移概率矩陣。令，且為已知。(a) 求的表達(dá)式。(b) 證明時(shí)有，且與取值無關(guān)，從而證明時(shí)的級聯(lián)信道容量解：N個(gè)信道級聯(lián)后BSC可表示為N個(gè)級聯(lián)可以看成N-1個(gè)級聯(lián)后與第N個(gè)級聯(lián)同理可得從而(a)(b)因此與無關(guān)。由于與無關(guān)，因此，C=0。 一PCM語音通信系統(tǒng)，已知信號帶寬W=4000 Hz，采樣頻率為2W，且采用8級幅度量化，各級出現(xiàn)的概率為1/2，1/4，1/8，1/16

16、，1/32，1/32，1/32，1/32。試求所需的信息速率.解： bit信息速率 bit/s 在數(shù)字電視編碼中，若每幀為500行，每行劃分成600個(gè)像素，每個(gè)像素采用8電平量化，且每秒傳送30幀時(shí)，試求所需的信息速率。解：每個(gè)像素信息量為3 bit每秒傳輸30幀，即個(gè)像素 bit/s 帶寬為3 kHZ，信噪比為30 dB的電話系統(tǒng)，若傳送時(shí)間為3分鐘，試估計(jì)可能傳送話音信息的數(shù)目。解：=30dB=1000則R bit/s= Kb/s又傳送時(shí)間t=30分鐘=180 s信息量為= Mbit 若要以R=的速率通過一個(gè)帶寬為8 kHz、信噪比為31的連續(xù)信道傳送，可否實(shí)現(xiàn)解：根據(jù)SHANNON公式40 Kb/s當(dāng)連續(xù)信道為高斯信道時(shí)，C<R=，于是不可實(shí)現(xiàn)；然而信道為非高斯信道時(shí)，其信道容量小于C，因此不能判定它與R的大小關(guān)系，從而不能確定能否實(shí)現(xiàn)。第五章 離散信道編碼定理 設(shè)有一DMC，其轉(zhuǎn)移概率矩陣為若=1/2，=1/4，試求兩種譯碼準(zhǔn)則下的譯碼規(guī)則，并計(jì)算誤碼率。解：（1）最大后驗(yàn)概率譯碼準(zhǔn)則