信息论及编码理论学习试题

精选文档精选文档精选文档第二章信息量和熵

2.2八元编码系统，码长为3，第一个符号用于同步，每秒1000个码字，求它的信息速率。

解：同步信息均同样，不含信息，所以每个码字的信息量为

2log8=2

3=6bit

所以，信息速率为

61000=6000bit/s

2.3掷一对无偏骰子，告诉你获得的总的点数为：(a)7;(b)12。问各获得多少信息量。

解：(1)可能的组合为{1，6},{2，5},{3，4},{4，3},{5，2},{6，1}61p(a)==366获得的信息量1=log=log6=2.585bitp(a)

可能的独一，为{6，6}p(b)=136

1=log36=5.17bit获得的信息量=logp(b)

2.4经过充分洗牌后的一副扑克（52张），问：

任何一种特定的摆列所给出的信息量是多少？

若从中抽取13张牌，所给出的点数都不同样时获得多少信息量？

1解：(a)p(a)=

1信息量=log=log52!=225.58bitp(a)

13!13种点数随意摆列(b)

413花色任选

p(b)=13!413=413A5213C5213信息量=logC5213log413=13.208bit—

2.9随机3骰子，X表示第一骰子的果，Y表示第一和第二骰子的

点数之和，Z表示3骰子的点数之和，求H(Z|Y)、H(X|Y)、

H(Z|X,Y)、H(X,Z|Y)、H(Z|X)。

解：令第一第二第三骰子的果分x1,x2,x3，x1，x2，x3互相独立，

Xx1，Yx1x2，Zx1x2x3

H(Z|Y)=H(x3)=log6=2.585bit

H(Z|X)=H(x2x3)=H(Y)=2(1log36+2log18+3log12+4log9+5log36)+6log63636363636536=3.2744bit

H(X|Y)=H(X)-I(X;Y)=H(X)-[H(Y)-H(Y|X)]

而H(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.8955bit

H(Z|X,Y)=H(Z|Y)=H(X)=2.585bit

H(X,Z|Y)=H(X|Y)+H(Z|XY)=1.8955+2.585=4.4805bit

2.10一个系送10个数字，0，1，⋯，9。奇数在送程中以0.5的概率成其余一个奇数，其余正确接收，求收到一个数字均匀获得的信息量。

解：

XYi1,3,5,7,9信道Χi0,2,4,6,8√I(X;Y)=H(Y)-H(Y|X)

因入等概，由信道条件可知，

2—

p(yii为奇数)110p(yii为偶数)1(11111)1102888810即输出等概，则H(Y)=log10H(Y|X)=p(xiyj)logp(yj|xi)ij=p(xiyj)logp(yj|xi)-p(xiyj)logp(yj|xi)ji偶ji奇=0-p(xiyj)logp(yj|xi)ji奇=-p(xi)p(yi|xi)logp(yi|xi)-p(xi)p(yj|xi)logp(yj|xi)i1,3,5,7，9iji＝1，3，5，7，91111145=log25+2log81021043

=1bit44

I(X;Y)=H(Y)-H(Y|X)=log10-1=log5=2.3219bit

2.11令{u1,u2,，u8}为一等概信息集，各信息相应被编成下述二元码字

u1=0000，u2=0011，u3=0101，u4=0110，

u5=1001，u6=1010，u7=1100，u8=1111

经过转移概率为p的BSC传达。求：

(a)接收到的第一个数字0与u1之间的互信息量。

(b)接收到的前二个数字00与u1之间的互信息量。

(c)接收到的前三个数字000与u1之间的互信息量。

(d)接收到的前四个数字0000与u1之间的互信息量。

解：

3—

即I(u1;0)，I(u1;00)，I(u1;000)，I(u1;0000)

p(0)=1(1p)4+1p4=1882p(0|u1)=log1p=1+log(1p)bitI(u1;0)=log1p(0)2p(00)=1[2(1p)24(1p)p2p2]=184I(u1;00)=logp(00|u1)=log(1p)2=2[1log(1p)]bitp(00)1/4p(000)=1[(1p)33(1p)2p3(1p)p2p3]=188I(u1;000)=3[1+log(1p)]bitp(0000)=1[(1p)46(1p)2p2p4]8I(u1;0000)=log8(1p)4bit(1p)46(1p)2p2p4

2.12计算习题2.9中I(Y;Z)、I(X;Z)、I(X,Y;Z)、I(Y;Z|X)、I(X;Z|Y)。

解：依据题2.9剖析H(Z)=2(1log216+3log216+6log216+10log216+216216321662161015216+21216+2521627log216216logloglog+216)15216212162527=3.5993bit

I(Y;Z)=H(Z)-H(Z|Y)=H(Z)-H(X)=1.0143bit

I(X;Z)=H(Z)-H(Z|X)=H(Z)-H(Y)=0.3249bit

I(X,Y;Z)=H(Z)-H(Z|XY)=H(Z)-H(X)=1.0143bit

4—

I(Y;Z|X)=H(Z|X)-H(Z|XY)=H(Y)-H(X)=0.6894bit

I(X;Z|Y)=H(Z|Y)-H(Z|XY)=H(X)-H(X)=0bit

2.14关于随意概率事件集X,Y,Z，证明下述关系式成立

(a)H(Y,Z|X)H(Y|X)+H(Z|X)，给出等号成立的条件

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)]

