【信息论与编码课后答案】 信息论编码第三版答案

2.1一个马尔可夫信源有3个符号{u 1, u , 2u }3，转移概率为：p (u 1|u 1)=1/2，

p (u 2|u 1)=1/2，p (u 3|u 1)=0，p (u 1|u 2)=1/3，p (u 2|u 2)=0，p (u 3|u 2)=2/3，

p (u 1|u 3)=1/3，p (u 2|u 3)=2/3，p (u 3|u 3)=0，画出状态图并求出各符号稳态概率。解：状态图如下

状态转移矩阵为：

0⎫⎛1/21/2

⎪p = 1/302/3⎪

1/32/30⎪⎝⎭

设状态u 1，u 2，u 3稳定后的概率分别为W 1，W 2、W 3

11⎧1

W 1+W 2+W 3=W 110⎧⎪2W 1=33⎪⎪2512⎪⎪⎧WP =W 9⎪W 1+W 3=W 2⎪

由⎨得⎨2计算可得⎨W 2= 3

25⎩W 1+W 2+W 3=1⎪2⎪

6⎪W 2=W 3⎪W 3=3⎪⎪25⎩⎪W 1+W 2+W 3=1⎩

2.2 由符号集{0，1}组成的二阶马尔可夫链，其转移概率为：p (0|00) =0.8，p (0|11)=0.2，

p (1|00) =0.2，p (1|11)=0.8，p (0|01) =0.5，p (0|10)=0.5，p (1|01) =0.5，p (1|10)=0.5。

画出状态图，并计算各状态的稳态概率。

=p 解：p (0|00) =p (00|00) =0.8 p (0|01)

p (0|11)=p (10|11)=0.2 p (0|10=) p p (1|00) =p (01|00) =0.2 p (1|01) =p

(10=|01) (00=|10) (11=|01)

p (1|11)=p (11|11)=0.8 p (1|10)=p (01|10)=0.5

0⎫⎛0.80.20

⎪000.50.5⎪ 于是可以列出转移概率矩阵：p =

0.50.500⎪ ⎪000.20.8⎝⎭

状态图为：

设各状态00，01，10，11的稳态分布概率为W 1,W 2, W 3, W 4 有

5⎧W 1=⎪14⎧0.8W 1+0.5W 3=W 1

⎪

⎪0.2W 1+0.5W 3=W 2

⎪W 2=1⎧WP =W ⎪⎪⎪⎪47

0.5W 2+0.2W 4=W 3 得 计算得到⎨⎨⎨

W i =1∑⎪0.5W 2+0.8W 4=W 4⎪W 3=1⎪⎩i =1

⎪⎪7W 1+W 2+W 3+W 4=1⎪⎪⎩5

⎪W 4=

14⎩

2.7 设有一离散无记忆信源，其概率空间为

⎛X ⎫⎛x 1=0x 2=1x 3=2x 4=3⎫

⎪= ⎪ P 3/81/41/41/8⎝⎭⎝⎭

（1）求每个符号的自信息量

（2）信源发出一消息符号序列为{202 120 130 213 001 203 210 110 321 010 021 032 011 223 210}，求该序列的自信息量和平均每个符号携带的信息量 解：I (x 1) =log 2

18

=log 2=1.415bit p (x 1) 3

同理可以求得I (x 2) =2bit , I (x 3) =2bit , I (x 3) =3bit

因为信源无记忆，所以此消息序列的信息量就等于该序列中各个符号的信息量之和 就有：I =14I (x 1) +13I (x 2) +12I (x 3) +6I (x 4) =87.81bit 平均每个符号携带的信息量为

87.81

=1.95bit/符号 45

2.11 有一个可以旋转的圆盘，盘面上被均匀的分成38份，用1，…，38的数字标示，其中有两份涂绿色，18份涂红色，18份涂黑色，圆盘停转后，盘面上的指针指向某一数字和颜

色。

（1）如果仅对颜色感兴趣，则计算平均不确定度

（2）如果仅对颜色和数字感兴趣，则计算平均不确定度 （3）如果颜色已知时，则计算条件熵

解：令X 表示指针指向某一数字，则X={1,2,……….,38}

Y 表示指针指向某一种颜色，则Y={l绿色，红色，黑色} Y 是X 的函数，由题意可知p (x i y j ) =p (x i ) （1）H (Y ) =

∑p (y j )log

j =1

3

12381838

=log +2⨯log =1.24bit/符号 p (y j ) 3823818

（2）H (X , Y ) =H (X ) =log 238=5.25bit/符号

（3）H (X |Y ) =H (X , Y ) -H (Y ) =H (X ) -H (Y ) =5.25-1.24=4.01bit/符号 2.12 两个实验X 和Y ，X={x1 x 2 x 3},Y={y1 y 2 y 3},l联合概率r (x i , y j )=r ij 为

⎛r 11r 12

r 21r 22 r

⎝31r 32r 13⎫⎛7/241/240⎫⎪ ⎪r 23⎪= 1/241/41/24⎪

r 33⎪1/247/24⎪⎭⎝0⎭

