信息理论与编码-期末试卷A及答案

题号 一 二 三 四 总分 统分人 题分 35 10 23 32 100

得分 一、填空题(每空1分,共35分) 得分| |阅卷人|

1、1948年,美国数学家 发表了题为“通信的数学理论”的长篇论文,从而创立了信息论。信息论的基础理论是 ,它属于狭义信息论。

2、信号是 的载体,消息是 的载体。

3、某信源有五种符号}{,,,,a b c d e ,先验概率分别为5.0=a P ,25.0=b P ,125.0=c P ,0625.0==e d P P ,则符号“a ”的自信息量为 bit ,此信源的熵为 bit/符号。

4、某离散无记忆信源X ,其概率空间和重量空间分别为1234

0.50.250.1250.125X x x x x P ????

=????????和

1234 0.5122X x x x x w ????

=????????,则其信源熵和加权熵分别为 和 。

5、信源的剩余度主要来自两个方面,一是 ,二是 。

6、平均互信息量与信息熵、联合熵的关系是 。

7、信道的输出仅与信道当前输入有关,而与过去输入无关的信道称为 信道。 8、马尔可夫信源需要满足两个条件:一、 ; 二、 。 9、若某信道矩阵为??

??????????0100010000001100,则该信道的信道容量C=

__________。

10、根据是否允许失真,信源编码可分为 和 。 11、信源编码的概率匹配原则是:概率大的信源符号用 ,概率小的信源符号用 。(填

短码或长码)

12、在现代通信系统中,信源编码主要用于解决信息传输中的 性,信道编码主要用于解决信息传输中的 性,保密密编码主要用于解决信息传输中的安全性。 13、差错控制的基本方式大致可以分为 、 和混合纠错。 14、某线性分组码的最小汉明距dmin=4,则该码最多能检测出 个随机错,最多能纠正 个随机错。

15、码字101111101、011111101、100111001之间的最小汉明距离为 。

16、对于密码系统安全性的评价,通常分为 和 两种标准。

17、单密钥体制是指 。 18、现代数据加密体制主要分为 和 两种体制。

19、评价密码体制安全性有不同的途径,包括无条件安全性、 和 。

20、时间戳根据产生方式的不同分为两类:即 和 。 二、选择题(每小题1分,共10分) 得分| |阅卷人|

1、下列不属于消息的是( )。

A. 文字

B. 信号

C. 图像

D. 语言

2、设有一个无记忆信源发出符号A 和B ,已知3

1)(,)(==B p A p ,发出二重符号序列消息的信源,

无记忆信源熵)(2X H 为( )。

A. 0.81bit/二重符号

B. 1.62bit/二重符号

C. 0.93 bit/二重符号 D . 1.86 bit/二重符号

3、 同时扔两个正常的骰子,即各面呈现的概率都是1/6,若点数之和为12,则得到的自信息为( )。

A. -log36bit

B. log36bit

C. -log (11/36)bit

D. log (11/36)bit

4、 二进制通信系统使用符号0和1,由于存在失真,传输时会产生误码,用符号表示下列事件,x0: 发出一个0 、 x1: 发出一个1、 y0 : 收到一个0、 y1: 收到一个1 ,则已知收到的符号,被告知

发出的符号能得到的信息量是( )。

A. H(X/Y)

B. H(Y/X)

C. H( X, Y)

D. H(XY)

5、一个随即变量x 的概率密度函数P(x)= x /2,V 20≤≤x ,则信源的相对熵为( )。 A . 0.5bit B. 0.72bit C. 1bit D. 1.44bit

6、 下面哪一项不属于熵的性质: ( ) A .非负性 B .完备性 C .对称性 D .确定性

7、根据树图法构成规则, ( ) A .在树根上安排码字 B .在树枝上安排码字 C .在中间节点上安排码字 D .在终端节点上安排码字

8、下列组合中不属于即时码的是( )。 A. { 0,01,011} B. {0,10,110} C. {00,10,11} D. {1,01,00}

9、 已知某(6,3)线性分组码的生成矩阵??

???

?????=011101110001111010G ,则不用计算就可判断出下列码中不是该

码集里的码是( )。 A. 000000 B. 110001 C. 011101 D. 111111 10、下列保密编码中属于现代密码体制的是( ) A. 凯撒密码 B. Vigenere 密码 C. 韦维纳姆密码 D. DES 加密算法 三、简答题(四小题,共23分) 得分| |阅卷人| 1、请简述现代密码系统应当满足的条件。(4分)

2、请简述连续信源最大熵定理的主要内容。(6分)

3、请解释最小错误概率译码准则,最大似然译码准则和最小距离译码准则的含义,并说明三者的关

系。(5分)

答:

4、已知密钥为yes ,请利用多表代换密码中的Vigenere (维吉尼亚)密码原理分别对下列明文和密文

进行编码和译码。明文:A Mathematical Theory of Communication ; 密文:G ee y hgaxgp (需给出

码表或编译码过程,8分)

四、计算题(四小题,共32分) 得分| |阅卷人| 1、居住在某地区的女孩中有25%是大学生,在女大学生中有75%是身高1.6米以上的,而女孩中身高1.6米以上的占总数的一半。假如我们得知“身高1.6米以上的某女孩是大学生”的消息,问获得多少信息量?(5分) 2、设离散符号信源为121/43/4x x X P ????=????????,试求:

(1)信源的熵、熵的相对效率以及剩余度; (2)求二次扩展信源的概率空间及其信源熵。(10分) 3、已知6符号离散信源的出现概率为????????321321161814121654321a a a a a a ,试写出Huffman 编码的码字并求其平均码长。(7分)

4、已知一个(5, 3)线性分组码C 的生成矩阵为:11001G 0110100111??

??

=??????,

(1)求系统生成矩阵及校验矩阵; (2)列出C 的信息位与系统码字的映射关系; (3)求收到r =11101时的译码步骤与译码结果。(10分)

2015-2016年第2学期《信息论与编码》期末考试A卷参考答案

一、填空题(每空1分,共35分)

1、香农、香农信息论;

2、消息、信息;

3、1、15/8;

4、7/4、9/4;

5、信源符号间的相关性、信源符号的统计不均匀性;

6、I(X;Y)=H(X)+H(Y)-H(XY);

7、无记忆;

8、某一时刻信源符号的输出只与此时刻信源状态有关,与之前的状态和输出符号无关;信源在t时刻的状态由当前输出符号及t-1时刻信源的状态唯一确定;

9、2bit/符号;10、无失真信源编码和限失真信源编码; 11、短码、长码;12、有效性、可靠性;13、前向纠错、反馈重发;14、3、1;15、2;16、理论保密性、实际保密性; 17、在加密和解密过程中,加、解密密钥相同或从一个容易得出另一个的密码体制;

18、公钥体制、私钥体制;填单钥体制、双钥体制)或(对称加密体制、非对称加密体制)也可; 19、计算安全性、可证明安全性; 20、自建时间戳、具有法律效力的时间戳

