信息论与编码理论-习题答案_姜楠_王健_编著_清华大学

第1章 绪论

1.1 1.2 1.3 1.4

信源、编码器、信道、干扰、译码器、信宿 香农

通信系统模型

信号是消息的表现形式，是物理的，比如电信号、光信号等。消息是信息的载荷者，是信号的具体内容，不是物理的，但是又比较具体，例如语言、文字、符号、图片等。信息包含在消息中，是通信系统中被传送的对象，消息被人的大脑所理解就形成了信息。 1.5 略

第2章 信息的统计度量

2.1 2.2 2.3 2.4 2.5

少

y的出现有助于肯定x的出现、y的出现有助于否定x的出现、x和y相互独立 FTTTF 2.12比特

依题意，题中的过程可分为两步，一是取出一枚硬币恰好是重量不同的那一枚，设其发生的概率为p1，由于每枚硬币被取出的概率是相同的，所以

p1?所需要的信息量

1 81I?A???logp1?6.34?bit?

二是确定它比其他硬币是重还是轻，设其发生的概率为p2，则

p2?总的概率

12

p?p1p2?所需要的信息量

111??812162

I??logp?log162?7.34?bit?

2.6 设A表示“大学生”这一事件，B表示“身高1.60m以上”这一事件，则

p?A??0.25p?B??0.5p?B|A??0.75

故

p?A|B??

p?AB?p?B??p?A?p?B|A?p?B??0.75?0.25?0.375

0.5

I?A|B??log11?log?1.42?bit?

p?A|B?0.3752.7 四进制波形所含的信息量为log4?2?bit?，八进制波形所含信息量为log8?3?bit?，故四进制波形所含信息量为二进制的2倍，八进制波形所含信息量为二进制的3倍。

2.8

I?2???log2p?bit?I?3???log3p?bit?I?3?I?2??log23?1.585

故以3为底的信息单位是比特的1.585倍。 2.9 （1）J、Z（2）E（3）X

2.10 （1）两粒骰子向上面的小圆点数之和为3时有(1, 2)和(2, 1)两种可能性，总的组合数为

11C6?C6?36，则圆点数之和为3出现的概率为

p3?故包含的信息量为

21?3618

1?4.17?bit?18

（2）小圆点数之和为7的情况有(1, 6), (6, 1), (2, 5), (5, 2), (3, 4), (4, 3)，则圆点数之和为7出现的概率为

I?3???logp3??logp7?故包含的信息量为

61?366

1?2.585?bit?6

I?7???logp7??log2.11 对于男性，是红绿色盲的概率记作p?a1??7%，不是红绿色盲的概率记作p?a2??93%，

这两种情况各含的信息量为

I?a1??log??1p?a1????logI?a2??log??1p?a2????log平均每个回答中含有的信息量为

100?3.83?bit?7

100?0.105?bit?93

793?3.83??0.105?0.366?bit?100100

H?A??p?a1?log??1p?a1????p?a2?log??1p?a2????对于女性，是红绿色盲的概率记作p?b1??0.5%，不是红绿色盲的概率记作p?b2??99.5%，则平均每个回答中含有的信息量为

H?B??p?b1?log??1p?b1????p?b2?log??1p?b2???510009951000?log??log100051000995?0.045?bit??

所以

H?A??H?B?

2.12 天平有3种状态，即平衡，左重，左轻，所以每称一次消除的不确定性为log3，12个

?11?球中的不等重球（可较轻，也可较重）的不确定性为：?log????log24，因为

?122?3log3?log24,所以3次测量可以找出该球。

2.13 （1）当最后3场比赛麦克胜的次数比大卫多时，麦克最终才能胜，因此

P?胜??P?麦克胜3场??P?大卫胜少于3场?+P?麦克胜2场??P?大卫胜少于2场??P?麦克胜1场??P?大卫胜0场?17343122???????88888864

同理

P?负??麦克最终比赛结果的熵为

22222220，P?平??1???64646464

222222222020?222220?H?,,???log?log?log646464646464?646464?2220?log64?2?log22?log2064644420?6??4.4594??4.32196464?6?3.0659?1.3506

因为胜、负、平这3种结果接近等概，所以该随机变量的熵接近最大熵。