（1） 如果有人告诉你X 和Y 的实验结果，你得到的平均信息量是多少？

（2） 如果有人告诉你Y 的实验结果，你得到的平均信息量是多少？

（3） 在已知Y 实验结果的情况下，告诉你X 的实验结果，你得到的平均信息量是多少？ 解：联合概率p (x i , y j ) 为

H (X , Y ) =∑p (x i , y j )log 2

ij

1p (x i , y j )

=2⨯

72411

log 2+4⨯log 224+log 24247244

=2.3bit/符号

1

H (Y ) =3⨯log 23=1.58bit/符号

3

H (X |Y ) =H (X , Y ) -H (Y ) =2.3-1.58

=0.72bit/符号

2.16 黑白传真机的消息元只有黑色和白色两种，即X={黑，白}，一般气象图上，黑色的出现概率p(黑) ＝0.3，白色出现的概率p(白) ＝0.7。

（1）假设黑白消息视为前后无关，求信源熵H(X)，并画出该信源的香农线图 （2）实际上各个元素之间是有关联的，其转移概率为：P(白|白) ＝0.9143，P(黑|白) ＝0.0857，P(白|黑) ＝0.2，P(黑|黑) ＝0.8，求这个一阶马尔可夫信源的信源熵，并画出该信源的香农线图。

（3）比较两种信源熵的大小，并说明原因。 解：（1）H (X ) =0.3log 2P(黑|白)=P(黑)

1010

+0.7log 2=0.8813bit/符号 37

P(白|白) ＝P(白)

P(黑|黑) ＝P(黑)

P(白|黑) ＝P(白)

（2）根据题意，此一阶马尔可夫链是平稳的（P(白) ＝0.7不随时间变化，P(黑) ＝0.3不随时 间变化）

H ∞(X ) =H (X 2|X 1) =∑p (x i , y j )log 2

ij

1p (x i , y j )

=0.9143⨯0.7log 2+0.8⨯0.3log 2

10.8

111

+0.0857⨯0.7log 2+0.2⨯0.3log 2

0.91430.08570.2

＝0.512bit/符号

2.20 给定语音信号样值X 的概率密度为p (x ) =小于同样方差的正态变量的连续熵。

解：

1-λx

λe , -∞

1-λx

H c (X ) =-⎰p x (x )log p x (x ) dx =-⎰p x (x )log e dx

2-∞-∞1

=-⎰p x (x )log dx -⎰p x (x )(-λx )log edx

2-∞-∞11-λx

=-log +log e ⎰e (λx ) dx

22-∞

11

=-log λ+log e ⎰e λx ⋅λ(-x ) dx +log

22-∞11

=-log λ+2log e ⎰2xe -λx dx

2201-λx +∞

⎤=-log λ-log e ⎡(1+λx ) e ⎣⎦0

212e =-log λ+log e =log

2λ

+∞0

+∞

+∞

+∞

+∞

+∞+∞

⎰

1-λx

e (λx ) dx 2

E (X ) =0, D (X ) =

2

λ2

1214πe H (X , ) =log 2πe 2=log 2=>=H (X )

2λ2λ

2.29 有一个一阶平稳马尔可夫链X 1, X 2, , X r , , 各X r 取值于集合A ={a 1, a 2, a 3}, 已知起始概率P(Xr ) 为p 1=1/2, p 2=p 3=1/4，转移概率如下图所示

(1) 求(X 1, X 2, X 3) 的联合熵和平均符号熵 (2) 求这个链的极限平均符号熵

(3) 求H 0, H 1, H 2和它们说对应的冗余度 解：（1）

H (X 1, X 2, X 3) =H (X 1) +H (X 2|X 1) +H (X 3|X 2, X 1)

=H (X 1) +H (X 2|X 1) +H (X 3|X 2)

111111

H (X 1) =-log -log -log =1.5bit /符号

224444

，X 的联合概率分布为

那么

p (x 2j ) =∑p (x 1i x 2j )

i

X 2的概率分布为

H (X 2|X 1) =

111131131

log 4+log 4+log 4+log +log3+log +log3 [1**********]

=1.209bit/符号

X 2X 3的联合概率分布为

那么

H (X 3|X 2) =

=1.26bit/符号

771535535

log 2+log 4+log 4+log +log 3+log +log 3 [**************]

H (X 1, X 2, X 3) =1.5+1.209+1.26=3.969bit /符号

所以平均符号熵H 3(X 1, X 2, X 3) =

3.969

=1.323bit ／符号 3

⎛1 2 2

（2）设a 1,a 2,a 3稳定后的概率分布分别为W1,W2,W3, 转移概率距阵为P =

3 2 ⎝3

14013

1⎫4⎪⎪1⎪ ⎪3⎪0⎪⎪⎭

224⎧1⎧W 1+W 2+W 3=1W 1=⎪2⎪337⎪⎪

⎧13⎪WP =W ⎪1⎪由⎨ 得到 ⎨W 1+W 3=W 2计算得到⎨W 2=

W i =1314⎪⎩∑⎪4⎪

3=1⎪W 1+W 2+W 3⎪W 3=⎪⎪14⎩⎩

