当前位置: 首页 > >

信息论基础—— 期末试卷 B 答案

发布时间:

? ? ○○大学

2008-2009 学年第一学期 学年第一

2006 级 信息与计算科学专业 本 科 卷 B 参考答案与评分标准 信息与计算科学专业 课程名称 信息论基础
课程号(???) ( 一、 15 分) (1)由图可知一阶马尔可夫信源的状态空间 E = A = {0,1,2} ,*稳后信源的概率分布就等于一 解: 阶马尔可夫信源状态的极限分布,即 考试形式(闭卷笔试) 时间(120 分钟) )

Q( Ei ) = P(a i ) , i = 1,2,3 ; Ei ∈ E , a i ∈ A ;
态的极限分布存在。可得状态一步转移矩阵

----------------(1 分)

从状态图中分析可知,这三个状态都是正规常返态,所以此马尔可夫链具有各态历经性,*稳后状

P 0 P P = P P 0 , 0 P P Q ( 0) Q(0) = P T Q(1) Q(1) Q(2) Q(2) Q(0) + Q(1) + Q(2) = 1
得: Q (0) = Q (1) = Q ( 2) = 1 / 3 , 则可得: p (0) = p (1) = p ( 2) = 1 / 3 ; (2) 一阶马尔可夫信源的熵

----------------(2 分)

----------------(2 分) ----------------(2 分)

H ∞ = H 2 = ∑ Q( Ei ) H ( X | Ei )
i =1

3

= P (0) H ( X | E ) + P (1) H ( X | 1) + P (2) H ( X | 2)
= 1 1 1 H ( P , 0, P ) + H ( P, P , 0) + H (0, P , P ) 3 3 3
----------------(4 分) ----------------(2 分)

= P log P P log P = H ( P ) ;
(3) 当 P = 0 , H ∞ = 0 当 P = 1 , H ∞ = 1 ;

因为信息熵是表示信源的*均不确定性,题中当 P = 0 或 P = 1 时表明信源从某一状态出发转移到另 一状态的情况是一定发生或一定不发生,即是确定的事件。当 P = 1 时,从 0 状态一定转移到 2 状态, 2 状态一定转移到 1 状态, 状态一定转移到 0 状态。 1 所以不论从何状态起信源输出的序列一定是 021021 序列,完全确定的。当 P = 0 时,0 状态永远处于 0 状态,1 状态永远处于 1 状态,2 状态用于处于 2

第 1 页 共 5 页

状态。信源输出的符号序列也是确定的。所以当 P = 1 或 P = 0 时,信源输出什么符号不存在不确定 性,完全是确定的,因此确定信源的信息熵等于零。 ----------------(4 分) ( 二、 20 分) 解:如下图所示, 其中

P Q1 = P

P P

q q Q2 = q q;

----------------(2 分)

----------------(2 分) 它们都是二元对称离散信道;又因为 C1 = 1 H ( P ) , C2 = 1 H ( q ) ; 所以这个和信道容量为:

C = log 2 ∑ 2ci = log 2
1

2

(2 + 2 )
C1 C2 1 q

----------------(4 分)

= log 2 2(1 p )
其中,Q1 的利用率 P1 = 其中,Q2 的利用率 P2 = 由此得:

1 p

p + 2(1 q )
p

q
q

2

C1 C

= =

(1 p )1 p p p (1 p )1 p p p + (1 q )1 q q q (1 q )1 q q q (1 p )1 p p p + (1 q )1 q q q
----------------(2 分)

2

C2 C

P(a1 ) = P(a 2 ) = P(a3 ) = P(a 4 ) =
三 、 12 分 ) (

1 (1 p )1 p p p P1 = 2 2 (1 p )1 p p p + (1 q )1q q q

[

] ]

1 (1 q ) q P2 = 1 p 2 2 (1 p ) p p + (1 q )1q q q
q

1 q

