信息科学基础2012B卷及答案

B卷（共13页）第1页河北科技大学2012——2013学年第一学期《信息科学基础》试卷（B′）学院理学院班级姓名学号题号一二总分得分一、简答题（共8题，每题5分）1.设有一离散无记忆信道，其信道矩阵为111236111623111362P，若11()2px，231()()4pxpx。试求最佳译码时的平均错误概率。2.设某二元码书C={111000，001011，010110，101110}，①假设码字等概率分布，计算此码的编码效率？②采用最小距离译码准则，当接收序列为110110时，应译成什么码字？得分B卷（共13页）第2页3.解释等长信源编码定理和无失真变长信源编码定理，说明对于等长码和变长码，最佳码的每符号平均码长最小为多少？编码效率最高可达多少？4.有一信源，它有6个可能的输出，其概率分布如下表所示，表中给出了对应的码A，B，C，D，E和F。消息()ipaABCDEF1a1/2000000002a1/4001011010101003a1/1601001111011011001014a1/1601101111110111011011105a1/161000111111110101111001116a1/1610101111111111011011111011(1)求这些码中哪些是唯一可译码；(2)求哪些是非延长码（即时码）；(3)对所有唯一可译码求出其平均码长L。B卷（共13页）第3页5.求以下三个信道的信道容量：，，6.设二进制对称信道的传递矩阵为21331233（1）若P(0)=3/4,P(1)=1/4,求H(X)、H(X/Y)、H(Y/X)和I(X；Y)；（2）求该信道的信道容量及其达到信道容量的输入概率分布。B卷（共13页）第4页7.有一个马尔可夫信源，已知转移概率为112(/)3pSS，211(/)3pSS，12(/)1pSS，22(/)0pSS。试画出状态转移图，并求出信源熵。8.居住某一地区的女孩中有25%是大学生，在女大学生中有75%是身高1.6米以上的，而女孩中身高1.6米以上的占总数一半。假如我们得知“身高1.6米以上的女孩是大学生”的消息，问获得多少信息量？二、综合题（共6题，每题10分）1.设消息集合共有7个元素，它们分别被编码为{a,c,ad,abb,bad,deb,bbcde},试利用惟一可译码判别准则判定它是否为惟一可译码。得分B卷（共13页）第5页2、设输入符号集为X={0,1},输出符号集为Y={0,1}。定义失真函数为d(0,0)=d(1,1)=0,d(0,1)=d(1,0)=1,试求失真矩阵D.3.设有一离散无记忆信源，其概率空间为120.60.4XxxP，它们通过一干扰信道，信道输出端的接受符号集为12[,]Yyy，信道传递概率如图所示。求：（1）信源X中事件1x和2x分别含有的自信息；（2）收到信息(1,2)jyj后，获得的关于(1,2)ixi的信息量；（3）信源X和信源Y的信息熵；B卷（共13页）第6页（4）信道疑义度(/)HXY和噪声熵(/)HYX；（5）接收到信息Y后获得的平均互信息。4.设某齐次马氏链的一步转移概率矩阵为012001020qpqpqp试求：（1）该马氏链的二步转移概率矩阵；（2）平稳后状态“0”，“1”，“2”的极限概率。B卷（共13页）第7页5.二元平稳马氏链，已知P（0/0）=0.8，P（1/1）=0.7，求：每三个符号合成一个来编二进制Huffman码,试建立新信源的模型，给出编码结果。6.某一信道，其输入X的符号集为10,,12，输入Y的符号集为0,1,信道矩阵为10112201P，现有4个消息的信源通过这信道传输（消息等概率出现），若对信源进行编码，我们选这样一种码，1211:{(,,,)}22Cxx01(1,2)ixi或其码长为4n。并选取这样的译码规则12341211(,,,)(,,,)22fyyyyyy（1）这样编码后信息传输率等于多少？（2）证明在选用的译码规则下，对所有码字有0EPB卷（共13页）第8页河北科技大学2012——2013学年第一学期《信息科学基础》答案（B′）一、简答题（共8题，每题5分）1．答：用极大似然译码规则译码，先写出输入输出的联合概率分布1114612111(,)2481211112248PXY平均译码错误概率为1124Ep2.答：由定义，信源的熵621()()log()iiiHXpapa222222220.2log0.20.19log0.190.18log0.180.17log0.170.16log0.160.17log0.17log6.282.64log6信源的概率分布要求满足()1ipa，而此题中()1.071ipa。即各种可能发生的情况下，概率之和大于“1”，在实际情况下这是不可能发生的。3.答：等长信源编码定理：对于任意，只要，则当L足够长时必可使译码差错。变长信源编码定理：只要，一定存在一种无失真编码。等长码和变长码的最小平均码长均为，编码效率最B卷（共13页）第9页高可达100%。4.答：（1）惟一可译码有A，B和C（2）即时码有A和C（3）3()AL码元/信源符号同理得B17()8L码元/信源符号，C17()8L码元/信源符号5.答：P1为一一对应确定信道，因此有。P2为具有归并性能的信道，因此有。P3为具有发散性能的信道，因此有。6.答：联合概率矩阵1124P11126XY，边缘概率分布为P(0)(1)Xpp75P1212Y（1）H(X)=21(0)log(0)(1)log(1)0.811()ppppbit，又因为信道传递矩阵/21331233YXP，故2211(/)()log(/)0.918()iiiiijHYXpxypyxbit()0.98()HYbit，(/)(,)()0.749()HXYHXYHYbit(;)()(/)0.06()IXYHXHXYbit（2）设XPww，其中2211(/)()log(/)0.918()iiiiijHYXpxypyxbit又由最大熵定理得2()loglog21()HYMbit，所以有(;)()(/)0.082()IXYHYHYXbitB卷（共13页）第10页故()max{(;)}0.082()pxCIXYbit，而上述等号成立的条件为12()()pypy又因为21123333YP，所以须21123333，12ww因此达到信道容量时，信道输入概率为1122XP7.答：状态转移矩阵213310P272992133P，故该马尔可夫信源是遍历的。设12由WPW即121122313121WW求得123414WW所以信源熵为21()()(/)=0.688bit/iiiHXpSHXS（符号）8.答：设A表示“大学生”这一事件，B表示“身高1.60m以上”这一事件，则()0.25pA，()0.5pB，(/)0.75pBA()()(/)(/)0.375()()pABpApBApABpBpB，2211(/)loglog1.42()(/)0.375IABbitpAB二、综合题（共6题，每题10分）1.答：S0S1S2S3S4S5S6S7adebdebB卷（共13页）第11页cbbcdedebadabbbadaddebbbcdebcdeS1到S7中都不包含S0中的元素，因此，S0是惟一可译码。2.答：0110D3.答：答：（1）1122()log()0.737()()log()1.322()IxpxbitIxpxbit（2）11111211221221122222(/)(;)log0.059()()(/)(;)log0.263()()(/)(;)log0.093()()(/)(;)log0.322()()pyxIxybitpypyxIxybitpypyxIxybitpypyxIxybitpy（3）信源X和信源Y的信息熵21()()log()0.97()iiiHXpxpxbit21()()log()0.722()jjjHYpypybit（4）信道疑义度(/)(,)()()(/)()0.963()HXYHXYHYHXHYXHYbitB卷（共13页）第12页（5）平均互信息(,)()(/)0.007()IXYHXHXYbit4.答：（1）由一步转移概率矩阵与二步转移概率矩阵的公式2PPP得22222222qpqpqpPqpqpqpqppq（2）设平稳状态123{,,}，马尔可夫信源性质知WPW，即1211322331231qWqWWpWqWWpWp求解得稳态后的概率为21222232111qWpppqWpppWpp5.答：由P（0/0）=0.8，P（1/1）=0.7,得极限概率：p(0)=0.6,p(1)=0.4新信源共8个序列，各序列的概率为信源模型为0000010100111001011101110.3840.0960.0360.0840.0960.0240.0840.196一种编码结果（依信源模型中的序列次序）为0，001，10101,1101，1011，00101，0011,111.6.答：(1)对信源四个消息进行编码，选择码长4n，这组码为1211:{(,,,)}22Cxx01(1,2)ixi或所以，码字为11111111:{00,01,10,11}22222222CB卷（共13页）第13页编码后信息传输率()12HSRL（bit/码元符号）（2）设接收序列1234()yyyy，{0,1}(1,2,3,4)iyi，根据信道的传输特性，接受序列共有16个，正好分成4个互不相交的子集，每一个码字只传输到其中对应的一个子集：1341100(00)22yy，2341101(01)22yy，3341110(10)22yy，4341111(11)22yy34,{0,1}yy具体传输信道如下：000000010010001101000101011001111000100110101011110011011110111111001111000000000000224444110111110000000000002244441110111100000000000022444411111111000000000000224444所以根据选取的译码规则12341211()()22fyyyyyy正好将接受序列译成所发送的码字。可计算对于每个码字引起的错误概率()[(/),()]0iEiiYppF(1,2,3,4)i所以有()()0iEiECPpp