《信息论与编码》课后答案.doc

1、第二章课后习题【2.1】设有 12 枚同值硬币，其中有一枚为假币。只知道假币的重量与真币的重量不同，但不知究竟是重还是轻。现用比较天平左右两边轻重的方法来测量。为了在天平上称出哪一枚是假币，试问至少必须称多少次？解：从信息论的角度看，“12 枚硬币中，某一枚为假币”该事件发生的概率为 P =112；“假币的重量比真的轻，或重”该事件发生的概率为 P =12；为确定哪一枚是假币，即要消除上述两事件的联合不确定性，由于二者是独立的，因此有I = log12 + log 2 = log 24 比特而用天平称时，有三种可能性：重、轻、相等，三者是等概率的，均为 P =平每一次消除的不确定性为 I =

2、log 3 比特因此，必须称的次数为13，因此天I 1I 2=log 24log 3 2.9 次因此，至少需称 3 次。【延伸】如何测量？分 3 堆，每堆 4 枚，经过 3 次测量能否测出哪一枚为假币。【2.2】同时扔一对均匀的骰子，当得知“两骰子面朝上点数之和为 2”或“面朝上点数之和为 8”或“两骰子面朝上点数是 3 和 4”时，试问这三种情况分别获得多少信息量？解：“两骰子总点数之和为 2”有一种可能，即两骰子的点数各为 1，由于二者是独立的，因此该种情况发生的概率为 P =1 16 6=136，该事件的信息量为：I = log 36 5.17 比特“两骰子总点数之和为 8”共有如下可能

3、：2 和 6、3 和 5、4 和 4、5 和 3、6 和 2，概率为 P =1 16 6536，因此该事件的信息量为：36I = log 2.85 比特5“两骰子面朝上点数是 3 和 4”的可能性有两种：3 和 4、4 和 3，概率为 P =1 16 6118，因此该事件的信息量为：I = log18 4.17 比特【2.3】如果你在不知道今天是星期几的情况下问你的朋友“明天星期几？”则答案中含有多少信息量？如果你在已知今天是星期四的情况下提出同样的问题，则答案中你能获得多少信息量（假设已知星期一至星期日的顺序）？解：如果不知今天星期几时问的话，答案可能有七种可能性，每一种都是等概率的，均为P

4、 =17，因此此时从答案中获得的信息量为I = log 7 = 2.807 比特而当已知今天星期几时问同样的问题，其可能性只有一种，即发生的概率为 1，此时获得的信息量为 0 比特。【2.4】居住某地区的女孩中有 25%是大学生，在女大学生中有 75%是身高 1.6 米以上的，而女孩中身高 1.6 米以上的占总数一半。假如我们得知“身高 1.6 米以上的某女孩是大学生”的消息，问获得多少信息量？解：设 A 表示女孩是大学生， P( A) = 0.25 ；B 表示女孩身高 1.6 米以上， P( B | A) = 0.75 ， P( B) = 0.5“身高 1.6 米以上的某女孩是大学生”的发生

5、概率为 5 = 2 =P( A | B) =P( AB)P( B)=P( A) P(B | A)P( B)=0. 25 0. 750.5= 0.375已知该事件所能获得的信息量为I = log10.375 1.415 比特 X a1 = 0 a2 = 1 a3 = 2 a4 = 31/ 4 1 / 4，其发出的消息为（202120130213001203210110321010021032011223210），求（1） 此消息的自信息是多少？（2） 在此消息中平均每个符号携带的信息量是多少？解：信源是无记忆的，因此，发出的各消息之间是互相独立的，此时发出的消息的自信息即为各消息的自信息之和。根

6、据已知条件，发出各消息所包含的信息量分别为：I (a0 = 0) = log83= 1.415 比特I (a1 = 1) = log 4 = 2 比特I (a2 = 2) = log 4 = 2 比特I (a3 = 3) = log 8 = 3 比特在发出的消息中，共有 14 个“0”符号，13 个“1”符号，12 个“2”符号，6 个“3”符号，则得到消息的自信息为：I = 14 1.415 + 13 2 + 12 2 + 6 3 87.81 比特45 个符号共携带 87.81 比特的信息量，平均每个符号携带的信息量为I =87.8145= 1.95 比特/符号注意：消息中平均每个符号携带的

