信息论习题

解： 根据条件熵公式：

H(X/Y)p(xiyj)log2p(xi/yj)

j1i1mnp(xi/yj)p(xiyj)2p(yj)

首先求p(yj)p(xiyj)，有

i131p(0)p(y10)p(x1y100)p(x2y110)c881同理可求得p(1)p(y21)2从而有：p(00)p(x1y100)1/81p(0/0)p(x10/y10)p(1/1)p(0)p(y10)1/243p(1/0)p(0/1),4H(X/Y)p(00)log2p(0/0)p(01)log2p(0/1)p(10)log2p(1/0)p(11)log2p(1/1)1331log2log220.40848X[例2.1.5]将已知信源x1P(X)0.5(bit/symbol)x2接到下图所示的0.5—

信道上，求在该信道上传输的平均互信息量I(X;Y)、疑义度H(X/Y)、噪声熵H(Y/X)和联合熵H(XY)。 x 0.98 y 0.02

0.2 x 0.8 y

1122

解：（1）由P(xiyj)p(xi)p(yj/xi),求出各联合概率： p(x1y1)p(x1)p(y1/x1)0.50.980.49

p(x1y2)p(x1)p(y2/x1)0.50.020.01 p(x2y1)p(x2)p(y1/x2)0.50.200.10 p(x2y2)p(x2)p(y2/x2)0.50.800.40

（2）由P(yj)P(xiyj),得到Y集各消息概率：

i1np(y1)P(xiy1)p(x1y1)p(x2y1)0.490.100.59

i12p(y2)1p(y1)10.590.41

（3）由p(xi/yj)p(xiyj)p(yj)，得到X的各后验概率：

p(x1y1)0.49p(x1/y1)0.831

p(y1)0.59p(x2/y1)1p(x1/y1)0.169

同样可推出p(x1/y2)0.024,p(x2/y2)0.976

欢迎下载 2

—

（4）H(X)p(xi)log2p(xi){0.5log20.50.5log20.5}1(比特/符号)

i12H(Y)p(yi)log2p(yi){0.59log20.590.41log20.41}

i12 =0.98(比特/符号)

H(XY)p(xiyj)log2p(xiyj)

i1j1nm{0.49log20.490.01log20.010.10log20.100.40log20.40}

= 1.43（比特/符号）

（5）平均互信息

