信息论与编码理论习题答案(3)

(i) ?????0.1，?????0.05，L?1884 下边界：(1???)2L(H(U)???)?0.9?21431..84 上边界：2L(H(U)???)=21620..24 故0.9?21431..84?MT?21620..24

(ii) ?????10?6，?????10?3，L?4.71?1011 (1???)2L(H(U)???)?0.9999?23.81?10 2L(H(U)???)=23.82?10

故0.9999?23.81?10?MT?23.82?10

3.4 对于有4字母的离散无记忆信源有两个码A和码B，参看题表。

11111111字母 a1 a2 a3 a4 概率 0.4 0.3 0.2 0.1 码A 1 01 001 0001 码B 1 10 100 1000 (a) 各码是否满足异字头条件？是否为唯一可译码？ (b) 当收到1时得到多少关于字母a1的信息？ (c) 当收到1时得到多少关于信源的平均信息？

解：①码A是异头字码，而B为逗点码，都是唯一可译码。

②码A I(a1;1)?log2p(a1|1)1?log2?1.32 bit p(a1)0.4p(a1|1)p(1)p(a1,1)0.4?log2?log?0 bit

p(a1)p(1)p(a1)p(1)0.4?1码B I(a1;1)?log2③码A U=｛a1,a2,a3,a4｝

I(u;1)??p(ak|1)I(ak;1)=p(a1|1)I(a1;1)?0=1.32 bit

k?14 码B I(u;1)??p(ak|1)I(ak;1)=0 bit

k?14（收到1后，只知道它是码字开头，不能得到关于U的信息。）

3.5 令离散无记忆信源

???aU??1?0.16??a20.14a30.13a40.12a50.10a60.90a70.08a80.07??a9a10???0.060.05??(a) 求最佳二元码,计算平均码长和编码效率。 (b) 求最佳三元码,计算平均码长和编码效率。

解：(a)

0.5800.4210.310.270.230.190000100111001101110010001110101011a10.16a20.14a30.13a40.1210101010.15010.1101010101a5a6a7a8a9a100.100.090.080.070.060.05

H(U)???pklogpk=3.234 bit

平均码长 n??pknk=3.26=R?nlogD

k效率 ??H(U)H(U)??99.2% RnlogD (b)

0.430.330.240001021012202122110111a1a201210.160.140.130.120.100.090.080.070.060.05010120.11102012a3a4a5a6a7a8a9a10

平均码长 n??pknk=2.11

kR?nlogD=3.344

效率 ??

H(U)?96.6% Ra2.........a3.....??a1.........3.6 令离散无记忆信源 U???

0.5...0.3.....0.2??(a) 求对U的最佳二元码、平均码长和编码效率。 (b) 求对U的最佳二元码、平均码长和编码效率。 (c) 求对U的最佳二元码、平均码长和编码效率。 解：(a)

0.510001a10.5a20.33201101a30.2

n=0.5×1+0.3×2+2×0.2=1.5

H(U)???pklogpk?1.485 bit

??H(U)?99% R (b) ∵离散无记忆 ∴H(U1U2)=2H(U)=2.97 bit

p(a1a1)=0.25, p(a1a2)=0.15, p(a1a3)=0.1, p(a2a1)=0.15, p(a2a2)=0.09 p(a2a3)=0.06, p(a3a1)=0.1, p(a3a2)=0.06, p(a3a3)=0.04

0.5500.4510110.2510a1a10.300.250.20.15010110010101101110000000101100111a1a20.150.150.10.10.090.060.060.0401010.1a2a1a1a3a3a1a2a201a2a3a3a2a3a3

n2??pknk?3

n?n2?1.5 2??H(U1U2)2.97==0.99 3n2logD(c) 有关U3最佳二元类似 略 3.7 令离散无记忆信源

a2..........ak?a1.........?U???

?p(a1)p(a2)p(ai)?且0≤P(a1)≤P(a2)≤…. ≤P(ak)<1。定义Qi=?p(ak), i>1，而Q1=0，今按

k?1i?1下述方法进行二元编码。消息ak的码字为实数Qk的二元数字表示序列的截短（例如1/2的二元数字表示序列为1/2→10000…，1/4→0100…）,保留的截短序列长度nk是大于或等于I(ak)的最小整数。

a1...a2.......a3......a4......a5.......a6.......a7......a8.....????构造码。 (a) 对信源U??11111111???4,4,8,8,16,16,16,16??(b) 证明上述编码法得到的码满足异字头条件，且平均码长n满足

H(U)≤n≤H(U)+1。

解：(a)

符号 Qi 0 1 161 83 161 43 84 83 4L 4 4 4 4 4 3 2 2 C 0000 0001 0010 0011 0100 011 10 11 a8 a7 a6 a5 a4 a3 a2 a1

(b) 反证法证明异字头条件

令k

这与假设ak是ak?的字头（即Qk??Qk?pk）相矛盾，故满足异字头条件。 由已知可得