（2）假定大卫最后3场比赛全部获胜，那么麦克也必须全部获胜最后3场比赛最终才能得平，否则就是负。麦克3场比赛全部获胜的可能性是2?3?1/8，因此在假定大卫最后3场比赛全部获胜的情况下麦克的最终比赛结果的条件熵是

7?1?H???3?log7?0.5436比特结果8?8? 2.14 （1）假定一个家庭里有k个女孩，1个男孩，相应的概率是0.5k?0.5，因此女孩的平

均数是0.5?k0.5k?1，女孩的平均数和男孩的平均数相等。

k?1??1.5835比特结果（2）H?X????0.5ilog?0.5i??2

i?1?2.15 （1）根据题意，可以得到：

p?E??p?F??p?U??1 ①

②

1.0p?E??0.5p?F??0.0p?U??0.95由式②可以得到：

p?F??1.9?2p?E? ③

将式③代入式②得到：

p?E??0.9?p?U? ④

由于p?E?,p?F?,p?U?的取值必须在0到1之间，由式③和式④可以得到p?E?的取值范围在0.9到0.95之间。 (2)就业情况的熵为

?1??1??1?H?p?E?log??pFlog?pUlog?????????pEpFpU???????????????????1?????11?p?E?log??1.9?2pElog?pE?0.9log??????????????????p?E????1.9?2p?E????p?E??0.9?? ???它在p?E?的取值范围内的曲线如图所示。

0.5 0.45 0.4 0.35 0.3 0.250.00.010.020.030.040.05

（3）当p?E??0.9081时，H?0.4823达到最大值，这时p?F??0.0838，p?U??0.0081。 2.16 假设X表示当地的实际天气情况，Y表示气象台预报的天气情况，Z表示总是预报不

下雨的天气情况。

H?X??0.696比特符号

I?X;Y???p?xy?logx,yp?xy?p?x?p?y?311013110?log?log16?log16?log163516513163111611138????1616161616161616?0.0906比特符号

I?X;Y???H?X?，可见气象台预报的确实不好。

18但是如果总是预报不下雨的话则会更糟，因为X和Z是相互独立的两个随机变量，即I?X;Z??0，所以

I?X;Y??I?X;Z?,H?X|Z??H?X|Y?

因此气象台的预报准确率虽然比总是预报不下雨低，但还是传递了一些信息，消除了一些不确定性。

2.17 由互信息量的定义

I?xi;yj??log因为pxi|yj?1，则有

p?xi|yj?p?xi?

??I?xi;yj??log同理，因为pyj|xi?1，则有

p?xi|yj?p?xi??log1?I?xi? p?xi???I?yj;xi??logp?yj|xi?p?yj??log1?I?yj? p?yj?2.18 （1）根据熵的极值性，当随机变量等概分布时，随机变量的熵最大。有7个可能取值

的随机变量的最大熵为log7，随机变量X不是等概分布，所以H?X??log7。 ?22222?2?1?2?1?（2）根据熵的递增性，H?X??H?,,,,??H???H???log5。

?1010101010?10?2?10?2?（3）

H?X????p?x?logp?x???3?x2211log?4?log101010106log2?3.322?0.610?2.722比特符号?log10?

2244log?log10101010H?Y????p?y?logp?y???3?y64log2?log41010?3.322?0.6?0.8?log10??1.922比特符号

（4）因为随机变量Y是X的函数，所以

H?XY??0比特符号

H?XY??H?XY??H?Y??H?X??H?YX??H?Y??0.8比特符号2.19 假定p1为最大的概率。根据熵函数的性质，如果p1?11，则熵小于2；如果p1?，则2211?11111?只有一种可能：?,,,,?。如果?p1?，则有无数个解，其中之一为

42?28888?

?0.375,0.25,0.25,0.97859,0.027141?；如果p1??2?9?22.20 ??9??2??95361721725?36??1? 72??1?72??1，则没有解。 42a32.21 ?logb??log

3e第3章 离散信源

3.1 p(x2)

3.2 5 3.3 1 3.4 2

3.5 （1）87.81bit （2）1.95bit 3.6 Hmax(X)=1

