信息论与编码试卷及答案

1、一、（11'）填空题（1）1948年，美国数学家香农 发表了题为"通信的数学理论”的长篇论文，从而创立了信息论。（2）必然事件的自信息是0。（3）离散平稳无记忆信源 X的N次扩展信源的熵等于离散信源X的熵的N倍。（4）对于离散无记忆信源，当信源熵有最大值时，满足条件为_-信源符号等概分布_。（5）若一离散无记忆信源的信源熵H（X等于，对信源进行等长的无失真二进制编码，则编码长度至少为_3。（6）对于香农编码、费诺编码和霍夫曼编码，编码方法惟一的是香农编码。（7）已知某线性分组码的最小汉明距离为3 ,那么这组码最多能检测出丄个码元错误，最多能纠正1_个码元错误。（8）设有一离散

2、无记忆平稳信道，其信道容量为C,只要待传送的信息传输率R小于 _ C（大于、小于或者等于），则存在一种编码，当输入序列长度n足够大，使译码错误概率任意小。（9）平均错误概率不仅与信道本身的统计特性有关，还与译码规则和 _编码方法有关三、（5 ）居住在某地区的女孩中有25%是大学生，在女大学生中有75%是身高米以上的，而女孩中身高米以上的占总数的一半。假如我们得知“身高 1.6米以上的某女孩是大学生”的消息，问获得多少信息量解：设A表示“大学生”这一事件，B表示“身高以上”这一事件，则P（A）= P（B）= P（BIA）=（ 2分）故 P（AlB）=P（AB）p（B）=p（A）p（BA）p（B）

3、=*=（ 2分）I(AlB)=(1分)四、（5）证明：平均互信息量同信息熵之间满足I(X; Y)=H(X)+H (Y )-H(X Y) 证明:P Xi yjI X;YP Xiyj logX YP XPXyjlog P XiX YH X H XY同理I X;Y H Y HYX则HYX H Y I X;Y因为H XY H X HYX故H XY H X H Y I X;Y即I X;Y H X H Y H XYP Xi yj log PXiyj（2分）X Y（1 分）（1分）（1 分）五、（18'）.黑白气象传真图的消息只有黑色和白色两种，求：1） 黑色出现的概率为，白色出现的概率为。给出这个

4、只有两个符号的信源X的数学模型。假设图上黑白消息出现前后没有关联，求熵H X ；2） 假设黑白消息出现前后有关联，其依赖关系为，求其熵H X 。3）分别求上述两种信源的冗余度，比较它们的大小并说明其物理意义。解：1）信源模型为（1分）2）由题意可知该信源为一阶马尔科夫信源。（2分）得极限状态概率3）H（X）log2 20.119（4分）（2 分）（3分）H （X）0.447log2 2（1 分）（1 分）21。说明：当信源的符号之间有依赖时，信源输出消息的不确定性减弱。而信源冗余度正是反映信源符号依赖关系的强弱，冗余度越大，依赖关系就越大。（2分）六、（18' ） 信源空间为P（X）X

5、X2×3X4X5X5X70.2 0.19 0.18 0.170.15 0.10.01,试分别构造二元香农码和二元霍夫曼码，计算其平均码长和编码效率（要求有编码过程）1/21/31/6P(X)411 ,试分别214七 （6 ）.设有一离散信道，其信道传递矩阵为1/61/21/3 ,并设P（X2）1/31/61/2P(X3)按最大后验概率准则与最大似然译码准则确定译码规则，并计算相应的平均错误概率。1）（ 3分）最小似然译码准则下，有，2）（ 3分）最大后验概率准则下，有，八（10）二元对称信道如图。3 11）若 P 0-， P 1,求 HX、HXlY 和 IX;Y ；4 42）求该信道

6、的信道容量。解：1）共6分H X |Y 0.749bit/符号2），（ 3分）此时输入概率分布为等概率分布。（1分）000111九、（18）设一线性分组码具有一致监督矩阵H0110011010111）求此分组码n=,k=共有多少码字2） 求此分组码的生成矩阵G3）写出此分组码的所有码字。4）若接收到码字（101001）,求出伴随式并给出翻译结果。2）设码字 CC5C4C3C2C1C0 由 HC TC2C1C0 0C4C3C0 0C5C3C1C0 0令监督位为C2C1C0，则有C2C5C3C1C5C4C0C4C3100110010011生成矩阵为001101解： 1）n=6,k=3, 共有8个码

