信息论基础-- 期末试卷 A 答案

？○？大学 2008-2009 学年第一学期 ○

级 卷参考答案与评分标准

课程名称 信息论基础

课程号（？？？） 考试形式（闭卷笔试） 时间（120分钟））

一、判断题：本题共10小题，每题2分，满分20分。

1、√；2、√；3、×；4、×；5、√；6、×；7、×；8、√；9、√；10、×。

二、填空题：本题共7小题，每空2分，满分20分。

1、码字的最小距离（dmin）;

2、（减少）冗余，提高编码效率; 提高信息传递的可靠性；

3、系统码; 4、无失真信源编码定理，信道编码定理，限失真信源编码定理;

a

5、信道和信源都是无记忆； 6、香农编码； 7、。

2

三、计算题：本题共4小题，满分50分。 (15分)

1/21/20

解：P

1/21/41/4

联合概率p(xi

,y)

则Y （2分）

11+a41a4log2loglog ------------------（2分） 241a41a1116a1a

log log2log 2

241a41a1111a1a

log log2log16log

2441a241a311a1a

log log2log；

241a241a

（1）H(Y) 取2为底

11a1a

log2log)bit； ------------------（1分） 2241a41a

1a11a11a11a1a

（2）H(Y|X)logloglogloglog

2222244442

