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

1、第二章 信息量和熵2.2 八元編碼系統(tǒng)，碼長(zhǎng)為3，第一個(gè)符號(hào)用于同步，每秒1000個(gè)碼字，求它的信息速率。解：同步信息均相同，不含信息，因此 每個(gè)碼字的信息量為 2=23=6 bit 因此，信息速率為 61000=6000 bit/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.585 bit (2) 可能的唯一，為 6，6 = 得到的信息量=5.17 bit2.4 經(jīng)過(guò)充分洗牌后的一副撲克（52張），問(wèn)：(a) 任何一種特定的排列所給出的信息量是多

2、少？(b) 若從中抽取13張牌，所給出的點(diǎn)數(shù)都不相同時(shí)得到多少信息量？解：(a) = 信息量=225.58 bit (b) = 信息量=13.208 bit2.9 隨機(jī)擲3顆骰子，X表示第一顆骰子的結(jié)果，Y表示第一和第二顆骰子的點(diǎn)數(shù)之和，Z表示3顆骰子的點(diǎn)數(shù)之和，試求、。 解：令第一第二第三顆骰子的結(jié)果分別為，相互獨(dú)立，則， =6=2.585 bit = =2(36+18+12+9+)+6 =3.2744 bit =-=- 而=，所以= 2-=1.8955 bit 或=-=+- 而= ，所以=2-=1.8955 bit=2.585 bit=+=1.8955+2.585=4.4805 bit2.

3、10 設(shè)一個(gè)系統(tǒng)傳送10個(gè)數(shù)字，0，1，9。奇數(shù)在傳送過(guò)程中以0.5的概率錯(cuò)成另外一個(gè)奇數(shù)，其余正確接收，求收到一個(gè)數(shù)字平均得到的信息量。 解：=-因?yàn)檩斎氲雀?，由信道條件可知，即輸出等概，則=10= =- =0- = - =25+845 =1 bit=-=10 -1=5=2.3219 bit2.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

4、與之間的互信息量。(d)接收到的前四個(gè)數(shù)字0000與之間的互信息量。解：即， =+= =1+ bit = = bit = =31+ bit = = bit2.12 計(jì)算習(xí)題2.9中、。解：根據(jù)題2.9分析=2(+) =3.5993 bit =-=-=1.0143 bit =-=-=0.3249 bit =-=-=1.0143 bit =-=-=0.6894 bit =-=-=0 bit2.14 對(duì)于任意概率事件集X,Y,Z，證明下述關(guān)系式成立 (a)+，給出等號(hào)成立的條件 (b)=+ (c) 證明：(b) =- =- =- =+ (c) =- =- - =- = 當(dāng)=，即X給定條件下，Y與Z相

5、互獨(dú)立時(shí)等號(hào)成立 (a) 上式(c)左右兩邊加上，可得+于是+2.28 令概率空間，令Y是連續(xù)隨機(jī)變量。已知條件概率密度為 ，求： (a)Y的概率密度 (b) (c) 若對(duì)Y做如下硬判決 求，并對(duì)結(jié)果進(jìn)行解釋。 解：(a) 由已知，可得= = =+ = (b) =2.5 bit = = =2 bit =-=0.5 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 = 0.5 bit2.29 令和是同一事件集U上的兩個(gè)概率分布，相應(yīng)的熵分別為和。 (a)對(duì)于，證明=+是概率分布

6、 (b)是相應(yīng)于分布的熵，試證明+ 證明：(a) 由于和是同一事件集U上的兩個(gè)概率分布，于是0，0 =1，=1 又，則=+0 =+=1 因此，是概率分布。 (b) = = （引理2） =+第三章 信源編碼離散信源無(wú)失真編碼 3.1 試證明長(zhǎng)為的元等長(zhǎng)碼至多有個(gè)碼字。證：在元碼樹(shù)上，第一點(diǎn)節(jié)點(diǎn)有個(gè)，第二級(jí)有，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)碼字，若最長(zhǎng)碼有，則函數(shù)有=，此時(shí)，所有碼字對(duì)應(yīng)碼樹(shù)中的所有節(jié)點(diǎn)。碼長(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ò)