3.7 （1）消息符合的平均熵

1133H?X???log?log?0.81?bit?

4444（2）自信息量为

4I?X??mlog4??100?m?log?200??100?m?log3

3（3）（2）中的熵为

1m??H?X??I?X??2??1??log3

100100??3.8 因为边沿分布

p?ai???p?aiaj?

j?13条件分布概率p?aj|ai??p?aiaj?p?ai?如下：

p?aj|ai? 0 0 9/11 2/11 0 ai 1 1/8 3/4 1/8 2 0 2/9 7/9 aj 所以信息熵：

1 2

3H?X????p?ai?logp?ai??1.542?bit?

i?1条件熵：

H?X2X1?????p?aiaj?logp?aj|ai??0.87?bit符号?

i?1j?133联合熵：

H?X1,X2?????p?aiaj?logp?aiaj??2.41?bit二个符号?

i?1j?133或

H?X1,X2??H?X1??H?X2|X1??1.542?0.87?2.412?bit二个符号?

可知

H?X2|X1??H?X?

解释：

（1）信源的条件熵H?X2|X1?比信源熵H?X?少0.672bit符号。这是由符号之间的相互依存性造成的。

（2）联合熵H?X1,X2?表示平均每两个信源符号所携带的信息量。平均每一个信源符号所携带的信息量近似为

1H2?X??H?X1,X2??1.205?bit符号?

2因此

H2?X??H?X?

原因：略去了?X1X2?和?X2X3?之间的依赖性。 3.9 由定义，信源的熵

H?X????p?ai?logp?ai??0.2log0.2?0.19log0.19?0.18log0.18?i?160.17log0.17?0.16log0.16?0.17log0.17?log6.28?2.64?log6

信源的概率分布要求满足?p?ai??1，而此题中?p?ai??1.07?1。即各种可能发生的情况下，概率之和大于“1”。在实际情况下这是不可能发生的。 3.10 由题意可知，联合概率分布为 X Y1 0 1 2

0 1/4 0 1/4 1 0 1/4 1/4

X Y2 0 1 2 Y的分布为

Y1 P(y1)

Y2 P(y2) 所以

H?Y1??H?Y2??1?bit?H?Y1|X????p?xy1?logp?y1|x??0.5?bit?XY10 1/4 1/4 0 1 0 0 1/2 1 1/2 1 1/2 0 1/2 0 1/2 H?Y2|X????p?xy2?logp?y2|x??0?bit?

XY2I?X;Y1??H?Y1??H?Y1|X??0.5?bit?I?X;Y2??H?Y2??H?Y2|X??1.0?bit?由于

I?X;Y1??I?X;Y2?

所以，第二个实验好。 3.11 由定义

H?X2??H?X2,X1??H?X1?+H?X2|X1??H?X2|X1?由于一阶马尔科夫信源之间的相关性，导致熵减小。 3.12 （1）一阶马尔可夫过程的状态转移图如图所示。

1/3s11/31/31/31/31/3s31/3s21/3

1/3

1一阶马尔可夫过程共有3种状态，每个状态转移到其他状态的概率均为，设状态的平稳分

3布为W??W1,W2,W3?，根据

??W1??W?2???W3???111?W1?W2?W3333111?W1?W2?W3333 111?W1?W2?W3333W1?W2?W3?1可得W??1/3,1/3,1/3?，3种状态等概率分布。 一阶马尔可夫信源熵为

1?111?H2?3??H?,,??1.585比特符号

3?333?信源剩余度为

??1?H2H?1?2?0 H0log3（2）二阶马尔可夫信源有9种状态（状态转移图略），同样列方程组求得状态的平稳分布为 ?111111111?W??,,,,,,,,?

?999999999?二阶马尔可夫信源熵为

1H3?9?log3?1.585比特符号

9信源剩余度为

H3H?1?3?0 H0log3??1?由于在上述两种情况下，3个符号均为等概率分布，所以信源剩余度都等于0。 3.13 （1）由题中条件，该信源是离散无记忆信源，对任意i1,i2,x1,x2,xN??0,1?XiN?xN,iN和h?0，

pXi1?x1,Xi2?x2,?0.4N1?0.6N?N1???

