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

1、河北科技大学20122013学年第一学期信息科学基础试卷（B）学院理学院班级 姓名 学号1.得分一、简答题（共8题，每题5分）设有一离散无记忆信道，其信道矩阵为P =121613131216161312，若 p(x )=，12题号一总分得分p（x ） = p（x ） = 4。试求最佳译码时的平均错误概率。234设某二元码书 C=111000，001011，010110，101110，假设码字等概率分布，计算此码的编码效率？采用最小距离译码准则，当接收序列为110110时，应译成什么码字?解释等长信源编码定理和无失真变长信源编码定理，说明对于等长码和变长 码，最佳码的每符号平均码长最小为多少？编

2、码效率最高可达多少？有一信源，它有6个可能的输出，其概率分布如下表所示，表中给出了对应 的码 A，B，C，D，E 和 F。消息P (a.)IABCDEFa11/200000000a21/400101101010100a31/160100111101101100101a41/160110111111011101101110a51/16100011111111010111100111a61/1610101111111111011011111011求这些码中哪些是唯一可译码；求哪些是非延长码(即时码)；对所有唯一可译码求出其平均码长L求以下三个信道的信道容量:,P3Q.10.20.30.400000

3、000000.30.700000000000.40.20.10.36.设二进制对称信道的传递矩阵为2313（1）若 P（0）=3/4,P（1）二1/4，求 H（X）、H（X/Y）、H（Y/X）和 I（X； Y）；（2）求该信道的信道容量及其达到信道容量的输入概率分布。7.有一个马尔可夫信源，已知转移概率为p (S / S) = -, p(S / S )= 113213p(S /S ) = 1, p(S /S ) = 0。试画出状态转移图，并求出信源熵。 12228.居住某一地区的女孩中有25%是大学生，在女大学生中有75%是身高1.6米以 上的，而女孩中身高1.6米以上的占总数一半。假如我们得

4、知“身高1.6米以上 的女孩是大学生”的消息，问获得多少信息量？得分二、综合题(共6题，每题10分)设消息集合共有7个元素，它们分别被编码为a,c, ad, abb,bad,deb, bbcde),试利用惟一可译码判别准则判定它是否为惟一可译码。2、设输入符号集为X=0,1,输出符号集为Y=0,1。定义失真函数为 d(0,0)=d(1,1)=0, d(0,1)=d(1,0)二1,试求失真矩阵 D. TX1 x x 1设有一离散无记忆信源，其概率空间为J、 0.J，它们通过一干扰信道，信道输出端的接受符号集为K =七,七，信道传递概率如图所示。求：(1)信源X中事件气和X2分别含有的自信息；收到

5、信息七(j = 1,2)后，获得的关于(，= 1,2)的信息量;信源X和信源Y的信息熵；（4）信道疑义度H（X/Y）和噪声熵H（Y/ X）；（5）接收到信息Y后获得的平均互信息。0 1 2设某齐次马氏链的一步转移概率矩阵为0勺p 0 1 q 0 p 21_ 0 q p试求：（1）该马氏链的二步转移概率矩阵；（2）平稳后状态“0”，“1”，“2”的极限概率。二元平稳马氏链，已知P (0/0) =0.8, P (1/1) =0.7，求：每三个符号合 成一个来编二进制Huffman码,试建立新信源的模型，给出编码结果。某一信道，其输入X的符号集为“，2,1；，输入Y的符号集为0,1 ，信道矩阵一1

6、0 -为P=11，现有4个消息的信源通过这信道传输(消息等概率出现)，若2 20 1对信源进行编码，我们选这样一种码，C:顷,x U,1)x = 0或1。= 1,2)12 2 2 i其码长为n = 4。并选取这样的译码规则f (y , y , y , y ) = (y , y J-J-)1 2 3 41 2 2 2这样编码后信息传输率等于多少？证明在选用的译码规则下，对所有码字有Pe = 0河北科技大学20122013学年第一学期信息科学基础答案（B）、 简答题（共8题，每题5分）答：用极大似然译码规则译码，先写出输入输出的联合概率分布122412平均译码错误概率为侦2412 24答：由定义，

