信息论与编码习题解答

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,贝U在可能

4、出现的36种可能中,只能个骰子都为1,这一种结果.即：P (A) =1/36 I (A) = log2 P (A) = log 2 35.17 比注设“面朝上点数之和为8为事件B,那么有五种可能：2、6;& 2; 44;3、5;5、3;即：P (B) = 5/36 I (B) = log2P (B) = log 2 36/#2.85 此设“骰子面朝上之和是 3和4为事件C,那么有两种可能：& 4; 4、3;即：P (C) = 2/36 I (C) = log2P (C) = log 2 36倍4.17 比注2.3如果你在不知道今天是星期几的情况下问你的朋友“明天是星期几 那么答

5、案中含有多少信息量如果你在今天是星期四的情况下提出同样的问题,那么答案中你能获得多少信息量(假设星期一至星期日的排序)解：(1) P= 1/7 I = 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)-4241 33P(AB) P(A)gP

6、(B | A) 一一一4 4 16P(AB) 3P(A|B)-P(B) 8所以信息量为log 3 log 2 32.5 一副充分洗乱了的牌(含52张牌),试问(1) 任一特定排列所给出的信息量是多少(2) 假设从中出去抽取13张牌,所给出的点数都不相同时得到多少信息量?解：(1)任一排列发生的概率为1/52!I = log52! = 225.58 bit(2) 13张牌点数都不相同发生的概率为1/413I = log413 = 26 bit2.设离散无记忆信源Xa= 0a?=1a3=2a4=3=,其发出的消息为(202120210213001203210110321010021032P(x)

7、3/8 1/4 1/4 1/8011223210),求：(1) 此消息的自信息是多少(2) 在此消息中平均每个符号携带的信息量是多少?解：(1)由于离散信源是无记忆的,所以起发出的消息序列中各符号是无依赖且统计独立的.因此,此消息的自信息就 为该消息中各符号自信息之和.比特I ( a10) = - log P ( a1)= - log = 1.415I ( a 21 ) = - log P ( a?) = - log =2 比料F4I ( a32) = - log P ( a3) = - log 】=2 比特4I ( a43) = - log P ( a4) = - log =3 比特8那么此

8、消息的自信息是:I=14I ( a1 0 ) + 13I ( a2 1) +12 I ( a32 ) + 6I ( a4 3)14 1.415+13 2+12 2+6 3 87.81比特(2)此消息中平均每个符号携带的信息量是：I 2 =87.81 45 1.95 比特/符号2.7如有6行8列的棋型方格,假设又二个质点 A和B,分别以等概率落入任一方格内,他们的坐标分别为(XA,YA ) ,(XB,YB),但A.B不能落入同一方格内.(1) 如仅有质点A,求A落入任一个格的平均自信息量是多少(2) 假设A已落入,求B落入的平均自信息量.(3) 假设A,B是可分辨的,求 A,B同都落入的平均自信

9、息量.24解：(1) H(XA)= P(ai)log P(ai) =log24 i 1(2) H(XB/XA)= P(ai)P(aj /ai)log P(aj /ai)i 1 j 1 24=24P(a1 )P(aj / a1 )log P(aj / a1) log 23j 20(3) H(XAXB)= P(aiaj)log P(aiaj)i 1 j 1q=24P(a1aj)logP(a1aj)=24*23* * log( * )24 2324 23=log24*23=log23+log242.8从大量统计资料知道,男性中红绿色盲的发病率为7%,女性发病率为 0.5%,如果你问一位男同志：“你是

10、否是红绿色盲 他的答复可能是“是,可能是“否,问这二个答案中各含多少信息量平均每个答复中含有多少信息量如果 你问一位女同志,那么答案中含有的平均自信息量是多少解：(1)(2)假设男同志答复“是 ：I= log(1/7%) = 3.84 bit答复“否：I= log(1/93%) = 0.1 bit平均信息量为：I = 7%log7% 93%log93% = 0.36 bit、 X2.9设信源P(x)极值性.务,0.2,假设问女同志,平均信息量为：I = 0.5%log0.5% 99.5%log99.5% = 0.045 bita2,a3,a4,a5,96求这信源的痼,并解释为什么H (x) l

