信息与编码习题答案

二章-信息量和熵习题解

2.1 莫尔斯电报系统中，若采用点长为0.2s，1划长为0.4s，且点和划出现的概率分别为2/3和1/3，试求它的信息速率(bits/s)。

214?0.2??0.4?秒 3315231 每个符号的熵为?log??log3?0.9183比特/符号

32315所以，信息速率为0.9183??3.444比特/秒

4解: 平均每个符号长为:

2.2 一个8元编码系统，其码长为3，每个码字的第一个符号都相同(用于同步)，若每秒产生1000个码字，试求其信息速率(bits／s)。

解: 同步信号均相同不含信息,其余认为等概,每个码字的信息量为 3*2=6 比特；

所以，信息速率为6?1000?6000比特/秒

2.3 掷一对无偏的骰子，若告诉你得到的总的点数为：(a) 7；(b) 12。

试问各得到了多少信息量?

6 366 所以，得到的信息量为 log2( 比特 )?2.585361 (b) 一对骰子总点数为12的概率是

361 所以，得到的信息量为 log2?5.17 比特

36 解: (a)一对骰子总点数为7的概率是

2.4 经过充分洗牌后的一付扑克(含52张牌)，试问：

(a) 任何一种特定排列所给出的信息量是多少?

(b) 若从中抽取13张牌，所给出的点数都不相同时得到多少信息量?

解: (a)任一特定排列的概率为

1, 52!1?225.58 比特 52!所以，给出的信息量为 ?log213!?413413?13 (b) 从中任取13张牌,所给出的点数都不相同的概率为 13A52C52 1

13C52所以，得到的信息量为 log213?13.21 比特.

42.5 设有一个非均匀骰子，若其任一面出现的概率与该面上的点数成正比，试求各点

出现时所给出的信息量，并求掷一次平均得到的信息量。

解:易证每次出现i点的概率为

I(x?i)??log2i,所以 21i,i?1,2,3,4,5,621I(x?1)?4.392比特I(x?2)?3.392比特I(x?3)?2.807比特I(x?4)?2.392比特I(x?5)?2.070比特I(x?6)?1.807比特H(X)???i?16

iilog2?2.398比特21212.6 园丁植树一行，若有3棵白杨、4棵白桦和5棵梧桐。设这12棵树可随机地排列，

且每一种排列都是等可能的。若告诉你没有两棵梧桐树相邻时，你得到了多少关于树的排列的信息?

解: 可能有的排列总数为

12!?27720

3!4!5!没有两棵梧桐树相邻的排列数可如下图求得，

Y X Y X Y X Y X Y X Y X Y X Y

图中X表示白杨或白桦，它有????种排法，Y表示梧桐树可以栽种的位置，它有????种排法，

所以共有??5??*??3??=1960种排法保证没有两棵梧桐树相邻，

????因此若告诉你没有两棵梧桐树相邻时，得到关于树排列的信息为

?7??3??8??5??8??7?log227720?log21960=3.822 比特

2.7 某校入学考试中有1/4考生被录取，3/4考生未被录取。被录取的考生中有50%来自本市，而落榜考生中有10％来自本市，所有本市的考生都学过英语，而外地落榜考生中以及被录取的外地考生中都有40%学过英语。

(a) 当己知考生来自本市时，给出多少关于考生是否被录取的信息?

2

(b) 当已知考生学过英语时，给出多少有关考生是否被录取的信息?

(c) 以x表示是否落榜，y表示是否为本市学生，z表示是否学过英语，x、y和z

取值为0或1。试求H(X)，H(Y|X)，H(Z|YZ)。

解: X=0表示未录取，X=1表示录取；

Y=0表示本市，Y=1表示外地；

Z=0表示学过英语，Z=1表示未学过英语，由此得

31p(x?0)?,p(x?1)?,44p(y?0)?p(x?0)p(y?0x?0)?p(x?1)p(y?0x?1)31111?????,41042514p(y?1)?1??,

55p(z?0)?p(y?0)p(z?0y?0)?p(y?1)p(z?0y?1)144013???,55100251312p(z?1)?1??,2525?

(a)p(x?0y?0)?p(y?0x?0)p(x?0)/p(y?0)?1313?/?104581115p(x?1y?0)?p(y?0x?1)p(x?1)/p(y?0)??/?2458p(x?0y?0)p(x?1y?0)I(X;y?0)?p(x?0y?0)log2?p(x?1y?0)log2

p(x?0)p(x?1)3535?log28?log28381844?0.4512比特 3