?pXi1?h?x1,Xi2?h?x2,?XiN?h?xN其中N1为x1,x2,xN中0的个数。

故该信源是平稳的。

（2）由离散无记忆信源的扩展信源的性质

N??limHN?X??limHN?XN|X1X2N??XN?1??H?X??0.971?bit?

（3）

H?X4??4H?X??4???0.4log0.4?0.6log0.6??3.884?bit?

可能发出的符号有0000，0001，0010，0011，0100，0101，0110，0111，1000，1001，1010，

1011，1100，1101，1110，1111。 3.14 状态转移矩阵

?21?P??33?

???10????7?92P???2??32?9?? 1?3??故该马尔科夫信源是遍历的。

设

W??W1W2?

由

WP?W

即

?2W?W2?W1??31??1W?W12??3W1?W2?1

求得

3?W???14 ?1?W?2??4所以信源熵为

H?X???p?Si?H?X|Si??i?123?21?131H?,??H?1,0???0.918??0?0.688?bit符号? 4?33?444状态转移图略。

3.15 （1）状态转移矩阵

??p?pP???2??p??2p2pp2p?2??p? ?2?p???p2pp2p?2??p?0???p??? p1?????2???p?2???p???则有

??p?p?0???p?0???????pT?p1?Pp1??????????2???p?2????p?2????p???2可得

ppp?1??p?2?22ppp?1??p?0??pp?1??p?2?

22ppp?2??p?0??p?1??pp?2?22p?0??pp?0??整理得

1p?0??p?1??p?2??

3（2）信源的熵

H???q?Si?H?ak|Si?

Si其中状态极限概率

q?Si???q?Sj?P?Si|Sj?

Sjppp?1??p?2?22ppp?1??p?0??pp?1??p?2?

22ppp?2??p?0??p?1??pp?2?22p?0??pp?0??整理得

1p?0??p?1??p?2??

3所以，此信源的熵

H???q?Si?H?ak|Si?Sip??pp??p?pp??q?0?H?p,,??q?1?H?,p,??q?2?H?,,p?2??22??2?22?

1?1p2p2??3??plog?log?log?3?p2p2p??plog12?plogpp（3）信源无记忆，符号的概率分布等于平稳分布。

1p?0??p?1??p?2??

3所以

H?X???p?ai?logi1p?ai??p?0?log?1.58?bit?111?p?1?log?p?2?log p?0?p?1?p?2?经比较，可得到H??H?X?。

（4）一阶马尔科夫信源的极值

H????1?p?log?1?p??21当且仅当p?,p?时成立。

33当p?0时，H??0；

1??1当p?1时，H????log??2?1?bit?

2??23.16 （1）状态转移矩阵

pppplog?log?log3 2222?pP???p??00ppp?0?? p??由

?p0??p??PT?1???p2???p0??p? ?1???p2??解得

p0?pp0?pp1p1?pp1?pp1 p0?p1?p2?1整理得，平稳后信源的概率分布

p0?p1?p2?（2）求信源熵H?。先求状态极限概率

1 3q?0??q?0??p?q?1??p?q?2??0q?1??q?0??0?q?1??p?q?2??p q?2??q?0??p?q?1??0?q?2??p又因为

?q?S??1

iSi可得

q?0??q?1??q?2??信源的熵

1 31?11?11H???q?Si?H?ak|Si??3??plog?plog??plog?plog

3?pp?ppSi（3）求p?0或p?1时的H?

p?0时

?11?H??lim?plog?plog??lim??p3?loge?0

p?0pp?p?0?p?1时，即p?0

?11?H??lim?plog?plog??lim??p3?loge?0

p?0pp?p?0?信源熵表示的是信源的平均不确定性。此题中p?0和p?1表明某一状态转化到另一状态的情况一定发生或一定不发生，即是确定事件，平均不确定性为零，即信源的熵为零。 3.17 可知消息的极大熵H0?log2?1?bit?，此信源的极限熵为

3311H??H1??log?log?0.811?bit?

4444由冗余度计算公式得

R?1?H?0.811?1??0.189 H013.18 （1）由一步转移概率矩阵与二步转移概率矩阵的公式P2?P?P得

