6.441信息传输 期中考试 2003年春季 问题1(10分)：对于任何的离散联合分布P(x,),其 中(x,)=x×y。已知x=x是X的任意可能值，证明： X,Y)=∑P()DPPa)-DP,) 问题2(20分)：己知X是一个iid随机变量序列，对 于所有的i,X,eX。假设0=x。每个符号X,的熵为H(X)。 信源编码器将X编码为平均长度为R比特的二进制序 列组成的码字。译码器观察一个码字，以估计值来恢 复X。 a)(8分)当X时，译码出错。采用与Fano不 等式类似的证明方法求证： P(error)1- 1 b)(6分)重新定义译码差错为在严格的多于d个输
6.441 信息传输 期中考试 2003 年春季 问题 1（10 分）：对于任何的离散联合分布 ，其 中 ),( ,YX yxP yx ),( ∈ χ × y 。已知 x0 ∈ χ 是 X 的任意可能值，证明： ∑∈ == = = − x χ X xXYxXY Y PPDPPDxPYXI xXY ()();( )()0 0 问题 2（20 分）：已知 是一个 i.i.d 随机变量序列，对 于所有的 ， n X1 i Xi ∈ χ 。假设0∈ χ 。每个符号 的熵为 。 信源编码器将 编码为平均长度为 比特的二进制序 列组成的码字。译码器观察一个码字，以估计值 来恢 复 。 Xi XH )( n X1 nR n X1 ˆ n X1 a）（8 分）当 时，译码出错。采用与 Fano 不 等式类似的证明方法求证： nn XX 11 ˆ ≠ )( 1 )( 1)error( XnHXH R P −−≥ b）（6 分）重新定义译码差错为在严格的多于nd 个输
入中不同于X”。定义Scx为n维和矢径为md的汉 明球，即： Sx:there is at most nd symbol inx that is not 小为该球的体积（元素的个数），（球的中心无关紧 要)。 证明： nR+1 P(error)>1- nH(X)-logS c)(6分)给出几何证明，为了满足当n→m时b)中 定义的错误概率趋于0，用于编码源X所需的每个输入 符号比特个数最小值应为： R≥H)-oe9l d)加分：完成问题3后再回答此问题。c)中的界可通 过随机编码实现吗？为什么？ 问题3(20分)：考虑下面著名问题：给一个天平和12 个球，..…，，所有的球有相等的重量，除了其中有 一个球或者太轻或者太重。我们的目标是3次使用天平 后找出那个球，且说出它地轻重。注意对于每次使用天
入中 不同于 。定义 为 维和矢径为nd 的汉 明球，即： n X1 ˆ n X1 nn Snd ⊂ χ )( n :{ 1 1 )( xS isthatxinsymbolndmostatisthere nnn n nd ∈= χ not 0} n)( nd S 为该球的体积（元素的个数），（球的中心无关紧 要）。 证明： )( log)( 1 1)error( n nd SXnH nR P − + −≥ c）（6 分）给出几何证明，为了满足当n → ∞ 时 b）中 定义的错误概率趋于 0，用于编码源 所需的每个输入 符号比特个数最小值应为： n X1 )( log 1 )( n Snd n XHR −≥ d）加分：完成问题 3 后再回答此问题。c）中的界可通 过随机编码实现吗？为什么？ 问题 3（20 分）：考虑下面著名问题：给一个天平和 12 个球， ，所有的球有相等的重量，除了其中有 一个球或者太轻或者太重。我们的目标是 3 次使用天平 后找出那个球，且说出它地轻重。注意对于每次使用天 21 12 L,,, bbb
平有3种可能的结果，左边的比右边的重：或者轻：或 者相等。（提示：很好的计划注释，避免过长的解释） a)(3分)若能达到该日标，我们可获得多少信息量 (以bit记)？ b)(3分)说明3次使用天平，如果是14个球则不 能达到目的。你的理由能说明可以解决13个球的问题 吗？ c)(4分)回到12个球的游戏中。Tom以第一次将 12个球分为每组6个球，再比较两组的重量来开始该游 戏。讨论以这种方法他不能达到目标的原因。（提示，使 用树结构) d)(4分)Tom又试了另一种方法。首先比较两组的 重量，每次包括3个球，给出一种基于信息论的论证， 说明他以这种方法也不能达到目的
平有 3 种可能的结果，左边的比右边的重；或者轻；或 者相等。（提示：很好的计划注释，避免过长的解释） a）（3 分）若能达到该目标，我们可获得多少信息量 （以 bit 记）？ b）（3 分）说明 3 次使用天平，如果是 14 个球则不 能达到目的。你的理由能说明可以解决 13 个球的问题 吗？ c）（4 分）回到 12 个球的游戏中。Tom 以第一次将 12 个球分为每组 6 个球，再比较两组的重量来开始该游 戏。讨论以这种方法他不能达到目标的原因。（提示，使 用树结构） d）（4 分）Tom 又试了另一种方法。首先比较两组的 重量，每次包括 3 个球，给出一种基于信息论的论证， 说明他以这种方法也不能达到目的
)(6分)总结解决该问题中的基本原理。可采用一 种解决12球问遵的方法来解释这些想法。注意解答本身 不记分（因为你们一些同学可能知道答案），只有解释了 才得分， )加分：假设有13个球，附加的球已知是好的，使 用天半3次找到坏的球
e）（6 分）总结解决该问题中的基本原理。可采用一 种解决 12 球问题的方法来解释这些想法。注意解答本身 不记分（因为你们一些同学可能知道答案），只有解释了 才得分。 f）加分：假设有 13 个球，附加的球已知是好的， 使 用天平 3 次找到坏的球