信息论与编码第2章习题解答336

-1-2.1设有12枚同值硬币，其中一枚为假币。只知道假币的重量与真币的重量不同，但不知究竟是重还是轻。现用比较天平左右两边轻重的方法来测量(因无砝码)。为了在天平上称出哪一枚是假币，试问至少必须称多少次？解：分三组，每组4个，任意取两组称。会有两种情况，平衡，或不平衡。(1)平衡：a)平衡：称一下那个剩下的就行了。b)不平衡：我们至少知道那组假币是轻还是重。从这三个有假币的组里任意选两个称一下，又有两种情况：平衡与不平衡，不过我们已经知道假币的轻重情况了，自然的，不平衡直接就知道谁是假币；平衡的话，剩下的呢个自然是假币，并且我们也知道他是轻还是重。组里有假币时候：的话，那么这组的个数不超过3。我们知道，只要我们知道了该组(3个)有假币，并且知道轻重，只要称一次就可以找出来假币了。从不平衡的两组中，比如轻的一组里分为3和1表示为“轻(3)”和“轻(1)”，同样重的一组也是分成3和1标示为“重(3)”和“重(1)”。在从另外4个剩下的，也就是好的一组里取3个表示为“准(3)”。交叉组合为：轻(3)+重(1)？=======？轻(1)+准(3)(1)左面轻：这说明假币一定在第一次称的时候的轻的一组，因为“重(1)”也出现在现在轻的一边，我们已经知道，假币是轻的。那么假币在轻(3)里面，根据推论1，再称一次就可以了。“重(1)”是假币，它是重的，或者“轻(1)”是假币，它是轻的。这两种情况，任意取这两个中的一个和一个真币(3)平衡：假币在“重(3)”里面，而且是重的。根据推论也只要称一次即可。22222则答案中含有多少信息量？如果你在已知今天是星期四的情况下提出同样的问题，则答案中你能获得多少信息量(假设已知星期一至星期日的排序)(2)已知今天星期四，问明天是星期几？即：明天是星期五是必然事件，不存在不确定性，I＝0。则依题意有:P(A)=,P(B)=,P(B|A)4244416-2-P(A|B)=P(AB)=3P(B)82322.5一副充分洗乱了的牌(含52张牌)，试问解：(1)任一排列发生的概率为1/52!(2)13张牌点数都不相同发生的概率为1/413(1)此消息的自信息是多少？(2)在此消息中平均每个符号携带的信息量是多少？解：(1)因为离散信源是无记忆的，所以起发出的消息序列中各符号是无依赖且统计独立的。因此，此消息的自信息就为该消息中各符号自信息之和。3I(a=0)=−logP(a)=−log=1.415比特1181I(a=1)=−logP(a)=−log=2比特2241I(a=2)=−logP(a)=−log=2比特3341I(a=3)=−logP(a)=−log=3比特4481234均每个符号携带的信息量是：2(1)如仅有质点A，求A落入任一个格的平均自信息量是多少？(2)若已知A已落入，求B落入的平均自信息量。(3)若A,B是可分辨的，求A,B同都落入的平均自信息量。HXAxPalogPa=log24iii=1(2)H(XB/XA)=－xqxqP(a)P(a/a)logP(a/a)ijiji1j1j1HXAXBxqxqPaa)logP(aa)ijij-3-1j1jj=21111=－24*23**log(*)24232423220.1920.1820.17+0.16log1+0.17log1=2.657bit/符号20.1620.17H(x)>log6是因为此信息的x6P(a)>1,不满足信息熵极值性的条件。ii=1H(X)＝－Σqi＝1PiLogPiH(X)＝－Σ2qi＝1P，iLogP，igPiq＝－{(1－ε)Σqi＝1PiLog(1－ε)＋(1－ε)Σqi＝1PiLogPi＋εΣ2qi＝q＋1Pi－qLogε＋εΣ2qi＝q＋1Pi－qLogPi－q}qLogPiqLogqiPiLogqiqPiqji＝H(X)－〔(1－ε)Log(1－ε)＋εLogε〕Σqi＝1Pi＝H(X)－(1－ε)Log(1－ε)－εLogε即：H,(X)＝H(X)－(1－ε)Log(1－ε)－εLogε2.13(1)为了使电视图象获得良好的清晰度和规定的适当的对比度，需要用5*105个象素和10个不同的亮度电平，求传递此图象所需的信息率(比特/秒)。并设每秒要传送30帧图像，所有象素是独立变化，且所有亮度电平等概率出现。(2)设某彩电系统，除了满足对于黑白电视系统的上述要求外，还必须有30个不同的色彩度，试证明传输这彩色系统的信息率要比黑白系统的信息率约大2.5倍。-4-解：(1)因为每帧图象可以看成是离散的数字图象，每个像素的亮度是随机而且等概率出现的，则每个像素亮度信源iii=1现在，所有的像素是独立变化的，则每帧图象可以看成是离散亮度信源的无记忆N次扩展信源。故，每帧图象含有而每秒传送30帧图象，则传递这个图象所需要的信息率为(2)证明：每个像素具有10个不同的亮度和30个色彩度。由上面的计算得亮度等概率出现的情况下，每个像素含有的息量：j=1而亮度和色彩度是相互独立的，所以亮度和色彩度同时出现，每像素含有的信息量：如果每帧所用的像素数和每秒传送的帧数都相同的情况下，传输这彩色系统的信息率与传输黑白系统的信息率之比就等于彩色系统每像素含有的信息量与黑白系统每像素含有的信息量之比：H(XY)2.14每帧电视图像可以认为是由3×105个像素组成,所以像素均是独立变化,且每一像素又取128个不同的亮度电平,并设亮汇中选1000个字来口述此电视图像,试问广播员描述图像所广播的信息量是多少(假设汉字字汇是等概率分布,并彼此无依赖)?若要恰当地描述图像,广播员在口述中至少需要多少汉字?HXlog128=7bit/像素.而每个像素均是独立变化的∵假设汉字字汇是等概率分布字间彼此无依赖,广播员口述的1000个汉字所广播的信息量为(1)不同字母等概率出现时，计算传输的平均信息速率？概率分别为pA=1/5,pB=1/4,pC=1/4,pD=3/10，试计算传输的平均信息速率？解：(1)由题可知，当不同字母等概率出现时，平均自信息量为：xlog率为100字母/秒(2)当每个字母分别以题中的概率出现时，平均自信息量为：-5-g号.(1)试问这个信源是否平稳的?N解：(1)因为信源发出符号的概率分布与时间平移无关,而且信源发出的序列之间也是彼此无依赖的.所以这个信源是平稳信源,是离散无记忆信源.因为信源是平稳无记忆信源,所以H(X2)=2H(X)≈1.942bit/两个符号H(X3|X1X2)=H(X3)=H(X)≈0.971比特/符号limH(limH(X)=limH(XXX)=limNH(X)=H(X)≈0.97bit/符号NNNN12NNN(3)H(X4)=4H(X)≈3.884bit/四个符号1101(称为高概率序列)。对于这样的信源我们可以用另一新信源来代替，新信源中只包含这些高概率序列。这时新信源(2)当n)w时求信源的熵H(S)=limH(S)n)wn解：依题意，因为是二元无记忆信源，在发出的二元序列中符号之间彼此是无依赖的，统计独立的，所以有： iii=1Pnii1-Pi=1i=1n)wnn)w1-P1-Pn)wn)w1-P-6-XiXiPXiXiPXXi尔可夫信源的图示法画出状态转移图，并计算信源熵，状态转移图为：E0E1abbccE3cbbE4E5E6E7E8E9E的状态必然会进入这个不可约闭集，所以计算信源熵时，可以不考虑过渡状态和过渡过程。由此，可得状态E1、E2、E3的EE12E0E3-7-(3)近似认为此信源为无记忆时，符号的概率分布等于平稳分布。求近似信源的熵H(X)并与H进行比较；wwwiiii1Q313(2)据一阶马尔可夫信源的熵的表达式可得H=H=x3Q(E)H(X|E)w2iii=1=P(0)H(X|0)+P(1)H(X|1)+P(2)H(X|2)322322322(3)信源近似为无记忆信源，符号的概率分布等于平稳分布，则此信源iiiw (4)求一阶马尔可夫信源H的最大值。因为w-8-plnln2plnln2pw ?H2(1-p)2(1-p)2Hwplogppp，Hw达到最大值；w的最大值等Hw2w2由此可以看出上面H(X)>H的结论时正确的。wX(1)求平稳后信源的概率分布。 (2)求信源的熵H。∞ppppp2p解：(1)由图可知一阶马尔可夫信源的状态空间E=A={0,1,2}.平稳后信源的概率分布就等于一阶马尔可夫信源状态的极p从状态图中分析可知，这三个状态都是正规常返态，所以此马尔可夫链具有各态历经性，平稳后状态的极限分布存在。可得状态一步转移矩阵|P0 PPP]|0 (2)一阶马尔可夫信源的熵-9-∞∞∞因为信息熵是表示信源的平均不确定性，题中当P=1或P=0时表明信源从某一状态出发转移到另一状态的情况是信源输出什么符号不存在不确定性，完全是确定的，因此确定信源的信息熵等于零。2.24设有一个马尔可夫信源,它的状态集为{s1,s2,s3},符号集为{a1,a2,a3},及在某状态下发符号的概率为P(ak|si)(i,k=1,2,3),如下图所示.S3(1)求出图中马尔可夫信源的状态极限概率并找出符号的极限概率条件熵H(sj)(j=1,2,3).解:(1)此信源的状态集不等于