?q2?pqpq?P2??q22pq?q2pq?p2??p2? pq?p2??（2）设平稳状态W??W1,W2,W3?，马尔可夫信源性质知WP?W，即

?qW1?qW2?W1?pW?qW?W?132 ?pW?pW?W33?2??W1?W2?W3?1?q2?W1?1?p?p2??pq?求解得稳态后的概率分布?W2? 21?p?p??p2?W3?1?p?p2??3.19 设状态空间S=?a,b,c?，符号空间X??a,b,c? 且

131P?X2?a|X1?b??P?X2?b|X1?b??P?X2?c|X1?b??3

1P?X2?a|X1?c??P?X2?b|X1?c??2P?X2?c|X1?c??0P?X2?a|X1?a??P?X2?b|X1?a??P?X2?c|X1?a??一步转移概率矩阵

?1?3?1P???3??1??21313121?3??1? 3??0???状态转移图

1/3a1/31/31/31/21/31/2设平稳状态W??W1,W2,W3?，由马尔可夫信源性质有

WP?W

即

11?1W?W??31322W3?W1?11?1?W1?W2?W3?W2

32?31?1?2W1?2W2?W3?可得

3?W??18?3??W2?

8?1??W3?4?马尔可夫链只与前一个符号有关，则有

s11bc

?3?H????p?Si???p?ak|Si?logp?ak|Si??i?1?k?1?3?11?3?11?1?11????3?log???3?log???2?log? 8?33?8?33?4?22??1.435?bit?3.20 消息元的联合概率是

p?白，白??p?白|白??p?白??0.7?0.9143?0.64p?黑，白??p?黑|白??p?白??0.7?0.0857?0.06p?白，黑??p?白|黑??p?黑??0.2?0.3?0.06p?黑，黑??p?黑|黑??p?黑??0.3?0.8?0.243

求得一阶马尔可夫信源的不确定性为

H?X|X???0.64log0.9143?0.06log0.0857?0.06log0.2?0.24log0.8?0.512?bit?

3.21 组成的字如下：

?,??,??,??,??,??,???,???,???,???,???,???,???,???,??? 这种简单语言平均每个码字的长度为

15938?1??2??3? 15151515则平均每个字符携带的信息量为

log15?1.542?bit? 3815所以，其冗余度为

1?1.542?0.027 log33.22 掷n次钱币就使其正面向上的概率为

?1?P?X?n?????2?n?11?1????? 2?2?n则有

1?1?H?X??????n?12?2??n?1?n?1?log????n?2?bit? ?2?n?12n

4.11 先求输入端须传输的信息量

1111H(X)?14000?log?14000?log2p?0?2p?1? ?14000?bit?再求输出端10s内传出的信息量。要求信道传出的信息量，必须先求信道容量。由

?1PX???21? 2???0.98P?Y|X?0.02?0.?02 ?90.?8知

?1?2???0???0??0.980.02??0.490.01??????1??0.020.98???0.010.49?

2???11?PY????22?PXY所以

H?X??log2?1?bit?H?Y??log2?1?bit?H?Y|X?????p?xiyj?logp?yj|xi?XY??0.49?log0.98?0.01?log0.02?0.14?bit?C?maxI?X;Y??H?Y??H?Y|X?p?x?

?1?0.14?0.86?bit?信道容量为0.86bit，对信道而言10s内共传输的符号数为15000个。所以输出端传出的信息量为0.86?15000?12900bit?14000bit，显然10s内传出端无法得到输入序列的全部信息。 4.12 （1）信道为准对称信道，输入等概率分布时达到信道容量，即C1?I?X;Y?。 设输入为

p?a1??p?a2??计算输出得

1 2p?b1??p?b2??所以

1?1?2??,p?b3??? 2C1?I?X;Y??H?Y??H?YX??1?2??2H??2? ??H?2???H?p????H?p????H?2????2???1?2??log????p???log?p?????p???log?p????1?2??

（2）信道仍为准对称信道，输入等概率分布时达到信道容量，即C2?I?X;Y?。 设输入为

p?a1??p?a2??计算输出得

1 2p?b1??p?b2??所以