(b)p(x?0z?0)?(p(z?0y?0,x?0)p(y?0x?0)?p(z?0y?1,x?0)p(y?1x?0))p(x?0)/p(z?0)19431369?(??)?/?101010425104p(x?1z?0)?(p(z?0y?0,x?1)p(y?0x?1)?p(z?0y?1,x?1)p(y?1x?1))p(x?1)/p(z?0)11211335?(??)?/?225425104I(X;z?0)?p(x?0z?0)log2p(x?0z?0)p(x?0)69356935?log2104?log21043104110444?0.02698比特?p(x?1z?0)log2p(x?1z?0)p(x?1)(c)H(X)?341log2?log24?0.8113比特434H(YX)?p(x?0)p(y?0x?0)log2p(y?0x?0)?p(x?0)p(y?1x?0)log2p(y?1x?0)p(x?1)p(y?0x?1)log2p(y?0x?1)?p(x?1)p(y?1x?1)log2p(y?1x?1)3139101111??log210??log2??log22??log2241041094242?0.6017比特

2.8 在A、B两组人中进行民意测验，组A中的人有50%讲真话(T)，30%讲假话(F)，20%拒绝回答(R)。而组B中有30%讲真话，50%讲假话和20%拒绝回答。设选A组进行测验的概率为p，若以I(p)表示给定T、F或R条件下得到的有关消息来自组A或组B的平均信息量，试求I(p)的最大值。

解:令X??A,B?,Y??T,F,R?，则

4

P(T)?P(TA)P(A)?P(TB)P(B)?0.5p?0.3?(1?p)?0.3?0.2p同理P(F)?0.5?0.2p,P(R)?0.2I(p)?I(X;Y)?H(Y)?H(YX)??(0.3?0.2p)log2(0.3?0.2p)?(0.5?0.2p)log2(0.5?0.2p)?0.2log20.2?(0.5plog22?0.3plog210?0.2plog25?0.3(1?p)log210?0.5(1?p)log22?330.2(1?p)log25)?0.3log20.3?0.5log20.5?(0.3?0.2p)log2(0.3?0.2p)?(0.5?0.2p)log2(0.5?0.2p)令I'(p)?0.2log2(0.5?0.2p)?0,得p?0.50.3?0.2p?I(p)max?I(p)p?0.5?0.03645比特

2.9 随机掷三颗骰子，以X表示第一颗骰子抛掷的结果，以Y表示第一和第二颗骰子抛掷的点数之和，以Z表示三颗骰子的点数之和。试求H(Z|Y)、H(X|Y)、H(Z|XY)，H(XZ|Y)和H(Z|X)。

解:令X=X1,Y=X1+X2,Z=X1+X2+X3,

H(X1)=H(X2)=H(X3)=log26 比特 H(X)= H(X1) =log26=2.585 比特 H(Y)= H(X2+X3)

=

2(12363364365361log236?log2?log2?log2?log2)?log26 363623633643656= 3.2744比特

H(Z)= H(X1+X2+X3)

?2(1321662161021615216log2216?log2?log2?log2?log2216216321662161021615 212162521627216log2?log2?log2)216212162521627= 3.5993 比特 所以

H(Z/Y)= H(X3)= 2.585 比特

H(Z/X) = H(X2+X3)= 3.2744比特

H(X/Y)=H(X)-H(Y)+H(Y/X) = 2.585-3.2744+2.585 =1.8955比特 H(Z/XY)=H(Z/Y)= 2.585比特

H(XZ/Y)=H(X/Y)+H(Z/XY) =1.8955+2.585 =4.4805比特

5

2.12 计算习题2.9中的I (Y；Z)，I (X；Z)，I (XY；Z)，I (Y；Z|X)和I (X；Z|Y)。

解:

I(Y;Z)=H(Z)-H(Z/Y) =H(Z)- H(X3)= 3.5993-2.585 =1.0143比特 I(X;Z)=H(Z)-H(Z/X)=3.5993- 3.2744=0.3249比特 I(XY ;Z)=H(Z)-H(Z/XY) =H(Z)-H(Z/Y) =1.0143比特

I(Y;Z/X)=H(Z/X)-H(Z/XY)= H(X2+X3)-H(X3) =3.2744-2.585 =0.6894比特 I(X;Z/Y)=H(Z/Y)-H(Z/XY)=H(Z/Y)-H(Z/Y) =0

2.10 设有一个系统传送10个数字：0, 1, ?, 9。奇数在传送时以0.5的概率错成另外

的奇数，而其它数字总能正确接收。试求收到一个数字平均得到的信息量。

解:设系统输出10个数字X等概,接收数字为Y,

191显然 w(j)??Q(i)p(ji)?， H(Y)=log10 p(ji)??10i?110i?0H(Y/X)????p(x,y)log2p(yx)???p(x,y)log2p(yx)yx?偶yx?奇9?0??p(x)p(xx)log2p(xx)?i?奇y?x,奇x?奇??p(x)p(yx)log2p(yx)