7、字。（ 3分）3）所有码字为 000000， 001101，010011T0得3分）3分）（2分）011110，100110，101011，110101，111000。（4分）4）由 ST HRT 得S 101 ，（2分）该码字在第 5位发生错误，（ 101001）纠正为（ 101011），即译码为 （ 101001）1分）一、填空题（本题 10空, 每空1分, 共10分） 1、必然事件的自信息量是 0，不可能事件的自信息量是 _无穷 。2、一信源有五种符号a , b, c, d, e,先验概率分别为Pa=, R=, Pc=, Pd=Fb=O符号“ a”的自信息量为 _1bit ，此信源的熵为

8、符号。3、如某线性分组码的最小汉明距 dmin=6 ,最多能纠正 2_个随机错。4、 根据密码算法所使用的加密密钥和解密密钥是否相同,可将密码体制分成_对称（单密钥） 和_非对称（双密钥） O5、 平均互信息量 I（X;Y） 与信源熵和条件熵之间的关系是 _I（X:Y）=H（X）-H（X/Y） O6、 克劳夫特不等式是唯一可译码 存在的充要条件。00 , 01, 10, 11是否是唯一可译码 _是O三、单项选择题 （本题共 10小题；每小题 2分，共 20分） 1、对连续集的熵的描述不正确的是（A）A连续集的熵和离散集的熵形式一致，只是用概率密度代替概率，用积分代替求和B连续集的熵值无限大C

9、连续集的熵由绝对熵和微分熵构成D 连续集的熵可以是任意整数2、设信道输入为Xm,输出为y,若译码准则是当P（y | Xm） Fty | Xm）,对所有mm时, 将y判为m ,则称该准则为（D）A 最大后验概率译码准则 B 最小错误概率准则C 最大相关译码准则 D 最大似然译码准则3、线性分组码不具有的性质是（ C）A 任意多个码字的线性组合仍是码字B 最小汉明距离等于最小非 0重量C 最小汉明距离为 3D 任一码字和其校验矩阵的乘积 cmHT=04、关于伴随式的描述正确的是（ A）A伴随式S与传送中信道出现的错误图样e有关B通过伴随式S可以完全确定传送中信道出现的错误图样 eC伴随式S与发送的

10、具体码字有关D伴随式S与发送的具体码字有关，与传送中信道出现的错误图样 e也有关5、率失真函数的下限为（ B）AH（U）B0CI （U; V）D 没有下限6、纠错编码中,下列哪种措施不能减小差错概率（ D）A 增大信道容量 B 增大码长 C 减小码率 D 减小带宽7、已知某无记忆三符号信源 a,b,c 等概分布,接收端为二符号集,其失真矩阵为 , 则信源的最大平均失真度 DmaX 为（ D）A 1/3 B 2/3 C 3/3 D 4/38、一珍珠养殖场收获 240 颗外观及重量完全相同的特大珍珠,但不幸被人用外观相同但重量仅有 微小差异的假珠换掉 1 颗。一人随手取出 3 颗,经测量恰好找出了

11、假珠,不巧假珠又滑落进去, 那人找了许久却未找到,但另一人说他用天平最多 6 次能找出,结果确是如此,这一事件给出的 信息量（ A ）。A 0bit B log6bit C 6bit D log240bit9、已知随机噪声电压的概率密度函数 P（X） =1/2, X的取值范围为一1V至+1V,若把噪声幅度从零开始向正负幅度两边按量化单位为 做量化，并且每秒取 10 个记录，求该信源的时间熵（ B ） A S B S C bit /S D以上都不对10、彩色电视显像管的屏幕上有 5×105 个像元，设每个像元有 64 种彩色度，每种彩度又有 16 种不同的亮度层次，如果所有的彩色品种和

12、亮度层次的组合均以等概率出现，并且各个组合之 间相互独立。每秒传送 25 帧图像所需要的信道容量（ C ）A B 75.106 C D第 7 章 线性分组码1.已知一个（5, 3）线性码C的生成矩阵为：11001G0110100111（1）求系统生成矩阵；（2）列出C的信息位与系统码字的映射关系；（3）求其最小Hamming距离，并说明其检错、纠错能力；（4）求校验矩阵H；（5）列岀译码表，求收到 r=11101时的译码步骤与译码结果。解：（1）线性码C的生成矩阵经如下行变换：110011001101101将第2、3加到第1行011010011100111100111001101101将第劝卩

