《信息论与编码》-曹雪虹-课后习题答案
第二章
一个马尔可夫信源有3个符号{}1,23,u u u ,转移概率为:()11|1/2p u u =,()21|1/2p u u =,
()31|0p u u =,()12|1/3p u u =,()22|0p u u =,()32|2/3p u u =,()13|1/3p u u =,()23|2/3p u u =,()33|0p u u =,画出状态图并求出各符号稳态概率。
解:状态图如下
*
状态转移矩阵为:
1/21/2
01/302/31/32/30p ?? ?= ? ???
设状态u 1,u 2,u 3稳定后的概率分别为W 1,W 2、W 3
由1231WP W W W W =??++=?得1231132231231112331223231W W W W W W W W W W W W ?++=???+=???=???++=?
计算可得1231025925625W W W ?=???
=??
?=??
由符号集{0,1}组成的二阶马尔可夫链,其转移概率为:(0|00)p =,(0|11)p =,(1|00)p =,
(1|11)p =,(0|01)p =,(0|10)p =,(1|01)p =,(1|10)p =。画出状态图,并计算各状态
的稳态概率。
解:(0|00)(00|00)0.8p p == (0|01)(10|01)0.5p p ==
"
(0|11)(10|11)0.2p p == (0|10)(00|10)0.5p p == (1|00)(01|00)0.2p p == (1|01)(11|01)0.5p p ==
(1|11)(11|11)0.8p p == (1|10)(01|10)0.5p p ==
于是可以列出转移概率矩阵:0.80.20
0000.50.50.50.500000.20.8p ?? ?
?= ? ???
状态图为:
设各状态00,01,10,11的稳态分布概率为W 1,W 2,W 3,W 4 有
41
1i i WP W W ==???=??∑ 得 131
132
24324412340.80.50.20.50.50.20.50.81W W W W W W W W W W W W W W W W +=??+=??+=??+=?+++=?? 计算得到1234514171
75
14W W W W ?
=??
?=??
?=???=
?
,
同时掷出两个正常的骰子,也就是各面呈现的概率都为1/6,求:
(1) “3和5同时出现”这事件的自信息; (2) “两个1同时出现”这事件的自信息;
(3) 两个点数的各种组合(无序)对的熵和平均信息量; (4) 两个点数之和(即2, 3, … , 12构成的子集)的熵; (5) 两个点数中至少有一个是1的自信息量。 解:
(1) %
bit
x p x I x p i i i 170.418
1
log )(log )(18
1
61616161)(=-=-==
?+?=
(2)
bit x p x I x p i i i 170.536
1
log
)(log )(361
6161)(=-=-==
?=
(3)
两个点数的排列如下:
11 12 13
; 14
15 16
21 22 23 24 25 `
26 31 32 33 34 35 36 41 [ 42 43 44
45 46 51 52 53 !
54 55 56
61
62
63
64
65
<
66
共有21种组合:
其中11,22,33,44,55,66的概率是36
16161=? 其他15个组合的概率是18
161612=??
symbol bit x p x p X H i
i i / 337.4181log 18115361log 3616)(log )()(=??? ??
?+?-=-=∑
(4)
参考上面的两个点数的排列,可以得出两个点数求和的概率分布如下: ?
symbol
bit x p x p X H X P X i
i i / 274.3 61log 61365log 365291log 912121log 1212181log 1812361log 36
12 )
(log )()(36112181111211091936586173656915121418133612)(=?
?? ??
+?+?+?+?+?-=-=??????????=?
?????∑(5)
bit x p x I x p i i i 710.136
11
log
)(log )(3611116161)(=-=-==
??=
2-4
居住某地区的女孩子有25%是大学生,在女大学生中有75%是身高160厘米以上的,而女孩子中身高160厘米以上的占总数的一半。假如我们得知“身高160厘米以上的某女孩是大学生”的消息,问获得多少信息量
解:
设随机变量X 代表女孩子学历
< X x 1(是大学生)
x 2(不是大学生)
P(X)
设随机变量Y 代表女孩子身高
] Y y 1(身高>160cm )
y 2(身高<160cm )
P(Y)
已知:在女大学生中有75%是身高160厘米以上的 {
即:bit x y p 75.0)/(11=
求:身高160厘米以上的某女孩是大学生的信息量 即:bit y p x y p x p y x p y x I 415.15
.075
.025.0log )()/()(log
)/(log )/(11111111=?-=-=-=
掷两颗骰子,当其向上的面的小圆点之和是3时,该消息包含的信息量是多少当小圆点之和是7时,该消息所包含的信息量又是多少 解:
1)因圆点之和为3的概率1()(1,2)(2,1)18
p x p p =+=
该消息自信息量()log ()log18 4.170I x p x bit =-==
,
2)因圆点之和为7的概率
1()(1,6)(6,1)(2,5)(5,2)(3,4)(4,3)6
p x p p p p p p =+++++=
该消息自信息量()log ()log6 2.585I x p x bit =-==
设有一离散无记忆信源,其概率空间为123401233/81/41/41/8X x x x x P ====????
= ? ?????
(1)求每个符号的自信息量
(2)信源发出一消息符号序列为{202 120 130 213 001 203 210 110 321 010 021 032 011 223 210},求该序列的自信息量和平均每个符号携带的信息量 解:12
2118
()log log 1.415()3
I x bit p x === —
同理可以求得233()2,()2,()3I x bit I x bit I x bit ===
因为信源无记忆,所以此消息序列的信息量就等于该序列中各个符号的信息量之和 就有:123414()13()12()6()87.81I I x I x I x I x bit =+++=
平均每个符号携带的信息量为
87.81
1.9545
=bit/符号 试问四进制、八进制脉冲所含信息量是二进制脉冲的多少倍
解:
四进制脉冲可以表示4个不同的消息,例如:{0, 1, 2, 3}
八进制脉冲可以表示8个不同的消息,例如:{0, 1, 2, 3, 4, 5, 6, 7} )
二进制脉冲可以表示2个不同的消息,例如:{0, 1} 假设每个消息的发出都是等概率的,则:
四进制脉冲的平均信息量symbol bit n X H / 24log log )(1=== 八进制脉冲的平均信息量symbol bit n X H / 38log log )(2=== 二进制脉冲的平均信息量symbol bit n X H / 12log log )(0=== 所以:
四进制、八进制脉冲所含信息量分别是二进制脉冲信息量的2倍和3倍。 2-9 “-” 用三个脉冲 “●”用一个脉冲 {
(1) I(●)=Log 4()2= I(-)=Log 4
3? ????
0.415=
(2) H=
14
Log 4()34Log 43?
??
??
+
0.811=
2-10
(2) P(黑/黑)= P(白/黑)=
H(Y/黑)=
(3) P(黑/白)= P(白/白)=
H(Y/白)=
(4) P(黑)=
P(白)=
~
H(Y)=
有一个可以旋转的圆盘,盘面上被均匀的分成38份,用1,…,38的数字标示,其中有两份涂绿色,18份涂红色,18份涂黑色,圆盘停转后,盘面上的指针指向某一数字和颜色。 (1)如果仅对颜色感兴趣,则计算平均不确定度
(2)如果仅对颜色和数字感兴趣,则计算平均不确定度 (3)如果颜色已知时,则计算条件熵
解:令X 表示指针指向某一数字,则X={1,2,……….,38} >
Y 表示指针指向某一种颜色,则Y={l 绿色,红色,黑色} Y 是X 的函数,由题意可知()()i j i p x y p x = (1)3
1
12381838
()()log
log 2log 1.24()3823818
j j j H Y p y p y ==
=+?=∑bit/符号 (2)2(,)()log 38 5.25H X Y H X ===bit/符号
(3)(|)(,)()()() 5.25 1.24 4.01H X Y H X Y H Y H X H Y =-=-=-=bit/符号 两个实验X 和Y ,X={x 1 x 2 x 3},Y={y 1 y 2 y 3},l 联合概率(),i j ij r x y r =为
1112
132122233132337/241/2401/241/41/2401/247/24r r r r r r r
r r ????
? ?= ? ? ? ?????
(1) 如果有人告诉你X 和Y 的实验结果,你得到的平均信息量是多少
(2) }
(3) 如果有人告诉你Y 的实验结果,你得到的平均信息量是多少
(4) 在已知Y 实验结果的情况下,告诉你X 的实验结果,你得到的平均信息量是多少
解:联合概率(,)i j p x y 为
2
2221(,)(,)log (,)
72411
2log 4log 24log 4247244
i j i j ij
H X Y p x y p x y ==?
+?+∑ =符号
X 概率分布
21
()3log 3 1.583
H Y =?=bit/符号
(|)(,)() 2.3 1.58
H X Y H X Y H Y =-=-
符号
/
有两个二元随机变量X 和Y ,它们的联合概率为
并定义另一随机变量Z = XY (一般乘积),试计算: .
(1) H(X), H(Y), H(Z), H(XZ), H(YZ)和H(XYZ);
(2) H(X/Y), H(Y/X), H(X/Z), H(Z/X), H(Y/Z), H(Z/Y), H(X/YZ), H(Y/XZ)和H(Z/XY);
(3) I(X;Y), I(X;Z), I(Y;Z), I(X;Y/Z), I(Y;Z/X)和I(X;Z/Y)。
解: (1)
symbol
bit y p y p Y H y x p y x p y p y x p y x p y p symbol
bit x p x p X H y x p y x p x p y x p y x p x p j
j j i
i i / 1)(log )()(2
1
8183)()()(21
8381)()()(/ 1)(log )()(2
1
8183)()()(21
8381)()()(22212121112212221111=-==
+=+==
+=+==-==
+=+==
+=+=∑∑
Z = XY 的概率分布如下:
symbol
bit z p Z H z z Z P Z k
k / 544.081log 8187log 87
)()(818710)(2
21=??? ??+-=-=??????????===?
?????∑
。
symbol
bit z x p z x p XZ H z p z x p z x p z x p z p z x p z p z x p z x p z x p z p x p z x p z x p z x p z x p x p i k
k i k i / 406.181log 8183log 8321log 21
)(log )()(8
1
)()()()()(8
35.087)()()()()()(5.0)()(0)()()()(2222221211112121111112121111=??? ??++-=-==
=+==-=-=+====+=∑∑
symbol
bit z y p z y p YZ H z p z y p z y p z y p z p z y p z p z y p z y p z y p z p y p z y p z y p z y p z y p y p j k
k j k j / 406.181log 8183log 8321log 21
)(log )()(8
1)()()()()(8
35.087)()()()()()(5.0)()(0)()()()(2222221211112121111112121111=??? ??++-=-==
=+==-=-=+====+=∑∑
symbol
bit z y x p z y x p XYZ H y x p z y x p y x p z y x p z y x p z y x p y x p z y x p y x p z y x p z y x p z y x p z x p z y x p z x p z y x p z y x p y x p z y x p y x p z y x p z y x p z y x p z y x p z y x p i
j
k
k j i k j i / 811.181log 8183log 8383log 8381log 8
1
)(log )()(8
1
)()()
()()(0
)(8
3)()()()()(8
38121)()()()()()(8/1)()()()()(0
)(0)(0)(22222222222122122121121221211211111121111111211111111211111212221211=??? ??+++-=-==
==+====+=-=-==+===+===∑∑∑
(2)
symbol
bit
XY
H
XYZ
H
XY Z
H
symbol
bit
XZ
H
XYZ
H
XZ
Y
H
symbol
bit
YZ
H
XYZ
H
YZ
X
H
symbol bit
Y
H
YZ
H
Y
Z
H
symbol
bit
Z
H
YZ
H
Z
Y
H
symbol
bit
X
H
XZ
H
X
Z
H
symbol
bit
Z
H
XZ
H
Z
X
H
symbol
bit
X
H
XY
H
X
Y
H
symbol
bit
Y
H
XY
H
Y
X
H
symbol
bit
y
x
p
y
x
p
XY
H
i j
j
i
j
i
/
811
.1
811
.1
)
(
)
(
)
/
(
/
405
.0
406
.1
811
.1
)
(
)
(
)
/
(
/
405
.0
406
.1
811
.1
)
(
)
(
)
/
(
/
406
.0
1
406
.1
)
(
)
(
)
/
(
/
862
.0
544
.0
406
.1
)
(
)
(
)
/
(
/
406
.0
1
406
.1
)
(
)
(
)
/
(
/
862
.0
544
.0
406
.1
)
(
)
(
)
/
(
/
811
.0
1
811
.1
)
(
)
(
)
/
(
/
811
.0
1
811
.1
)
(
)
(
)
/
(
/
811
.1
8
1
log
8
1
8
3
log
8
3
8
3
log
8
3
8
1
log
8
1
)
(
log
)
(
)
(
2
=
-
=
-
=
=
-
=
-
=
=
-
=
-
=
=
-
=
-
=
=
-
=
-
=
=
-
=
-
=
=
-
=
-
=
=
-
=
-
=
=
-
=
-
=
=
?
?
?
?
?
+
+
+
-
==
-
=∑∑
(3)
symbol
bit
YZ
X
H
Y
X
H
Y
Z
X
I
symbol
bit
XZ
Y
H
X
Y
H
X
Z
Y
I
symbol
bit
YZ
X
H
Z
X
H
Z
Y
X
I
symbol
bit
Z
Y
H
Y
H
Z
Y
I
symbol
bit
Z
X
H
X
H
Z
X
I
symbol
bit
Y
X
H
X
H
Y
X
I
/
406
.0
405
.0
811
.0
)
/
(
)
/
(
)
/
;
(
/
457
.0
405
.0
862
.0
)
/
(
)
/
(
)
/
;
(
/
457
.0
405
.0
862
.0
)
/
(
)
/
(
)
/
;
(
/
138
.0
862
.0
1
)
/
(
)
(
)
;
(
/
138
.0
862
.0
1
)
/
(
)
(
)
;
(
/
189
.0
811
.0
1
)
/
(
)
(
)
;
(
=
-
=
-
=
=
-
=
-
=
=
-
=
-
=
=
-
=
-
=
=
-
=
-
=
=
-
=
-
=
2-14
~
(1)
P(ij)= P(i/j)=
(2) 方法1: =
方法2:
2-15
P(j/i)=
;
黑白传真机的消息元只有黑色和白色两种,即X={黑,白},一般气象图上,黑色的出现概率p(黑)=,白色出现的概率p(白)=。
(1)假设黑白消息视为前后无关,求信源熵H(X),并画出该信源的香农线图
(2)实际上各个元素之间是有关联的,其转移概率为:P(白|白)=,P(黑|白)=,P(白|黑)=,P(黑|黑)=,求这个一阶马尔可夫信源的信源熵,并画出该信源的香农线图。 (3)比较两种信源熵的大小,并说明原因。 <
解:(1)221010
()0.3log 0.7log 0.881337
H X =+=bit/符号 P(黑|白)=P(黑)
P(白|白)=P(白) 黑
白
0.7
0.3
0.7
0.3
P(黑|黑)=P(黑)
P(白|黑)=P(白)
(2)根据题意,此一阶马尔可夫链是平稳的(P(白)=不随时间变化,P(黑)=不随时 间变化)
212
222
2
1()(|)(,)log (,)
111
0.91430.7log 0.08570.7log 0.20.3log 0.91430.08570.2
10.80.3log 0.8
i j i j ij
H X H X X p x y p x y ∞===?+?+?+?∑ 【
=符号
每帧电视图像可以认为是由3105
个像素组成的,所有像素均是独立变化,且每像素又取128个不同的亮度电平,并设亮度电平是等概出现,问每帧图像含有多少信息量若有一个广播员,在约10000个汉字中选出1000个汉字来口述此电视图像,试问广播员描述此图像所广播的信息量是多少(假设汉字字汇是等概率分布,并彼此无依赖)若要恰当的描述此图像,广播员在口述中至少需要多少汉字
解: 1)
symbol
bit X NH X H symbol
bit n X H N
/ 101.27103)()(/ 7128log log )(6
5
22?=??=====
2) —
symbol
bit X NH X H symbol bit n X H N
/ 13288288.131000)()(/ 288.1310000log log )(22=?=====
3)
158037288
.13101.2)()(6
=?==X H X H N N
给定语音信号样值X 的概率密度为1()2
x
p x e λλ-=,x -∞<<+∞,求H c (X),并证明它小于同样方差的正态变量的连续熵。 - 解:
201()()log ()()log 21
()log ()()log 211log log ()2211
1log log ()log
()222
11
log 2log 22x
c x x x x x x
x x
H X p x p x dx p x e dx
p x dx p x x edx
e e x dx
e e x dx e x dx e xe λλλλλλλλλλλλλλλλ+∞+∞
--∞-∞+∞
+∞
-∞-∞+∞
--∞
+∞
--∞+∞-=-=-=---=-+=-+?-+=-+???????
?0
1log log (1)212log log log
2x x dx
e x e e e λλλλλλ
+∞
-??=--+??=-+= 2
2
()0,()E X D X λ==
,221214()log 2log log log ()22e H X e H X ππλλλλ
=
==>=
连续随机变量X 和Y 的联合概率密度为:???
??≤+=其他
1
),(2222
r y x r y x p π,求H(X),
H(Y), H(XYZ)和I(X;Y)。
(提示:?-
=20
222log 2
sin log π
π
xdx )
解:
$
???
??
?????
??????
?
-+-=+
==-==--=--=--=-+-=--=---=--=-=≤≤--===----------
---202020
220
2
20
20
22220
2
20
2222
22
2222222222222
22222
222
22sin log 2
2cos 1422cos 1log 4
sin log sin 4
log sin 4sin log sin 4
sin log sin 4)
cos (sin log sin 4cos log 4log 2log )(/ log 2
1
log log 2
1
1log 2log log )(2log log )(2
log )( 2log )( )(log )()()( 21)()(2
2222
22
2π
π
π
π
π
ππθ
θθ
πθθπθ
θθπθθπθθθπ
θθθπθθθπθπππππππππd d r d rd d r d r r r r d r r r r x dx x r x r r dx x r r x r dx
x r x p symbol
bit e r e
r r dx
x r x p r dx
x r x p dx r
x p dx r
x r x p dx
x p x p X H r x r r
x r dy r dy xy p x p r r
r r
r
r r r r r r r
r r
r c x r x r x r x r 令其中:
e
e e d e d e d e d e d e
d d d e
r d r d d r r d d d r d r 220
2220
220
22
0220
2220
220
20
20
20
220
20
220
20
20
20
20
log 2
1
2sin log 21log 212cos log 1log 122cos 1log 2
cos log 2
sin log cos cos sin 21
sin log 2sin sin log 2sin 12sin sin log 1
sin log 2cos 2
log 2
1
1log sin log 2cos 2
1log sin log 2cos 2
)2log 2
(2
2sin log 1
log sin log 2cos 2
sin log 2
2cos log 2
log 2
-=--=--=+-
=-=-=???
?
??-==
+-=-
-=-
-
+
-
=-
+
-
=
?????
??
??
?
??
?
??π
π
ππ
π
π
π
π
π
π
π
π
π
π
π
π
π
θπθ
θπ
θπθ
θ
πθ
θπθ
θ
θθ
θπθθθθπθ
θπθ
θθπθ
θθπθ
θθπππ
θπ
θ
θθπθθπθθπ
θπ
其中:
bit/symbol e r e r XY H Y H X H Y X I bit/symbol r dxdy xy p r dxdy r xy p dxdy
xy p xy p XY H bit/symbol
e r X H Y H x p y p r y r r y r dx r dx xy p y p c c c c R
R
R
c C C y r y r y r y r log log
log log log 2
)()()();( log
)(log
1
log )(
)(log )()( log 2
1
log )()()
()()( 21
)()(222222222
222
2222
2222
22
2-=--=-+===-=-=-===≤≤--=
==???????
?
---
---πππππππππ
某一无记忆信源的符号集为{0, 1},已知P(0) = 1/4,P(1) = 3/4。 !
(1) 求符号的平均熵;
(2) 有100个符号构成的序列,求某一特定序列(例如有m 个“0”和(100 - m )个“1”)的自信息量的表达式; (3) 计算(2)中序列的熵。
解: (1)
symbol bit x p x p X H i
i i / 811.043log 4341log 41
)(log )()(=??? ??+-=-=∑
(2)
bit m x p x I x p m
i i m m
m
i 585.15.4143
log
)(log )(4
34341)(100
100100
100100+=-=-==?
?
?
?????? ??=---
|
(3)
symbol bit X H X H / 1.81811.0100)(100)(100=?==
2-26
P(i)= P(ij)=
H(IJ)=
$
有一个一阶平稳马尔可夫链1,2,
,,
r X X X ,各X r 取值于集合{}1,2,3A a a a =,已知起始
概率P(X r )为1231/2,1/4p p p ===,转移概率如下图所示
j i
1 2 3 1 2 ! 3
1/2
2/3 2/3
1/4 0 1/3
1/4 ) 1/3 0
(1) 求123(,,)X X X 的联合熵和平均符号熵 (2) 求这个链的极限平均符号熵
(3) 求012,,H H H 和它们说对应的冗余度 解:(1)
12312132,112132(,,)()(|)(|)
()(|)(|)
H X X X H X H X X H X X X H X H X X H X X =++=++
1111111
()log log log 1.5/224444
H X bit =---=符号
&
X 1,X 2的联合概率分布为
¥
212()()
j i j i
p x p x x =∑
X 2的概
率分布为 那么
12()i j p x x
1 2
3 1 1/
4 ·
1/8 1/8 2 1/6 0
1/12 3
1/6
>
1/12
1 2 3 14/24
5/24
5/24
21111131131
(|)log 4log 4log 4log log3log log348862126212
H X X =++++++
=符号
X 2X 3
那么
32771535535
(|)log 2log 4log 4log log3log log3244883627236272
H X X =
++++++ —
=符号
123(,,) 1.5 1.209 1.26 3.969H X X X bit =++=/符号
所以平均符号熵3123 3.969
(,,) 1.3233
H X X X bit =
=/符号 (2)设a 1,a 2,a 3稳定后的概率分布分别为W1,W2,W3,转移概率距阵为11
12442
103321033
P ?? ? ?
?= ? ? ? ???
由1i WP W W =???=??∑ 得到 123132123122123311431W W W W W W W W W ?++=???+=??++=???计算得到12347314314W W W ?=??
?=??
?=??
又满足不可约性和非周期性
3
1
4111321
()(|)(,,)2(,,0) 1.2572441433
i i i H X W H X W H H bit ∞===
+?=∑/符号 (3)0log3 1.58H bit ==/符号 1 1.5H bit =/符号 2 1.5 1.209
1.3552
H bit +=
=/符号 :
00 1.25110.211.58γη=-=-
=11 1.25110.6171.5γη=-=-= 22 1.25
110.0781.355
γη=-=-=
a
1
a 3 a
2
1/2 2/3
1/4
1/3
2/3
1/4
2-30
(1) 求平稳概率 P(j/i)=
解方程组
得到
(
(2)
信源熵为:
2-31
P(j/i)=解方程组得到W1= , W2= , W3= :
一阶马尔可夫信源的状态图如图2-13所示,信源X 的符号集为(0,1,2)。 (1)求信源平稳后的概率分布P(0),P(1),P(2) (2)求此信源的熵
(3)近似认为此信源为无记忆时,符号的概率分布为平稳分布。求近似信源的熵H(X)并与H ∞进行比较
1
2
1-p
p/2
1-p
p/2p/2
p/2
p/2
p/2
1-p
图2-13
;
解:根据香农线图,列出转移概率距阵1/2/2/21/2/2/21p p p P p p p p p p -????=-????-??
令状态0,1,2平稳后的概率分布分别为W1,W2,W3
31
1i i WP W W ==???=??∑ 得到 1231
1232123(1)2
2
(1)221p p p W W W W p
p W p W W W W W W ?
-++=???+-+
=??++=???
计算得到131313W W W ?=??
?
=??
?=??
由齐次遍历可得
112
()(|)3(1,,)(1)log log 3221i i i
p p H X W H X W H p p p p p ∞==?-=-+-∑