I(X;Y)H(X)H(Y)H(XY)10.981.430.55(比特/符号）

（6）疑义度

H（X/Y）p(xiyj)log2p(xi/yj)

i1j122{0.49log20.8310.01log20.0240.10log20.1690.40log20.976}

0.45(比特/符号）

（7）噪声熵

H（Y/X）p(xiyj)log2p(yj/xi)

i1j122{0.49log20.980.01log20.020.10log20.200.40log20.80}

欢迎下载 3

—

0.43(比特/符号）

[例2.2.1]有一离散平稳无记忆信源

x1,x2,x3XP(X)111,,244p(x)1，求此信源的二次扩展

ii13信源的熵。

先求出此离散平稳无记忆信源的二次扩展信源。扩展信源的每个元素是信源X的输出长度为2的消息序列。由于扩展信源是无记忆的，故

p(ai)p(xi1)p(xi2)X2信源(i1,i21,2,3;i1,2,,9)

的元素 a1 a2 a3 a4 a5 a6 a7 a8 a9 x1x1 x1x2 x1x3 x2x1 x2x2 x2x3 x3x1 x3x2 x3x3 1 41 81 81 81 161 161 81 161 16对应的消息序列 概率p(ai)

根据熵的定义，二次扩展信源的熵为

H(XN)3(比特/符号)2H(X)

结论：计算扩展信源的熵时，不必构造新的信源，可直接从原信源X的熵导出。即离散平稳无记忆信源X的N次扩展信源的熵为离散信源X的熵的N倍。

欢迎下载

4

—

[例2.2.2]设某二维离散信源X=X1X2的原始信源X的

xX1信源模型为1P(X)4x249x3X=X1X2中前后两个符号11，36的条件概率为

X2 x1 P(X2/X1) X1 x2 x3 x1 x2 x3 7/9 1/8 0 2/9 3/4 2/11 0 1/8 9/11

原始信源的熵为：

H(X)p(xi)log2p(xi)1.2(bit/symbol)

i13由条件概率确定的条件熵为：

H(X2/X1)p(xi)p(xi/xi)log2p(xi/xi)0.870(bit/symbol)i11i211212133条件熵比信源熵（无条件熵）减少了0.672bit/symbol,正是由于符号之间的依赖性所造成的。信源X=X1X2平均每发一个消息所能提供的信息量，即联合熵

H(X1X2)H(X1)H(X2/X1)2.412(bit/symbol)则每一个信源符号所提供的平均信息量

欢迎下载

5

—

11H2(X)H(X)H(X1X2)1.206(bit/symbol)

22小于信源X所提供的平均信息量H(X)，这同样是由于符号之间的统计相关性所引起的。

[例2.2.3]设信源符号X{x1,x2,x3}，信源所处的状态

S{e1,e2,e3,e4,e5}。各状态之间的转移情况由下图给出。

1x22x312x3141x121x24e2x2e1341x24e3x114x314e4x11e5x312

将图中信源在ei状态下发符号xk的条件概率

p(xk/ei)用矩阵表示为

x1x2x3

欢迎下载 6

—

12001143141234014141214012

由矩阵可明显看出，p(xk/ei)1,i1,2,3,4,5。另从图

k1中还可得

P(SlP(SlP(SlP(Sle2/Xlx1,Sl1e1)0e1/Xlx1,Sl1e1)1e2/Xlx2,Sl1e1)1e1/Xlx2,Sl1e1)0

所以信源满足式(4)

由图还可得状态的进一步转移概率

e1e2e3e4e5

120000141234000121400140003400 0014该信源满足式(2)-(4)，所以是马尔可夫信源，并且是时齐的马尔可夫信源。

欢迎下载

7

—

[例2.2.4]某二元2阶马尔可夫信源，原始信源X的符号集为X10,X21，其状态空间共有nm224个不同的

状态e1,e2,e3,e4，即E:{e100,e201,e310,e411}，其状态转移概率图如下，

0.8000.20.50.5010.50.510110.80.2

由上图可知，当信源处于状态00e1时,其后发生符号0的概率是0.8,即p(0|00)p(x1|e1)0.8, 状态仍停留在e1,即

p(e1|e1)p(x1|e1)0.8。当信源仍处于状态e1，而发出的符

号为1时，状态转移至01e2，故一步转移概率

p(1|00)p(x2|e1)p(e2|e1)0.2。当信源处于状态e201时，其

一步转移概率为p(0|01)p(x1|e2)p(e3|e2)0.5，

欢迎下载

8

—

p(1|01)p(x2|e2)p(e4|e2)0.5。

同理，当信源处于状态e310时，

p(0|10)p(x1|e3)p(e1|e3)0.5 p(1|10)p(x2|e3)p(e2|e3)0.5

当信源处于状态e411

p(0|11)p(x1|e4)p(e3|e4)0.2

p(1|11)p(x2|e4)p(e4|e4)0.8

这样，由二元信源X{0,1}得到的状态空间e1,e2,e3,e4和相应的一步转移概率构成的2阶马尔可夫信源模型为

e1且

4e2e4p(ej/ei)e3i,j1,2,3,4

p(ej1j/ei)1,p(ei)0 j1,2,3,4

由p(ej)p(ei)p(ej/ei)i14可求出稳定状态下的p(ej)，称为状态极限概率。

将一步转移概率代入上式得：

欢迎下载 9

—

p(e1)0.8p(e1)0.5p(e3)p(e2)0.2p(e1)0.5p(e3)p(e3)0.5p(e2)0.2p(e4) p(e4)0.5p(e2)0.8p(e4)解此方程组得

514 2

p(e2)p(e3)14p(e1)p(e4)计算极限熵

HH21p(ei)p(ej/ei)logp(ej/ei)0.8(bit/symbol)

i1j144

需要注意的是H并非在任何情况下都存在。首先应记住的是：我们讨论的是平稳信源。其次，对n元m阶马尔可夫信源来说，只有极限概率

p(ej),j1,2,,n都存在时，方能计算出H。从理论上

可以证明，如果m阶马尔可夫信源稳定后具有各态历经性，则状态极限概率p(ej)可根据式（10）求出。

必须强调的是，m阶马尔可夫信源和消息长度为m的有记忆信源，其所含符号的依赖关系不同，对相应关系的数学描述不同，平均信息量的计算公式也不

欢迎下载

10

m—

同。m阶马尔可夫信源的记忆长度虽为有限值m，但符号之间的依赖关系延伸到无穷，通常用状态转移概率（条件概率）来描述这种依赖关系。可理解为马尔可夫信源以转移概率发出每个信源符号，所以平均每发一个符号提供的信息量应是极限熵Hm1。而对于长度为m的有记忆信息源X，发出的则是一组组符号序列，每m个符号构成一个符号序列组，代表一个消息。组与组之间是相互统计的，因此符号之间的相互依赖关系仅限于符号之间的m个符号，一般用这m个符号的联合概率来描述符号间的依赖关系。对于这种有记忆信源，平均每发一个符号，（不是一个消息）提供的信息量，是m个符号的联合熵的m分之一，即平均符号熵

1Hm(X)H(X1X2Xm)

m[例2.4.1]设某单符号信源模型为

x2x3x4x5x6x7x8Xx1p(x)0.40.180.100.100.070.060.050.04 计算得

H(X)2.55(比特/符号)

2 [I(xi)]1.323

若要求编码效率为90%,即

欢迎下载

11

—

H(X)0.90

H(X)则 =0.28

设译码差错率为106，由式（3）可得

7L1.687510

由此可见，在差错率和效率的要求都不苛刻的情况下，就必须有1600多万个信源符号一起编码，技术实现非常困难。

不仅如此，它的编码效率也不高。对8种可能的取值编定长码，要无差错地译码，每种取值需用3个比特，其编码效率

2.5585%

3为了解决这一问题，就出现了不等长编码，也称变长编码。

不等长编码允许把等长的消息变换成不等长的码序列。通常把经常出现的消息编成短码，不常出现的消息编成长码。这样可使平均码长最短，从而提高通信效率，代价是增加了编译码设备的复杂度。例如在不等长码字组成的序列中要正确识别每个长度不同的码字的起点就比等长码复杂得多。另外，接收到一个不等长码序列后，有时不能

欢迎下载

12

—

马上断定码字是否真正结束，因而不能立即译出该码，要等到后面的符号收到后才能正确译出。这就是所谓的译码同步和译码延时问题。

[思考题] 已知12个球中有一个球的重量与其它球不同，其它球均等重。问用无砝码的天平至少须几次才能找出此球？

解：天平有3种状态，即平衡，左重，左轻，所以每称一次消除的不确定性为log3，12个球中的不等重球（可较轻，也可

11较重）的不确定性为：log122log24 因

为 3log3＞log24

∴3次测量可以找出该球 具体称法略。

[例一]一副充分洗乱了的牌（含52张牌），试问：

(1) 任一特定排列所给出的信息量是多少？

欢迎下载

13

—

(2) 若从中抽取13张牌，所给出的点数都不

相同能得到多少信息量？

52(1)任意排列共有P5252!种，则任一排列

1的自信息量为：log52!log52!。

(2)应将点数相同花色不同的牌看作一类，则任意抽取的13张牌应在13类中分别进行。其概率为：

C52C48C44....C413C521111，

15214814413521....CCCC4log∴ 信息量。 C[例二] 已知随机变量X和Y的联合概率分布满足：p(a)1,p(a)p(a)1,p(b)2,p(b)p(b)1

1223413236试求能使H(XY)取最大值的联合概率分布。

H(X Y) ≤ H(X) + H(Y) 等号在X、Y时取得

11ab) = P(ab) = ∴P(ab) = 1 P(3121211121311ab) = P(ab) = P(ab) = 1 P( 2424621222311ab) = ab) = P(ab) = 1 P( P( 24246313233 满足 H(XY) 取最大值

欢迎下载

14

—

[例三]求证：

I(X;Y;Z)=H(XYZ)-H(X)-H(Y)-H(Z)+I(X;Y)+I(Y;Z)+I(Z;X)

I(X;Y;Z)I(X;Y)I(X;Y|Z)H(X)H(X|Y)H(Y|Z)H(Y|XZ)H(X)H(X|Y)H(Y|Z)H(XYZ)H(XZ)H(XYZ)H(X|Y)H(Y|Z)H(Z|X)而等式右边H(XYZ)H(X)H(Y)H(Z)H(X)H(X|Y)H(Y)H(Y|Z)H(Z)H(Z|X)H(XYZ)H(X|Y)H(Y|Z)H(Z|X)故左式右式，原式成立

[例4]令X为掷钱币直至其正面第一次朝上所需的次数，求H(X)

1n1n11P(X=n) = (2)2 = (2)

11n11n()log()H(X) = 2n122

1n = n(2) = 2 bit

[例5]一个无记忆信源有四种符号0，1，2，

3111p(0),p(1),p(2),p(3)3。已知试求8448。

由6000个符号构成的消息所含的信息量。 解：先计算一个符号所含的平均自信息量，

欢迎下载

15

—

即信源熵H

p(i)logP(i) =1.9056bit H=i03无记忆信源由6000个符号构成的符号序列消息H(X6000)6000H(X)11434bit

[例6]发出二重符号序列消息的信源熵为

H(X2),而一阶马尔可夫信源的信源熵为H(XX),试比较这两者的大小，并说明原因。 解：根据公式H(XY)H(X)H(YX)，当Y和

2X为同一集合时，有H(XX)H(X)H(X)H(XX)，各种熵和条件熵均为非负值，当且仅当X中只含有一个确定性事件时才出现H（X）=0。当X中含有二个或二个以上事件时，有H（X）2＞0，及H（X）＞0，H（X|X）＞0，因为H2（X）＞0所以H（X）＞H（X|X）

说明，在一般情况下，发二重符号序列的信

2源的信源熵H（X）大于一阶马尔可夫过程的信源熵H（X|X）

2p(xx)[例7]有一个马尔可夫信源，已知113，

p(x1x2)1，p(x2x2)0，试画出该p(x2x1)13，

信源的概率转移图，并求出信源熵。 解：该信源的概率转移图为：

欢迎下载

16

—

1/3 ○ ○

2/3 (x1) 1 (x2)

在计算信源熵之前，先用转移概率求稳定状态下二个状态x1和 x2 的概率p(x1)和p(x2) 立方程：p(x1)p(x1x1)p(x1)+p(x1x2)p(x2)

=p(x1)p(x2)

23 p(x2)p(x2x1)p(x1)+p(x2x1)p(x1)

1 =3p(x1)0p(x2) p(x1)p(x2)=1

31p(x)p(x) 得124 4

p(xi)p(xjxi)logp(xjxi) 马尔可夫信源熵H = Ij得 H=0.6bit/符号

欢迎下载 17