7、信息量有别于离散平均无记忆信源平均每个符号携带的信息量，后者是信息熵，可计算得H ( X ) = P( x) log P( x) = 1.91比特/符号 = 3 / 81/ 8 【 2.5 】 设 离 散 无 记 忆 信 源 P( x) 【2.6】如有 6 行 8 列的棋型方格，若有二个质点 A 和 B，分别以等概率落入任一方格内，且它们的坐标分别为（XA,YA）和（XB,YB），但 A 和 B 不能落入同一方格内。（1） 若仅有质点 A，求 A 落入任一个格的平均自信息量是多少？（2） 若已知 A 已落入，求 B 落入的平均自信息量。（3） 若 A、B 是可分辨的，求 A、B 同都落入的平均

8、自信息量。解：（1）求质点 A 落入任一格的平均自信息量，即求信息熵，首先得出质点 A 落入任一格的概率空间为： X a2148a3148L a48 1 L 平均自信息量为H ( A) = log 48 = 5.58 比特/符号（2）已知质点 A 已落入，求 B 落入的平均自信息量，即求 H ( B | A) 。A 已落入，B 落入的格可能有 47 个，条件概率 P(b j | ai ) 均为147。平均自信息量为48 47i =1 j =1（3）质点 A 和 B 同时落入的平均自信息量为H ( AB) = H ( A) + H (B | A) = 11.13 比特/符号【2.7】从大量统计资

9、料知道，男性中红绿色盲的发病率为 7%，女性发病率为 0.5%，如果你问一位男同志：“你是否是红绿色盲？”，他的回答可能是“是”，也可能是“否”，问这两个回答中各含有多少信息量？平均每个回答中含有多少信息量？如果你问一位女同志，则答案中含有的平均自信息量是多少？解： a1 P = 1 4848 H ( B | A) = P(ai )P(b j | ai ) log P(b j | ai ) = log 47 = 5.55 比特/符号男同志红绿色盲的概率空间为： X a1 a 2 问男同志回答“是”所获昨的信息量为：I = log10.07 3.836 比特/符号问男同志回答“否”所获得的信息量

10、为：I = log10.93 0.105 比特/符号男同志平均每个回答中含有的信息量为H ( X ) = P( x) log P( x) = 0.366 比特/符号同样，女同志红绿色盲的概率空间为Y P b1 b2 问女同志回答“是”所获昨的信息量为：I = log10.005 7.64 比特/符号问女同志回答“否”所获昨的信息量为：I = log10.995 7.23 10 3 比特/符号女同志平均每个回答中含有的信息量为H (Y ) = P( x) log P( x) = 0.045 比特/符号 X a1 a2 a3 a 4 a5 a6 P( x) 么 H ( X ) log 6 ，不满足

11、信源熵的极值性。解：H ( X ) = P( x) log P( x) = 2.65 log 6原因是给定的信源空间不满足概率空间的完备集这一特性，因此不满足极值条件。 P = 0.07 0.93= 0.005 0.995 = 0.2 0.19 0.18 0.17 0.16 0.17 ，求此信源的熵，并解释为什【2.8】设信源 【 2.9 】 设 离 散 无 记 忆 信 源 S 其 符 号 集 A = a1 , a2 ,., aq ， 知 其 相 应 的 概 率 分 别 为(P1 , P2 ,., Pq ) 。 设 另 一 离 散 无 记 忆 信 源 S ， 其 符 号 集 为 S 信 源 符

12、 号 集 的 两 倍 ，A = ai , i = 1,2,.,2q，并且各符号的概率分布满足Pi = (1 ) PiPi = Pii = 1,2,., qi = q + 1, q + 2,.,2q试写出信源 S 的信息熵与信源 S 的信息熵的关系。解：H (S ) = P( x) log P( x)= (1 ) Pi log(1 )Pi Pi log Pi= (1 ) Pi log(1 ) (1 ) Pi log Pi Pi log Pi log Pi= (1 ) log(1 ) log + H (S )= H (S ) + H ( ,1 )【2.10】设有一概率空间，其概率分布为 p1 ,