7、信源的熵h( x)= p( a/% p(a)i=1=0.2log 0.2 - 0.19log 0.19 - 0.18log 0.18 0.17log 0.17 - 0.16log 0.16 - 0.17log 0.17 =log 6.282=2.64 堕6 信源的概率分布要求满足 p（气）=1，而此题中 p（a）=1.07 1。即各种可能发生的情况下，概率之和大于“ 1”，在实际情况下这是不可能发生的。答：等长信源编码定理：对于任意e0,S。，只要堕酬上丑）+ ，则勺箜1当L足够长时必可使译码差错亍。变长信源编码定理：只要一 陀好，一定丑(X)存在一种无失真编码。等长码和变长码的最小平均码长均

8、为1%酬，编码效率最高可达100%。答：（1）惟一可译码有A,B和（2）即时码有A和C（3）L =3（码元/信源符号） A17同理得可f码元/信源符号）,-17 一 Lc=疽码元/信源付答：P1为一一对应确定信道，因此有宓H透）=1性4=2况/符号。P2为具有归并性能的信道，因此有C2 H（Y）Mog23=1.5995切计符号P3为具有发散性能的信道，因此有GFaxH顷）=1箜技=1.5995切”符号6.答：联合概率矩阵P =：XV 1214，边缘概率分布为Px=p（0）6P (1)71212(1) H(X)= -p(0)log 2 p(0) - p(1)log1 p(1) = 0.811(b

9、it)，又因为信道传递矩阵 TOC o 1-5 h z 134 2P = 1 c ，故 H(Y / X) = -*p(xy )log p(y / x ) = 0.918(bit)Y / X12i ii i-一i=1 J =13 3H(Y) = 0.98(bit)，H(X / Y) = H(X, Y) H(Y) = 0.749(bit)I(X; Y) = H (X) - H(X / Y) = 0.06(bit)(2)设 P = w w 其中 H(Y/ X) = -* 2 p(x y )log p(y /x ) = 0.918(bit)X，i ii ii=1 J =1又由最大熵定理得H(Y) lo

10、gM = log2 2 = 1(bit)，所以有I(X; Y) = H(Y) - H (Y / X) 0.082(bit)故C = max/(X;Y) = 0.082(bit)，而上述等号成立的条件为p(y ) = p(打)P (x)又因为P =Y21 _w + w 332112所以须 w + w = w + w一 333因此达到信道容量时，信道输入概率为P =|上 x I 2设 W = w wW = 34W =141- 一-72 -2133P 2 =9921101_ 33 _7.答：状态转移矩阵P 二，故该马尔可夫信源是遍历的。-W + W = W3 121W = W3 12W + W2 =

11、 1所以信源熵为 H(X) = f p(S)H(X / S)=0.688(bit/符号)i =18.答：设A表示“大学生”这一事件，B表示“身高1.60m以上”这一事件，则 p(A) = 0.25，p(B) = 0.5，p(B / A) = 0.75心 A B)= P( B)些=冬* = 0.375 ，p( B)= log = 1.420.375(bit)二、综合题（共6题，每题10分）1.答：S0S1S2 S3 S4 S5S6 S7ebebbb cde de bad abbbadaddebbbcdebcdeS1到S7中都不包含S0中的元素，因此，S0是惟一可译码。2.答： 3.答：答:)-l

12、ogP(x= 0.737(骚)口 口I(x ) = -log p(x ) = 1.322(bit)22(2)I(x ; y ) = log P(七/ 气)=0.059(bit)1 1 P(y)1I(x ; y ) = log P(y2/ x= 0.263(bit)2P( y2)I(x ; y ) = log P(J 切=0.093(bit)1p(y)1I(x ; y ) = log P(y2/ %)= 0.322(bit)2 2P( y2)(3)信源X 和信源r 的信息熵H(X) = -22 P(x)log p(x) = 0.97(bit)i=1H(Y)=-费 P(y .)log P(y.)

13、= 0.722(bit)j=1(4)信道疑义度H(X / Y) = H (X, Y) H(Y) = H(X) + H(Y / X) H(Y) = 0.963(bit)(5)平均互信息 I(X, Y) = H(X) = H(X / Y) = 0.007(bit)4.答：（1）由一步转移概率矩阵与二步转移概率矩阵的公式P2 = PxP得q 2 + pqpqp2q 22 pqp2q2pqp 2 + pqP 2 =（2）设平稳状态W = W1,W2,W3，马尔可夫信源性质知WP = W，即qW + qW = WpW + qW = W132pW + pW = W233、W+ W + W3 = 1求解得稳

14、态后的概率为/W =q21 - p + p 2W = pq1 - p + p 2P（O） = P（O）P（O/O） + P（1）P（O/1）5.答：由尹（）+ 只1）=1P（0/0）=0.8，P（1/1）=0.7,得极新信源共8个序列，各序列的概率为皿5） = Pg）皿/茶）汽圣/站趴）信源模型为000 001 010 011 100 101 110 1110.3840.0960.0360.0840.0960.0240.0840.196一种编码结果（依信源模型中的序列次序）为0，001，10101, 1101，1011，00101， 0011,111.6.答：（1）对信源四个消息进行编码，选择

15、码长n = 4，这组码为C:（x ,x ,1,1） x = 0或 1（i = 1,2）1 2 2 2 i1 1)1 1)* 1 1)1 1 ,01 ,10 ,11 2云V2 2)V2 2)V2 2)（所以，码子为C: 0 0V编码后信息传输率R =丑炊)=J_ (bit/码兀符号)L 2(2)设接收序列& = (yy yy ), y e0,1(i = 1,2,3,4)，根据信道的传输特性，1 2 3 4 i接受序列&共有16个，正好分成4个互不相交的子集，每一个码字只传输到其中对应的一个子集：a =100I12-(00 y y，以2 =r0 1I121、2 /一-(01 y3 y4)，a3=1I1 0 -2 J-(10，3，4)a 4 =r1 1I12/-(11y3y4)y3,y4 引0,1具体传输信道如下:m 1 1000000010010001101000101011001111000100110101011110011011110111100一2 20