1?1?2??,p?b3??p?b4??? 2C2?I?X;Y??H?Y??H?YX??1?2??2H??2? ??2H????H?p????H?p????H?2????2???1?2??log????p???log?p?????p???log?p????2?log2??1?2??比较两信道容量，得

C2?C1?2?log2??C1?2?

4.13 依题意，阻值的概率空间为

R?2k?R?5k??X??x1x2??P???0.70.3? ????功率的概率空间

y2??Y??y1??P??0.640.36? ????1P?W81P?W4由题意知p?y1x1??0.8,p?y2x1??0.2,再设p?y2x1??p,则

PY??0.640.36??p?y1x1?p?y2x1???? ??p?x1?p?x2????pyxpyx?????1222????0.80.2???0.70.3?????0.56?0.3p0.14?0.3p?pp??由0.56?0.3p?0.64,得

p?PYX0.84?315?0.80.2? ??411????1515???又

H?Y??H?0.64,0.36??0.943(bit) ?411?H?YX??0.7?H?0.8,0.2??0.3?H?,??0.756(bit)?1515?所以

I?X;Y??H?Y??H?YX??0.943?0.756?0.187(bit)

通过测阻值可以得到关于瓦数的平均信息量为0.187bit。

?0?0???1??2??0001?001???与信道的传输符号的概率分布100?2?010????01???1???0???0??1??80????0?1? 2??4.14 （1）X?c1?Y,由信道传输矩阵PYX得到信道输入与输出的联合分布矩阵为

?1?4??0?PXY???0???0?0140000140?0???0?0??0???10??2???01???4??1P?Y?8?00180000140000102011?4??1?4?? 0???0??有边缘概率

1814输出符号熵为

H?Y????p?yj?logp?yj?Y11111111??log?log?log?log?1.75(bit)88884422条件熵为

H?YX?????p?xiyj?logp?yjxi?XY1111111??log1?log1?log?log?log1?0.25(bit)4482824

I?X;Y??H?Y??H?YX??1.75?0.25?1.5(bit)

（2）X?c1?Y?c2?Z

?0?0???1??2?0?0012001??0?001?????100????210????00012001??0?001??????000????110????20001210?10??01?

?00???PZX?PYXPZY

?1?4??0?PXZ???0???0?0140000140?0???0?0??0???10??2???01???4??1PZ???8010110200??00???0???0???1??0??0???1??81? 4??00018141400?0??0??? 1?4??0??1812H?Z????p?zl?logp?zl?Z11111111??log?log?log?log?1.75(bit)88882244H?ZX?????p?xizl?logp?zlxi?XZ

1111??log?log?0.25(bit)8282

I?X;Z??H?Z??H?ZX??1.75?0.25?1.5(bit)

显然I?X;Y??I?X;Z?。

4.15 （1）由信道1的转移概率矩阵可知其为对称信道

所以

?11?C1?log4?H?,??1

?22?因为

H?X??log4?2?C1

所以有信息熵损失，信道有噪声。

（2）由信道2的转移概率矩阵可知其为准对称信道，输入为等概分布时达到信道容量。令此时的输出分布为

q1?q2?所以

1?q8?

8C2?H?Y??H?Y|X??11??log8?H?,??22??2因为

H?X??log4?C2

所以信道2无噪声。

4.16 因为是二元对称信道，根据信源概率分布：p?a1??p?a2??1/2，

信道传输概率： p?b1|a1??p?b2|a2??1??,p?b1|a2??p?b2|a1??? 得到输出符号概率分布

p?b1??p?b2??根据互信息量的定义，有

I?a1;b1??I?b1;a1??logI?a1;b2??I?b2;a1??logp?b1|a1?p?b1?p?b2?1 21???log??2?1?????1/2?logp?b2|a1??log?1/2

?log?2??4.17 （1）这是一个错误传递概率为0.08的二元对称信道，它的信道容量为

C?1?0.08log（2）每次顾客点菜时提供的信息为

11?0.92log?0.5978比特 0.080.9211?0.9log?0.469比特 0.10.9（3）由于需要传递的信息量小于信道容量，因此在这个信道上可以正确传递顾客点菜的信息。

H(X)?0.1log第5章 连续信源和连续信道

5.1 略