13、p 2 ,., p q ，并有 p1 p2 。若取 p1 = p1 ，p2 = p2 + ，其中 0 2 p1 p2 ，而其他概率值不变。试证明由此所得新的概率空间的熵是增加的，并用熵的物理意义加以解释。解：设新的信源为 X ，新信源的熵为：H ( X ) = pi log pi = ( p1 ) log( p1 ) ( p2 + ) log( p2 + ) L pq log p q原信源的熵H ( X ) = pi log pi = p1 log p1 p2 log p 2 L pq log p q因此有，H ( X ) H ( X ) = ( p1 ) log( p1 ) + ( p2 +

14、 ) log( p 2 + ) p1 log p1 p2 log p 2 p p2 2 f ( x) = logp 2 + xp1 x 0令 f ( x) = ( p1 x) log( p1 x) + ( p2 + x) log( p2 + x) ， x 0, 1 ，则即函数 f ( x) 为减函数，因此有 f (0) f ( ) ，即( p1 ) log( p1 ) + ( p 2 + ) log( p2 + ) p1 log p1 + p 2 log p2因此 H ( X ) H ( X ) 成立。【解释】当信源符号的概率趋向等概率分布时，不确定性增加，即信息熵是增加的。L mi=1 j

15、=1H ( p1 , p2 ,K, p L1 , q1 , q 2 ,K, qm ) = H ( p1 , p2 ,K, p L 1 , p L ) + p L H (,p L p Lq,K, m )p L并说明等式的物理意义。解：H ( p1 , p2 ,K, p L1 , q1 , q2 ,K, qm )= p1 log p1 p 2 log p2 K p L 1 log p L 1 q1 log q1 q2 log q 2 K q m log qm= p1 log p1 p 2 log p2 K p L 1 log p L 1 p L log p L + p L log p L q1 l

16、og q1 q2 log q2 K qm log qm= p1 log p1 p 2 log p2 K p L 1 log p L 1 p L log p L + (q1 + q2 + q3 + L + qm ) log p L q1 log q1 q2 log q2 K qm log qm= p1 log p1 p 2 log p2 K p L 1 log p L 1 p L log p L q1 logq1p Lp L p Lq q= p1 log p1 p 2 log p2 K p L 1 log p L 1 p L log p L+ p L (q1p Lq q q q qp L p L

17、 p L p L p L= H ( p1 , p2 ,K, p L1 , p L ) + p L H m (,p L p Lq,K, m )p L【意义】将原信源中某一信源符号进行分割，而分割后的符号概率之和等于被分割的原符号的概率，则新信源的信息熵增加，熵所增加的一项就是由于分割而产生的不确定性量。【2.12】（1）为了使电视图像获得良好的清晰度和规定的适当的对比度，需要用 5105 个【2.11】试证明：若 pi = 1， q j = p L ，则q1 q 2 q 2 log 2 K qm log mlog 1 2 log 2 K m log m )q1 q2像素和 10 个不同亮度电平，

18、求传递此图像所需的信息率（比特/秒）。并设每秒要传送 30帧图像，所有像素是独立变化的，且所有亮度电平等概率出现。（2）设某彩电系统，除了满足对于黑白电视系统的上述要求外，还必须有 30 个不同的色彩度，试证明传输这彩色系统的信息率要比黑白系统的信息率约大 2.5 倍。解：每个像素的电平取自 10 个不同的电平，每一个像素形成的概率空间为： X P a1= 1a2110L a10 1 L 这样，平均每个像素携带的信息量为：H ( X ) = log10 = 3.32 比特/像素现在所有的像素点之间独立变化的，因此，每帧图像含有的信息量为：H ( X N ) = NH ( X ) = 5 105