[

----------------(2 分)

解:要将此信源编码成为 r 元唯一可译变长码,其码字对应的码长

(l1 , l2 , l3 , l4 , l5 , l6 ) = (1,1,2,3,2,3)
必须满足克拉夫特不等式,即
6

∑r
i =1

li

= r 1 + r 1 + r 2 + r 3 + r 2 + r 3 ≤ 1 ;

----------------(5 分) ----------------(2 分) ----------------(1 分)

2 2 2 + + ≤ 1 ,其中 r 是大于或等于 1 的正整数; r r2 r3 可见,当 r = 1 时,不能满足 Kraft 不等式;
所以要满足

第 2 页 共 5 页

当 r = 2 时, 当 r = 3 时,

2 2 2 + + > 1 ,不能满足 Kraft; 2 4 8 2 2 2 26 + + = < 1 ,满足 Kraft; 3 9 27 27

----------------(1 分) ----------------(1 分) ----------------(2 分)

所以,求得 r 的最大值下限值等于 3。 (15 四、(15 分) 解:信源的概率分布为: 1 1 1 2 2 p(s i ) = ( , , , , ) 3 5 5 15 15 二元霍夫曼码:00,10,11,010,011; 码长:2,2,2,3,3;

----------------(7 分) ----------------(2 分)

当信源给定时,二元霍夫曼码是最佳二元码;所以对于概率分布为 ( 5 , 5 , 5 , 5 , 5 ) 的信源,其最佳二 元码就是二元霍夫曼码。 ----------------(2 分) 这二元霍夫曼码一定是三个信源符号的码长为 2(码符号/信源符号) ,另二个信源符号的码长为 3(码 符号/信源符号) ,其*均码长最短。因此,上述对概率分布为 ( 3 , 5 , 5 , 15 , 15 ) 信源所编的二元霍夫 曼码也是概率分布为 ( 5 , 5 , 5 , 5 , 5 ) 信源的最佳二元码。 五 、 (20 分 ) 解:令信道输入为 xm 时输出 y 的转移概率为 PN ( y | xm ) ,则最小错误概率译码实际上为最

1 1 1 1 1

1 1 1 2

2

1 1 1 1 1

----------------(4 分)

大后验概率译码
P(m | y ) =
M Q(m) PN ( y | x m ) ,其中 w( y ) = ∑ Q(m) PN ( y | x m ) w( y ) m =1

----------------(3 分)

对于给定的 y 和所有的 m ,其 w( y ) 必然相同,所以 p (m | y ) ≥ p (m ' | y ) 就可化为比较如下 式子

Q(m) PN ( y | x m ) ≥ Q(m ' ) PN ( y | x m' )

----------------(3 分)

则当先验等概时 Q (m) = Q (m ') 上式化为 PN ( y | x m ) ≥ PN ( y | x m ' ) ,此即最大似然译码。
----------------(4 分)

所以,当先验等概时,最小错误概率译码与最大似然译码是等价的。---------(2 分) 因为 M = 2 且输入等概,所以由题可知,当收到 y2 判为 x1 时应为错,同理,收到 y1 区间 中任一序列,判为 x2 也为错。这样:
Pe = Pe1 = Pe 2 = P 4 + 4 P 3 (1 p ) ;
----------------(4 分)

当收到的序列属于 Y3 时无法判定为 X1 或 X2,但此时必然有错误发生。所以,有错而不 能判决的概率为:
(18 六、 (18 分)

Pe = 6 P 2 (1 P ) 2

----------------(4 分)

第 3 页 共 5 页

解:信源

S P(s ) =
(1) H (s ) = 剩余度 γ = 1
2 i =1 i i

s1 s 2 0 .1 0 .9
----------------(2 分) ----------------(2 分)

∑ P(s ) log P(s ) ≈ 0.469 比特/符号

H (s ) = 0.531=53.1%; log 2

(2) 码符号 X = {0,1} ,对信源 S 编紧致码为:

s1 → 0 , s 2 → 1
其*均码长 L = 1 码符号/信源符号; (3) 当 N = 2 时

----------------(2 分) ----------------(1 分)

S 2 α 1 = s1 s1 , α 2 = s1 s 2 , α 3 = s 3 s1 , α 4 = s 2 s 2 ----------------(2 分) = 0.09, 0.09, 0.81 P(α i ) 0.01,
紧致码(即霍夫曼码)为

α4,
码字 Wi 码长 l i *均码长 0, 1,

α3,
10 , 2,

α2,
110 , 3,

α1
111 3 ----------------(3 分)

LN N

1 = 2

∑ P(α )l
i =1 i

4

i

≈ 0.645 码符号/信源符号

S3 N = 3 时, = P(α i ) α2, α1 , (0.1)3 , (0.1)2 0.9,

(0.1)

α3,
2

0.9,

(0.1)

α4,
2

0.9, 0.1 (0.9 ) , 0.1 (0.9 ) , 0.1 (0.9 ) ,
2 2 2

α5,

α6,

α7,

(0.9)3

α8

----------------(1 分) 对信源 S 进行霍夫曼编码,其紧致码为
3

α8 ,
码字 Wi 码长 l i 0, 1,

α7,
100 , 3,

α6,
101 , 3,

α5,
110 , 3,

α4,
11100 , 5,

α3,
11101 , 5,

α2,
11110 , 5,

α1
11111 5

----------------(3 分) *均码长

LN N

1 = 3

∑ P(α )l
i =1 i

8

i

≈ 0.533 码符号/信源符号。

----------------(2 分)

第 4 页 共 5 页




友情链接: