(完整版)信息论与编码习题参考答案

1、H.F.概出现。求传输此图象所需要的信息率(bit/s)。解：由于亮度电平等概出现，由熵的极值性：每个像素的熵是：H(x)=Kp(a)logp(a)=log10=3.322bit/pels0iii=1每帧图像的熵是：H(X)=5x105xH(x)=5x105x3.322=1.661x106bit/frame0二所需信息速率为：R=r(frame/s)xH(X)(bit/frame)=30 x1.661x106=4.983x107bit/s1.7设某彩电系统，除了满足对于黑白电视系统的上述要求外，还必须有30个不同的色彩度。试证明传输这种彩电系统的信息率要比黑白系统的信息率大2.5倍左右。证:增

2、加30个不同色彩度,在满足黑白电视系统要求下,每个色彩度需要10个亮度,所以每个像素需要用30 x10=300bit量化每个像素的熵是：H(x)=2p(b)logp(b)=log300bit/pels1iii=1=2.477沁2.5H(x)log100彩色电视系统每个像素信息量比黑白电视系统大2.5倍作用，所以传输相同的图形,彩色电视系统信息率要比黑白电视系统高2.5倍左右.1.8每帧电视图像可以认为是由3X105个像素组成，所以像素均是独立变化，且每像素又取128个不同的亮度电平，并设亮度电平是等概出现。问每帧图像含有多少信息量？若现在有一个广播员，在约10000个汉字中选1000个字来口述

3、这一电视图像，试问若要恰当地描述此图像，广播员在口述中至少需要多少汉字？解:每帧图象所含信息量:H(X)=3x105xH(x)=3x105xlog128=2.1x106bit/symble每个汉字所出现概率p=永宀=0.110000.每个汉字所包含信息量:H(c)=-logp描述一帧图像需要汉字数n,H(X)H(X)=2.1x106=6.322x105/frameH(c)-log0.1.最少需要6.322x105个汉字1.9给定一个概率分布(p1,p2,.,pn)和一个整数m，0mn。定义q=1-2p，证明nmii=1H(p,p，p)0)为凸函数，如下：/f(x)=(-xlogx)=-loge

4、又x0 x:.f(x)=(-xlogx)=一loge0)为凸函数。x又；H(p,P：”.,p”)=plogpplogpi=1i=m+1由凸函数的性质，变量函数的平均值小于变量的算术平均值的函数，可得：y2f(卩,)仝互互-2plogp=-(n一m)i=m+1-(n一m)f(i=m+i)=-(n一m)i=m+1logi=m+1=-qlogJiin-mn-mn-mn-mmn-mi=m+1即-2nplogp-qlogq+qlog(n-m)iimmmi=m+1当且仅当p=p=.=p时等式成立。m+1m+2n.H(p,p,.,p)=-2plogp-2plogp-2plogp-qlogq+qlog(n-m

5、)12niiiiiimmmi=1i=m+1i=1TH(p,p,.,p,q)=-2plogp-qlogq12mmiimmi=1TH(p,p,.,p)H(p,p,.,p,q)+qlog(n-m)12n12mmm当且仅当p=p=.=p时等式成立。m+1m+2n2.13把n个二进制对称信道串接起来，每个二进制对称信道的错误传输概率为p(0p1),试证明:整个串接信道的错误传输概率p”=0.51-(1-2p)。再证明:n-o时,limI(X0;X”)=0。信道串接如下图所示：XH.F.解：用数学归纳法证明:当n=2时由：1-ppJ1-pp2p-2p2.p1-pp1-p|_1-2p+2p2.p=2p-2p