19、 log10 = 1.66 10 6 比特/帧按每秒传输 30 帧计算，每秒需要传输的比特数，即信息传输率为：30 H ( X N ) = 4.98 10 7 比特/秒除满足黑白电视系统的要求外，还需 30 个不同的色彩度，不妨设每个色彩度等概率出现，则其概率空间为：Y P b1= 1b2130L b30 1 L 其熵为 log 30 比特/符号，由于电平与色彩是互相独立的，因此有H ( XY ) = H ( X ) + H (Y ) = log 300这样，彩色电视系统的信息率与黑白电视系统信息率的比值为H ( XY )H ( X )=log 300log10 2.51010 3030 【2

20、.13】每帧电视图像可以认为是由 3105 个像素组成，所以像素均是独立变化，且每一像素又取 128 个不同的亮度电平，并设亮度电平等概率出现。问每帧图像含有多少信息量？若现有一广播员在约 10000 个汉字的字汇中选 1000 个来口述此电视图像，试问广播员描述此图像所广播的信息量是多少（假设汉字是等概率分布，并且彼此无依赖）？若要恰当地描述此图像，广播员在口述中至少需用多少汉字？解：每个像素的电平亮度形成了一个概率空间，如下： X P a1 a2= 1 1L a128 1 L 平均每个像素携带的信息量为：H ( X ) = log128 = 7 比特/像素每帧图像由 3105 个像素组成，

21、且像素间是独立的，因此每帧图像含有的信息量为：H ( X N ) = NH ( X ) = 2.1 10 6 比特/帧如果用汉字来描述此图像，平均每个汉字携带的信息量为 H (Y ) = log10000 = 13.29 比特/汉字，选择 1000 字来描述，携带的信息量为H (Y N ) = NH (Y ) = 1.329 10 4 比特如果要恰当的描述此图像，即信息不丢失，在上述假设不变的前提下，需要的汉字个数为：H ( X N )H (Y )=2.110613.29 1.58 105 字【2.14】为了传输一个由字母 A、B、C 和 D 组成的符号集，把每个字母编码成两个二元码脉冲序列，

22、以 00 代表 A，01 代表 B，10 代表 C，11 代表 D。每个二元码脉冲宽度为 5ms。（1） 不同字母等概率出现时，计算传输的平均信息速率？128 128128 （2） 若每个字母出现的概率分别为 p A =15， p B =14， pC =14， p D =310，试计算传输的平均速率？解：假设不同字母等概率出现时，平均每个符号携带的信息量为H ( X ) = log 4 = 2 比特每个二元码宽度为 5ms，每个字母需要 2 个二元码，则其传输时间为 10ms，每秒传送n = 100 个，因此信息传输速率为：R = nH ( X ) = 100 2 = 200 比特/秒当不同字

23、母概率不同时，平均传输每个字母携带的信息量为1 1 15 4 4310log103= 1.985 比特/符号此时传输的平均信息速度为R = nH ( X ) = 1.985 10 2 比特/秒【2.15】证明离散平稳信源有 H ( X 3 | X 1 X 2 ) H ( X 2 | X 1 ) ，试说明等式成立的条件。解：H ( X 3 | X 1 X 2 ) = P( x1 x2 x3 ) log P( x3 | x1 x2 )= P( x1 x 2 ) P( x3 | x1 x2 ) log P( x3 | x1 x2 )X 1 X 2 X 3 P( x1 x2 ) P( x3 | x1

24、x2 ) log P( x3 | x2 )X 1 X 2 X 3= H ( X 3 | X 2 )根据信源的平稳性，有 H ( X 3 | X 2 ) = H ( X 2 | X 1 ) ，因此有 H ( X 3 | X 1 X 2 ) H ( X 2 | X 1 ) 。等式成立的条件是 P( x3 | x1 x2 ) = P( x3 | x2 ) 。【2.16】证明离散信源有 H ( X 1 X 2 L X N ) H ( X 1 ) + H ( X 2 ) + L + H ( X N ) ，并说明等式成立的条件。证明：H ( X ) = log 5 + log 4 + log 4 +H (

25、 X 1 X 2 L X N ) = H ( X 1 ) + H ( X 2 | X 1 ) + L + H ( X N | X 1 X 2 L X N 1 )而H ( X N | X 1 X 2 L X N 1 )LX 1 X 2 X N= L P( x1 x2 L x N 1 ) P( x N | x1 x2 L x N 1 ) logP( x N | x1 x2 L x N 1 )X 1 X 2 X N 1 X N L P( x1 x2 L x N 1 ) P( x N | x1 x2 L x N 1 ) logP( x N )X 1 X 2 X N 1 X N= H ( X N )即H

