信息论与编码理论—第三章习题解答

1
111 0.125
112 0.075
121 0.075
211 0.075
113 0.050
131 0.050
311 0.050
122 0.045
212 0.045
221 0.045
123 0.030
132 0.030
213 0.030
312 0.030
231 0.030
321 0.030
0
0.057
1) 1)
2019/6/6
8
U~
a1 0.5
a2 0.3
0a.32
3.6 令离散无记忆信源如上。
(a) 求对U（即U1）的最佳二元码、平均码长和编码效率。 (b) 求对U2 （即U1U2）的最佳二元码、平均码长和编码效率。 (c) 求对U3 （即U1U2U3 ）的最佳二元码、平均码长和编码效率。
2019/6/6
6
习题课
(b) “当收到1时得到多少关于字母a1的信息”，这是求事件a1与事 件“收到1”的（非平均）互信息量。以码A为例。
P(a1)=0.4。 P(收到1)=P(a1)×P(收到1|a1)+P(a2)×P(收到1|a2)
+P(a3)×P(收到1|a3)+P(a4)×P(收到1|a4) =0.4×1+0.3×(1/2)+0.2×(1/3)+0.1×(1/4)=0.642。 P(a1，且收到1)=P(a1)×P(收到1|a1)=0.4×1=0.4。 所以I(a1；收到1)=log{0.4/(0.4×0.642)}=0.64155。
(b) 当收到1时得到多少关于字母a1的信息? (c) 当收到1时得到多少关于信源的平均信息?
字母
a1 a2 a3 a 2019/6/6
4
概率 0.4 0.3 0.2 0.1
码A 1 01 001 0001
码B
1
10
100
1000
5
习题课
[3.4的解答]
(a) 码A是异字头码。码B不是异字头码。码A和码B都是 唯一可译码。码A的译码规则是：1就是一个码字的末 尾。码B的译码规则是：1就是一个码字的开头。
2019/6/6
9
（U1U2U3 ）~
a1a1a1 a1a1a2 a1a2a1 a2a1a1 a1a1a3 a1a3a1 a3a1a1 a1a2a2 a2a1a2 0.125 0.075 0.075 0.075 0.050 0.050 0.050 0.045 0.045
a2a2a1 a1a2a3 a1a3a2 a2a1a3 a3a1a2 a2a3a1 a3a2a1 a2a2a2 a1a3a3 0.045 0.030 0.030 0.030 0.030 0.030 0.030 0.027 0.020
2019/6/6
2
习题课
(b) 含有两个和更少个al的序列拥有不同的码字，它们的译码不 会出现错误。因此错误概率(误组率)不会超过“含有三个以上 al的序列”出现的概率。而“含有三个以上al的序列”出现的 概率等于
100
C
k 100
(0 .004
)k
(0 .996
)100 k
k 3
2
1
习题课
3.1 试证明长度不超过N的D元不等长码至多有D(DN－1)/(D－1) 个码字。
[3.1的解答] 长度等于k的D元码字至多有Dk个，其中k=1~N。 因此长度不超过N的D元码字至多有
N
Dk D(DN1)/(D1)
k1
2019/6/6
1
U~0.0a104 0.a9296
222 0.027
1
133 0.020
0
0.040
313 0.020
1
331 0.020
0
0.038
223 0.018
1
232 0.018
0
0.036
322 0.018
1
233 0.012
212 0.045
221 0.045
123 0.030
132 0.030
213 0.030
312 0.030
231 0.030
321 0.030
222 0.027
133 0.020
313 0.020
331 0.020
223 0.018
232 0.018
0
0.036
322 0.018
1
233 0.012
3.2 以上是一个离散无记忆信源。若对其输出的长为100的事件 序列中含有两个和更少个al的序列提供不同的码字。
(a) 在等长编码下，求二元码的最短码长N。 (b) 求错误概率(误组率)。 [3.2的解答] (a) 长为L=100的事件序列中含有两个和更少个al的序列，其个数
为
C1000C1100C1200110049559； 6 而29 596210，所以最短N码 1长 。 0 为
100
C1k0(00.00)k 4(0.99)1 60 0k 42(0 8.00)3 4(0.99)9 67
k3
2
1
0.4k e0.40.00002
k0 k!
2019/6/6
4
习题课
3.4 对于有4个字母的离散无记忆源有两个码A和B，参看下表。 试问：
(a) 各码是否满足异字头条件?是否为唯一可译码?
因此平均n码 n长 (U2为 )1.5 2
H (U ) 0 .5 lo1g 0 .3 lo1g 0 .2 lo1g 1 .48503
0 .5
0 .3
0 .2
编码速R 率 n为 log2n
因此编 (U 2 码 )H (U 效 ) 1 .4 率 8 5 为 0 .9 09 30 R 1 .5
222 0.027
133 0.020
0
0.040
313 0.020
1
331 0.020
0
0.038
223 0.018
1
232 0.018
0
0.036
322 0.018
1
233 0.012
0
0.024
0
0.044
323 0.012
1
332 0.012
0
2019/6/6
0.020
1
19
333 0.008
U 1 U 2 ~ 0 a . 1 2 a 1 0 a 5 1 .1 a 2 0 a 5 . 2 1 a 10 a 5 . 1 1 a 3 0 a 0 . 3 1 a 1 a 0 0 . 2 0 a 20 a 9 . 2 0 a 30 a 6 . 3 0 a 20 a 6 . 3 0 a 3 4
0 1
0.25
1
0.45
1
2019/6/6
码字 00 010 011 100 101 1100 1101 1110 1111
12
（U1U2）的最佳二元码平均码长和编码效 率：
n ( U 2 ) 2 0 . 2 3 ( 5 0 . 1 2 0 5 . 1 2 ) 0 4 ( 0 . 0 0 . 0 9 2 0 6 . 0 ) 3 4
11
（U1U2）的第二种最佳二元码
事件 概率
a1a1 0.25
0
a1a2 0.15 a2a1 0.15
0 1
0.30
1
0.55
a1a3 0.10 a3a1 0.10
0 1
0.20
0
0 1.00
a2a2 0.09 a2a3 0.06 a3a2 0.06 a3a3 0.04
0 1 0 1
0.15 0.10
231 0.030
321 0.030
222 0.027
133 0.020
0
0.040
313 0.020
1
331 0.020
0
0.038
223 0.018
1
232 0.018
0
0.036
322 0.018
1
233 0.012
0
0.024
323 0.012
1
332 0.012
0
2019/6/6
0.020
0 0.45
0
a1a2 0.15 a2a1 0.15
0 1
0.30
0
a1a3 0.10 a3a1 0.10
0 1
0.20
1
1.00
a2a2 0.09 a2a3 0.06 a3a2 0.06 a3a3 0.04
0 1 0 1
0.15 0.10
0 1
0.25
1
0.55
1
2019/6/6
码字 00 100 101 010 011 1100 1101 1110 1111
2019/6/6
7
(c) “当收到1时得到多少关于信源的平均信息”，这是求信 源随机变量U与事件“收到1”的（半平均）互信息量。 以码A为例。
I(收到1；U)=
P ( a 1 | 收到
1) log
P ( a 1 , 且收到 P ( a 1 ) P (收到
1) 1)
P ( a 2 | 收到
1) log
P ( a 2 , 且收到 P ( a 2 ) P (收到
1) 1)
P ( a 3 | 收到
1) log
P ( a 3 , 且收到 1) P ( a 3 ) P (收到 1)
P ( a 4 | 收到
1) log
P ( a 4 , 且收到 P ( a 4 ) P (收到
18
333 0.008
1
111 0.125
112 0.075
121 0.075
Hale Waihona Puke Baidu
211 0.075
113 0.050
131 0.050
311 0.050
122 0.045
212 0.045
221 0.045
123 0.030
132 0.030
213 0.030
312 0.030
231 0.030
321 0.030
232 0.018
322 0.018
233 0.012
0
0.024
323 0.012
1
332 0.012
0
2019/6/6
0.020
15
333 0.008
1
111 0.125
112 0.075
121 0.075
211 0.075
113 0.050
131 0.050
311 0.050
122 0.045
132 0.030
213 0.030
312 0.030
231 0.030
321 0.030
222 0.027
133 0.020
313 0.020
331 0.020
0
0.038
223 0.018
1
232 0.018
0
0.036
322 0.018
1
233 0.012
0
0.024
323 0.012
1
332 0.012
C
k 10
0
(0 .004
)k
(0 .996
)100 k
k 0
1 2 0 .4 k e 0.4 k0 k!
2019/6/6
3
习题课
[3.2的注解] 事实上，在对“含有两个或更少个al的长为100的序 列”提供不同的码字之后,还有210-596=428个富余的码字。这 些富余的码字如果提供给其中428 个“含有恰好三个al的长为 100的序列”，作为它们各自的不同码字。则错误概率不会超 过
2019/6/6
13
111 0.125
112 0.075
121 0.075
211 0.075
113 0.050
131 0.050
311 0.050
122 0.045
212 0.045
221 0.045
123 0.030
132 0.030
213 0.030
312 0.030
231 0.030
321 0.030
113 0.050
131 0.050
311 0.050
122 0.045
212 0.045
221 0.045
123 0.030
132 0.030
213 0.030
312 0.030
231 0.030
321 0.030
222 0.027
133 0.020
313 0.020
331 0.020
223 0.018
a3a1a3 a3a3a1 a2a2a3 a2a3a2 a3a2a2 a2a3a3 a3a2a3 a3a3a2 a3a3a3 0.020 0.020 0.018 0.018 0.018 0.012 0.012 0.012 0.008
2019/6/6
10
（U1U2）的第一种最佳二元码
事件 概率
a1a1 0.25
0
2019/6/6
0.020
17
333 0.008
1
111 0.125
112 0.075
121 0.075
211 0.075
113 0.050
131 0.050
311 0.050
122 0.045
212 0.045
221 0.045
123 0.030
132 0.030
213 0.030
312 0.030
0
0.024
323 0.012
1
332 0.012
0
2019/6/6
0.020
16
333 0.008
1
111 0.125
112 0.075
121 0.075
211 0.075
113 0.050
131 0.050
311 0.050
122 0.045
212 0.045
221 0.045
123 0.030
222 0.027
133 0.020
313 0.020
331 0.020
223 0.018
232 0.018
322 0.018
233 0.012
323 0.012
332 0.012
0
2019/6/6
0.020
14
333 0.008
1
111 0.125
112 0.075
121 0.075
211 0.075