信息论与编码理论习题答案(2)

??14,?2?y?x?2 p(y|x)??，求：

??0,其他 (a)Y的概率密度?(y) (b)I(X;Y)

(c) 若对Y做如下硬判决

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

??1,??y??1? 求I(X;V)，并对结果进行解释。

解：(a) 由已知，可得

?1????3?y?1p(y|x??1)=?4

??0??else?1????1?y?3 p(y|x?1)=?4

??0??else ?(y)=p(x??1)p(y|x??1)+p(x?1)p(y|x?1)

?1?8???3?y??1?1?????1?y?1 =?4

?1???1?y?3?8??0??else1?111log8?2?log4=2.5 bit (b) HC(Y)=???3?184 HC(Y|X)=?p(x??1)?p(y|x??1)logp(y|x??1)dy

?31 ?p(x?1)?p(y|x?1)logp(y|x?1)dy

?1311111311 =??logdy??logdy =2 bit

2?3442?144 I(X;Y)=HC(Y)-HC(Y|X)=0.5 bit

(c) 由?(y)可得到V的分布律

V p 再由p(y|x)可知

V p(V|x=-1) p(V|x=1)

11log2??2log4?1.5 bit 241112?log2]?2=1 bit H(V|X)?[log222-1 1/4 0 1/2 1 1/4 -1 1/2 0 0 1/2 1/2 1 0 1/2 H(V)? I(X;V)=H(V)?H(V|X)= 0.5 bit

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

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

(a)对于0???1，证明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 又0???1，则

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?(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

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

ND(D?1)3.1 试证明长为N的D元等长码至多有

个码字。

D?1证：①在D元码树上，第一点节点有D个，第二级有D2，每个节点对应一

D(1?DN)D(DN?1)个码字，若最长码有N，则函数有?D==，此

1?DD?1i?1Ni时，所有码字对应码树中的所有节点。

②码长为1的D个；码长为2的D2个，…，码长为N的DN个

D(DN?1)∴总共?D=个

D?1i?1Ni

?a2??a1,?3.2 设有一离散无记忆信源U??若对其输出的长为100的事件序?。

??0.004,0.996??列中含有两个或者少于两个a1的序列提供不同的码字。 (a) 在等长编码下，求二元码的最短码长。 (b) 求错误概率（误组率）。 解: (a)不含a1的序列 1个

1长为100的序列中含有1个a1的序列 C100=100个 2长为100的序列中含有2个a1的序列 C100=4950个

∴所需提供码的总数M=1+100+4950=5051 于是采用二元等长编码N?logM =12.3，故取N=13 logD(b)当长度为100的序列中含有两个或更多的a1时出现错误， 因此错误概率为

012Pe=1?C100(0.996)100-C100(0.004)(0.996)99?C100(0.004)2(0.996)98

=7.775?10?3

?a1,a2???3.3 设有一离散无记忆信源，U=?13?，其熵为H(U)。考察其长为L的输出

?,??44?序列，当L?L0时满足下式

?I(uL)?Pr??H(U)????? ?L?(a)在?=0.05，?=0.1下求L0 (b)在?=10?3，?=10?8下求L0 (c)令T是序列uL的集合，其中

I(uL)?H(U)?? L 试求L=L0时情况(a)(b)下，T中元素个数的上下限。

134解：H(U)=??pklogpk=log4?log=0.81 bit

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

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

=?pk(logpk)2?H2(U)

k =0.471

则根据契比雪夫大数定理

?I(uL)??Pr??H(U)????I2?? ?L?L?2?I20.471(a) L=2==1884

0.1?(0.05)2???I20.47113?10(b) L?==4.71 ?8?32210?(10)???(c) 由条件可知uL为典型序列，若设元素个数为MT，则根据定理

(1???)2L(H(U)???)?MT?2L(H(U)???)

其中????，????，可知