26、 ( X 2 | X 1 ) H ( X 2 )H ( X 3 | X 1 X 2 ) H ( X 3 )代入上述不等式，有H ( X 1 X 2 L X N ) H ( X 1 ) + H ( X 2 ) + L + H ( X N )等号成立的条件是：P( x N | x1 x2 L x N 1 ) = P( x N )P( x N 1 | x1 x 2 L x N 2 ) = P( x N 1 )P( x 2 | x1 ) = P( x2 )即离散平稳信源输出的 N 长的随机序列之间彼此统计无依赖时，等式成立。【2.17】设有一个信源，它产生 0、1 序列的消息。它在任意时间而且不论以前

27、发生过什么符号，均按 P(0) = 0.4 ， P(1) = 0.6 的概率发出符号。（1） 试问这个信源是否是平稳的？N （3） 试计算 H ( X 4 ) 并写出 X 4 信源中可能有的所有符号。解：)|(log)( 12121 NNN xxxxPxxxP= LL（2） 试计算 )( 2XH 、 )|( 213 XXXH 及 )(lim XH N 。该信源任一时刻发出 0 和 1 的概率与时间无关，因此是平稳的，即该信源是离散平稳信源。其信息熵为H ( X ) = P( x) log P( x) = 0.971 比特/符号信源是平稳无记忆信源，输出的序列之间无依赖，所以H ( X 2 )

28、= 2H ( X ) = 1.942 比特/符号H ( X 3 | X 1 X 2 ) = H ( X ) = 0.971 比特/符号N N 1NH ( X 1 X 2 L X N ) = H ( X ) = 0.971比特/符号H ( X 4 ) = 4H ( X ) = 3.884 比特/符号X 4 信源中可能的符号是所有 4 位二进制数的排序，即从 00001111 共 16 种符号。【2.18】设有一信源，它在开始时以 P(a) = 0.6 ， P(b) = 0.3 ， P(c) = 0.1的概率发出 X 1 。如1 13 3如果 X 1 为 c 时，则 X 2 为 a、b 的概率为1

29、2，为 c 的概率为 0。而且后面发出 X i 的概率只与X i1 有关，又当 i 3 时， P( X i | X i 1 ) = P( X 2 | X 1 ) 。试用马尔克夫信源的图示法画出状态转移图，并计算此信源的熵 H 。解：信源为一阶马尔克夫信源，其状态转换图如下所示。a :13a :13b :13b :13a :12c :13b :12c :13根据上述状态转换图，设状态极限概率分别为 P(a) 、P(b) 和 P(c) ，根据切普曼柯尔莫哥洛夫方程有lim H N ( X ) = lim果 X 1 为 a 时，则 X 2 为 a、b、c 的概率为 ；如果为 b 时，则 X 2 为

30、a、b、c 的概率为 ； 1 1 11 1 1 3 3 2 1 1Q(a) + Q(b) + Q 3 ) = 1解得：Q(a) = Q(b) =38， Q(c) =14得此一阶马尔克夫的信息熵为：H = Q( Ei )H ( X | Ei ) = 1.439 比特/符号p【2.19】一阶马尔克夫信源的状态图如右图所示，p02p1p信源 X 的符号集为0,1,2 并定义 p = 1 p 。p2p（1） 求 信 源 平 稳 后 的 概 率 分 布 P(0) 、 P(1) 和p22pP(2) ；（2） 求此信源的熵 H ；22p2（3） 近似认为此信源为无记忆时，符号的概率分布等于平稳分布。求近似信