H(Y)(

3

2

3(1a)3a

log2log2； 223a

bit； ------------------（2分） 取2为底，H(Y|X)2

11a1aa

（3）CmaxI(X;Y)maxH(Y)H(Y|X)maxlog2loglog。 2p(xi)p(xi)p(xi)441a1a2

alog2

------------------（2分）

a11a1a

(ln2lnln2

取e为底，令a

112a11aa11

ln() ln2

241a241a41a1a1a11aa2

ln2 ln22

22(1a)41a41a111a

ln2ln= 0；

241a1a13

，可得a ------------------（2分） 即

1a45

[1**********]13

log2loglog 所以Clog2log log9

416204254145410

315315log2lglolog； ------------------（2分） 10241024

23

最佳入口分布为：(,)。 -------------------（2分）

55

2、(15分)

1pp/2p/2 解：根据状态转移图，列出转移概率距阵Pp/21pp/2 ------------------（1分） p/2p/21p

（1）令状态0,1,2平稳后的概率分布为WW1,W2,W3，则

p

(1p)W1W22

WPW

p

3 得到 W1(1p)W2

2Wi1

i1

W1W2W31

（2）由齐次遍历可得 H(X)

1pWW3W1

23

p1

W3W2 计算得到W------------------（3分） 23

1W3

1ogp1p

2

log------------（2分） p



1pp

WiHX(W|i)H(p1,322i

,

)p(1

（3）H(X)log31.58bit/符号 ---------------（2分）

由最大熵定理可知H(X)存在极大值：





H(X)1pp21

log(1p(1)ogp

p1p2p2

p11



2(1p)22(1p)

又0p1，所以

p

2(1p)

p

0,；

2(1p)

当p=2/3时

p

1；

2(1p)

H(X)p

0

p2(1p)

H(X)p

2/3

p2(1p)

所以当p=2/3时H(X)存在极大值,且H(X)max1.58bit/符号 -------------（3分）





所以H(X)H(X,) -------------------（2分）

3、(10分)

解：构造三元紧致码(三元霍夫曼码)要使短码得到充利用就必须让信源符号个数q满足

r q(r1) -------------（3分）

信源S的三元霍夫曼码如下：

-------------（5分）

得信源符号 s1 s2 s3 s4 s5 s6 s7 s8

三元紧致码 1 00 02 20 21 22 010 011。 -------------（2分）

4、(10分)

解：（1）该码的一致校验矩阵为

1 H0

0

01

001

110

011

111 -------------（2分）  011

因为二元(7,4)码的纠错范围是7个一位错，所以各陪集首和与之相对应的S如下：

e0000001―S101， e0000010―S111 e0000100―S011， e0001000―S110 e0010000―S001， e0100000―S010

e1000000―S100 -------------（4分）

（2）当v(0001011)的时候，S100；对照最小距离译码准则与S和e之间的关系表，知e1000000。 所以 Cev1001011。 -------------（4分）

四、证明题(10分)： 证明：设概率矢量P

(p1,p2,,pL1,pL)，根据熵函数表达式：

L

H(P)H(1p,2p,L,p1

,p)

i1

L

i

； pploig

m

H(p1,p2,p,L1q,1q,qm,)pilogpiqjlogqj； ① -------------（2分） 2,

i1

j1

L1

H(p,,Lp1,p2

1

,Lp)

i1

L

i

plo gp ② -------------（2分） i

mqmqjqjqmq1q2j

H(,,,)pLlog ③ -------------（2分） qjlog

pLpLpLpppj1j1LLL

②+③得： [ [ [

m

pilogpi qjlog

i1

j1

i

m

Lm

qjpL

]

loqg qjj

j1m

p

i1

L1

logpip LlopgLqj

j1

m

pgloj

m

]

p

i1j

L1

i

logpiqjloqgjpLlopgL

j1

lopLg

j1

q j ]

q

j1

 pL -------------（2分）

所以， ①=②+③ 结论得证 （2）等式的物理意义：

该等式是熵函数递增性性质的数学表达。表明了若原信源X（L个符号的概率分布为p1,p2,,pL） 中有一符号划分成m个元素（符号），而这m个符号的概率之和等于原符号的概率，则新信源的熵增 加。增加了一项由于划分而产生的不确定性量。 -------------（2分）

？○？大学 2008-2009 学年第一学期 ○

级 卷参考答案与评分标准

课程名称 信息论基础

课程号（？？？） 考试形式（闭卷笔试） 时间（120分钟））

一、判断题：本题共10小题，每题2分，满分20分。

1、√；2、√；3、×；4、×；5、√；6、×；7、×；8、√；9、√；10、×。

二、填空题：本题共7小题，每空2分，满分20分。

1、码字的最小距离（dmin）;

2、（减少）冗余，提高编码效率; 提高信息传递的可靠性；

3、系统码; 4、无失真信源编码定理，信道编码定理，限失真信源编码定理;

a

5、信道和信源都是无记忆； 6、香农编码； 7、。

2

三、计算题：本题共4小题，满分50分。 (15分)

1/21/20

解：P

1/21/41/4

联合概率p(xi

,y)

则Y （2分）

11+a41a4log2loglog ------------------（2分） 241a41a1116a1a

log log2log 2

241a41a1111a1a

log log2log16log

2441a241a311a1a

log log2log；

241a241a

（1）H(Y) 取2为底

11a1a

log2log)bit； ------------------（1分） 2241a41a

1a11a11a11a1a

（2）H(Y|X)logloglogloglog

2222244442

H(Y)(

3

2

3(1a)3a

log2log2； 223a

bit； ------------------（2分） 取2为底，H(Y|X)2

11a1aa

（3）CmaxI(X;Y)maxH(Y)H(Y|X)maxlog2loglog。 2p(xi)p(xi)p(xi)441a1a2

alog2

------------------（2分）

a11a1a

(ln2lnln2

取e为底，令a

112a11aa11

ln() ln2

241a241a41a1a1a11aa2

ln2 ln22

22(1a)41a41a111a

ln2ln= 0；

241a1a13

，可得a ------------------（2分） 即

1a45

[1**********]13

log2loglog 所以Clog2log log9

416204254145410

315315log2lglolog； ------------------（2分） 10241024

23

最佳入口分布为：(,)。 -------------------（2分）

55

2、(15分)

1pp/2p/2 解：根据状态转移图，列出转移概率距阵Pp/21pp/2 ------------------（1分） p/2p/21p

（1）令状态0,1,2平稳后的概率分布为WW1,W2,W3，则

p

(1p)W1W22

WPW

p

3 得到 W1(1p)W2

2Wi1

i1

W1W2W31

（2）由齐次遍历可得 H(X)

1pWW3W1

23

p1

W3W2 计算得到W------------------（3分） 23

1W3

1ogp1p

2

log------------（2分） p



1pp

WiHX(W|i)H(p1,322i

,

)p(1

（3）H(X)log31.58bit/符号 ---------------（2分）

由最大熵定理可知H(X)存在极大值：





H(X)1pp21

log(1p(1)ogp

p1p2p2

p11



2(1p)22(1p)

又0p1，所以

p

2(1p)

p

0,；

2(1p)

当p=2/3时

p

1；

2(1p)

H(X)p

0

p2(1p)

H(X)p

2/3

p2(1p)

所以当p=2/3时H(X)存在极大值,且H(X)max1.58bit/符号 -------------（3分）





所以H(X)H(X,) -------------------（2分）

3、(10分)

解：构造三元紧致码(三元霍夫曼码)要使短码得到充利用就必须让信源符号个数q满足

r q(r1) -------------（3分）

信源S的三元霍夫曼码如下：

-------------（5分）

得信源符号 s1 s2 s3 s4 s5 s6 s7 s8

三元紧致码 1 00 02 20 21 22 010 011。 -------------（2分）

4、(10分)

解：（1）该码的一致校验矩阵为

1 H0

0

01

001

110

011

111 -------------（2分）  011

因为二元(7,4)码的纠错范围是7个一位错，所以各陪集首和与之相对应的S如下：

e0000001―S101， e0000010―S111 e0000100―S011， e0001000―S110 e0010000―S001， e0100000―S010

e1000000―S100 -------------（4分）

（2）当v(0001011)的时候，S100；对照最小距离译码准则与S和e之间的关系表，知e1000000。 所以 Cev1001011。 -------------（4分）

四、证明题(10分)： 证明：设概率矢量P

(p1,p2,,pL1,pL)，根据熵函数表达式：

L

H(P)H(1p,2p,L,p1

,p)

i1

L

i

； pploig

m

H(p1,p2,p,L1q,1q,qm,)pilogpiqjlogqj； ① -------------（2分） 2,

i1

j1

L1

H(p,,Lp1,p2

1

,Lp)

i1

L

i

plo gp ② -------------（2分） i

mqmqjqjqmq1q2j

H(,,,)pLlog ③ -------------（2分） qjlog

pLpLpLpppj1j1LLL

②+③得： [ [ [

m

pilogpi qjlog

i1

j1

i

m

Lm

qjpL

]

loqg qjj

j1m

p

i1

L1

logpip LlopgLqj

j1

m

pgloj

m

]

p

i1j

L1

i

logpiqjloqgjpLlopgL

j1

lopLg

j1

q j ]

q

j1

 pL -------------（2分）

所以， ①=②+③ 结论得证 （2）等式的物理意义：

该等式是熵函数递增性性质的数学表达。表明了若原信源X（L个符号的概率分布为p1,p2,,pL） 中有一符号划分成m个元素（符号），而这m个符号的概率之和等于原符号的概率，则新信源的熵增 加。增加了一项由于划分而产生的不确定性量。 -------------（2分）