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

-1-2.1设有12枚同值硬币，其中一枚为假币。只知道假币的重量与真币的重量不同，但不知究竟是重还是轻。现用比较天平左右两边轻重的方法来测量（因无砝码）。为了在天平上称出哪一枚是假币，试问至少必须称多少次？解：分三组，每组4个，任意取两组称。会有两种情况，平衡，或不平衡。(1)平衡：明确假币在其余的4个里面。从这4个里面任意取3个，并从其余8个好的里面也取3个称。又有两种情况：平衡或不平衡。a）平衡：称一下那个剩下的就行了。b）不平衡：我们至少知道那组假币是轻还是重。从这三个有假币的组里任意选两个称一下，又有两种情况：平衡与不平衡，不过我们已经知道假币的轻重情况了，自然的，不平衡直接就知道谁是假币；平衡的话，剩下的呢个自然是假币，并且我们也知道他是轻还是重。(2)不平衡：假定已经确定该组里有假币时候：推论1：在知道该组是轻还是重的时候，只称一次，能找出假币的话，那么这组的个数不超过3。我们知道，只要我们知道了该组（3个）有假币，并且知道轻重，只要称一次就可以找出来假币了。从不平衡的两组中，比如轻的一组里分为3和1表示为“轻（3）”和“轻（1）”，同样重的一组也是分成3和1标示为“重（3）”和“重（1）”。在从另外4个剩下的，也就是好的一组里取3个表示为“准（3）”。交叉组合为：轻（3）+重（1）？=======？轻（1）+准（3）来称一下。又会有3种情况：(1)左面轻：这说明假币一定在第一次称的时候的轻的一组，因为“重（1）”也出现在现在轻的一边，我们已经知道，假币是轻的。那么假币在轻（3）里面，根据推论1，再称一次就可以了。(2)右面轻：这里有两种可能：“重（1）”是假币，它是重的，或者“轻（1）”是假币，它是轻的。这两种情况，任意取这两个中的一个和一个真币称一下即可。(3)平衡：假币在“重（3）”里面，而且是重的。根据推论也只要称一次即可。2.2同时扔一对骰子，当得知“两骰子面朝上点数之和为2”或“面朝上点数之和为8”或“骰子面朝上之和是3和4”时，试问这三种情况分别获得多少信息量？解：设“两骰子面朝上点数之和为2”为事件A，则在可能出现的36种可能中，只能个骰子都为1，这一种结果。即：P（A）=1/36，I（A）=2logP（A）=2log36≈5.17比特设“面朝上点数之和为8”为事件B，则有五种可能：2、6；6、2；4、4；3、5；5、3；即：P（B）=5/36，I（B）=2logP（B）=2log36/5≈2.85比特设“骰子面朝上之和是3和4”为事件C，则有两种可能：3、4；4、3；即：P（C）=2/36，I（C）=2logP（C）=2log36/2≈4.17比特2.3如果你在不知道今天是星期几的情况下问你的朋友“明天是星期几？”则答案中含有多少信息量？如果你在已知今天是星期四的情况下提出同样的问题，则答案中你能获得多少信息量（假设已知星期一至星期日的排序）解：（1）P＝1/7I＝－Log2P＝－Log27（2）已知今天星期四，问明天是星期几？即：明天是星期五是必然事件，不存在不确定性，I＝0。2.4地区的女孩中有25％是大学生，在女大学生中有75％是身高1.6米以上的，而女孩中身高1.6米以上的占半数一半。假如我们得知“身高1.6米以上的某女孩是大学生”的消息，问获得多少信息量？解：设A为女大学生,B为1.6米以上的女孩则依题意有:1()4PA,1()2PB,3(|)4PBA133()()(|)4416PABPAPBA-2-()3(|)()8PABPABPB所以信息量为228log3log332.5一副充分洗乱了的牌（含52张牌），试问(1)任一特定排列所给出的信息量是多少？(2)若从中出去抽取13张牌，所给出的点数都不相同时得到多少信息量？解：（1）任一排列发生的概率为1/52!I＝log52!＝225.58bit（2）13张牌点数都不相同发生的概率为1/413I＝log413＝26bit2.设离散无记忆信源)x(PX=8/13a4/12a4/11a8/30a4321＝＝＝＝,其发出的消息为（202120130213001203210110321010021032011223210），求：（1）此消息的自信息是多少？（2）在此消息中平均每个符号携带的信息量是多少？解：(1)因为离散信源是无记忆的，所以起发出的消息序列中各符号是无依赖且统计独立的。因此，此消息的自信息就为该消息中各符号自信息之和。I（01a）=−logP（1a）=−log83=1.415比特I（12a）=−logP（2a）=−log41=2比特I（23a）=−logP（3a）=−log41=2比特I（34a）=−logP（4a）=−log81=3比特则此消息的自信息是：I=14I（01a）+13I（12a）+12I（23a）+6I（34a）141.415+132+122+6387.81比特(2)此消息中平均每个符号携带的信息量是：I2=87.81451.95比特/符号2.7如有6行8列的棋型方格，若又二个质点A和B，分别以等概率落入任一方格内，他们的坐标分别为（XA,YA）,(XB,YB),但A.B不能落入同一方格内。（1）如仅有质点A，求A落入任一个格的平均自信息量是多少？（2）若已知A已落入，求B落入的平均自信息量。（3）若A,B是可分辨的，求A,B同都落入的平均自信息量。解:(1)H(XA)=－)(log)(241iiiaPaP=log24(2)H(XB/XA)=－qi1)/(log)/()(1ijqjijiaaPaaPaP=－2423log)/(log)/()(1124201aaPaaPaPjjj(3)H(XAXB)=－qi1)(log)(1jiqjjiaaPaaP-3-=)(log)(24121jqjjaaPaaP=－24*23*241*231log(241*231)=log24*23=log23+log242.8从大量统计资料知道，男性中红绿色盲的发病率为7％，女性发病率为0.5％，如果你问一位男同志：“你是否是红绿色盲？”他的回答可能是“是”，可能是“否”，问这二个答案中各含多少信息量？平均每个回答中含有多少信息量？如果你问一位女同志，则答案中含有的平均自信息量是多少？解：（1）若男同志回答“是”：I＝log(1/7%)＝3.84bit回答“否”：I＝log(1/93%)＝0.1bit平均信息量为：I＝－7%log7%－93%log93%＝0.36bit（2）若问女同志，平均信息量为：I＝－0.5%log0.5%－99.5%log99.5%＝0.045bit2.9设信源123456,,,,,()0.2,0.19,0.18,0.17,0.16,0.17XaaaaaaPx求这信源的熵，并解释为什么()log6Hx，不满足信源熵的极值性。解：信源的熵为：2222111()0.2log50.19log0.18log0.17log0.190.180.17Hx22110.16log0.17log2.6570.160.17bit/符号()log6Hx是因为此信息的61()1iiPa,不满足信息熵极值性的条件。2.10设离散无记忆信源S其符号集A{a1,a2,...,aq},知其相应的概率分布为（P1,P2,...,Pq）。设另一离散无记忆信源S’，其符号集为S信源符号集的两倍，A’={ai}i=1,2,...,2q,并且各符号的概率分布满足：Pi’=(1-ε)Pi(i=1,2,...,q)Pi’=εPi-q(i=q+1,q+2,...,2q)试写出信源S’信息熵与信源S的信息熵的关系。解：S：a1a2……aqP：p1p2……pqH（X）＝－Σqi＝1PiLogPiΣqi＝1Pi＝1S`：a1a2……aqaq＋1……a2qP：p，1p，2……p，qp，q＋1……p，2qH（X）＝－Σ2qi＝1P，iLogP，i＝－〔Σqi＝1P，iLogP，i＋Σ2qi＝q＋1P，iLogP，i〕＝－{Σqi＝1（1－ε）Pi〔Log（1－ε）＋LogPi〕＋Σ2qi＝q＋1εPi－q（Logε＋LogPi－q）}＝－{（1－ε）Σqi＝1PiLog（1－ε）＋（1－ε）Σqi＝1PiLogPi＋εΣ2qi＝q＋1Pi－qLogε＋εΣ2qi＝q＋1Pi－qLogPi－q}＝－{（1－ε）Σqi＝1PiLogPi＋εΣ2qi＝q＋1Pi－qLogPi－q＋（1－ε）Log（1－ε）Σqi＝1Pi＋εLogεΣ2qi＝q＋1Pi－q}＝－{（1－ε）Σqi＝1PiLogPi＋εΣqj＝1PjLogPj＋（1－ε）Log（1－ε）Σqi＝1Pi＋εLogεΣqj＝1Pj}＝－{Σqi＝1PiLogPi＋〔（1－ε）Log（1－ε）＋εLogε〕Σqi＝1Pi}＝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）因为每帧图象可以看成是离散的数字图象，每个像素的亮度是随机而且等概率出现的，则每个像素亮度信源的概率空间为：)(iaPX=1.0,....,1.0,1.0,....,,1021aaa101)(iiaP=1每个像素亮度含有的信息量为：H(X)=log2103.32比特/像素=1哈特/像素现在，所有的像素是独立变化的，则每帧图象可以看成是离散亮度信源的无记忆N次扩展信源。故，每帧图象含有的信息量是：H(XN)=NH(X)=5105log10=5105哈特/帧1.66106比特/帧而每秒传送30帧图象，则传递这个图象所需要的信息率为R1=30H(XN)=1.5106哈特/秒4.98107比特/秒（2）证明：每个像素具有10个不同的亮度和30个色彩度。由上面的计算得亮度等概率出现的情况下，每个像素含有的信息量是：H(X)=log2103.32比特/像素。每个像素的色彩度也是等概率出现的，则色彩度信源的概率空间为：)(jbPX=30/1,....,30/1,30/1,....,,1021bbb301)(jjbP=1每个像素色彩度含有的信息量：H(Y)=log2304.91比特/像素而亮度和色彩度是相互独立的，所以亮度和色彩度同时出现，每像素含有的信息量：H(XY)=H(X)+H(Y)=log10+log30=log3008.23比特/像素如果每帧所用的像素数和每秒传送的帧数都相同的情况下，传输这彩色系统的信息率与传输黑白系统的信息率之比就等于彩色系统每像素含有的信息量与黑白系统每像素含有的信息量之比：)()(XHXYH=10log300log2.5证毕。2.14每帧电视图像可以认为是由3×105个像素组成,所以像素均是独立变化,且每一像素又取128个不同的亮度电平,并设亮度电平等概率出现.问每帧图像含有多少信息量?现有一广播员在约10000个汉字的字汇中选1000个字来口述此电视图像,试问广播员描述图像所广播的信息量是多少(假设汉字字汇是等概率分布,并彼此无依赖)?若要恰当地描述图像,广播员在口述中至少需要多少汉字?解:∵亮度电平等概率出现∴每个像素所含的信息量为H(X)=log128=7bit/像素.而每个像素均是独立变化的∴每帧电视图像所包含的信息量为H(X)=3×105H(X)=2.1×106b