PDF《第五章课后习题》

第五章课后习题 【5.

1】某信源按

4 3 )

0 ( = P ,

4 1 )

1 ( = P 的概率产生统计独立的二元序列. (1)试求

0 N ,使当

0 N N > 时有

01 .

0 05 .

0 ) ( ) ( ≤ ? ? ? ? ? ? ≥ ? S H N I P i α 式中, ) (S H 是信源的熵. (2)试求当

0 N N = 时典型序列集 N Gε 中含有的信源序列个数. 解: (1)该信源的信源熵为

811 .

0 ) ( log ) ( ) ( = ? = ∑ i i s p s p S H 比特/符号 自信息的方差为

4715 .

0 811 .

0 4 log

4 1

3 4 log

4 3 ) ( )] ( [ )] ( [

2 2

2 2

2 = ? + = ? = S H s I E s I D i i 根据等长码编码定理,我们知道 δ ε α ? ≤ ? ? ? ? ? ? ≥ ?

1 ) ( ) ( S H N I P i 根据给定条件可知,

05 .

0 = ε ,

99 .

0 = δ .而[]2)(εδNsIDi=因此 [ ]

5 .

190 99 .

0 *

05 .

0 4715 .

0 ) (

2 2

0 = = ≥ δε i s I D N 取191

0 = N . (2)ε 典型序列中信源序列个数取值范围为: ] ) ( [ ] ) ( [

2 2 )

1 ( ε ε ε δ + ? < < ? S H N N S H N G 代入上述数值得

451 .

164 351 .

145 2

2 01 .

0 < < * N Gε 【5.2】有一信源,它有六个可能的输出,其概率分布如下表所示,表中给出了 对应的码 A、B、C、D、E 和F. 表5.2 消息 ) ( i a P A B C D E F

1 a 1/2

000 0

0 0

0 0

2 a 1/4

001 01

10 10

10 100

3 a 1/16

010 011

110 110

1100 101

4 a 1/16

011 0111

1110 1110

1101 110

5 a 1/16

100 01111

11110 1011

1110 111

6 a 1/16

101 011111

111110 1101

1111 011 (1) 求这些码中哪些是惟一可译码;

(2) 求哪些码是非延长码(即时码) ;

(3) 求对所有惟一可译码求出其平均码长 L . 解: (1)上述码字中,A 为等长码,且为非奇异码,因此码 A 为惟一可译码;

码B中,根据惟一可译码的判断方法,可求得其尾随后缀集合为}11111 ,

1111 ,

111 ,

11 ,

1 { ,且其中任何后缀均不为码字,因此码 B 是惟一可译码.码C为逗点码,因此码 C 为惟一可译码;

码D不是惟一可译码,因为其尾随后缀 集合中包含 0,而0又是码字;

码E的尾随后缀集合为空集,因此码 E 是惟一可 译码;

码F不是惟一可译码,因为其尾随后缀集合中包含 0,而0又是码字,因此F不是惟一可译码. (2)码A、C、E 是即时码(非延长码) (3)码A的平均码长为 3;

码B的平均码长为 2.125;

码C的平均码长为 2.125;

码F的平均码长为 2. 【5.3】证明定理 5.6,若存在一个码长为 q l l l , , ,

2 1 K 的惟一可译码,则一定存在具 有相同码长的即时码. 证明: 如果存在码长为 q l l l , , ,

2 1 K 的惟一可译码,则qlll,,

,21K必定满足如下不等式

1 1 ≤ ∑ = ? q i li r 而如果码长 q l l l , , ,

2 1 K 满足上述不等式,根据 Kraft 不等式构造即时码的方法,可 以构造出码长为 q l l l , , ,

2 1 K 的即时码,具体构造过程略,参照课本相关定理. 【5.4】设信源 ? ? ? ? ? ? = ? ? ? ? ? ?

6 2

1 6

2 1 ) ( p p p s s s s P S L L 将此信源编码为 r 元惟一可译变长码(即码符号集 } , ,

2 ,

1 { r X K = ) ,其对应的码 长为 )

3 ,

2 ,

3 ,

2 ,

1 ,

1 ( ) , , , (

6 2

1 = l l l K ,求r值的下限. 解: 如果要构造出惟一可译变长码,则相关码长必须满足

1 1 ≤ ∑ = ? q i li r ,代入上式有

2 1

3 2

1 ≤ + + ? ? ? r r r 当2=r时,上述不等式不成立;

当3=r时,成立.因此 r 值的下限为 3. 【5.5】若有一信源 ? ? ? ? ? ? = ? ? ? ? ? ?

2 .

0 8 .