1??x?1??x??eln??e?dx??2?2??1?1?????e??x?ln?ln???x?dx??2?2?5.2 1??ln?ln??122e?ln奈特H?X??????5.3 略 5.4 略

第6章 无失真信源编码

6.1 1

6.2 信源序列

6.3 （1）唯一可译码有：A，B，C。 （2）即时码有：A，C

（3）LA??1/2?1/4?1/16?1/16?1/16?1/16??3?（码元 3/信息符号）

同理得

17LB?（码元/信息符号）8

17LC?（码元/信息符号）86.4 1．?xx,xz,y,zz,xyz?

（1）此码的码长满足Kraft-McMillan不等式:

111113393119???????????1 3232313233272727272727（2）根据码树图可知，此码是即时码；

（3）由于此码是即时码，所以它也是唯一可译码。 2．?000,10,00,11?

（1）此码满足Kraft-McMillan不等式：

111112227?????????1 2322222288888（2）此码不是即时码，因为码字00是码字000的前缀；

（3）此码不是唯一可译码，因为码符号序列000000可以译码为00，00，00，也可以译码为000，000。 3．?100,101,0,11?

（1）此码满足Kraft-McMillan不等式：

111111428?????????1 2323212288888（2）根据码树图可知，此码是即时码；

（3）由于此码是即时码，所以它也是唯一可译码。 4．?01,100,011,00,111,1010,1011,1101? （1）此码不满足Kraft-McMillan不等式：

111111114224211117?3?3?2?3?4?4?4??????????1 222222222161616161616161616（2）因为不满足Kraft-McMillan不等式，所以此码不是即时码； （3）因为不满足Kraft-McMillan不等式，所以此码不是唯一可以码。 5．{01，111，011，00，010，110}

（1）此码不满足Kraft-McMillan不等式：

1111112112118?????????????1 2223232223238888888（2）此码不是即时码，因为码字01是码字011的前缀；

（3）此码是唯一可译码。根据唯一可译码判决准则，我们构造以下的尾随后缀序列：

C??01,111,011,00,010,110?

F0??1,0?F1??11,10,1,0? F2??11,10,1,0??13?6.5 （1）H?S??H?,??0.811(bit/信源符号)

?44?13（2）p?0?=p?A??，p?1??p?B??

44（3）对二重延长消息采用费诺方法编码，结果为

BB:0BA:10AB:110AA:111

平均码长：

1L?N?pli?14ii?1?1.6875?0.844(码元/信源符号) 20.811?0.961(bit/码元符号) 0.844平均信息传输速率

R?H?S?L?码元0和1的概率分别为

9313123?????1616216332

313219p?1???????1621631632p?0??（4）对三重延长消息采用霍夫曼方法编码，结果为

BBB:1BBA:001BAB:010BAA:00000

ABB:011ABA:00001AAB:00010AAA:00011平均码长：

181L??pili??2.46875?0.823(码元/信源符号)

Ni?13平均信息传输速率

R?H?S?L?0.811?0.985(bit/码元符号) 0.83码元0和1的概率分别为

9292913343413117?????????????64364364364645645645320

27919192313112203p?1???????????????64643643643645645645320p?0??6.6 由香农第一定理知

H?S?logr?1LNH?S??? NNlogr显然当N??时

LNH?S?? Nlogr

此时的信息传输率为

R?H?S?L?H?S?H?S??logr logr编码后原信源变换成一个新的信源

?X??x1?P???p???1x2p2xr? pr??新信源的信道容量C?logr，且在输入信源等概率时达到此容量。 由式R?H?S?L?H?S?H?S??logr知，经过霍夫曼编码后，信心传输率达到信道容量，logr1很难推出此时的信源趋于等概分布，即pi=。

r6.7 （1）至少需要二位二进制码元来发送4个等概发生的信息

晴——00，云——01，雨——10，雾——11 （2）4个消息的概率恰好是2的负整数次幂，根据bi??logpi得 晴——2位，云——3位，雨——3位，雾——1位

（3）采用霍夫曼方法得

雾——0，晴——10，云——110，雨——111

它们的平均码长分别为：

1第一种情况：L??2?4?2(码元/信源符号)

