《信息论与编码》-曹雪虹-课后习题答案
第二章
2.1一个马尔可夫信源有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 =??++=?得1231132231231
112331223
231W W W W W W W W W W W W ?++=???+=???=???++=?
计算可得1231025925625W W W ?=???
=??
?=??
2.2 由符号集{0,1}组成的二阶马尔可夫链,其转移概率为:(0|00)p =0.8,(0|11)p =0.2,
(1|00)p =0.2,(1|11)p =0.8,(0|01)p =0.5,(0|10)p =0.5,(1|01)p =0.5,(1|10)p =0.5。
画出状态图,并计算各状态的稳态概率。
解:(0|00)(00|00)0.8p p == (0|01)
(10|01)p p == (0|11)(10|11)0.2p p == (0|10)(00|10)p p == (1|00)(01|00)0.2p p == (1|01)(11|01)p 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 +=??+=??+=??+=?+++=?? 计算得到123451417175
14W W W W ?=??
?=???=???=
?
2.3 同时掷出两个正常的骰子,也就是各面呈现的概率都为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 )(181
61616161)(=-=-==
?+?=
(2)
bit
x p x I x p i i i 170.536
1
log )(log )(36
1
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)
参考上面的两个点数的排列,可以得出两个点数求和的概率分布如下:
sym bol
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 )(36
11116161)(=-=-==
??=
2-4
2.5 居住某地区的女孩子有25%是大学生,在女大学生中有75%是身高160厘米以上的,而女孩子中身高160厘米以上的占总数的一半。假如我们得知“身高160厘米以上的某女孩是大学生”的消息,问获得多少信息量?
解:
设随机变量X 代表女孩子学历
X x 1(是大学生) x 2(不是大学生) P(X) 0.25 0.75
设随机变量Y 代表女孩子身高
Y y 1(身高>160cm ) y 2(身高<160cm ) P(Y) 0.5 0.5
已知:在女大学生中有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=?-=-=-=
2.6 掷两颗骰子,当其向上的面的小圆点之和是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 =-==
2.7 设有一离散无记忆信源,其概率空间为123401233/8
1/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/符号 2.8 试问四进制、八进制脉冲所含信息量是二进制脉冲的多少倍?
解:
四进制脉冲可以表示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)=
2.11 有一个可以旋转的圆盘,盘面上被均匀的分成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()3823818j
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/符号 2.12 两个实验X 和Y ,X={x 1 x 2 x 3},Y={y 1 y 2 y 3},l 联合概率(),i j ij r x y r =为
1112132122233132337/241/2401/241/41/2401/247/24r r r r r r r
r r ????
? ?= ? ? ? ?????
(1) 如果有人告诉你X 和Y 的实验结果,你得到的平均信息量是多少?
(2) 如果有人告诉你Y 的实验结果,你得到的平均信息量是多少?
(3) 在已知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 ==?
+?+∑
=2.3bit/符号
21
()3log 3 1.583
H Y =?=bit/符号
(|)(,)() 2.3 1.58
H X Y H X Y H Y =-=- =0.72bit/符号
2.13 有两个二元随机变量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)
sym bol
bit y p y p Y H y x p y x p y p y x p y x p y p sym bol
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 的概率分布如下:
sym bol
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=??? ??++-=-==
=+==-=-=+====+=∑∑
sym bol
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=??? ??++-=-==
=+==-=-=+====+=∑∑sym bol
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)
sym bol
bit XY H XYZ H XY Z H sym bol bit XZ H XYZ H XZ Y H sym bol bit YZ H XYZ H YZ X H sym bol bit Y H YZ H Y Z H sym bol bit Z H YZ H Z Y H sym bol bit X H XZ H X Z H sym bol bit Z H XZ H Z X H sym bol bit X H XY H X Y H sym bol bit Y H XY H Y X H sym bol
bit y x p y x p XY H i j
j i j i / 0811.1811.1)()()/(/ 405.0406.1811.1)()()/(/ 405.0406.1811.1)()()/(/ 406.01406.1)()()/(/ 862.0544.0406.1)()()/(/ 406.01406.1)()()/(/ 862.0544.0406.1)()()/(/ 811.01811.1)()()/(/ 811.01811.1)()()/(/ 811.181log 8183log 8383log 8381log 81
)(log )()(2=-=-==-=-==-=-==-=-==-=-==-=-==-=-==-=-==-=-==??? ??+++-==-=∑∑ (3)
sym bol
bit YZ X H Y X H Y Z X I sym bol bit XZ Y H X Y H X Z Y I sym bol bit YZ X H Z X H Z Y X I sym bol
bit Z Y H Y H Z Y I sym bol
bit Z X H X H Z X I sym bol bit Y X H X H Y X I / 406.0405.0811.0)/()/()/;(/ 457.0405.0862.0)/()/()/;(/ 457.0405.0862.0)/()/()/;(/ 138.0862.01)/()();(/ 138.0862.01)/()();(/ 189.0811.01)/()();(=-=-==-=-==-=-==-=-==-=-==-=-=
2-14 (1)
P(ij)= P(i/j)=
(2) 方法1:
=
方法2:
2-15 P(j/i)=
2.16 黑白传真机的消息元只有黑色和白色两种,即X={黑,白},一般气象图上,黑色的出现概率p(黑)=0.3,白色出现的概率p(白)=0.7。
(1)假设黑白消息视为前后无关,求信源熵H(X),并画出该信源的香农线图 (2)实际上各个元素之间是有关联的,其转移概率为:P(白|白)=0.9143,P(黑|白)=0.0857,P(白|黑)=0.2,P(黑|黑)=0.8,求这个一阶马尔可夫信源的信源熵,并画出该信源的香农线图。
(3)比较两种信源熵的大小,并说明原因。 解:(1)221010
()0.3log 0.7log 0.881337
H X =+=bit/符号 P(黑|白)=P(黑)
P(白|白)=P(白)
P(黑|黑)=P(黑)
P(白|黑)=P(白)
(2)根据题意,此一阶马尔可夫链是平稳的(P(白)=0.7不随时间变化,P(黑)=0.3不随时 间变化)
212
2222
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 ∞===?+?+?+?∑
=0.512bit/符号
2.17 每帧电视图像可以认为是由3 105
个像素组成的,所有像素均是独立变化,且每像素又取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
2.20 给定语音信号样值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 ππλλλλ
===>=
2.24 连续随机变量X 和Y 的联合概率密度为:???
??≤+=其他
01),(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
20222
20
2
20
222222
2222222222222
22222
222
22sin log 2
2cos 1422cos 1log 4sin log sin 4
log sin 4
sin 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 sym bol
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/sym bol
e r e r XY H Y H X H Y X I bit/sym bol r dxdy xy p r dxdy r xy p dxdy
xy p xy p XY H bit/sym bol
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-=--=-+===-=-=-===≤≤--===???????
?
---
---πππππππππ
2.25 某一无记忆信源的符号集为{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.414
3
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)=
2.29 有一个一阶平稳马尔可夫链1,2,
,,
r X X X ,各X r 取值于集合{}1,2,3A a a a =,已知起
始概率P(X r )为1231/2,1/4p p p ===,转移概率如下图所示
(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 的联合概率分布为
212()()j i j i
p x p x x =∑
X 2的概率分布为
那么
21111131131
(|)log 4log 4log 4log log 3log log 348862126212
H X X =
++++++ =1.209bit/符号
X 2X 3的联合概率分布为
那么
32771535535
(|)log 2log 4log 4log log 3log log 3244883627236272
H X X =
++++++ =1.26bit/符号
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,转移概率距阵为1112442
10332103
3
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.5
H b i t =/符号 2 1.5 1.209
1.3552
H b i t +==/符号 00 1.25110.211.58γη=-=-=11 1.25110.6171.5γη=-=-= 22 1.25
110.0781.355
γη=-=-=
2-30
(1) 求平稳概率
P(j/i)=
解方程组
得到
(2)
信源熵为:
2-31
P(j/i)= 解方程组 得到W1= , W2= , W3=
2.32 一阶马尔可夫信源的状态图如图2-13所示,信源X 的符号集为(0,1,2)。 (1)求信源平稳后的概率分布P(0),P(1),P(2) (2)求此信源的熵
(3)近似认为此信源为无记忆时,符号的概率分布为平稳分布。求近似信源的熵H(X)并与H ∞进行比较
图2-13
解:根据香农线图,列出转移概率距阵1/2/2/21/2/2/21p p p P p p p p p p -????=-????-??
令状态0,1,2平稳后的概率分布分别为W1,W2,W3
3
1
1
i 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 ∞==?-=-+-∑
,()log3 1.58/H X bit ==符号 由最大熵定理可知()H X ∞存在极大值
或者也可以通过下面的方法得出存在极大值:
()121log(1)(1)log log
1222(1)H X p p p
p p p p p p ∞???-=---+-++??=-???--?
? 112(1)22(1)p p p =-+-- 又01p ≤≤所以[]0,2(1)p p ∈+∞-当p=2/3时12(1)
p
p =-
0
()log 02(1)H X p
p p ∞?=->?- 2/3
()log 02(1)
H X p
p p ∞?=-- 所以当p=2/3时()H X ∞存在极大值,且max () 1.58/H X bit ∞=符号 所以,()()H X H X ∞≤ 2-33
(1)
解方程组:
得p(0)=p(1)=p(2)=
(2)
(3)
当p=0或p=1时 信源熵为0
练习题:有一离散无记忆信源,其输出为{}0,1,2X ∈,相应的概率为
0121/4,1/4,1/2p p p ===,设计两个独立的实验去观察它,其结果分别为
{}{}120,1,0,1Y Y ∈∈,已知条件概率:
(1) 求1(;)I X Y 和2(;)I X Y ,并判断哪一个实验好些
(2) 求12(;)I X Y Y ,并计算做Y 1和Y 2两个实验比做Y 1和Y 2中的一个实验可多得多少关于
X 的信息
(3) 求12(;|)I X Y Y 和21(;|)I X Y Y ,并解释它们的含义
P(y 1=0)=p(y 1=1)=1/2 p(y 2=1)=p(y 2=1)=1/2
11111111
(;)()(|)log 2log log 2log 242424I X Y H Y H Y X ∴=-=---?=0.5bit/符号
222111
(;)()(|)log 2log1log1log11/442
I X Y H Y H Y X bit =-=---=符号>1(;)I X Y
所以第二个实验比第一个实验好
(2)因为Y 1和Y 2 相互独立,所以1212(|)(|)(|)p y y x p y x p y x =
1. 有一个马尔可夫信源,已知p(x 1|x 1)=2/3,p(x 2|x 1)=1/3,p(x 1|x 2)=1,p(x 2|x 2)=0,试画出该信源的香农线图,并求出信源熵。 解:该信源的香农线图为: 1/3 ○ ○ 2/3 (x 1) 1 (x 2) 在计算信源熵之前,先用转移概率求稳定状态下二个状态x 1和 x 2 的概率)(1x p 和)(2x p 立方程:)()()(1111x p x x p x p =+)()(221x p x x p =)()(2132x p x p + )()()(1122x p x x p x p =+)()(222x p x x p =)(0)(2131x p x p + )()(21x p x p +=1 得4 3 1)(=x p 4 12)(=x p 马尔可夫信源熵H = ∑∑- I J i j i j i x x p x x p x p )(log )()( 得 H=0.689bit/符号 2.设有一个无记忆信源发出符号A 和B ,已知4 341)(.)(= =B p A p 。求: ①计算该信源熵; ②设该信源改为发出二重符号序列消息的信源,采用费诺编码方法,求其平均信息传输速率; ③又设该信源改为发三重序列消息的信源,采用霍夫曼编码方法,求其平均信息传输速率。 解:①∑- =X i i x p x p X H )(log )()( =0.812 bit/符号 ②发出二重符号序列消息的信源,发出四种消息的概率分别为 用费诺编码方法 代码组 b i BB 0 1 BA 10 2 AB 110 3 AA 111 3 无记忆信源 624.1)(2)(2 ==X H X H bit/双符号 平均代码组长度 2B =1.687 bit/双符号 B X H R )(22==0.963 bit/码元时间 ③三重符号序列消息有8个,它们的概率分别为 用霍夫曼编码方法 代码组 b i BBB 64 27 0 0 1 BBA 64 9 0 )(6419 1 110 3
信息论与编码理论习题 答案 LG GROUP system office room 【LGA16H-LGYY-LGUA8Q8-LGA162】
第二章 信息量和熵 八元编码系统,码长为3,第一个符号用于同步,每秒1000个码字,求它的信息速 率。 解:同步信息均相同,不含信息,因此 每个码字的信息量为 2?8log =2?3=6 bit 因此,信息速率为 6?1000=6000 bit/s 掷一对无偏骰子,告诉你得到的总的点数为:(a) 7; (b) 12。问各得到多少信息 量。 解:(1) 可能的组合为 {1,6},{2,5},{3,4},{4,3},{5,2},{6,1} )(a p =366=6 1 得到的信息量 =) (1 log a p =6log = bit (2) 可能的唯一,为 {6,6} )(b p =361 得到的信息量=) (1 log b p =36log = bit 经过充分洗牌后的一副扑克(52张),问: (a) 任何一种特定的排列所给出的信息量是多少? (b) 若从中抽取13张牌,所给出的点数都不相同时得到多少信息量? 解:(a) )(a p =! 521 信息量=) (1 log a p =!52log = bit (b) ? ??????花色任选种点数任意排列 13413!13 )(b p =13 52134!13A ?=1352 13 4C 信息量=1313 52 4log log -C = bit 随机掷3颗骰子,X 表示第一颗骰子的结果,Y 表示第一和第二颗骰子的点数之和, Z 表示3颗骰子的点数之和,试求)|(Y Z H 、)|(Y X H 、),|(Y X Z H 、 )|,(Y Z X H 、)|(X Z H 。
第一章 1.设计现代OS的主要目标是什么? 答:(1)有效性(2)方便性(3)可扩充性(4)开放性 4.试说明推劢多道批处理系统形成和収展的主要劢力是什么? 答:主要动力来源于四个方面的社会需求与技术发展: (1)不断提高计算机资源的利用率; (2)方便用户; (3)器件的不断更新换代; (4)计算机体系结构的不断发展。 12.试从交互性、及时性以及可靠性方面,将分时系统不实时系统迚行比较。答:(1)及时性:实时信息处理系统对实时性的要求与分时系统类似,都是以人所能接受的等待时间来确定;而实时控制系统的及时性,是以控制对象所要求的开始截止时间或完成截止时间来确定的,一般为秒级到毫秒级,甚至有的要低于100微妙。 (2)交互性:实时信息处理系统具有交互性,但人与系统的交互仅限于访问系统中某些特定的专用服务程序。不像分时系统那样能向终端用户提供数据和资源共享等服务。 (3)可靠性:分时系统也要求系统可靠,但相比之下,实时系统则要求系统具有高度的可靠性。因为任何差错都可能带来巨大的经济损失,甚至是灾难性后果,所以在实时系统中,往往都采取了多级容错措施保障系统的安全性及数据的安全性。 13.OS有哪几大特征?其最基本的特征是什么? 答:并发性、共享性、虚拟性和异步性四个基本特征;最基本的特征是并发性。 第二章 2. 画出下面四条诧句的前趋图: S1=a:=x+y; S2=b:=z+1; S3=c:=a –b;S4=w:=c+1; 8.试说明迚程在三个基本状态之间转换的典型原因。 答:(1)就绪状态→执行状态:进程分配到CPU资源 (2)执行状态→就绪状态:时间片用完 (3)执行状态→阻塞状态:I/O请求 (4)阻塞状态→就绪状态:I/O完成
bit/s 104.98310661.130)/)(()/(R bit/frame 10661.1322.3105)(H 105)(H bit/pels 322.310log )(log )()(H 76650510 10?=??=?=∴?=??=??====∑=frame bit X H s frame r x X a p a p x i i i 所需信息速率为:每帧图像的熵是:每个像素的熵是:,由熵的极值性: 由于亮度电平等概出现 . 5.2,,5.25.2477.210 log 300log )(H )(H pels /bit 300log )(log )()(H bit 3001030,10,,3001300 11倍左右比黑白电视系统高彩色电视系统信息率要图形所以传输相同的倍作用大信息量比黑白电视系统彩色电视系统每个像素每个像素的熵是:量化 所以每个像素需要用个亮度每个色彩度需要求下在满足黑白电视系统要个不同色彩度增加∴≈====∴=?∑=x x b p b p x i i i 个汉字 最少需要数描述一帧图像需要汉字每个汉字所包含信息量每个汉字所出现概率每帧图象所含信息量556 6 5 5 10322.6/10322.61 .0log 101.2)()()()(,log H(c):1.010000 1000 symble /bit 101.2128log 103)(103)(: ?∴?=-?=≥ ≤-=∴== ?=??=??=frame c H X H n c nH X H n p p x H X H ),...,,(21n p p p n m ≤≤0∑=-=m i i m p q 1 1)log(),,...,,(),...,,(2121m n q q p p p H p p p H m m m n -+≤ ∑∑+==- -=>-=<-=''-=''∴>- =''-=''>-=n m i i i m i i i n p p p p p p p H x x x x f x e x x x f x x e x x x f x x x x f 1 121log log ),...,,( )0(log )( 0log )log ()(0 log )log ()()0(log )( 又为凸函数。即又为凸函数,如下:先证明 时等式成立。 当且仅当时等式成立。当且仅当即可得: 的算术平均值的函数,函数的平均值小于变量由凸函数的性质,变量n m m m m m n m m m i i i m m m m m m i i i n m i i i m i i i n n m m m m m n m i i i m m n m i i n m i i n m i i n m i i n m i i i p p p m n q q p p p H p p p H q q p p q p p p H m n q q q p p p p p p p p p H p p p m n q q q p p m n q q m n p m n p m n m n p f m n m n p f m n p p ===-+≤--=-+--≤- -=∴===-+-≤- --=----=---≤---=- ++==+==+++=+=+=+=+=+=∑∑∑∑∑∑∑∑∑ ∑...)log(),,...,,(),...,,(log log ),,...,,() log(log log log log ),...,,(...) log(log log log log )()()() ()(log 2121211 211 1 1 21211 1111 1 X n
信息论与编码理论习题解 第二章-信息量和熵 解: 平均每个符号长为:154 4.0312.032= ?+?秒 每个符号的熵为9183.03log 3 1 23log 32=?+?比特/符号 所以信息速率为444.34 15 9183.0=?比特/秒 解: 同步信号均相同不含信息,其余认为等概, 每个码字的信息量为 3*2=6 比特; 所以信息速率为600010006=?比特/秒 解:(a)一对骰子总点数为7的概率是 36 6 所以得到的信息量为 585.2)366(log 2= 比特 (b) 一对骰子总点数为12的概率是36 1 所以得到的信息量为 17.536 1 log 2= 比特 解: (a)任一特定排列的概率为 ! 521 ,所以给出的信息量为 58.225! 521 log 2 =- 比特 (b) 从中任取13张牌,所给出的点数都不相同的概率为 1352 13 13 521344!13C A =? 所以得到的信息量为 21.134 log 1313 52 2=C 比特. 解:易证每次出现i 点的概率为 21 i ,所以
比特比特比特比特比特比特比特398.221 log 21)(807.1)6(070.2)5(392.2)4(807.2)3(392.3)2(392.4)1(6,5,4,3,2,1,21 log )(26 12=-==============-==∑ =i i X H x I x I x I x I x I x I i i i x I i 解: 可能有的排列总数为 27720! 5!4!3! 12= 没有两棵梧桐树相邻的排列数可如下图求得, Y X Y X Y X Y X Y X Y X Y X Y 图中X 表示白杨或白桦,它有???? ??37种排法,Y 表示梧桐树可以栽 种的位置,它有???? ??58种排法,所以共有???? ??58*???? ??37=1960种排法保证没有 两棵梧桐树相邻,因此若告诉你没有两棵梧桐树相邻时,得到关于树排列的信息为1960log 27720log 22-= 比特 解: X=0表示未录取,X=1表示录取; Y=0表示本市,Y=1表示外地; Z=0表示学过英语,Z=1表示未学过英语,由此得
第一章 1 .设计现代OS 的主要目标是什么? 答:(1)有效性(2)方便性(3)可扩充性(4)开放性 2 .OS 的作用可表现在哪几个方面? 答:(1)OS作为用户与计算机硬件系统之间的接口 (2)OS 作为计算机系统资源的管理者 (3)OS 实现了对计算机资源的抽象 4 .试说明推动多道批处理系统形成和发展的主要动力是什么?答:主要动力来源于四个方面的社会需求与技术发展: (1)不断提高计算机资源的利用率; (2)方便用户; (3)器件的不断更新换代; (4)计算机体系结构的不断发展。 7 .实现分时系统的关键问题是什么?应如何解决?答:关键问题是当用户在自己的终端上键入命令时,系统应能及时接收并及时处理该命令,在用户能接受的时延内将结果返回给用户。 解决方法:针对及时接收问题,可以在系统中设置多路卡,使主机能同时接收用户从各个终端上输入的数据;为每个终端配置缓冲区,暂存用户键入的命令或数据。针对及时处理问题,应使所有的用户作业都直接进入内存,并且为每个作业分配一个时间片,允许作业只在自己的时间片内运行,这样在不长的时间内,能使每个作业都运行一次。 12 .试从交互性、及时性以及可靠性方面,将分时系统与实时系统进行比较。 答:( 1 )及时性:实时信息处理系统对实时性的要求与分时系统类似,都是以人所能接受的等待时间来确定;而实时控制系统的及时性,是以控制对象所要求的开始截止时间或完成截止时间来确定的,一般为秒级到毫秒级,甚至有的要低于100 微妙。 (2)交互性:实时信息处理系统具有交互性,但人与系统的交互仅限于访问系统中某些特定的专用服务程序。不像分时系统那样能向终端用户提供数据和资源共享等服务。 (3)可靠性:分时系统也要求系统可靠,但相比之下,实时系统则要求系统具有高度 的可靠性。因为任何差错都可能带来巨大的经济损失,甚至是灾难性后果,所以在实时系统中,往往都采取了多级容错措施保障系统的安全性及数据的安全性。 13 .OS 有哪几大特征?其最基本的特征是什么?答:并发性、共享性、虚拟性和异步性四个基本特征;最基本的特征是并发性。
一个马尔可夫信源有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 =??++=?得1231132231231 112331223 231W 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 ==
信息论与编码习题参考答案 第一章 单符号离散信源 同时掷一对均匀的子,试求: (1)“2和6同时出现”这一事件的自信息量; (2)“两个5同时出现”这一事件的自信息量; (3)两个点数的各种组合的熵; (4)两个点数之和的熵; (5)“两个点数中至少有一个是1”的自信息量。 解: bit P a I N n P bit P a I N n P c c N 17.536log log )(361 )2(17.418log log )(362)1(36 662221111 616==-=∴====-=∴== =?==样本空间: (3)信源空间:
bit x H 32.436log 36 16236log 36215)(=??+?? =∴ (4)信源空间: bit x H 71.3636 log 366536log 3610 436log 368336log 366236log 36436log 362)(=??+?+?+??= ∴++ (5) bit P a I N n P 17.111 36 log log )(3611333==-=∴== 如有6行、8列的棋型方格,若有两个质点A 和B ,分别以等概落入任一方格内,且它们的坐标分别为(Xa ,Ya ), (Xb ,Yb ),但A ,B 不能同时落入同一方格内。 (1) 若仅有质点A ,求A 落入任一方格的平均信息量; (2) 若已知A 已落入,求B 落入的平均信息量; (3) 若A ,B 是可辨认的,求A ,B 落入的平均信息量。 解: bit a P a P a a P a I a P A i 58.548log )(log )()(H 48log )(log )(481 )(:)1(48 1 i i i i i ==-=∴=-=∴= ∑=落入任一格的概率Θ bit b P b P b b P b I b P A i 55.547log )(log )()(H 47 log )(log )(47 1 )(:B ,)2(48 1i i i i i ==-=∴=-=∴=∑=落入任一格的概率是落入任一格的情况下在已知Θ
第3章处理机调度1)选择题 (1)在分时操作系统中,进程调度经常采用_D_ 算法。 A. 先来先服务 B. 最高优先权 C. 随机 D. 时间片轮转 (2)_B__ 优先权是在创建进程时确定的,确定之后在整个进程运行期间不再改变。 A. 作业 B. 静态 C. 动态 D. 资源 (3)__A___ 是作业存在的惟一标志。 A. 作业控制块 B. 作业名 C. 进程控制块 D. 进程名 (4)设有四个作业同时到达,每个作业的执行时间均为2小时,它们在一台处理器上按单道方式运行,则平均周转时间为_ B_ 。 A. l小时 B. 5小时 C. 2.5小时 D. 8小时 (5)现有3个同时到达的作业J1、J2和J3,它们的执行时间分别是T1、T2和T3,且T1<T2<T3。系统按单道方式运行且采用短作业优先算法,则平均周转时间是_C_ 。 A. T1+T2+T3 B. (T1+T2+T3)/3 C. (3T1+2T2+T3)/3 D. (T1+2T2+3T3)/3 (6)__D__ 是指从作业提交给系统到作业完成的时间间隔。 A. 运行时间 B. 响应时间 C. 等待时间 D. 周转时间 (7)下述作业调度算法中,_ C_调度算法与作业的估计运行时间有关。 A. 先来先服务 B. 多级队列 C. 短作业优先 D. 时间片轮转 2)填空题 (1)进程的调度方式有两种,一种是抢占(剥夺)式,另一种是非抢占(非剥夺)式。 (2)在_FCFS_ 调度算法中,按照进程进入就绪队列的先后次序来分配处理机。 (3)采用时间片轮转法时,时间片过大,就会使轮转法转化为FCFS_ 调度算法。 (4)一个作业可以分成若干顺序处理的加工步骤,每个加工步骤称为一个_作业步_ 。 (5)作业生存期共经历四个状态,它们是提交、后备、运行和完成。 (6)既考虑作业等待时间,又考虑作业执行时间的调度算法是_高响应比优先____ 。 3)解答题 (1)单道批处理系统中有4个作业,其有关情况如表3-9所示。在采用响应比高者优先调度算法时分别计算其平均周转时间T和平均带权周转时间W。(运行时间为小时,按十进制计算) 表3-9 作业的提交时间和运行时间
I (X ;Y=1)= P(x/Y 1)I(x;Y 1) x P(x/Y 1)log P(x/Y 1) P(x) = P(X 0/Y 1)log P(X 0/Y 1) P(X 0) P(X 1/Y 1)log P(X 1/Y 1) P(X 1) 部分答案,仅供参考。 信息速率是指平均每秒传输的信息量点和划出现的信息量分别为log3Jog3, 2’ 一秒钟点和划出现的次数平均为 1 15 2 1 ~4 0.20.4 - 3 3 一秒钟点和划分别出现的次数平均为巴5 4 4 那么根据两者出现的次数,可以计算一秒钟其信息量平均为10 log 3 5 竺 5 4 2 4 4 2 解: ⑻骰子A和B,掷出7点有以下6种可能: A=1,B=6; A=2,B=5; A=3,B=4; A=4,B=3; A=5,B=2; A=6,B=1 概率为6/36=1/6,所以信息量 -log(1/6)=1+log3 ~ bit (b)骰子A和B,掷出12点只有1种可能: A=6,B=6 概率为1/36,所以信息量 -log(1/36)=2+log9 ~ bit 解: 出现各点数的概率和信息量: 1 点:1/21 , log21 ?bit ; 2 点:2/21 , log21-1 ?bit ; 3 点:1/7 , log7 4 点:4/21 , log21-2 5 点:5/21 , log (21/5 )~; 6 点:2/ 7 , log(7/2)? 平均信息量: (1/21) X +(2/21) X +(1/7) X +(4/21) X +(5/21) X +(2/7) 解: X=1:考生被录取;X=0考生未被录取; Y=1:考生来自本市;Y=0考生来自外地; Z=1:考生学过英语;z=o:考生未学过英语 P(X=1)=1/4, P( X=q=3/4; P( Y=1/ X=1)=1/2 ;P( Y=1/ X=0)=1/10 ;P(Z=1/ Y=1 )=1, P( Z=1/ X=0, Y=0 )=, P( Z=1/ X=1, Y=0 )=, P(Z=1/Y=0)= (a)P(X=0,Y=1)=P(Y=1/X=0)P(X=0)=, P(X=1,Y=1)= P(Y=1/X=1)P(X=1)= P(Y=1)= P(X=0,Y=1)+ P(X=1,Y=1)= P(X=0/Y=1)=P(X=0,Y=1)/P(Y=1)=, P(X=1/Y=1)=P(X=1,Y=1)/P(Y=1)=
信息论与编码理论习题答案全解
第二章 信息量和熵 2.2 八元编码系统,码长为3,第一个符号用于同步,每秒1000个码字,求它的 信息速率。 解:同步信息均相同,不含信息,因此 每个码字的信息量为 2?8log =2?3=6 bit 因此,信息速率为 6?1000=6000 bit/s 2.3 掷一对无偏骰子,告诉你得到的总的点数为:(a) 7; (b) 12。问各得到多少 信息量。 解:(1) 可能的组合为 {1,6},{2,5},{3,4},{4,3},{5,2},{6,1} )(a p =366=6 1 得到的信息量 =) (1 log a p =6log =2.585 bit (2) 可能的唯一,为 {6,6} )(b p =361 得到的信息量=) (1 log b p =36log =5.17 bit 2.4 经过充分洗牌后的一副扑克(52张),问: (a) 任何一种特定的排列所给出的信息量是多少? (b) 若从中抽取13张牌,所给出的点数都不相同时得到多少信息量? 解:(a) )(a p =! 521 信息量=) (1 log a p =!52log =225.58 bit (b) ???????花色任选 种点数任意排列 13413!13 )(b p =13 52134!13A ?=1352 13 4C 信息量=1313 52 4log log -C =13.208 bit
2.9 随机掷3颗骰子,X 表示第一颗骰子的结果,Y 表示第一和第二颗骰子的 点数之和,Z 表示3颗骰子的点数之和,试求)|(Y Z H 、)|(Y X H 、 ),|(Y X Z H 、)|,(Y Z X H 、)|(X Z H 。 解:令第一第二第三颗骰子的结果分别为321,,x x x ,1x ,2x ,3x 相互独立, 则1x X =,21x x Y +=,321x x x Z ++= )|(Y Z H =)(3x H =log 6=2.585 bit )|(X Z H =)(32x x H +=)(Y H =2?( 361log 36+362log 18+363log 12+364log 9+365log 536)+36 6 log 6 =3.2744 bit )|(Y X H =)(X H -);(Y X I =)(X H -[)(Y H -)|(X Y H ] 而)|(X Y H =)(X H ,所以)|(Y X H = 2)(X H -)(Y H =1.8955 bit 或)|(Y X H =)(XY H -)(Y H =)(X H +)|(X Y H -)(Y H 而)|(X Y H =)(X H ,所以)|(Y X H =2)(X H -)(Y H =1.8955 bit ),|(Y X Z H =)|(Y Z H =)(X H =2.585 bit )|,(Y Z X H =)|(Y X H +)|(XY Z H =1.8955+2.585=4.4805 bit 2.10 设一个系统传送10个数字,0,1,…,9。奇数在传送过程中以0.5的概 率错成另外一个奇数,其余正确接收,求收到一个数字平均得到的信息量。 解: 信道 X Y 9,7,5,3,1=i 8,6,4,2,0=i √Χ );(Y X I =)(Y H -)|(X Y H 因为输入等概,由信道条件可知,
2.1 一类操作系统服务提供对用户很有用的函数,主要包括用户界面、程序执行、I/O操作、文件系统操作、通信、错误检测等。 另一类操作系统函数不是帮助用户而是确保系统本身高效运行,包括资源分配、统计、保护和安全等。 这两类服务的区别在于服务的对象不同,一类是针对用户,另一类是针对系统本身。 2.6 优点:采用同样的系统调用界面,可以使用户的程序代码用相同的方式被写入设备和文件,利于用户程序的开发。还利于设备驱动程序代码,可以支持规范定义的API。 缺点:系统调用为所需要的服务提供最小的系统接口来实现所需要的功能,由于设备和文件读写速度不同,若是同一接口的话可能会处理不过来。 2.9 策略决定做什么,机制决定如何做。他们两个的区分对于灵活性来说很重要。策略可能会随时间或位置而有所改变。在最坏的情况下,每次策略改变都可能需要底层机制的改变。系统更需要通用机制,这样策略的改变只需要重定义一些系统参数,而不需要改变机制,提高了系统灵活性。 3.1、短期调度:从准备执行的进程中选择进程,并为之分配CPU; 中期调度:在分时系统中使用,进程能从内存中移出,之后,进程能被重新调入内存,并从中断处继续执行,采用了交换的方案。 长期调度:从缓冲池中选择进程,并装入内存以准备执行。 它们的主要区别是它们执行的频率。短期调度必须频繁地为CPU选择新进程,而长期调度程序执行地并不频繁,只有当进程离开系统后,才可能需要调度长期调度程序。 3.4、当控制返回到父进程时,value值不变,A行将输出:PARENT:value=5。 4.1、对于顺序结构的程序来说,单线程要比多线程的功能好,比如(1)输入三角形的三边长,求三角形面积;(2)从键盘输入一个大写字母,将它改为小写字母输出。
第二章 信息量和熵 2.2 八元编码系统,码长为3,第一个符号用于同步,每秒1000个码字,求它 的信息速率。 解:同步信息均相同,不含信息,因此 每个码字的信息量为 2?8log =2?3=6 bit 因此,信息速率为 6?1000=6000 bit/s 2.3 掷一对无偏骰子,告诉你得到的总的点数为:(a) 7; (b) 12。问各得到多 少信息量。 解:(1) 可能的组合为 {1,6},{2,5},{3,4},{4,3},{5,2},{6,1} )(a p = 366=6 1 得到的信息量 =) (1 log a p =6log =2.585 bit (2) 可能的唯一,为 {6,6} )( b p = 36 1 得到的信息量=) (1 log b p =36log =5.17 bit 2.4 经过充分洗牌后的一副扑克(52),问: (a) 任何一种特定的排列所给出的信息量是多少? (b) 若从中抽取13牌,所给出的点数都不相同时得到多少信息量?
解:(a) )(a p = ! 521 信息量=) (1 log a p =!52log =225.58 bit (b) ???????花色任选 种点数任意排列 13413!13 )(b p =13 52134!13A ?=1352 13 4C 信息量=1313 52 4log log -C =13.208 bit 2.9 随机掷3颗骰子,X 表示第一颗骰子的结果,Y 表示第一和第二颗骰子的点 数之和,Z 表示3颗骰子的点数之和,试求)|(Y Z H 、)|(Y X H 、),|(Y X Z H 、 )|,(Y Z X H 、)|(X Z H 。 解:令第一第二第三颗骰子的结果分别为321,,x x x ,1x ,2x ,3x 相互独立, 则1x X =,21x x Y +=,321x x x Z ++= )|(Y Z H =)(3x H =log 6=2.585 bit )|(X Z H =)(32x x H +=)(Y H =2?( 361log 36+362log 18+363log 12+364log 9+365log 536)+36 6log 6 =3.2744 bit )|(Y X H =)(X H -);(Y X I =)(X H -[)(Y H -)|(X Y H ] 而)|(X Y H =)(X H ,所以)|(Y X H = 2)(X H -)(Y H =1.8955 bit 或)|(Y X H =)(XY H -)(Y H =)(X H +)|(X Y H -)(Y H 而)|(X Y H =)(X H ,所以)|(Y X H =2)(X H -)(Y H =1.8955 bit
1.1在多道程序和分时环境中,多个用户同时共享一个系统,返种情冴导致多种安全问题。a. 列出此类的问题b.在一个分时机器中,能否确保像在与用机器上一样的安全度?并解释乀。 Answer:a.窃叏戒者复制某用户癿程序戒数据;没有合理癿预算来使用资源(CPU,内存,磁盘空闱,外围设备)b.应该丌行,因为人类设计癿仸何保护机制都会丌可避兊癿被另外癿人所破译,而丏径自信癿认为程序本身癿实现是正确癿是一件困难癿亊。 1.2资源的利用问题在各种各样的操作系统中出现。试例丼在下列的环境中哪种资源必须被严栺的管理。(a)大型电脑戒迷你电脑系统(b)不服务器相联的工作站(c)手持电脑 Answer: (a)大型电脑戒迷你电脑系统:内存呾CPU资源,外存,网络带宽(b)不服务器相联癿工作站:内存呾CPU资源(c)手持电脑:功率消耗,内存资源 1.3在什举情冴下一个用户使用一个分时系统比使用一台个人计算机戒单用户 工作站更好? Answer:当另外使用分时系统癿用户较少时,仸务十分巨大,硬件速度径快,分时系统有意丿。充分利用该系统可以对用户癿问题产生影响。比起个人电脑,问题可以被更快癿解决。迓有一种可能収生癿情冴是在同一时闱有许多另外癿用户在同一时闱使用资源。当作业足够小,丏能在个人计算机上合理癿运行时,以及当个人计算机癿性能能够充分癿运行程序来达到用户癿满意时,个人计算机是最好癿,。 1.4在下面丼出的三个功能中,哪个功能在下列两种环境下,(a)手持装置(b)实
时系统需要操作系统的支持?(a)批处理程序(b)虚拟存储器(c)分时 Answer:对二实时系统来说,操作系统需要以一种公平癿方式支持虚拟存储器呾分时系统。对二手持系统,操作系统需要提供虚拟存储器,但是丌需要提供分时系统。批处理程序在两种环境中都是非必需癿。 1.5描述对称多处理(SMP)和非对称多处理乀间的区别。多处理系统的三个优点和一个缺点? Answer:SMP意味着所以处理器都对等,而丏I/O可以在仸何处理器上运行。非对称多处理有一个主处理器控制系统,不剩下癿处理器是随从关系。主处理器为从处理器安排工作,而丏I/O也叧在主处理器上运行。多处理器系统能比单处理器系统节省资金,返是因为他们能共享外设,大容量存储呾电源供给。它们可以更快速癿运行程序呾增加可靠性。多处理器系统能比单处理器系统在软、硬件上也更复杂(增加计算量、觃模经济、增加可靠性) 1.6集群系统不多道程序系统的区别是什举?两台机器属二一个集群来协作提 供一个高可靠性的服务器的要求是什举? Answer:集群系统是由多个计算机耦合成单一系统幵分布二整个集群来完成计算仸务。另一方面,多道程序系统可以被看做是一个有多个CPU组成癿单一癿物理实体。集群系统癿耦合度比多道程序系统癿要低。集群系统通过消息迕行通信,而多道程序系统是通过共享癿存储空闱。为了两台处理器提供较高癿可靠性服务,两台机器上癿状态必项被复制,幵丏要持续癿更新。当一台处理器出现敀障时,另一台处理器能够接管敀障处理癿功能。 1.7试区分分布式系统(distribute system)的客户机-服务器(client-server)模型不对等系统(peer-to-peer)模型
第一章操作系统引论 一、填空题 1~5 BCABA 6~8BCB 、填空题 处理机管理 计算机硬件 分时系统 单道批处理系统 、简答题 1. 什么叫多道程序?试述多道程序设计技术的基本思想 及特征。为什么对作业 进行多道批处理可以提高系统效率? 多道程序设计技术是指在计算机内存中同时存放几道相互独立的程序, 使它 们在管理程序控制下,相互穿插运行。 基本思想:在计算机的内存中同时存放多道相互独立的程序, 当某道程序因 某种原因不能继续运行下去时候,管理程序就将另一道程序投入运行,这样使几 道程序在系统内并行工作,可使中央处理机及外设尽量处于忙碌状态, 从而大大 提高计算机使用效率。 特征:多道性;无序性;调度性 在批处理系统中采用多道程序设计技术形成多道批处理系统, 多个作业成批送入 计算机,由作业调度程序自动选择作业运行,这样提高了系统效率。 2. 批处理系统、分时系统和实时系统各有什么特点?各适合应用于哪些方面? 批处 理系统得特征:资源利用率高;系统吞吐量大;平均周转时间长;无交 互能力。适用于那些需要较长时间才能完成的大作业。 分时系统的特征:多路性;独立性;及时性;交互性。适合进行各种事务处 理,并为进行软件开发提供了一个良好的环境。 实时系统的特征:多路性;独立性;实时性;可靠性;交互性。适合对随机发生 的外部事件能做出及时地响应和处理的系统, 如实时控制系统,实时信息处理系 统。1、 2、 存储器管理 设备管理 计算机软件 实时系统 批处理系统 多道批处理系统 文件管理
第二章进程管理 一、填空题 1~6 CBABBB 7 ① A ② C ③ B ④ D 8 ① D ② B 9 ~10 CA 11~15 CBBDB 16~18 DDC 20~21 BB 22 ① B ② D ③ F 25 B 26~30 BDACB 31~32 AD 二、填空题 1、动态性并发性 2、可用资源的数量等待使用资源的进程数 3、一次只允许一个进程使用的共享资源每个进程中访问临界资源的那段代码 4、执行态就绪态等待态 5、程序数据进程控制块进程控制块 &同步关系 7、等待 8、进程控制块 9、P V 11、同步互斥同步互斥 12、P V P V P V 13、封闭性 14、-(m-1)~1 15、② 16、动静 17、4 0 18、s-1<0 19、①③ 三、简答题 1.在操作系统中为什么要引入进程的概念?进程和程序的关系? 现代计算机系统中程序并发执行和资源共享的需要,使得系统的工作情况变得非常复杂,而程序作为机器指令集合,这一静态概念已经不能如实反映程序并发执行过程的动态性,因此,引入进程的概念来描述程序的动态执行过程。这对于我们理解、描述和设计操作系统具有重要意义。 进程和程序关系类似生活中的炒菜与菜谱。菜谱相同,而各人炒出来的菜的味道却差别很大。原因是菜谱基本上是一种静态描述,它不可能把所有执行的动态过程中,涉及的时空、环境等因素一一用指令描述清楚。 2.试从动态性、并发性和独立性上比较进程和程序。 动态性:进程的实质是进程实体的一次执行过程。动态性是进程的基本特征。而程序只是一组有序指令的集合,其本身不具有动态的含义,因而是静态的。 并发性:并发性是进程的重要特征,引入进程的目的也正是为了使其进程实体能和其他进程实体并发执行,而程序是不能并发执行的。 独立性:进程的独立性表现在进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。而程序不能做为一个独立的单位参与运行。 3.何谓进程,进程由哪些部分组成? 进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位进程由程序段,数据段,进程控制块三部分组成。
1. 有一个马尔可夫信源,已知p(x 1|x 1)=2/3,p(x 2|x 1)=1/3,p(x 1|x 2)=1,p(x 2|x 2)=0,试画出该信源的香农线图,并求出信源熵。 解:该信源的香农线图为: 1/3 ○ ○ 2/3 (x 1) 1 (x 2) 在计算信源熵之前,先用转移概率求稳定状态下二个状态x 1和 x 2 的概率)(1x p 和)(2x p 立方程:)()()(1111x p x x p x p =+)()(221x p x x p =)()(2132x p x p + )()()(1122x p x x p x p =+)()(222x p x x p =)(0)(2131x p x p + )()(21x p x p +=1 得4 3 1)(=x p 4 12)(=x p 马尔可夫信源熵H = ∑∑- I J i j i j i x x p x x p x p )(log )()( 得 H=符号 2.设有一个无记忆信源发出符号A 和B ,已知4 3 41)(.)(= =B p A p 。求: ①计算该信源熵; ②设该信源改为发出二重符号序列消息的信源,采用费诺编码方法,求其平均信息传输速率; ③又设该信源改为发三重序列消息的信源,采用霍夫曼编码方法,求其平均信息传输速率。 解:①∑- =X i i x p x p X H )(log )()( = bit/符号 ②发出二重符号序列消息的信源,发出四种消息的概率分别为 1614141)(=?=AA p 1634341 )(=?=AB p 1634143)(=?=BA p 1694343)(=?=BB p 用费诺编码方法 代码组 b i BB 0 1 BA 10 2 AB 110 3 AA 111 3 无记忆信源 624.1)(2)(2 ==X H X H bit/双符号 平均代码组长度 2B = bit/双符号 B X H R )(22== bit/码元时间 ③三重符号序列消息有8个,它们的概率分别为
《计算机操作系统》课后习题答案 注:课本为《计算机操作系统(第四版)》,汤小丹梁红兵哲凤屏汤子瀛编着,西安电子科技大学出版社出版 第一章 1.设计现代OS的主要目标是什么 答:(1)有效性(2)方便性(3)可扩充性(4)开放性 2.OS的作用可表现在哪几个方面 答:(1)OS作为用户与计算机硬件系统之间的接口 (2)OS作为计算机系统资源的管理者 (3)OS实现了对计算机资源的抽象 3.为什么说OS实现了对计算机资源的抽象 答:OS首先在裸机上覆盖一层I/O设备管理软件,实现了对计算机硬件操作的第一层次抽象;在第一层软件上再覆盖文件管理软件,实现了对硬件资源操作的第二层次抽象。OS 通过在计算机硬件上安装多层系统软件,增强了系统功能,隐藏了对硬件操作的细节,由它们共同实现了对计算机资源的抽象。 4.试说明推动多道批处理系统形成和发展的主要动力是什么 答:主要动力来源于四个方面的社会需求与技术发展: (1)不断提高计算机资源的利用率; (2)方便用户; (3)器件的不断更新换代; (4)计算机体系结构的不断发展。 5.何谓脱机I/O和联机I/O 答:脱机I/O 是指事先将装有用户程序和数据的纸带或卡片装入纸带输入机或卡片机,在外围机的控制下,把纸带或卡片上的数据或程序输入到磁带上。该方式下的输入输出由外围机控制完成,是在脱离主机的情况下进行的。 而联机I/O方式是指程序和数据的输入输出都是在主机的直接控制下进行的。 6.试说明推动分时系统形成和发展的主要动力是什么 答:推动分时系统形成和发展的主要动力是更好地满足用户的需要。主要表现在:CPU 的分时使用缩短了作业的平均周转时间;人机交互能力使用户能直接控制自己的作业;主机的共享使多用户能同时使用同一台计算机,独立地处理自己的作业。 7.实现分时系统的关键问题是什么应如何解决 答:关键问题是当用户在自己的终端上键入命令时,系统应能及时接收并及时处理该命令,
1.6为了使电视图象获得良好的清晰度和规定的对比度,需要用5×105个像素和10个不同的亮度电平,并设每秒要传送30帧图象,所有的像素是独立的,且所有亮度电平等概出现。求传输此图象所需要的信息率(bit/s )。 解: bit/s 104.98310661.130)/)(()/(R bit/frame 10661.1322.3105)(H 105)(H bit/pels 322.310log )(log )()(H 76650510 10?=??=?=∴?=??=??====∑=frame bit X H s frame r x X a p a p x i i i 所需信息速率为:每帧图像的熵是:每个像素的熵是:,由熵的极值性: 由于亮度电平等概出现 1.7设某彩电系统,除了满足对于黑白电视系统的上述要求外,还必须有30个不同的色彩度。试证明传输这种彩电系统的信息率要比黑白系统的信息率大 2.5倍左右。 证: . 5.2,,5.25.2477.210 log 300log )(H )(H pels /bit 300log )(log )()(H bit 3001030,10,,3001300 11倍左右比黑白电视系统高彩色电视系统信息率要图形所以传输相同的倍作用大信息量比黑白电视系统彩色电视系统每个像素每个像素的熵是:量化 所以每个像素需要用个亮度每个色彩度需要求下在满足黑白电视系统要个不同色彩度增加∴≈====∴=?∑=x x b p b p x i i i Θ 1.8每帧电视图像可以认为是由3×105个像素组成,所以像素均是独立变化,且每像素又取128个不同的亮度电平,并设亮度电平是等概出现。问每帧图像含有多少信息量?若现在有一个广播员,在约10000个汉字中选1000个字来口述这一电视图像,试问若要恰当地描述此图像,广播员在口述中至少需要多少汉字? 解: 个汉字 最少需要数描述一帧图像需要汉字每个汉字所包含信息量每个汉字所出现概率每帧图象所含信息量556 6 5 5 10322.6/10322.61 .0log 101.2)()()()(,log H(c):1.010000 1000 symble /bit 101.2128log 103)(103)(: ?∴?=-?=≥ ≤-=∴== ?=??=??=frame c H X H n c nH X H n p p x H X H 1.9 给 定 一 个 概 率 分 布 ) ,...,,(21n p p p 和一个整数m , n m ≤≤0。定义 ∑=-=m i i m p q 1 1,证明: )log(),,...,,(),...,,(2121m n q q p p p H p p p H m m m n -+≤。并说明等式何时成立? 证: ∑∑+==- -=>-=<-=''-=''∴>- =''-=''>-=n m i i i m i i i n p p p p p p p H x x x x f x e x x x f x x e x x x f x x x x f 1 121log log ),...,,( )0(log )( 0log )log ()(0 log )log ()()0(log )(ΘΘ又为凸函数。即又为凸函数,如下:先证明 时等式成立。 当且仅当时等式成立。当且仅当即可得: 的算术平均值的函数,函数的平均值小于变量由凸函数的性质,变量n m m m m m n m m m i i i m m m m m m i i i n m i i i m i i i n n m m m m m n m i i i m m n m i i n m i i n m i i n m i i n m i i i p p p m n q q p p p H p p p H q q p p q p p p H m n q q q p p p p p p p p p H p p p m n q q q p p m n q q m n p m n p m n m n p f m n m n p f m n p p ===-+≤--=-+--≤- -=∴===-+-≤- --=----=---≤---=- ++==+==+++=+=+=+=+=+=∑∑∑∑∑∑∑∑∑ ∑...)log(),,...,,(),...,,(log log ),,...,,() log(log log log log ),...,,(...) log(log log log log )()()() ()(log 2121211 211 1 1 21211 1111 1 ΘΘ 2.13把n 个二进制对称信道串接起来,每个二进制对称信道的错误传输概率为p(0