信息理论与编码参考答案教案

信息理论与编码参考答案教案 2.3一副充分洗乱的牌（含52张），试问 （1）任一特定排列所给出的不确定性是多少？ （2）随机抽取13张牌，13张牌的点数互不相同时的不确定性是多少？解 （1）52张扑克牌可以按不同的顺序排列，所有可能的不同排列数就是全排列种数，为526752528.06610P?因为扑克牌充分洗乱，任一特定排列出现的概率相等，设事件A为任一特定排列，则其发生概率为?6811.241052P A?可得，该排列发生所给出的信息量为?22log log52225.58I AP A?bit67.91?dit （2）设事件B为从中抽取13张牌，所给出的点数互不相同。 扑克牌52张中抽取13张，不考虑排列顺序，共有1352C种可能的组合。 13张牌点数互不相同意味着点数包括A，2，?，K，而每一种点数有4种不同的花色意味着每个点数可以取4中花色。 所以13张牌中所有的点数都不相同的组合数为134。 因为每种组合都是等概率发生的，所以?1313413524413391.05681052P BC?则发生事件B所得到的信息量为?13213524log log13.208I BP BC?bit3.976?dit2.5设在一只布袋中装有100只对人手的感觉完全相同的木球，每只上涂有1种颜色。 100只球的颜色有下列三种情况 (1)红色球和白色球各50只； (2)红色球99只，白色球1只； (3)红，黄，蓝，白色各25只。 求从布袋中随意取出一只球时，猜测其颜色所需要的信息量。 解猜测木球颜色所需要的信息量等于木球颜色的不确定性。 令R“取到的是红球”，W“取到的是白球”，Y“取到的是黄球”，B“取到的是蓝球”。 （1）若布袋中有红色球和白色球各50只，即?5011002P RP W?则?221log log212I RI W?bit （2）若布袋中红色球99只，白色球1只，即?990.99100P R?10.01100P W?则?22log log0.990.0145I RP R?bit?22log log0.016.644I WP W?bit （3）若布袋中有红，黄，蓝，白色各25只，即?2511004P RP YP BP W?则?21log24I RI YI BI W?bit2.7设信源为1234560.20.190.180.170.160.17XX x x x x x xP?求?62logi iiP x P x?，井解释为什么?622log log6i iiP x P x?，不满足信源熵的极值性。 解?62logi iiP x P x?2222220.2log0.20.19log0.190.18log0.180.17log0.170.16log0.160.17log0.17?2.657?bit/symbol?622log log62.585i iiP x P x?不满足极值性的原因是?61.071iiP x?，不满足概率的完备性。 2.8大量统计表明，男性红绿色盲的发病率为7%，女性发病率为0.5%，如果你问一位男同志是否为红绿色盲，他回答“是”或“否”。 （1）这二个回答中各含多少信息量? （2）平均每个回答中含有多少信息量? （3）如果你问一位女同志，则答案中含有的平均信息量是多少?解对于男性，是红绿色盲的概率记作?17%P a?，不是红绿色盲的概率记作?293%P a?，这两种情况各含的信息量为?1212100log1log3.837I a P a?bit?2222100log1log0.10593I a P a?bit平均每个回答中含有的信息量为?1122()()H AP aI a P aI a?7933.830.105100100?0.366?bit/回答对于女性，是红绿色盲的概率记作?10.5%P b?，不是红绿色盲的记作?299.5%P b?，则平均每个回答中含有的信息量为?1122()()H BP b I b P b I b?22510009951000log log100051000995?0.045?bit/回答?H AH B?联合熵和条件熵2.9任意三个离散随机变量X、Y和Z，求证()()()()H XYZ H XY H XZ H X?。 证明方法一要证明不等式?X H X Z H Y X H Y X H?,Z,成立，等价证明下式成立?0,?X H Z X H Y X H Z Y X H根据熵函数的定义?,log logplog logloglog1(zi j k i j k i j k i jX Y Z X Y Zi jk i ki jk iX Y Z X Y Zi jk ii j kX Y Zi j i ki j i ki j kX Y Zi jkiH X Y ZH X Y H X ZH Xp x y z p x y z p x y z x yp x y z p x z p x y z p xp x y z p xp x y zp x y p x zp x y p x ze p x yzp x y p x?信息论不?)loglog|log110,Z,ij i kij kX Y Z X Y Zij i ikijkX Y Z X YZij iki ijkp x y p x zep x yzp xe p y x p xz p x yzeH X Y H X Y H X ZH Xp x y p xz p x p x yz?等式所以等号成立的条件为得证方法二因为()()(|)H XYZH XY H Z XY?()()(|)H XZH X H Z X?所以，求证不等式等价于(|)(|)H Z XY H Z X?因为条件多的熵不大于条件少的熵，上式成立，原式得证。 2.11设随机变量12,0,1X x x?和12,0,1Y yy?的联合概率空间为11122122(,)(,)(,)(,)18383818XYXY x y x y x y x yP?定义一个新随机变量Z XY?（普通乘积）。 （1）计算熵()H X、()H Y、()H Z、()H XZ、()H YZ以及()H XYZ； （2）计算条件熵(|)H XY、(|)H Y X、(|)H X Z、(|)HZ X、(|)H YZ、(|)HZ Y、(|)H X YZ、(|)H Y XZ以及(|)HZXY； （3）计算互信息量(;)I XY、(;)I X Z、(;)I YZ、(;|)I XYZ、(;|)I YZX以及(;|)I X Z Y；解 （1）?13100,00,1882p x p x y p x y?11102p x p x?log1i iiH X P x P x?bit/symbol?13100,01,0882p y p x y p x y?11102p y p y?log1j jjH Y py py?bit/symbol1337 (0) (00) (01) (10)8888P zP xyP xyP xy?71 (1)1 (0)188P zP z?可得ZXY?的概率空间如下07()8zZP Z?118z?27711()()log log)0.544/8888kKH Zp bit symbolz?由()()()p xz px p z x?得11(0,0) (0) (00)122pxz px p z x?1(0,1) (0) (10)0023(1,0) (1) (01) (1) (01)(1,0)81(1,1) (1) (11) (1) (11)(1,1)8pxz px p z xpxz pxp z xpxpy xpx yp xz pxp z xpxpy xpx y?113311()()log log log1.406/228888i kikH XZpxz bit symbol?由对称性可得()1.406/H YZbt symbol?()()(),()1p xyz p xy p z xy p z xy?由又或者等于，或者等于0.1(0,0,0)(0,0)(00,0)(0,0)18px yzpx y p zxy pxy?1(0,0,1)(0,0)(10,0)0083(0,1,0)(0,1)(00,1)(0,1)183(0,1,1)(0,1)(10,1)0083(1,0,0)(1,0)(01,0)(1,0)18(pxyzpxy pzx yp xyzpxypzxypx ypxyzpxypzx ypxyzpxypzxypxyp?31,0,1)(1,0)(11,0)0081(1,1,0)(1,1)(01,1)0081(1,1,1)(1,1)(11,1)(1,1)18xyzpxypzxypxyzpxypzxypxyzpxypzxypxy?2()()log()11333311log log log log1.811/88888888ijkij kij kH XYZ pxyzpxyzbit symbol? （2）H?XY-symbol bit/811.181log8183log8383log8381log81?H?YX/=H?XY-H?1.81110.811/Y bit symbol?根据对称性，H?XY/=H?|XY0.811/bit symbol?H?ZX/=H?XZ-H?symol bitZ/862.0544.0406.1?H?XZ/=H?XZ-H?symol bitX/406.01406.1?根据对称性，H?Z Y/=H?ZX/0.862/bit symbol?H?YZ/=H?XZ/0.406/bit symol?H?YZ X/=H?XYZ-H?symol bitYZ/405.0406.1811.1?根据对称性，把X和Y互换得H?XZ Y/=H?YZ X/0.405/bit symbol?H?XY Z/=H?XYZ-H?symol bitXY/0811.1811.1? (3)?;/10.8110.189/I XY H X H XYbit symbol?;/10.8620.138/I XZH X H XZbit symbol?根据对称性，得?;0.138/I YZ I XZbit symbol?;/0.8620.4050.457/I XYZH XZH XYZbit symbol?;/0.8110.4050.406/I YZX H YX H YXZbit symbol?根据对称性得?;/;/0.406/I XZYI YZX bitsymbol?2.17设信源发出二次扩展消息i ixy,其中第一个符号为A、B、C三种消息，第二个符号为D、E、F、G四种消息，概率()ip x和()i ipy x如下()ip xA BC1/21/31/6()i ipy xD1/43/101/6E1/41/51/2F1/41/51/6G1/43/101/6求二次扩展信源的联合熵(,)H XY。 解联合概率为(,)(|)()ijj i ip xypyxpx?可得X,Y的联合概率分布如下()iipxy A BC D1/81/101/36E1/81/151/12F1/81/151/36G1/81/101/36所以(,)()log()3.415/iii iXYH XY pxypxy?比特扩展消息2.19设某离散平稳信源X，概率空间为01211364914XP?并设信源发出的符号只与前一个相邻符号有关，其联合概率为(,)i jp a a如下表所示(,)i jp a aia012ja01/41/18011/181/31/18201/187/36求信源的信息熵、条件熵与联合熵，并比较信息熵与条件熵的大小。 解边缘分布为31()()iijjp a p aa?条件概率()()()jij iipa a p aa pa?如下表()j ipa aia012ja09/111/8012/113/42/9201/87/9所以信源熵为311141()()log()(,)1.542/3694i iiH X pa pa Hbitsymbol?条件熵332111121()()log()()()0.87ijj iijbit symH X X p aapaaH X H X Xol?可知21()()H X X H X?因为无条件熵不小于条件熵，也可以得出如上结论。 联合熵331211121(,)()log()()()2.41iji jijbitH X X paapaaH X H X X?二个符号说明 （1）符号之间的相互依赖性造成了信源的条件熵21()H X X比信源熵)H X（少。 （2）联合熵12(,)H XX表示平均每两个信源符号所携带的信息量。 平均每一个信源符号所携带的信息量近似为2121=(,)1.205()2bit H XH XXH X?符号（）原因在于2H X（）考虑了符号间的统计相关性，平均每个符号的不确定度就会小于不考虑符号相关性的不确定度。 2.20黑白气象传真图的消息只有黑色（B）和白色（W）两种，即信源X?B，W，设黑色出现的概率为()0.3P?B，白色的出现概率为()0.7P?W。 （1）假设图上黑白消息出现前后没有关联，求熵)(XH （2）假设图上黑白消息出现前后有关联，其依赖关系为(|)0.9P?W W，(|)0.1P?B W，(|)0.2P?W B，(|)0.8P?B B，求此一阶马尔可夫信源的熵)(2XH。 （3）分别求上述两种信源的剩余度，并比较)(XH和)(2XH的大小，试说明其物理意义。 解 （1）假设传真图上黑白消息没有关联，则等效于一个DMS，则信源概率空间为()1().xXp xPx?B W0307信源熵为21()()log()(0.3,0.7)0.7log0.70.3log0.30.881i jisymbolH XpapaH?bit （2）该一阶马尔可夫信源的状态空间集为?,S W B?根据题意可得状态的一步转移矩阵0.90.10.20.8W BWB?状态极限概率(),()p W p B满足1)(,)|()()(?S SiS Sj ij jijS p SSP Sp Sp即()(|)()(|)()0.9()0.2()()(|)()(|)()0.1()0.8()()()1p W p WW p Wp WB p B p Wp Bp B p B WpWp BBpBpWpBp WpB?可以解得2()3pW?，1()3pB?该一阶马尔可夫信源的熵为2()(|)jj jSHpSH XS?(-0.2log0.20.8log0.8(-0.9log0.90.1log0.1p p?B）W）12(0.2,0.8)(0.9,0.1)33H H?120.7720.4690.55333?bit/symbol （3）黑白消息信源的剩余度为1()0.881=110.119log2log2H X?一阶马尔可夫信源的剩余度为220.553110.447log2log2H?由前两小题中计算的()H X和2H比较可知212)H XH?（即该结果说明当信源的消息（符号）之间有依赖时，信源输出消息的不确定性降低。 所以，信源消息之间有依赖时信源熵小于信源消息之间无依赖时信源熵。 这表明信源熵反映了信源的平均不确定性的大小。 而信源剩余度反映了信源消息依赖关系的强弱，剩余度越大，信源消息之间依赖关系就越大。 2.23设信源为4341=21x xPXX试求 （1）信源的熵、信息含量效率以及冗余度； （2）求二次和三次扩展信源的概率空间和熵。 解 （1）134()log4log0.811/443H Xbit?符号0.81181.1%log2?10.189? （2）假设X为DMS，则1212()()()Px x Px Px?123123()()()()Px x x Px PxPx?可得二次扩展信源的概率空间?2211212122339116161616Xx x x x x x x xXP?2次扩展信源的熵为2()2()1.622/H XH Xbit?2元符号三次扩展信源的概率空间及熵为?331111121211222112122212223393992716464646464646464Xx x x x x x x x x x x x x x x xxxxxxxx xXP?3()3()2.433/3H XH Xbit?元符号2.18设有一个信源，它产生0，1符号的信息。 它在任意时间而且不论以前发生过什么符号，均按 (0)0.4, (1)0.6p p?的概率发出符号。 （1）试问这个信源是否是平稳的？ （2）试计算2()H X,312()HXXX及H?； （3）试计算4()HX并写出4X信源中可能有的所有符号。 解 （1）该信源在任何时刻发出的符号概率都是相同的，即信源发出符号概率分布与时间起点无关，因此这个信源是平稳信源。 又因为信源发出的符号之间彼此独立。 所以该信源也是离散无记忆信源。 （2）2()2()2H(0.4,0.6)2(0.4log0.40.6log0.6)1.942HXH Xbitsymbol?312(/)HXXX3()HX?（信源无记忆）()log()(0.4log0.40.6log0.6)0.971i iipxpxbit symbol?121lim()()0.971N NNNH HXXXXHXbitsymbol? （3）4()4()HXHX?（信源无记忆）4(0.4log0.40.6log0.6)3.8844bit?元符号4X的所有符号0000000100100011010001010110011110001001101010111100110111101111?2.23设信源为4341=21x xPXX试求 （1）信源的熵、信息含量效率以及冗余度； （2）求二次和三次扩展信源的概率空间和熵。 解 （1）134()log4log0.811/443HXbit?符号0.81181.1%log2?10.189? （2）假设X为DMS，则1212()()()PxxPxPx?123123()()()()PxxxPxPxPx?可得二次扩展信源的概率空间?2211212122339116161616Xx xxxxxx xXP?2次扩展信源的熵为2()2()1.622/HXHXbit?2元符号三次扩展信源的概率空间及熵为?331111121211222112122212223393992716464646464646464Xx xxxxxxxxxxxxxxxxxxxxxx xXP?3()3()2.433/3HXHXbit?元符号2.25设连续随机变量X的概率密度函数为其他a xbxx fX00=)(2 （1）求X的熵； （2）求)0(+=A AXY的熵； （3）求XY2=的熵。 解 （1）0()()log()aX Xh X f x fx dx?-?20logaXf xbx dx?-200log()2loga aXbfx dx bx xdx?-20log2log lnab b ex xdx?-3322log log log93ba bae a b?-因为200()1a aXfx dxbx dx?所以23=ab故2()log2log log33log3h Xe aa?-2log log3log3e a?- （2）首先求得Y的分布函数?F Yy F X A y?F X y A?()y AXfx dx?01,(),0,y AXy A afx dxAyA ayA?Y的概率密度为()YdFf ydy?2(),0,b yA AyAa?其它Y的微分熵为()()A aYAh Y f y dy?22()log()A aAb yAbyA dy?220logabt bt dt?（令ty A?）()h X?2log log3log3e a?-因为已知X，关于Y没有不确定，常数A不会增加不确定度，所以从熵的概念上也可判断此时()()hYh X? （3）首先求得Y的分布函数?2F Yy FXy?/2FXy?/2()yXf xdx?/201,2(),020,0yXy afxdxy ay?Y的概率密度为()YdFf ydy?21,0280,by ya?其它Y的微分熵为20()()aYh Yfydy?22xxlog88aby bydy?22xxlog log2a abtbt dtbtdt?（令/2t y?）()log2hX?23log log log32ea?-3.2信道线图如下，试确定该信道的转移概率矩阵dcabjihfge0.00010.00090.150.30.040.0092.03.03.015.004.0009.00009.00001.02.03.0解按照转移矩阵的排列原则行对应输入符号，列对应输出符号0.20.30.30.150.040.0090.00090.00010.00010.00090.0090.040.150.30.30.2轾犏犏臌3.3DMC的转移矩阵如下|0.60.30.10.30.10.6Y XP? （1）画出信道线图； （2）若输入概率为?0.50.5XP?，求联合概率、输出概率以及后验概率。 解 （1）1a2a3b2b1b0.60.30.10.60.30.1 （2）1()P a乘以|X YP的第1行，2()P a乘以|X YP的第2行，得联合概率矩阵XYP0.30.150.050.150.050.3XYP?XYP的各列元素相加得对应的输出概率，写成矩阵形式?0.450.200.35YP?XYP的各列元素除以对应的输出概率，得后验概率矩阵|2/33/41/71/31/46/7X YP?3.4设离散无记忆信源X通过离散无记忆信道?|,Y XXP Y传送信息，设信源的概率分布和信道的线图分别为?4.06.021a aPX1a2a1b2b0.80.90.20.1试求 （1）信源X的符号1a和2a分别含有的自信息； （2）从输出符号(1,2)jb j?所获得的关于输入符号(1,2)ia i?的信息量； （3）信源X和信道输出Y的熵； （4）信道疑义度(|)HXY和噪声熵(|)H YX； （5）从信道输出Y中获得的平均互信息量。 解 (1)11()log0.73700.6I a?bit/符号21()log1.32200.4I a?bit/符号 (2)?YXY XP PP=?0.80.20.60.40.520.480.10.9?11111(;)()()?I ab Ib Ib a=0.94340.32190.6215?bit/符号12221(;)()()I ab Ib Ibb?=1.05892.32201.2631?bit/符号21112(;)()()I ab Ib Ib a?=0.94343.3222.3786?bit/符号22222(;)()()I abIbIb a?=1.05890.15200.9609?bit/符号 (3)()0.60.73700.41.32200.971?HXbit/符号()0.520.94340.481.05890.9988?H Ybit/符号 (4)、 (5)1()(0.8,0.2)0.80.32190.22.32200.7219?H Ya Hbit/符号2()(0.1,0.9)0.13.3220.90.1520.469?H Ya Hbit/符号()0.60.72190.40.4690.6207?HYXbit/符号(;)()()0.99880.62070.3781?I XY HY HYXbit/符号又根据?;()()?I XY HXHXY()()(;)?HXY HX IXY=0.9710.37810.5929?bit/符号3.6举出下列信道的实例，给出线图和转移矩阵。 （1）无损的，但不是确定的，也不是对称的； （2）准对称且无损，但不是确定的； （3）无损的确定信道。 解 (1)满足()0?HXY（无损），()0?HYX(不确定)，不具有行列排列性，线图和转移矩阵如下1a1b12a2b3b0.50.510000.50.5Y ZP? (2)无损要求()0?HXY；不确定要求()0?HYX，具有行排列性，线图和转移矩阵如下1a1b0.40.62b2a3b0.40.64b0.40.600000.60.4Y ZP? (3)无损、确定信道的线图和转移矩阵如下1a1b12a2b11001?Y XP3.7求下列两个信道的信道容量和最佳输入分布，并加以比较。 其中1?p p。 2 (1)2p pp p?xx)2(p pp p解 (1)方法一利用一般DMC信道容量解的充要条件，计算各偏互信息，并使之均等于信道容量C，再结合输出概率的完备性，可以解出信道容量，最后利用全概率公式得出最佳输入分布。 该方法通用，但过程繁琐。 方法二观察发现此信道是准对称信道。 信道矩阵中Y可划分为二个互不相交的子集，如下,p pp p?，22?而这两个子矩阵满足对称性，因此，可直接利用准对称信道的信道容量公式进行计算。 121log(,)?nk kkskM MCs Hp p pr r其中n=2,2r?，112?M，24?M，24M?，12s?,21s?，所以?11212442log1log(,2)2222212log2log2loglog2log212212logloglog12C Hp pp p p pp ppp?输入等概率分布时达到信道容量。 （2）此信道也是准对称信道，现采用准对称信道的信道容量公式进行计算。 此信道矩阵中Y可划分成两个互不相交的子集为,p ppp?，xx?这两矩阵为对称矩阵。 其中n=2，2r?，112?M，22?M，122s s?，所以?21211log(,)1212222log2log(,2)2222212log2logloglog2log212212logloglog2log2122log2nk kkskM MCs Hpppr rHp pppp pppp pC?输入等概率分布（121()()2P aP a?）时达到此信道容量。 两个信道的噪声熵相等但第二个信道的输出符号个数较多，输出熵较大，故信道容量也较大。 3.8求下列二个信道的信道容量及其最佳的输入概率分布。 1a2a1b2b3b4b13161316161613131a2a1b2b0.980.020.980.02解图中2个信道的信道矩阵为11111363611116363P?20.980.020.020.98?P矩阵为行列排列阵，其满足对称性，所以这两信道是对称离散信道。 由对称离散信道的信道容量公式得11111log4,0.08173636C H?比特/符号?2log20.02,0.980.858?C H特/符号最佳输入分布是输入为等概率分布。 3.9设信道转移矩阵为|1000101Y XPpppp? （1）求信道容量和最佳输入分布的一般表达式； （2）当0p?和12p?时，信道容量分别为多少