信息论英文课后部分习题答案

本答案是英文原版的配套答案，与翻译的中文版课本题序不太一样但内容一样。翻译的中文版增加了题量。2.2、Entropyoffunctions.LetbearandomvariabletakingonafiniteXHXnumberofvalues.Whatisthe(general)inequalityrelationshipofifHYand(a)Y2X?(b)YcosX?.ThenygxSolution:Letpyp(x).x:yg(x)Consideranysetofx’sthatmapontoasingley.Forthissetp(x)logpxp(x)logpyp(y)logp(y),x:yg(x)x:yg(x)pxSinceisamonotoneincreasingfunctionandp(x)p(y).logx:yg(x)ExtendingthisargumenttotheentirerangeofX(andY),weobtainp(x)logp(x)HXp(x)logp(x)xyx:g(x)p(y)logp(y)H(Y),ywithequalityiffifone-to-onewithprobabilityone.g(a)Y2isone-to-oneandhencetheentropy,whichisjustafunctionofXtheprobabilitiesdoesnotchange,i.e.,H(X)H(Y).(b)YcosXisnotnecessarilyone-to-one.HenceallthatwecansayisthatH(X)H(Y),whichequalityifcosineisone-to-oneontherangeofX.

2.16.Exampleofjointentropy.Letp(x,y)begivenbyX01Y011/301/31/3Find(a),H(X)H(Y).(b)(c),.H(X|Y)H(Y|X)H(X,Y)(d)(e)H(Y)H(Y|X).I(X;Y)(f)DrawaVenndiagramforthequantitiesin(a)through(e).Solution:H(X)I(X;Y)H(Y)H(X|Y)H(Y|X)H(X；Y)Fig.1VenndiagramH(X)2loglog30.918bits=H(Y)3123(a)(b).3H(X|Y)1H(X|Y0)2H(X|Y1)0.667bitsH(Y/X)(33p(x|y)p(x,y)p(y))(H(X|Y)H(X,Y)H(Y))1(c)H(X,Y)3log31.585bits3(d)H(Y)H(Y|X)0.251bits(e)I(X;Y)H(Y)H(Y|X)0.251bits(f)SeeFigure1.2.29Inequalities.LetX,YandZbejointrandomvariables.Provethefollowinginequalitiesandfindconditionsforequality.(a)(b)(c)(d)H(X,Y|Z)H(X|Z)I(X,Y;Z)I(X;Z)H(X,Y,Z)H(X,Y)H(X,Z)H(X)I(X;Z|Y)I(Z;Y|X)I(Z;Y)I(X;Z)Solution:(a)Usingthechainruleforconditionalentropy,H(X,Y|Z)H(X|Z)H(Y|X,Z)H(X|Z)WithequalityiffH(Y|X,Z)0,thatis,whenYisafunctionofXandZ.(b)Usingthechainruleformutualinformation,I(X,Y;Z)I(X;Z)I(Y;Z|X)I(X;Z),WithequalityiffI(Y;Z|X)0,thatis,whenYandconditionallyindependentgivenX.areZ(c)Usingfirstthechainruleforentropyandthendefinitionofconditionalmutualinformation,H(X,Y,Z)H(X,Y)H(Z|X,Y)H(Z|X)I(Y;Z|X)H(Z|X)H(X,Z)H(X),WithequalityiffI(Y;Z|X)0,thatis,whenYandareZ