13、到第2行010100011100111得到线性码C的系统生成矩阵为10011GS0101000111(2)码字C (C,Cl, ,Cn 1)的编码函数为C f (m) m0 1 0 0 1 1 m1 0 1 0 1 0 m2 0 0 1 1 1生成了的8个码字如下信息元系统码字000Ooooo00100111010010100110110110010011101101001101100111111110（3）最小汉明距离d=2 ,所以可检1个错，但不能纠错11110H10 10 1(5)消息序列 m=000,001,010,011,100,101,110,111,由 c=mGs得码字序列Co=

14、OOOOO, C1=00111,C2=01010, C3=01101,C4=10011, C5=10100, C6=11001, C7=11110则译码表如下:0000000111010100110110011101001100111110100001011111010111010001100100010010111001000011110001000101110111110010001101100000100110010110110010010101011100011111当接收到r =(11101)时，查找码表发现它所在的列的子集头为(01101),所以将它译为C=011012设(7, 3

15、 )线性码的生成矩阵如下010101 0G001011 1100110 1(1)求系统生成矩阵；(2)求校验矩阵；(3)求最小汉明距离；(4)列岀伴随式表。解：(1)生成矩阵G经如下行变换0 10 10 1010 0 110 100101110010111100110101010101001101100110100101 1101010 1001010 1000101 11得到系统生成矩阵:1001101GS01010100010111(2)由 G In k,Ak(n k),HAk (n k),n k,得校验矩阵为110 10 0 010 10 10 0 H0 110 0 101 0 1 0

16、0 0 1(3) 由于校验矩阵 H的任意两列线性无关，3列则线性相关，所以最小汉明距离d=3。(4) (7, 3)线性码的消息序列 m=000,001,010,011,100,101,110,111,由 c=mGs得码字序列：CO=Ooooooo,g=0010111，C2=0101010, C3=0111101，0=1001101, C5=1011010，©=1100111，C7=1110000。又因伴随式有 24=16种组合，差错图7样为1的有177种，差错图样为2的有221种，而由HrTHeT ,则计算陪集首的伴随式，构造伴随表如下:伴随式陪集首伴随式陪集首00000000000

17、0101100100011011000000100110001001010010000011110011000011100100001100000110010000001000111001001000100000010010110100001001000000100011001010000010000001011000001103.已知一个(6, 3)线性码C的生成矩阵为:100101G010011001110(1)写岀它所对应的监督矩阵 H;(2)求消息M=(101)的码字；(3)若收到码字为101010 ,计算伴随式，并求最有可能的发送码字。解：(1)线性码C的生成矩阵G就是其系统生成矩阵

18、 G,所以其监督矩阵 H直接得岀:10 110 0H 0110101 1 0 0 0 1(2)消息 MKm, m, m)=(101),则码字 C 为:Cf(m) 10 0 10 1 0 011 1010 10 11(3)收到码字r=(101010),则伴随式101011110rH101010 g001100010001又(6, 3)线性码的消息序列m=000,001,010,011,100,101,110,111,由C=mGs得码字序列：6=000000,C=001110,C2=010011,C3=011101 ,C4=100101,C5=101011,C6=110110,C7=111000o

19、伴随式有23=8种情况，则计算伴随式得到伴随表如下：伴随式陪集首000000000101100000011010000110001000100000100010000010001000001111100010伴随式(001)对应陪集首为(000001),而C=叶e,则由收到的码字r=(101010),最有可能发送的码字 C为:C= (101011)。4 设(6, 3)线性码的信息元序列为X1 X2X3, 它满足如下监督方程组X1X2X40X2X3X50X1X3X60(1) 求校验矩阵，并校验 10110是否为一个码字；(2) 求生成矩阵，并由信息码元序列101生成一个码字解：(1)由监督方程直

20、接得监督矩阵即校验矩阵为:110100H011010101001因为收到的序列10110 为 5位，而由（ 6, 3 ）线性码生成的码字为6 位，所以 10110 不是码字由 G I n k ,Ak (n k) ,H Ak (n k) ,I n k，则生成矩阵为：100101G 0 10110GS001011信息码元序列M= (101),由c=mGs得码字为Cc m0 100101 m1 010110 m2 001011 101110第 8 章 循环码1. 已知（8, 5） 线性分组码的生成矩阵为1111000010001000G0100010000100010111000011)证明该码是循