二、选择题(每小题1分,共10分)

B B B A

C B

D A D D

三、简答题(四小题,共23分)

1、请简述现代密码系统应当满足的条件。(4分)

答:一个安全的现代密码系统应当满足以下几点要求:(每小点1分)

(1)系统即使达不到理论上不可破译,也应当是实际上不可破译的。

(2)系统的保密性不依赖于对加密、解密算法和系统的保密,而仅仅依赖于密钥的保密性。、(3)加密、解密算法适用于所有密钥空间的元素。

(4)加密、解密运算简单快捷,易于实现。

2、请简述连续信源最大熵定理的主要内容。(6分)

答:连续信源最大熵定理主要内容如下:(每小点2分)

(1)峰值功率受限条件下信源的最大熵定理:若某信源输出信号的峰值功率受限,即信号的取值被限定在某一有限范围(假设为[a,b])内,则在限定的范围内,当输出信号概率密度分布为均匀分布

时,该信源具有最大熵,且为log()

b a

-。

(2)平均功率受限条件下信源的最大熵定理:若某信源输出信号的平均功率和均值被限定,则当其

输出信号幅度的概率密度函数是高斯分布时,该信源达到最大熵值,且最大熵值为1

2

log2eP

π

(3)均值受限条件下信源的最大熵定理:若某连续信源X输出非负信号的均值被限定,则其输出信

号幅度为指数分布时,信源X具有最大熵,且其值为

log2em。

3、请解释最小错误概率译码准则,最大似然译码准则和最小距离译码准则的含义,并说明三者的关

系。(5分)

答:最小错误概率译码准则下,将接收序列译为后验概率最大时所对应的码字(1分)。最大似然译

码准则下,将接收序列译为信道传递概率最大时所对应的码字。(1分) 最小距离译码准则下,将接

收序列译为与其距离最小的码字。(1分)三者关系为:输入为等概率分布时,最大似然译码准则等

效于最小错误概率译码准则。(1分)在二元对称无记忆信道中,最小距离译码准则等效于最大似然

译码准则。(1分)

4、已知密钥为yes,请利用多表代换密码中的Vigenere(维吉尼亚)密码原理分别对下列明文和密

文进行编码和译码。明文:A Mathematical Theory of Communication;密文:G ee y hgaxgp (需

给出码表或编译码过程,8分)

答:我们已知26个字母的排列如下表

A B C D E F G H I J K L M

0 1 2 3 4 5 6 7 8 9 10 11 12

N O P Q R S T U V W X Y Z

13 14 15 16 17 18 19 20 21 22 23 24 25

