信息论与编码第2章习题解答.doc

2.1设有12枚同值硬币，其中一枚为假币。只知道假币的重量与真币的重量不同，但不知究竟是重还是轻。现用比较天平左右两边轻重的方法来测量（因无砝码）。为了在天平上称出哪一枚是假币，试问至少必须称多少次？
解：分三组，每组4个，任意取两组称。会有两种情况，平衡，或不平衡。
  (1) 平衡：
明确假币在其余的4个里面。从这4个里面任意取3个，并从其余8个好的里面也取3个称。又有 两种情况：平衡或不平衡。
a）平衡：称一下那个剩下的就行了。
b）不平衡：我们至少知道那组假币是轻还是重。
从这三个有假币的组里任意选两个称一下，又有两种情况：平衡与不平衡，不过我们已经知道假币的轻重情况了，自然的，不平衡直接就知道谁是假币；平衡的话，剩下的呢个自然是假币，并且我们也知道他是轻还是重。
(2) 不平衡：
假定已经确定该组里有假币时候：
推论1：在知道该组是轻还是重的时候，只称一次，能找出假币的话，那么这组的个数不超过3。
     我们知道，只要我们知道了该组（3个）有假币，并且知道轻重，只要称一次就可以找出来假币了。
从不平衡的两组中，比如轻的一组里分为3和1表示为“轻（3）”和“轻（1）”，同样重的一组也是分成3和1标示为“重（3）”和“重（1）”。在从另外4个剩下的，也就是好的一组里取3个表示为“准（3）”。交叉组合为：
      轻（3） +  重（1  ？=======？ 轻（1） +  准（3）
来称一下。又会有3种情况：
(1)左面轻：这说明假币一定在第一次称的时候的轻的一组，因为“重（1）”也出现在现在轻的一边，我们已经知道，假币是轻的。那么假币在轻（3）里面，根据推论1，再称一次就可以了。
(2)右面轻：这里有两种可能：
“重（1）”是假币，它是重的，或者“轻（1）”是假币，它是轻的。这两种情况，任意 取这两个中的一个和一个真币称一下即可。
(3)平衡：假币在“重（3）”里面，而且是重的。根据推论也只要称一次即可。
2.2 同时扔一对骰子，当得知“两骰子面朝上点数之和为2”或“面朝上点数之和为8”或“骰子面朝上之和是3和4”时，试问这三种情况分别获得多少信息量？
解：设“两骰子面朝上点数之和为2”为事件A，则在可能出现的36种可能中，只能个骰子都为1，这一种结果。即：
P（A）=1/36，I（A）= P（A）=36≈5.17 比特
设“面朝上点数之和为8”为事件B，则有五种可能：2、6；6、2；4、4；3、5；5、3；即：
P（B）= 5/36，I（B）= P（B）= 36/5≈2.85 比特
设“骰子面朝上之和是3和4”为事件C，则有两种可能：3、4；4、3；即：
P（C）= 2/36，I（C）= P（C）= 36/2≈4.17 比特
2.3 如果你在不知道今天是星期几的情况下问你的朋友“明天是星期几？”则答案中含有多少信息量？如果你在已知今天是星期四的情况下提出同样的问题，则答案中你能获得多少信息量（假设已知星期一至星期日的排序）
解：（1）P＝1/7 I＝－Log2P＝－Log27
（2）已知今天星期四，问明天是星期几？
即：明天是星期五是必然事件，不存在不确定性，I＝0。
2.4地区的女孩中有25％是大学生，在女大学生中有75％是身高1.6米以上的，而女孩中身高1.6米以上的占半数一半。假如我们得知“身高1.6米以上的某女孩是大学生”的消息，问获得多少信息量？
解：设A为女大学生,B为1.6米以上的女孩
则依题意有: , ,

所以信息量为
2.5一副充分洗乱了的牌（含52张牌），试问
(1) 任一特定排列所给出的信息量是多少？
(2) 若从中出去抽取13张牌，所给出的点数都不相同时得到多少信息量？
解：（1）任一排列发生的概率为1/52!
I＝log52!＝225.58 bit
（2）13张牌点数都不相同发生的概率为1/413
I＝log413＝26 bit
2. 设离散无记忆信源=,其发出的消息为（202120130213001203210110321010021032 011223210），求：
（1）此消息的自信息是多少？
（2）在此消息中平均每个符号携带的信息量是多少？
解：(1) 因为离散信源是无记忆的，所以起发出的消息序列中各符号是无依赖且统计独立的。因此，此消息的自信息就为该消息中各符号自信息之和。
I（）= −log P（） = −log= 1.415 比特
I（）= − log P（）= −log=2比特
I（）= −log P（）= −log=2比特
I（）= −log P（）= −log=3比特
则此消息的自信息是：
I=14I（）+ 13I（）+12 I（）+ 6I（）
141.415+132+122+63
87.81比特
(2)此消息中平均每个符号携带的信息量是：
　I=87.81451.95比特/符号
2.7如有6行8列的棋型方格，若又二个质点A和B，分别以等概率落入任一方格内，他们的坐标分别为（XA,YA）,(XB,YB),但A.B不能落入同一方格内。
（1）如仅有质点A，求A落入任一个格的平均自信息量是多少？
（2）若已知A已落入，求B落入的平均自信息量。
（3）若A,B是可分辨的，求A,B同都落入的平均自信息量。
解:(1) H(XA)=－=log24
(2) H(XB/XA)=－
=－24
(3) H(XAXB)=－
=
=－24*23**log(*)
=log24*23=log23+log24
2.8 从大量统计资料知道，男性中红绿色盲的发病率为7％，女性发病率为0.5％，如果你问一位男同志：“你是否是红绿色盲？”他的回答可能是“是”，可能是“否”，问这二个答案中各含多少信息量？平均每个回答中含有多少信息量？如果你问一位女同志，则答案中含有的平均自信息量是多少？
解：（1） 若男同志回答“是”：I＝log(1/7%)＝3.84 bit
回答“否”：I＝log(1/93%)＝0.1 bit
平均信息量为：I＝－7%log7%－93%log93%＝0.36 bit
（2） 若问女同志，平均信息量为：I＝－0.5%log0.5%－99.5%log99.5%＝0.045 bit
2.9设信源求这信源的熵，并解释为什么，不满足信源熵的极值性。
解：信源的熵为：