6、2=1-(1-2p)222假设n=k时公式成立，贝I；1+(1-2p)*11-(1-2p)*:1+(1-2p)*+1:1-(1-2p)*+1=；1-(1-2p)*+1；1-(1-2p)nP2PkJ=Pk+l1-2p+2p22p-2p2:1-(1-2p)*:1+(1-2p)k；1-(1-2p)k+1；1+(1-2p)k+11-ppp1-pv1-2p1.limP=lim；1(12p)=：设输入信源空间X:p(X=0)=a,p(X=1)=1-a(其中0a0(i,j=1,2,3)0ij0信源具有各态经历性，存在极限概率p(S)(i=1,2,3)p(S)1pp2p/2p(S)2=p/2pp!2p(S)3

7、p/2p/2pp(S1)+p(S2)+p(S3)=1Tp(S)0(i=1,2,3)ip(S)1p(S)2p(S3)3H“=-YYp(S)p(S/S)logp(S/S)ijiji叫=1p(S2)=p(s3)=3i=1=-3x(丄plogp+丄x于log+1x片log)=-(plogp+plog)bit/symbl33223222(3)H,=-(plogp+plog)=-(plogp+；log；+；log；)p+予+片=1.由熵的极限定理，当p=予=片=1即p=2时H取得最大，且222233H=log3=l.585bit/symblemax3.9某一阶马尔柯夫信源的状态转移如下图所示，信源符号集为

8、X：0,1,2。试求:试求信源平稳后状态“0”、“1”、“2”的概率分布p(0)、p(1)、p(2)；求信源的极限熵Hao求当p=0,p=1时的信息熵，并作出解释。0P=12解:(1)由题意，此信源一步转移概率为：0pp0各态经历性信源p(S)1p0pTrp(S)1p(s2)=pp0p(s2)p(S)0ppp(S)3L1-3i由.由状态转移图可知,此信源为不可约、非周期性、存在极限概率p(S)(i=1,2,3)p(S1)+p(S2)+p(S3)=1p(S1)=:p(s2)=3p(S3)=1p(S)0(i=1,2,3)i.H=-XEp(S)p(S/S)logp(S/S)ijijiCOi=1_=一

9、(丄plogp+1xplogp+1plogp+1xplogp+1plogp+1xplogp)333333=-(plogp+plogp)=H(p)bit/symbl(3)p=0时,H=H(0)=0bit/symblp=1时,H=H二0bit/symbl第六章无失真信源编码65某信源S的信源空间为:S:s0.81P(S):0.2n(1)若用U:0,1进行无失真信源编码，试计算平均码长的下限值;n把信源S的N次无记忆扩展信源Sn编成有效码，试求N=2,3,4时的平均码长计算上述N=1,2,3,4,这四种码的信息率.解:(1)H(S)=一p(s)logp(s)=一(0.2xlog0.2+0.8xlog

10、0.8)=0.7219bit/symblei=i.由平均码长界限定理：n丑=07219=0.7219logrlog2(2)N=2时S2P=S2P(S2)S110.04S120.16SS21220.160.64对其进行Huffman编码：码长编码信符信符概率10S“0.640210S，10.16I03110S120.16131110.081n(2)=pn=0.64x1+0.16x2+0.16x3+0.08x3=1.68码符号/2信源符号iii=ln=心=皿=0.84码符号/信源符号22/.n(3)=pniii=1=0.512x1+0.128x3+0.128x3+0.128x3+0.032x5+0

11、.032x5+0.032x5+0.008x5=2.184码符号/3信源符号n(3)n=2184=0.72833N=4时S2S1111P(S3)0.0016S3P=S2S2111P(S3)0.0064码符号/信源符号SSS1112112111220.00640.00640.0512SSS2112212121220.02560.02560.1024SSSS12111212122112220.00640.05120.05120.1024SSSS22112212222122220.02560.10240.10240.4096HF/.n(4)=Kpn=0.4096x1+0.1024x(3+3+4+4)+

12、0.0256x(6+6+6+6+6+6)+0.0064x(7+7+7)+0.0064x8+0.0016x8三2.9632码符号/4信源符号n(4)29632n=E=29632=0.7408码符号/信源符号44(3)N二1时，进行Huffman编码则n二1aRH)=0.7219bit/symblen1bit/symble若编码平均码长达到下限n=0.7129时,R=H(S)nH(S)07219N=2时,R=0.8594bit/symblen0.84H(S)0729N=3时,R=0.9916bit/symblen0.728N=4时,R=0.7219=0.9745bit/symblen0.74086

13、6设信源S的信源空间为SP:S:sP(S):0.2s0.10.3ss450.20.05ss670.050.050.05n符号集U:0,1,2,试编出有效码，并计算其平均码长解:进行Huffman编码:r=3,q=8,因为(q-r)mod(r-1)=5mod2=1工0,所以插入m=(r-1)-(q-r)mod(r-1)=2-1=1个虚假符号,令其为SQ,则:n-Ypni=i=0.3x1+0.2x1+0.2x2+0.1x2+0.05x3+0.05x3+0.05x4+0.05x4=1.8码符号/信源符号,ar，编码后所得的码符号可以看作一个新的信源67设信源S的N次扩展信源Sn用霍夫曼编码法对它编码

14、，而码符号U:aayUP：fU:a1P(U):p1a2p2arpr试证明:当N8时，limp=1(i=1,2,.,r)-NTSi证明:对信源S的N次扩展信源Sn进行Huffam编码，得到的编码是无失真非延长有效码.由平均码长的界限定理，有：心匕n宀+1logrN_logr则H(S“)匕H(S“)+亠其中，为N次扩张信源每个符号需要的平均码长NxlogrNNxlogrN其中n为信源S每个符号所需要的平均码长亠.：5n+logrlogrN对上式各项求极限,不等式仍成立r八.|.fHS+、limlimnlim(+)NTlogrNTSNTSlogrN-H-HSlimnSlogr/T-logrH.lim

15、n=S=HNTSlogrSr同时由无失真信源编码定理,有TT/GTT/编码速率R=H(S=H(S)nNnH(S*)十H(S)-H.Rs=limR=lim=lim=口-=logrbit/symbleNTSNTSnNtsnlogr.在Nts时,编码速率即码符号集U每一符号所包含信源的平均信息量R可见,对于码符号集U,在NT-时提供的信息量达到了最大H_(U)=logr由信源熵的最大值定理知,此时各符号等概出现:.limp=1(i=1,2,，r)NTSir6.8logr,max6.9设某信源的信源空间为:s1p(s)：2fS:s214s318s4丄16s5丄32s6丄64s7丄64n试用U:0,1作

16、码符号集,采取香农编码方法进行编码，并计算其平均码长解:H.F.二n=Xpniii=1=x1+x2+x3+24816X4*x5+x6+3264丄64x6=1.96875码符号/信源符号第七章抗干扰信道编码7.6考虑一个码长为4的二进制码，其码字为w|=0000；w2=0011；W3=1100；w4=1111o若码字送入一个二进制对称信道(其单符号的误传概率为p,p0.01),而码字的输入是不等概率的，其概率为：p(W|)=1/2，p(w2)=1/8，p(W3)=1/8，p(W4)=1/4试找出一种译码规则使平均错误概率Pemin=Pe。emine解：由于信道为二进制对称信道，所以先验概率等于后验概率，且p错误传递概率p。试选择译码函数，并使