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

第二章课后习题【21】设有12枚同值硬币，其中有一枚为假币。只知道假币的重量与真币的重量不同，但不知究竟是重还是轻。现用比较天平左右两边轻重的方法来测量。为了在天平上称出哪一枚是假币，试问至少必须称多少次解从信息论的角度看，“12枚硬币中，某一枚为假币”该事件发生的概率为121P；“假币的重量比真的轻，或重”该事件发生的概率为21P；为确定哪一枚是假币，即要消除上述两事件的联合不确定性，由于二者是独立的，因此有24LOG2LOG12LOGI比特而用天平称时，有三种可能性重、轻、相等，三者是等概率的，均为31P，因此天平每一次消除的不确定性为3LOGI比特因此，必须称的次数为923LOG24LOG21II次因此，至少需称3次。【延伸】如何测量分3堆，每堆4枚，经过3次测量能否测出哪一枚为假币。【22】同时扔一对均匀的骰子，当得知“两骰子面朝上点数之和为2”或“面朝上点数之和为8”或“两骰子面朝上点数是3和4”时，试问这三种情况分别获得多少信息量解“两骰子总点数之和为2”有一种可能，即两骰子的点数各为1，由于二者是独立的，因此该种情况发生的概率为3616161P，该事件的信息量为17536LOGI比特“两骰子总点数之和为8”共有如下可能2和6、3和5、4和4、5和3、6和2，概率为36556161P，因此该事件的信息量为852536LOGI比特“两骰子面朝上点数是3和4”的可能性有两种3和4、4和3，概率为18126161P，因此该事件的信息量为17418LOGI比特【23】如果你在不知道今天是星期几的情况下问你的朋友“明天星期几”则答案中含有多少信息量如果你在已知今天是星期四的情况下提出同样的问题，则答案中你能获得多少信息量（假设已知星期一至星期日的顺序）解如果不知今天星期几时问的话，答案可能有七种可能性，每一种都是等概率的，均为71P，因此此时从答案中获得的信息量为80727LOGI比特而当已知今天星期几时问同样的问题，其可能性只有一种，即发生的概率为1，此时获得的信息量为0比特。【24】居住某地区的女孩中有25是大学生，在女大学生中有75是身高16米以上的，而女孩中身高16米以上的占总数一半。假如我们得知“身高16米以上的某女孩是大学生”的消息，问获得多少信息量解设A表示女孩是大学生，250AP；B表示女孩身高16米以上，750|ABP，50BP“身高16米以上的某女孩是大学生”的发生概率为375050750250|BPABPAPBPABPBAP已知该事件所能获得的信息量为415137501LOGI比特【25】设离散无记忆信源8/14/14/18/332104321AAAAXPX，其发出的消息为（202120130213001203210110321010021032011223210），求（1）此消息的自信息是多少（2）在此消息中平均每个符号携带的信息量是多少解信源是无记忆的，因此，发出的各消息之间是互相独立的，此时发出的消息的自信息即为各消息的自信息之和。根据已知条件，发出各消息所包含的信息量分别为415138LOG00AI比特24LOG11AI比特24LOG22AI比特38LOG33AI比特在发出的消息中，共有14个“0”符号，13个“1”符号，12个“2”符号，6个“3”符号，则得到消息的自信息为818736212213415114I比特45个符号共携带8781比特的信息量，平均每个符号携带的信息量为951458187I比特/符号注意消息中平均每个符号携带的信息量有别于离散平均无记忆信源平均每个符号携带的信息量，后者是信息熵，可计算得911LOGXPXPXH比特/符号【26】如有6行8列的棋型方格，若有二个质点A和B，分别以等概率落入任一方格内，且它们的坐标分别为（XA,YA）和（XB,YB），但A和B不能落入同一方格内。（1）若仅有质点A，求A落入任一个格的平均自信息量是多少（2）若已知A已落入，求B落入的平均自信息量。（3）若A、B是可分辨的，求A、B同都落入的平均自信息量。解（1）求质点A落入任一格的平均自信息量，即求信息熵，首先得出质点A落入任一格的概率空间为48148148148148321LLAAAAPX平均自信息量为58548LOGAH比特/符号（2）已知质点A已落入，求B落入的平均自信息量，即求|ABH。A已落入，B落入的格可能有47个，条件概率|IJABP均为471。平均自信息量为55547LOG|LOG|481471IJIJIJIABPABPAPABH比特/符号（3）质点A和B同时落入的平均自信息量为1311|ABHAHABH比特/符号【27】从大量统计资料知道，男性中红绿色盲的发病率为7，女性发病率为05，如果你问一位男同志“你是否是红绿色盲”，他的回答可能是“是”，也可能是“否”，问这两个回答中各含有多少信息量平均每个回答中含有多少信息量如果你问一位女同志，则答案中含有的平均自信息量是多少解男同志红绿色盲的概率空间为93007021AAPX问男同志回答“是”所获昨的信息量为83630701LOGI比特/符号问男同志回答“否”所获得的信息量为10509301LOGI比特/符号男同志平均每个回答中含有的信息量为3660LOGXPXPXH比特/符号同样，女同志红绿色盲的概率空间为99500050Y21BBP问女同志回答“是”所获昨的信息量为64700501LOGI比特/符号问女同志回答“否”所获昨的信息量为31023799501LOGI比特/符号女同志平均每个回答中含有的信息量为0450LOGXPXPYH比特/符号【28】设信源17016017018019020654321AAAAAAXPX，求此信源的熵，并解释为什么6LOGXH，不满足信源熵的极值性。解6LOG652LOGXPXPXH原因是给定的信源空间不满足概率空间的完备集这一特性，因此不满足极值条件。【29】设离散无记忆信源S其符号集,21QAAAA，知其相应的概率分别为,21QPPP。设另一离散无记忆信源S，其符号集为S信源符号集的两倍，2,2,1,QIAAI，并且各符号的概率分布满足QQQIPPQIPPIIII2,2,1,2,11EE试写出信源S的信息熵与信源S的信息熵的关系。解1,LOG1LOG1LOGLOGLOG11LOG1LOG1LOG1LOGEEEEEEEEEEEEEEEEHSHSHPPPPPPPPPPXPXPSHIIIIIIIIII【210】设有一概率空间，其概率分布为,21QPPP，并有21PP。若取E11PP，E22PP，其中2120PPLX（2）拉普拉斯概率密度函数，XEXPLL21，0,KKXY，XY22，试分别求出1Y和2Y的熵1YH和2YH。解BABAEBAXDXXEBBDXBXBXDXXPXPXHAALOGLOG32LOG92LNLOG2LOGLOGLOG3302022由于1DXXP，因此33BA，因此3LOGLOGLOG32AEXH当01KKXY时，11YX，因此3LOGLOGLOG321LOG1AEXHEXHYH当XY22时，211YX，因此23LOGLOGLOG3221LOG1AEXHEXHYH【44】设给定两随机变量1X和2X，它们的联合概率密度为221222121XXEXXPP时有010050SHNIPIA式中，SH是信源的熵。（2）试求当0NN时典型序列集NGE中含有的信源序列个数。解（1）该信源的信源熵为8110LOGIISPSPSH比特/符号自信息的方差为4715081104LOG4134LOG4322222SHSIESIDII根据等长码编码定理，我们知道DEA1SHNIPI根据给定条件可知，050E，990D。而2EDNSIDI因此519099005047150220DEISIDN取1910N。（2）E典型序列中信源序列个数取值范围为221EEED成立，即,1111JIJIJJDNDDNDPRPPRPBABABABA因此有,11JIJJIJDDDDPRPBABABABA一般情况下，211PP，因此有,JIJDDBABA成立，而这即为最小距离译码规则。【66】某一信道，其输入X的符号集为1,21,0，输出Y的符号集为1,0，信道矩阵为10212101P现有四个消息的信源通过这信道传输（消息等概率出现）。若对信源进行编码，我们选这样一种码21,21,21XXC，10或IX（2,1I）其码长为4N，并选取这样的译码规则21,21,214321YYYYYYF（1）这样编码后信道的信息传输率等于多少（2）证明在选用的译码规则下，对所有码字0EP。解输入码字不同的个数共有4个，因此编码后信道的信息传输率为2144LOGR比特/码符号21210021210121211021211100001/400000011/400000101/400000111/4000010001/400010101/400011001/400011101/4001000001/401001001/401010001/401011001/4011000001/411010001/411100001/411110001/4可以看出，通过上述译码，对每一个输出都有一个输入与其对应，通过计算，可得其平均错误概率0EP。【67】考虑一个码长为4的二元码，其码字为00001W，00112W，11003W，11114W。假设码字送入一个二元对称信道（其单符号错误概率为P，且010P。因此完成上述编码的概率分布为311P12PP143PPP，而平均码长NTLC，NTLC，可得TT（2）当1A时，所有码字的码长相等，均为KLI；当2A时，所有码字的码长相等，均为1KLI；而当21A时，信源符号个数是位于K2至12K之间的某正整数，反应在码树上，应是一些长度为K的节点上生出分枝，作为长度为1K的码字（第（3）小题中所说的码长要么是KL1，要么是1KL）。设码长为K的节点数为X，则码长为1K的节点的分枝数一定为22XK，而码字的总个数为KKKAXXX22221因此有1222222221KKKKKKILILXXXXRII（3）已在第（2）小题中加以说明，此处略。（4）根据第（2）小题中的分析可知1KL，且有KAVU2UVK221解得KKAU2211121222KKKAAV编码后的平均码长为AKAKAAAKAKALKKKK22221211222111【89】现有一幅已离散量化后的图像，图像的灰度量化分成8级，见下表。表中数字为相应像素上的灰度级。1111111111111111111111111111111111111111222222222222222223333333333444444444455555556666667777788888另有一无损无噪二元信道，单位时间（秒）内传输100个二元符号。（1）现将图像通过给定的信道传输，不考虑图像的任何统计特性，并采用二元等长码，问需要多长时间才能传完这幅图像（2）若考虑图像的统计特性（不考虑图像的像素之间的依赖性），求此图像的信源熵SH，并对灰度级进行霍夫曼最佳二元编码，问平均每个像素需用多少二元码符号来表示这时需多少时间才能传送完这幅图像（3）从理论上简要说明这幅图像还可以压缩，而且平均每个像素所需的二元码符号数可以小于SH比特。解（1）采用二元等长码，不考虑信源符号的统计特性，平均每个灰度需要3位二进制表示，在1010的图像上，共需300位二进制表示，以每秒传输100位计算，共需3秒钟传输。（2）统计图像中各灰度级的出现次数12345678401710107655如果考虑信源符号的统计特性，对上述灰度级进行编码，如下图所示。得如下码字12345678401710107655010010101011110011011110111113444444平均码长为632443051040L在1010的图像上，共需263位二进制表示，以每秒传输100位计算，共需263秒钟传输完。（3）在计算（2）小题时，并未考虑像素灰度级之间的依赖关系，例如，灰度1后只能跟灰度1和2，并未有其他灰度值。这样得到的信源熵SHH，而根据香农第一定理，当对信源进行扩展时，其平均码长L逼近于SHH，因此，该图像可以进一步压缩，平均每个像素所需要的二元码符号数SHHL。【810】有一个含有8个消息的无记忆信源，其概率各自为02,015,015,01,01,01,01,01。试编成两种三元非延长码，使它们的平均码长相同，但具有不同的码长的方差，并计算平均码长和方差，说明哪一种码更实用些。解进行三元编码，需增补一个概率为0的信源符号，两种编码方法如下所示。图1图2平均码长为26060303020L编码1的码方差为40101020221LLEIS0222LLEIS虽然两种编码的平均码长相同，但由于编码2的码方差较小，因此编码2更实用一些。【811】设有两个信源X和Y如下01010150170180190207654321XXXXXXXXPX010020020040070070140140490987654321YYYYYYYYYYPY（1）分别用霍夫曼码编成二元变长惟一可译码，并计算其编码效率；（2）分别用香农编码法编成二元变长惟一可译码，并计算编码效率；（3）分别用费诺编码方法编成二元变长惟一可译码，并计算编码效率；（4）从X、Y两种不同信源来比较这三种编码方法的优缺点。解第一个信源信源熵为608682LOGXPXPXH比特对其进行二元霍夫曼编码，如下所示0201901801701501001011026035039061010101010001100011010111011101111平均码长为722411035502390L码符号/信源符号编码效率为959070LXHH对其进行费诺编码，如下所示0002001001900110180111001701100150111001011110011111平均码长为742440450340337040L码符号/信源符号编码效率为952070LXHH对其进行香农编码，如下所示。概率码长累积概率分布二进制小数码字023000000019302000110011001100101830390011000111101011017305701001000111101000153074010111101011110101408901110001111011110001709901111110101111111111其平均码长为143070403890L码符号/信源符号编码效率为830790LXHH第二个信源信源熵为313562LOGYPYPYH比特对其进行二元霍夫曼编码，如下所示。平均码长为3326030502041803280490L码符号/信源符号编码效率为992940LYHH对其进行费诺编码，如下所示。0049010001401010140111000070110100701111000401111000201111100020111111001111111平均码长为3326030502041803280490L码符号/信源符号编码效率为992940LYHH对其进行香农编码，如下所示概率码长累积概率分布二进制小数码字049200000014304900111110101110110143063010100001010010100740770110001010001110000740840110101110000110100450910111010001111111010026095011110011001111110000260970111110000101111110001709901111110101111111110平均码长为892701060405040414032802490L编码效率为800540LYHH从上述编码中可以看出，霍夫曼编码的平均码长最短，编码效率最高，香农编码的平均码长最长，其编码效率最低，费诺编码居中。【812】信源符号集,2,1QAK，其概率分布为QPPP,21K。采用以下方法对信源符号进行编码。首先将概率分布按大小顺序排列QPPPK21，定义累积分布函数11IKKIPFIF是所有小于I符号的概率和。于是符号I的码字是取IF的二进制数的小数IL位，若有尾数就进位到第IL位，其中IIPL1LOG。（1）证明这样编得的码是即时码；（2）证明1SHLSH；（3）对于概率分布为05,025,0125,0125的信源进行编码，求其各码字；（4）（3）中所得的码是否与此信源的霍夫曼码正巧完全一致试说明这种完全一致的一般原理。解（1）按照所取的累积分布函数，我们得知0ISFC且二者的差必然小于第IL上的权值，因此有ILISFC20而IIPL1LOG，得11LOG1LOGIIIPLP，即2ILSPI，可得ILIISFCSF2画出累积分布函数的图像，如下图所示。可以发现，最后所得的码字取值区间并无重叠，根据二进制小数的特性，可得不重叠的区间其二进制小数的前缀部分是不同的，所以，这样得到的码一定满足变长码的前缀条件，因此是即时码。（2）根据IIPL1LOG，得11LOG1LOGIIIPLP，因此有IIIIIIIPPPLPPP1LOG1LOG两边进行统计平均得1SHLSH（3）对概率分布为05,025,0125,0125的信源进行编码，过程如下码字概率码长累积分布二进制小数00510001002520501110012530750111110125308750111（4）该码字与此信源的霍夫曼编码完全一致，即它本身构造成了该信源的紧致码，其原因是其码长恰好为1LOGISP，信源的先验概率恰好为2的幂次方分布，构成了香农第一定理下限成立的条件，因此必然可以构造出紧致码。【814】已知二元信源1,0，其810P，871P，试对其进行算术编码，并计算此序列的平均码长11111110111110解序列的发生概率为21220121818711101111111011PPSP在编码时应对该序列的码长值为931183278LOG121LOGSPLI码字在码树上的相对位置如下图所示因此可得码序列的累积分布函数为906312139281878711111111111011111111111128PPSF将累积分布函数变为二进