(完整版)信息论第五章答案

51设信源P(X)xxxx12340.20.190.180.17xx560.150.1x70.013.145.2对信源P(X)」x0.23.145.2对信源P(X)」x0.2x20.19x30.18x40.17x50.15x60.10.01X7l编二进制费诺码，计算编码效率。求信源熵H(X)；编二进制香农码；计算平均码长和编码效率。解：(1)H(X)=-£p(x)logp(x)i2ii=1=-(0.2xlog0.2+0.19xlog0.19+0.18xlog0.18+0.17xlog0.172222+0.15xlog0.15+0.1xlog0.1+0.01xlog0.01)222=2.609bit/symbolxp(x)p(x.)k码字x10.203000x20.190.23001x30.180.393011x40.170.573100x50.150.743101x60.10.8941110x70.010.9971111110(3)K=£kp(x)=3x0.2+3x0.19+3x0.18+3x0.17+3x0.15+4x0.1+7x0.01iii=3.14H(X)H(X)2.609=83.1%耳==83.1%R解：xp(x)编码码字kx10.200002x20.19100103x30.1810113x40.1710102x50.15101103x60.11011104x70.01111114K=£kp(x)=2x0.2+3x0.19+3x0.18+2x0.17+3x0.15+4x0.1+4x0.01iii=2.74竺=竺=2609=95.2%RK2.74(3)(3)5.3对信源P(X)」xx120.20.19x30.18x40.170.150.10.01“7!＞编二进制和三进制哈夫曼码，计算各自的平均码长和编码效率。解：二进制哈夫曼码：X.p(xi)编码码字kS610.6100.391s40.3500.261X0.20102x0.191112XQ0.18000030.1710013x40.15001030.111X60.10011040.01101114K=Ykp(x)=2x0.2+2x0.19+3x0.18+3x0.17+3x0.15+4x0.1+4x0.01iii=2.72HX=HB)=如=95.9%RK2.72三进制哈夫曼码：XP(Xi)编码码字ks10.540s0.261X10.2221X0.190002X0.1810120.172022X40.150102X60.111120.012122K=工kp(x)=lx0.2+2X(0.19+0.18+0.17+0.15+0.1+0.01)iii=1.8n=HX)=严(X)=2.609=91.4%RK、1.8xlog3logm2L2—X—<xxxxxxxx5.4设信源=V1112131415161718]P(X)]、248163264128128J求信源熵H(X)；编二进制香农码和二进制费诺码；计算二进制香农码和二进制费诺码的平均码长和编码效率编三进制费诺码；计算三进制费诺码的平均码长和编码效率；解：(1)H(X)=-fp(卩叫p3)i=1=—xlog2+—xlog4+—xlog8+xlog16+xlog32+xlog64+xlog128+xlog128224&28216232264212821282=1.984bit/symbol=127/64bit/symbol(2)二进制香农码：X.p(x.)p(Xi)k码字X10.5010X20.250.5210X30.1250.753110X40.06250.87541110X50.031250.9375511110X60.0156250.968756111110X70.00781250.98437571111110X80.00781250.992187571111111二进制费诺码：xiP(Xi)编码码字kX10.5001X20.250102X30.12501103X40.0625011104X50.03125110111105X60.0156251101111106X70.007812511011111107X80.0078125111111117香农编码效率：