11、og6 ,不满足信源痼的0.19, 0.18, 0.17, 0.16, 0.17解：信源的痼为:H(x) 0.2log25-1-110.19log 2 0.18log 2 0.17log 2 -0.190.180.170.16log 20.16110.17log 2 2.657 bit/符号0.17H(x) log6是由于此信息的P(aJ 1,不满足信息痼极值性的条件.i 12.10设离散无记忆信源 S其符号集Aa1,a2,.,aq,知其相应的概率分布为(P1,P2,.,Pq).设另一离散无记忆信源S',其符号集为S信源符号集的两倍,A =aii=1,2,.,2q,并且各符号的概率分布

12、满足：Pi ' =(1)Pi(i=1,2,.,q)Pi '专 Pi-q (i=q+1,q+2,.,2q)试写出信源S'信息痼与信源S的信息痼的关系.解：S ：a 32 aqP： p1 p2 pqH (X)=一刃=1PiLogPi羽=1Pi = 1S':a1 a2aq aq+1a2qP : p 1 p 2p qp q+1 p2qH (X)=我1P iLogP i=一2fi=1P iLogP i+22qi= q+1P iLogP i= i=1 (1 - £) PiLog (1 + LogPi+ 22qi = q+1 Pi q (Log 汁 LogPi q)

13、 =(1 -刃=PiLog (1 &) + ( 1 8 寸i=PiLogPi+ £ 势=q+Pi-qLog £+ £ 务=q+侣-qLogPi-q=(1 -刃=1PiLogPi + £势=q+ 1Pi qLogPi q+ (1 一对 Log (1一对 羽= 1Pi+ £og £ 牢q + 1Pi q=(1 -寸i=1PiLogPi + £S>1PjLogPj+ (1 一对 Log (1 8 刈S+ Log £ 罗=1Pj=浏=1PiLogPi+( 1一对 Log (1 8 + Log 4 刃=1Pi=

14、H (X) (1 对 Log (1 s) + Log &岑=1Pi=H (X) (1 e) Log (1 e) eLog &即：H,(X) = H (X) (1 £) Log (1一对一£og £2.13 (1)为了使电视图象获得良好的清楚度和规定的适当的比照度,需要用5*10 5个象素和10个不同的亮度电平,求传递此图象所需的信息率(比特/秒).并设每秒要传送30帧图像,所有象素是独立变化,且所有亮度电平等概率出现.(2) 设某彩电系统,除了满足对于黑白电视系统的上述要求外,还必须有30个不同的色彩度,试证实传输这彩色系统的信息率要比黑白系统的信

15、息率约大2.5倍.解：(1)由于每帧图象可以看成是离散的数字图象,每个像素的亮度是随机而且等概率出现的,那么每个像素亮度信源的概率空间为:心2,.用0P(ai)0.1,0.1,.,0.110P(ai)=1i 1每个像素亮度含有的信息量为：H(X)=log 210 3.32比特/像素=1哈特/像素现在,所有的像素是独立变化的,那么每帧图象可以看成是离散亮度信源的无记忆N次扩展信源.故,每帧图象含有的信息量是：H(X N)=NH(X)=5 105log10=5 105 哈特 /帧 1.66 106 比特 /帧而每秒传送30帧图象,那么传递这个图象所需要的信息率为Ri=30 H(X n)=1. 5

16、106 哈特 /秒 4.98 107 比特 /秒(2)证实：每个像素具有 10个不同的亮度和30个色彩度.由上面的计算得亮度等概率出现的情况下,每个像素含有的信息量是：H(X)=log 210 3.32比特/像素.每个像素的色彩度也是等概率出现的,那么色彩度信源的概率空间为：30P(bj)=1 j 1X _ 打屈.,.P(bj) 一 1/30,1/30,.,1/30每个像素色彩度含有的信息量：H(Y)=log 230 4.91 比特/像素而亮度和色彩度是相互独立的,所以亮度和色彩度同时出现,每像素含有的信息量：H(XY)=H(X)+H(Y)=log10+log30=log3008.23 比特

17、/像素如果每帧所用的像素数和每秒传送的帧数都相同的情况下,传输这彩色系统的信息率与传输黑白系统的信息率之比 就等于彩色系统每像素含有的信息量与黑白系统每像素含有的信息量之比：H (XY) = log 300 25H(X) 一 log 10.证毕.2.14每帧电视图像可以认为是由3 X 105个像素组成,所以像素均是独立变化,且每一像素又取128个不同的亮度电平,并设亮度电平等概率出现.问每帧图像含有多少信息量 现有一播送员在约 10000个汉字的字汇中选 1000个字来口述此电视图 像,试问播送员描述图像所播送的信息量是多少(假设汉字字汇是等概率分布,并彼此无依赖)?假设要恰当地描述图像,播送

18、员在口述中至少需要多少汉字解：.亮度电平等概率出现.每个像素所含的信息量为H(X)=log 128=7 bit/像素.而每个像素均是独立变化的 每帧电视图像所包含的信息量为H(X)= 3 X 105H(X)= 2.1 X 106bit假设汉字字汇是等概率分布 一、一,1每个汉字出现的概率均为 10000从而每个汉字携带的信息量为log 10000=13.2877 bit/字.汉字间彼此无依赖,播送员口述的1000个汉字所播送的信息量为1000 X 13.2877=13287.7 bit假设要恰当地描述图像,播送员在口述中至少需要的汉字数为2土兰 -15841个汉字.13.28772.15为了传

19、输一个由字母 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) 当每个字母分别以题中的概率出现

20、时,平均自信息量为：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)试计算 H(X2),H(X3|X1X2)及 Nim Hn(X).试计算H(X4)并写出X4信源中可能有的所有符号解：(1)源,是离散无记忆信源.X(2)P(x) 0.4由于信源发出符号的概率

21、分布与时间平移无关,而且信源发出的序列之间也是彼此无依赖的.所以这个信源是平稳信1,计算 H(X) R 0.971 bit/符号0.6由于信源是平稳无记忆信源,所以H(X2)=2H(X) - 1.942 bit/两个符号H(X 3|X1X2)=H(X 3)=H(X) r 0.971 比特/符号1,lim Hn(X)= lim H(X1X2L XN) N NN N(3) H(X 4)=4H(X) q 3.884 bit/ 四个符号 可能的所有 16个符号:0000 0001 00101110 1111= Nim00111、.一 NH (X)= H(X) x 0.97 bit/符号 N0100 0

22、101 0110 0111 1000 1001 1010 1011 1100 11010的序列2.19有一个元无记忆信源,其发 0的概率为p,而p约等于1,所以在发出的二元序列中经常出现的是那些一串为(称为高概率序列).对于这样的信源我们可以用另一新信源来代替,新信源中只包含这些高概率序列.这时新信源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) 当n时求信源的痼H(

23、S) lim H(Sn)解：依题意,由于是二元无记忆信源,在发出的二元序列中符号之间彼此是无依赖的,统计独立的,所以有:NaiNPk 1P ai1, ai2aiki1,i 21,2由此可得新信源Sn为:SnPSiSi1 S2 01PPSn0001PnSn 1001P Pn证实满足完备性:n 1P(§)Pi 1PPnP(1P2Pn1)PnnPL_p_1 PPn 1H(S) nim由于0 PI 1P($)log P(§)1I Pn1H(P) H(P)1 P1 P. . . .一11,所以 lim Pn 0,贝U： H(S) H(P)H(Sn)nPii 11 _ i 1 _Plo

24、g(P P)nnP log P1 PnttH(P)H(Sn) nimH(P)lim PnX1为c, X2为a、b的概率为1/2,为c的概率为0,而且后面发出 法3.是利用马尔可夫信源的图示法画出状态转移图,并计算信源痼2.21有一信源,它在开始时以P(a)=0.6,P(b)=0.3,P(c)=0.1的概率发出 XI.如果X1为a时,贝U X2为a、b、c的概率为1/3;如果X1为b, X2为a、b、c的概率为1/3;如果Xi 的概率只与 Xi-1 有关,又 P(Xi|Xi-1)=P(X2|X1) iH8.解：由题可得,状态转移图为:E0可见,状态E1和E4、E7、E10的功能是完全相同的,状态

25、E2和E5、E8、E11的功能是完全相同的,状态E3和E6、E12的功能是完全相同的.A;由于此马尔可夫信源Ei、E2、E3 的其中Eo是过渡状态,而Ei、E2、E3组成一个不可约闭集,具有遍历性.故有如下的状态转移图 的状态必然会进入这个不可约闭集,所以计算信源痼时,可以不考虑过渡状态和过渡过程.由此,可得状态 极限概率：产 Q(Ei)=1/3Q(Ei)+1/3Q(E 2)+1/2Q(E 3)Q(E2)=1/3Q(Ei)+1/3Q(E 2)+1/2Q(E 3)Q(E3)=1/3Q(Ei)+1/3Q(E 2) Q(Ei)+Q(E2)+Q(E3)=1可得：Q(Ei)=Q(E2)=3/8 , Q(

26、E3)=1/4a:1/3所以 H8=H2=Q(Ei)H(1/3,1/3,1/3)+Q(E 2)H(1/3,1/3,1/3)+Q(E 3)H(1/2,1/2)=1.4388(比特/符号)2.22 一阶马尔可夫信源的状态图如图2.8所示,信源X的符号集为0,1,2并定义P 1 po 求信源平稳后的概率分布P(0), P(1刑P(2);H (X )并与H进行比较;(2)求此信源的痼；(3) 近似认为此信源为无记忆时,符号的概率分布等于平稳分布.求近似信源的痼(4) 对一阶马尔可夫信源 p取何值时H取最大值,又当 p 0和p 1时结果如何?解：(1) E A 0,1,2,由图可得 Q(eJ P(q)

27、i 1,2,3Ei E,ai A而 E A 0,1,2p p/2 于是得到 p/2 pp/2 p/2Q(0)Q(0)Q(1) pt Q(1)Q(2)Q(2)Q(0) Q(1) Q(2) 1p/2p/2pp p/2 p/2 q(0)p/2 p p/2 Q(1)p/2 p/2 p Q(2)-一、,1整理计算得Q(0) Q(1) Q(2) 351即 P(0) P(1) P(2) 3(2)据一阶马尔可夫信源的痼的表达式可得3H H2Q(Ei)H(X|Ei)P(0)H (X |0)1p-H(p,卫32IH京壹)3P(1)H(X |1) 1P(2)H (X |2)H(挡,.piog ppp p plog

28、log 2222, pplog p plog _2plog p plog p p(3)信源近似为无记忆信源,符号的概率分布等于平稳分布,那么此信源X0,1,2P(a)1/3,1/3,1/33得到： H (X)P(ai)log P(ai) log 3 1.585 比特/"i 1由此计算结果可知H(X) h(4)求一阶马尔可夫信源H的最大值.由于H (1 p)log(l p) plog p p求其对p的一阶导数iog(i p)plog(1 p) log"2(1 p)logp1.log p in 2p log 2上1 in 2令门.,得log 0,所以言1,所以p log 3 1

29、.585比特/符号.当 P0时HPlogp P咔 0当p 1时Hplog p plog p 1比特/符号由此可以看出上面H (X) H的结论时正确的.2- 一w时,H到达最大值;3H的最大值等2.23 一阶马尔可夫信源的状态图如图2.9所示,信源X的符号集为0,1,2.(1) 求平稳后信源的概率分布.(2) 求信源的痼H“°(3) 求当p=0和p=1时信源的痼,并说明其理由.Ei E,ai A,而 E= A阶马尔可夫信源状态的极从状态图中分析可知,这三个状态都是正规常返态,所以此马尔可夫链具有各态历经性,平稳后状态的极限分布存在.可得状态一步转移矩阵P0PPPP00PPQ(0)Q(0

30、)QPT QQ(2)Q(2)Q(0) Q(1) Q(2) 1Q(0) = Q(1) = Q(2) = 1/3那么可得P(0) = P(1)= P=1/3(2) 一阶马尔可夫信源的痼H8 = H2=H i=13Q(Ei)H(X I Ei)=P(0)H(X I E)+P(1)H(X I 1)+P(2)H(X I 2)=1/3H(P1,0,P)+1/3H(P,P1,0)+1/3H(0,P,P1)=-P1 log P1-P log P=H(P)(3)当 P= 0 ,H8= 0当 p= 1 ,Hy 1由于信息痼是表示信源的平均不确定性,题中当 P=1或P=0时说明信源从某一状态出发转移到另一状态的情况是

31、一定发生或一定不发生,即是确定的事件.当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),如卜图所示.a2：?a1：1a3：?(1

32、) 求出图中马尔可夫信源的状态极限概率并找出符号的极限概率(2) 计算信源处在某一状态下输出符号的条件痼H(Sj)(j=1,2,3).(3) 求出马尔可夫信源嫡fH 8.解：(1)此信源的状态集不等于符号集,从状态转移图可知P(a1|s1)=1/2, P(a1|s1)=0,P(a|s3)=1P(a2|s1)=1/4, P(a2|s2)=1/2, P(a2|s3)=0P(a3|S1)=1/4, P(a3|s2)=1/2, P(a3|s3)=0状态转移概率为 P(s2|s1)= P(a1 |s)+ P(a2|s)=3/4P(s3|si)= P(a3|s1)=1/4P(s1|s1)=0P(s1|s2

33、)= 0P(s2|s2)= P(a2|s2)=1/2P(s3|s2)= P(a3|s2)=1/2P(s1 |s3)= P(a1|s3)=1P(s2|s3)= P(a2|s3)=0P(s3|s4)= P(a3|s3)=0得状态转移矩阵：P=3/41/41/21/2从图可知此状态马尔可夫链是时齐的,状态数有限的和是不可约闭集,所以其具有各态历经性,平稳后状态的极限概率分布存在.得到如下方程组： Q(s1)= Q(s 3)Q(s2)=3/4 Q(s 1)+1/2 Q(s 2),Q(s3)=1/4 Q(s 1)+1/2 Q(s 2)Q(s1)+ Q(s 2)+ Q(s 3)=1解得：Q(s i)=2/7, Q(s 2)=2/7, Q(s 3)=3/7 3符号的极限概率P(ak)= ? Q(si)P(ak|si)k=1,2,3i=1所以 P(ai)=Q(si)P(ai |si)+ Q(s2)P(ai |s2)+ Q(s3)P(ai|s3)=3/7,P(a2)=2/7, P(a3