信息论+傅祖芸+答案.pdf
- 文档编号:14654971
- 上传时间:2023-06-25
- 格式:PDF
- 页数:91
- 大小:942.35KB
信息论+傅祖芸+答案.pdf
《信息论+傅祖芸+答案.pdf》由会员分享,可在线阅读,更多相关《信息论+傅祖芸+答案.pdf(91页珍藏版)》请在冰点文库上搜索。
第二章课后习题第二章课后习题【2.1】设有12枚同值硬币,其中有一枚为假币。
只知道假币的重量与真币的重量不同,但不知究竟是重还是轻。
现用比较天平左右两边轻重的方法来测量。
为了在天平上称出哪一枚是假币,试问至少必须称多少次?
解:
从信息论的角度看,“12枚硬币中,某一枚为假币”该事件发生的概率为121=P;“假币的重量比真的轻,或重”该事件发生的概率为21=P;为确定哪一枚是假币,即要消除上述两事件的联合不确定性,由于二者是独立的,因此有24log2log12log=+=I比特而用天平称时,有三种可能性:
重、轻、相等,三者是等概率的,均为31=P,因此天平每一次消除的不确定性为3log=I比特因此,必须称的次数为9.23log24log21=II次因此,至少需称3次。
【延伸】如何测量?
分3堆,每堆4枚,经过3次测量能否测出哪一枚为假币。
【2.2】同时扔一对均匀的骰子,当得知“两骰子面朝上点数之和为2”或“面朝上点数之和为8”或“两骰子面朝上点数是3和4”时,试问这三种情况分别获得多少信息量?
解:
“两骰子总点数之和为2”有一种可能,即两骰子的点数各为1,由于二者是独立的,因此该种情况发生的概率为3616161=P,该事件的信息量为:
17.536log=I比特“两骰子总点数之和为8”共有如下可能:
2和6、3和5、4和4、5和3、6和2,概率为36556161=P,因此该事件的信息量为:
85.2536log=I比特“两骰子面朝上点数是3和4”的可能性有两种:
3和4、4和3,概率为18126161=P,因此该事件的信息量为:
17.418log=I比特【2.3】如果你在不知道今天是星期几的情况下问你的朋友“明天星期几?
”则答案中含有多少信息量?
如果你在已知今天是星期四的情况下提出同样的问题,则答案中你能获得多少信息量(假设已知星期一至星期日的顺序)?
解:
如果不知今天星期几时问的话,答案可能有七种可能性,每一种都是等概率的,均为71=P,因此此时从答案中获得的信息量为807.27log=I比特而当已知今天星期几时问同样的问题,其可能性只有一种,即发生的概率为1,此时获得的信息量为0比特。
【2.4】居住某地区的女孩中有25%是大学生,在女大学生中有75%是身高1.6米以上的,而女孩中身高1.6米以上的占总数一半。
假如我们得知“身高1.6米以上的某女孩是大学生”的消息,问获得多少信息量?
解:
设A表示女孩是大学生,25.0)(=AP;B表示女孩身高1.6米以上,75.0)|(=ABP,5.0)(=BP“身高1.6米以上的某女孩是大学生”的发生概率为375.05.075.025.0)()|()()()()|(=BPABPAPBPABPBAP已知该事件所能获得的信息量为415.1375.01log=I比特【2.5】设离散无记忆信源=8/14/14/18/33210)(4321aaaaxPX,其发出的消息为(202120130213001203210110321010021032011223210),求
(1)此消息的自信息是多少?
(2)在此消息中平均每个符号携带的信息量是多少?
解:
信源是无记忆的,因此,发出的各消息之间是互相独立的,此时发出的消息的自信息即为各消息的自信息之和。
根据已知条件,发出各消息所包含的信息量分别为:
415.138log)0(0=aI比特24log)1(1=aI比特24log)2(2=aI比特38log)3(3=aI比特在发出的消息中,共有14个“0”符号,13个“1”符号,12个“2”符号,6个“3”符号,则得到消息的自信息为:
81.8736212213415.114+=I比特45个符号共携带87.81比特的信息量,平均每个符号携带的信息量为95.14581.87=I比特/符号注意:
消息中平均每个符号携带的信息量有别于离散平均无记忆信源平均每个符号携带的信息量,后者是信息熵,可计算得=91.1)(log)()(xPxPXH比特/符号【2.6】如有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平均自信息量为58.548log)(=AH比特/符号
(2)已知质点A已落入,求B落入的平均自信息量,即求)|(ABH。
A已落入,B落入的格可能有47个,条件概率)|(ijabP均为471。
平均自信息量为55.547log)|(log)|()()|(481471=ijijijiabPabPaPABH比特/符号(3)质点A和B同时落入的平均自信息量为13.11)|()()(=+=ABHAHABH比特/符号【2.7】从大量统计资料知道,男性中红绿色盲的发病率为7%,女性发病率为0.5%,如果你问一位男同志:
“你是否是红绿色盲?
”,他的回答可能是“是”,也可能是“否”,问这两个回答中各含有多少信息量?
平均每个回答中含有多少信息量?
如果你问一位女同志,则答案中含有的平均自信息量是多少?
解:
男同志红绿色盲的概率空间为:
=93.007.021aaPX问男同志回答“是”所获昨的信息量为:
836.307.01log=I比特/符号问男同志回答“否”所获得的信息量为:
105.093.01log=I比特/符号男同志平均每个回答中含有的信息量为366.0)(log)()(=xPxPXH比特/符号同样,女同志红绿色盲的概率空间为=995.0005.0Y21bbP问女同志回答“是”所获昨的信息量为:
64.7005.01log=I比特/符号问女同志回答“否”所获昨的信息量为:
31023.7995.01log=I比特/符号女同志平均每个回答中含有的信息量为045.0)(log)()(=xPxPYH比特/符号【2.8】设信源=17.016.017.018.019.02.0)(654321aaaaaaxPX,求此信源的熵,并解释为什么6log)(XH,不满足信源熵的极值性。
解:
6log65.2)(log)()(=xPxPXH原因是给定的信源空间不满足概率空间的完备集这一特性,因此不满足极值条件。
【2.9】设离散无记忆信源S其符号集,.,21qaaaA=,知其相应的概率分别为),.,(21qPPP。
设另一离散无记忆信源S,其符号集为S信源符号集的两倍,2,.,2,1,qiaAi=,并且各符号的概率分布满足qqqiPPqiPPiiii2,.,2,1,.,2,1)1(+=试写出信源S的信息熵与信源S的信息熵的关系。
解:
)1,()()(log)1log()1(logloglog)1()1log()1(log)1log()1()(log)()(+=+=HSHSHPPPPPPPPPPxPxPSHiiiiiiiiii【2.10】设有一概率空间,其概率分布为,.,21qppp,并有21pp。
若取=11pp,+=22pp,其中2120ppx
(2)拉普拉斯概率密度函数,xexp=21)(,0,+=KKXY,XY22=,试分别求出1Y和2Y的熵)(1Yh和)(2Yh。
解:
babaebaxdxxebbdxbxbxdxxpxpXhaaloglog32log92lnlog2loglog)(log)()(3302022=由于1)(=dxxp,因此33=ba,因此3logloglog32)(+=aeXh当)0(1+=KKXY时,11=YX,因此3logloglog32)(1log)()(1+=aeXhEXhYh当XY22=时,211=YX,因此23logloglog32)(21log)()(1aeXhEXhYh+=【4.4】设给定两随机变量1X和2X,它们的联合概率密度为221222121)(xxexxp+=时有01.005.0)()(SHNIPi式中,)(SH是信源的熵。
(2)试求当0NN=时典型序列集NG中含有的信源序列个数。
解:
(1)该信源的信源熵为811.0)(log)()(=iispspSH比特/符号自信息的方差为4715.0811.04log4134log43)()()(22222=+=SHsIEsIDii根据等长码编码定理,我们知道1)()(SHNIPi根据给定条件可知,05.0=,99.0=。
而2)(NsIDi=因此5.19099.0*05.04715.0)(220=isIDN取1910=N。
(2)典型序列中信源序列个数取值范围为:
)()(22)1(+SHNNSHNG代入上述数值得451.164351.1452201.0NG【5.2】有一信源,它有六个可能的输出,其概率分布如下表所示,表中给出了对应的码A、B、C、D、E和F。
表5.2消息)(iaPABCDEF1a1/2000000002a1/4001011010101003a1/1601001111011011001014a1/1601101111110111011011105a1/161000111111110101111101116a1/1610101111111111011011111011
(1)求这些码中哪些是惟一可译码;
(2)求哪些码是非延长码(即时码);(3)求对所有惟一可译码求出其平均码长L。
解:
(1)上述码字中,A为等长码,且为非奇异码,因此码A为惟一可译码;码B中,根据惟一可译码的判断方法,可求得其尾随后缀集合为11111,1111,111,11,1,且其中任何后缀均不为码字,因此码B是惟一可译码。
码C为逗点码,因此码C为惟一可译码;码D不是惟一可译码,因为其尾随后缀集合中包含0,而0又是码字;码E的尾随后缀集合为空集,因此码E是惟一可译码;码F不是惟一可译码,因为其尾随后缀集合中包含0,而0又是码字,因此F不是惟一可译码。
(2)码A、C、E是即时码(非延长码)(3)码A的平均码长为3;码B的平均码长为2.125;码C的平均码长为2.125;码F的平均码长为2。
【5.3】证明定理5.6,若存在一个码长为qlll,21K的惟一可译码,则一定存在具有相同码长的即时码。
证明:
如果存在码长为qlll,21K的惟一可译码,则qlll,21K必定满足如下不等式11=qilir而如果码长qlll,21K满足上述不等式,根据Kraft不等式构造即时码的方法,可以构造出码长为qlll,21K的即时码,具体构造过程略,参照课本相关定理。
【5.4】设信源=621621)(pppssssPSLL将此信源编码为r元惟一可译变长码(即码符号集,2,1rXK=),其对应的码长为)3,2,3,2,1,1(),(621=lllK,求r值的下限。
解:
如果要构造出惟一可译变长码,则相关码长必须满足11=qilir,代入上式有21321+rrr当2=r时,上述不等式不成立;当3=r时,成立。
因此r值的下限为3。
【5.5】若有一信源=2.08.0)(21sssPS每秒钟发出2.66个信源符号。
将此信源的输出符号送入某一个二元信道中进行传输(假设信道是无噪无损的),而信道每秒钟只传递两个二元符号。
试问信源不通过编码能否直接与信道连接?
若通过适当编码能否中在信道中进行无失真传输?
若能连接,试说明如何编码并说明原因。
解:
如果不通过编码,即信道的两个码符号对应两个信源符号,而信道传输码符号的速度小于信源发出信源符号的速度,因此势必会造成信源符号的堆积,因此不通过编码是无法将信源与信道直接连接。
信源平均每秒发出的信息量为921.1)(log)(*66.2)(*66.2=sPsPSH比特/秒而该信道的信道容量为1比特/符号,平均每秒能够传输的最大信息量为2比特,因此通过编码可以实现二者的连接。
若要连接,需要对扩展信源的信源符号进行编码,目的是使送入信道的信息量小于信道每秒能接收的最大信息量(或使每秒钟编码后送入信道的码符号个数必须小于信道所能接受的最大码符号个数),具体编码方法将在第八章进行。
【5.6】设某无记忆二元信源,概率1.0)1(1=Pp,9.0)0(0=Pp,采用下述游程编码方案:
第一步,根据0的游程长度编成8个码字,第二步,将8个码字变换成二元变长码,如下表所示。
表5.6信源符号序列中间码二元码字10100100010000100000100000010000000100000000s0s1s2s3s4s5s6s7s8100010011010101111001101111011110
(1)试问最后的二元变长码是否是否是惟一可译码;
(2)试求中间码对应的信源序列的平均长度1L;(3)试求中间码对应的二元变长码码字的平均长度2L;(4)计算比值12/LL,解释它的意义,并计算这种游程编码的编码效率;解:
(1)该码是非延长码,因此肯定是惟一可译码;
(2)由于信源本身是无记忆的,因此各信源符号的概率如下表所示。
信源符号序列概率中间码二元码字101001000100001000001000000100000001000000000.10.090.0810.07290.065610.0590490.05314410.047829690.43046721s0s1s2s3s4s5s6s7s8100010011010101111001101111011110因此信源序列的平均长度为695328.5)(1=iilspL(3)中间码对应的二元变长码码长为708598.2)(2=iilspL(4)4756.012=LL,反应了每个信源符号需要的二元码符号数。
平均每个信源符号的信息量为469.01.0log1.09.0log9.0)(=SH编码效率为986.0/)(12=LLSH第六章课后习题第六章课后习题【6.1】设有一离散信道,其信道传递矩阵为216131312161613121并设21)(1=xP,41)()(32=xPxP,试分别按最小错误概率准则与最大似然译码准则确定译码规则,并计算相应的平均错误概率。
解:
假设输入符号集和输出符号集分别为,321xxx和,321yyy。
按照最大似然译码规则,选择如下:
332211)()()(xyFxyFxyF=平均错误概率为:
21613121613121)|()(*=+=XyxYijiEjxyPxPP对应的如果需要按照最小错误概率译码,需要首先求出其联合概率矩阵:
81241121121812411216141最小错误概率译码规则应如下:
331211)()()(xyFxyFxyF=此时错误概率为:
241124112112181241121),()|()(*=+=XyxYjiXyxYijiEjjyxPxyPxPP对应的对应的【6.2】计算码长5=n的二元重复码的译码错误概率。
假设无记忆二元对称信道中正确传递概率为p,错误传递概率为pp=1。
此码能检测出多少错误?
又能纠正多少错误。
若01.0=p,译码错误概率是多大?
解:
将0和1编成00000和11111后,当传输过程中产生1位至4位错误时均可检测出,但产生5位错误却无法检测出,同时,如果输入等概率分布,当传输过程中存在1位错误以及2位错误时,可以自动纠正。
此时的错误概率为:
错3位的概率为:
2335ppC;错4位的概率为:
ppC445;错5位的概率为:
555pC因此,译码错误概率为:
555544523351002961.1=+pCppCppC【6.3】设某二元码为00111,10010,01001,11100=C
(1)计算此码的最小距离mind;
(2)计算此码的码率R,假设码字等概率分布;(3)采用最小距离译码准则,试问接收序列10000,01100和00100应译成什么码字?
(4)此码能纠正几位码元的错误?
解:
(1)此码字的最小距离3min=d;
(2)此码字的码率52log=nMR比特/码符号;(3)采用最小距离译码,10000应译成10010;01100应译成11100;00100译成11100、00111均可;(4)由于1123min+=d,因此此码能纠正1位码元的错误。
【6.4】设无记忆二元对称信道的正确传递概率为p,错误传递概率为ppp=1。
令长度为n的M个二元码字)(21niiiiaaaL=,其中1,0kia(码字为等概率分布),接收的二元序列为)(21njjjjbbbL=,1,0kjb。
试证明:
采用最小距离译码准则可使平均译码错误概率EP达到最小,并且=iDnDEjjppMP*11证明:
构造函数xnxppxf=)(,有0lnln)(成立,即()(),(),(),(),(1111*jijijjDnDDnDprpprp因此有(),(),(),(),(*11jijjijDDDDprp一般情况下,211=pp,因此有),(),(*jijDD成立,而这即为最小距离译码规则。
【6.6】某一信道,其输入X的符号集为1,21,0,输出Y的符号集为1,0,信道矩阵为=10212101P现有四个消息的信源通过这信道传输(消息等概率出现)。
若对信源进行编码,我们选这样一种码)21,21,(:
21xxC,10或ix(2,1=i)其码长为4=n,并选取这样的译码规则)21,21,(),(214321yyyyyyf=
(1)这样编码后信道的信息传输率等于多少?
(2)证明在选用的译码规则下,对所有码字0=EP。
解:
输入码字不同的个数共有4个,因此编码后信道的信息传输率为2144log=R比特/码符号21210021210121211021211100001/400000011/400000101/400000111/4000010001/400010101/400011001/400011101/4001000001/401001001/401010001/401011001/4011000001/411010001/411100001/411110001/4可以看出,通过上述译码,对每一个输出都有一个输入与其对应,通过计算,可得其平均错误概率0=EP。
【6.7】考虑一个码长为4的二元码,其码字为00001=W,00112=W,11003=W,11114=W。
假设码字送入一个二元对称信道(其单符号错误概率为p,且01.0p),而码字输入是不等概率的,其概率为21)(1=WP,81)(2=WP,81)(3=WP,41)(4=WP试找出一种译码规则使平均错误概率EP最小。
解:
设接收码字为iV,则一共可能有16种不同的码字序列,而),(),()|(ijijWVDWVDnijppWVP=列出所有的输出,如下表所示。
iW0000001111001111接收码字jV)|(211WVPj)|(812WVPj)|(813WVPj)|(414WVPj目标序列0000421p2281pp2281pp441p00000001pp321pp381381pp341pp00000010pp321pp381381pp341pp000000112221pp481p481p2241pp00110100pp321381pppp381341pp000001012221pp2281pp2281pp2241pp000001102221pp2281pp2281pp2241pp00000111321pppp381381pppp34111111000pp321381pppp381341pp000010012221pp2281pp2281pp2241pp000010102221pp2281pp2281pp2241pp00001011321pppp381381pppp341111111002221pp481p481p2241pp11001101321pp381pppp381pp34111111110321pp381pppp381pp34111111111421p2281pp2281pp441p1111【6.8】设一种离散无记忆信道,其信道矩阵为=21000212121000021210000212100002121P
(1)计算信道容量C;
(2)找出一个码长为2的重复码,其信息传输率为5log21(即5个码字)。
如果按最大似然译码准则设计译码器,求译码器输出端的平均错误概率EP(输入码字等概率)。
(3)有无可能存在一个码长为2的码,使0)(=ieP(5,4,3,2,1=i),即0=EP,如存在的话请找出来。
解:
(1)观察该信道,其每一行数据都是第一行数据的置换,每一列数据都是第一列数据的置换,因此该信道是对称信道,其信道容量为:
322.115log)0,0,0,21,21(log=HrC比特/码符号
(2)假设信道中的输入符号集和输出符号集为0,1,2,3,4,进行二次重复码,编得00、11、22、33、44其码率为5log21)(=nSHR比特/码符号。
此时,输出方可能有25种可能性,进行最大似然译码,如下表所示。
错误概率为41414141414151=+=EP输入序列输出序列0011223344译码001/40001/400/44011/40000000200000均可0300000均可0400001/444101/4000000111/41/400000/111201/4000111300000均可1400000均可2000000均可2101/4000112201/41/40011/2223001/400222400000均可3000000均可3100000均可32001/4002233001/41/4022/33340001/40334000001/4444100000均可4200000均可430001/4033440001/41/433/44(3)将25个长度为2的序列排成一方块图,如下所示:
000102030400101112131410202122232420303132333430404142434440000102030400为使平均错误概率为0,须充分利用译码规则,假如选择了一个码字,则在接收序列中与这个码字对应的条件概率不为零的肯定不
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息论 傅祖芸 答案