第二章信息量和嫡八元編碼系統(tǒng)，碼長為3,第一個符號用于同步，每秒1000個碼字，求它的信息速率。解：同步信息均相同，不含信息，因此每個碼字的信息量為2log8=23=6bit因此，信息速率為61000=6000bit/s擲一對無偏骰子，告訴你得到的總的點(diǎn)數(shù)為：(a)7;(b)12。問各得到多少信息量。解：(1)可能的組合為{1,6},{2,5},{3,4},{4,3},{5,2},{6,1}61p(a)==—3661得到的信息重=log=log6=2.585bitP(a)(2)可能的唯一，為{6,6}1p(b)=361得到的信息重=log=log36=5.17bitp(b)經(jīng)過充分洗牌后的一副撲克(52張)，問：(a)任何一種特定的排列所給出的信息量是多少？(b)若從中抽取13張牌，所給出的點(diǎn)數(shù)都不相同時得到多少信息量?1解：(a)p(a)=-52!1信息重=log=log52!=225.58bitP(a)13!13種點(diǎn)數(shù)任意排列TOC\o"1-5"\h\z(b)13413花色任選13413413p(b)=13=T1TA52C52信息量=logC53log413=13.208bit隨機(jī)擲3顆骰子，X表示第一顆骰子的結(jié)果，Y表示第一和第二顆骰子的點(diǎn)數(shù)之和，Z表示3顆骰子的點(diǎn)數(shù)之和，試求H(Z|Y)、H(X|Y)、H(Z|X,Y)、H(X,Z|Y)、H(Z|X)o解：令第一第二第三顆骰子的結(jié)果分別為Xl,X2,X3,Xi,X2,X3相互獨(dú)立,則XX1,YX1x2,ZX1x2x3H(Z|Y)=H(x3)=log6=2.585bitH(Z|X)=H(X2X3)=H(Y)=2(—log36+—log18+—log12+—log9+—log—)+—log63636363636536=3.2744bitH(X|Y)=H(X)-I(X;Y)=H(X)-[H(Y)-H(Y|X)]fMH(Y|X)=H(X),所以H(X|Y)=2H(X)-H(Y)=1.8955bit或H(X|Y)=H(XY)-H(Y)=H(X)+H(Y|X)-H(Y)而H(Y|X)=H(X),所以H(X|Y)=2H(X)-H(Y)=1.8955bitH(Z|X,Y)=H(Z|Y)=H(X)=2.585bitH(X,Z|Y)=H(X|Y)+H(Z|XY)=1.8955+2.585=4.4805bit設(shè)一個系統(tǒng)傳送10個數(shù)字，0,1,…，9。奇數(shù)在傳送過程中以0.5的概率錯成另外一個奇數(shù)，其余正確接收，求收到一個數(shù)字平均得到的信息量。解：TOC\o"1-5"\h\zX-YM信道ai1,3,5,7,91Xi0,2,4,6,8VI(X;Y)=H(Y)-H(Y|X)因?yàn)檩斎氲雀?，由信道條件可知，