又满足不可约性和非周期性

3 4111321

H ∞(X ) =∑W i H (X |W i ) =H (, , ) +2⨯H (, ,0) =1.25bit /符号

72441433i =1

b i /t 符号 H 2=(3)H 0=log3=1.58bit /符号 H 1=1. 5

1. 5+1. 209

=1. 35b 5i /t 符号 2

1.251.251.25

γ0=1-η0=1

-=0.21γ1=1-η1=1-=0.617 γ2=1-η2=1-=0.078

1.581.51.355

2.32 一阶马尔可夫信源的状态图如图2－13所示，信源X 的符号集为（0，1，2）。

（1）求信源平稳后的概率分布P(0),P(1),P(2) （2）求此信源的熵

（3）近似认为此信源为无记忆时，符号的概率分布为平稳分布。求近似信源的熵H(X)并与H ∞进行比较

图2-13

⎡1-p p /2p /2⎤⎢⎥解:根据香农线图, 列出转移概率距阵P =p /21-p p /2 ⎢⎥⎢⎣p /2p /21-p ⎥⎦

令状态0,1,2平稳后的概率分布分别为W1,W2,W3

p ⎧

(1-p ) W 1+W 2+⎪2

⎧WP =W ⎪

⎪p ⎪3

得到 ⎨W 1+(1-p ) W 2+⎨W i =1⎪2⎪∑⎩i =1

⎪W 1+W 2+W 3=1⎪⎩

由齐次遍历可得

1p ⎧W =W 3=W 1

⎪32

⎪

p 1⎪

W 3=W 2 计算得到⎨W = 23⎪

1⎪W =⎪3⎩

1p p 12

H ∞(X ) =∑W i H (X |W i ) =3⨯H (1-p , , ) =(1-p )log +p log

3221-p p i

H (X ) =log3=1.58bit /符号 由最大熵定理可知H ∞(X ) 存在极大值

,

或者也可以通过下面的方法得出存在极大值:

⎡∂H ∞(X ) 1-p p 21⎤p

=-⎢-log(1-p ) +(-1) +log +p ⋅⋅⎥=-log

∂p 1-p 2p 2⎦2(1-p ) ⎣

p 11p p

=-+∈[0, +∞]当p=2/3时=1 又0≤p ≤1所以

2(1-p ) 22(1-p ) 2(1-p ) 2(1-p )

∂H ∞(X ) p

0

0

∂p 2(1-p )

∂H ∞(X ) p

2/3

∂p 2(1-p )

所以当p=2/3时H ∞(X ) 存在极大值, 且H ∞(X ) max =1.58bit /符号

所以H ∞(X ) ≤H (X , )

练习题：有一离散无记忆信源，其输出为X ∈{0,1,2}，相应的概率为

p 0=1/4, p 1=1/4, p 2=1/2，设计两个独立的实验去观察它，其结果分别为

Y 1∈{0,1}, Y 2∈{0,1}，已知条件概率:

(1) 求I (X ; Y 1) 和I (X ; Y 2) ，并判断哪一个实验好些

(2) 求I (X ; Y 1Y 2) ，并计算做Y 1和Y 2两个实验比做Y 1和Y 2中的一个实验可多得多少关于

X 的信息

(3) 求I (X ; Y 1|Y 2) 和I (X ; Y 2|Y 1) ，并解释它们的含义

P(y1=0)=p(y1=1)=1/2 p(y2=1)=p(y2=1)=1/2

11111

∴I (X ; Y 1) =H (Y 1) -H (Y 1|X ) =log 2-log -log -2⨯log 2=0.5bit/符号

42424111

I (X ; Y 2) =H (Y 2) -H (Y 2|X ) =log 2

-log1-log1-log1=1bit /符号>I (X ; Y 1)

442

所以第二个实验比第一个实验好

（2）因为Y 1和Y 2 相

互独立，所以

p (y 1y 2|x ) =p (y 1|x ) p (y 2|x )

111

∴I (X ; Y 1Y 2) =H (Y 1, Y 2) -H (Y 1Y 2|X ) =log 4-log1-log1-⨯2log 2bit/符号

444

=1.5bit/符号

由此可见，做两个实验比单独做Y 1可多得1bit 的关于X 的信息量，比单独做Y 2多得0.5bit 的关于X 的信息量。 （3）

I (X ; Y 1|Y 2) =H (X |Y 1) -H (X |Y 1, Y 2) =H (X , Y 2) -H (X ) -[H (X ) -I (X ; Y 1, Y 2)]=[H (X ) -I (X ; Y 2)]-[H (X ) -I (X ; Y 1, Y 2)]=I (X ; Y 1, Y 2) -I (X ; Y 2)

=1.5-1=0.5bit/符号

表示在已做Y2的情况下，再做Y1而多得到的关于X 的信息量 同理可得

I (X ; Y 2|Y 1) =I (X ; Y 1, Y 2) -I (X ; Y 1) =1.5-0.5=1bit/符号

表示在已做Y1的情况下，再做Y2

而多得到的关于X 的信息量