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

1、2.1 设有 12 枚同值硬币，其中一枚为假币。只知道假币的重量与真币的重量不同，但不知究竟是重还是轻。现用比较天平左右两边轻重的方法来测量（因无祛码）。为了在天平上称出哪一枚是假币，试问至少必须称多少次？解：分三组，每组 4 个，任意取两组称。会有两种情况，平衡，或不平衡。（1）平衡：明确假币在其余的 4 个里面。从这 4 个里面任意取 3 个，并从其余 8 个好的里面也取 3 个称。又有两种情况：平衡或不平衡。a）平衡：称一下那个剩下的就行了。b）不平衡：我们至少知道那组假币是轻还是重。从这三个有假币的组里任意选两个称一下，又有两种情况：平衡与不平衡，不过我们已经知道假币的轻重情况了，自然

2、的，不平衡直接就知道谁是假币；平衡的话，剩下的呢个自然是假币，并且我们也知道他是轻还是重。（2）不平衡：假定已经确定该组里有假币时候：推论 1:在知道该组是轻还是重的时候，只称一次，能找出假币的话，那么这组的个数不超过 3。我们知道，只要我们知道了该组（3 个）有假币，并且知道轻重，只要称一次就可以找出来假币了。从不平衡的两组中，比如轻的一组里分为 3 和 1 表示为轻（3）”和轻（1）”，同样重的一组也是分成 3 和 1 标示为重（3）”和重（1）在从另外 4 个剩下的，也就是好的一组里取 3 个表示为推（3）交叉组合为：轻（3）+重（1）?=?轻（1）+准（3）来称一下。又会有 3 种情况

3、：（1）左面轻：这说明假币一定在第一次称的时候的轻的一组，因为重（1）”也出现在现在轻的一边，我们已经知道，假币是轻的。那么假币在轻（3）里面，根据推论 1,再称一次就可以了。（2）右面轻：这里有两种可能：重（1）”是假币，它是重的，或者轻（1）”是假币，它是轻的。这两种情况，任意取这两个中的一个和一个真币称一下即可。（3）平衡：假币在重（3）”里面，而且是重的。根据推论也只要称一次即可。2.2同时扔一对骰子，当得知“两骰子面朝上点数之和为 2”或“面朝上点数之和为 8”或“骰子面朝上之和是 3 和 4”时,试问这三种情况分别获得多少信息量？解：设“两骰子面朝上点数之和为 2”为事件 A,则在

4、可能出现的 36 种可能中，只能个骰子都为 1,这一种结果。即：P（A）=1/36I（A）=10g2P（A）=log2365.17 上第设“面朝上点数之和为 8”为事件 B,则有五种可能：2、6;62;44;3、5;5、3;即：P（B）=5/36I（B）=10g2P（B）=log236/52.85 上第设“骰子面朝上之和是 3 和 4”为事件 C,则有两种可能：&4;4、3;即：P(C)=2/36I(C)=10g2P(C)=log236/24.17 由特2.3如果你在不知道今天是星期几的情况下问你的朋友“明天是星期几？”则答案中含有多少信息量？如果你在已知今天是星期四的情况下提出同样的

5、问题，则答案中你能获得多少信息量（假设已知星期一至星期日的排序）解：（1）P=1/7I=-Log2P=Log27（2）已知今天星期四，问明天是星期几？即：明天是星期五是必然事件，不存在不确定性，I=0。2.4地区的女孩中有 25%是大学生，在女大学生中有 75%是身高 1.6 米以上的，而女孩中身高 1.6 米以上的占半数一半。假如我们得知“身高 1.6 米以上的某女孩是大学生”的消息，问获得多少信息量？解：设 A 为女大学生，B 为 1.6 米以上的女孩113则依题意有：P(A)=一,P(B),P(B|A)=-4241133P(AB)=P(A)LP(B|A)=-二一4416P(AB)3P(A

6、|B)二P(B)8所以信息量为log21=3-log232.5一副充分洗乱了的牌(含 52 张牌)，试问(1)任一特定排列所给出的信息量是多少？(2)若从中出去抽取 13 张牌，所给出的点数都不相同时得到多少信息量?解：(1)任一排列发生的概率为 1/52!I=log52!=225.58bit213 张牌点数都不相同发生的概率为 1/413I=10g413=26bitXLSiW3,其发出的消息为(P(x)_13/81/41/41/8011223210),求：(1)此消息的自信息是多少？(2)在此消息中平均每个符号携带的信息量是多少?解：(1)因为离散信源是无记忆的，所以起发出的消息序列中各符号