1111??log22?5?4???log28102108?1比特?5?所以 I(X;Y)= log210?1?2.3219比特

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

ul=0000，u2=0011，u3=0101，u4=0110 u5=1001，u6=1010，u7=1100，u8=1111 通过转移概率为p的BSC传送。试求

(a) 接收的第一个数字0与ul之间的互信息量。 (b) 接收的前二个数字00与ul之间的互信息量。 (c) 接收的前三个数字000与ul之间酌互信息量。 (d) 接收的前四个数字0000与ul之间的互信息量。

解:（a）接收前一个数字为0的概率

w(0)??q(ui)p(0ui)?i?0812

I(u1;0)?log2p(0u1)1?p?log21?1?log2(1?p)w(0)2bits

6

（b）同理 w(00)??q(u)p(00u)?iii?0814

p(00u1)(1?p)2I(u1;00)?log2?log2?2?2log2(1?p)1w(00)4（c）同理 w(000)?bits

?q(u)p(000u)?iii?0818

p(000u1)(1?p)3I(u1;000)?log2?log2?3?3log2(1?p)1w(000)8bits

（d）同理 w(0000)??q(u)p(0000u)?iii?0818((1?p)6?6p2(1?p)2?p4)

p(0000u1)(1?p)4I(u1;0000)?log2?log21w(0000)((1?p)6?6p2(1?p)2?p4)8?log28

2.13 令X、Y、Z是概率空间，试证明下述关系式成立。

(a) H(YZ|X)≤H(Y|X)＋H(Z|X)，给出等号成立的条件。 (b) H(YZ|X)=H(Y|X)＋H(Z|XY)。

(c) H(Z|XY)≤H(Z|X)，给出等号成立的条件。

(1?p)(1?p)6?6p2(1?p)2?p44

bits 解: (b)

H(YZ/X)????p(xyz)logxyz1p(yz/x)1p(y/x)p(z/xy)11????p(xyz)logp(y/x)p(z/xy)xyz

????p(xyz)logxyz????p(xyz)logxyz?H(Y/X)?H(Z/XY)(c)

H(Z/XY)???p(xy)?p(z/xy)logxyz1p(z/xy)1（由第二基本不等式） p(z/x)???p(xy)?p(z/xy)logxyz?H(Z/X)或

7

H(Z/XY)?H(Z/X)???p(xy)?p(z/xy)logxyz1p(z/xy)???p(xy)?p(z/xy)logxyz1p(z/x)（由第一基本

