H(Y|X)=H(Y)－I(X;Y)=0.1425 bit/信符
7．四个等概分布的消息M1，M2，M3，M4被送入如图所示的信道进行传输，通过编码使M1 = 00，M2 = 01，M3 =10，M4 =11。求输入是M1和输出符号是0的互信息量是多少？如果知道第2个符号也是0，这时带来多少附加信息量？
X Y p 0 0 p p 1 1 p 图2.6
解：信源P(M1)= P(M2)= P(M3)= P(M4)=1/4, 信道为二元对称无记忆信道，消息Mi与码字一一对应，所以设Mi
?(xi1xi2)设接收序列为Y=(y1y2)
接收到第一个数字为0，即y1=0。那么，接收到第一个数字0与M1之间的互信息为
I(M1;y1?0)?logP(y1?0|M1)
P(y1?0)因为信道为无记忆信道，所以
P(y1?0|M1)?P(y1?0|x11x12?00)?P(y1?0|x11?0)?P(0|0)?p同理，得I(y1
?0|Mi)?P(y1?0|xi1xi2)?P(y1?0|xi1)
输出第一个符号是y1=0时，
有可能是四个消息中任意一个第一个数字传送来的。 所以
P(y1?0)??P(Mi)(y1?0|Mi)i?141?[P(y1?0|x11?0)?P(y1?0|x21?0)?P(y1?0|x31?1)?P(y1?0|x41?1)]41?2I(M1;y1?0)?1?lbp 比特
接收到第二个数字也是0时，得到关于M1的附加互信息为 I(M1;y2?0|y1?0)?I(M1;y1y2?00)?I(M1;y1?0)
其中
故得
I(M1;y1y2?00)?logP(y1y2?00|M1)
P(y1y2?00)同理，因为信道是无记忆信道，
所以
P(y1y2?00|Mi)?P(y1y2?00|xi1xi2)?P(y1?0|xi1)P(y2?0|xi2)
得
P(y1y2?00|M1)?P(y1?0|x11?0)P(y2?0|x12?0)?P(0|0)P(0|0)?p42
输出端出现第一个符号和第二个符号都为0的概率为
P(y1y2?00)??P(Mi)(y1y2?00|Mi)i?11?[P(y1?0|x11?0)P(y2?0|x12?0)?P(y1?0|x21?0)P(y2?0|x21?1) 4?P(y1?0|x31?1)P(y2?0|x31?0)?P(y1?0|x41?1)P(y2?0|x41?1)]?14p2?2(1?lbp) 比特 所以I(M1;y1y2?00)?log14得附加互信息为
I(M1;y2?0|y1?0)?1?lbp 比特
8．证明若随机变量X，Y，Z构成马氏链，即X→Y→Z，则有Z→Y→X。
证明：因为(X,Y, Z)是马氏链，有P(z|xy)=P(z|y),对所有x?X,y?Y,z?Z成立，而
P(x|yz)=P(xyz)/P(yz) = P(z|xy) P(xy)/ P(y) P(z|y)
= P(z|xy) P(y) P(x|y)/ P(y) P(z|y) 对所有x?X,y?Y,z?Z成立
故得P(x|yz)=P(x|y) 对所有x?X,y?Y,z?Z成立 所以(Z,Y, X)也是马氏链。
习题（第3章）
1．发出二重符号序列消息的信源熵为H(X2)，而一阶马尔可夫信源的信源熵为H(X/X)。试比较这两者的大小，并说明原因。 2． 设随机变量序列(XYZ)是马氏链，且X：{a1, a2, …, ar}，Y：{ b1, b2, …, bs}，Z：{ c1, c2, …, cL}。又设X与Y之间的转移概率为p(bj /ai) ( i =1, 2, …, r；j =1, 2, …, s)；Y与Z之间的转移概率为p(ck /bj) ( j =1, 2, …, s；k =1, 2, …, L)。试证明X与Y之间的转移概率为
p?ck/ai???p?bj/ai?p?ck/bj?
j?1s
3． 有一个马尔可夫信源，已知p(x1x1)?23，p(x2x1)?13，p(x1x2)?1，p(x2x2)?0，
试画出该信源的香农线图，并求出信源熵。
2一步转移矩阵为P，P?[3113] 02?Q(x)??13Q(x1)?Q(x2)?1?可得 ? Q(x2)?Q(x1)3??Q(x2)?Q(x1)?1??3Q(x1)?4 故 {1Q(x2)?4所以，信源熵为
H??H2????Q(Ei)P(ak|Ei)logP(ak|Ei)i?1k?12221??Q(Ei)H(ak|Ei)?Q(x1)H(,)?Q(x2)H(1,0)
33i?13231?[log?log3]?0.6887比特/符号4323
4．一个马尔科夫链的基本符号为0，1，2三种，他们以等概率出现，且具有相同的转移概率，没有任何固定约束，试（1）画出单纯马尔科夫链信源的香农线图，并求稳定状态下的信源熵H1。（2）画出二阶马尔科夫链信源的香农线图，并求稳定状态下的信源熵H2。 解：（1）由已知得P(j|i)?21 i,j?0,1,2则香农线图如下 3 1/3 1/3 1/3 0 1/3 1/3 1/3 1/3 1/3 2 1/3 1
稳定时 H(X)?3?log bit/符号 3?1.585
13（2）二阶马尔可夫信源，初始状态有3?9个，等概分布
2 P(m|ij)?2221 3 H2????P(m|ij)logP(m|ij)?1.585 bit/符号
i?0j?0m?001 00 02 10 22 21 20 12 11
图中每条路径概率均为1/3
5．某一阶马尔可夫信源的状态转移如图3.4所示，信源符号集为X：{0, 1, 2}，并定义p?1?p。试求：
（1） 信源的极限熵H?；
（2） p取何值时H?取最大值。
p p p/2 0 p/2 p/2 p/2 p/2 p/2 2 1 p 图3.4
解：（1）
?p?p一步转移矩阵为P，P???2?p??2p2pp2p?2?p? 2?p???pp?Q(0)?pQ(0)?Q(1)?Q(2)?22?pp?Q(1)?Q(0)?pQ(1)?Q(2)可得 ? 22?ppQ(2)?Q(0)?Q(1)?pQ(2)?22?Q(0)?Q(1)?Q(2)?1?计算得Q(0)?Q(1)?Q(2)?1 3则得P(0)?P(1)?P(2)?所以，信源熵为
1 3H??H2??Q(Ei)H(X|Ei)i?12?P(0)H(X|0)?P(1)H(X|1)?P(2)H(X|2)1pp1pp1pp?H(p,,)?H(,p,)?H(,,p)322322322??plogp?plogp?p比特/符号
（2）因为 H???(1?p)log(1?p)?plogp?p 求其对p的一阶导数
?H?11?log(1?p)??logp??1?pln2ln2
2(1?p)?log(1?p)?logp?log2?logp令
?H?2(1?p)?0,得log?0 ?pp所以当p=2/3时，信源的极限熵达到最大值。 6．设随机变量序列X=X1X2?XN通过某离散信道{X; P(Y/X); Y}，其输出序列为Y=Y1Y2?YN。试证明若
（1）p (bjN / ai1 ai1…aiN；bj1 bj2…bjN –1) = p (bjN / aiN)；
（2）p (bj1 bj2…bjN –1 / ai1 ai1…aiN) = p (bj1 bj2…bjN –1 / ai1 ai1…aiN–1) 则该信道的转移概率为
P(X/Y)?p?bj1bj2?bjN/ai1ai2?aiN???p?bjk/aik?
k?1N证明：
?p?bj1bj2?bjN?1/ai1ai2?aiN??p?bjN/ai1ai2?aiN;bi1bi2?biN?1??p?bj1bj2?bjN?1/ai1ai2?aiN?1??p?bjN/aiN??...??p?bjk/aik?k?1NP(X/Y)?p?bj1bj2?bjN/ai1ai2?aiN?
?p?bj1bj2?bjN?2/ai1ai2?aiN?2??p?bjN?1/aiN?1??p?bjN/aiN?7．设信源X的N次扩展信源X=X1X2?XN通过信道{X; P(Y/X); Y}，其输出序列为Y=Y1Y2?YN。试证明
（1） 当信源为无记忆信源，即X1X2?XN之间统计独立时，有
?I?Xk;Yk??I?X;Y?；
k?1N