□/、lilclc—lrl,lrlriiK=kp(x)=xl+x2+—x3+x4+x5+x6+x7+x7ii--248l63264128128i=l.984=l27/64竺=HX=竺=lo。%RKl.984费诺编码效率：□/、l|lclcl/l「l,lrlrK=kp(x)=xl+—x2+—x3+x4+x5+x6+x7+x7「i248l63264l28l28i=l.984H(X)=竺=雪=loo%RKl.984..lllllK=kp(x)=xl+—xl+—x..lllllK=kp(x)=xl+—xl+—x2+x2+x3+x3+-2iii=l.328l63264x4+丄x4l28l28l.984K-logm2==94.3%l.328xlog32X5.5设无记忆二进制信源(P(X)0l[0.90.lj先把信源序列编成数字0,l,2,……,8,再替换成二进制变长码字，如下表所示。验证码字的可分离性；求对应于一个数字的信源序列的平均长度K；求对应于一个码字的信源序列的平均长度K2；计算运尹，并计算编码效率；K1序列数字二元码字10l0000l1l00l(5)若用4位信源符号合起来编成二进制哈夫曼码，求它的平均码长K，并计算编码效率。X.p(x.)编码码字kX10.5001X20.25111X30.1250202X40.06251212X50.03125202203X60.015625212213X70.00781252022204X80.0078125122214(5)0013101000013101100001411000000015110100000016111000000001711110000000080其它码字的前其它码字的前2)序列长度、序列概率及二元码长如下表所示：序列序列长度Li序列概率p；数字二元码长L'；二兀码字110.10410000120.1X0.914100100130.1X0.92341010000140.1X0.933410110000150.1X0.9444110000000160.1X0.95541101000000170.1X0.966411100000000180.1X0.977411110000000080.98810K=1LpL=5.693信源符号/数字符号1iii=1K=送pL=2・7086bit/数字符号2iii=1K=0・4756bit/信源符号，此值表示无记忆二元信源采用游程长度编码后每个二元信源需1要的平均码长。H(X)=》p(x)logp(x)=0・469bit/信源符号，n==98.6%i2iK/Ki=121(5)4位信源符号的联合概率、Huffman编码及码长如下表：(码字可以不同，但码长一样)S4P(Si)码字Wi码长LiS4P(s)码字Wi码长Li00000.65610110010.00811111010700010.0729110310100.00811111011700100.0729100311000.00811111110712512512512501000.0729101301110.0009111111100910000.07291110410110.0009111111101900110.0081111110611010.0009111111110901010.00811111000711100.000111111111101001100.00811111001711110.0001111111111110K=兰p(s)L=1.9702bit/4Sym,4iiK=K/4=0.4926bit/Symi=1H(X)==95.2%K5.6有二元平稳马氏链，已知p(0/0)=0.8,p(l/l)=0.7，求它的符号熵。用三个符号合成一个来编写二进制哈夫曼码，求新符号的平均码字长度和编码效率。解：平稳时马尔科夫状态的概率：'p(S)=0・8P(S)+(1-0.7)P(S)彳001P(S)+P(S)=101解得：jp(S0)=3/51P(S)=2/51一阶马氏信源的熵：H=一丫工p(S)p(SIS)logP(SIS)1+1iji2jii=0j=0一H+log5一Alog3一—log7=0・786bit/sym252252252p(SSS)=p(S)p(SIS)p(SIS)12312132p(S=0)=3/5,p(S=1)=2/5,p(S=0IS=0)=0.8,p(S=1IS=0)=0.2,p(S=0IS=1)=0.3,p(S=1IS=1)=0.7S】S2S3P(S,S2S3)LiWiS,S2S3P(S,S2S3)LiWi00048/1251101121/2504001111149/250300011021/2504010000112/12530110109/25050101010012/125400101013/12550101148q/124912212193、K=为p(s)L=1x+3x(+)+4x(++)+5x(+)ii125125250125250250250125i=1327==2・616bit/3symH"=K/3=9°・14%OT96/25000049/25011124/25024/25021/25021/2509/2506/25000110001111001010115/250o5.7对题5.6的信源进行游程编码。若“0”游程长度的截止值为16，“1”游程长度的截止值为8，求编码效率。解：一阶马氏信源的熵同上题，H=0.786bi/sym1+1二元平稳一阶记忆序列“0”游程的长度概率：TOC\o"1-5"\h\z、pio-ipl0=1,2,3・・・15V1、-p(l0)=y0/0^1/0i，乙P(l0)=1iP1510>15%0/0ili0=1二元平稳一阶记忆序列“1”游程的长度概率：/八puP11=1,2,3・・・7V*/八,p(l1)=yhi"0/1i,乙p(11)=1ip711>7i1/1ili1=11”游程长度的熵：

H[l1]=—Xp[l1]logp[l1]=—Xp[l1]logp[l1]—p7logp7ii2ii2i1/121/1l1=1l1=1II=—Xpli1—1plog(pli1—1p)—p7logp71/10/121/10/11/121/1li1=1I0/1i11=1i—pp・(logp)・Xpl1_1—p7logp71/10/121/1Qp0/1i11=1i—pp・(logp)・Xpl1_1—p7logp71/10/121/1Qp1/11/121/11/1l1=1Ip(1—p7)+7p7logp—-U11LLlogp—p7logp71/121/11—p2"1/11/121/11/1TOC\o"1-5"\h\z1/10/120/1i1/10/121/11/121/1li1=1I=—(1—p7)logp=-(1-pi)=-(1-pi)10g2化/1=-(1-PLi)l0g=-(1-PLi)l0g2Po/i1—p^1/11/1(1_pi；)H(p,p)=2.696bit/信源符号1—p0/11/11/1同理，“0”游程长度的熵：H[l0]=Q_P0；0)H(p,p)=3.483bit/信源符号i1—p0/01/00/0分别对“0”和“1”游程序列进行Huffman编码，并分别计算出它们的编码效率。“0”游程序列的长度、对应得概率、Huffman编码的二元码长及码字序列序列长度Li序列概率pi数字二元码长L'i二兀码字01P1/00211002PP丄0/0丄1/0130010003P2P0/01/02301100004P3P0/01/0331010000,05P4P0/01/04400010000,006P5P0/01/05401010000,0007P6P0/01/06410010000,00008P7P0/01/075000000000,0000,09P8P0/01/085010010000,0000,0010P0/09P1/095100010000,0000,00011P0/010P1/0A60000100000,0000,000012P0/011P1/0B61000000000,0000,0000,013P12P0/01/0C61000010000,0000,0000,0014P13P丄0/0J丄1/0D700001100000,0000,0000,00015P0/014P1/0E700001110000,0000,0000,000016P0/015F501000L=弋pL=2p+3pp(1+p+p2)+4pp4(1+p+p2)+5pp7(1+p+p2)+5pl52ii11000100010000i=1+6pp10(1+p+p2)+7pp13(1+p)1000100=2p+(1+p+p2)(3pp+4pp4+5pp7+6pp10)+7pp13(1+p)+5p15100101010101000=2p+pp(1+p+p2)(3+4p3+5p6+6p9)+7pp13(1+p)+5p15110000001000=3.511信源符号/数字符号n=H[l0]/L=3・483/3.511=99.19%0i21”游程序列的长度、对应得概率、Huffman编码的二元码长及码字:序列序列长度K序列概率pi数字二元码长K'i二兀码字11P0/10201112P0/1P1/112101113P0/1P1/123300111114P0/1P115P0/1P1/144400011111,116P0/1P1/155411101111,1117P0/1P1/166411111111,11118—P11Z740000K2=[pK',=p0/1(1+p1/1)(2+3p1/12)+4p0/1p1/14(1+p1/1+p1/12)+4p1/17=2.73二元码字/数字符号n1=H出]/K2=2696=98・75%H[l0]+H[l1]H[l0]+H[l1]3.483+2.696/.n=ii=ii==99%H[l0]/n+H[l1]/nL+K3・511+2.73i0i122可见满足n>n>n，这里的“0”游程编码效率高，因为游程长度长，而游程编码效率受游程01的长度限制显得比“0”游程编码效率略低一些，因此整体的编码效率介于两者之间。5.8选择帧长N=63对00100000,00000000,00000000,00000000,01000000,00000000,00000000,0000000编L-D码;对10000100,00101100,00000001,00100001,01001000,00000111,00000100,0000001编L-D码再译码；对0000000000000000000000000000000000000000000000000000000000000000编L-D码；对1010001101011100011000111010011000011110110010100011010101101001编L-D码；对上述结果进行讨论。解：(解：(1)本帧内信息位数Q=2；各信息位位置值叫=3,n2=34；帧长N=63。=2+528=530T=*Cj==2+528=530TOC\o"1-5"\h\zn»—13—134—1j=1jQ位和t位需要的二进制自然码位数分别是:bog(N+1)」=Ijog?64」=611Cq=C2=1953,Llog1953」11N632所以,L-D编码结果：000010,01000010010解码：已知N=63，故前6位为Q的自然码表示，所以Q=2；后11位为T的自然码表示，得T=530寻找某一值K,使Cq<TvCq,即：C2<530vC2,得KKK+1KK+1得:K=33再令，T=T—C2=530—C2=530—528=2再令，1K33再次寻找某一值L,使Cq-1<TvCq-1,即即C1<2vC1,得L1L+1LL+1得：L=2所以解码出信息位的位置值是n1=3,n2=34(2)对10000100,00101100,00000001,00100001,01001000,00000111,00000100,00000010编L-D码本帧内信息位数Q=15；各信息位位置值n1=1，n2=6，出=11,n4=13，匕=14,兔=24,n7=27，ng=32，斑=34,片0=37,nn=46,片2=47,叫3=48,片4=54,片5=63；帧长N=63。TOC\o"1-5"\h\zT=丈C=C1+C2+C3+C4+C5+C6+C7+Cgnj—11—16—111—113—114—124—127—132—1j=1+C9+C10+C11+C12+C