4111??2??6?1.75(码元/信源符号) 2486.8 （1）采用霍夫曼编码方法得到最佳二元码为 第二种情况：L?s1:000s6:111s2:010s70010s3:011s8:0011s4:100s9:1010s5:110s10:1011

平均码长：

L??pili?3.26(码元/信源符号)

i?110编码效率

??H?S?Llogr?3.23?0.9908 3.26（2）仍采用霍夫曼编码方法求得最佳三元码

s1:00s6:20s2:01s721s3:02s8:22s4:10s9:110s5:12s10:111

平均码长：

L??pili?2.11(码元/信源符号)

i?110

编码效率

??H3?S?L?H3?S?Llog3?2.038?0.966 2.11s3:01

6.9 （1）采用霍夫曼方法进行编码，得s1:1平均码长：

s2:00L??pili?1.5(码元/信源符号)

i?13信源熵为

H?S????pilogpi?1.458(bit/信源符号)

i?13编码效率

??H?S?L?0.99

?S2??s1s1s1s2s2s1s1s3s3s1s2s2s2s3s3s2s3s3?（2）????? 0.250.150.150.10.10.090.060.060.04P????霍夫曼编码后

s1s1:10s2s2:0000s1s2:001s2s30001s2s1:011s1s3:110s3s1:111s3s2:0110s3s3:0111

平均码长：

L??pili?3(码元/信源符号)

i?19信源熵为

H?S2????plogpii?19i?2.971(bit/信源符号)

编码效率

??H?S2?L?0.99

（3）同理可得S3的最佳二元码，计算平均码长和编码效率。具体步骤略。 6.10 霍夫曼编码的结果为：

s1:01s2:11s3:000s4:001s5:100s6:101

平均码长：

L??pili?2.55(码元/信源符号)

i?16信源熵为

H?S????pilogpi?2.504(bit/信源符号)

i?16平均信息传输速率

2.61?0.982(bit/码元符号)

L3.146.11 （1）{0，10，11}是概率分布{1/2,1/4,1/4}的Huffman编码。

R??H?S?（2）{00，01，10，110}可以被改进为{00，01，10，11}而不丧失其即时可译性，因此原码不是最佳码，因此也就不是一个Huffman编码。

另外，此码中最长的码长只有一个码字，这也和Huffman编码的特性不符。

（3）{01，10}可以被改进为{0，1}而不丧失其即使可译性，因此原码不是最佳码，也就不是一个Huffman编码。 6.12 4位

6.13 （1）不存在

（2）存在{0，1，20，21，220，221，222} （3）不存在

6.14 对灰度{0，4，5，6，7}编码为{10，0，2，11，12}，??94%

6.15 码{0，010}是唯一可译码，但是它既不满足前缀条件也不满足后缀条件。换句话说，在

这个码中，某些码字是另外一些码字的前缀，并且某些码字是另外一些码字的后缀。 6.16 （1）我们将品尝次数看作码字的码长，由于只能依次品尝每一瓶酒，所以对于这个题

目而言码长只能是1，2，3，4，4这样的分布，所需的平均品尝次数就是平均码长，想要使得平均码长最小，则应该将较短的码长安排给概率较大的符号，因此所需的最小平均品尝次数为

5111117pili??1??2??3??4??4??2.33 ?3466123i?1（2）应该首先品尝概率为1/3的那瓶酒。

（3）这个问题可以转化为求取此概率分布的Huffman编码，如图所示

0001111001011/31/41/61/61/12

品尝时首先将第一比特为0的酒混合起来品尝，分出好坏后再按照第二比特来混合，直到找到坏酒，因此品尝的平均次数为

51111127pili??2??2??2??3??3??2.25 ?34661212i?1（4）根据上述编码，首先应该品尝第一和第二瓶酒的混合，或者第三，四，五瓶酒的混合。

由于Huffman编码不是唯一的，所以还存在另外的方案，其对应的编码如下：

概率 码字 1/3 00 1/4 10 1/6 11 1/6 010 1/12 011 在这种方案的指导下，首先应该品尝第一、四、五瓶酒的混合。 6.17 序列S ?

F(S) 0 p(S) 1 码长 --- 码字 --- 计算过程 ---

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