1p(yii為司數(shù))一10p(yii為偶數(shù))—(1111-)—102888810即輸出等概，則H(Y)=log10H(Y|X)=p(Xiyj)logp(yj|x)p(xyj)10gp(yj|x)-p(Xiyj)10gp(yj|x)ji偶ji奇=0-p(Ky=0-p(Kyj)10gp(yj|x。i奇p(Xi)p(y|x)10gp(y|x)-1,3,5,7,91p(Xi)p(y|x)10gp(y|x)-1,3,5,7,91p(xjp(yj|為)10gp(yj|x)iji=1,3,5,7,9——log25+—13=1bit4411log84524I(X;Y)=H(Y)-H(Y|X)=log10-1=1og5=2.3219bit令｛Ui,U2,,凡｝為一等概消息集，各消息相應(yīng)被編成下述二元碼字5=0000,u2=0011,u3=0101,u4=0110,U5=1001,U6=1010,U7=1100,U8=1111通過轉(zhuǎn)移概率為p的BSC傳送。求：(a)接收到的第一個數(shù)字0與ui之間的互信息量。(b)接收到的前二個數(shù)字00與3之間的互信息量⑹接收到的前三個數(shù)字000⑹接收到的前三個數(shù)字000與Ui之間的互信息量。(d)接收到的前四個數(shù)字(d)接收到的前四個數(shù)字0000與U1之間的互信息量。解:

解:即I(u1;0),I(u1;00),I(u1;000),I(u1;0000)一1〃、，1,1p(0)=-(1p)4+-p4=-882I(Ui；0)=logI(Ui；0)=logp(0|ujp(0),1p=log—2=1+log(1p)bit1~p(00)=[2(181~p(00)=[2(18、2，?、p)4(1p)p2p2]=14I(Ui；00)I(Ui；00)=logp^jqp(00)舟=2[1l0gibit132231p(000)=-[(1p)33(1p)2p3(1p)p2p3]=-88I(uiI(ui；000)=3[1+log(1P)]bit1_..Ap(0000)=-[(1p)1_..Ap(0000)=-[(1p)4

86(1p)2p24-1p]I(u1;0000)=logI(u1;0000)=log48(1p)422(1p)46(1p)2p2—bitp2.12計算習(xí)題2.12計算習(xí)題2.9中I(Y;Z)、I(X;Z)、I(X,Y;Z)、I(Y;Z|X)、I(X;Z|Y)0解：根據(jù)題2.9分析?解：根據(jù)題2.9分析?1.…3,H(Z)=2(2i6log216+236log216一+321610g和+也10g純+

62161015216212162521627216—log—+log—+log+log)21615216212162521627=3.5993bitI(Y;Z)=H(Z)-H(Z|Y)=H(Z)-H(X)=1.0143bitI(X;Z)=H(Z)-H(Z|X)=H(Z)-H(Y)=0.3249bitI(X,Y;Z)=H(Z)-H(Z|XY)=H(Z)-H(X)=1.0143bitI(Y;Z|X)=H(Z|X)-H(Z|XY)=H(Y)-H(X)=0.6894bitI(X;Z|Y)=H(Z|Y)-H(Z|XY)=H(X)-H(X)=0bit2.14對于任意概率事件集X,Y,Z,證明下述關(guān)系式成立(a)H(Y,Z|X)H(Y|X)+H(Z|X),給出等號成立的條件(b)H(Y,Z|X)=H(Y|X)+H(Z|X,Y)(c)H(Z|X,Y)H(Z|X)證明：(b)H(Y,Z|X)=-p(xyz)logp(yz|x)xyz=-p(xyz)log[p(y|x)p(z|xy)]xyz=-p(xyz)logp(y|x)-p(xyz)logp(z|xy)xyzxyz=H(Y|X)+H(Z|XY)(c)H(Z|X,Y)=-p(xyz)logp(z|xy)xyz=p(xy)[-p(z|xy)logp(z|xy)]xyzp(xy)[-p(z|x)logp(z|x)]xyz=-p(xyz)logp(z|x)xyz=H(Z|X)當(dāng)p(z|xy)=p(z|x),即X給定條件下，Y與Z相互獨(dú)立時等號成立(a)上式(c)左右兩邊加上H(Y|X),可得H(Y|X)+H(Z|X,Y)H(Y|X)+H(Z|X)于是H(Y,Z|X)H(Y|X)+H(Z|X)1.12.28令概率空間X11，令Y是連續(xù)隨機(jī)變量。已知條件概率密度為2,214,2yxp(y|x)0,k2,求:(a)Y的概率密度(y)(b)I(X;Y)⑹若對Y做如下硬判決1,V0,1,求I(X;V),并對結(jié)果進(jìn)行解釋。解：(a)由已知,可得p(y|x1)=elsep(y|x1)=40else(y)=p(x1)p(yIx1)+p(x1)p(y|x1)1814180else一、1(U)Hc(Y)=-813log8log4=2.5bitHc(Y|X)=p(x11)3P(y|x31)logp(y|x1)dy3p(x1)1P(y|x1)iogp(y|x1)dy111「1」1一一log—dy—234421,1,Mdy=2bitI(X;Y)=Hc(Y)-Hc(Y|X)=0.5bit(c)由(y)可得到V的分布律V-101p1/41/21/4再由p(y|x)可知V-101P(V|x=-1)1/21/20P(V|x=1)01/21/2TOC\o"1-5"\h\z1…H(V)-log2—2log41.5bit411H(V|X)[log2-log2]2=1bit22I(X;V)=H(V)H(V|X)=0.5bit2.29令Qi(x)和Q2(x)是同一事件集U上的兩個概率分布，相應(yīng)的嫡分別為H(U)1和H(U)2。(a)對于01,證明Q(x)=Qi(x)+(1)Q2(x)是概率分布(b)H(U)是相應(yīng)于分布Q(x)的嫡，試證明H(U)H(U)i+(1)H(U)2證明：(a)由于Qi(x)和Q2(x)是同一事件集U上的兩個概率分布，于是q1(x)0,q2(x)0q[(x)dx=1,q2(x)dx=1TOC\o"1-5"\h\zxx又01,則q(x)=q1(x)+(1)q2(x)0q(x)dx=q1(x)dx+(1)q2(x)dx=1xxx因此，Q(x)是概率分布。H(U)=[q[(x)(1)q2(x)]log[q[(x)(1)q2(x)]dxxq1(x)log[q[(x)(1)qz(x)]dx(1)q2(x)log[qi(x)(1)q2(x)]dxxqi(x)logqi(x)dx(1)q2(x)logq2(x)dx(引理2)xx=H(U)i+(1)H(U)2第三章信源編碼一一離散信源無失真編碼試證明長為N的D元等長碼至多有D(DN%1個碼字。證：①在D元碼樹上，第一點(diǎn)節(jié)點(diǎn)有D個，第二級有D2,每個節(jié)點(diǎn)對應(yīng)一TOC\o"1-5"\h\z個碼字，若最長碼有N,則函數(shù)有NDi=D(1dn)=D(DN1),此i11DD1時，所有碼字對應(yīng)碼樹中的所有節(jié)點(diǎn)。②碼長為1的D個；碼長為2的D2個，…，碼長為N的DN個NN???總共Di=^(^—個1D1設(shè)有一離散無記憶信源Ua1,a2。若對其輸出的長為100的事件序0.004,0.996列中含有兩個或者少于兩個a1的序列提供不同的碼字。(a)在等長編碼下，求二元碼的最短碼長。(b)求錯誤概率(誤組率)。解：(a)不含21的序列1個長為100的序列中含有1個a1的序列C；0o=100個長為100的序列中含有2個a1的序列。2)0=4950個「?所需提供碼的總數(shù)M=1+100+4950=5051于是采用二元等長編碼N國M=12.3,故取N=13logD(b)當(dāng)長度為100的序列中含有兩個或更多的a1時出現(xiàn)錯誤，因此錯誤概率為

Pe=1Ci0)0(0.996)-C；00(0.004)(0.996)C點(diǎn)(0.004)-/-/3=7.77510a1，a2設(shè)有一離散無記憶信源，U=13，其嫡為H(U)0考察其長為L的輸出4,4序列，當(dāng)LLo時滿足下式Pr■I^h(u)(a)在=0.05,=0.1下求L0(b)在=10(a)l=t=ot^=18842I0.47113(b)L2=8FT(a)l=t=ot^=18842I0.47113(b)L2=8FT=4.711010(10)(c)令T是序列Ul的集合，其中|KUl)HULH(U)試求L=Lo時情況(a)(b)下，T中元素個數(shù)的上下限134斛：H(U)=pklogpk=log4log=0.81bit443E[I(ak)]=H(U)I2=E{[I(aQH(U)]2}=E[I(ak)2]-H2(U)Pk(logPk)2H2(U)k=0.471則根據(jù)契比雪夫大數(shù)定理PrPr哈H(U)(c)由條件可知Ul為典型序列，若設(shè)元素個數(shù)為Mt,則根據(jù)定理(1)2L(H(U))Mt2L(H(U))其中，(i),可知0.1,0.05,L1884下邊界：L(H(U))1431..84(1)20.92上邊界：2L(H(U))=21620.24故0.921431-84Mt21620-24)106,103,L4.711011(1)2L(H(U))0.999923.8110112L(H(U))=23.821011故0.999923.811011Mt23.8210113.4對于有4字母的離散無記憶信源有兩個碼A和碼B,參看題表。字母概率碼A碼Ba10.411a20.30110a30.2001100a40.100011000(a)各碼是否滿足異字頭條件？是否為唯一可譯碼？(b)當(dāng)收到1時得到多少關(guān)于字母a/勺信息？(c)當(dāng)收到1時得到多少關(guān)于信源的平均信息？解：①碼A是異頭字碼，而B為逗點(diǎn)碼，都是唯一■可譯碼。TOC\o"1-5"\h\z②碼AI(a1;1)log2p(a1⑴log2—1.32bit

p(a1)0.4p(a1|1)p⑴,p(a1,1),0.4BBI(a1;1)log2log2log0bitp(a1)p⑴p(a1)p(1)0.41

③碼AU={a1,a2,a3,a4}4I(u;1)p(ak|1)I(ak；1)=p(ai|1)I(ai；1)0=1.32bitk14碼BI(u;1)p(ak11)I(ak；1)=0bitk1(收到1后，只知道它是碼字開頭，不能得到關(guān)于U的信息。)3.5令離散無記憶信源Uqa2a3電a5a6a7a8a9引0.160.140.130.120.100.900.080.070.060.05(a)求最佳二元碼，計算平均碼長和編碼效率。(b)求最佳三元碼，計算平均碼長和編碼效率。解：(a)0000100111001101110010001110101011H(U)pklogpk=3.234bit平均碼長npknk=3.26=RnlogDk效率HIU2H(U)99.2%RnlogD(b)0.430.24.0.33.12“Q1、1112“Q1、1100ai01a202a310a412a520a621a?22a8110a9111a100.160.140.130.120.100.090.080.070.06—010.05—平均碼長npknk=2.11kRnlogD=3.344效率HU)96.6%

R3.6令離散無記憶信源3.6令離散無記憶信源Ua1.........a2.........a3....0.5...0.3…..0.2(a)求對U的最佳二元碼、平均碼長和編碼效率。2…一一一…一(b)求對U的最佳二元碼、平均碼長和編碼效率3(c)求對U的最佳二元碼、平均碼長和編碼效率,解：(a)010.50100n=0.5X+0.32+2X0.2=1.5H(U)pH(U)pklogpk1.485bit喈99%(b)v離散無記憶H(U1U2)=2H(U)=2.97bitp(a1al)=0.25,p(a1a2)=0.15,p(a1a3)=0.1,p(a2al)=0.15,p(a2a2)=0.09p(a2a3)=0.06,p(a3al)=0.1,p(a3a2)=0.06,p(a3a3)=0.04n2n210a1al001aia2010a2al110艇111a3al0000a2a20001a2a30110a3a20111a3a3p^k31.5H(U1U2)_2.97

n2logD3=0.99(c)有關(guān)U3最佳二元類似略3.7令離散無記憶信源Uai.........a2..........akp(ai)p(a2)p(ai)i1且0WP(a)WP夠0???.wPR^I。定義Qi=p(ak),i>1,而Q1=0,今按k1下述方法進(jìn)行二元編碼。消息ak的碼字為實(shí)數(shù)Qk的二元數(shù)字表示序列的截短(例如1/2的二元數(shù)字表示序列為1/2一10000…，1/4-0100…)，保留的截短序列長度nk是大于或等于I(ak)的最小整數(shù)。(a)對信源Ua1...a2.......a3…...a4…...a5.......a6…....a7…...a8.....%,%/8,%%6,%6%6,116構(gòu)造碼(b)證明上述編碼法得到的碼滿足異字頭條件，且平均碼長n滿足H(U)<n<H(U)+1解：(a)符號QiLCa8040000a711640001a61840010a531640011a41440100a3383011a248210a134211(b)反證法證明異字頭條件令k<k',若ak是ak的字頭，則QkQk2nk又由I(ak)nkI(ak)1可知,2nkPk2nk1從而得QkQk2nkPk這與假設(shè)ak是ak的字頭(即QkQkPk)相矛盾，故滿足異字頭條件。由已知可得log—Pknlog—Pknklog—Pk對不等號兩邊取概率平均可得,1Pk,1Pklog——kPkPknk.1,Pklog——1

Pk即H(U)nH(U)13.8即H(U)nH(U)13.8擴(kuò)展源DMC,Ua1.....a20.6,0.4(a)求對U的最佳二元碼、平均碼長和編碼效率。2…、，、(b)求對U的最佳二元碼、平均碼長和編碼效率。3⑹求對U的最佳二元碼、平均碼長和編碼效率。4(d)求對U的最佳二元碼、平均碼長和編碼效率。解：(a)C10,C2=1,n=1(b)H(U)0.97bit加97%RDMC信道00011011a1ala〔a2a24a2a20.36——0.24——0.2400.16——12e冏aa2e冏aa〔a22*1aza小a〔a2a2a2a1a2a2a2a1a2a2a2n22,n1,H^U)97%n(c)0111100000110010111001101n3=2.944n=0.981=98.85%3.9(d)略設(shè)離散無記憶信源UHuffman編碼。a1,.....a2,....a3,......a4,..—,...%0.3,..0.2,..0.15,..0.15,..0.1,..0.1試求其二元和三元解:0.40.30.601110000011001010.30.20.20.150.15a50.1—0a60.1—1100010220213.11設(shè)信源有K個等概的字母，其中K=2j,12。今用Huffman編碼法進(jìn)行二元編碼。(a)是否存在有長度不為j或j+1的碼字，為什么？(b)利用和j表示長為j+1的碼字?jǐn)?shù)目。(c)碼的平均長度是多少？解：Huffman思想：將概率小的用長碼，大的用短碼，保證n當(dāng)?shù)雀艜r，趨于等長碼。a)對1時，K=2j,則用長度為j碼表示；當(dāng)2時，用K=2巾，用長度為j+1碼表示。平均碼長最短，則當(dāng)12時，則介于兩者之間，即只存在j,j+1長的碼字。b)設(shè)長為j的碼字個數(shù)為Nj,長度為j+1的碼字?jǐn)?shù)目為Nj+1,根據(jù)二元Huffman編碼思想(必定占滿整個碼樹)，即NjNj1K2jTOC\o"1-5"\h\zNj2jNj12(j1)1從而Nj(2)2j,Nj1(1)2j1、-112c)LNjjNj1(j1)=j2—KK、_,13.、―—3.12設(shè)二兀信源的字母概率為p(0)-,p(1)—。若信源輸出序列為441011011110110111(a)對其進(jìn)行算術(shù)編碼并進(jìn)行計算編碼效率。(b)對其進(jìn)行LZ編碼并計算編碼效率。解：12431&12(a)p(s)443I，-r—t--rF(ui1)F(ui)p(ui)F(Ui1)根據(jù)遞推公式『T可得如下表格p(Ui1)p(Ui)p(Ui1)其中，F(xiàn)(1)=0,F(1)=%,p(0)=%,p(1)=34Uip(Ui)F(G)1013414044161T1_916464193276442560334513446

135不136不137不03740138411139412039413131041413114151312不15081251354160.0101100111100100從而C=1,,3.4H(U)

H(U)

R99.85%44399.85%13

16(b)首先對信源序列進(jìn)行分段：1011011110110111然后對其進(jìn)行編碼，編碼字典如下所示段號短語ij編碼11011000120000000311110011401210101

511131011160114110017011161110117nlogD---r一74416TOC\o"1-5"\h\z134...H(U)log4-log0.8113bit443生(〃46.36%

R3.13&DMSUjU=.a1.....…a2..…a3…a4，各a.相應(yīng)編成碼字0、10、110和1110。3.131111i2,..4「8,..8試證明對足夠長的信源輸出序列，相應(yīng)的碼序列中0和1出現(xiàn)的概率相等。解：概率信源符號碼字1/2a101/4a2101/8a31101/8a41110設(shè)信源序列長為N,則相應(yīng)碼字長為（條件是N要足夠長）相應(yīng)碼序列中0出現(xiàn)的次數(shù)L0一L11p(0)=T=2p(1)=1-p(0)=23.14設(shè)有一DMS,U=3.14設(shè)有一DMS,U=010.90.1米用如下表的用長編碼法進(jìn)行編碼信源輸出序列0用長度(或中間數(shù)字)輸出二元碼字1000000110001001…2…0010…00000001701110000000081(a)求H(U)。(b)求對于每個中間數(shù)字相應(yīng)的信源數(shù)字的平均長度n1(c)求每個中間數(shù)字對應(yīng)的平均長度不7。(d)說明碼的唯一可譯性。解：(a)H(U)0.9log0.90.1log0.10.469bit由已知可得下表先驗(yàn)概率信源輸出序列0節(jié)長度(或中間數(shù)字)輸出二元碼字0.11000000.0901100010.081001200100.07290001300110.0656r00001401000.059000001501010.0531I0000001601100.0478F00000001701110.430500000000181(b)n110.120.980.43055.6953bit(c)n210.43054(10.4305)2.7085bit(d)異字碼頭第四章信道與信道容量計算由下述轉(zhuǎn)移概率矩陣給定的DMC的容量。pp0(a)01ppp01p,「它是一對稱信道，達(dá)到C需要輸入等概，即p=13Clog3p(jk)logp(jk)log3(1p)log(1p)plogplog3H(p)Ht/符號(b)1p1p2(b)1p1p22pP.22pE221p1p22它是一對稱信道10gzpcpiPc2log22它是一對稱信道10gzpcpiPc2log222_1pp2(1p)logplog-p1H(p)Ht/符號1pp0(c)p1p0001它是分信道1P0和1的和信道

p1pCilog2(1p)log(1p)1H(p)C20由2c由2c2c12c2，可知Clog121H(p)bit/符號4.3求圖中DMC的容量與最佳輸入分布(a)(b)(a)(b)解：(a)由圖知■,■發(fā)送符號1時等概率收到0,1,2,「?傳對與傳錯概率完全相同，即不攜帶任何信息量，于是信道簡化為二元純刪除信道14131141314013343/43/4C1q11/43/4Ht/符號(b)由圖知丫為準(zhǔn)對稱「?當(dāng)輸入等概，即Q「?當(dāng)輸入等概，即Q。Q1Q211時達(dá)到信道容量3此時01113334.5?.CI(x0,Y)p(j0)log111=1log31log31log34.5?.CI(x0,Y)p(j0)log111=1log31log31log3323231993N個相同的BSC級聯(lián)如圖。p(j0)23-log3bit/符號32XXXXn各信道的轉(zhuǎn)移概率矩陣P1P。令Qp{Xt0},t0,1,小，且、0為1pp已知。(a)求Qt的表達(dá)式。(b)證明N時有Qn1/2,且與Q0取值無關(guān)，從而證明N時的級聯(lián)信道容量Cn0(p0)解：N個信道級聯(lián)后BSC可表示為1P1Pn1N個級聯(lián)可以看成N-1個級聯(lián)后與第N個級聯(lián)一pN(1Pn1)PPn1(1P)Pn1(12p)p同理可得PnpN2(12p)pPnPn3(12p)pP2Pi(12p)pPi從而PnPn1(1[pN2(1pN2(12p)2p)2p)2Pp](12p)(1pN3(12p)P(1N12p)(122p)2p)2P(12p)p(12p)iN1p(12p)ii01(12p)NP1(12p)1(12p)N2(a)QnQ0(1Pn)(1Q0)pN(b)NimQn(12Q°)Pn(12Qo)1(12p)NNimQo(11(12p)N2Qo)--———2Qo因此與Q0無關(guān)由于QnP{Xn0},1P{Xo0}(1Pn)P{Xo1}Pn-21與p{x00}Q0無關(guān)，因此pN-,C=0O4.8-PCM語音通信系統(tǒng)，已知信號帶寬W=4000Hz,采樣頻率為2W,且采用8級幅度量化,各級出現(xiàn)白向概率為1/2,1/4,1/8,1/16,1/32,1/32,1/32,1/32。試求所需的信息速率.?111119一一解：H(V)pklogpklog2log4log8log16410g32bitk24816324..信息速率RfsH(V)8000918000bit/s在數(shù)字電視編碼中，若每幀為500行，每行劃分成600個像素，每個像素采用8電平量化，且每秒傳送30幀時，試求所需的信息速率。解：每個像素信息量為Ilog83bit每秒傳輸30幀，即305006009106個像素R910632.7107bit/s帶寬為3kHZ,信噪比為30dB的系統(tǒng)，若傳送時間為3分鐘，試估計可能傳送話音信息的數(shù)目。解：(制B=30dB=103=1000…...S.則CWlog(1—)3000log(11000)Rbit/s=29.9Kb/s又傳送時間