bit/符号
是因为此信息的,不满足信息熵极值性的条件。
2.10设离散无记忆信源S其符号集A{a1,a2,...,aq},知其相应的概率分布为（P1,P2,...,Pq）。设另一离散无记忆信源S’， 其符号集为S信源符号集的两倍，A’={ai}i=1,2,...,2q,并且各符号的概率分布满足：
Pi’=(1-ε)Pi (i=1,2,...,q)
Pi’=εPi-q (i=q+1,q+2,..2q)
试写出信源S’信息熵与信源S的信息熵的关系。
解：S： a1 a2 …… aq
P：　p1 p2 …… pq
H（X）＝－Σqi＝1PiLogPi
Σqi＝1Pi　＝1
S`：　a1 a2 ……aq aq＋1……a2q
　P ：　p，1 p，2……p，qp，q＋1……p，2q
H（X）＝－Σ2qi＝1P，iLogP，i
＝－〔Σqi＝1P，iLogP，i＋Σ2qi＝q＋1P，iLogP，i〕
＝－{Σqi＝1（1－ε）Pi〔Log（1－ε）＋LogPi〕＋Σ2qi＝q＋1εPi－q（Logε＋LogPi－q）}
＝－{（1－ε）Σqi＝1PiLog（1－ε）＋（1－ε）Σqi＝1PiLogPi＋εΣ2qi＝q＋1Pi－qLogε＋εΣ2qi＝q＋1Pi－qLogPi－q}
＝－{（1－ε）Σqi＝1PiLogPi＋εΣ2qi＝q＋1Pi－qLogPi－q＋（1－ε）Log（1－ε）Σqi＝1Pi＋εLogεΣ2qi＝q＋1Pi－q}
＝－{（1－ε）Σqi＝1PiLogPi＋εΣqj＝1PjLogPj＋（1－ε）Log（1－ε）Σqi＝1Pi＋εLogεΣqj＝1Pj}
＝－{Σqi＝1PiLogPi＋〔（1－ε）Log（1－ε）＋εLogε〕Σqi＝1Pi}
＝H（X）－〔（1－ε）Log（1－ε）＋εLogε〕Σqi＝1Pi
＝H（X）－（1－ε）Log（1－ε）－εLogε
即：H,（X）＝H（X）－（1－ε）Log（1－ε）－εLogε
2.13 （1）为了使电视图象获得良好的清晰度和规定的适当的对比度，需要用5*105个象素和10个不同的亮度电平，求传递此图象所需的信息率（比特/秒）。并设每秒要传送30帧图像，所有象素是独立变化，且所有亮度电平等概率出现。
（2）设某彩电系统，除了满足对于黑白电视系统的上述要求外，还必须有30个不同的色彩度，试证明传输这彩色系统的信息率要比黑白系统的信息率约大2.5倍。
解：（1）因为每帧图象可以看成是离散的数字图象，每个像素的亮度是随机而且等概率出现的，则每个像素亮度信源的概率空间为：= =1
每个像素亮度含有的信息量为：H(X)=log2103.32比特/像素=1哈特/像素
现在，所有的像素是独立变化的，则每帧图象可以看成是离散亮度信源的无记忆N次扩展信源。故，每帧图象含有的信息量是：
H(XN)=NH(X)=5105log10=5105哈特/帧1.66106比特/帧
而每秒传送30帧图象，则传递这个图象所需要的信息率为
R1=30H(XN)=1. 5106哈特/秒498107比特/秒
（2）证明：每个像素具有10个不同的亮度和30个色彩度。由上面的计算得亮度等概率出现的情况下，每个像素含有的信息量是：H(X)=log2103.32比特/像素。每个像素的色彩度也是等概率出现的，则色彩度信源的概率空间为：
= =1
每个像素色彩度含有的信息量：
H(Y)=log2304.91比特/像素
而亮度和色彩度是相互独立的，所以亮度和色彩度同时出现，每像素含有的信息量：
H(XY)=H(X)+H(Y)=log10+log30=log3008.23比特/像素
如果每帧所用的像素数和每秒传送的帧数都相同的情况下，传输这彩色系统的信息率与传输黑白系统的信息率之比就等于彩色系统每像素含有的信息量与黑白系统每像素含有的信息量之比：
　　　　　　　=2.5
证毕。
2.14每帧电视图像可以认为是由3×105个像素组成,所以像素均是独立变化,且每一像素又取128个不同的亮度电平,并设亮度电平等概率出现.问每帧图像含有多少信息量?现有一广播员在约10000个汉字的字汇中选1000个字来口述此电视图像,试问广播员描述图像所广播的信息量是多少(假设汉字字汇是等概率分布,并彼此无依赖)?若要恰当地描述图像,广播员在口述中至少需要多少汉字?
解: ∵亮度电平等概率出现
　　∴每个像素所含的信息量为 H(X)=log 128=7 bit/像素.
　　而每个像素均是独立变化的
　　 ∴每帧电视图像所包含的信息量为 H(X)= 3×105H(X)= 2.1×106bit
　　 ∵假设汉字字汇是等概率分布
　　∴每个汉字出现的概率均为
从而每个汉字携带的信息量为log 10000=13.2877 bit/字
　　 ∵汉字间彼此无依赖, 广播员口述的1000个汉字所广播的信息量为
1000×13.2877=13287.7 bit
若要恰当地描述图像,广播员在口述中至少需要的汉字数为≈15841个汉字。
2.15 为了传输一个由字母A、B、C、D组成的符号集，把每个字母编码成两个二元码脉冲序列，以00代表A，01代表B，10代表C，11代表D。每个二元脉冲宽度为5ms。
（1）不同字母等概率出现时，计算传输的平均信息速率？
（2）若每个字母出现的概率分别为pA=1/5,pB=1/4,pC=1/4,pD=3/10，试计算传输的平均信息速率？
解：（1）由题可知，当不同字母等概率出现时，平均自信息量为：
H(x)=log4=2(比特/字母)
又因为每个二元脉冲宽度为5ms,故一个字母的脉冲宽度为10ms
则字母的传输速率为 100字母/秒
故传输的平均信息速率为：200 比特/秒
(2) 当每个字母分别以题中的概率出现时，平均自信息量为：
H(x)=－∑P(ai)logP(ai)
=(1/5)*log5+2*(1/4)*log4+(3/10)*log(10/3)=1.98(比特/字母)
同样字母的传输速率为 100个/秒
故传输的平均信息速率为：198 比特/秒
2.18 设有一个信源,它产生0,1序列的消息.它在任意时间而且不论以前发生过什么符号,均按P(0)=0.4,P(1)=0.6的概率发出符号.
(1) 试问这个信源是否平稳的?
(2) 试计算H(X2),H(X3|X1X2)及.
(3) 试计算H(X4)并写出X4信源中可能有的所有符号.
解：(1) 因为信源发出符号的概率分布与时间平移无关,而且信源发出的序列之间也是彼此无依赖的.所以这个信源是平稳信源,是离散无记忆信源.
(2) ＝,计算H(X)≈0.971 bit/符号
因为信源是平稳无记忆信源,所以H(X2)=2H(X)≈1.942 bit/两个符号
H(X3|X1X2)=H(X3)=H(X)≈0.971 比特/符号
===H(X)≈0.97 bit/符号
(3) H(X4)=4H(X)≈3.884 bit/四个符号
可能的所有16个符号:0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
2.19 有一个元无记忆信源，其发0的概率为p，而p约等于1，所以在发出的二元序列中经常出现的是那些一串为0的序列（称为高概率序列）。对于这样的信源我们可以用另一新信源来代替，新信源中只包含这些高概率序列。这时新信源Sn={S1 , S2 , S3 , ……, Sn , Sn+1},共有n+1个符号，它与高概率的二元序列的对应关系如下：
二元序列：001,01,0001,00000001,1 ,…,00…01(n位),00…000(n位)
新信源符号：S3,S2, S4, S8, S1,…, Sn, Sn+1
(1) 求H（Sn）
(2) 当 时求信源的熵
解：依题意，因为是二元无记忆信源，在发出的二元序列中符号之间彼此是无依赖的，统计独立的，所以有：
1, 2
由此可得新信源Sn为：

证明满足完备性：

因为 所以，则：

2.21有一信源，它在开始时以P(a)=0.6,P(b)=0.3,P(c)=0.1的概率发出X1。如果X1为a时，则X2为a、b、c的概率为1/3；如果X1为b，X2为a、b、c的概率为1/3；如果X1为c，X2为a、b的概率为1/2，为c的概率为0，而且后面发出Xi的概率只与Xi-1有关，又P(Xi|Xi-1)=P(X2|X1) i≥3。是利用马尔可夫信源的图示法画出状态转移图，并计算信源熵H∞。
解：由题可得，状态转移图为：
a:0.6
b:0.3
c:0.1
b:1/2
a:1/2
c:1/3
a:1/3
c:1/3
a:1/3
b:1/3
b:1/3
a
b
c
a
b
c
a
b
c
a
E0
E1
E2
E3
E4
E5

E6
E7
E8
E9
E10
E11
b

可见，状态E1和E4、E7、E10的功能是完全相同的，
状态E2和E5、E8、E11的功能是完全相同的，
状态E3和E6、E12的功能是完全相同的。
其中E0是过渡状态，而E1、E2、E3组成一个不可约闭集，具有遍历性。故有如下的状态转移图A;由于此马尔可夫信源的状态必然会进入这个不可约闭集，所以计算信源熵时，可以不考虑过渡状态和过渡过程。由此，可得状态E1、E2、E3的极限概率：
Q(E1)=1/3Q(E1)+1/3Q(E2)+1/2Q(E3)
Q(E2)=1/3Q(E1)+1/3Q(E2)+1/2Q(E3)
Q(E3)=1/3Q(E1)+1/3Q(E2)
Q(E1)+Q(E2)+Q(E3)=1
可得： Q(E1)=Q(E2)=3/8， Q(E3)=1/4
c:1/3
c:1/3
b:1/2
b:1/3
c:0.1
b:0.3
a:0.6
c:1/3
b:1/2
a:1/3
E2
E3
E0
E1
a:1/3

图A
所以H∞=H2=Q(E1)H(1/3,1/3,1/3)+Q(E2)H(1/3,1/3,1/3)+Q(E3)H(1/2,1/2)
=1.4388(比特/符号)
2.22 一阶马尔可夫信源的状态图如图2.8所示，信源X的符号集为并定义。
(1) 求信源平稳后的概率分布；
(2) 求此信源的熵；
(3) 近似认为此信源为无记忆时，符号的概率分布等于平稳分布。求近似信源的熵并与进行比较；
(4) 对一阶马尔可夫信源取何值时取最大值，又当时结果如何？
解：（1），由图可得

于是得到

整理计算得
即
（2） 据一阶马尔可夫信源的熵的表达式可得

（3） 信源近似为无记忆信源，符号的概率分布等于平稳分布，则此信源

得到：
由此计算结果可知
（4） 求一阶马尔可夫信源的最大值。因为

求其对p的一阶导数

令，得，所以，所以时，达到最大值；的最大值等。
当时
当时
由此可以看出上面的结论时正确的。
2.23 一阶马尔可夫信源的状态图如图2.9所示，信源X的符号集为{0,1,2}。
（1） 求平稳后信源的概率分布。
（2） 求信源的熵H∞。
（3） 求当p=0和p=1时信源的熵，并说明其理由。
p

p
p

1
0

p
p

2

p

解：（1）由图可知一阶马尔可夫信源的状态空间E=A={0,1,2}.平稳后信源的概率分布就等于一阶马尔可夫信源状态的极限分布，即Q(Ei)＝P(ai) i＝1,2,3
Ei∈E,ai∈A,而E＝A
从状态图中分析可知，这三个状态都是正规常返态，所以此马尔可夫链具有各态历经性，平稳后状态的极限分布存在。可得状态一步转移矩阵
得
Q(0)＝Q(1)＝Q(2)＝1/3
则可得 P(0)＝P(1)＝P(2)＝1/3
(2) 一阶马尔可夫信源的熵
H∞＝H2＝∑I=13Q(Ei)H(X∣Ei)
＝P(0)H(X∣E)+P(1)H(X∣1)+P(2)H(X∣2)
＝1/3H(P1,0,P)+1/3H(P,P1,0)+1/3H(0,P,P1)
＝-P1㏒P1-P㏒P
＝H(P)

(3) 当P＝0 ,H∞＝0
当P＝1 ,H∞＝1
因为信息熵是表示信源的平均不确定性，题中当P=1或P=0时表明信源从某一状态出发转移到另一状态的情况是一定发生或一定不发生，即是确定的事件。当P=1时，从0状态一定转移到2状态，2状态一定转移到1状态，1状态一定转移到0状态。所以不论从何状态起信源输出的序列一定是021021序列，完全确定的。当P=0时，0状态永远处于0状态，1状态永远处于1状态，2状态用于处于2状态。信源输出的符号序列也是确定的。所以当P=1或P=0时，信源输出什么符号不存在不确定性，完全是确定的，因此确定信源的信息熵等于零。
2.24 设有一个马尔可夫信源,它的状态集为{s1,s2,s3},符号集为{a1,a2,a3},及在某状态下发符号的概率为P(ak|si)(i,k=1,2,3),如下图所示.
S1
S2
S3
a1:½
a2:¼
a2:½
a3:½
a3:¼
a1:1

(1) 求出图中马尔可夫信源的状态极限概率并找出符号的极限概率
(2) 计算信源处在某一状态下输出符号的条件熵H(sj)(j=1,2,3).
(3) 求出马尔可夫信源熵H∞.
解: (1) 此信源的状态集不等于符号集,从状态转移图可知
P(a1|s1)=1/2, P(a1|s1)=0, P(a1|s3)=1
P(a2|s1)=1/4, P(a2|s2)=1/2, P(a2|s3)=0
P(a3|s1)=1/4, P(a3|s2)=1/2, P(a3|s3)=0
状态转移概率为P(s2|s1)= P(a1|s1)+ P(a2|s1)=3/4
P(s3|s1)= P(a3|s1)=1/4
P(s1|s1)=0
P(s1|s2)= 0
P(s2|s2)= P(a2|s2)=1/2
P(s3|s2)= P(a3|s2)=1/2
P(s1|s3)= P(a1|s3)=1
P(s2|s3)= P(a2|s3)=0
P(s3|s4)= P(a3|s3)=0
得状态转移矩阵: P=
从图可知 此状态马尔可夫链是时齐的,状态数有限的和是不可约闭集,所以其具有各态历经性,平稳后状态的极限概率分布存在.
得到如下方程组：
Q(s1)= Q(s3)
Q(s2)=3/4 Q(s1)+1/2 Q(s2)
Q(s3)=1/4 Q(s1)+1/2 Q(s2)
Q(s1)+ Q(s2)+ Q(s3)=1
解得： Q(s1)=2/7, Q(s2)=2/7, Q(s3)=3/7
符号的极限概率 P(ak) =
所以P(a1)=Q(s1)P(a1|s1)+ Q(s2)P(a1|s2)+ Q(s3)P(a1|s3)=3/7,P(a2)=2/7, P(a3)=2/7

(2) 信源处于某一状态下的输出符号的条件熵
H(X|sj)= - j=1,2,3
H(X|s1)= - P(a1|s1)log P(a1|s1) - P(a2|s1)log P(a2|s1) - P(a3|s1)log P(a3|s1)
=-1/2log21/2-1/4log21/4-1/4log21/4
=1.5 比特/符号
H(X|s2)=H(0,1/2,1/2)=1比特/符号
H(X|s2)=H(1,0,0)= 0比特/符号
（3）马尔可夫信源熵
H∞=
= Q(s1)H(X|s1)+ Q(s2)H(X|s2)+ Q(s3)H(X|s3)
=2/7×1.5+3/7×1+0
=6/7比特/符号
≈0.857比特/符号
2.25黑白气象传真图的消息只有黑色和白色两种，即信源X＝{黑，白}，设黑色出现的概率为P（黑）＝0.3，白色的出现概率为P（白）＝0.7。
（1） 假设图上黑白消息出现前后没有关联，求熵H（X）。
（2） 假设消息前后有关联，其依赖关系为P（白|白）＝0.9，P（黑|白）＝0.1，P（白|黑）＝0.2，P（黑|黑）＝0.8，求此一阶马尔可夫信源的熵H2。
（3） 分别求出上述两种信源的剩余度，并比较H（X）和H2的大小，并说明其物理意义。
解：（1）如果图上黑白消息出现没有关联，则熵为：
H（X）=H0.7，0.3）=0.881bit/符号
（2）设白为w，黑为b 那么对应两种状态Sw和Sb 那么转移概率为
Sw à Sb 0.1
Sw à Sw 0.9
Sb à Sw 0.2
Sb à Sb 0.8
则 Q（Sw）=0.9 Q（Sw）+0.2 Q（Sb）
Q（Sb）=0.8 Q（Sb）+0.1 Q（Sw）
Q（Sb）+ Q（Sw）=1
由以上三式可得出Q（Sw）=2/3，Q（Sb）=1/3
所以P（w）= Q（Sw）*0.9+ Q（Sb）*0.2=2/3
P（B）= Q（Sw）*0.1+ Q（Sb）*0.8=1/3
由以上可得到：
H2=H（0.9，0.1）*2/3+ H（0.8，0.2）*1/3 =0.554bit/符号
（3）最大熵H0=H（0.5，0.5）=1，则信源一的剩余度为 1-0.881=0.118
信源二的剩余度为1-0.554=0.446
推出H（x）>H2
这说明消息前后有关联的熵小于信息前后没有关联的熵，即传送相同符号数后消息前后无关联所获得的信息量大于前后有关联的信息量。
- 10 -