《信息论》—基础理论与应用(傅祖芸)课后答案

第二章课后习 【2.1】设有 12 枚同值硬币，其中有一枚为假币。只知道假币的重量与真币的重量不同， 但不知究竟是重还是轻。现用比较天平左右两边轻重的方法来测量。为了在天平上称出哪 一枚是假币，试问至少必须称多少次？ 解：从信息论的角度看， “12枚硬币中，某一枚为假币”该事件发生的概率为 12 1 =P ； “假币的重量比真的轻，或重”该事件发生的概率为 2 1 =P ； 为确定哪一枚是假币，即要消除上述两事件的联合不确定性，由于二者是独立的，因 此有 24log2log12log =+=I 比特 而用天平称时，有三种可能性：重、轻、相等，三者是等概率的，均为 3 1 =P ，因此天 平每一次消除的不确定性为 3log=I 比特 因此，必须称的次数为 9.2 3log 24log 2 1 »= I I 次 因此，至少需称 3次。 【延伸】如何测量？分 3堆，每堆 4枚，经过 3次测量能否测出哪一枚为假币。 【2.2】同时扔一对均匀的骰子，当得知“两骰子面朝上点数之和为 2”或“面朝上点数之 和为 8”或“两骰子面朝上点数是 3和 4”时，试问这三种情况分别获得多少信息量？ 解： “两骰子总点数之和为 2”有一种可能，即两骰子的点数各为 1，由于二者是独立的， 因此该种情况发生的概率为 36 1 6 1 6 1 =´=P ，该事件的信息量为： 17.536log »=I 比特 “两骰子总点数之和为 8”共有如下可能：2和 6、3和 5、4和 4、5和 3、6和 2，概 率为 36 55 6 1 6 1 =´´=P ，因此该事件的信息量为： 85.2 5 36log »=I 比特 “两骰子面朝上点数是 3和 4”的可能性有两种：3和 4、4和 3，概率为 18 12 6 1 6 1 =´´=P ， 因此该事件的信息量为： 17.418log »=I 比特 【2.3】如果你在不知道今天是星期几的情况下问你的朋友“明天星期几？”则中含有 多少信息量？如果你在已知今天是星期四的情况下提出同样的问题，则答案中你能获得多 少信息量（假设已知星期一至星期日的顺序）？ 解： 如果不知今天星期几时问的话，答案可能有七种可能性，每一种都是等概率的，均为 7 1 =P ，因此此时从答案中获得的信息量为 807.27log ==I 比特 而当已知今天星期几时问同样的问题，其可能性只有一种，即发生的概率为 1，此时获得 的信息量为 0比特。 【2.4】居住某地区的女孩中有 25%是大学生，在女大学生中有 75%是身高 1.6米以上的， 而女孩中身高 1.6 米以上的占总数一半。假如我们得知“身高 1.6 米以上的某女孩是大学 生”的消息，问获得多少信息量？ 解： 设 A表示女孩是大学生， 25.0)( =AP ； B表示女孩身高 1.6米以上， 75.0)|( =ABP ， 5.0)( =BP “身高 1.6米以上的某女孩是大学生”的发生概率为 pan 打字机 pan 打字机 pan 高亮 pan 高亮 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2010，版权所有， 仅供试用。ഀ 375.0 5.0 75.025.0 )( )|()( )( )()|( =´=== BP ABPAP BP ABPBAP 已知该事件所能获得的信息量为 415.1 375.0 1log »=I 比特 【2.5】设离散无记忆信源 ú û ù ê ë é ==== =ú û ù ê ë é 8/14/14/18/3 3210 )( 4321 aaaa xP X ，其发出的消息为 （202120130213001203210110321010021032011223210），求 （1） 此消息的自信息是多少？ （2） 在此消息中平均每个符号携带的信息量是多少？ 解： 信源是无记忆的，因此，发出的各消息之间是互相独立的，此时发出的消息的自信息 即为各消息的自信息之和。根据已知条件，发出各消息所包含的信息量分别为： 415.1 3 8log)0( 0 ===aI 比特 24log)1( 1 ===aI 比特 24log)2( 2 ===aI 比特 38log)3( 3 ===aI 比特 在发出的消息中，共有 14个“0”符号，13个“1”符号，12个“2”符号，6个“3” 符号，则得到消息的自信息为： 81.8736212213415.114 »´+´+´+´=I 比特 45个符号共携带 87.81比特的信息量，平均每个符号携带的信息量为 95.1 45 81.87 ==I 比特/符号 注意：消息中平均每个符号携带的信息量有别于离散平均无记忆信源平均每个符号携带的 信息量，后者是信息熵，可计算得 å =-= 91.1)(log)()( xPxPXH 比特/符号 pan 高亮 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2010，版权所有， 仅供试用。ഀ 【2.6】如有 6行 8列的棋型方格，若有二个质点 A和 B，分别以等概率落入任一方格内， 且它们的坐标分别为（XA,YA）和（XB,YB），但 A和 B不能落入同一方格内。 （1） 若仅有质点 A，求 A落入任一个格的平均自信息量是多少？ （2） 若已知 A已落入，求 B落入的平均自信息量。 （3） 若 A、B是可分辨的，求 A、B同都落入的平均自信息量。 解： （1）求质点 A落入任一格的平均自信息量，即求信息熵，首先得出质点 A落入任一 格的概率空间为： ú ú û ù ê ê ë é =ú û ù ê ë é 48 1 48 1 48 1 48 1 48321 L L aaaa P X 平均自信息量为 58.548log)( ==AH 比特/符号 （2）已知质点 A已落入，求 B落入的平均自信息量，即求 )|( ABH 。 A已落入，B落入的格可能有 47个，条件概率 )|( ij abP 均为 47 1 。平均自信息量为 55.547log)|(log)|()()|( 48 1 47 1 ==-= åå = =i j ijiji abPabPaPABH 比特/符号 （3）质点 A和 B同时落入的平均自信息量为 13.11)|()()( =+= ABHAHABH 比特/符号 【2.7】从大量统计资料知道，男性中红绿色盲的发病率为 7%，女性发病率为 0.5%，如果 你问一位男同志：“你是否是红绿色盲？”，他的回答可能是“是”，也可能是“否”，问这 两个回答中各含有多少信息量？平均每个回答中含有多少信息量？如果你问一位女同志， 则答案中含有的平均自信息量是多少？ 解： 男同志红绿色盲的概率空间为： ú û ù ê ë é =ú û ù ê ë é 93.007.0 21 aa P X 问男同志回答“是”所获昨的信息量为： 836.3 07.0 1log »=I 比特/符号 问男同志回答“否”所获得的信息量为： 105.0 93.0 1log »=I 比特/符号 男同志平均每个回答中含有的信息量为 366.0)(log)()( =-= å xPxPXH 比特/符号 同样，女同志红绿色盲的概率空间为 ú û ù ê ë é =ú û ù ê ë é 995.0005.0 Y 21 bb P 问女同志回答“是”所获昨的信息量为： 64.7 005.0 1log »=I 比特/符号 问女同志回答“否”所获昨的信息量为： 31023.7 995.0 1log -´»=I 比特/符号 女同志平均每个回答中含有的信息量为 045.0)(log)()( =-= å xPxPYH 比特/符号 【2.8】设信源 ú û ù ê ë é =ú û ù ê ë é 17.016.017.018.019.02.0)( 654321 aaaaaa xP X ，求此信源的熵，并解释为什 么 6log)( >XH ，不满足信源熵的极值性。 解： 6log65.2)(log)()( >=-= å xPxPXH 原因是给定的信源空间不满足概率空间的完备集这一特性，因此不满足极值条件。 【 2.9】设离散无记忆信源 S 其符号集 },...,,{ 21 qaaaA = ，知其相应的概率分别为 ),...,,( 21 qPPP 。设另一离散无记忆信源 S ¢ ，其符号集为 S 信源符号集的两倍， }2,...,2,1,{ qiaA i ==¢ ，并且各符号的概率分布满足 qqqiPP qiPP ii ii 2,...,2,1 ,...,2,1)1( ++==¢ =-=¢ e e 试写出信源 S ¢的信息熵与信源 S的信息熵的关系。 解： )1,()( )(log)1log()1( logloglog)1()1log()1( log)1log()1( )(log)()( ee eeee eeeeee eeee -+= +----= -------= ----= -=¢ åååå åå å HSH SH PPPPPP PPPP xPxPSH iiiiii iiii 【2.10】设有一概率空间，其概率分布为 },...,,{ 21 qppp ，并有 21 pp > 。若取 e-=¢ 11 pp ， e+=¢ 22 pp ，其中 2120 pp -£< e ，而其他概率值不变。试证明由此所得新的概率空间的 熵是增加的，并用熵的物理意义加以解释。 解： 设新的信源为 X ¢，新信源的熵为： qqii ppppppppXH log)log()()log()(log)( 2211 --++----=-=¢ å Leeee 原信源的熵 qqii ppppppppXH loglogloglog)( 2211 ----=-= å L 因此有， 22112211 loglog)log()()log()()()( ppppppppXHXH --+++--=¢- eeee 令 )log()()log()()( 2211 xpxpxpxpxf +++--= ， çç è æ úû ù-Î 2 ,0 21 ppx ，则 0log)( 1 2 £ - + =¢ xp xpxf 即函数 )(xf 为减函数，因此有 )()0( eff ³ ，即 22112211 loglog)log()()log()( pppppppp +£+++-- eeee 因此 )()( XHXH ¢£ 成立。 【解释】 当信源符号的概率趋向等概率分布时，不确定性增加，即信息熵是增加的。 【2.11】试证明：若 1 1 =å = L i ip ， L m j j pq =å =1 ，则 ),,,(),,,,(),,,,,,,( 2112121121 L m LL LLLmL p q p q p qHpppppHqqqpppH KKKK += -- 并说明等式的物理意义。 解： ),,,(),,,,( )logloglog( loglogloglog logloglog loglogloglog logloglog log)(loglogloglog logloglog logloglogloglog loglogloglogloglog ),,,,,,,( 21 121 2211 112211 2 2 1 1 112211 2211 321112211 2211 112211 2211112211 21121 L m LL mLLL L m L m LLLL L LLLL L m m LL LLLL mm LmLLLL mm LLLLLL mmLL mL p q p q p qHpppppH p q p q p q p q p q p qp pppppppp p qq p qq p qq pppppppp qqqqqq pqqqqpppppppp qqqqqq pppppppppp qqqqqqpppppp qqqpppH KK K K K K K LK K K KK KK += ----+ -----= ---- -----= ---- +++++-----= ---- +-----= --------= - -- -- -- -- -- - 【意义】 将原信源中某一信源符号进行分割，而分割后的符号概率之和等于被分割的原符号的 概率，则新信源的信息熵增加，熵所增加的一项就是由于分割而产生的不确定性量。 【2.12】（1）为了使电视图像获得良好的清晰度和规定的适当的对比度，需要用 5×105 个 pan 高亮 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2010，版权所有， 仅供试用。ഀ 像素和 10 个不同亮度电平，求传递此图像所需的信息率（比特/秒）。并设每秒要传送 30 帧图像，所有像素是独立变化的，且所有亮度电平等概率出现。 （2）设某彩电系统，除了满足对于黑白电视系统的上述要求外，还必须有 30个不同的色 彩度，试证明传输这彩色系统的信息率要比黑白系统的信息率约大 2.5倍。 解： 每个像素的电平取自 10个不同的电平，每一个像素形成的概率空间为： ú ú û ù ê ê ë é =ú û ù ê ë é 10 1 10 1 10 1 1021 L L aaa P X 这样，平均每个像素携带的信息量为： 32.310log)( ==XH 比特/像素 现在所有的像素点之间独立变化的，因此，每帧图像含有的信息量为： 65 1066.110log105)()( ´=´´== XNHXH N 比特/帧 按每秒传输 30帧计算，每秒需要传输的比特数，即信息传输率为： 71098.4)(30 ´=´ NXH 比特/秒 除满足黑白电视系统的要求外，还需 30个不同的色彩度，不妨设每个色彩度等概率出 现，则其概率空间为： ú ú û ù ê ê ë é =ú û ù ê ë é 30 1 30 1 30 1 3021 L L bbb P Y 其熵为 30log 比特/符号，由于电平与色彩是互相独立的，因此有 300log)()()( =+= YHXHXYH 这样，彩色电视系统的信息率与黑白电视系统信息率的比值为 5.2 10log 300log )( )( »= XH XYH pan 高亮 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2010，版权所有， 仅供试用。ഀ 【2.13】每帧电视图像可以认为是由 3×105 个像素组成，所以像素均是独立变化，且每一 像素又取 128个不同的亮度电平，并设亮度电平等概率出现。问每帧图像含有多少信息量？ 若现有一广播员在约 10000 个汉字的字汇中选 1000 个来口述此电视图像，试问广播员描 述此图像所广播的信息量是多少（假设汉字是等概率分布，并且彼此无依赖）？若要恰当 地描述此图像，广播员在口述中至少需用多少汉字？ 解： 每个像素的电平亮度形成了一个概率空间，如下： ú ú û ù ê ê ë é =ú û ù ê ë é 128 1 128 1 128 1 12821 L L aaa P X 平均每个像素携带的信息量为： 7128log)( ==XH 比特/像素 每帧图像由 3×105个像素组成，且像素间是独立的，因此每帧图像含有的信息量为： 6101.2)()( ´== XNHXH N 比特/帧 如果用汉字来描述此图像，平均每个汉字携带的信息量为 29.1310000log)( ==YH 比特 /汉字，选择 1000字来描述，携带的信息量为 410329.1)()( ´== YNHYH N 比特 如果要恰当的描述此图像，即信息不丢失，在上述假设不变的前提下，需要的汉字个 数为： 51058.1 29.13 1106.2 )( )( ´»= YH XH N 字 【2.14】为了传输一个由字母 A、B、C 和 D 组成的符号集，把每个字母编码成两个二元 码脉冲序列，以 00代表 A，01代表 B，10代表 C，11代表 D。每个二元码脉冲宽度为 5ms。 （1） 不同字母等概率出现时，计算传输的平均信息速率？ pan 高亮 pan 高亮 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2010，版权所有， 仅供试用。ഀ （2） 若每个字母出现的概率分别为 5 1 =Ap ， 4 1 =Bp ， 4 1 =Cp ， 10 3 =Dp ，试计算传输的 平均速率？ 解： 假设不同字母等概率出现时，平均每个符号携带的信息量为 24log)( ==XH 比特 每个二元码宽度为 5ms，每个字母需要 2个二元码，则其传输时间为 10ms，每秒传送 100=n 个，因此信息传输速率为： 2002100)( =´== XnHR 比特/秒 当不同字母概率不同时，平均传输每个字母携带的信息量为 985.1 3 10log 10 34log 4 14log 4 15log 5 1)( =+++=XH 比特/符号 此时传输的平均信息速度为 210985.1)( ´== XnHR 比特/秒 【2.15】证明离散平稳信源有 )|()|( 12213 XXHXXXH £ ，试说明等式成立的条件。 解： )|( )|(log)|()( )|(log)|()( )|(log)()|( 23 2321321 21321321 213321213 1 2 3 1 2 3 XXH xxPxxxPxxP xxxPxxxPxxP xxxPxxxPXXXH X X X X X X = -£ -= -= åå å åå å ååå 根据信源的平稳性，有 )|()|( 1223 XXHXXH = ，因此有 )|()|( 12213 XXHXXXH £ 。 等式成立的条件是 )|()|( 23213 xxPxxxP = 。 【2.16】证明离散信源有 )()()()( 2121 NN XHXHXHXXXH +++£ LL ，并说明等式成立 的条件。 证明： )|()|()()( 12112121 -+++= NNN XXXXHXXHXHXXXH LLL 而 )( )(log)|()( )|(log)|()( )|(log)( )|( 1 2 1 1 2 1 1 2 121121 121121121 12121 121 N N X X X X NNN NN X X X X NNN X X X NNN NN XH xPxxxxPxxxP xxxxPxxxxPxxxP xxxxPxxxP XXXXH N N N N N = -£ -= -= åå å å åå å å åå å - - -- --- - - LLL LLLL LLL L 即 )()|( 212 XHXXH £ )()|( 3213 XHXXXH £ …… 代入上述不等式，有 )()()()( 2121 NN XHXHXHXXXH +++£ LL 等号成立的条件是： )()|( 121 NNN xPxxxxP =-L )()|( 12211 --- = NNN xPxxxxP L …… )()|( 212 xPxxP = 即离散平稳信源输出的 N长的随机序列之间彼此统计无依赖时，等式成立。 【2.17】设有一个信源，它产生 0、1序列的消息。它在任意时间而且不论以前发生过什么 符号，均按 4.0)0( =P ， 6.0)1( =P 的概率发出符号。 （1） 试问这个信源是否是平稳的？ （2） 试计算 )( 2XH 、 )|( 213 XXXH 及 )(lim XH NN ¥® 。 （3） 试计算 )( 4XH 并写出 4X 信源中可能有的所有符号。 解： pan 高亮 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2010，版权所有， 仅供试用。ഀ 该信源任一时刻发出 0和 1的概率与时间无关，因此是平稳的，即该信源是离散平稳 信源。其信息熵为 971.0)(log)()( =-= å xPxPXH 比特/符号 信源是平稳无记忆信源，输出的序列之间无依赖，所以 942.1)(2)( 2 == XHXH 比特/符号 971.0)()|( 213 == XHXXXH 比特/符号 971.0)()(1lim)(lim 21 === ¥®¥® XHXXXHN XH NNNN L 比特/符号 884.3)(4)( 4 == XHXH 比特/符号 4X 信源中可能的符号是所有 4位二进制数的排序，即从 0000~1111共 16种符号。 【2.18】设有一信源，它在开始时以 6.0)( =aP ， 3.0)( =bP ， 1.0)( =cP 的概率发出 1X 。如 果 1X 为 a时，则 2X 为 a、b、c 的概率为 3 1；如果为b时，则 2X 为 a、b、c 的概率为 3 1； 如果 1X 为 c时，则 2X 为 a、b的概率为 2 1，为 c的概率为 0。而且后面发出 iX 的概率只与 1-iX 有关，又当 3³i 时， )|()|( 121 XXPXXP ii =- 。试用马尔克夫信源的图示法画出状态 转移图，并计算此信源的熵 ¥H 。 解： 信源为一阶马尔克夫信源，其状态转换图如下所示。 3 1:a 3 1:b 3 1:c 3 1:b 3 1:a 3 1:c2 1:a 2 1:b 根据上述状态转换图，设状态极限概率分别为 )(aP 、 )(bP 和 )(cP ，根据切普曼—柯尔 莫哥洛夫方程有 ï ï ï î ï ï ï í ì =++ += ++= ++= 1)()()( )( 3 1)( 3 1)( )( 2 1)( 3 1)( 3 1)( )( 2 1)( 3 1)( 3 1)( cQbQaQ bQaQcQ cQbQaQbQ cQbQaQaQ 解得： 8 3)()( == bQaQ ， 4 1)( =cQ 得此一阶马尔克夫的信息熵为： 439.1)|()( == å¥ ii EXHEQH 比特/符号 【2.19】一阶马尔克夫信源的状态图如右图所示， 信源 X 的符号集为 }2,1,0{ 并定义 pp -= 1 。 （1） 求信源平稳后的概率分布 )0(P 、 )1(P 和 )2(P ； （2） 求此信源的熵 ¥H ； （3） 近似认为此信源为无记忆时，符号的概率分布等于平稳分布。求近似信源的熵 )(XH 并与 ¥H 进行比较； （4） 对一阶马尔克夫信源 p取何值时， ¥H 取最大值，又当 0=p 和 1=p 时结果如何？ 解： 根据切普曼—柯尔莫哥洛夫方程，可得 ï ï ï î ï ï ï í ì =++ ++= ++= ++= 1)2()1()0( )2()1( 2 )0( 2 )2( )2( 2 )1()0( 2 )1( )2( 2 )1( 2 )0()0( PPP PpPpPpP PpPpPpP PpPpPpP 0 1 2 p p p 2 p 2 p 2 p 2 p 2 p 2 p pan 高亮 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2010，版权所有， 仅供试用。ഀ 解得： 3 1)2()1()0( === PPP 该一阶马尔克夫信源的信息熵为： pppppEXHEQH ii +--== å¥ loglog)|()( 比特/符号 当信源为无记忆信源，符号的概率分布等于平稳分布，此时信源的概率空间为： ú ú û ù ê ê ë é =ú û ù ê ë é 3 1 3 1 3 1 210 P X 此时信源的信息熵为 585.13log)( ==XH 比特/符号 由上述计算结果可知： )()( ¥³ HXH 。 求一阶马尔克夫信源熵 ¥H 的最大值， pppppH +--=¥ loglog ，有 p p dp dH )1(2log -=¥ 可得，当 3 2 =p 时， ¥H 达到最大值，此时最大值为 585.13log = 比特/符号。 当 0=p 时， 0=¥H 比特/符号； 1=p 时， 1=¥H 比特/符号 【2.20】黑白气象传真图的消息只有黑色和白色两种，即信源 },{ 白黑=X ，设黑色出现的 概率为 3.0)( =黑P ，白色出现的概率为 7.0)( =白P 。 （1） 假设图上黑白消息出现前后没有关联，求熵 )(XH ； （2） 假设消息前后有关联，其依赖关系为 9.0)|( =白白P ， 1.0)|( =白黑P ， 2.0)|( =黑白P ， 8.0)|( =黑黑P ，求此一阶马尔克夫信源的熵 2H 。 （3） 分别求上述两种信源的冗余度，并比较 )(XH 和 2H 的大小，并说明其物理意义。 解： 如果出现黑白消息前后没有关联，信息熵为： 881.0log)( =-= å ii ppXH 比特/符号 当消息前后有关联时，首先画出其状态转移图，如下所示。 pan 高亮 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2010，版权所有， 仅供试用。ഀ 设黑白两个状态的极限概率为 )(黑Q 和 )(白Q ，根据切普曼—柯尔莫哥洛夫方程可得： ï î ï í ì =+ += += 1)()( )(9.0)(2.0)( )(1.0)(8.0)( 白黑 白黑白 白黑黑 QQ QQQ QQQ 解得： 3 1)( =黑Q ， 3 2)( =白Q 此信源的信息熵为： å ==¥ 553.0)|()(H ii EXHEQ 比特/符号 两信源的冗余度分别为： 119.0 2log )(11 =-= XH g 447.0 2log 11 =-= ¥Hg 结果表明：当信源的消息之间有依赖时，信源输出消息的不确定性减弱。就本题而言， 当有依赖时前面已是白色消息，后面绝大多数可能是出现白色消息；前面是黑色消息，后 面基本可猜测是黑色消息。这时信源的平均不确定性减弱，所以信源消息之间有依赖时信 源熵小于信源消息之间无依赖时的信源熵，这表明信源熵正是反映信源的平均不确定的大 小。而信源剩余度正是反映信源消息依赖关系的强弱，剩余度越大，信源消息之间的依赖 关系就越大。 第三章课后习题 【3.1】 设信源 ú û ù ê ë é =ú û ù ê ë é 4.06.0)( 21 xx xP X 通过一干扰信道，接收符号为 ],[ 21 yyY = ，信道传递概率如下图所示，求 （1）信源 X 中事件 1x 和 2x 分别含有的自信息； （2）收到消息 )2,1( =jy j 后，获得的关于 )2,1( =ixi 的信 息量； （3）信源 X 和信源Y的信息熵； （4）信道疑义度 )|( YXH 和噪声熵 )|( XYH ； （5）接收到消息Y后获得的平均互信息。 解： （1）信源 X 中事件 1x 和 2x 分别含有的自信息分别为： 737.06.0log )( 1log)( 1 1 =-== xP xI 比特 32.14.0log )( 1log)( 2 2 =-== xP xI 比特 （2）根据给定的信道以及输入概率分布，可得 8.0)|()()( 11 == å X ii xyPxPyP 2.0)|()()( 22 == å X ii xyPxPyP 所求的互信息量分别为： 059.0 24 25log 8.0 6/5log )( )|(log);( 1 11 11 ==== yP xyPyxI 比特 x1 x2 y1 y2 5/6 1/6 3/4 1/4 pan 高亮 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2010，版权所有， 仅供试用。ഀ 093.0 16 15log 8.0 4/3log )( )|(log);( 1 21 12 -==== yP xyPyxI 比特 263.0 6 5log 2.0 6/1log )( )|(log);( 2 12 21 -==== yP xyPyxI 比特 322.0 4 5log 2.0 4/1log )( )|(log);( 2 22 22 ==== yP xyPyxI 比特 （3）信源 X 以及Y的熵为： 971.04.0log4.06.0log6.0)(log)()( =--=-= å X xPxPXH 比特/符号 722.02.0log2.08.0log8.0)(log)()( =--=-= å Y yPyPYH 比特/符号 （4）信道疑义度 å å-= X Y yxPxyPxPYXH )|(log)|()()|( 而相关条件概率 )|( yxP 计算如下： 8 5 8.0 5.0 )( )()|( )( ),()|( 1 111 1 11 11 ==== yP xPxyP yP yxPyxP 8 3)|( 12 =yxP 2 1 2.0 6/6.0 )( )()|( )( ),()|( 2 112 2 21 21 ==== yP xPxyP yP yxPyxP 2 1)|( 22 =yxP 由此计算出信道疑义度为： 9635.0 2 1log 4 1 8 3log 4 34.0 2 1log 6 1 8 5log 6 56.0)|( =úû ù êë é +-úû ù êë é +-=YXH 比特/符号 噪声熵为： 符号比特 /7145.0 4 1log 4 1 4 3log 4 34.0 6 1log 6 1 6 5log 6 56.0 )|(log)|()()|( = úû ù êë é +-úû ù êë é +-= -= å xyPxyPxPXYH （5）接收到信息Y后获得的平均互信息为： 0075.0)|()();( =-= YXHXHYXI 比特/符号 【3.2】 设 8个等概率分布的消息通过传递概率为 p的 BSC进行传送，8个消息 相应编成下述码字： M1=0000，M2=0101，M3=0110，M4=0011 M5=1001，M6=1010，M7=1100，M8=1111 试问： （1）接收到第一个数字 0与M1之间的互信息； （2）接收到第二个数字也是 0时，得到多少关于M1的附加互信息； （3）接收到第三个数字仍为 0时，又增加了多少关于M1的互信息； （4）接收到第四个数字还是 0时，再增加了多少关于M1的互信息。 解： 各个符号的先验概率均为 8 1 （1）根据已知条件，有 pxyPyPMyP ======= )0|0()0000|0()|0( 11111 2 1)|0()()0( 1 === å iM ii MPMPyP 因此接收到第一个数字 0与M1之间的互信息为： pp yP MyPyMI log1 2/1 log )0( )|0(log)0;( 1 11 11 +=== = == 比特 （2）根据已知条件，有 2 21121 )0000|00()|00( pyyPMyyP ==== [ ] 4 1242 8 1)|00()()00( 2221 =++=== å ppppMPMPyyP iM ii 因此接收到第二个数字也是 0时，得到多少关于M1的互信息为： pp yyP MyyPyyMI log22 4/1 log )00( )|00( log)00;( 2 21 121 211 +=== = == 比特/符号 得到的附加信息为： pyMIyyMI log1)0;()00;( 11211 +==-= 比特/符号 （3）根据已知条件，有 3 3211321 )000|000()|000( pyyyPMyyyP ==== [ ] 8 133 8 1)|000()()000( 3223321 =+++=== å ppppppMPMPyyyP iM ii 因此接收到第三个数字也是 0时，得到多少关于M1的互信息为： pp yyyP MyyyPyyyMI log33 8/1 log )000( )|000( log)000;( 3 321 1321 3211 +=== = == 此时得到的附加信息为： pyyMIyyyMI log1)00;()000;( 2113211 +==-= 比特/符号 （4）根据已知条件，有 4 432114321 )0000|0000()|0000( pyyyyPMyyyyP ==== [ ]42244321 68 1)|0000()()0000( ppppMPMPyyyyP iM ii ++=== å 因此接收到第四个符号为 0时，得到的关于M1的互信息为 ( ) ( )4224 4224 4 4321 14321 3211 6loglog43 6 8 1 log )0000( )|0000(log)0000;( ppppp pppp p yyyyP MyyyyPyyyMI ++-+= ++ = = = == 此时得到的附加信息为 ( )4224321143211 6loglog)000;()000;( pppppyyyMIyyyyMI ++-==-= 【3.3】 设二元对称信道的传递矩阵为 ú ú ú û ù ê ê ê ë é 3 2 3 1 3 1 3 2 （1）若 P(0)=3/4，P(1)=1/4，求 )(XH ， )|( YXH ， )|( XYH 和 );( YXI ； （2）求该信道的信道容量及其达到信道容量时的输入概率分布。 解： （1）根据已知条件，有 符号比特 /811.0 4 1log 4 1 4 3log 4 3 )(log)()( = --= -= å X ii xPxPXH 12 7 3 1 4 1 3 2 4 3)|0()()0( =´+´==== å X xyPxPyP 12 5)|1()()1( ==== å X xyPxPyP 7 6 12/7 3 2 4 3 )0( )0|0()0()0|0( = ´ = = === === yP xyPxPyxP 7 1)0|1( === yxP 5 3 12/5 3 1 4 3 )1( )0|1()0()1|0( = ´ = = === === yP xyPxPyxP 5 2)1|1( === yxP 符号比特 /918.0 3 2log 3 2 3 1log 3 1 4 1 3 1log 3 1 3 2log 3 2 4 3 )|(log)|()()|( = ÷ ø ö ç è æ +-÷ ø ö ç è æ +-= -= å å X Y xyPxyPxPXYH pan 高亮 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2010，版权所有， 仅供试用。ഀ 符号比特 /749.0 5 2log 3 2 7 1log 3 1 4 1 5 3log 3 1 7 6log 3 2 4 3 )|(log)|()()|( = ÷ ø ö ç è æ +-÷ ø ö ç è æ +-= -= å å X Y yxPxyPxPYXH 062.0)|()();( =-= YXHXHYXI 比特/符号 （2）此信道是对称信道，因此其信道容量为： 082.0) 3 1, 3 2(1)(1 =-=-= HpHC 比特/符号 根据对称信道的性质可知，当 2 1)1()0( == PP 时，信道的传输率 );( YXI 达到 信道容量。 【3.4】 设有一批电阻，按阻值分 70%是 2kΩ，30%是 5kΩ；按功耗分 64%是 1/8W， 其余是 1/4W。现已知 2kΩ 阻值的电阻中 80%是 1/8W。问通过测量阻值可以平 均得到的关于瓦数的信息量是多少？ 解： 根据已知条件，设电阻的阻值为事件 X，电阻的功耗为事件 Y，则两事件的 概率空间为： ú û ù ê ë é W=W= =ú û ù ê ë é 3.07.0 52 21 kxkx P X ， ú û ù ê ë é == =ú û ù ê ë é 36.064.0 4/18/1 21 WyWy P Y 给定条件为 8.0)|( 11 =xyP ， 2.0)|( 12 =xyP ，而 )|(*3.08.0*7.0)|()()|()()(64.0 212121111 xyPxyPxPxyPxPyP +=+== )|(*3.02.0*7.0)|()()|()()(36.0 222221212 xyPxyPxPxyPxPyP +=+== 解得： 15 4)|( 21 =xyP ， 15 11)|( 22 =xyP ( ) 7567.0 15 11log 15 11 15 4log 15 4*3.02.0log2.08.0log8.0*7.0)|( =÷ ø ö ç è æ +-+-=XYH 186.0)|()();( =-= XYHYHYXI 比特/符号 【3.5】 若 X 、Y和Z是三个随机变量，试证明： （1） )|;();()|;();();( ZYXIZXIYZXIYXIYZXI +=+= （2） )|()|()|;()|;( YZXHZXHZXYIZYXI -== （3） 0)|;( ³ZYXI 当且仅当 ),,( YZX 是马氏链时等式成立。 证明： （1） );()|;( )( )|(log),,( )|( )|(log),,( )( )|( )|( )|(log),,( )( )|(log),,();( ,,,, ,, ,, YXIYZXI xP yxPzyxP yxP yzxPzyxP xP yxP yxP yzxPzyxP xP yzxPzyxPYZXI ZYXZYX ZYX ZYX += += ÷÷ ø ö çç è æ *= = åå å å 同理， )|;();();( ZYXIZXIYZXI += （2） )|;( )|( )|(log),,( )()( )()(log),,( )|( )|(log),,()|;( ,, ,, ,, ZXYI zyP xzyPzyxP yzPxzP zPxyzPzyxP zxP yzxPzyxPZYXI ZYX ZYX ZYX = = = = å å å )|()|( )|(log),,()|(log),,( )|( )|(log),,()|;( ,,,, ,, YZXHZXH yzxPzyxPzxPzyxP zxP yzxPzyxPZYXI ZYXZYX ZYX -= +-= = åå å （3） 0 )( )()(log )|( )|(),,(log )|( )|(log),,()|;( ,, ,, ,, = = £ =- å å å ZYX ZYX ZYX zP yzPxzP yzxP zxPzyxP yzxP zxPzyxPZYXI 等 号 成 立 当 且 仅 当 )|( )|( )()( )()(1 )|( )|( xzyP zyP zPxyzP yzPxzP yzxP zxP === ， 即 )|()|( xzyPzyP = ，即 ),,( YZX 是马氏链。 【3.6】若有三个离散随机变量，有如下关系： ZYX =+ ，其中 X 和Y相互统计 独立，试证明： （1） )()( ZHXH £ ，当且仅当Y是常量时等式成立； （2） )()( ZHYH £ ，当且仅当 X 为常量时等式成立； （3） )()()()( YHXHXYHZH +££ ，当且仅当 X ，Y中任意一个为常量时 等式成立； （4） )()();( YHZHZXI -= ； （5） )();( ZHZXYI = ； （6） )();( XHYZXI = ； （7） )()|;( YHXZYI = ； （8） )|()|()|;( ZYHZXHZYXI == 。 证明： 当 ZYX =+ 时 ， 有 î í ì += +¹ = yxz yxz xyzP 1 0 )|( ， 即 0)|( =XYZH ， 而 );()()|( ZXYIZHXYZH -= ，因此 )();( ZHZXYI = 。 )( )( ),(log),( )( ),(log),( )|(log),()|( YH xP yxPyxP xP zxPzxP xzPzxPXZH = -= -= -= å å å 而 )|()();( XZHZHZXI -= ，因此 )()();( YHZHZXI -= 。 根据互信息的性质，有 0);( ³ZXI ，因此 )()( YHZH ³ 成立，而当 X 为常量 时，Z和 X 的概率分布相同，因此上述不等式中的等号成立。 同理， )()( XHZH ³ 成立。 由 于 )()|()()|()();( ZHZXYHXYHXYZHZHZXYI =-=-= ， 而 0)|( ³ZXYH ，因此 )()( XYHZH £ 成立。 根 据 条 件 ， 有 î í ì += +¹ = yxz yxz yzxP 1 0 )|( ， 因 此 0)|( =YZXH ， 而 )|()();( YZXHXHYZXI -= ，因此 )();( XHYZXI = 。 )()|()|()|()|;( YHXYHXZYHXYHXZYI ==-= )|( )|()|( )|;( )|( )|()|()|;( ZYH XZYHZYH ZXYI ZXH YZXHZXHZYXI = -= = = -= 【3.7】 设 X ，Y是两个相互统计独立的二元随机变量，其取“0”或“1”的概率为 等概率分布。定义另一个二元随机变量Z，而且 XYZ = （一般乘积），试计算： （1） )(XH ， )(YH ， )(ZH ； （2） )(XYH ， )(XZH ， )(YZH ， )(XYZH ； （3） )|( YXH ， )|( ZXH ， )|( ZYH ， )|( XZH ， )|( YZH ； （4） )|( YZXH ， )|( XZYH ， )|( XYZH ； （5） );( YXI ， );( ZXI ， );( ZYI ； （6） )|;( ZYXI ， )|;( ZXYI ， )|;( YXZI ， )|;( XYZI ； （7） );( ZXYI ， );( YZXI ， );( XZYI ； 解： 由于 X 和Y是相互独立的等概率分布的随机变量，因此有 1)()( == YHXH 比特/符号 而符号Z的概率空间为： ú ú û ù ê ê ë é =ú û ù ê ë é 4 1 4 3 10 P Z ，因此 811.0) 4 1, 4 3()( == HZH 比特/符号 2)()()( =+= YHXHXYH 比特/符号 根据已知条件可得 2 1)0()0,0( ===== xPzxP ， 0)1,0( === zxP 4 1)0,1()0,1( ====== yxPzxP ， 4 1)1,1()1,1( ====== yxPzxP 1 )0( )0,0()0|0( = = == === xP xzPxzP ， 0 )0( )0,1()0|1( = = == === xP xzPxzP 2 1 )1( )1,0()1|0( = = == === xP xzPxzP ， 2 1 )1( )1,1()1|1( = = == === xP xzPxzP 5.0 2 1log 4 1 2 1log 4 11log 2 1)|(log),()|( =---=-= å xzPzxPXZH 比特/符号 5.1)|()()( =+= XZHXHXZH 比特/符号 同理， 5.0)|( =YZH 比特/符号， 5.1)|()()( =+= YZHYHYZH 比特/符号 由于 î í ì ¹ = = xyz xyz xyzP 0 1 )|( ，因此 0)|( =XYZH 比特/符号 2)|()()( =+= XYZHXYHXYZH 比特/符号 1)()()|( =-= YHXYHYXH 比特/符号 689.0)()()|( =-= ZHXZHZXH 比特/符号 689.0)()()|( =-= ZHYZHZYH 比特/符号 5.05.12)()()|( =-=-= YZHXYZHYZXH 比特/符号 同理， 5.0)|( =XZYH 比特/符号 0)|()();( =-= YXHXHYXI 比特/符号 311.0)|()();( =-= ZXHXHZXI 比特/符号 311.0)|()();( =-= ZYHYHZYI 比特/符号 189.05.0689.0)|()|()|;( =-=-= YZXHZXHZYXI 比特/符号 189.0)|;()|;( == ZYXIZXYI 比特/符号 5.0)|()|()|;( =-= XYZHYZHYXZI 比特/符号 5.0)|()|()|;( =-= XYZHXZHXYZI 比特/符号 811.0)|()();( =-= XYZHZHZXYI 比特/符号 5.05.01)|()();( =-=-= YZXHXHYZXI 比特/符号 5.0)|()();( =-= XZYHYHXZYI 比特/符号 【3.8】 有一个二元信道，其信道如右图所示。设该信 道以 1500 个二元符号/秒的速度传输输入符号，现有一 消息序列共有 14000 个二元符号，并设在这消息中 2 1)1()0( == PP 。问从信息传输的角度来考虑，10 秒内 能否将这消息序列无失真地传送完。 解： 0 1 0 1 0.98 0.02 0.0 2 0.98 pan 高亮 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2010，版权所有， 仅供试用。ഀ 该信道的信道矩阵为 ú û ù ê ë é 98.002.0 02.098.0 ，信道容量为： 8586.0)02.0,98.0(2log =-= HC 比特/符号 10秒内可以传输的最大信息量为： 410288.1108586.01500 ´=´´ 比特 而 14000个符号中所含有的信息量为：14000比特，因此从信息的角度来考虑， 10秒钟内不可能把上述 14000个符号传输完。 【3.9】 求下图中信道的信道容量及其最佳的输入概率分布。 1/31/6 1/2 1/3 1/6 1/6 1/21/3 1/3 1/6 1/2 解：两个信道的信道矩阵分别如下： ú ú ú û ù ê ê ê ë é 3 1 6 1 3 1 6 1 6 1 3 1 6 1 3 1 ， ú ú ú ú ú ú û ù ê ê ê ê ê ê ë é 2 1 6 1 3 1 3 1 2 1 6 1 6 1 3 1 2 1 可见，两个信道均是对称信道，信道容量分别为： 0817.0) 6 1, 3 1, 6 1, 3 1(4log1 =-= HC 比特/符号 126.0) 3 1, 6 1, 2 1(3log2 =-= HC 比特/符号 输入的最佳分布是等概率分布。 【3.10】 求下列两个信道的信道容量，并加以比较 pan 高亮 pan 高亮 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2010，版权所有， 仅供试用。ഀ （1） ú û ù ê ë é -- -- eee eee 2 2 pp pp （2） ú û ù ê ë é -- -- eee eee 20 02 pp pp 解：这两个信道均是准对称信道，当输入符号等概率时，平均互信息达到信道容 量，具体如下： （1）该准对称信道的信道容量为： )log()()log()( 21 2log)21( )2,,(2log2 2 21log 2 21 2 21log 2 21 )2,,()}(max{1 eeee e e eeeee eeee eee --+--+ - -= ---- -- - -- -= ---= pppp ppH ppHYHC （2）该准对称信道的信道容量为： e eeeee e e eeeeeee eeee eee 2 2)log()()log()( 21 2log)21( )2,,(loglog 2 21log 2 21 2 21log 2 21 )2,,()}(max{ 1 2 += +--+--+ - -= ----- -- - -- -= ---= C pppp ppH ppHYHC 【3.11】 求下图中信道的信道容量及其最佳的输入概率分布，并求出 0=e 和 2 1 =e 时的信道容量C。 1 2 1 2 1-ε 1-ε ε ε 0 01 解： 该信道的信道矩阵如下： ú ú ú û ù ê ê ê ë é - - ee ee 10 10 001 pan 高亮 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2010，版权所有， 仅供试用。ഀ 该信道既非对称信道，也非准对称信道，因此根据一般信道容量的计算公式，有 åå = )|(log)|()|( ijijjij abPabPabP b 即 ï î ï í ì +--==-+ +--=+- = eeeebeeb eeeeebbe b log)1log()1()1( log)1log()1()1( 0 32 32 1 解得： 01 =b ， eeeebb log)1log()1(32 +--== 而信道容量 ( )ee b ee --+= = å 1)1(21log 2log jC 信道的输出符号概率为： ee b ee - - -+ == 11 )1(21 12)( 1 CbP ee ee b ee ee - - - -+ - == 1 1 2 )1(21 )1(2)( 2 CbP ee ee b ee ee - - - -+ - == 1 1 3 )1(21 )1(2)( 3 CbP 而 )()( 11 aPbP = )()()1()( 322 aPaPbP ee +-= )()1()()( 323 aPaPbP ee -+= 可得： ee ee --+ = 11 )1(21 1)(aP ee ee ee ee - - -+ - = 1 1 2 )1(21 )1()(aP ee ee ee ee - - -+ - = 1 1 3 )1(21 )1()(aP 当 0=e 时， ( ) 3log)1(21log 1 =-+= - ee eeC ，信道为一一对应信道； 当 2 1 =e 时， 2log 2 121log =÷÷ ø ö çç è æ ÷ ø ö ç è æ+=C 。 【3.12】 试证明 )(XH 是输入概率分布 )(xP 的上凸函数。 证明： å-= X xPxPXH )(log)()( 设存在两个概率分布 )(1 xP 和 )(2 xP ，目标是要证明 ))()(())(())(( 2121 xPxPHxPHxPH qqqq +£+ 证明过程如下： ( ) 0 1 )( )()(log1 )( )()(log )( )(log)( )( )(log)( )(log)()()(log)()(log)( ))()(())(())(( 2 2 1 1 2 2 1 1 212211 2121 = ÷÷ ø ö çç è æ -+÷÷ ø ö çç è æ -£ += ++--= +-+ åå åå ååå xP xPxPe xP xPxPe xP xPxP xP xPxP xPxPxPxPxPxPxP xPxPHxPHxPH qq qq qqqq qqqq 【3.13】 从平均互信息的表达式证明，当信道和信源都是无记忆时，有 );();( YXNIYXI NN = 证明：设 ( ) Nkkkk aaa L 21 =a , ( ) Nhhhh bbb L 21 =b ，按照给定信道和信源均是无记忆， 有 )()()()()( 2121 NN kkkkkkk aPaPaPaaaPP LL ==a )|()|()|()|()|( 22112121 NNNN khkhkhkkkhhhkh abPabPabPaaabbbPP LLL ==ab )()()( )|()|()|()()()( )|()()( 21 221121 N NNN hhh khkhkhkkk khkh PbPbP aPabPabPaPaPaP PPP L LL = = = abab );();();( )( )|( log)( )( )|( log)( )()()( )|()|()|( log)( )( )|( log)( )|(log)()(log)( )|()();( 2211 1 11 21 2211 NN h kh ji h kh ji hhh khkhkh ji j ij ji ijjijj NNNNN YXIYXIYXI bP abP P bP abP P PbPbP abPabPabP P P P P PPPP XYHYHYXI N NN N NN +++= ++= = = +-= -= åå å å åå L L L L baba ba b ab ba abbabb 【3.14】 证明：若 ),,( ZYX 是马氏链，则 ),,( XYZ 也是马氏链。 证明： 如果 ),,( ZYX 是马氏链，则有 )|()|( yzPxyzP = ，即 )( )( )( )( yP yzP xyP xyzP = 因此有 )( )( )( )( yP xyP yzP xyzP = ，即 )|()|( yxPyzxP = ，即 ),,( XYZ 也是马氏链。 【3.15】 把n个二元对称信道串接起来，每个二元对称信道的错误传递概率为 p。 证明这 n个串接信道可以等效于一个二元对称信道，其错误传递概率为 ])21(1[ 2 1 np-- ，并证明 0);(lim 0 =¥® nn XXI ，设 0¹p 或 1，信道的串接如下图所 示。 证明： 当 1=n 时，错误概率 ))21(1( 2 1 pp --= 成立； 假设 kn = 成立，即 k个串接信道的错误概率为 ])21(1[ 2 1 kp-- ； 当 1+= kn 时，其错误概率为： ])21(1[ 2 1 )21()21( 2 1 2 1 )21( 2 )21( 22 1 ])21(1[ 2 )21( 22 ])21(1[ 2 11])21(1[ 2 1 1+--= -+--= -+--= ---+--= ÷ ø ö ç è æ ---+-- k kk kk kk kk p ppp pppp pppppp pppp 当 ¥®n 时，错误概率近似为 2 1，总信道矩阵为 ú ú ú û ù ê ê ê ë é 2 1 2 1 2 1 2 1 ，此时不论输入为何分 布，输出均为等概率分布。其互信息为： 0)|(1)|()();(lim 000 =-=-=¥® XXHXXHXHXXI nnnnn 比特/符号 【3.16】 若有两个串接的离散信道，它们的信道矩阵都是 ú ú ú ú ú û ù ê ê ê ê ê ë é 0100 00 2 1 2 1 1000 1000 并设第一个信道的输入符号 },,,{ 4321 aaaaX Î 是等概率分布，求 );( ZXI 和 );( YXI 并加以比较。 解： 串接后的信道矩阵为： ú ú ú ú ú û ù ê ê ê ê ê ë é = ú ú ú ú ú û ù ê ê ê ê ê ë é ú ú ú ú ú û ù ê ê ê ê ê ë é 00 2 1 2 1 1000 0100 0100 0100 00 2 1 2 1 1000 1000 0100 00 2 1 2 1 1000 1000 [ ] [ ] úû ù êë é= ú ú ú ú ú û ù ê ê ê ê ê ë é = 2 1 4 1 8 1 8 1 0100 00 2 1 2 1 1000 1000 )()()()()()()()( 43214321 aPaPaPaPbPbPbPbP 符号比特 /5.1 2 1log 2 1 4 1 2 1log 2 1 4 1 2 1log 2 1 4 1log 4 1 8 1log 8 1 8 1log 8 1 )|()();( = ´-´-----= -= XYHYHYXI [ ] [ ] úû ù êë é= ú ú ú ú ú û ù ê ê ê ê ê ë é = 4 1 2 1 8 1 8 1 00 2 1 2 1 1000 0100 0100 )()()()()()()()( 43214321 aPaPaPaPcPcPcPcP 符号比特 /5.1 2 1log 2 1 4 1 2 1log 2 1 4 1 2 1log 2 1 4 1log 4 1 8 1log 8 1 8 1log 8 1 )|()();( = ´-´-----= -= XZHZHZXI 可见， );();( YXIZXI = 。 第四章课后习题 【4.1】 设有一连续随机变量，其概率密度函数为 ïî ï í ì £= 其他值0 2 cos)( pxxAxp 又有 1)(2 2 =ò- p p dxxp ，试求这随机变量的熵。 解： ò ò òò ò --= --= --= -= - xdxxAAA xdxxAxAA xdxxAAdxxA dxxpxpXh coslogcoslog2 coslogcossinlog coslogcoslogcos )(log)()( 2 2 p p 而 òò ò òò -++= -++= -= xdxexdxe xdxxe xdxexdxx sin)sin1ln(log 2 1sin)sin1ln(log 2 1 sin)sin1ln()sin1ln(log 2 1 sinsin1lnlogcoslogcos 2 22ln2 sin sin1 sin1)sin1ln()sin1(sin)sin1ln( 2 2 -= + + -++=+ òò - xdx xxxxdx p p 22ln2 sin sin1 sin1)sin1ln()sin1( )sin1()sin1ln(sin)sin1ln( 2 2 -= - - ----= ---=- ò òò - xd x xxx xdxxdx p p 因此有 AeAAA eAeAAA eAAAXh 2log2log2 2lnlog2log2log2 )22ln222ln2(log 2 log2)( -+-= -+-= -+---= 而 1)(2 2 =ò- p p dxxp ，即 2 1 =A ，因此 eeeXh log1log11log 2 1log)( =-+=-+-= 【4.2】计算连续随机变量 X 的差熵 （1） 指数概率密度函数 xexp ll -=)( ， 0,0 >³ lx （2） 拉普拉斯概率密度函数， xexp ll -= 2 1)( ， 0, >¥<<¥- lx 解： （1） l l l l lll ll lll lll ll e e dtetet deeee dxeedxe dxee dxxpxpXh xxx xxx xx log loglog loglnloglog lnloglog loglog log )(log)()( 0 1 0 = +-= -+-= +-= --= -= -= ò ò òò ò ò --¥- --- -- （2） l l lll ll ll lll ll ll e e dxeedxe dxee dxee dxxpxpXh xxx xx xx 2log log2log log 2 1log 2 1log 2 1log 2 1 )(log)()( 00 0 = += --= -= -= -= òò ò ò ò ¥ --¥ - ¥ -- ¥ ¥- -- 注：（2）题直接借用了（1）的结论。 【4.3】设有一连续随机变量，其概率密度函数为： î í ì ££ = 其他值0 0 )( 2 axbx xp 试求这随机变量的熵。又若 )0(1 >+= KKXY ， XY 22 = ，试分别求出 1Y 和 2Y 的 熵 )( 1Yh 和 )( 2Yh 。 解： babaeba xdxxebb dxbxbx dxxpxpXh a a loglog 3 2log 9 2 lnlog2log log )(log)()( 33 0 2 0 22 --= --= -= -= ò ò ò 由于 1)( =ò dxxp ，因此 33 =ba ，因此 3logloglog 3 2)( -+= aeXh 当 )0(1 >+= KKXY 时， 1 1 = ¶ ¶ Y X ，因此 3logloglog 3 2)(]1[log)()( 1 -+==-= aeXhEXhYh 当 XY 22 = 时， 2 1 1 = ¶ ¶ Y X ，因此 2 3logloglog 3 2)(] 2 1[log)()( 1 aeXhEXhYh +==-= 【4.4】设给定两随机变量 1X 和 2X ，它们的联合概率密度为 2 21 2 2 2 1 2 1)( xx exxp + - = p ¥<<¥- 21, xx 求随机变量 211 XXY += 的概率密度函数，并计算变量Y的熵 )(Yh 。 解： )()( 2 1 2 1 2 1)( 2122221 2 2 2 1 2 2 2 1 xpxpeeexxp xxxx === -- + - ppp 因此 211 XXY += 也是一个高斯分布的随机变量，其均值为 0，方差为 2，即 4 21 2 2 1)( y exxp - = p 因此其差熵为 eeYh y psp 4log2 12log 2 1)( 2 == 【4.5】设一连续消息通过某放大器，该放大器输出的最大瞬时电压b，最小瞬时 电压为 a。若消息从放大器中输出，问放大器输出消息在每个自由度上的最大熵 是多少？又放大器的带宽为F，问单位时间内输出最大信息量是多少？ 解： 该问题等价于取值受限的随机变量的最大熵，根据差熵的极值性，当等概率 分布时其差熵最大，即 )log()( abYh -= 如果放大器的带宽为F，则取样率为 F2 ，单位时间内输出的最大信息量为 )log(2 abF - 比特/秒 【4.6】有一信源发出恒定宽度，但不同幅度的脉冲，幅度值处在 1a 和 2a 之间， 此信源连至某信道，信道接收端接收脉冲的幅度 y处在 1b 和 2b 之间。已知随机变 量 X 和Y的联合概率密度函数 ))(( 1)( 1212 bbaa xyp -- = 试计算 )(Xh ， )(Yh ， )(XYh 和 );( YXI 。 解： 12 1212 1 ))(( 1 ),()( aa dy bbaa dyyxpxp - = -- = = ò ò 同理， 12 1)( bb yp - = 。 因此 )log()(log)()( 12 aadxxpxpXh -=-= ò )log()(log)()( 12 bbdyypypYh -=-= ò )log()log(),(log),()( 1212 bbaadxdyyxpyxpXYh -+-=-= ò 0)()()();( =-+= XYhYhXhYXI 【4.7】在连续信源中，根据差熵、条件差熵和联合差熵的定义，证明 （1） )()|( XhYXh £ ，当且仅当 X 和Y统计独立时等号成立； （2） )()()()( 2121 NN XhXhXhXXXh +++£ LL ，当且仅当 NXXX L21 彼此统计 独立时等式成立。 证明： （1） )( )(log),( )(log)|()( )|(log)|()()( Xh dxdyxpyxp dxxpyxpdyyp dxyxpyxpdyypXYh = -= -£ -= ò ò ò ò ò 等号成立当且仅当 )()|( xpyxp = ，即 )()(),( ypxpyxp = ，因此仅当 X 和Y 统计 独立时等号成立。 （2）根据条件概率密度的相关公式，有 )|()|()|()()( 12121312121 -++++= NNN XXXXhXXXhXXhXhXXXh L 根据（1）的结论，条件差熵小于差熵，因此有 )()()()( 2121 NN XhXhXhXXXh +++£ LL 等号成立当且仅当 )()|( 212 xpxxp = )()|( 3213 xpxxxp = …… )()|( 121 NNN xpxxxxp =-L 即 )()()( 2121 xpxpxxp = )()()()( 321321 xpxpxpxxxp = …… )()()()( 2121 NN xpxpxpxxxp LL = 【4.8】设连续随机变量 X ，已知 0³X ，其平均值受限，即数学期望为 A，试求 在此条件下获得的最大熵的最佳分布，并求出最大熵。 解： 给定条件如下： 1)( =ò dxxp Adxxxp =ò )( 目标：求 ò- dxxpxp )(log)( 的最大值。 构造函数 ( )ò òòò ++-= ++-= dxxxpxpxpxp dxxxpdxxpdxxpxpxpF )()()(log)( )()()(log)())(( ml ml 欲使 0 )( ))(( = xdp xpdF ，只需 ( ) 0 )( )()()(log)( = ++- xdp xxpxpxpxpd ml 即可，因此有 0log)(log =++-- xexp ml exxp log2)( -+= ml 根据 1)( =ò dxxp ， Adxxxp =ò )( ，可得 12 log =ò -+ dxexml Þ elog2 --= lm Adxxxp =ò )( Þ ( )2log 1 e A -=m 因此 ( ) ( ) 2log2 2log1)( e A x e A xp - = ，此时 ( ) ( )22 loglog1log )(log)()( ee A dxxpxpXh +÷ ø ö ç è æ-= -= ò 【4.9】 N 维连续型随机序列 NXXX L21 ，有概率密度 )( 21 NXXXp L 以及 2)][( iii mXE s== 。证明：当随机序列的分量各自达到正态分布并彼此统计独立 时熵最大。最大熵为 N Ne N /122 2 2 1 )(2log2 sssp L 证明： )()()()( 2121 NN XhXhXhXXXh +++£ LL 等号成立当且仅当各分量统计独立。 而对于任何一个分量而言，当 2)][( iii mXE s== 时，高斯分布的差熵最大，为 22log 2 1)( ii eXh sp= 因此原序列差熵的最大值为： ( ) ú û ù ê ë é = +++= N N NN eN eeeXXXh 1 22 2 2 1 22 2 2 121 2log 2 2log 2 12log 2 12log 2 1)( sssp spspsp L LL 【4.10】N维连续型随机序列 NXXX L21 ，其各分量幅度分别受限为 ],[ ii ba 。证 明：当随机序列的分量各自达到均匀分布并彼此统计独立时熵最大。最大熵为 Õ = - N i ii ab 1 )(log 证明： )()()()( 2121 NN XhXhXhXXXh +++£ LL 等号成立当且仅当各分量统计独立。 而对于任何一个分量而言，当幅度分别受限为 ],[ ii ba 时，均匀分布的差熵最大， 为 ( )iii abXh -= log)( 因此原序列差熵的最大值为： ( ) ( ) ( ) ( )Õ = -= -++-+-= N i ii NNN ab abababXXXh 1 221121 log logloglog)( LL 【4.11】 设 NXXX L21 都是互相独立的正态分布的随机变量，其方差分别为 2 1s ， 2 2s ，…, 2 Ns ，均值分别为 Nmmm ,,, 21 L 。试证明 NXXXY +++= L21 仍是正态 随机变量，其均值为 å= imm ，方差 å= 22 iss 。 证明： 设 1X 和 2X 是相互独立的正态分布的随机变量，其均值为 im ，方差为 2 is 。设 212 XXY += ，根据已知条件，有 212 11 XXY XX += = 因此有 )()( )()(),( 10 11 ),( ),(),( 121 2121 21 2 2 2 1 1 2 1 1 2121 xypxp xpxpxxp xxp X Y X X X Y X X xxpyxp -= == = ¶ ¶ ¶ ¶ ¶ ¶ ¶ ¶ = 因此有 ( ) ( ) ( ) ( ) ò ò ò ò þ ý ü î í ì -- - - -= þ ý ü î í ì -- - þ ý ü î í ì - -= -= = 12 2 2 212 2 1 2 11 21 12 2 2 212 2 2 1 2 11 1 1121 1212 22 exp 2 1 2 exp 2 1 2 exp 2 1 )()( )()( dxmxymx dxmxymx dxxypxp dxyxpyp sssps sspssp 而 ( ) ( ) ( ) ( ) ( ) ( ){ } ( ) ( ) ( ){ } ( ) 2 2122 2 2 1 2 2 2 2 1 2 212 2 12 2 1 12 2 2 1 2 21222 2 2 1 2 2 2 1 2 2 2 2 1 2 212 2 12 2 1 12 2 2 1 2 2 2 1 22 2 1 2 2 2 1 2 1 2 2 2 2 2 1 2 212 2 12 2 1 1 2 12 2 2 1 22 2 1 2 2 2 1 2 2 2 1 2 1 2 2 2 212 2 12 2 11 2 1 2 2 2 12 2 2 1 2 212 2 1 2 11 2 22 2 2 1 2 2 2 212 2 1 2 11 2 2 2 212 2 1 2 11 )( )(2 111 2 1 )(11 2 1 2211 2 1 22 2 1 2 1 2 1 22 mmymymx mmymymx myymmymxx myymmmymxx mxymx mxymx mxymx -- + -÷÷ ø ö çç è æ + -- +÷÷ ø ö çç è æ +-= ïþ ï ý ü ïî ï í ì -- + +÷÷ ø ö çç è æ + -- +÷÷ ø ö çç è æ +-= þ ý ü î í ì ÷÷ ø ö çç è æ + -+ +÷÷ ø ö çç è æ + -- +÷÷ ø ö çç è æ +-= -+++--++-= --+--= þ ý ü î í ì -- + - -= -- - - - ssss sss ss ss ss ss sss ss ss sss ss sss ss sssssssss ss ss ss ss ss 所以 ( ) ( ) ( ) þý ü î í ì + -- - + = ÷÷ ø ö çç è æ +þ ý ü î í ì -- + -= ïþ ï ý ü ïî ï í ì ÷÷ ø ö çç è æ + -- +÷÷ ø ö çç è æ +- þ ý ü î í ì -- + -= þ ý ü î í ì -- - - -= ò ò )(2 )(exp 2 1 11 2 1 )( )(2 1exp 2 1 11 2 1exp )( )(2 1exp 2 1 22 exp 2 1)( 2 2 2 1 2 212 2 2 2 1 2 2 2 1 2 2122 2 2 121 1 2 2 2 2 1 2 212 2 12 2 1 12 2 2 1 2 2122 2 2 121 12 2 2 212 2 1 2 11 21 2 ssssp ss p sssps ss sss ss sssps sssps mmy mmy dxmymx mmy dxmxymxyp 因此， 212 XXY += 是均值为 21 mm + ，方差为 2 2 2 1 ss + 的高斯分布，同理， 3213 XXXY ++= ，……， NXXXY +++= L21 均为高斯分布，因此 NXXXY +++= L21 是正态随机变量，其均值为 å= imm ，方差 å= 22 iss 【4.12】设某连续信道，其特性如下： 22 3/) 2 1( 3 1)|( a pa xy exyp -- = 而且输入变量 X 的概率密度函数为 22 4/ 2 1)( a pa xexp -= 试计算： （1） 信源的熵 )(Xh ； （2） 平均互信息 );( YXI 。 解： 22 22 22/ 2 4/ 22 1 2 1)( a a ap pa ·- - · = = x x e exp 可见， X 为均值为 0，方差为 22a 的正态分布，其差熵为 22 4log 2 122log 2 1)( apap eeXh == ï ï þ ï ï ý ü ï ï î ï ï í ì - ÷ ø ö ç è æ - -= ï ï þ ï ï ý ü ï ï î ï ï í ì +÷ ø ö ç è æ - -= þ ý ü î í ì -+ -= ï ï þ ï ï ý ü ï ï î ï ï í ì ÷ ø ö ç è æ - --= = 2 2 2 2 2 2 2 2 2 2 22 2 2 2 2 2 2 43 2 1 exp 32 1 3 4 3 2 1 exp 32 1 12 444exp 32 1 3 2 1 4 exp 32 1 )|()(),( aapa apa apa aapa y yx yyx xyyx xy x xypxpyxp 而 2 2 22 2 2 2 2 2 2 2 4 4 3 2 1 4 3 2 1 4 2 2 2 2 2 2 2 1 2 1 3 2 1 2 1 32 1 43 2 1 exp 32 1),()( a a a a a a pa pa apapa aapa y t y yx y yx y e dtee yx deedxee dxy yx dxyxpyp - - - ÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ - - -÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ - - - = = ÷÷ ÷ ÷ ø ö çç ç ç è æ - == ï ï þ ï ï ý ü ï ï î ï ï í ì - ÷ ø ö ç è æ - -== ò òò òò 因此Y是均值为 0，方差为 22a 的高斯分布，其差熵为 22 4log 2 122log 2 1)( apap eeYh =´= 而条件熵为 dxdy xy yxpe dxdyeyxpdxdyyxp dxdyeyxp dxdyxypxypxpXYh xy xy ò òò ò ò ÷ ø ö ç è æ - += --= ÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ -= -= ÷ ø ö ç è æ - - ÷ ø ö ç è æ - - 2 2 3 2 1 3 2 1 3 2 1 ),(log3log log),( 3 1log),( 3 1log),( )|(log)|()()|( 2 2 2 2 a ap pa pa a a 而 ò ò ò òò òò ÷ ø ö ç è æ - -- - ÷ ø ö ç è æ - - +÷ ø ö ç è æ - - +- - - ÷ ø ö ç è æ - - ÷ ø ö ç è æ -= ÷ ø ö ç è æ -= ÷ ø ö ç è æ -=÷ ø ö ç è æ -= ÷ ø ö ç è æ - = ÷ ø ö ç è æ - dyexydxe dxdyexy dxdyexydxdyexy dxdye xy dxdy xy yxp xy x x xy xxy xxyy y yx 2 2 2 2 2 2 2 2 2 2 2 2 22 2 2 2 2 3 2 1 2 4 4 43 2 1 2 4 3 4 3 2 1 2 4 3 2 4 43 2 1 22 2 2 2 2 1 36 1 2 1 36 1 2 1 36 1 2 1 36 1 32 1 3 2 1 3 2 1 ),( aa aa aa aa pa pa papa paaa 而 3 23 3 2 12 23 2 1 2 3 2 3 33 3 2 1 3 2 1 33 2 1 2 2 2 2 ap a aa aa a a = = ÷÷ ÷ ÷ ø ö çç ç ç è æ - ÷÷ ÷ ÷ ø ö çç ç ç è æ - =÷ ø ö ç è æ - ò òò - ÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ - -÷ ø ö ç è æ - - dtet xy de xy dyexy t xy xy 因此 2 1 2 4 1 4 13 2 3 36 1 2 1 36 1 3 2 1 ),( 2 2 2 2 2 2 2 2 434 4 3 2 1 2 4 42 2 = ·= =·= ÷ ø ö ç è æ -= ÷ ø ö ç è æ - òò ò òò -- ÷ ø ö ç è æ - -- pa pa pa ap pa paa aa aa dxedxe dyexydxedxdy xy yxp xx xy x 2 2 2 3log 2 1 log 2 13log 3 2 1 ),(log3log)|( ap ap a ap e e dxdy xy yxpeXYh = += ÷ ø ö ç è æ - += ò 因此平均互信息为： 21.0 3 4log 2 1 3log 2 14log 2 1 )|()();( 22 = = -= -= apap ee XYHYHYXI 注：该题推导过程中引用的相关积分公式： （1） p2 2 2 1 =ò ¥ ¥- - dte t （2） 2 22 p=ò ¥ ¥- - dtet t 【4.13】试证明两连续随机变量之间的平均互信息 );( YXI 是输入随机变量 X 的 概率密度函数 )(xp 的I型凸函数。 证明： ò ò ò = = dxdy dxxypxp xypxypxp dxdy yp xypxypxpYXI )|()( )|(log)|()( )( )|(log)|()();( 设存在 X 的两个概率密度 )(1 xp 和 )(2 xp ，参数 10 ££ q ，目标证明： ))(())(())()(( 2121 xpIxpIxpxpI qqqq ++³+ 过程如下： òò ò òò += - += +-++ dxdy yp ypxypxpdxdy yp ypxypxp dxdy yp xypxypxp dxdy yp xypxypxpdxdy yp xypxypxp xpxpIxpIxpI )( )(log)|()( )( )(log)|()( )( )|(log)|()( )( )|(log)|()( )( )|(log)|()( ))()(())(())(( 2 2 1 1 2 2 1 1 2121 qq qq qqqq 而 0 )()|(log )( )(),(log )( )(log),( )( )(log)|()( 1 1 1 1 1 1 1 = = £ = ò ò òò dxdyypyxp dxdy yp ypyxp dxdy yp ypyxpdxdy yp ypxypxp 同理， 0 )( )(log)|()( 2 2 £ò dxdyyp ypxypxp ，因此有 ))(())(())()(( 2121 xpIxpIxpxpI qqqq ++³+ 【4.14】试证明多维连续无记忆信道的充要条件为 Õ = = N i ii xypxyp 1 )|()|( 证明： （1）充分性。 )|()|()|( )|( 121211212211 2121 -= NNNNN NN yyyxxxypyxxxypxxxyp xxxyyyp LLLLL LL 而 )|( )|( )|( )|( )|( )|( )|( )|( )|( )( )()|( 1 1 1 1 1 21121 1 21121 21121 12121 12121 12121 NN N i ii N i ii N N i ii N i ii NNNN N i ii NN NNN NN NNN NNN xyp xyp xyp dyxyp xyp dyxxxyyyyp xyp xxxyyyp xxxyyyyp yyyxxxp yyyyxxxpyyyxxxyp = == = = = Õ Õ òÕ Õ ò Õ - = = = = - = - - - - - LL LL LL LL LL LL 同理 )|()|( 11221211 ---- = NNNNN xypyyyxxxyp LL …… )|()|( 221212 xypyxxxyp N =L )|()|( 11211 xypxxxyp N =L 因此该信道是无记信道。 （2）必要性。 根据无记信道的性质，有 )|()|( 11221211 ---- = NNNNN xypyyyxxxyp LL …… )|()|( 221212 xypyxxxyp N =L )|()|( 11211 xypxxxyp N =L 而 )|()|()|( )|( 121211212211 2121 -= NNNNN NN yyyxxxypyxxxypxxxyp xxxyyyp LLLLL LL 因此有 Õ = = N i ii xypxyp 1 )|()|( 【4.15】试证明连续信源 X 的相对熵 )(Xh 是概率密度 )(xp 的I型凸函数。 证明： 设存在 X 的两个概率密度 )(1 xp 和 )(2 xp ，参数 10 ££ q ，目标证明： ))(())(())()(( 2121 xphxphxpxph qqqq ++³+ 过程如下： ( ) òò òòò += ++--= +-++ dx xp xpxpdx xp xpxp dxxpxpxpdxxpxpdxxpxp xpxphxphxph )( )(log)( )( )(log)( )(log)()()(log)()(log)( ))()(())(())(( 2 2 1 1 212211 2121 qq qqqq qqqq 而 0 1log )( )()(log )( )(log)( 1 1 1 1 = = £ òò dxxp xpxpdx xp xpxp 同理， 0 )( )(log)( 2 2 £ò dxxp xpxp 因此 0))()(())(())(( 2121 £+-++ xpxphxphxph qqqq 【4.16】设信道输入是连续型随机序列 NXXX L21 ，输出也是连续型随机序列 NYYY L21 ，信道传递概率密度为 )|( xyp 。试证明： （1）当信源是无记忆时，有 å³ );();( 2121 iiNN YXIYYYXXXI LL （2）当信道是无记忆时，有 å£ );();( 2121 iiNN YXIYYYXXXI LL 证明： ò ò = = )( )|(log),( )( )|(log),( );( 21 2121 2121 21 2121 2121 2121 N NN NN N NN NN NN yyyp xxxyyypyyyxxxp xxxp yyyxxxpyyyxxxp YYYXXXI L LL LL L LL LL LL ò ò ò å = = = NN N NN NN NN N NN NN NN i ji ji ii dydydydxdxdx ypypyp xypxypxypyyyxxxp dydydydxdxdx xpxpxp yxpyxpyxpyyyxxxp dydydydxdxdx xp yxp yxp YXI LL L L LL LL L L LL LL 2121 21 2211 2121 2121 21 2211 2121 2121 )()()( )|()|()|(log),( )()()( )|()|()|(log),( )( )|( log),( );( （1）当信源无记忆时，即 )()()()( 2121 NN xpxpxpxxxp LL = 1 )()|()|(log ),( )()|()|(),(log )|( )|()|()|(),(log )|( )|()|()|(log),( );();( 112111 11 11 2111 11 11 2121 2211 2121 11 2121 2211 2121 2121 = = = £ ÷÷ ø ö çç è æ = - ò ò ò ò å NNNNN NN NN NNN NN NN NN NN NN NN NN NN NN NNii dydydxdxyyypyxpyxp dydydxdx yyxxp yyypyxpyxpyyxxp dydydxdx yyyxxxp yxpyxpyxpyyyxxxp dydydxdx yyyxxxp yxpyxpyxpyyyxxxp YYYXXXIYXI LLLL LL LL LL LL LL LL L LL LL LL L LL LL 等号成立当且仅当 )|()|()|()|( 21212211 NNNN yyyxxxpyxpyxpyxp LLL = 。 当 )|()|()|( 1111 NNNN xypxypxxyyp LLL = 时，根据信源的无记忆性，即 )()()|()|()()|( 111111 NNNNNN xpxpxypxypxxpxxyyp LLLLL = 即 ),(),(),( 1111 NNNN yxpyxpyyxxp LLL = （1） 两边对各自由度积分得 )()()( 11 NN ypypyyp LL = （2） （1）式两边除以（2）式两边得 )|()|()|()|( 21212211 NNNN yyyxxxpyxpyxpyxp LLL = 因此等号成立当且仅当连续信道无记忆。 （2）当信道无记忆时，即 )|()|()|( 1111 NNNN xypxypxxyyp LLL = 时， 0 )( )()()(),(log )( )()()(log),( );();( 11 21 21 2121 11 21 21 2121 2121 = £ = - ò ò å NN N N NN NN N N NN iiNN dydydxdx yyyp ypypypyyyxxxp dydydxdx yyyp ypypypyyyxxxp YXIYYYXXXI LL L L LL LL L L LL LL 等号成立当且仅当 )()()( 11 NN ypypyyp LL = 。 当 )()()()( 2121 NN xpxpxpxxxp LL = ，根据信道的无记忆性，有 )|()|()|( 1111 NNNN xypxypxxyyp LLL = 因此有 ),(),(),( 1111 NNNN yxpyxpyyxxp LLL = 两边对自由度 Nxx L1 求和得 )()()( 11 NN ypypyyp LL = 即（2）式等号成立的条件是信源为无记忆信源。 【4.17】在图片传输中，每帧约 61025.2 ´ 个像素，为了能很好地重现图像，需分 16个亮度电平，并假设亮度电平等概率分布。试计算每秒钟传送 30帧图片所需 信道的带宽（信噪功率比为 30dB）。 解： 每秒需要传输的信息量为： 86 107.216log301025.2 ´=´´´ 比特/秒 信道的信噪比为 30dB，即 30log10 10 = N S P P ，即 1000= N S P P 因此信道容量为 8107.2 1log ´= ÷÷ ø ö çç è æ += N S P PWC 可推得带宽为 7 8 1071.2 1001log 107.2 ´= ´ =W Hz 【4.18】设在平均功率受限高斯加性波形信道中，信道带宽为 3kHz，又设（信 号功率+噪声功率）/噪声功率=10dB。 （1） 试计算该信道传送的最大信息率（单位时间）； （2） 若功率信噪比降为 5dB，要达到相同的最大信息传输率，信道带宽应为多 少？ 解： （1） 根据已知条件有， 10log10 10 = + N NS P PP 因此 9= N S P P 3 3 1096.9 10log103 1log ´= ´= ÷÷ ø ö çç è æ += N S P PWC 即最大信息率为 31096.9 ´ 比特/秒。 （2）如果功率信噪比降为 5dB，即 5log10 10 = + N NS P PP ，即 10=+ N NS P PP ，因此 10log 2 1 10log 1log W W P P WC N S = = ÷÷ ø ö çç è æ += 为达到以前的信息传输率，因此带宽应为原来的 2倍，即 3106´=W Hz 第五章课后习题 【5.1】某信源按 4 3)0( =P ， 4 1)1( =P 的概率产生统计独立的二元序列。 （1）试求 0N ，使当 0NN > 时有 01.005.0)( )( £ þ ý ü î í ì ³- SH N IP ia 式中， )(SH 是信源的熵。 （2）试求当 0NN = 时典型序列集 NGe 中含有的信源序列个数。 解： （1）该信源的信源熵为 811.0)(log)()( =-= å ii spspSH 比特/符号 自信息的方差为 4715.0 811.04log 4 1 3 4log 4 3 )()]([)]([ 222 22 = -+= -= SHsIEsID ii 根据等长码编码定理，我们知道 de a -£ þ ý ü î í ì ³- 1)( )( SH N IP i 根据给定条件可知， 05.0=e ， 99.0=d 。而 [ ] 2 )( e d N sID i= 因此 [ ] 5.190 99.0*05.0 4715.0)( 220 ==³ de isIDN 取 1910 =N 。 pan 高亮 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2010，版权所有， 仅供试用。ഀ （2）e 典型序列中信源序列个数取值范围为： ])([])([ 22)1( ee ed +- <<- SHNN SHN G 代入上述数值得 451.164351.145 2201.0 <<´ NGe 【5.2】有一信源，它有六个可能的输出，其概率分布如下表所示，表中给出了 对应的码 A、B、C、D、E和 F。 表 5.2 消息 )( iaP A B C D E F 1a 1/2 000 0 0 0 0 0 2a 1/4 001 01 10 10 10 100 3a 1/16 010 011 110 110 1100 101 4a 1/16 011 0111 1110 1110 1101 110 5a 1/16 100 01111 11110 1011 1110 111 6a 1/16 101 011111 111110 1101 1111 011 （1） 求这些码中哪些是惟一可译码； （2） 求哪些码是非延长码（即时码）； （3） 求对所有惟一可译码求出其平均码长 L。 解： （1）上述码字中，A为等长码，且为非奇异码，因此码 A为惟一可译码； 码 B 中，根据惟一可译码的判断方法，可求得其尾随后缀集合为 }11111,1111,111,11,1{ ，且其中任何后缀均不为码字，因此码 B是惟一可译码。码 C 为逗点码，因此码 C 为惟一可译码；码 D不是惟一可译码，因为其尾随后缀 pan 高亮 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2010，版权所有， 仅供试用。ഀ 集合中包含 0，而 0又是码字；码 E的尾随后缀集合为空集，因此码 E是惟一可 译码；码 F不是惟一可译码，因为其尾随后缀集合中包含 0，而 0又是码字，因 此 F不是惟一可译码。 （2）码 A、C、E是即时码（非延长码） （3）码 A的平均码长为 3；码 B 的平均码长为 2.125；码 C 的平均码长为 2.125；码 F的平均码长为 2。 【5.3】证明定理 5.6，若存在一个码长为 qlll ,,, 21 K 的惟一可译码，则一定存在具 有相同码长的即时码。 证明： 如果存在码长为 qlll ,,, 21 K 的惟一可译码，则 qlll ,,, 21 K 必定满足如下不等式 1 1 £å = - q i lir 而如果码长 qlll ,,, 21 K 满足上述不等式，根据 Kraft不等式构造即时码的方法，可 以构造出码长为 qlll ,,, 21 K 的即时码，具体构造过程略，参照课本相关定理。 【5.4】设信源 ú û ù ê ë é =ú û ù ê ë é 621 621 )( ppp sss sP S L L 将此信源编码为 r元惟一可译变长码（即码符号集 },,2,1{ rX K= ），其对应的码 长为 )3,2,3,2,1,1(),,,( 621 =lll K ，求 r值的下限。 解： 如果要构造出惟一可译变长码，则相关码长必须满足 1 1 £å = - q i lir ，代入上式有 2 1321 £++ --- rrr 当 2=r 时，上述不等式不成立；当 3=r 时，成立。因此 r值的下限为 3。 【5.5】若有一信源 ú û ù ê ë é =ú û ù ê ë é 2.08.0)( 21 ss sP S 每秒钟发出 2.66 个信源符号。将此信源的输出符号送入某一个二元信道中进行 传输（假设信道是无噪无损的），而信道每秒钟只传递两个二元符号。试问信源 不通过编码能否直接与信道连接？若通过适当编码能否中在信道中进行无失真 传输？若能连接，试说明如何编码并说明原因。 解： 如果不通过编码，即信道的两个码符号对应两个信源符号，而信道传输码符 号的速度小于信源发出信源符号的速度，因此势必会造成信源符号的堆积，因此 不通过编码是无法将信源与信道直接连接。 信源平均每秒发出的信息量为 921.1)(log)(*66.2)(*66.2 =-= å sPsPSH 比特/秒 而该信道的信道容量为 1比特/符号，平均每秒能够传输的最大信息量为 2比特， 因此通过编码可以实现二者的连接。 若要连接，需要对扩展信源的信源符号进行编码，目的是使送入信道的信息 量小于信道每秒能接收的最大信息量（或使每秒钟编码后送入信道的码符号个数 必须小于信道所能接受的最大码符号个数），具体编码方法将在第八章进行。 【5.6】设某无记忆二元信源，概率 1.0)1(1 == Pp ， 9.0)0(0 == Pp ，采用下述游 程编码：第一步，根据 0的游程长度编成 8个码字，第二步，将 8个码字变 换成二元变长码，如下表所示。 表 5.6 信源符号序列 中间码 二元码字 1 01 001 0001 00001 000001 0000001 00000001 00000000 s0 s1 s2 s3 s4 s5 s6 s7 s8 1000 1001 1010 1011 1100 1101 1110 1111 0 （1） 试问最后的二元变长码是否是否是惟一可译码； （2） 试求中间码对应的信源序列的平均长度 1L ； （3） 试求中间码对应的二元变长码码字的平均长度 2L ； （4） 计算比值 12 / LL ，解释它的意义，并计算这种游程编码的编码效率； 解： （1）该码是非延长码，因此肯定是惟一可译码； （2）由于信源本身是无记忆的，因此各信源符号的概率如下表所示。 信源符号序列 概率 中间码 二元码字 1 01 001 0001 00001 000001 0000001 00000001 00000000 0.1 0.09 0.081 0.0729 0.06561 0.059049 0.0531441 0.04782969 0.43046721 s0 s1 s2 s3 s4 s5 s6 s7 s8 1000 1001 1010 1011 1100 1101 1110 1111 0 因此信源序列的平均长度为 695328.5)(1 == å ii lspL （3）中间码对应的二元变长码码长为 708598.2)(2 == å ii lspL （4） 4756.0 1 2 = L L ，反应了每个信源符号需要的二元码符号数。 平均每个信源符号的信息量为 469.01.0log1.09.0log9.0)( =--=SH 编码效率为 986.0 / )( 12 == LL SH h 第六章课后习题 【6.1】设有一离散信道，其信道传递矩阵为 ú ú ú ú ú ú û ù ê ê ê ê ê ê ë é 2 1 6 1 3 1 3 1 2 1 6 1 6 1 3 1 2 1 并设 2 1)( 1 =xP ， 4 1)()( 32 == xPxP ，试分别按最小错误概率准则与最大似然译码 准则确定译码规则，并计算相应的平均错误概率。 解： 假设输入符号集和输出符号集分别为 },,{ 321 xxx 和 },,{ 321 yyy 。 按照最大似然译码规则，选择如下： 33 22 11 )( )( )( xyF xyF xyF = = = 平均错误概率为： 2 1 6 1 3 1 2 1 6 1 3 1 2 1 )|()( * = ÷ ø ö ç è æ ++÷ ø ö ç è æ += = å å -X yxY ijiE j xyPxPP 对应的 如果需要按照最小错误概率译码，需要首先求出其联合概率矩阵： ú ú ú ú ú ú û ù ê ê ê ê ê ê ë é 8 1 24 1 12 1 12 1 8 1 24 1 12 1 6 1 4 1 pan 高亮 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2010，版权所有， 仅供试用。ഀ 最小错误概率译码规则应如下： 33 12 11 )( )( )( xyF xyF xyF = = = 此时错误概率为： 24 11 24 1 12 1 12 1 8 1 24 1 12 1 ),( )|()( * * = +++++= = = å å å å - - X yxY ji X yxY ijiE j j yxP xyPxPP 对应的 对应的 【6.2】计算码长 5=n 的二元重复码的译码错误概率。假设无记忆二元对称信道 中正确传递概率为 p，错误传递概率为 pp -=1 。此码能检测出多少错误？又能 纠正多少错误。若 01.0=p ，译码错误概率是多大？ 解： 将 0和 1编成 00000和 11111后，当传输过程中产生 1位至 4位错误时均可 检测出，但产生 5位错误却无法检测出，同时，如果输入等概率分布，当传输过 程中存在 1位错误以及 2位错误时，可以自动纠正。此时的错误概率为： 错 3位的概率为： 2335 ppC ； 错 4位的概率为： ppC 445 ； 错 5位的概率为： 555 pC 因此，译码错误概率为： 555 5 44 5 233 5 1002961.1 -´=++ pCppCppC 【6.3】设某二元码为 }00111,10010,01001,11100{=C （1） 计算此码的最小距离 mind ； （2） 计算此码的码率R，假设码字等概率分布； pan 高亮 pan 高亮 pan 高亮 pan 高亮 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2010，版权所有， 仅供试用。ഀ （3） 采用最小距离译码准则，试问接收序列 10000，01100和 00100应译成什 么码字？ （4） 此码能纠正几位码元的错误？ 解： （1） 此码字的最小距离 3min =d ； （2） 此码字的码率 5 2log == n MR 比特/码符号； （3） 采用最小距离译码，10000应译成 10010；01100应译成 11100；00100 译成 11100、00111均可； （4） 由于 1123min +´==d ，因此此码能纠正 1位码元的错误。 【 6.4】设无记忆二元对称信道的正确传递概率为 p ,错误传递概率为 ppp <<-=1 。令长度为 n的M 个二元码字 )( 21 niiii aaa L=a ，其中 }1,0{Î ki a （码 字为等概率分布），接收的二元序列为 )( 21 njjjj bbb L=b ， }1,0{Î kj b 。试证明：采 用最小距离译码准则可使平均译码错误概率 EP 达到最小，并且 å --= i DnD E jj pp M P **11 证明： 构造函数 xnx ppxf -=)( ，有 0lnln)( <-=¢ -- ppppppxf xnxxnx 因此该函数为减函数，即当 ijj DD £* 时，有 DijnDDnD pppp ijjj -- ³** 。因此按照 最小距离选择的译码规 则 *)( ab =jF ，使 ijj DD £* 成立，必然会有 DijnDDnD pppp ijjj -- ³** ，即 EE PP ¢³ 其中 EP 为最小距离译码得到的正确概率，而 EP ¢则是其他译码得到的正确概率， 进一步可以得到运用最小距离译码得到的错误概率为最小。 【6.5】对于离散无记忆强对称信道，信道矩阵为： ú ú ú ú ú ú ú ú û ù ê ê ê ê ê ê ê ê ë é - --- -- - - --- - = p r p r p r p r p r pp r p r p r p r pp P 1 111 11 1 1 111 1 L MMMM L L 试证明对于此信道，最小距离译码准则等价于最大似然译码准则。 证明： 当信道发送符号序列为 ( ) niiii aaa L 21 =a ，接收符号序列为 ( ) njjjj bbb L 21 =b 时，信道矩阵中的条件概率为： ( ) ( ) ( ) ( ) ( ) ),( ),( 1 1 ||| |)|( 2211 2121 ji ji nn nn Dn D ijijij iiijjjij p r p abPabPabP aaabbbPP ba ba ab --÷ ø ö ç è æ - = = = L LL 按照最大似然译码规则，选择 *)( ab =jF ，使 )|()|( * ijj PP abab > 成立，即 ( ) ( ) ),( ),( ),( ),( 1 1 1 1 * * ji ji j j Dn D Dn D p r pp r p ba ba ba ba -- -÷ ø ö ç è æ - >-÷ ø ö ç è æ - 因此有 ( ) ),(),( ),(),( * * 1 1 jij jij DD DD p r p baba baba - - ->÷ ø ö ç è æ - 一般情况下， 2 11 >-= pp ，因此有 ),(),( * jij DD baba £ 成立，而这即为最 小距离译码规则。 【6.6】某一信道，其输入 X 的符号集为 }1, 2 1,0{ ，输出Y的符号集为 }1,0{ ，信道 矩阵为 ú ú ú ú ú ú û ù ê ê ê ê ê ê ë é = 10 2 1 2 1 01 P 现有四个消息的信源通过这信道传输（消息等概率出现）。若对信源进行编码， 我们选这样一种码 )} 2 1, 2 1,,{(: 21 xxC ， 10或Îix （ 2,1=i ） 其码长为 4=n ，并选取这样的译码规则 ) 2 1, 2 1,,(),,,( 214321 yyyyyyf = （1） 这样编码后信道的信息传输率等于多少？ （2） 证明在选用的译码规则下，对所有码字 0=EP 。 解： 输入码字不同的个数共有 4个，因此编码后信道的信息传输率为 2 1 4 4log ==R 比特/码符号 2 1 2 100 2 1 2 101 2 1 2 110 2 1 2 111 0000 1/4 0 0 0 0001 1/4 0 0 0 0010 1/4 0 0 0 0011 1/4 0 0 0 0100 0 1/4 0 0 0101 0 1/4 0 0 0110 0 1/4 0 0 0111 0 1/4 0 0 1000 0 0 1/4 0 1001 0 0 1/4 0 1010 0 0 1/4 0 1011 0 0 1/4 0 1100 0 0 0 1/4 1101 0 0 0 1/4 1110 0 0 0 1/4 1111 0 0 0 1/4 可以看出，通过上述译码，对每一个输出都有一个输入与其对应，通过计算， 可得其平均错误概率 0=EP 。 【6.7】考虑一个码长为 4的二元码，其码字为 00001 =W ， 00112 =W ， 11003 =W ， 11114 =W 。假设码字送入一个二元对称信道（其单符号错误概率为 p，且 01.0

p 。因此完成上述编码的概率分布为： 3 1 1 >p 12 pp £ 143 ppp <+ 【8.3】设信源符号集 ú û ù ê ë é =ú û ù ê ë é 9.01.0)( 21 ss sP S （1） 求 )(SH 和信源冗余度； （2） 设码符号为 }1,0{=X ，编出 S的紧致码，并求 S的紧致码的平均码长 L； （3） 把信源的N次无记忆扩展信源 NS 编成紧致码，试求出 ¥= ,4,3,2N 时 的平均码长 N LN ； （4） 计算上述 4,3,2,1=N 这四种码的编码效率和码冗余度。 解： （1） 信源熵为 469.0)(log)()( =-= å xPxPSH 比特/符号 因此得信源冗余度为 531.0 log )(1 =-= r SH g （2）对其进行紧致码编码，二个信源符号一个编码为 0，一个编码为 1，因 此平均码长为 1码符号/信源符号； （3）对原码字进行二次扩展，其信源空间为： ú û ù ê ë é =ú û ù ê ë é 81.009.009.001.0)( 22122111 2 ssssssss P S ia 进行 Huffman编码，得码字如下： 平均码长为： 29.103.027.018.081.02 =+++=L 645.02 = N L 码符号/信源符号 对原信源进行三次扩展，得扩展信源空间为 ú û ù ê ë é 3222 222122212112221121211111 1.09.01.09.01.0081.09.01.0081.0081.0729.0 ssssssssssssssssssssssss 进行 Huffman编码，码字如下： 扩展信源的平均码长为： 598.1005.015*009.09*081.0729.03 =+++=L 532667.03 = N L 码符号/信源符号 四次扩展信源略； 当 ¥®N 时，根据香农第一定理，平均码长为： 469.0 log )( == r SH N LN 码符号/信源符号 （5） 编码效率为： L SH r N L SH N )( log )( ==h 因此有 不进行信源扩展时，编码效率为： 469.0)( == L SH h 进行一次扩展时，编码效率为： 727.0)( == L SH h 进行二次扩展时，编码效率为： 880476.0)( == L SH h 当 ¥®N 时，编码效率趋向于 1。 因此，从本题结论可看出，对于变长紧致码，扩展信源的次数不需很大时就 可以达到高效的无失真编码，这一点与等长码有很大的不同。 【8.4】信源空间为 ú û ù ê ë é =ú û ù ê ë é 05.005.005.005.01.01.02.04.0)( 87654321 ssssssss sP S 码符号为 }2,1,0{=X ，试构造一种三元的紧致码。 解： 原信源有 8个信源符号，为了有效利用短码，需对原信源进行扩展，添加 1 个概率为 0的信源符号，使其满足 9=2*3+3成立。编码过程如下： 0.4 0.2 0.1 0.1 0.05 0.05 0.05 0.05 0 0.1 0.2 0.1 0.2 0.4 0.4 0.2 0 1 2 0 1 2 0 1 2 0 1 2 1 00 02 010 011 012 20 21 22 【8.5】某气象员

气象状态，有四种可能的消息：晴、去、雨和雾。若每个 消息是等概率的，那么发送每个消息最少所需的二元脉冲数是多少？又若四个消 息出现的概率分别为 4 1、 8 1 、 8 1和 2 1，问在此情况下消息所需的二元脉冲数是多 少？如何编码？ 解： pan 高亮 pan 高亮 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2010，版权所有， 仅供试用。ഀ 平均每个消息携带的信息量为 2比特，因此发送每个消息最少需要的二元脉 冲数为 2。如果四个消息非等概率分布，采用紧致码编码，可使得所需要的二元 脉冲数最少，编码过程如下： 平均码长为： 75.1)( == å ii lsPL 二元码符号/信源符号 即在此情况下消息所需的二元脉冲数为 1.75个。 【8.6】若某一信源有 N个符号，并且每个符号等概率出现，对这信源用最佳霍 夫曼码进行二元编码，问当 iN 2= 和 12 += iN （ i是正整数）时，每个码字的长 度等于多少？平均码长是多少？ 解： （1）当 iN 2= 时，对每个符号编码所得的码字为等长码，其码长为 i，平均 码长 iL = ； （2）当 12 += iN 时，每次进行编码时，总会剩余一个，因此，我们可以先 将两个信源符号进行缩减，使得缩减后的信源符号个数恰好为 i2 个，而这 i2 个 信源符号进行编码时是等长的，其码长为 i，其中包含原信源符号为 12 -i 个，同 时，另外两个信源符号的码长为 1+i ，因此，原信源符号的平均码长为 12 2 12 22 12 )1(2)12( + += + ++ = + ++- = ii i i i iiiiiL 【8.7】设信源 ú û ù ê ë é - - MM MM pppp ssss S 121 121: L L 并满足 1 1 =å = M i ip 和 Mppp ³³³ L21 。试证明对于信源 S一定存在这样的二元最佳 码。其码字 1-MW 和 MW 具有相同的长度，且 1-MW 和 MW 只有最后一位码符号不同 （分别为 1和 0）。 解： 请参照课本 264页最佳码三个性质的证明过程，此处略。 【8.8】设码C是均匀概率分布 )/1,,/1,/1( nnnP K= 信源的二元霍夫曼码。并设码 C中各码字的码长为 il ，又设 kan 2= ，而 21 ££ a 。 （1） 证明对于此等概率信源的所有即时码中，码C的总码长 å= i ilT 最短； （2） 证明码C满足 1=å - i lir ； （3） 证明码C中，所有 i满足 Lli = 或 1-= Lli ，其中 }max{ ilL = ； （4） 设u是码长为 1-L 的码字个数，v是码长为 L的码字个数，根据 ka, 确 定u、 v和 L。 证明： （1）根据二元霍夫曼编码的性质，我们知道，它一定是最优即时码，即在 所有即时码中，它的平均码长最短。设C ¢是其他码字，一定有 CC LL >¢ ，而平均 码长 n TLC = ， n TLC ¢ =¢ ，可得 TT ¢£ （2）当 1=a 时，所有码字的码长相等，均为 kli = ； 当 2=a 时，所有码字的码长相等，均为 1+= kli ； 而当 21 << a 时，信源符号个数是位于 k2 至 12 +k 之间的某正整数，反应在码 树上，应是一些长度为 k的节点上生出分枝，作为长度为 1+k 的码字（第（3） 小题中所说的码长要么是 kL =-1 ，要么是 1+= kL ）。设码长为 k的节点数为 x， 则码长为 1+k 的节点的分枝数一定为 ( ) 22 ´- xk ，而码字的总个数为： ( ) kkk axxx 2222 1 =-=´-+ + 因此有 ( ) ( ) 1 222 2222 2 1 = ´-+= ´´-+= = -- --- -- åå kkk kkk i l i l xx xx r ii （3）已在第（2）小题中加以说明，此处略。 （4）根据第（2）小题中的分析可知 1+= kL ，且有 kavu 2=+ uv k 22 1 -= + 解得 kk au 22 1 -= + 11 2)1(222 ++ -=-= kkk aav 编码后的平均码长为 ( ) ( )[ ] [ ] a k aka a akak a L kkkk 22 221 2)1(122 2 1 11 -+= -+= -++-= ++ 【8.9】现有一幅已离散量化后的图像，图像的灰度量化分成 8 级，见下表。表 中数字为相应像素上的灰度级。 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 另有一无损无噪二元信道，单位时间（秒）内传输 100个二元符号。 （1） 现将图像通过给定的信道传输，不考虑图像的任何统计特性，并采用二元 等长码，问需要多长时间才能传完这幅图像？ （2） 若考虑图像的统计特性（不考虑图像的像素之间的依赖性），求此图像的 信源熵 )(SH ，并对灰度级进行霍夫曼最佳二元编码，问平均每个像素需 用多少二元码符号来表示？这时需多少时间才能传送完这幅图像？ （3） 从理论上简要说明这幅图像还可以压缩，而且平均每个像素所需的二元码 符号数可以小于 )(SH 比特。 解： （1）采用二元等长码，不考虑信源符号的统计特性，平均每个灰度需要 3 位二进制表示，在 10*10 的图像上，共需 300 位二进制表示，以每秒传输 100 位计算，共需 3秒钟传输。 （2）统计图像中各灰度级的出现次数： 1 2 3 4 5 6 7 8 40 17 10 10 7 6 5 5 如果考虑信源符号的统计特性，对上述灰度级进行编码，如下图所示。 得如下码字： 1 2 3 4 5 6 7 8 40 17 10 10 7 6 5 5 0 100 1010 1011 1100 1101 1110 1111 1 3 4 4 4 4 4 4 平均码长为： 63.24*43.051.04.0 =++=L 在 10*10的图像上，共需 263位二进制表示，以每秒传输 100位计算，共需 2.63秒钟传输完。 （3）在计算（2）小题时，并未考虑像素灰度级之间的依赖关系，例如，灰 度 1后只能跟灰度 1和 2，并未有其他灰度值。这样得到的信源熵 )(SHH <¥ ， 而根据香农第一定理，当对信源进行扩展时，其平均码长 L逼近于 )(SHH <¥ ， 因此，该图像可以进一步压缩，平均每个像素所需要的二元码符号数 )(SHHL <® ¥ 。 【8.10】有一个含有 8个消息的无记忆信源，其概率各自为 0.2, 0.15, 0.15, 0.1, 0.1, 0.1, 0.1, 0.1。试编成两种三元非延长码，使它们的平均码长相同，但具有不同的 码长的方差，并计算平均码长和方差，说明哪一种码更实用些。 解： 进行三元编码，需增补一个概率为 0的信源符号，两种编码方法如下所示。 图 1 图 2 平均码长为： 26.06.03.03.02.0 =++++=L 编码 1的码方差为： 4.01.01.02.0])[( 221 =++=-= LlE is 0])[( 222 =-= LlE is 虽然两种编码的平均码长相同，但由于编码 2的码方差较小，因此编码 2更 实用一些。 【8.11】设有两个信源 X 和Y如下： ú û ù ê ë é =ú û ù ê ë é 01.01.015.017.018.019.02.0)( 7654321 xxxxxxx xP X pan 高亮 pan 高亮 pan 高亮 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2010，版权所有， 仅供试用。ഀ ú û ù ê ë é =ú û ù ê ë é 01.002.002.004.007.007.014.014.049.0)( 987654321 yyyyyyyyy yP Y （1） 分别用霍夫曼码编成二元变长惟一可译码，并计算其编码效率； （2） 分别用香农编码法编成二元变长惟一可译码，并计算编码效率； （3） 分别用费诺编码方法编成二元变长惟一可译码，并计算编码效率； （4） 从 X 、Y两种不同信源来比较这三种编码方法的优缺点。 解： 第一个信源： 信源熵为： 60868.2)(log)()( =-= å xPxPXH 比特 对其进行二元霍夫曼编码，如下所示： 0.2 0.19 0.18 0.17 0.15 0.1 0.01 0.11 0.26 0.35 0.39 0.61 0 1 0 1 0 1 0 1 00 01 100 0 1 101 0 1 110 1110 1111 平均码长为： 72.24*11.03*55.02*39.0 =++=L 码符号/信源符号 编码效率为： 95907.0)( == L XH h 对其进行费诺编码，如下所示： 00 0.2 0 010 0.19 0 011 0.18 0 1 1 10 0.17 0 110 0.15 0 1110 0.1 0 1111 0.01 1 1 1 1 平均码长为： 74.244.045.034.03*37.04.0 =++++=L 码符号/信源符号 编码效率为： 95207.0)( == L XH h 对其进行香农编码，如下所示。 概率 码长 累积概率分布 二进制小数 码字 0.2 3 0 0.0 000 0.19 3 0.2 0.001100110011 001 0.18 3 0.39 0.011000111101 011 0.17 3 0.57 0.100100011110 100 0.15 3 0.74 0.101111010111 101 0.1 4 0.89 0.111000111101 1110 0.01 7 0.99 0.111111010111 1111111 其平均码长为： 14.307.04.03*89.0 =++=L 码符号/信源符号 编码效率为： 83079.0)( == L XH h 第二个信源： 信源熵为： 31356.2)(log)()( =-= å yPyPYH 比特 对其进行二元霍夫曼编码，如下所示。 平均码长为： 33.26*03.05*02.04*18.03*28.049.0 =++++=L 码符号/信源符号 编码效率为： 99294.0)( == L YH h 对其进行费诺编码，如下所示。 0 0.49 0 100 0.14 0 101 0.14 0 1 1100 0.07 0 1101 0.07 0 1 1110 0.04 0 11110 0.02 0 111110 0.02 0 111111 0.01 1 1 1 1 1 1 平均码长为： 33.26*03.05*02.04*18.03*28.049.0 =++++=L 码符号/信源符号 编码效率为： 99294.0)( == L YH h 对其进行香农编码，如下所示： 概率 码长 累积概率分布 二进制小数 码字 0.49 2 0 0.0 00 0.14 3 0.49 0.011111010111 011 0.14 3 0.63 0.101000010100 101 0.07 4 0.77 0.110001010001 1100 0.07 4 0.84 0.110101110000 1101 0.04 5 0.91 0.111010001111 11101 0.02 6 0.95 0.111100110011 111100 0.02 6 0.97 0.111110000101 111110 0.01 7 0.99 0.111111010111 1111110 平均码长为： 89.27*01.06*04.05*04.04*14.03*28.02*49.0 =+++++=L 编码效率为： 80054.0)( == L YH h 从上述编码中可以看出，霍夫曼编码的平均码长最短，编码效率最高，香农 编码的平均码长最长，其编码效率最低，费诺编码居中。 【8.12】信源符号集 },,2,1{ qA K= ，其概率分布为 qppp ,,, 21 K 。采用以下方法对 信源符号进行编码。首先将概率分布按大小顺序排列 qppp ³³³ K21 ，定义累 积分布函数 å - = D = 1 1 i k ki pF iF是所有小于 i符号的概率和。于是符号 i的码字是取 iF的二进制数的小数 il 位， 若有尾数就进位到第 il 位，其中 ú ú ù ê ê é = i i p l 1log 。 （1） 证明这样编得的码是即时码； （2） 证明： 1)()( +<£ SHLSH ； （3） 对于概率分布为(0.5,0.25,0.125,0.125)的信源进行编码，求其各码字； （4） （3）中所得的码是否与此信源的霍夫曼码正巧完全一致？试说明这 种完全一致的一般原理。 解： （1）按照所取的累积分布函数，我们得知 0)( ³- isFC 且二者的差必然小于第 il 上的权值，因此有 il isFC -<-£ 2)(0 而 ú ú ù ê ê é = i i p l 1log ，得 11log1log +<£ i i i p l p ，即 )(2 i l sPi £- ，可得 il ii sFCsF -+<£ 2)()( 画出累积分布函数的图像，如下图所示。 可以发现，最后所得的码字取值区间并无重叠，根据二进制小数的特性，可 得不重叠的区间其二进制小数的前缀部分是不同的，所以，这样得到的码一定满 足变长码的前缀条件，因此是即时码。 （2）根据 ú ú ù ê ê é = i i p l 1log ，得 11log1log +<£ i i i p l p ，因此有 i i iii i i pp plp p p +<£ 1log1log 两边进行统计平均得 1)()( +<£ SHLSH （3）对概率分布为(0.5,0.25,0.125,0.125)的信源进行编码，过程如下： 码字 概率 码长 累积分布 二进制小数 0 0.5 1 0 0.0 10 0.25 2 0.5 0.1 110 0.125 3 0.75 0.11 111 0.125 3 0.875 0.111 （4）该码字与此信源的霍夫曼编码完全一致，即它本身构造成了该信源的 紧致码，其原因是其码长恰好为 )( 1log isP ，信源的先验概率恰好为 2的幂次方分 布，构成了香农第一定理下限成立的条件，因此必然可以构造出紧致码。 【8.14】已知二元信源 }1,0{ ，其 8 1 0 =p ， 8 7 1 =p ，试对其进行算术编码，并计算 此序列的平均码长 11111110111110 解： 序列的发生概率为： 212 2 0 12 1 8 1 8 7)11101111111011( ÷ ø ö ç è æ ÷ ø ö ç è æ=== ppsP 在编码时应对该序列的码长值为： é ù 9311.83*27 8log*12 )( 1log ==úú ù êê é +=ú ú ù ê ê é = sP li 码字在码树上的相对位置如下图所示： 因此可得码序列的累积分布函数为： 90.63121392 8 1 8 7 8 71 )1111111111011()11111111(1)( 128 = ´÷ ø ö ç è æ-÷ ø ö ç è æ-= --= PPSF 将累积分布函数变为二进制小数，得 0.101000011001，取小数点后 9位，并 进行进位处理，得上述序列的编码为 101000100。 平均码长为 6429.0 14 9 ==L 码符号/信源符号 编码效率为： %555.84 6429.0 54356.0)( === L SH h 【8.15】对输入数据流 000010110011100001001101111分别用 LZ-77算法、LZ-78 算法，LZW算法、K-Y算法进行编码，并计算各种方法的压缩率。 解： 采用 LZ-77编码，所得的编码序列为： (0,0,0) (1,3,1) (0,0,1) (2,2,1) (6,3,1) (5,3,0) (13,3,0) (9,3,1) (14,3,eof) 采用 LZ-78编码，其分段顺序为：0, 00,01,011,001,1,10,000,100,11,0111,11 字典的建立过程如下： 字典编号 存储条目 发送序列 1 2 3 4 5 6 7 8 9 10 11 0 00 01 011 001 1 10 000 100 11 0111 (0,0) (1,0) (1,1) (3,1) (2,1) (0,1) (7,0) (2,0) (7,0) (6,1) (4,1) (10,eof) 采用 LZW编码，过程如下： 基本字典 1 2 0 1 3 4 5 6 7 8 9 10 11 12 13 14 15 00 000 01 10 011 100 0111 1000 001 1001 11 101 111 11 1 3 1 2 5 6 7 8 3 8 2 6 13 13,eof K-Y算法： 令 D0=0，D1=1，先读入 4个，0000，前后相等，因此暂时编码 D2D2 其中 D2=D0D0 继续输入至 D2D2 D1D0D1D0，出现重复情况， 令 D1D0=D3=10，则该序列变为：D2D2 D3D3，继续输入，得 D2D2 D3D3D0D1D1D1D2D2 令 D4=D2D2=0000，上序列变为： D4D3D3D0D1D1D1D4D1D0D0D1 令 D5=D0D1，上序列变为： D4D3D3D5D1D1D4D1D0D5D1 令 D6=D5D1上序列变为： D4D3D3D6D1D4D1D0D6D0D1D1D1D1 令 D7=D1D1=11，上序列变为 D4D3D3D6D1D4D1D0D6D0D7D7 其中 D0=0，D1=1，D2=00，D3=10，D4=0000，D5=01，D6=011，D7=11 将上述序列以及字典发送至接收方即可。 第二章 第三章 第四章 第五章 第六章 第八章 8-11 3-8