21、环码；2)求该码的生成多项式g(x)。1）证明如下：1 1 1 1 0 0 0 01 1 1 1 0 0 0 01 0 0 0 1 0 0 00 1 1 1 1 0 0 00 1 0 0 0 1 0 0(1) (2) 0 1 0 0 0 1 0 00 0 1 0 0 0 1 00 0 1 0 0 0 1 01 1 1 0 0 0 0 11 1 1 0 0 0 0 11 1 1 1 0 0 0 01 1 1 1 0 0 0 00 1 1 1 1 0 0 00 1 1 1 1 0 0 00 0 1 1 1 1 0 0(3) (4) 0 0 1 1 1 1 0 00 0 1 0 0 0 1 00 0

22、 0 1 1 1 1 01 1 1 0 0 0 0 11 1 1 0 0 0 0 11 1 1 1 0 0 0 01 1 1 1 0 0 0 00 1 1 1 1 0 0 00 1 1 1 1 0 0 00 0 1 1 1 1 0 0(4) (5) 0 0 1 1 1 1 0 00 0 0 1 1 1 1 00 0 0 1 1 1 1 00 0 0 1 0 0 0 10 0 0 0 1 1 1 1由生成矩阵可知为( 8、 5)循环码。 (2)生成多项式如下：(2) (3)(1) (5)g(x) x3 x2 x 12. 证明： x10 x8 x5 x4 x2 x 1为(15, 5) 循环码的生成

23、多项式，并写出信息多项式为4m(x) x4 x 1 时的码多项式(按系统码的形式) 。由定理 8-1 可知( n， k )循环码的生成多项式 g(x) 为 xn+1 的因子， g(x) 为 n-k 次多项式，本题目4 nEAQ中知： g(x) x10x8x5x4x2x 1为一个 10 次多项式， n-k=15-5=1015 10 8 5 4 2并且： (x 1) mod( x x x x x x 1) 0所以： x10 x8 x5 x4 x2 x 1 是 x15 1 的一个因子，也是循环码的生成多项式。 按系统码构造多项式如下：m(x) x4 x 1m(x)n k4X(X10141110X 1

24、) XXXXb(x)(m(x) Xn k108542)mod(xXXXXX1)876XXXXC(X)n km(x) X14111087b(x) XXXXX6XX333.已知(7, 4)循环码的生成多项式为 g(x) X X 1 ,信息多项式为m(x) X1 ,分别由编码电路和代数计算求其相应的码多项式C(X)。由题目可知代数计算求解过程如下：m(x) X31n k 63m(x) X X Xb(X) (m(X) Xn k)mod(X3 X 1) X2 XC(X) m(x) Xn k b(x) X6 X3 X2 XC (1001110)由编码电路进行求解: 编码电路如下所示：编码过程如下:时钟信息

25、元寄存器码字输出码字D) D1 D200 0 0111 1 01200 1 10301 1 10410 1 1150 0 1160 0 0170 0 00可得：C(X) X6 X3 X2 X4.令(15, 11)循环码的生成多项式为g(x) X4 X 1 ,计算(1)若信息多项式为 m(x)10X1,试求编码后的系统码字;(2)求接收码组R(X) X14X41的校正子多项式。(1) 解题过程如下:m(x)m(x)b(x)10 8 X X 1Xn k m(x)(m(x) Xn k) mod(xn km(x) X b(x) X414X X412 XC(X)C (1010000000010101)X

26、141)12X2X4X(2) 校正多项式如下所示:S(X)R(X)g(x)X144XX4X 1X 13mod(g(x) X 15.码长为n=15的本原BCH码，求不同纠错能力下的BCH码各自的生成多项式 g(x)。n 2m 115 m 4纠错能力：t 2m 18 ,所以最多能纠正 7个错误码。有限域GF( 24)，4次本原多项式f() X4 X 1，%为f(x)的一个根，可知:10,计算 2t=14个连续幕次为对应的最小多项式：m()4 XX 1,m2(x) X4X 1,m3(x)432XXXX1m4(x)4 XX 1,m5 (x) X2X 1,ms()432XXXX1m7(x)4 X3X 1,m8() X4 X 1,m9()4X X 1m°()2 XX 1,m11()432XXXX 1m2()4