7、是无依赖且统计独立的。因此，此消息的自信息就为该消息中各符号自信息之和。I(a1=0)=-logP(a1)=-log=1.415 比特81一I(a2=1)=-logP(a2)=-log=2 比特4一，、1I(a3=2)=-logP(a3)=-log=2 比特4一，、1I(a4=3)=-logP(a4)=-log-=3 比特8则此消息的自信息是：I=14I(a1=0)+13I(a2=1)+12I(a3=2)+6I(a4=3)：141.415+132+122+63网 87.81 比特(2)此消息中平均每个符号携带的信息量是：I2=87.8145 定 1.95 比特/符号2.7 如有 6 行 8 列

8、的棋型方格，若又二个质点 A 和 B,分别以等概率落入任一方格内，他们的坐标分别为(XA,YA),(XB,YB),但 A.B 不能落入同一方格内。(1)如仅有质点 A,求 A 落入任一个格的平均自信息量是多少？(2)若已知 A 已落入，求 B 落入的平均自信息量。(3)若 A,B 是可分辨的，求 A,B 同都落入的平均自信息量。24解：(1)H(XA)=P(ai)logP(ai)=log24i1qq21.%2H(XB/XA)=PP(a。P(aj/a。logP(aj/a。i4j124=24 二P(a1)P(aj/a1)logP(aj/a1)=log23j=20qq22.%2H(XAXB)=二P(

9、aiaj)logP(aiaj)i=1j1q=-24、P(aiaj)logP(aaj)j=2=24*23*log(*)2.设离散无记忆信源20212013021300120321011032101002103224232423=log24*23=log23+log242.8 从大量统计资料知道，男性中红绿色盲的发病率为 7%,女性发病率为 0.5%,如果你问一位男同志：“你是否是红绿色盲？”他的回答可能是“是”，可能是“否”，问这二个答案中各含多少信息量？平均每个回答中含有多少信息量？如果你问一位女同志，则答案中含有的平均自信息量是多少？解：(1)若男同志回答“是：I=log(1/7%)=3.8

10、4bit回答“否：I=log(1/93%)=0.1bit平均信息量为：I=7%log7%93%log93%=0.36bit(1)若问女同志，平均信息量为：I=0.5%10g0.5%99.5%10g99.5%=0.045bit2.9 设信源1a1,a2,a3,a4,a5,a6求这信源的嫡，并解释为什么H(x)log6,不满足信源嫡的jP(x)_p.2,0.19,0.18,0.17,0.16,0.17_极值性。解：信源的嫡为:111H(x)=0.2log250.19log20.18log20.1710g20.190.180.171八一1+0.16log2+0.17log2=2.657bit/符号0

11、.160.176H(x)log6是因为此信息的P(a)1,不满足信息嫡极值性的条件。i12.10 设离散无记忆信源 S 其符号集 Aa1,a2,.,aq,知其相应的概率分布为(P1,P2,.,Pq)。设另一离散无记忆信源 S，其符号集为 S 信源符号集的两倍，A=aii=1,2,.,2q,并且各符号的概率分布满足：Pi=(1)Pi(i=1,2,.,q)Pi专Pi-q(i=q+1,q+2,.,2q)试写出信源 S信息嫡与信源 S 的信息嫡的关系。解：S：aa2aqP：P1P2PqH(X)=即-PiLogPi引i=1Pi=1S：a1a2aaq+1a2qP：p1p2pqpq+1p2qH(X)=-2f

12、qi=1PiLogPi=一/i=IPiLogPi+fQi=q+1PiLogPi=-刃i=1(1e)PiLog(1e)+LogPi+22qi=q+1Pi-q(Loge+LogPiq)=-(1e)Wi=1PiLog(1e)+(19Wi=1PiLogPi+e-=q+1PiqLogs+e2qi=q+1PiqLogPiq=-(1e)阳=1PiLogPi+2=q+1Pi-qLogPi-q+(1aLog(1a2?i=1Pi+loge2=q+1Pi-q=-(19-=1PiLogPi+ea=1PjLogPj+(17Log(19-=旧+Loge,R=-*=PiLogPi+(1 一aLog(1-9+Log。2fli

13、=旧=H(X)(1aLog(1e)+Loge2qi=1Pi=H(X)(1。Log(1s)eLogs即：H,(X)=H(X)(1。Log(10Log(1)为了使电视图象获得良好的清晰度和规定的适当的对比度，需要用 5*105个象素和 10 个不同的亮度电平，求传递此图象所需的信息率(比特/秒)。并设每秒要传送 30 帧图像，所有象素是独立变化，且所有亮度电平等概率出现。(2)设某彩电系统，除了满足对于黑白电视系统的上述要求外，还必须有 30 个不同的色彩度，试证明传输这彩色系统的信息率要比黑白系统的信息率约大 2.5 倍。解：(1)因为每帧图象可以看成是离散的数字图象，每个像素的亮度是随机而且等

14、概率出现的，则每个像素亮度信源的概率空间为： IX!=aia2.a10|P(ai)_10.1Q.1，.,0.1,每个像素亮度含有的信息量为： H(X)=log210 定 3.32比特/像素=1 哈特/像素现在，所有的像素是独立变化的，则每帧图象可以看成是离散亮度信源的无记忆 N 次扩展信源。故，每帧图象含有的信息量是：H(XN)=NH(X)=5 父 10510g10=5.105哈特/帧划 1.66x106比特/帧而每秒传送 30 帧图象，则传递这个图象所需要的信息率为RI=30MH(XN)=1.5X106哈特/秒=4.98M107比特/秒(2)证明：每个像素具有 10 个不同的亮度和 30 个

15、色彩度。由上面的计算得亮度等概率出现的情况下，每个像素含有的信息量是：H(X)=log210=3.32 比特/像素。每个像素的色彩度也是等概率出现的，则色彩度信源的概率空间为：每个像素色彩度含有的信息量：H(Y)=log230%4.91 比特/像素而亮度和色彩度是相互独立的，所以亮度和色彩度同时出现，每像素含有的信息量:H(XY)=H(X)+H(Y)=log10+log30=log300%8.23 比特/像素如果每帧所用的像素数和每秒传送的帧数都相同的情况下，传输这彩色系统的信息率与传输黑白系统的信息率之比就等于彩色系统每像素含有的信息量与黑白系统每像素含有的信息量之比：H(XY)10g300

16、H(X)-log10证毕。每帧电视图像可以认为是由 3X105个像素组成，所以像素均是独立变化，且每一像素又取 128 个不同的亮度电平，并设亮度电平等概率出现.问每帧图像含有多少信息量？现有一广播员在约 10000 个汉字的字汇中选 1000 个字来口述此电视图像，试问广播员描述图像所广播的信息量是多少(假设汉字字汇是等概率分布，并彼此无依赖)?若要恰当地描述图像，广播员在口述中至少需要多少汉字？解：.亮度电平等概率出现，每个像素所含的信息量为 H(X)=log128=7bit/像素.而每个像素均是独立变化的，每帧电视图像所包含的信息量为 H(X)=3X105H(X)=2.1x106bit假

17、设汉字字汇是等概率分布一、，一，1.每个汉字出现的概率均为10000从而每个汉字携带的信息量为 log10000=13.2877bit/字汉字间彼此无依赖，广播员口述的 1000 个汉字所广播的信息量为1000X13.2877=13287.7bit2.1106若要恰当地描述图像，广播员在口述中至少需要的汉字数为弋 15841 个汉字。13.28772.15 为了传输一个由字母 A、B、C、D 组成的符号集，把每个字母编码成两个二元码脉冲序列，以 00 代表 A,01 代表 B,10 代表 C,11 代表 D。每个二元脉冲宽度为 5ms。(1)不同字母等概率出现时，计算传输的平均信息速率？(2)

18、若每个字母出现的概率分别为 PA=1/5，PB=1/4，PC=1/4，PD=3/10,试计算传输的平均信息速率？解：(1)由题可知，当不同字母等概率出现时，平均自信息量为：H(x)=log4=2(比特/字母)又因为每个二元脉冲宽度为 5ms,故一个字母的脉冲宽度为 10ms则字母的传输速率为 100 字母/秒故传输的平均信息速率为：200 比特/秒(2)当每个字母分别以题中的概率出现时，平均自信息量为：10P(ai)=li1b,b2,.,bi0%：=1/30,1/30,.,时30、P(bj)=1j12.5H(x)=汇 P(ai)logP)=(1/5)*log5+2*(1/4)*log4+(3/

19、10)*log(10/3)=1.98(比特/字母)同样字母的传输速率为 100 个/秒故传输的平均信息速率为：198 比特/秒2.18 设有一个信源，它产生 0,1 序列的消息.它在任意时间而且不论以前发生过什么符号，均按 P(0)=0.4,P(1)=0.6 的概率发出符号.(1)试问这个信源是否平稳的？2(2)试计算 H(X),H(X3|XIX2)及pmHN(X).(3)试计算 H(X4)并写出 X4信源中可能有的所有符号.解：(1)因为信源发出符号的概率分布与时间平移无关，而且信源发出的序列之间也是彼此无依赖的.所以这个信源是平稳信源，是离散无记忆信源.X01-=，计算 H(X)=0.97

20、1bit/符号|P(x)_p.40.6_因为信源是平稳无记忆信源，所以 H(X2)=2H(X)-1.942bit/两个符号H(X3|XIX2)=H(X3)=H(X)=0.971 比特/符号11limHNX=)limH(X1X2IXN)=limNH(X)=H(X)-0.97bit/符号NNNNNNNH(X4)=4H(X)3.884bit/四个符号可能的所有 16 个符号：00000001001000110100010101100111100010011010101111001101111011112.19 有一个元无记忆信源，其发 0 的概率为 p,而 p 约等于 1,所以在发出的二元序列中经常

21、出现的是那些一串为 0 的序列(称为高概率序列)。对于这样的信源我们可以用另一新信源来代替，新信源中只包含这些高概率序列。这时新信源Sn=S1,S2,S3,Sn,Sn+1,共有 n+1 个符号，它与高概率的二元序列的对应关系如下：二元序列：001,01,0001,00000001,1,-,00-01(n 位),00000(n 位)新信源符号：S3,S2,S4,S8,S1,，Sn,Sn+1(1)求 H(Sn)(2)当nTg时求信源的嫡H(S)=limH(Sn)nj二二解：依题意，因为是二元无记忆信源，在发出的二元序列中符号之间彼此是无依赖的，统计独立的，所以有:NaiN=.Paikk1由此可得新

22、信源 Sn为:Sn1/6=1S2=01Sn=00-01Sn书=000、P(Si)J3。是利用马尔可夫信源的图示法画出状态转移图，并计算信源嫡 H解：由题可得，状态转移图为：E0a:1/3所以 H“=H2=Q(EI)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.8 所示，信源 X 的符号集为0,1,2并定义8=1p。(1)求信源平稳后的概率分布P(0),P(1剂P(2);(2)求此信源的嫡；(3)近似认为此信源为无记忆时，符号的概率分布等于平稳分布。求近似信源的嫡H(X)并与H0G

23、进行比较;(4)对一阶马尔可夫信源p取何值时H”取最大值，又当p=0和p=1时结果如何？解：(1)E=A=0,1,2,由图可得Q(Ei)=P(ai)i=1,2,3EiwE,aiwA而E=A=0,1,2pp/2p/2于是得到p/2pp/2【p/2p/26p(0)+Q(1)+Q(2)=1一1整理计算得Q(0)-Q(1)-Q(2)=3rr1即P(0)=P(1)=P(2)=3(2)据一阶马尔可夫信源的嫡的表达式可得3H-H2=1Q(Ei)H(X|Ei)i1=P(0)H(X|0)P(1)H(X|1)P(2)H(X|2)”(p衅),p-plogp-plog2-plogp-plogpp(3)信源近似为无记忆

24、信源，符号的概率分布等于平稳分布，则此信源3得到:H(X)=P(ai)10gP(ai)=log3期1.585比特/符号i1由此计算结果可知H(X),H-(4)求一阶马尔可夫信源H0c的最大值。因为Q(0)JQ(I)=PT-Q(2)j-Q(0)1Q(1):Q(2)Jpp/2p/2pp/2p/2、p/2PP(0)Q(i)Q(2)j二-plogp-PlogR-Bog卫222：JXJ0,1,2%/3,1/3,1/3_H二-(1-p)log(1-p)-plogpp求其对p的一阶导数H111d-=log(1p)logp1:pln2ln2=log(1-p)-logplog2,2(1-p)二logp令1=0,

25、得log2(1-p)=0,所以2(1-p)=1,所以p=Z时,H.达到最大值；H步的最大值等Fppp3log3定1.585比特/符号。当p=0时Hnplogpplog=0当p=1时H5=plogpplogE=1比特/符号由此可以看出上面H(X)之H七的结论时正确的。在。可得状态一步转移矩阵0P1P=口 P0?PP-Q(0)=Q(1)=Q(2)=1/3则可得 P(0)=P(1)=P(2)=1/3(2)一阶马尔可夫信源的嫡H“=H2=I=13Q(Ei)H(XIEi)=P(0)H(XIE)+P(1)H(XI1)+P(2)H(XI2)=1/3H(P1,0,P)+1/3H(P,P1,0)+1/3H(0,

26、P,P1)-Q(0)1-Q(0)【,Q(1)=PTQ(1)IJQ(2)_b(2).Q(0)Q(1)Q(2)=12.23 一阶马尔可夫信源的状态图如图 2.9 所示，信源 X 的符号集为0,1,2。(1)求平稳后信源的概率分布。(2)求信源的嫡 Hs。(3)求当 p=0 和 p=1 时信源的嫡，并说明其理由。=-P1logP1-PlogP=H(P)(3)当 P=0,H“=0当 p=1,H“=1因为信息嫡是表示信源的平均不确定性，题中当P=1 时，从 0 状态一定转移到 2 状态，2 状态一定转移到 1 状态，1 状态求出图中马尔可夫信源的状态极限概率并找出符号的极限概率计算信源处在某一状态下输出

27、符号的条件嫡 H(Sj)(j=1,2,3).求出马尔可夫信源嫡 Hs.此信源的状态集不等于符号集，从状态转移图可知P(a1|S1)=1/2,P(a1|S1)=0,P(a1|S3)=1P(a2|S1)=1/4,P(a21s2)=1/2,P(a21s3)=0P(a3|S1)=1/4,P(a31s2)=1/2,P(a31s3)=0状态转移概率为 P(S21s1)=P(a1|si)+P(a2|S1)=3/4P(S3|SI)=P(a3|S1)=1/4P(SI|SI)=0P(S1|S2)=0P(S2|S2)=P(a21s2)=1/2P(S3|S2)=P(a31s2)=1/2P(SI|S3)=P(a1|S3

28、)=1P(s21s3)=P(a21s3)=0P(S3|S4)=P(a31s3)=0从图可知此状态马尔可夫链是时齐的，状态数有限的和是不可约闭集，所以其具有各态历经性概率分布存在.得到如下方程组：kQ(S1)=Q(S3)Q(S2)=3/4Q(SI)+1/2Q(S2)QQ(S3)=1/4Q(SI)+1/2Q(S2)Q(SI)+Q(S2)+Q(s3)=1P=1 或 P=0 时表明信源从某一状态出发转移到另一状态的情况是定发生或一定不发生，即是确定的事件。当定转移到 0 状态。所以不论从何状态起信源输出的序列一定是021021 序列，完全确定的。当 P=0 时，0 状态永远处2.24于 0 状态，1

29、状态永远处于 1 状态，2 状态用于处于 2 状态。信源输出的符号序列也是确定的。所以当信源输出什么符号不存在不确定性，完全是确定的，因此确定信源的信息嫡等于零。P=1 或 P=0 时,设有一个马尔可夫信源，它的状态集为S1,S2,S3,符号集为a1,a2,a3,及在某状态下发符号的概率为下图所示.P(ak|s)(i,k=1,2,3),如(2)解：(1)得状态转移矩阵：P=-003/41/21/41/20，平稳后状态的极限解得：Q(si)=2/7,Q(s2)=2/7,Q(s3)=3/73符号的极限概率 P(ak)=?Q(si)P(ak|s)k=1,2,3i=1所以 P(ai)=Q(si)P(ai|&)+Q(s2)P(ai+Q(s3)P(ai|s3)=3/7,P(a2)=2/7,P(a3)=2/7(2)信源处于某一状态下的输出符号的条