xyz

p(xy)[-p(z|x)logp(z|x)]xyz=-p(xyz)logp(z|x)xyzH(Z|X)

当p(z|xy)=p(z|x)，即X给定条件下，Y与Z互相独立刻等号成立

上式(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令概率空间X1,1，令Y是连续随机变量。已知条件概率密度为22

5—

14,2yx2p(y|x)，求：0,其余(a)Y的概率密度(y)

I(X;Y)

若对Y做以下硬裁决

1,y1V0,1y11,y1

求I(X;V)，并对结果进行解说。

解：(a)由已知，可得

13y1p(y|x1)=40else11y3p(y|x1)=40else(y)=p(x1)p(y|x1)+p(x1)p(y|x1)13y1811y1=411y380else11211(b)HC(Y)=log84log4=2.5bit831HC(Y|X)=p(x1)1p(y|x1)logp(y|x1)dy3p(x1)31)logp(y|x1)dyp(y|x1=111log11311234dy14logdy=2bit424I(X;Y)=HC(Y)-HC(Y|X)=0.5bit

6—

由(y)可获得V的分布律

V-101p1/41/21/4再由p(y|x)可知V-101p(V|x=-1)1/21/20p(V|x=1)01/21/2

1log21bitH(V)2log41.524H(V|X)1[1log21log2]2=1bit222I(X;V)=H(V)H(V|X)=0.5bit

2.29令Q1(x)和Q2(x)是同一事件集U上的两个概率分布，相应的熵分别为

H(U)1和H(U)2。

(a)关于01，证明Q(x)=Q1(x)+(1)Q2(x)是概率分布

(b)H(U)是相应于分布Q(x)的熵，试证明H(U)H(U)1+(1)H(U)2

证明：(a)因为Q1(x)和Q2(x)是同一事件集U上的两个概率分布，于是

q1(x)0，q2(x)0

q1(x)dx=1，q2(x)dx=1

xx

又01，则

q(x)=q1(x)+(1)q2(x)0

q(x)dx=q1(x)dx+(1)q2(x)dx=1

xxx

所以，Q(x)是概率分布。

(b)H(U)=[q1(x)(1)q2(x)]log[q1(x)(1)q2(x)]dx

x

=q1(x)log[q1(x)(1)q2(x)]dx

x

7—

(1)q2(x)log[q1(x)(1)q2(x)]dx

x

q1(x)logq1(x)dx(1)q2(x)logq2(x)dx（引理2）

xx

=H(U)1+(1)H(U)2

8—

第三章信源——失散信源无失真3.1明N的D元等至多有D(DN1)个字。D1：①在D元上，第一点点有D个，第二有D2，每个点一NDi=D(1DN)=D(DN1)，此个字，若最有N，函数有1i11DD，全部字中的全部点。②1的D个；2的D2个，⋯，N的DN个NDi=D(DN1)个∴共i1D1

3.2有一失散无信源Ua1,a2。若其出的100的事件序0.004,0.996列中含有两个或许少于两个a1的序列供给不同样的字。

在等下，求二元的最短。

求概率（率）。

解:(a)不含a1的序列1个

100的序列中含有1个a1的序列C1001=100个100的序列中含有2个a1的序列C1002=4950个∴所需供给的数M=1+100+4950=5051于是采纳二元等NlogM=12.3，故取N=13logD(b)当度100的序列中含有两个或更多的a1出，所以概率Pe=1C1000(0.996)100-C1001(0.004)(0.996)99C1002(0.004)2(0.996)98=7.775103

9—

a1,a23.3设有一失散无记忆信源，U=1,3，其熵为H(U)。观察其长为L的输出44

序列，当LL0时满足下式

PrI(uL)H(U)L(a)在=0.05，=0.1下求L0(b)在=103，=8下求L010(c)令T是序列uL的会集，此中

I(uL)H(U)L

试求L=L0时状况(a)(b)下，T中元素个数的上下限。

解：H(U)=pklogpk=1log43log4=0.81bit443

E[I(ak)]=H(U)

I2=E{[I(ak)H(U)]2}=E[I(ak)2]-H2(U)

=pk(logpk)2H2(U)

k

=0.471

则依据契比雪夫大数定理

I(uL)2PrH(U)IL2L20.471(a)L=I==18842(0.05)20.12L2=80.47132=4.711013

10(10)由条件可知uL为典型序列，若设元素个数为MT，则依据定理I

(1)2L(H(U))MT2L(H(U))

此中，，可知

10—

(i)0.1，0.05，L1884下界限：(1)2L(H(U))0.921431..84上界限：2L(H(U))=21620..24故0.921431..84MT21620..24(ii)106，103，L4.711011(1)2L(H(U))0.999923.8110112L(H(U))=23.821011故0.999923.811011MT23.821011

3.4关于有4字母的失散无记忆信源有两个码A和码B，参看题表。字母概率码A码Ba0.4111a0.301102a30.2001100a40.100011000各码能否满足异字头条件？能否为独一可译码？

当收到1时获得多少关于字母a1的信息？

当收到1时获得多少关于信源的均匀信息？

解：①码A是异头字码，而B为逗点码，都是独一可译码。

②码AI(a1;1)log2p(a1|1)log211.32bitp(a1)0.4码BI(a1;1)log2p(a1|1)p(1)log2p(a1,1)log0.40bitp(a1)p(1)p(a1)p(1)0.41③码AU=｛a1,a2,a3,a4｝4I(u;1)p(ak|1)I(ak;1)=p(a1|1)I(a1;1)0=1.32bitk1

11—

4

码BI(u;1)p(ak|1)I(ak;1)=0bit

k1

（收到1后，只知道它是码字开头，不可以获得关于U的信息。）

3.5令失散无记忆信源

Ua1a2a3a4a5a6a7a8a9a100.160.140.130.120.100.900.080.070.060.05

求最正确二元码,计算均匀码长和编码效率。

求最正确三元码,计算均匀码长和编码效率。

解：(a)

0.58010.421

0.31

0

0.2710.2300.191000a10.160.1501010a20.140011a30.1301100a40.120.111110a50.100111a60.0910010a70.0800011a80.0711010a90.0601011a100.051H(U)pklogpk=3.234bit均匀码长npknk=3.26=RnlogDk效率H(U)H(U)99.2%RnlogD

12—

(b)

0.4300.33110.24200a10.16001a20.14102a30.13210a40.1200.11112a50.10220a60.09021a70.08122a80.072110a90.060111a100.051均匀码长npknk=2.11

k

nlogD=3.344

H(U)效率96.6%R

a1.........a2.........a3.....3.6令失散无记忆信源U0.5...0.3.....0.2

求对U的最正确二元码、均匀码长和编码效率。

2求对U的最正确二元码、均匀码长和编码效率。

3求对U的最正确二元码、均匀码长和编码效率。

解：(a)

0.5011a10.5100a20.3001a30.21n=0.5×1+0.3×2+2×0.2=1.5H(U)pklogpk1.485bit13—

H(U)99%R

(b)∵失散无记忆∴H(U1U2)=2H(U)=2.97bit

p(a1a1)=0.25,p(a1a2)=0.15,p(a1a3)=0.1,p(a2a1)=0.15,p(a2a2)=0.09

p(a2a3)=0.06,p(a3a1)=0.1,p(a3a2)=0.06,p(a3a3)=0.04

0.55010.4510.300.25110a1a10.2500.210.150001a1a20.151010a2a10.1500.11110a1a30.10111a3a10.110000a2a20.0900001a2a30.0610110a3a20.0600111a3a30.041

n2pknk3

n2n1.52

H(U1U2)=2.97=0.99n2logD3有关U3最正确二元近似略

3.7令失散无记忆信源a1.........a2..........akUp(a1)p(a2)p(ai)

14—

i1且0≤P(a≤P(a)≤⋯≤P(a)<1。定Q=，而1，今按12kik1

下述方法行二元。信息ak的字数Qk的二元数字表示序列的截短（比方1/2的二元数字表示序列1/2→10000⋯，1/4→0100⋯）,保存的截短序列度nk是大于或等于I(ak)的最小整数。

(a)信源Ua1...a2.......a3......a4......a5.......a6.......a7......a8.....构造。111111114,4,8,8,16,16,16,16(b)明上述法获得的足异字条件，且均匀n足H(U)≤n≤H(U)+1。

解：(a)

符号QiLCa8040000a714000116a61400108a534001116a41401004a3330118a242108a132114

反法明异字条件

令k<k’，若ak是ak的字，QkQk2nk又由I(ak)nkI(ak)1可知，2nkpk2nk1从而得QkQk2nkpk与假ak是ak的字（即QkQkpk）相矛盾，故足异字条件。由已知可得

15—

log1nklog11pkpk对不等号两边取概率均匀可得pklog1pknkpklog11kpkkkpk即H(U)nH(U)1

a1.....a23.8扩展源DMC，U0.6,0.4

(a)求对U的最正确二元码、均匀码长和编码效率。

2(b)求对U的最正确二元码、均匀码长和编码效率。

3(c)求对U的最正确二元码、均匀码长和编码效率。

4(d)求对U的最正确二元码、均匀码长和编码效率。

解：(a)C10，C2=1，n=1

H(U)0.97bitH(U)

R

97%

DMC信道

0.600.41100a1a10.360101a1a20.24010a2a10.24111a2a20.16

n22，n1，H(U)97%n(c)

16—

0.50410.496010.288001a1a1a10.21610.20400.1920.1610111a1a1a20.1441000a1a2a10.1440001a2a1a10.1441100a1a2a20.0960101a2a1a20.09611100a2a2a10.09601101a2a2a20.0641

n3=2.944n=0.981

=98.85%

略

3.9设失散无记忆信源Ua1,.....a2,....a3,......a4,....a5,...a6试求其二元和三元0.3,..0.2,..0.15,..0.15,..0.1,..0.1

Huffman编码。

解：

17—

0.40.610.3001a10.310.211a20.2000a30.150001a40.151100a50.10101a60.1101a10.3110.2200a20.2001a30.15102a40.15220a50.1021a60.11

3.11设信源有K个等概的字母,此中K=2j,12。今用Huffman编码法进

行二元编码。

（a）能否存在有长度不为j或j+1的码字，为何？

（b）利用和j表示长为j+1的码字数量。

（c）码的均匀长度是多少？

解：Huffman思想：将概率小的用长码，大的用短码，保证n↓，当等概时，趋

于等长码。

a)对1时，K=2j，则用长度为j码表示；当2时，用K=2j+1，用长

度为j+1码表示。均匀码长最短，则当12时，则介于二者之间，

即只存在j，j+1长的码字。

设长为j的码字个数为Nj，长度为j+1的码字数量为Nj+1，依据二元Huffman编码思想（必然占满整个码树），即

18—

NjNj1K2jNj2jNj12(j1)1从而Nj(2)2j，Nj1(1)2j1c）1j1(j1)=j22LNjNj1KK3.12设二元信源的字母概率为p(0)1，p(1)3。若信源输出序列为44解：

3124112(a)p(s)344416r)rrF(uF(u)p(u)F(ui1)i1ii依据递推公式rr可得以下表格p(ui1)p(ui)p(ui1)此中，F(1)=0，F(1)=3，p(0)=1，p(1)=3444uip(ui)F(ui)

10131440313144164339116464932716442563305434164

19—

1354736148

37149

0

37

410

1

38

411

1

39

412

0

39

1

413

310414

1

311

1

415

312416

1508125135从而C=H(U)1log43log444399.85%R1316段号短语ij编码110100012000000031111001140121010120—

5111310111601141100170111611101

RnlogD1774416H(U)1log43log40.8113bit443H(U)46.36%R

3.13设DMS为U=.a1..........a2........a3......a4，各a相应编成码字0、10、110和1110。1..1..1..1i4,82,8,试证明对足够长的信源输出序列，相应的码序列中0和1出现的概率相等。

解：

概率信源符号码字1/2a101/4a2101/8a31101/8a41110

设信源序列长为N，则相应码字长为（条件是N要足够长）LN1N2N37N2484相应码序列中0出现的次数

NNN7L0111N2488∴p(0)=L0=1p(1)=1-p(0)=1L22

013.14设有一DMS,U=

0.90.1

采纳以下表的串长编码法进行编码

21—

信源出序列0串度（或中数字）出二元字100000011000100120010⋯⋯⋯00000001701110000000081(a)求H(U)。(b)求于每此中数字相的信源数字的均匀度n1。(c)求每此中数字的均匀度n2。(d)明的独一可性。解：(a)H(U)0.9log0.90.1log0.10.469bit由已知可得下表先信源出0串度出二元字概率序列（或中数字）0.11000000.0901100010.081001200100.07290001300110.065600001401000.059000001501010.05310000001601100.047800000001701110.430500000000181(b)n110.120.980.43055.6953bit(c)n210.43054(10.4305)2.7085bit异字

22—

第四章信道及信道容量

4.1计算由下述转移概率矩阵给定的DMC的容量。

1pp0(a)01ppp01pQ它是一对称信道，达到C需要输入等概，即p=13∴Clog3p(jk)logp(jk)log3(1p)log(1p)plogplog3H(p)bit/符号1p1ppp(b)2222pp1p1p2222它是一对称信道∴Clog41plog1p2plogp222222(11pplogp1H(p)bit/符号p)log221pp0（c）p1p0

001

它是分信道1pp和1的和信道p1pC1log2(1p)log(1p)1H(p)C20

由2c2c12c2，可知Clog121H(p)bit/符号

23—

4.3求图中DMC的容量及最正确输入分布

3/4

001/3001/41/31/31/31/3111/3111/31/31/321/41/31/322233/41/3（a）(b)解：（a）由图知31044P11133301344Q发送符号1时等概率收到0,1,2,

∴传对与传错概率完满同样，即不携带任何信息量，于是信道简化为二元

纯删除信道

31044310P11144333130134404403/401/411/4123/4

C1q11/43/4bit/符号

（b）由图知

24—

1101333P01113331011333为准对称∴当输入等概，即Q0Q1Q21时达到信道容量C1123此时012323931131333∴CI(x0,Y)jp(j0)logp(j0)j111=1log31log31log32log3bit/符号323231329934.5N个同样的BSC级联如图。

X0X1X2XN1XN

各信道的转移概率矩阵p1p。令Qt{0},t0,1,,N，且Q0为1pppXt已知。

(a)求Qt的表达式。

(b)证明N时有QN1/2，且与Q0取值没关，从而证明N时的级

联信道容量CN0(p0)

解：N个信道级联后BSC可表示为

pN1

00pN1pN1

11pN1

N个级联可以看作N-1个级联后与第N个级联

25—

1pN11p000pN1pN1pp

11pN1111p∴pN(1pN1)ppN1(1p)pN1(12p)p同理可得pN1pN2(12p)ppN2pN3(12p)pM

p2p1(12p)p

p1p

从而pNpN1(12p)p[pN2(12p)p](12p)ppN2(12p)2p(12p)ppN3(12p)3p(12p)2p(12p)pN2p(12p)N1p(12p)ii0N1

(12p)i

0

p1(12p)N1(12p)N1(12p)2(a)

QNQ0(1pN)(1Q0)pN

Q0(12Q0)pNQ(12Q)1(12p)N002(b)

limQNlimQ0(11(12p)N2Q0)NN212Q01Q022

26—

所以与Q0没关。

因为

QNp{xN0}p{x00}(1pN)p{x011}pN2与p{x00}Q0没关，所以pN1，C=0。2

4.8一PCM语音通讯系统，已知信号带宽W=4000Hz，采样频率为2W，且采

用8级幅胸怀化，各级出现的概率为1/2，1/4，1/8，1/16，1/32，1/32，1/32，

1/32。试求所需的信息速率.

解：H(V)pklogpk1log21log41log81log1614log329bitk24816324∴信息速率RfsH(V)8000918000bit/s44.9在数字电视编码中，若每帧为500行，每行区分红600个像素，每个像素采纳8电平量化，且每秒传达30帧时，试求所需的信息速率。

解：每个像素信息量为Ilog83bit

每秒传输30帧，即305006009106个像素

R910632.7107bit/s

4.10带宽为3kHZ，信噪比为30dB的电话系统，若传达时间为3分钟，试预计可能传达话音信息的数量。

解：(S)dB=30dB=103