当前位置：文档库 › 信息论与编码-曹雪虹-课后习题答案

信息论与编码-曹雪虹-课后习题答案

3.1 设二元对称信道的传递矩阵为?

?????????32313132

(1) 若P(0) = 3/4, P(1) = 1/4，求H(X), H(X/Y), H(Y/X)和I(X;Y)； (2) 求该信道的信道容量及其达到信道容量时的输入概率分布；

解： 1)

symbol

bit Y X H X H Y X I symbol bit X Y H Y H X H Y X H X Y H Y H Y X H X H Y X I symbol bit y p Y H x y p x p x y p x p y x p y x p y p x y p x p x y p x p y x p y x p y p symbol

bit x y p x y p x p X Y H symbol

bit x p X H j

j i

i j i j i i i / 062.0749.0811.0)/()();(/ 749.0918.0980.0811.0)/()()()/()

/()()/()();(/ 980.0)4167.0log 4167.05833.0log 5833.0()()(4167

.03

413143)/()()/()()()()(5833.031

413243)/()()/()()()()(/ 918.0 10

log )3

lg 324131lg 314131lg 314332lg 3243( )

/(log )/()()/(/ 811.0)41

log 4143log 43()()(222221212221221211112111222=-==-==+-=+-=-=-==?+?-=-==?+?=+=+==?+?=

+=+==??+?+?+?-=-==?+?-=-=∑∑∑∑

2221122

max (;)log log 2(lg lg )log 100.082 /3333

mi C I X Y m H bit symbol

==-=++?=其最佳输入分布为1

()2

i p x =

3.5 求下列二个信道的信道容量，并加以比较

（1）

???

? ??----εεεεεε22p p p p （2）???

? ??----εε

εεεε20

02p p p p

其中p+p =1

解：

（1）此信道是准对称信道，信道矩阵中Y 可划分成三个互不相交的子集由于集列所组

成的矩阵????

??----εεεεp p p p ,???

??εε22而这两个子矩阵满足对称性，因此可直接利用准对称信道的信道容量公式进行计算。

C1=logr-H(p1’ p2’ p3’)-

Mk k N k log 2

∑=

其中r=2,N1=M1=1-2ε N2=ε2 M2=4ε 所以 C1=log2-H(ε-p ,p-ε,2ε)-(1-2ε)log(1-2ε)-2εlog4ε

=log2+(ε-p )log(ε-p )+(p-ε)log(p-ε)+2εlog2ε-(1-2ε)log(1-2ε)-2εlog4ε =log2-2εlog2-(1-2ε)log(1-2ε)+(ε-p )log(ε-p )+(p-ε)log(p-ε) =(1-2ε)log2/(1-2ε)+(ε-p )log(ε-p )+(p-ε)log(p-ε) 输入等概率分布时达到信道容量。

（2）此信道也是准对称信道，也可采用上述两种方法之一来进行计算。先采用准对称信

道的信道容量公式进行计算，此信道矩阵中Y 可划分成两个互不相交的子集，由子

集列所组成的矩阵为???? ?

?----εε

εε

p p p p ，???

??εε2002这两矩阵为对称矩阵其中r=2,N1=M1=1-2ε N2=M2=2ε，所以

C=logr-H(p -ε,p-ε,2ε,0)-∑=2

log k Mk Nk

=log2+(p -ε)log(p -ε)+(p-ε)log(p-ε)+2εlog2ε-(1-2ε)log(1-2ε)-2εlog2ε =log2-(1-2ε)log(1-2ε)+( p -ε)log(p -ε)+(p-ε)log(p-ε) =(1-2ε)log2/(1-2ε)+2εlog2+(p -ε)log(p -ε)+(p-ε)log(p-ε) =C1+2εlog2

输入等概率分布（P （a1）=P （a2）=1/2）时达到此信道容量。比较此两信道容量，可得C2=C1+2εlog2

3. 9 在图片传输中，每帧约有2.25 106个像素，为了能很好地重现图像，能分

16个亮度电平，并假设亮度电平等概分布。试计算每分钟传送一帧图片所需信道的带宽（信噪功率比为30dB ）。

解：

bit t I C bit NH I symbol bit n H t / 101.560

10910

10941025.2/ 416log log 56

6622?=?===?=??=====

15049)10001(log 105.11log 1log 25

H P P C W P P W C N X t

N X t =+?=?

??? ??+=?

???

?+=

4.2 某二元信源??????=??????2/12/110)(X P X 其失真矩阵为

???=a a D 00求这信源的D max 和D min 和R(D)函数。

解：

021

021),(min )(202121),()(min min min max =?+?===

?+?===∑∑i j i j i i

j i i j j y x d x p D a

a y x d x p D D

因为二元等概信源率失真函数：

??-=a D H n D R ln )(

其中n = 2, 所以率失真函数为：

?????? ??-??? ??-+-=a D a D a D a D D R 1ln 1ln 2ln )(

4.3 一个四元对称信源??

????=?????

?4/14/1324/14/110

)(X P X ，接收符号Y = {0, 1, 2, 3}，其失真矩阵为???????????

?0111101111011110，求D max 和D min 及信源的R(D)函数，并画出其曲线（取4至5个点）。

解：

041

041041041),(min )(43041141141141),()(min min min max =?+?+?+?===

?+?+?+?===∑∑i j i j i i

j i i j j y x d x p D y x d x p D D

因为n 元等概信源率失真函数：

??-??? ??-+-+=a D a D n a D a D n D R 1ln 11ln ln )(

其中a = 1, n = 4, 所以率失真函数为：

()()D D D

D D R --++=1ln 13ln

4ln )(

(2) 哪些码是非延长码？

(3) 对所有唯一可译码求出其平均码长和编译效率。解：首先，根据克劳夫特不等式，找出非唯一可译码

31123456231244135236:621

63:222222164

63:

164

:22421:2521:2521

C C C C C C --------------?<+++++=<<++?=+?>+?<

5C ∴不是唯一可译码，而4C ：

又根据码树构造码字的方法

1C ，3C ，6C 的码字均处于终端节点 ∴他们是即时码

5-2

(1) 因为A,B,C,D 四个字母,每个字母用两个码,每个码为0.5ms, 所以每个字母用10ms 当信源等概率分布时,信源熵为H(X)=log(4)=2

平均信息传递速率为bit/ms=200bit/s

(2) 信源熵为

H(X)=

=0.198bit/ms=198bit/s

5-5

(1) 1

128

H(U)=

1 2Log2()

Log4()

Log8()

Log16

()

Log32

()

Log64

()

128

Log128

()

128

Log128

()

+ 1.984

= (2) 每个信源使用3个二进制符号,出现0的次数为

出现1的次数为

P(0)=

P(1)=

(3)

相应的费诺码

（5）香农码和费诺码相同平均码长为

编码效率为：

5-11

（1）信源熵

（2）香农编码：

平均码长：

编码效率为

（3）

平均码长为：

编码效率：

（4）哈夫曼编码

平均码长为：

编码效率：

5.16 已知二元信源{0，1}，其p0=1/4,p1=3/4,试用式（4.129）对序列11111100

编算术码，并计算此序列的平均码长。

解：根据算术编码的编码规则，可得：P(s=11111100) = P2(0)P6(1) = (3/4)6 (1/4)2

7)(1log =??

????=S P l

根据（4.129）可得：

F(S) = P(0) + P(10) + P(110) + P(1110) + P(11110) + P(111110) = 1–

∑≥s

y y P )(= 1 – P(11111111) – P(11111110) – P(11111101) – P(11111100)

= 1– P(111111) = 1– (3/4)6 = 0.82202 = 0.110100100111

又P(S) = A(S)= 0.0000001011011001，所以F(S) + P(S) = 0.1101010 即得C = 0.1101010 得S 的码字为1101010 平均码长L 为 0.875。

信息论与编码课后习题答案

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.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

操作系统概念课后习题答案整理.doc

1.1在多道程序和分时环境中，多个用户同时共享一个系统，返种情冴导致多种安全问题。a. 列出此类的问题b.在一个分时机器中，能否确保像在与用机器上一样的安全度？并解释乀。 Answer:a.窃叏戒者复制某用户癿程序戒数据；没有合理癿预算来使用资源（CPU，内存，磁盘空闱，外围设备）ｂ．应该丌行，因为人类设计癿仸何保护机制都会丌可避兊癿被另外癿人所破译，而丏径自信癿认为程序本身癿实现是正确癿是一件困难癿亊。 1.2资源的利用问题在各种各样的操作系统中出现。试例丼在下列的环境中哪种资源必须被严栺的管理。（ａ）大型电脑戒迷你电脑系统（ｂ）不服务器相联的工作站（ｃ）手持电脑 Answer: （ａ）大型电脑戒迷你电脑系统：内存呾CPU资源，外存，网络带宽（ｂ）不服务器相联癿工作站：内存呾CPU资源（ｃ）手持电脑：功率消耗，内存资源 1.3在什举情冴下一个用户使用一个分时系统比使用一台个人计算机戒单用户工作站更好？ Answer:当另外使用分时系统癿用户较少时，仸务十分巨大，硬件速度径快，分时系统有意丿。充分利用该系统可以对用户癿问题产生影响。比起个人电脑，问题可以被更快癿解决。迓有一种可能収生癿情冴是在同一时闱有许多另外癿用户在同一时闱使用资源。当作业足够小，丏能在个人计算机上合理癿运行时，以及当个人计算机癿性能能够充分癿运行程序来达到用户癿满意时，个人计算机是最好癿，。 1.4在下面丼出的三个功能中，哪个功能在下列两种环境下，(a)手持装置(b)实

时系统需要操作系统的支持？(a)批处理程序(b)虚拟存储器(c)分时 Answer:对二实时系统来说，操作系统需要以一种公平癿方式支持虚拟存储器呾分时系统。对二手持系统，操作系统需要提供虚拟存储器，但是丌需要提供分时系统。批处理程序在两种环境中都是非必需癿。 1.5描述对称多处理（ＳＭＰ）和非对称多处理乀间的区别。多处理系统的三个优点和一个缺点？ Answer:ＳＭＰ意味着所以处理器都对等，而丏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