根据提供的明文,可以得出密文YQSRLWKELGGSJXZCSJWSXASEKYFGGSRMGL,编码过程如下表所示(5分)

A

M

12

A

T

19

H

7

E

4

M

12

A

T

19

I

8

C

2

A

L

11

T

19

H

7

E

4

O

14

R

17

Y

24

O

14

F

5

C

2

O

14

M

12

M

12

U

20

N

13

I

8

C

2

A

T

19

I

8

O

14

N

13

Y

24

E

4

S

18

Y

24

E

4

S

18

Y

24

E

4

S

18

Y

24

E

4

S

18

Y

24

E

4

S

18

Y

24

E

4

S

18

Y

24

E

4

S

18

Y

24

E

4

S

18

Y

24

E

4

S

18

Y

24

E

4

S

18

Y

24

E

4

S

18

Y

24

Y Q S R L W K E L G G S J X Z C S J W S X A S E K Y F G G S R M G L

根据提供的密文,可以得出译码后的明文为:I AM A DOCTOR。译码过程如下表所示:(3分)

G

6

E

4

E

4

Y

24

H

7

G

6

A

X

23

G

6

P

15

Y

24

E

4

S

18

Y

24

E

4

S

18

Y

24

E

4

S

18

Y

24

I

8

A

M

12

A

D

3

O

14

C

2

T

19

O

14

R

17

四、计算题(四小题,共32分) 1、居住在某地区的女孩中有25%是大学生,在女大学生中有75%是身高1.6米以上的,而女孩中身高1.6米以上的占总数的一半。假如我们得知“身高1.6米以上的某女孩是大学生”的消息,问获得多

少信息量?(5分) 解:设A 表示“大学生”这一事件,B 表示“身高1.60以上”这一事件,则 P(A)=0.25 p(B)=0.5 p(B|A)=0.75 (2分)故 p(A|B)=p(AB)/p(B)=p(A)p(B|A)/p(B)=0.75*0.25/0.5=0.375 (2分) I(A|B)=-log0.375=1.42bit (1分) 2、设离散符号信源为???

???=??????4/34/121

x x P X X ,试求:(1)信源的熵、熵的相对效率以及剩余度;(2)求二次扩展信源的概率空间及其信源熵。(10分) 解:(1)

22max 2()1/4log 43/4log (4/3)0.811/()/()()/log 2()81.1% 11()18.9%

H X bit H X H X H X H X R H X ηη=+======-=-=符号,(4分) (2)二次扩展信源的概率空间为:(3分) X\X 1x 2x 1x 1/16 3/16 2x 3/16 9/16 2222()1/16log 163/16log (16/3)3/16log (16/3)9/16log (16/9)2() 1.622/H XX H X bit =+++==符号(3分) 3、已知6符号离散信源的出现概率为????????321321161814121654321a a a a a a ,试写出Huffman 编码的码字并计算平均码长。(7分) 解: Huffman 编码为: a 1 0.5 a 2 0.25 a 3 0.125

a 4 0.0625 a 5 0.03125 a 6 0.03125 0.0625 0.125 0.25

0.5

1.0

1 1 1 1

0 0 0 0

0 1

符号 概率 码字

1

01 001

0001

00001

00000 (5分)其他正确的Huffman 编码也给分。 平均码长符号码元/933.15*321

5*321

4*161

3*81

2*41

1*21

=+++++= (2分)

4、已知一个(5, 3)线性码C 的生成矩阵为:11001G 0110100111??

??

=??????

,(1)求系统生成矩阵及校验

矩阵;(2)列出C 的信息位与系统码字的映射关系;(3)列出译码表,求收到r =11101时的译码步骤与译码结果。(10分)

解:(1)线性码C 的生成矩阵经如下行变换:

2313211001

1001110011011010110101010001110011100111??????

??????

??????→??????→???

???????????????

将第、加到第行将第加到第行

得到线性码C 的系统生成矩阵为 100110101000111G ????=??

????,对应的校验矩阵 1 1 1 1 0 1 0 1 0 1H ??=????

3分)

(2)由c =mG 得消息序列m =000,001,010,011,100,101,110,111的系统码字依次分别为:(3分)

c 0=00000, c 1=00111,c 2=01010, c 3=01101,c 4=10011, c 5=10100, c 6=11001, c 7=11110

(3) 根据该(5,3)线性码的系统码定,可得其标准阵列译码表如下:(4分) 00000 00111 01010 01101 10011 10100 11001 11110

10000 10111 11010 11101 00011 00100 01001 01110

01000 01111 00010 00101 11011 11100 10001 10110 00001 00110 01011 01100 10010 10101 11000 11111

当接收到r =(11101)时,根据标准阵译码方法,可查找码表发现它所在的列的子集头为(01101),所以将它译为c =01101。

相关推荐
相关主题
热门推荐