???p(xy)?p(z/xy)logxyzp(z/x)p(z/xy)p(z/x)?1)p(z/xy)???p(xy)?p(z/xy)loge?(xyz?0不等式）

所以 H(Z/XY)?H(Z/X)，

等号成立的条件为p(z/xy)?p(z/x),对所有x?X,y?Y,z?Z,即在给定X条件

下Y与Z相互独立。

(a)

H(Y/X)?H(Z/X)?H(Y/X)?H(Z/XY)?H(YZ/X)

等号成立的条件为p(z/xy)?p(z/x),对所有x?X,y?Y,z?Z,即在给定X条件

下Y与Z相互独立。

2.14 对于任意概率事件集X、Y、Z，证明下述三角不等式成立。

H(X|Y)＋H(Y|Z)≥H(X|Z)

H(X|Y)/H(XY)＋H(Y|Z)/H(YZ)≥H(X|Z)/H(XZ)

解: (a) H(X/Y)?H(Y/Z)?H(X/YZ)?H(Y/Z)?H(XY/Z)?H(X/Z)

(b)

8

H(X/Y)H(Y/Z)H(X/Y)H(Y/Z)???H(XY)H(YZ)H(Y)?H(X/Y)H(Y)?H(Z/Y)H(X/Y)H(Y/Z)??H(Y)?H(X/Y)?H(Z/Y)H(Y)?H(Z/Y)?H(X/Y)H(X/Y)?H(Y/Z)?H(Y)?H(X/Y)?H(Z/Y)H(X/Y)?H(Y/Z)?H(YZ)?H(X/Y)H(X/Y)?H(Y/Z)?H(X/Y)?H(Y/Z)?H(Z)?H(X/Y)?H(Y/Z)?H(X/Z)?0,H(Z)?0H(X/Y)H(Y/Z)??H(XY)H(YZ)H(X/Y)?H(Y/Z)H(X/Y)?H(Y/Z)?H(Z)H(X/Z)? H(X/Z)?H(Z)H(X/Z)?H(XZ)?注：?a1?a2?0,b?0?a1b?a2b?a1b?a1a2?a2b?a1a2?

a1a2? a1?ba2?b2.15 令d(X，Y)=H(X|Y)＋H(Y|X)为X和Y的信息距离，令ρ(X，Y)=[H(X|Y)＋H(Y|X)]/H(XY)

为X和Y的信息距离系数。试证明有关距离的三个公理： d(X，X)=0 d(X，Y)≥0

d(X，Y)=d(Y，X)

d(X，Y)＋d(Y，Z)≥d(X，Z)

解: (a)

d(X,X)?H(X/X)?H(X/X)?0d(X,Y)?H(X/Y)?H(Y/X)?0

(b) d(X,Y)?H(X/Y)?H(Y/X)?H(Y/X)?H(X/Y)?d(Y,X) (c)

d(X,Y)?d(Y,Z)?H(X/Y)?H(Y/X)?H(Y/Z)?H(Z/Y)H(X/Y)?H(Y/Z)?H(X/YZ)?H(Y/Z)?H(XY/Z)?H(X/Z) 同理H(Z/Y)?H(Y/X)?H(Z/X)?d(X,Y)?d(Y,Z)?H(X/Z)?H(Z/X)?d(X,Z)

9

2.16 定义S(X，Y)=1－ρ(X，Y)=I(X；Y)/H(XY)为X和Y之间的信息相似度，证明：

0≤S(X，Y)≤1 S(X，X)=1

S(X，Y)=0，X和Y独立时。

解:(a)

I(X,Y)?H(X)?H(Y)?H(XY)?H(X)?H(Y)?H(XY)?H(X/Y)?H(Y/X)?H(XY)?S(X,Y)?

又由互信息的非负性，即I(X;Y)?0，有S(X;Y)?0，所以 0?S(X;Y)?1

I(X,Y)?1H(XY)I(X,X)H(X)?H(X/X)H(X)???1

H(XX)H(XX)H(X)(c) 当且仅当X和Y独立时，I（X；Y）=0，所以，当且仅当X和Y独立时，

I(X,Y)S(X,Y)??0。

H(XY)(b) S(X,X)?

2.17 令X→Y→Z为马尔可夫链，证明：

I(X；Z|Y)=0 I(XY；Z)=I(Y；Z) I(Y；Z|X)=I(Y|Z)－I(X；Z) I(Y；Z|X)≤I(Y；Z)

解: X→Y→Z为马尔可夫链，有p(z/xy)=p(z/y),对所有x,y,z。

10

I(X;Z/Y)?I(XY;Z)??????p(xyz)logp(z/y)zyxyxp(z/xy)?0???p(xyz)logzp(z/xy)p(z)???zyxp(z/y)p(xyz)logp(z)??zyp(z/y)p(yz)logp(z)p(z/xy)p(xyz)logp(z/x)p(z/y)p(z)?I(Y;Z)I(Y;Z/X)???

???zyxzyx???p(xyz)logp(z/x)p(z)??p(yz)logzyp(z/y)p(z/x)???p(xz)logp(z)p(z)xz

?I(Y;Z)?I(X;Z)I(Y;Z/X)?I(Y;Z)?I(X;Z)?I(Y;Z)(?I(X;Z)?0)

2.18 若三个随机变量有如下关系：x＋y=z，其中x和y独立。试证明：

H(X)≤H (Z) H(Y)≤H(Z) H(XY)≥H(Z) I(X；Z)=H(Z)－H(Y) I(XY；Z)=H(Z) I(X；YZ)=H(X) I(Y；Z|X)=H(Y)

I(X；Y|Z)=H(X|Z)=H(Y|Z)

解: (a) H(X)≤H (Z)

11

I(Y;Z)?H(Z)?H(Z/Y)H(Z/Y)????p(yz)logpz/y(z/y)????p(yz)logpx(z?y)zyzy????pz/y(z/y)p(y)logpx(z?y)????px(z?y)p(y)logpx(z?y)

zyzy???px(x)logpx(x)?H(X)x?I(Y;Z)?H(Z)?H(Z/Y)?H(Z)?H(X)?0即H(X)?H(Z)(b) H(Y)≤H(Z)

同理I(X;Z)?H(Z)?H(Z/X)H(Z/X)?H(Y)?I(X,Z)?H(Z)?H(Z/X)?H(Z)?H(Y)?0

即H(Y)?H(Z)(c) H(XY)≥H(Z)

H(Z/XY)?0I(XY;Z)?H(Z)?H(Z/XY)?H(Z)I(XY;Z)?H(XY)?H(XY/Z)?H(XY)

?H(XY)?H(Z)(d) I(X；Z)=H(Z)－H(Y) I(X;Z)=H(Z)-H(Z/X)=H(Z)-H(Y) (e) I(XY；Z)=H(Z)

H(Z/XY)?0I(XY;Z)?H(Z)?H(Z/XY)?H(Z)

(f) I(X；YZ)=H(X)

H(X/YZ)?0I(X;YZ)?H(X)?H(X/XY)?H(X)

(g) I(Y；Z|X)=H(Y) H(Y/XZ)=0

I(Y;Z/X)=H(Y/X)-H(Y/XZ)=H(Y/X)=H(Y)

(h) I(X；Y|Z)=H(X|Z)=H(Y|Z)

I(X;Y/Z)=H(X/Z)-H(X/YZ)=H(Y/Z)-H(Y/XZ)

12

而 H(X/YZ)=0,H(Y/XZ)=0

所以 I（X；Y/Z）=H(X/Z）=H(Y/Z) #

2.19 证明HK(P)是概率矢量P?(p1,p2,?,pK)的上凸函数，即对?，0

设 P1?(p11,p12,...,p1k),P2?(p21,p22,...,p2k),0???1?P1?(1??)P2?(?p11?(1??)p21,?p21?(1??)p22,...,?p1k?(1??)p2k)H(?P1?(1??)P2)???(?p1i?(1??)p2i)log(?p1i?(1??)p2i)i?1k????p1ilog(?p1i?(1??)p2i)?(1??)?p2ilog(?p1i?(1??)p2i)i?1ki?1kk????p1ilogp1i?(1??)?p2ilogp2ii?1i?1k??H(P1)?(1??)H(P2)不等式中的等号当且仅当P1?P2时成立. #

2.20 用拉格朗日乘因子法求解下述泛函的极值。

Hn(pl, p2, ?, pn)， 解：

?pni?1。

Hn(p1,p2,...,pn)???pilnpii?1令f(p1,p2,...,pn,?)?Hn(p1,p2,...,pn)???pii?1n由?f??lnpi?1???0,i?1,2,...,n,得 pi?e?(1??)?pin1由?pi?1,得 pi?.ni?1?2f1又2???0?pipi111?Hn(p1,p2,...,pn)极大值为Hn(,,...,)?logn#nnn

13

2.22 令U是非负整数集合，事件k∈U的概率为p(k)，且使H(U)为最大的分布p(k)。

解：

?kp(k)?A(常数)。试求

k?0?H(P)???pklnpk,约束条件为k?0? ?pk=1 和?kpk?A k?0k?0??设 f(p0,p1,...,?1,?2)???pklnpk??1?kpk??2?pk,k?0k?0k?0???由?f??lnpk?1??1k??2?0,得 pk?e?1k??2?1?pk??k?0k?0由约束条件?pk?1 和?kpk?A,得?e?{?k?0k?0?1k??2?1?1?A?ke?1k??2?1A1 ,e?2?1=1-e?1=1+A1+A1Ak?pk?(),k?0,1,2,...1+A1+A?H(P)为P的上凸函数,此时H(P)为极大值# 解得 e?1=

2.23 设X是在[－1，1]上为均匀分布的随机变量。试求Hc(X)，Hc(X 2)和Hc(X 3)。

解: (a)

?pX(x)???112,?1?x?10,其它

HC(X)???1log1dx?1比特 22?1(b) 令y?x,2dx1? dy2y 14

?1p?,y?1Y(y)??2y

??0,其它H2??C(X)?????pY(y)logpY(y)dy1???1log1dy02y2y

?1?log2e??0.443比特(c)

令z?x3,dx1?2dz?3z3 pdxZ(z)?pX(x)dz?1?2 ??3??6z,z?1?0,其它H??C(X3)?????pZ(z)logpZ(z)dz01??1z?2223log(6z3)dz??16?1z?23log(6z3)dz06 ?log26?2log2e??0.3比特

2.24．设连续随机变量X和Y的联合概率密度为

?1x2f(xy)???a2?y2b2?1,a?0,b?0??ab?0其它试求Hc(X)，Hc(Y)，Hc(XY)及I(X；Y)。 解：

15

??pb2?b2x(x)?xy)dy?(xy)dy?2?a1?x2f???f(?2x2a?b2?b22x2aa2,x?a同理??2py(y)?f(xy)dx?(xy)dx?2????a2?a2y2b?a2?a22b2y?b1?y2fb2,y?b??Hac(X)???px(x)logpx(x)dx?ln???e

??Hc(Y)???py(y)logpy(y)dy?ln?b??e????Hc(XY)??(xy)logf(xy)dxdy?ln(?ab)??????fI(X;Y)?Hc(X)?Hc(X)?Hc(XY)?ln?e#

2.25 设X和Y为连续随机变量，且X的概率密度为

q(x)?1x2/4?22??e?

条件概率密度为

p(y|x)?(1x)2/3?223??)e?(y?1

其中－∞

X~N(0,2?2),?2x?2?2,??Hc(X)???q(x)logq(x)dx?12log(4?e?2) 0 16

????Hc(Y/X)??????????????q(x)p(y/x)logp(y/x)dxdy1?????????2??e?x2/4?211?(y?x)2/3?2?(y?x)2/3?211()e2log()e2dxdy3??3??1log(3?e?2)2??w(y)????q(x)p(y/x)dx??2???1?e?x2/4?21?(y?x)2/3?211?y2/4?22()edx?e3??2??Hc(Y)?1log(4?e?2)21log(4/3)21Hc(X/Y)?Hc(X)?I(X;Y)?log(3?e?2)2I(X;Y)?Hc(Y)?Hc(Y/X)?

2.27 设x为[0，∞]上分布的连续随机变量，且满足求实现最大微分熵的分布及相应的熵值。

解：

??#??0xq(x)dx=S，

Hc(X)???q(x)lnq(x)dx, 约束条件为0???? ?q(x)dx=1 和?xq(x)dx=s .00??????设 f(q(x),?1,?2)???q(x)lnq(x)dx??1?xq(x)dx??2?q(x)dx000????0e??1x??2q(x)lndx?q(x)???0e??1x??2q(x)(?1)dxq(x)当f(q(x),?1,?2)为最大值时,Hc(X)在约束条件下取得最大值,此时q(x)?e??1x??2

17

????由约束条件?q(x)dx=1 和?xq(x)dx=s,得00????1x??2edx?1?{??0?0xe??1x??2dx=s

1 解得 ?1? ,?2?lnssx1?s?实现Hc(X)max的分布为q(x)?e,x?0s??xx1?s1?sHc(X)max???elnedx?lns?1#ss02.28 令概率空间X???1/21/2??，令Y是连续随机变量。已知条件概率率密度为

???1?1??1/4p(y|x)???0试求：

?2?y?x?2其它

(a) Y的概率密度ω(y) (b) I(X；Y)

(c) 若对Y作如下的硬判决：

?1?V??0??1?y?1?1?y?1

y??1 求I(X；Y)，并对结果进行解释。

解:(a) 由已知，

,?3?y?1?1p(yx??1)??4

0,其它?,?1?y?3?1p(yx?1)??4

0,其它? 18

w(y)??pxy(xy)??px(x)pyx(yx)xx?px(x??1)pyx(yx??1)?px(x?1)pyx(yx?1) ,?3?y??1?18?1?4,?1?y?1??1?8,1?y?3?其它?0,（b）

?1118314H(Y)??3?log28dy??1?log24dy??1log28dy81

?2.5bits13141log24dy?12?4log24dy?1H(YX)??2bits12?3?

?I(X;Y)?H(Y)?H(Y/X)?0.5bit

(c)由

?1,y?1?v??0,?1?y?1 ??1,y??1?可求得V的分布为

??101?V???111?? ?424??1,y?1?再由p(y/x)及v??0,?1?y?1可求得V的条件分布为

??1,y??1?,(v,x)??(?1,?1),(0,?1),(0,?1),(?1,?1)??1p(v/x)??2

0,(v,x)??(?1,?1),(1,?1)??1?H(V)?2?1log4?log22?1.5bit242H(V/X)???p(x??1)p(v/x??1)log2p(v/x??1)??p(x?1)p(v/x?1)log2p(v/x?1)vv?1bitI(V;X)?H(V)?H(V/X)?0.5bit可见I(X;Y)?I(X;V),Y?V变换没有信息损失.

19

第三章 离散信源无失真编码

3.1解:长为n码字的数目为Dn ,因此长为N的D元不等长码至多有：

D(DN?1) ?D?

D?1k?1Ni3.2 解:

(a)长为100的事件序列中含有两个和更少个a1的序列数目为012M?C100?C100?C100?1?100?4950?5051因此在二元等长编码下所需码长为

N??log25051???12.3??13 (b)误组率为长为100的事件序列中含有三个a1的序列出现的概率,因此有012Pe?1?C1000.996100?C100?0.99699?0.004?C100?0.9962?0.0042?7.755?10?33.3 解: 3.4 解:

20

(a)码A中,任一码字不是其它码字的字头,是异字头码.码B不是异字头码,但码A和码B均是唯一可译码.(b)对码AI(ap(a11)1;1)?log2p(a?log12(a?1.321)p1)bit对码BI(a1;1)?logp(a11)2p(a?logp(a1)2)?0bit1)p(a1(c)U??a1,a2,a3,a4?对码A,4I(U;1)??p(ap(ak1)k1)log2p(?1.32bitk?1ak)对码B4I(U;1)??p(ak1)logp(ak1)2k?1p(a)?0bitk3.5解:

（a）二元Huffman编码

10H(U)???p(ak)log2p(ak)?3.234bitsk?1平均码长10n??p(ak)nk?3.26

k?1编码效率??H(U)R?H(U)nlog?3.23426?99.2-3.（b）三元Huffman编码

注意：K=10为偶数，需要添一个概率为零的虚假符号

平均码长10n??p(ak)nk?2.11k?1编码效率

??H(U)H(U)R?nlog?3.234?96.6-2.11?log23

21

3.6解:二元Huffman编码 （a）二元Huffman编码

3H(U)???p(ak)log2p(ak)?1.485bitsk?1平均码长3n??p(ak)nk?1.5

k?1编码效率??H(U)H(U)1.R?nlog?4852D1.5?99%（b）

H(U2)?H(U1U2)?2H(U)?2.97bits平均码长9n2??p(ak)nk?3.0

k?1编码效率??H(U2)2H(U)2R?nD?.97?992log23.0%（c）

H(U3)?H(U1U2U3)?3H(U)?4.455bits平均码长27n3??p(ak)nk?4.487k?1编码效率??H(U3)3H(U)4.455R?n??99.32%3log2D4.4873.10 傅P186【5.11】 3.11 解: 3.12 解: 对

22

3.13 解:

(a)根据唯一可译码的判断方法可知,输出二元码字为异字头码,所以它是唯一可译码。

H(U)??0.9?log20.9?0.1?log20.1?0.469 比特 (b)因为信源是二元无记忆信源，所以有 P(Si)?P(Si1)P(Si2)?P(Sin)

其中Si?(Si1,Si2,?,Sin)Si1,Si2,?,Sin??0,1?

S0?1,l1,0?1,p(S0)?0.1S1?1,l1,1?1,p(S1)?0.09S2?1,l1,2?1,p(S2)?0.081S3?1,l1,3?1,p(S3)?0.729S4?1,l1,4?1,p(S4)?0.06561

S5?1,l1,5?1,p(S5)?0.059049S6?1,l1,6?1,p(S6)?0.0531441S7?1,l1,7?1,p(S7)?0.04782969S8?1,l1,8?1,p(S8)?0.43046721可计算每个中间数字相应的信源数字的平均长度 L?81??P(Si)l1,i?5.6953 信源符号/中间数字

i?0(c) 根据表有

l2,0?l2,1?l2,2?l2,3?l2,4?l2,5?l2,6?l2,7?4,l2,8?1

可计算每个中间数字所对应的平均长度

L?82??P(Si)l2,i?2.7086二元码/中间数字

i?0_由

L2_?0.4756 二元码/信源符号

L1 23

编码效率为0.4756/0.469=98.6% 精选题

1.傅P191【5.15】 2.傅P192【5.16】

信道及其容量

作业：4.1 4.3 4.5 4.8 4.9 4.10 4.12 4.14 4.1解： (a) 对称信道 (b) 对称信道

(c) 和信道(课堂教学例题)! 4.3解：

(a): 可先假设一种分布,利用信道其容量的充要条件来计算(课堂教学例题)

(b): 准对称信道！ 4.5解：课堂教学例题

4.8解：该题概率有误，应把1/32改为1/64。 每个符号的熵为

H(S)???pilog2pi?2bits

i?18采样频率Fs为 Fs=2W=8000 Hz

24

所以信息速率R为

R?Fs ?H(S)?8000?2?1.6?104 bps

4.9解：每象点8电平量化认为各级出现的概率相等，即H(U)=3 bits 所以信息速率R为

R?30?500?600??2.7?107bps

4.10解：

S?30dB?1000,T?3?60sNSC?Wlog2(1?)?3000?log2(1?1000)?29.9kb/s

N所以,3分钟可能传送话音信息为W?3KHz,29.9?1000?3?60?5.382?106bits

4.12解：W?8KHz,S?31 N高斯信道的信道容量为

C高斯?Wlog2(1?S)?8000?log2(1?31)?4?104bpsNR?105bps?4?104bps?C高斯所以,如该信道是高斯信道,不可实现。如该信道不是高斯信道,因此时信道容量C大于高斯信道的信道容量，即C?4?104bps,但无法判定R与信道容量C的大小关系，故无法判定是否能实现。如R?3?104bps，则一定可以实现，因R?C高斯?C。4.14解：

第五章 离散信道编码定理

习题5.1

解：DMC信道

25

??111?36?P??2?111??623??111? ???362??有

Q(x111)?2,Q(x2)?Q(x3)?4

w(y111)?2?2?14?(16?13)?38w(y)?111112?3?4?(122?6)?3

w(y?1111173)2?6?4?(3?2)?24因为

P(xp(x1)p(y1x1)11)??2?1221yw(y1)3?

83P(xp(x1)p(y2x1)1?1211y2)?w(y?31?

2)32P(x?p(x1)p(y3x1)12?121y3)w(y?67?

3)247xp(x2)p(y3x2)1?1P(2y3)?w(y?4323)7?

247P(xp(x3)p(y3x3)1?13y3)??423w(y3)7?

247所以

最大后验概率译码为： y1和y2判为x1,y3判为x3。译码错误概率为：

26

pe?Q(x1)P(y3x1)?Q(x2)?Q(x3)(1?p(y3x3))11111????(1?)2644211?24?

若按最大似然译码准则译码为：y1判为x1,y2判为x2,y3判为x3 译码错误概率为：

pe?Q(x1)(1?P(y1x1))?Q(x2)(1?P(y2x2))?Q(x3)(1?p(y3x3))111111?????(1?)2242421?2?

可见,最大似然译码的译码错误概率大于最大后验概率译码的译码错误概率。

第七章 信道编码

1. 设(7,3)码的生成矩阵为

?1011100?? G??0110110????0001111??(1) 写出该码的一致校验矩阵H； (2) 写出该码的所有许用码字；

(3) .写出该码的“译码表”---标准译码表或简化(伴随式)译码表； (4) 写出接收矢量R=1000001的错误图样,并译相应的许用码字；

(5) 写出该码在

BSC(错误转移概率为p)中传输的(平均)正确译码

概率pc的表达式；

(6) 写出该码在

BSC(错误转移概率为p)中传输的漏检概率Pud(也

27

称不可检测错误概率)的表达式.

解: (1) G不为系统码形式,我们通过初等行变换变为系统码形式

?1011100??1011100??~?1101010? 0110110 G????????0001111????0001111???1011100?? 1101010 ~?????0111001??因此

?1?0?H??0?0??000110?100011??010101? 001111???(2) 由C=MG得该码的许用码字为

0000000,0111001,1101010,1010011,1011100,1100101,0110110,0001111 该码的最小汉明距离为4。

(3) 该码的标准阵由16个陪集构成, 在BSC(错误转移概率为p<1/2)应将重量最小的错误图样选作陪集首, 故该码的标准译码表为

许用码字 0000000 (陪集首) 0000001 0000010 0000100 禁用码字 0001000 0010000 0100000 1000000 0111000 0111011 0111101 0110001 0101001 0011001 1111001 1101011 1101000 1101110 1100010 1111010 1001010 0101010 1010010 1010001 1010111 1011011 1000011 1110011 0010011 1011101 1011110 1011000 1010100 1001100 1111100 0011100 1100100 1100111 1100001 1101101 1110101 1000101 0100101 0110111 0110100 0110010 0111110 0100110 0010110 1110110 0001110 0001101 0001011 0000111 0011111 0101111 1001111 0111001 1101010 1010011 1011100 1100101 0110110 0001111 28

0000011 0000101 0001001 0010001 0100001 1000001 1001000 1110000 0111010 0111100 0110000 0101000 0011000 1111000 1110001 1001001 1101001 1101111 1100011 1111011 1001011 0101011 0100010 0011010 1010000 1010110 1011010 1000010 1110010 0010010 0011011 0100011 1011111 1011001 1010101 1001101 1111101 0011101 0010100 0101100 1100110 1100000 1101100 1110100 1000100 0100100 0101101 0010101 0110101 0110011 0111111 0100111 0010111 1110111 1111110 1000110 0001100 0001010 0000110 0011110 0101110 1001110 1000111 1111111 译码规则为若接收矢量在第i列出现,则译码输出为对应列中的码字,也就是陪集首为可纠正错误图样. 伴随式译码表为

伴随式 0000 0111 1101 1011 0001 0010 0100 1000 1010 1100 0110 0101 0011 1111 1001 1110 陪集首 0000000 0000001 0000010 0000100 0001000 0010000 0100000 1000000 0000011 0000101 0001001 0010001 0100001 1000001 1001000 1110000

(4) 接收矢量R=1010101出现在标准译码表的第五列, 译码输出为

29

1011100, 错误图样为0001001.

(5) 该码标准译码表的陪集首重量分布为 A0=1,A1=7,A2=7,A3=1,A4=A5=A6=A7=0 所以正确译码概率pc为

7Pi3c??Aip(1?p)7?i?(1?p)7?7p(1?p)6?7p2(1?p)5?p(1?p)4i?0注意：i=0

(6) 该码的重量分布为

A0=1,A1=A2=A3=0,A4=7,A5=A6=A7=0 所以该码在BSC中传输的漏检概率Pud为

7Piiud??Aip(1?p)7??7p4(1?p)3

i?1注意：i=1

30

本文来源：https://www.bwwdw.com/article/136g.html