conditionallyindependentgivenX.(d)Usingthechainruleformutualinformation,I(X;Z|Y)I(Z;Y)I(X,Y;Z)I(Z;Y|X)I(X;Z)Andthereforethisinequalityisactuallyanequalityinallcases.4.5EntropyratesofMarkovchains.(a)Findtheentropyrateofthetwo-stateMarkovchainwithtransitionmatrix1ppP01011p10p10(b)Whatvaluesof,maximizetherateofpart(a)?pp0110(c)Findtheentropyrateofthetwo-stateMarkovchainwithtransitionmatrix1ppP10(d)FindthemaximumvalueoftheentropyrateoftheMarkovchainofpart(c).Weexpectthatthemaximizingvalueofpshouldbelessthan1/2,sincethe0statepermitsmoreinformationtobegeneratedthanthe1state.Solution:(a)Thestationarydistributioniseasilycalculated.pp01pp010,10pp1010110ThereforetheentropyrateispH(p)pH(p)1H(X|X)H(p)H(p)100101pp0110102100110(b)Theentropyrateisatmost1bitbecausetheprocesshasonlytwostates.Thisratecanbeachievedif(andonlyif)whichcasetheprocessisactuallyi.i.d.withPr(X0)Pr(X1)1/2.,inpp1/20110ii(c)Asaspecialcaseofthegeneraltwo-stateMarkovchain,theentropyrateisH(p)p1.1H(X|X)H(p)H(1)210(d)Bystraightforwardcalculus,wefindthatthemaximumvalueofofpart(c)occursforp(35)/20.382.ThemaximumH(χ)valueis51H(p)H(1p)H()0.694bits(wrong!)25.4Huffmancoding.Considertherandomvariablexxxxxxx7X1234560.490.260.120.040.040.030.02(a)FindabinaryHuffmancodeforX.(b)Findtheexpectedcodelengthforthisencoding.(c)FindaternaryHuffmancodeforX.Solution:(a)TheHuffmantreeforthisdistributionis(b)TheexpectedlengthofthecodewordsforthebinaryHuffmancodeis2.02bits.(E(X)lp(i))(c)TheternaryHuffmantreeis5.9Optimalcodelengthsthatrequireonebitaboveentropy.ThesourcecodingtheoremshowsthattheoptimalcodeforarandomvariableXhasanexpectedlengthlessthanH(X)1.GivenanexampleofarandomvariableforwhichtheexpectedlengthoftheoptimalcodeisclosetoH(X)1,i.e.,forany0,constructadistributionforwhichtheoptimalcodehasLH(X)1.Solution:thereisatrivialexamplethatrequiresalmost1bitaboveitsentropy.LetXbeabinaryrandomvariablewithprobabilityofX1closeto1.Thenentropyofiscloseto0,butthelengthofitsoptimalXcodeis1bit,whichisalmost1bitaboveitsentropy.5.25Shannoncode.ConsiderthefollowingmethodforgeneratingacodewithforarandomvariableXwhichtakesonmvalues1,2,,mprobabilities.Assumethattheprobabilitiesareorderedsothatp,p,pm12pppm.Definei1p,thesumoftheprobabilitiesofallFi12ik1symbolslessthani.ThenthecodewordforiisthenumberF[0,1]illlog1roundedofftobits,where.piii(a)Showthatthecodeconstructedbythisprocessisprefix-freeandtheaveragelengthsatisfiesH(X)LH(X)1.(b)Constructthecodefortheprobabilitydistribution(0.5,0.25,0.125,0.125).Solution:1(a)Since,wehavellogipilog1llog11ppiiiWhichimpliesthat.H(X)LplH(X)1iiBythechoiceofl,wehave.ThusF,differsji2lp2(li1)iiijfrombyatleast,andwillthereforedifferfromisatleast2lFiFjioneplaceinthefirstlbitsofthebinaryexpansionofF.ThustheiicodewordforF,ji,whichhaslengthll,differsfromthejjicodewordforatleastonceinthefirstlplaces.ThusnocodewordFiiisaprefixofanyothercodeword.(b)WebuildthefollowingtableininlSymbolProbabilityCodewordFiFiidecimalbinary10.50.00.01233000.1100.1111030.1250.125X,X,0.750.87511011143.5AEP.Letbeindependentidenticallydistributedrandom21variablesdrawnaccordingtotheprobabilitymassfunction.Thusp(x,x,,x)p(x).Weknowthatp(x),x1,2,mn12nii11logp(X,X,,X)H(X)q(x,x,,x)q(x),inprobability.Letnn1212nnii1whereqisanotherprobabilitymassfunctionon.1,2,m1(a)Evaluate,wherearei.i.d.~p(x).,,XX12nlimlogq(X,X,,X)n12Solution:Sincethearei.i.d.,soare,,…，q(X)，X,X,,X()()qXqX12n12nandhencewecanapplythestronglawoflargenumberstoobtainlim1logq(X,X,,X)lim1logq(X)n12nniE(logq(X))w.p.1p(x)logq(x)p(x)logp(x)p(x)logp(x)q(x)D(p||q)H(p)8.1Preprocessingtheoutput.OneisgivenacommunicationchannelwithtransitionprobabilitiesandchannelcapacityI(X;Y).p(x)p(y|x)CmaxAhelpfulstatisticianpreprocessestheoutputbyformingY_g(Y).Heclaimsthatthiswillstrictlyimprovethecapacity.(a)Showthatheiswrong.(b)Underwhatconditiondoeshenotstrictlydecreasethecapacity?Solution:(a)ThestatisticiancalculatesY_g(Y).SinceformsaXYY_Markovchain,wecanapplythedataprocessinginequality.Henceforeverydistributiononx,_I(X;Y)I(X;Y).Letp_(x)bethedistributiononxthatmaximizesI(X;Y_).ThenCmaxI(X;Y)I(X;Y)I(X;Y_)maxI(X;Y_)C_.__p(x)p(x)p(x)p(x)p(x)p(x)Thus,thestatisticianiswrongandprocessingtheoutputdoesnotincreasecapacity.(b)Wehaveequalityintheabovesequenceofinequalitiesonlyifwehaveequalityindataprocessinginequality,i.e.,forthedistributionthatmaximizesI(X;Y_),wehaveformingaMarkovchain._XYY8.3Anadditionnoisechannel.Findthechannelcapacityofthefollowingdiscretememorylesschannel:.Assume0,1PrZ0PrZa1Where.ThealphabetforxisX2thatZisindependentofX.Observethatthechannelcapacitydependsonthevalueofa.Solution:Asumchannel.,YXZX0,1Z0,aWehavetodistinguishvariouscasesdependingonthevaluesofa.a0Inthiscase,YXpertransmission.,andmaxI(X;Y)1.Hencethecapacityis1bitInthiscase,Yhasfourpossiblevalues0,1,a,1a.Knowinga0,1Y,weknowtheXwhichwassent,andhenceH(X|Y)0.Hencethecapacityisalso1bitpertransmission.a1InthiscaseYhasthreepossibleoutputvalues,0,1,2,thechannelisf1identicaltothebinaryerasurechannel,with.Thecapacityofthis21channelis1fbitpertransmission.2a1Thisissimilartothecasewhena1andthecapacityisalso1/2bitpertransmission.8.5Channelcapacity.Considerthediscretememorylesschannel1,2,3X0,1,,10YXZ(mod11),whereand.AssumethatZ1/3,1/3,1/3ZisindependentofX.(a)Findthecapacity.(b)Whatisthemaximizing?p*(x)Solution:ThecapacityofthechannelisCmaxI(X;Y)p(x)I(X;Y)H(Y)H(Y|X)H(Y)H(Z|X)H(Y)H(Z)11,whichisobtainedwhenYhasanI(X;Y)logyH(Z)logbits3uniformdistribution,whichoccurswhenXhasanuniformdistribution.11(a)Thecapacityofthechannelis/transmission.logbits3(b)Thecapacityisachievedbyanuniformdistributionontheinputs.p(Xi)1fori0,1,,10118.12Time-varyingchannels.Consideratime-varyingdiscretememorylesschannel.LetbeconditionallyindependentgivenY,Y,Yn12,X,withconditionaldistributiongivenbyp(y|x).iiip(y|x)nX,X12ni1LetX(X,X,X)Y(Y,Y,Y),.FindI(X;Y).max12n12np(x)Solution:I(X;Y)H(Y)H(Y|X)H(Y)H(Y,Y,Y|X)12nH(Y)nH(Y|Y,Y,X)H(Y)nH(Y|X)i1i1iii1i1nH(Y)nH(Y|X)n(1h(p))iiiii1i1i1Withequlityif,Xnischoseni.i.d.HenceX,X12maxI(X;Y)n(1h(p)).ip(x)i110.2AchannelwithtwoindependentlooksatY.LetYandYbe12conditionallyindependentandconditionallyidenticallydistributedgivenX.(a)Show.2I(X;Y,Y)2I(X;Y)I(Y;Y)1211(b)ConcludethatthecapacityofthechannelX(Y1,Y2)islessthantwicethecapacityofthechannelXY1Solution:(a)I(X;Y,Y)H(Y,Y)H(Y,Y|X)121212H(Y)H(Y)I(Y;Y)H(Y|X)H(Y|X)121212I(X;Y)I(X;Y)I(Y;Y)12122I(X;Y)I(Y;Y)112(b)Thecapacityofthesinglelookchannelis.CmaxI(X;Y)1XY11p(x)ThecapacityofthechannelisX(Y,Y)12CmaxI(X;Y,Y)max2I(X;Y)I(Y;Y)212112p(x)p(x)max2I(X;Y)2C11p(x)10.3Thetwo-lookGaussianchannel.ConsidertheordinaryShannonGaussianchannelwithtwocorrelatedlooksatX,i.e.,,where2Y(Y,Y)1YXZ11withapowerconstraintPonX,and(Z,Z)~N(0,K),YXZ21222whereNN.FindthecapacityforCKNN10(a)(b)(c)1Solution:ItisclearthatthetwoinputdistributionthatmaximizesthecapacityisX~N(0,P).Evaluatingthemutualinformationforthisdistribution,CmaxI(X;Y,Y)h(Y,Y)h(Y,Y|X)2121212h(Y,Y)h(Z,Z|X)h(Y,Y)h(Z,Z)12121212NNNowsince,wehave(Z,Z)~N0,NN12h(Z,Z)1log(2e)2Kz1log(2e)2N2(12).2212Since,and,weYXZ1YXZ212,PNPNhaveAnd(Y,Y)~N0,PNPN12h(Y,Y)1log(2e)2K1log(2e)2(N2(12)2PN(1)).2212YCh(Y,Y)h(Z,Z)21212Hence1log12PN(1)21