《信息论、编码与密码学》课后习题答案

《信息论、编码与密码学》课后习题答案

第1章 信源编码

1.1

考虑一个信源概率为{0.30，0.25，0.20，0.15，0.10}的DMS。求信源熵H（X）。

解： 信源熵 H(X)???pklog2(pk)

k?15

H(X)=-[0.30*(-1.737)+0.25*(-2)+0.2*(-2.322)+0.15*(-2.737)+0.1*(-3.322)]

=[0.521+0.5+0.464+0.411+0.332] =2.228(bit)

故得其信源熵H(X)为2.228bit

1.2 证明一个离散信源在它的输出符号等概率的情况下其熵达到最大值。 解： 若二元离散信源的统计特性为

P+Q=1 H(X)=-[P*log(P)+(1-P)*log(1-P)] 对H(X)求导求极值，由dH(X)/d(P)=0可得

plog?01?pp?11?p

1p?2可知当概率P=Q=1/2时，有信源熵H(X)max

对于三元离散信源，当概率

?1(bit)

时，信源熵

P1?P2?P3?1/3H(X)max?1.585(bit)，

此结论可以推广到N元的离散信源。

1.3 证明不等式lnx?x?1。画出曲线y1?lnx和y2?x?1的平面图以表明上述不

等式的正确性。 证明：

f(x)?lnx?x?1(x?0)1f(x)??x令f(x)??0，x?1又有x?0?0?x?1时f(x)??0此时f(x)?fmax?0也即lnx?x?1当x?1时同理可得此时lnx?x?1综上可得lnx?x?1证毕

绘制图形说明如下 可以很明确说明上述 不等式的正确性。

1.4 证明I(X;Y)?0。在什么条件下等号成立？

（IX；Y）=??P(xi,yj)I(xi,yj)i?1j?1nm y Y=x-1 1 x Y=lnx ???P(xi,yj)logi?1j?1nmP(xi,yj)P(xi)P(yj)

当和相互独立时等号成立。

1.5 有一个信源X，它有无穷多个可能的输出，它们出现的概率为P（Xi）=2i-1,i=1,2,3,?.,这个信源的平均自信息H（X）是什么？

解：因为 P（Xi）=2i-1,i=1,2,3,?

所以 H（X）= -?p(xi)logp(xi)

i?1n

=-log2(2+2.22+3.23+?..+n.2n) =2-（1-n）2n+1

i-1

1.6 考虑另一个几何分布的随机变量X，满足P（Xi）=P（1-P）i=1,2,3,?..,

这个信源的 平均自信息H（X）是什么？

解：因为 P（Xi）= P（1-P）i-1,i=1,2,3,

所以H（X）= -?p(xi)logp(xi)

i?1n

=-logp(1-p)[p(1-p)+2p(1-p)2+3p(1-p)3+??.+np(1-p)n]

(p?1)2=(1-n)(1-p)- pn+1

1.7 考虑一个只取整数值的随机变量X，满足P?X?n??1，n?2,3,...,?。求熵H?X?。 2n?2nlogn?1，其中2AnlognA??

解：为了方便计算，设B?nlogn，则A??211，P?X?n??；

ABBn?2??1?根据公式计算自信息量为：I?X??log??P?X????log?AB?；

????1?logB???????B1log?AB??则熵为：H?X???P?X?I?X???log?AB???????n?2?=？

1ABn?2n?2ABn?2n?2B??n?2B1.8 计算概率分布函数为

?a?1p?x????00?x?a

?否则?的均匀分布随机变量X的微分熵H?X?。画出H?X?相对于参数a?0.1?a?10?的平面图，并对结果进行评论。

解：根据公式（1-21）可知，微分熵为：H?X????p?x?logp?x?dx

????当0?x?a时，p?x??a?1，则

H?X????a?1loga?1dx?0a1logaa?loga??x?0??a?loga aa当x?0或x?a时，p?x??0 ，则H?X???

根据得到的结果可以画出相应的平面图，由图可以看到随着a的增加，即p?x?的减小，微分熵H?X?相应的增加。

H?X?

0.1 0 10 a

1.9考虑一个信源的概率为?0.35,0.25,0.20,0.15,0.05?的DMS。 （1）给出此信源的霍夫曼码。 （2）计算出这些码子的平均码长R。 （3）这个码的效率?是多少？

解：1）依题意，由霍夫曼编码的规则，得：

1 1.00 x1 0.35

1 0.65 0.40 0

0 x2 0.25 x3 0.20 x4 0.15 0 0.20 0 1 1 x5 0.05

表格如下：

符号

概率 0.35 0.25 0.20 0.15 0.05

自信息 1.515 2.000 2.322 2.738 4.322

码字 1 01 000 0010 0011

x1 x2

x3 x4

x5

2）由平均码长公式 R?5?n(xk?1nk)?p(xk),代入数据，得：

R??n(xk)?p(xk)?1(0.35)?2(0.25)?3(0.20)k?1?4(0.15)?5(0.05)?0.35?0.5?0.6?0.6?0.25?2.3(bit)3）首先，该信源的熵为：

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