信息论与编码理论习题解
第二章-信息量和熵
2.1解: 平均每个符号长为:15
4
4.0312.03
2=
⨯+⨯秒
每个符号的熵为9183.03log 3
1
23log 32=⨯+⨯比特/符号
所以信息速率为444.34
15
9183.0=⨯比特/秒
2.2 解: 同步信号均相同不含信息,其余认为等概,
每个码字的信息量为 3*2=6 比特； 所以信息速率为600010006=⨯比特/秒
2.3 解:(a)一对骰子总点数为7的概率是
36
6 所以得到的信息量为 585.2)36
6(log 2= 比特 (b) 一对骰子总点数为12的概率是36
1 所以得到的信息量为 17.536
1
log 2= 比特 2.4 解: (a)任一特定排列的概率为
!
521
,所以给出的信息量为 58.225!
521
log 2
=- 比特 (b) 从中任取13张牌,所给出的点数都不相同的概率为
1352
13
13
521344!13C A =⨯ 所以得到的信息量为 21.134
log 1313
52
2=C 比特.
2.5 解:易证每次出现i 点的概率为
21
i
,所以
比特比特比特比特比特比特比特398.221
log 21)(807.1)6(070.2)5(392.2)4(807.2)3(392.3)2(392.4)1(6,5,4,3,2,1,21
log )(26
12=-==============-==∑
=i i X H x I x I x I x I x I x I i i
i x I i
2.6 解: 可能有的排列总数为
27720!
5!4!3!
12= 没有两棵梧桐树相邻的排列数可如下图求得，
Y X Y X Y X Y X Y X Y X Y X Y 图中X 表示白杨或白桦，它有⎪⎪⎭
⎫
⎝⎛37种排法，Y 表示梧桐树可以栽种的位置，它有⎪⎪⎭⎫
⎝⎛58种排法，所以共有⎪⎪⎭⎫ ⎝⎛58*⎪⎪⎭⎫
⎝⎛37=1960种排法保证没有
两棵梧桐树相邻，因此若告诉你没有两棵梧桐树相邻时，得到关于树排列的信息为1960log 27720log 22-=3.822 比特 2.7 解: X=0表示未录取，X=1表示录取； Y=0表示本市，Y=1表示外地；
Z=0表示学过英语，Z=1表示未学过英语，由此得
比特比特
比特比特
6017.02log 21
412log 2141910log 1094310log 10143)11(log )11()1()10(log )10()1()01(log )01()0()00(log )00()0()(8113.04log 4
1
34log 43)()(02698.04
1104
35
log 104354310469log 10469)
1()
01(log )01()0()00(log )00()0;(104
352513/41)522121()0(/)1())11()1,10()10()1,00(()
01(104692513/43)104109101(
)0(/)0())01()0,10()00()0,00(()
00()(4512.04
18
5log 85
4383log 8
3)
1()
01(log )01()0()00(log )00()0;(8
5
51/4121)0(/)1()10()01(8351/43101)0(/)0()00()00()(,
25
12
25131)1(,2513100405451)
10()1()00()0()0(,
5
4
511)1(,51101432141)10()1()00()0()0(,
4
1
)1(,43)0(2222222222222
2
222
2=⨯+⨯+⨯+⨯=
=====+=====+=====+=======+==+======+========⨯⨯+========+=========⨯⨯+========+=========+======+========
⨯=========⨯=
========-===⨯+=
===+======-===⨯+⨯=
===+=========x y p x y p x p x y p x y p x p x y p x y p x p x y p x y p x p X Y H X H c x p z x p z x p x p z x p z x p z X I z p x p x y p x y z p x y p x y z p z x p z p x p x y p x y z p x y p x y z p z x p b x p y x p y x p x p y x p y x p y X I y p x p x y p y x p y p x p x y p y x p a z p y z p y p y z p y p z p y p x y p x p x y p x p y p x p x p
2.8 解:令{}{}R F T Y B A X ,,,,==，则
比特
得令同理03645.0)()(5
.0,02.03.0)
2.05.0(log 2.0)()2.05.0(log )2.05.0()2.0
3.0(log )2.03.0(5.0log 5.03.0log 3.0)
5log )1(2.02log )1(5.0log )1(3.05log 2.0log 3.02log 5.0(2.0log 2.0)2.05.0(log )2.05.0()2.03.0(log )2.03.0()
()();()(2.0)(,2.05.0)(2.03.0)1(3.05.0)
()()()()(5.0max 2
'2222223102231022222==∴==+-=---++-+=-+-+-+++-----++-=-===-=+=-⨯+=+==p p I p I p p
p p I p p p p p p p p p p p p p p X Y H Y H Y X I p I R P p F P p
p p B P B T P A P A T P T P
2.9 & 2.12
解:令X=X 1,Y=X 1+X 2,Z=X 1+X 2+X 3, H(X 1)=H(X 2)=H(X 3)= 6log 2 比特 H(X)= H(X 1) = 6log 2 =2.585比特 H(Y)= H(X 2+X 3)
=
6log 6
1)536log 365436log 364336log 363236log 36236log 361(
2222222+++++ = 3.2744比特 H(Z)= H(X 1+X 2+X 3)
=
)27
216log 2162725216log 2162521216log 2162115
216log 2161510216log 216106216log 21663216log 2163216log 2161(
222222222++++++
= 3.5993比特 所以
H(Z/Y)= H(X 3)= 2.585 比特 H(Z/X) = H(X 2+X 3)= 3.2744比特 H(X/Y)=H(X)-H(Y)+H(Y/X) = 2.585-3.2744+2.585 =1.8955比特
H(Z/XY)=H(Z/Y)= 2.585比特 H(XZ/Y)=H(X/Y)+H(Z/XY) =1.8955+2.585 =4.4805比特 I(Y;Z)=H(Z)-H(Z/Y) =H(Z)- H(X 3)
= 3.5993-2.585 =1.0143比特 I(X;Z)=H(Z)-H(Z/X)
=3.5993- 3.2744 =0.3249比特 I(XY ;Z)=H(Z)-H(Z/XY) =H(Z)-H(Z/Y)
=1.0143比特 I(Y;Z/X)=H(Z/X)-H(Z/XY) = H(X 2+X 3)-H(X 3) =3.2744-2.585 =0.6894比特 I(X;Z/Y)=H(Z/Y)-H(Z/XY) =H(Z/Y)-H(Z/Y) =0
2.10 解:设系统输出10个数字X 等概,接收数字为Y,
显然101
)(101)()()(919
===∑∑==i j p i j p i Q j w i i
H(Y)=log10
比特奇奇
奇
奇
偶
18log 81
101452log 211015)
(log
)()()(log )()(0)
(log ),()(log ),()(22,2
222=⨯⨯⨯⨯+⨯⨯⨯
=-
-=--=∑∑∑∑∑∑∑≠====x y p x y p x p x x p x x p x p x y p y x p x y p y x p X Y H x y x i y x y x
所以
I(X;Y)= 3219.2110log 2=-比特
2.11 解:（a ）接收前一个数字为0的概率 218
0)0()()0(==∑=i i i u p u q w
bits p p
w u p u I )1(log 11log )0()0(log )0;(22
1212
1-+=-==
（b ）同理 4
18
)00()()00(=
=
∑=i
i i
u p u q w
bits p p w u p u I )1(log 22)1(log )00()00(log )00;(24
1
2
2121-+=-== （c ）同理 8
1
8
)000()()000(=
=
∑=i
i i
u p u q w
bits p p w u p u I )1(log 33)1(log )000()000(log )000;(28
1
3
2121-+=-== （d ）同理 ))1(6)1(()0000()()0000(42268
1
8
p p p p u p u q w i
i i
+-+-=
=
∑=
bits
p p p p p p p p p p w u p u I 4
2264
242268
1
4
2121)1(6)1()
1(8
log ))1(6)1(()1(log )0000()0000(log )0000;(+-+--=+-+--==
2.12 解:见2.9 2.13 解: (b)
)
/()/()
/(1
log
)()/(1log
)()
/()/(1
log
)()/(1log
)()/(XY Z H X Y H xy z p xyz p x y p xyz p xy z p x y p xyz p x yz p xyz p X YZ H x y z x
y
z
x
y
z
x
y
z
+=+===∑∑∑∑∑∑∑∑∑∑∑∑
(c)
)
/()
/(1
log
)/()()
/(1
log
)/()()/(X Z H x z p xy z p xy p xy z p xy z p xy p XY Z H x
y
z
x
y
z
=≤=∑∑∑∑∑∑（由第二基本不等式） 或
)
1)
/()
/((
log )/()()
/()/(log
)/()()
/(1log
)/()()
/(1log
)/()()/()/(=-⨯≤=-=-∑∑∑∑∑∑∑∑∑∑∑∑xy z p x z p e xy z p xy p xy z p x z p xy z p xy p x z p xy z p xy p xy z p xy z p xy p X Z H XY Z H x
y
z
x
y
z
x
y
z
x
y
z
（由第一基
本不等式）
所以
)/()/(X Z H XY Z H ≤
(a)
)/()/()/()/()/(X YZ H XY Z H X Y H X Z H X Y H =+≥+
等号成立的条件为)/()/(x z p xy z p =,对所有Z z Y y X x ∈∈∈,,,即在给定X 条件下Y 与Z 相互独立。
2.14 解:
(a) )/()/()/()/()/()/(Z X H Z XY H Z Y H YZ X H Z Y H Y X H ≥=+≥+ (b)
)
()/()()/()/()
()/()/()/()/()()/()()/(0)(,0)/()/()/()
()/()/()/()/()/()()/()/()/()/()()/()/()
/()/()()
/()/()/()()/()
/()()
/()/()()/()()/()()/(XZ H Z X H Z H Z X H Z X H Z H Z Y H Y X H Z Y H Y X H YZ H Z Y H XY H Y X H Z H Z X H Z Y H Y X H Z H Z Y H Y X H Z Y H Y X H Y X H YZ H Z Y H Y X H Y Z H Y X H Y H Z Y H Y X H Y X H Y Z H Y H Z Y H Y Z H Y X H Y H Y X H Y Z H Y H Z Y H Y X H Y H Y X H YZ H Z Y H XY H Y X H =
+≥
+++=+∴≥≥≥++++=
++=
+++=
+++
++≥++
+=+ 注：
b
a a
b a a a a b a a a b a b a b a b a a +≥+→
+≥+→≥→>>≥22
1121221121210,0 2.15 解: (a)
)/()/(),(0
)/()/(),(≥+==+=X Y H Y X H Y X d X X H X X H X X d
(b)
),()/()/()/()/(),(X Y d Y X H X Y H X Y H Y X H Y X d =+=+=
(c)
)
,()/()/(),(),()
/()/()/()/()/()/()/()/()/()
/()/()/()/(),(),(Z X d X Z H Z X H Z Y d Y X d X Z H X Y H Y Z H Z X H Z XY H Z Y H YZ X H Z Y H Y X H Y Z H Z Y H X Y H Y X H Z Y d Y X d =+≥+∴≥+≥=+≥++++=+同理
2.16 解: (a)
1
)
()
,(),()()/()/()()()()()()(),(≤=
∴=++-+≤-+=XY H Y X I Y X S XY H X Y H Y X H XY H Y H X H XY H Y H X H Y X I
又由互信息的非负性，即0);(≥Y X I 有0);(≥Y X S ，所以
1);(0≤≤Y X S
(b) 1)
()
()()/()()(),(),(==-==
X H X H XX H X X H X H XX H X X I X X S (c) 当且仅当X 和Y 独立时，I （X ；Y ）=0，所以 当且仅当X 和Y 独立时，0)
()
,(),(==XY H Y X I Y X S 。
2.23 解: (a)
⎩
⎨
⎧
≤≤-=其它
,01
1,)(2
1x x p X
比特1log )(2
111
21=-=⎰-dx X H C (b) 令y
dy dx x y 21
,
2==
⎪⎩⎪⎨⎧≤=其它
,01,21)(y y y p Y 比特
443.0log 121
log 21
)(log )()(2102-=-=-=-=⎰⎰+∞
∞
-e
dy y y dy y p y p X H Y Y C
(c) 令323
1,3-==z dz dx x z ⎪⎩⎪⎨⎧≤==-其它
,01,61)()(32z z dz
dx
x p z p X Z 比特
3.0log 26log )6log(61)6log(61)(log )()(221
001332323232-=-=+=-=⎰⎰⎰---+∞∞
-e
dz z z dz z z dz z p z p X H Z Z C 2.28 解:
(a) 由已知，
⎩⎨⎧≤<-=-=其它,
013,)(41
1y y p x ⎩⎨⎧≤<-==其它,
031,)(41
1y y p x
⎪⎪⎩⎪⎪⎨⎧≤<≤<--≤<-===+-=-====∑∑其它,
03
1,11,13,)1()1()1()1()
()()()(814181
y y y x y p x p x y p x p x y p x p xy p y w x y x x y x x
x y x x xy
（b ）
bits
dy dy dy Y H 5.28log 4log 8log )(2318121
14121381
=++=
⎰⎰⎰---
bits dy dy X Y H 24log 4log )(23
141212134121=+=
⎰⎰--
bit X Y H Y H Y X I 5.0)/()();(=-=∴
(c)由
⎪⎩
⎪⎨⎧-<-≤≤->=1,111,01,1y y y v
可求得V 的分布为
⎪⎪⎭
⎫ ⎝⎛-=412141101V 再由)/(x y p 及⎪⎩
⎪⎨⎧-<-≤≤->=1,111,01,1y y y v 可求得V 的条件分布为
{}{}⎩
⎨⎧-+-∈+++---∈=)1,1(),1,1(),(,0)1,1(),1,0(),1,0(),1,1(),(,)/(2
1x v x v x v p .
),;();(5.0)/()();(1)
1/(log )1/()1()1/(log )1/()1()/(5.12log 4log 2)(2222
1241变换没有信息损失可见V Y V X I Y X I bit
X V H V H X V I bit
x v p x v p x p x v p x v p x p X V H bit V H v
v →==-=====--=-=-=-==+⨯=∴∑∑
第三章 离散信源无失真编码
3.1解:长为n 码字的数目为D n ,因此长为N 的D 元不等长码至多有： 1)1(1--=∑=D D D D N N k i
3.2 解:
⎡⎤⎡⎤3
222100991100100010012210011000100110755.7004.0996.0004.0996.0996.01,100)(13
3.125051log 5051
49501001100)(-⨯=⨯⋅-⨯⋅--=====++=++=C C C P a b N C C C M a a e 因此有
的序列出现的概率的事件序列中含有三个误组率为长为所需码长为
因此在二元等长编码下的序列数目为
和更少个的事件序列中含有两个长为
3.3 解:
3.4 解:
{}
bit a p a p a p U I B
bit a p a p a p U I A a a a a U c bit a p a p a p a p a I B
bit a p a p a p a I A
b B A B A a k k k k k
k k k 0)()1(log )1()1;(32.1)()1(log )1()1;(,
,,,)(0)()(log )()1(log )1;(32.1)
(1log )()1(log )1;()(.
,
.,,)(2
412414321112112112112
1===========∑∑==对码对码对码对码均是唯一可译码和码但码不是异字头码码是异字头码的字头任一码字不是其它码字中码
3.5解:
（a ）二元Huffman 编码
%2.9926
.3234.3log )()(26
.3)(234.3)(log )()(2101210
1=======-=∑∑==D n U H R U H n a p n bits
a p a p U H k k k k k k η编码效率
平均码长
（b ）三元Huffman 编码
注意：K=10为偶数，需要添一个概率为零的虚假符号
%6.963
log 11.2234.3log )()(11
.2)(2210
1=⨯===
==∑=D n U H R U H n a p n k k k η编码效率平均码长
3.6解:二元Huffman 编码
（a ）二元Huffman 编码
%995.1485.1log )()(5
.1)(485.1)(log )()(23123
1=======-=∑∑==D
n U H R U H n a p n bits
a p a p U H k k k k k k η编码效率
平均码长
（b ）
%990
.397.2log )(2)(0
.3)(97.2)(2)()(229121222=========∑=D n U H R U H n a p n bits
U H U U H U H k k k η编码效率
平均码长
（c ）
%32.99487.4455.4log )(3)(487
.4)(455.4)(3)()(23271321333=========∑=D
n U H R U H n a p n bits
U H U U U H U H k k k η编码效率
平均码长
3.10 傅P186【5.11】
3.11 解:
3.12 解:
对
3.13 解:
(a)根据唯一可译码的判断方法可知,输出二元码字为异字头码,所以
它是唯一可译码。
469.01.0log 1.09.0log 9.0)(22=⨯-⨯-=U H 比特
(b)因为信源是二元无记忆信源，所以有
)()()()(21in i i i S P S P S P S P =
其中{}1,0,,,),,,(2121∈=in i i in i i i S S S S S S S
43046721.0)(,1,104782969
.0)(,1,10531441
.0)(,1,1059049
.0)(,1,106561
.0)(,1,1729
.0)(,1,1081
.0)(,1,109
.0)(,1,11
.0)(,1,188,1877,1766,1655,1544,1433,1322,1211,1100,10===========================S p l S S p l S S p l S S p l S S p l S S p l S S p l S S p l S S p l S
可计算每个中间数字相应的信源数字的平均长度
6953.5)(,18
01==∑=-i i i l S P L 信源符号/中间数字
(c) 根据表有
1,48,27,26,25,24,23,22,21,20,2=========l l l l l l l l l
可计算每个中间数字所对应的平均长度
7086.2)(,28
02==∑=-i i i l S P L 二元码/中间数字 由4756.0_1_2
=L L 二元码/信源符号
编码效率为0.4756/0.469=98.6%
精选题
1.傅P191【5.15】
2.傅P192【5.16】
信道及其容量
作业：4.1 4.3 4.5 4.8 4.9 4.10 4.12 4.14
4.1解：
(a) 对称信道
(b) 对称信道
(c) 和信道(课堂教学例题)!
4.3解：
(a): 可先假设一种分布,利用信道其容量的充要条件来计算(课堂教
学例题)
(b): 准对称信道！
4.5解：课堂教学例题
4.8解：该题概率有误，应把1/32改为1/64。
每个符号的熵为
bits p p S H i i i 2log )(28
1=-=∑=
采样频率Fs 为
Fs=2W=8000 Hz
所以信息速率R 为
bps 101.628000H(S) Fs R 4⨯=⨯=⨯=
4.9解：每象点8电平量化认为各级出现的概率相等，即H(U)=3 bits
所以信息速率R 为
bps 7102.760050030R ⨯=⨯⨯⨯=
4.10解：
bits
s kb 62210382.560310009.293,/9.29)10001(log 3000)N
S (1Wlog C s 603T 1000,dB 30N
S 3KHz,
W ⨯=⨯⨯⨯=+⨯=+=⨯====为分钟可能传送话音信息所以
4.12解：31N
S 8KHz,W == 高斯信道的信道容量为
C 。
C R ，bps ，R 。
，C R bps C ，C 。
C bps bps R bps ≤<⨯=⨯>=⨯>=⨯=+⨯=+=高斯高斯
高斯因则一定可以实现如故无法判定是否能实现的大小关系与信道容量但无法判定即的信道容量大于高斯信道因此时信道容量如该信道不是高斯信道不可实现如该信道是高斯信道所以4445422103,104,,,10410104)311(log 8000)N
S (1Wlog C
4.14解：
第五章 离散信道编码定理
习题5.1
解：DMC 信道
⎥⎥⎥⎥⎥⎥⎦
⎤⎢⎢⎢⎢⎢⎢⎣⎡=21316161213131
6
121P 有
4
1)()(,21)(321===x Q x Q x Q 247)2131(416121)(3
1)6121(413121)(8
3)3161(412121)(321=+⨯+⨯==+⨯+⨯==+⨯+⨯=
y w y w y w 因为
32)()()()(8
32121111111=⨯==y w x y p x p y x P 21)()()()(3
131********=⨯==y w x y p x p y x P 72)()()()(24
76121313131=⨯==y w x y p x p y x P 72)()()()(24
73141323232=⨯==y w x y p x p y x P 73)()()()(24
72141333333=⨯==y w x y p x p y x P 所以
最大后验概率译码为： 33121x ,x 判为判为和y y y 。
译码错误概率为：
2411)2
11(41416121)
)(1)(()()()(3332131=-⨯++⨯=-++=x y p x Q x Q x y P x Q p e
若按最大似然译码准则译码为：332211x ,x ,x 判为判为判为y y y
译码错误概率为：
21)2
11(4121412121)
)(1)(())(1)(())(1)((333222111=-⨯+⨯+⨯=-+-+-=x y p x Q x y P x Q x y P x Q p e
可见,最大似然译码的译码错误概率大于最大后验概率译码的译码错误概率。
第七章 信道编码
1. 设(7,3)码的生成矩阵为
⎥⎥⎥⎦
⎤⎢⎢⎢⎣⎡=111100001101100011101G (1) 写出该码的一致校验矩阵H ；
(2) 写出该码的所有许用码字；
(3) .写出该码的“译码表”---标准译码表或简化(伴随式)译码表；
(4) 写出接收矢量R=1000001的错误图样,并译相应的许用码字；
(5) 写出该码在BSC(错误转移概率为p)中传输的(平均)正确译码
概率p c 的表达式；
(6) 写出该码在BSC(错误转移概率为p)中传输的漏检概率P ud (也
称不可检测错误概率)的表达式.
解: (1) G 不为系统码形式,我们通过初等行变换变为系统码形式
⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=111100001101100011101G ~⎥⎥
⎥⎦⎤
⎢⎢⎢⎣⎡111100001010110011101 ~⎥⎥
⎥⎦
⎤
⎢⎢⎢⎣⎡100111001010110011101 因此
⎥⎥⎥⎥⎥⎦
⎤⎢⎢⎢⎢⎢⎣
⎡=11110001010100
11000100110001
H (2) 由C=MG 得该码的许用码字为
0000000,0111001,1101010,1010011,1011100,1100101,0110110,0001111 该码的最小汉明距离为4。
(3) 该码的标准阵由16个陪集构成, 在BSC(错误转移概率为p<1/2)应将重量最小的错误图样选作陪集首, 故该码的标准译码表为
译码规则为若接收矢量在第i列出现,则译码输出为对应列中的码字,也就是陪集首为可纠正错误图样.
伴随式译码表为
(4) 接收矢量R=1010101出现在标准译码表的第五列, 译码输出为
1011100, 错误图样为0001001.
(5) 该码标准译码表的陪集首重量分布为 A 0=1,A 1=7,A 2=7,A 3=1,A 4=A 5=A 6=A 7=0 所以正确译码概率p c 为
4326777
0)1(5)1(7)1(7)1()1(p p p p p p p p p A P i i i i c -+-+-+-=-=-=∑
注意：i=0
(6) 该码的重量分布为
A 0=1,A 1=A 2=A 3=0,A 4=7,A 5=A 6=A 7=0 所以该码在BSC 中传输的漏检概率P ud 为
3477
1)1(7)1(p p p p A P i i i i ud -=-=-=∑
注意：i=1。