7、誤概率（誤組率）。解: (a)不含的序列 1個(gè)長(zhǎng)為100的序列中含有1個(gè)的序列 =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è)或更多的時(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.81 bit =-= =0.471則根據(jù)契比雪夫大數(shù)定理(a) =188

8、4(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(niǎo)為逗點(diǎn)碼，都是唯一可譯碼。碼A bit碼B bit碼A U= =1.32 bit 碼B =0 bit（收到1后，只知道它是碼字開(kāi)頭，

9、不能得到關(guān)于U的信息。）3.5 令離散無(wú)記憶信源(a) 求最佳二元碼,計(jì)算平均碼長(zhǎng)和編碼效率。(b) 求最佳三元碼,計(jì)算平均碼長(zhǎng)和編碼效率。解：(a) =3.234 bit平均碼長(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.5 bit (b) 離散無(wú)記憶 H(UU)=2H(U)=2.97 bitp(aa)=0.25, p(a

10、a)=0.15, p(aa)=0.1, p(aa)=0.15, p(aa)=0.09 p(aa)=0.06, p(aa)=0.1, p(aa)=0.06, p(aa)=0.04=0.99(c) 有關(guān)最佳二元類似 略3.7 令離散無(wú)記憶信源且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）,保留的截短序列長(zhǎng)度n是大于或等于I(a)的最小整數(shù)。(a) 對(duì)信源構(gòu)造碼。(b) 證明上述編碼法得到的碼滿足異字頭條件，且平均碼長(zhǎng)滿足H(U)

11、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，=1 bit(b) DMC信道，(c)=2.944 =0.981=98.85%(d) 略3.9 設(shè)

12、離散無(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編碼思想（

13、必定占滿整個(gè)碼樹(shù)），即從而，c） =3.12 設(shè)二元信源的字母概率為，。若信源輸出序列為 1011 0111 1011 0111 (a) 對(duì)其進(jìn)行算術(shù)編碼并進(jìn)行計(jì)算編碼效率。 (b) 對(duì)其進(jìn)行LZ編碼并計(jì)算編碼效率。解：(a) 根據(jù)遞推公式 可得如下表格其中，F(xiàn)(1)=0， F(1)= ， p(0)=， p(1)=101011011110110111 從而 C = (b) 首先對(duì)信源序列進(jìn)行分段：1 0 11 01 111 011 0111然后對(duì)其進(jìn)行編碼，編碼字典如下所示段號(hào)短語(yǔ)ij編碼11010001200000003111100114012101015111310111601141100

14、170111611101 bit3.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ù)字）輸出二元碼字10100100000001000000000127800000001001001111 (a)求H(U)。 (b)求對(duì)于每個(gè)中間數(shù)字相應(yīng)

15、的信源數(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) bit(d) 異字碼頭 第四章 信道及信道容量4.1 計(jì)算由下述轉(zhuǎn)移概率矩陣給定的DMC的容量。(a) 它是一對(duì)稱信道，達(dá)到C需要輸入等概

16、，即=C bit/符號(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)4.5 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)同理可得從而

17、(a)(b)因此與無(wú)關(guān)。由于與無(wú)關(guān)，因此，C=0。4.8 一PCM語(yǔ)音通信系統(tǒng)，已知信號(hào)帶寬W=4000 Hz，采樣頻率為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è)像素信息量為3 bit每秒傳輸30幀，即個(gè)像素 bit/s4.10 帶寬為3 kHZ，信噪比為30 dB的電話系統(tǒng)，若傳送時(shí)間為3分鐘，試估計(jì)可能傳送話音信息的數(shù)目。解：=30dB=1000則R bit/s=29.9 Kb/s又傳送時(shí)間t=30分鐘=180 s信息量為29.9180=5.382 Mbit4.12 若要以R=的速率通過(guò)一個(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)。第五章 離散信道編碼定理5.1 設(shè)有一DMC，其轉(zhuǎn)移概率矩陣為若=1/2，=1/4，試求兩種譯碼準(zhǔn)則下的譯碼規(guī)則，并計(jì)算誤碼率。解：（1）最大后驗(yàn)概率譯碼準(zhǔn)則首先計(jì)算 譯碼規(guī)則為 （2