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

信息論與編碼理論習(xí)題答案全解第二章信息量和熵2.2八元編碼系統(tǒng)，碼長(zhǎng)為3，第一個(gè)符號(hào)用于同步，每秒1000個(gè)碼字，求它的信息速率。解：同步信息均相同，不含信息，因此每個(gè)碼字的信息量為2?8log=2?3=6bit因此，信息速率為6?1000=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})(ap=366=61得到的信息量=)(1logap=6log=2.585bit(2)可能的唯一，為{6，6})(bp=361得到的信息量=)(1logbp=36log=5.17bit2.4經(jīng)過(guò)充分洗牌后的一副撲克（52張），問(wèn)：(a)任何一種特定的排列所給出的信息量是多少？(b)若從中抽取13張牌，所給出的點(diǎn)數(shù)都不相同時(shí)得到多少信息量？解：(a))(ap=!521信息量=)(1logap=!52log=225.58bit(b)???????花色任選種點(diǎn)數(shù)任意排列13413!13)(bp=1352134!13A?=1352134C信息量=1313524loglog-C=13.208bit2.9隨機(jī)擲3顆骰子，X表示第一顆骰子的結(jié)果，Y表示第一和第二顆骰子的點(diǎn)數(shù)之和，Z表示3顆骰子的點(diǎn)數(shù)之和，試求)|(YZH、)|(YXH、),|(YXZH、)|,(YZXH、)|(XZH。解：令第一第二第三顆骰子的結(jié)果分別為321,,xxx，1x，2x，3x相互獨(dú)立，則1xX=，21xxY+=，321xxxZ++=)|(YZH=)(3xH=log6=2.585bit)|(XZH=)(32xxH+=)(YH=2?(361log36+362log18+363log12+364log9+365log536)+366log6=3.2744bit)|(YXH=)(XH-);(YXI=)(XH-[)(YH-)|(XYH]而)|(XYH=)(XH，所以)|(YXH=2)(XH-)(YH=1.8955bit或)|(YXH=)(XYH-)(YH=)(XH+)|(XYH-)(YH而)|(XYH=)(XH，所以)|(YXH=2)(XH-)(YH=1.8955bit),|(YXZH=)|(YZH=)(XH=2.585bit)|,(YZXH=)|(YXH+)|(XYZH=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ù)字平均得到的信息量。解：8,6,4,2,0=i√);(YXI=)(YH-)|(XYH因?yàn)檩斎氲雀牛尚诺罈l件可知，=++++====101)8181818121(101)(101)(為偶數(shù)為奇數(shù)iiypiiyp即輸出等概，則)(YH=log10)|(XYH=)|(log)(ijjjiixypyxp∑∑-=)|(log)(ijjijixypyxp∑∑-偶-)|(log)(ijjijixypyxp∑∑奇=0-)|(log)(ijjijixypyxp∑∑奇=-)|(log)|()(97,5,3,1iiiiiixypxypxp∑=，-)|(log)|()(97531ijjiiijixypxypxp∑∑≠，，，，＝=101?21log2?5+101?21?41log8?4?5=4341+=1bit);(YXI=)(YH-)|(XYH=log10-1=log5=2.3219bit2.11令{821,,uuu，?}為一等概消息集，各消息相應(yīng)被編成下述二元碼字1u=0000，2u=0011，3u=0101，4u=0110，5u=1001，6u=1010，7u=1100，8u=1111通過(guò)轉(zhuǎn)移概率為p的BSC傳送。求：(a)接收到的第一個(gè)數(shù)字0與1u之間的互信息量。(b)接收到的前二個(gè)數(shù)字00與1u之間的互信息量。(c)接收到的前三個(gè)數(shù)字000與1u之間的互信息量。(d)接收到的前四個(gè)數(shù)字0000與1u之間的互信息量。解：即)0;(1uI，)00;(1uI，)000;(1uI，)0000;(1uI)0(p=4)1(81?-p+481?p=21)0;(1uI=)0()|0(log1pup=211logp-=1+)1log(p-bit)00(p=]2)1(4)1(2[8122pppp+-+-=41)00;(1uI=)00()|00(log1pup=4/1)1(log2p-=)]1log(1[2p-+bit)000(p=])1(3)1(3)1[(813223pppppp+-+-+-=81)000;(1uI=3[1+)1log(p-]bit)0000(p=])1(6)1[(814224pppp+-+-)0000;(1uI=42244)1(6)1()1(8logppppp+-+--bit2.12計(jì)算習(xí)題2.9中);(ZYI、);(ZXI、);,(ZYXI、)|;(XZYI、)|;(YZXI。解：根據(jù)題2.9分析)(ZH=2(216log2161+3216log2163+6216log2166+10216log21610+15216log21615+21216log21621+25216log21625+27216log21627)=3.5993bit);(ZYI=)(ZH-)|(YZH=)(ZH-)(XH=1.0143bit);(ZXI=)(ZH-)|(XZH=)(ZH-)(YH=0.3249bit);,(ZYXI=)(ZH-)|(XYZH=)(ZH-)(XH=1.0143bit)|;(XZYI=)|(XZH-)|(XYZH=)(YH-)(XH=0.6894bit)|;(YZXI=)|(YZH-)|(XYZH=)(XH-)(XH=0bit2.14對(duì)于任意概率事件集X,Y,Z，證明下述關(guān)系式成立(a))|,(XZYH≤)|(XYH+)|(XZH，給出等號(hào)成立的條件(b))|,(XZYH=)|(XYH+),|(YXZH(c)),|(YXZH≤)|(XZH證明：(b))|,(XZYH=-∑∑∑xyzxyzpxyzp)|(log)(=-∑∑∑xyzxyzpxypxyzp)]|()|(log[)(=-∑∑∑xyzxypxyzp)|(log)(-∑∑∑xyzxyzpxyzp)|(log)(=)|(XYH+)|(XYZH(c)),|(YXZH=-∑∑∑xyzxyzpxyzp)|(log)(=∑∑xyxyp)([-∑zxyzpxyzp)|(log)|(]≤∑∑xyxyp)([-∑zxzpxzp)|(log)|(]=-∑∑∑xyzxzpxyzp)|(log)(=)|(XZH當(dāng))|(xyzp=)|(xzp，即X給定條件下，Y與Z相互獨(dú)立時(shí)等號(hào)成立(a)上式(c)左右兩邊加上)|(XYH，可得)|(XYH+),|(YXZH≤)|(XYH+)|(XZH于是)|,(XZYH≤)|(XYH+)|(XZH2.28令概率空間???-=21,211,1X，令Y是連續(xù)隨機(jī)變量。已知條件概率密度為≤-<-=其他,022,41)|(xyxyp，求：(a)Y的概率密度)(yω(b));(YXI(c)若對(duì)Y做如下硬判決-≤??-≤<-??>??=1,111,01,1yyyV求);(VXI，并對(duì)結(jié)果進(jìn)行解釋。解：(a)由已知，可得)1|(-=xyp=???????≤<-??elsey01341)1|(=xyp=???????≤<-??elsey03141)(yω=)1(-=xp)1|(-=xyp+)1(=xp)1|(=xyp=?????????????≤<??≤<-??-≤<-??elseyyy0318111411381(b))(YHC=??---+?11134log4128log81=2.5bit)|(XYHC=?--=-=-=-13)1|(log)1|()1(dyxypxypxp-===-31)1|(log)1|()1(dyxypxypxp=dydy??----311341log412141log4121=2bit);(YXI=)(YHC-)|(XYHC=0.5bit(c)由)(yω可得到V的分布律再由)|(xyp可知5.14log2412log21)(=?+=VHbit2]2log212log21[21)|(?+=XVH=1bit);(VXI=)|()(XVHVH-=0.5bit2.29令)(1xQ和)(2xQ是同一事件集U上的兩個(gè)概率分布，相應(yīng)的熵分別為1)(UH和2)(UH。(a)對(duì)于10≤≤λ，證明)(xQ=λ)(1xQ+)1(λ-)(2xQ是概率分布(b))(UH是相應(yīng)于分布)(xQ的熵，試證明)(UH≥λ1)(UH+)1(λ-2)(UH證明：(a)由于)(1xQ和)(2xQ是同一事件集U上的兩個(gè)概率分布，于是)(1xq≥0，)(2xq≥0dxxqx)(1=1，dxxqx)(2=1又10≤≤λ，則)(xq=λ)(1xq+)1(λ-)(2xq≥0dxxqx)(=dxxqx)(1λ+dxxqx-)()1(2λ=1因此，)(xQ是概率分布。(b))(UH=dxxqxqxqxqx-+-+-)]()1()(log[)]()1()([2121λλλλ=dxxqxqxqx-+-)]()1()(log[)(211λλλdxxqxqxqx-+--)]()1()(log[)()1(212λλλ≥?-xdxxqxq)(log)(11λ?--xdxxqxq)(log)()1(22λ（引理2）=λ1)(UH+)1(λ-2)(UH第三章信源編碼——離散信源無(wú)失真編碼3.1試證明長(zhǎng)為N的D元等長(zhǎng)碼至多有1)1(--DDDN個(gè)碼字。證：①在D元碼樹(shù)上，第一點(diǎn)節(jié)點(diǎn)有D個(gè)，第二級(jí)有2D，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)碼字，若最長(zhǎng)碼有N，則函數(shù)有∑=NiiD1=DDDN--1)1(=1)1(--DDDN，此時(shí)，所有碼字對(duì)應(yīng)碼樹(shù)中的所有節(jié)點(diǎn)。②碼長(zhǎng)為1的D個(gè)；碼長(zhǎng)為2的2D個(gè)，…，碼長(zhǎng)為N的ND個(gè)∴總共∑=NiiD1=1)1(--DDDN個(gè)3.2設(shè)有一離散無(wú)記憶信源??=996.0,004.0,21aaU。若對(duì)其輸出的長(zhǎng)為100的事件序列中含有兩個(gè)或者少于兩個(gè)1a的序列提供不同的碼字。(a)在等長(zhǎng)編碼下，求二元碼的最短碼長(zhǎng)。(b)求錯(cuò)誤概率（誤組率）。解:(a)不含1a的序列1個(gè)長(zhǎng)為100的序列中含有1個(gè)1a的序列1100C=100個(gè)長(zhǎng)為100的序列中含有2個(gè)1a的序列2100C=4950個(gè)∴所需提供碼的總數(shù)M=1+100+4950=5051于是采用二元等長(zhǎng)編碼DMNloglog≥=12.3，故取N=13(b)當(dāng)長(zhǎng)度為100的序列中含有兩個(gè)或更多的1a時(shí)出現(xiàn)錯(cuò)誤，因此錯(cuò)誤概率為eP=-11000100)996.0(C-991100)996.0)(004.0(C9822100)996.0()004.0(C-=310775.7-?3.3設(shè)有一離散無(wú)記憶信源，U=???43,41,21aa，其熵為)(UH?？疾炱溟L(zhǎng)為L(zhǎng)的輸出序列，當(dāng)0LL≥時(shí)滿(mǎn)足下式εδ≤??≥-)()(UHLuIPLr(a)在δ=0.05，ε=0.1下求0L(b)在δ=310-，ε=810-下求0L(c)令T是序列Lu的集合，其中δ<-)()(UHLuIL試求L=0L時(shí)情況(a)(b)下，T中元素個(gè)數(shù)的上下限。解：)(UH=kkpplog∑-=34log434log41+=0.81bit)]([kaIE=)(UH2Iσ=})]()({[2UHaIEk-=])([2kaIE-)(2UH=∑-kkkUHpp)()(log22=0.471則根據(jù)契比雪夫大數(shù)定理εσσσ=≤??????>-22)()(LUHLuIPILr(a)L=22εσσI=2)05.0(1.0471.0?=1884(b)=L22εσσI=238)10(10471.0--?=4.711310?(c)由條件可知Lu為典型序列，若設(shè)元素個(gè)數(shù)為T(mén)M，則根據(jù)定理))(())((22)1(εεσ'+'-≤≤'-UHLTUHLM其中εσ='，σε='，可知(i)1.0=='εσ，05.0=='σε，1884=L下邊界：84..1431))((29.02)1(?='-'-εσUHL上邊界：))((2ε'+UHL=24..16202故24..162084..1431229.0≤≤?TM(ii)610-=='εσ，310-=='σε，111071.4?=L111081.3))((29999.02)1(?'-?='-εσUHL))((2ε'+UHL=111082.32?故11111082.31081.3229999.0??≤≤?TM3.4(a)各碼是否滿(mǎn)足異字頭條件？是否為唯一可譯碼？(b)當(dāng)收到1時(shí)得到多少關(guān)于字母a1的信息？(c)當(dāng)收到1時(shí)得到多少關(guān)于信源的平均信息？解：①碼A是異頭字碼，而B(niǎo)為逗點(diǎn)碼，都是唯一可譯碼。②碼A32.14.01log)()1|(log)1;(21121===apapaIbit碼B014.04.0log)1()()1,(log)1()()1()1|(log)1;(1121121=?===papappappapaIbit③碼AU=｛4321,,,aaaa｝∑==41)1;()1|()1;(kkkaIapuI=0)1;()1|(11+aIap=1.32bit=05.006.007.008.090.010.012.013.014.016.010*********aaaaaaaaaaU碼B∑==41)1;()1|()1;(kkkaIapuI=0bit（收到1后，只知道它是碼字開(kāi)頭，不能得到關(guān)于U的信息。）3.5令離散無(wú)記憶信源(a)求最佳二元碼,計(jì)算平均碼長(zhǎng)和編碼效率。(b)求最佳三元碼,計(jì)算平均碼長(zhǎng)和編碼效率。解：(a)0101010101010.050.060.070.080.090.100.120.130.140.110.230.150.160.190.270.310.580.42101010100001001110011011100100011101010111a2a3a4a5a6a7a8a9a10a∑-=kkppUHlog)(=3.234bit平均碼長(zhǎng)∑=kkknpn=3.26=DnRlog=效率%2.99log)()(===DnUHRUHη(b)0.160.140.130.120.100.090.080.070.060.05010120120120210.110.240.330.4311a2a3a4a5a6a7a8a9a10a0001021012202122110111平均碼長(zhǎng)∑=kkknpn=2.11DnRlog==3.344效率%6.96)(==RUHη3.6令離散無(wú)記憶信源?=2.0.....3.0...5.0.....3.........2.........1aaaU(a)求對(duì)U的最佳二元碼、平均碼長(zhǎng)和編碼效率。(b)求對(duì)U2的最佳二元碼、平均碼長(zhǎng)和編碼效率。(c)求對(duì)U3的最佳二元碼、平均碼長(zhǎng)和編碼效率。解：(a)0.50.30.210.501011a2a3a10001n=0.5×1+0.3×2+2×0.2=1.5∑=-=485.1log)(kkppUHbit%99)(==RUHη(b)∵離散無(wú)記憶∴H(U1U2)=2H(U)=2.97bitp(a1a1)=0.25,p(a1a2)=0.15,p(a1a3)=0.1,p(a2a1)=0.15,p(a2a2)=0.09p(a2a3)=0.06,p(a3a1)=0.1,p(a3a2)=0.06,p(a3a3)=0.040.250.150.150.10.10.090.060.060.0411aa21aa12aa31aa13aa22aa32aa23aa33aa1000101011011100000001011001110.10.150.20.250.30.450.55010110101010101132==∑kknpn5.122==nnDnUUHlog)(221=η=397.2=0.99(c)有關(guān)3U最佳二元類(lèi)似略3.7令離散無(wú)記憶信源=)()()(21..........2.........1ikapapapaaaU且0≤P(a1)≤P(a2)≤….≤P(ak)<1。定義Qi=∑-=11)(ikkap,i>1，而Q1=0，今按下述方法進(jìn)行二元編碼。消息ak的碼字為實(shí)數(shù)Qk的二元數(shù)字表示序列的截短（例如1/2的二元數(shù)字表示序列為1/2→10000…，1/4→0100…）,保留的截短序列長(zhǎng)度nk是大于或等于I(ak)的最小整數(shù)。(a)對(duì)信源??=161,161,161,161,81,81,41,41.....8......7.......6.......5......4......3.......2...1aaaaaaaaU構(gòu)造碼。(b)證明上述編碼法得到的碼滿(mǎn)足異字頭條件，且平均碼長(zhǎng)n滿(mǎn)足H(U)≤n≤H(U)+1。解：(a)(b)反證法證明異字頭條件令k<-2=""122+--≤≤k=""a=""i=""k=""n=""p=""q=""’，若k=""≤<--'2<=""從而得k=""又由1)()(+≤≤k=""可知，=""是k="">這與假設(shè)ka是ka'的字頭（即kkkpQQ+='）相矛盾，故滿(mǎn)足異字頭條件。由已知可得11log1log+<≤kkkpnp對(duì)不等號(hào)兩邊取概率平均可得∑∑∑+<≤kkkkkkkkkppnppp11log1log即1)()(+<≤UHnUH3.8擴(kuò)展源DMC，???=4.0,6.02.....1aaU(a)求對(duì)U的最佳二元碼、平均碼長(zhǎng)和編碼效率。(b)求對(duì)U2的最佳二元碼、平均碼長(zhǎng)和編碼效率。(c)求對(duì)U3的最佳二元碼、平均碼長(zhǎng)和編碼效率。(d)求對(duì)U4的最佳二元碼、平均碼長(zhǎng)和編碼效率。解：(a)01=C，2C=1，n=197.0)(=UHbit%97)(==RUHη(b)DMC信道11aa21aa12aa22aa00011011110.60.401010.360.240.240.1622=n，1=n，%97)(==nUHη(c)111aaa211aaa121aaa112aaa221aaa212aaa122aaa222aaa01111000001100101110011010.2160.1440.1440.1440.0960.0960.0960.0640.160.1920.2040.