31、源的熵 H ( X )并与 H 进行比较；（4） 对一阶马尔克夫信源 p 取何值时， H 取最大值，又当 p = 0 和 p = 1时结果如何？解：根据切普曼柯尔莫哥洛夫方程，可得 p pp pP(2)2 2 p p2 2Q(a) = 3 Q(a) + 3 Q(b) + 2 Q(c)Q(b) = Q(a) + Q(b) + Q(c)Q(c) = Q(a) + Q(b) (3 cP(0) = pP(0) + 2 P(1) + 2 P(2)P(1) =P(0) + pP(1) +P(2) =P(0) +P(1) + pP(2)P(0) + P(1) + P(2) = 1解得： P(0) = P(1

32、) = P(2) =13该一阶马尔克夫信源的信息熵为：H = Q( Ei ) H ( X | Ei ) = p log p p log p + p 比特/符号当信源为无记忆信源，符号的概率分布等于平稳分布，此时信源的概率空间为： X P 0= 1 31132 1 3 此时信源的信息熵为 H ( X ) = log 3 = 1.585 比特/符号由上述计算结果可知： H ( X ) H () 。求一阶马尔克夫信源熵 H 的最大值， H = p log p p log p + p ，有dH dp= log2(1 p)p可得，当 p =23时， H 达到最大值，此时最大值为 log 3 = 1.58

33、5 比特/符号。当 p = 0 时， H = 0 比特/符号； p = 1时， H = 1比特/符号【2.20】黑白气象传真图的消息只有黑色和白色两种，即信源 X = 黑,白，设黑色出现的概率为 P(黑) = 0.3 ，白色出现的概率为 P(白) = 0.7 。（1） 假设图上黑白消息出现前后没有关联，求熵 H ( X ) ；（2） 假设消息前后有关联，其依赖关系为 P(白 |白) = 0.9 ，P(黑 |白) = 0.1 ，P(白 | 黑) = 0.2 ，P(黑 | 黑) = 0.8 ，求此一阶马尔克夫信源的熵 H 2 。（3） 分别求上述两种信源的冗余度，并比较 H ( X ) 和 H 2

34、 的大小，并说明其物理意义。解：如果出现黑白消息前后没有关联，信息熵为：H ( X ) = pi log pi = 0.881 比特/符号当消息前后有关联时，首先画出其状态转移图，如下所示。 设黑白两个状态的极限概率为 Q(黑) 和 Q(白) ，根据切普曼柯尔莫哥洛夫方程可得：Q(黑) = 0.8Q(黑) + 0.1Q(白)Q(黑) + Q(白) = 1解得：Q(黑) =13， Q(白) =23此信源的信息熵为：H = Q( Ei ) H ( X | Ei ) = 0.553比特/符号两信源的冗余度分别为： 1 = 1 H ( X )log 2= 0.119 1 = 1 H log 2= 0.

35、447结果表明：当信源的消息之间有依赖时，信源输出消息的不确定性减弱。就本题而言，当有依赖时前面已是白色消息，后面绝大多数可能是出现白色消息；前面是黑色消息，后面基本可猜测是黑色消息。这时信源的平均不确定性减弱，所以信源消息之间有依赖时信源熵小于信源消息之间无依赖时的信源熵，这表明信源熵正是反映信源的平均不确定的大小。而信源剩余度正是反映信源消息依赖关系的强弱，剩余度越大，信源消息之间的依赖关系就越大。Q(白) = 0.2Q(黑) + 0.9Q(白)第三章课后习题【3.1】 设信源 X x1 x2 通过一干扰信道，接收符号为 Y = y1 , y 2 ，信道传递概率如下图所示，求（1）信源 X 中事件 x1 和 x2 分别含有的自信息；（2）收到消息 y j ( j = 1,2) 后，获得的关于 xi (i = 1,2) 的信x15/61/6y1息量；x23/41/4y2（3）信源 X 和信源 Y 的信息熵；（4）信道疑义度 H ( X | Y ) 和噪声熵 H (Y | X ) ；（5）