信息论与编码理论习题答案

1、信息论与编码理论习题答案第二章信息量和爛2.2八元编码系统，码长为3,第一个符号用于同步，每秒1000个码字，求它的 信息速率。解：同步信息均相同，不含信息，因此每个码字的信息量为 2xlog8二2x3二6 bit因此,信息速率为 6x1000=6000 bit/s2。3 掷一对无偏骰子，告诉你得到的总的点数为：(a) 7；(b) 12问各得解：(1)可能的组合为到多少信息量。1,6 , 2, 5 , 3,4 , 4, 3, 5,2, 6, 1 得到的信息量二log一二log6二2. 585 bitPW(2)可能的唯一，为6, 6得到的信息量二log一二log36二5。17 bit2.4经过充

2、分洗牌后的一副扑克(52张)，问：(a) 任何一种特定的排列所给出的信息量是多少？(b) 若从中抽取13张牌，所给出的点数都不相同时得到多少信息量？解：(a) p(a) =52!信息量二log一二log52!二225。58 bit“、13!13种点数任意排列(b)413花色任选“(b)二131x4"4136 / 31信息量二logC；_log4= 3。208 bit信息论与编码理论习题签案2。9 随机掷3颗骰子，X表示第一颗骰子的结果，Y表示第一和第二颗骰子的 点数之和，Z表示3颗骰子的点数之和，试求H(Z | Y) . H(X | Y).H(Z|X,Y)、H(X,Z|Y)、H(Z|

3、X).解：令第一第二第三颗骰子的结果分别为,x2,x3, X, x2, x3相互独立，则X = xlt Y = xY + x2 f Z = xx-.+xH(Z | /) = /f(x3) = log6=2. 585 bitH(ZX) = H(x2 + x5) = HY)二 2x (log 36+log18+ log 12+A log 9+ log ) + A log 636363636 &36 & 536=3. 2744 bitH(X | 丫)二H(X)-/(X;Y)二H(X) X)而 H(YX) = H(X)f 所以 H (X |K)= 2H(X)-H(Y)=1O 8955

4、bit或 H(XY) = H(XY)-H(Y)=H(X) + H(YX)-H(<Y)而 H(YX) = H(X),所以H(X Y)=2H(X) H(Y)=K 8955 bitH(Z | X,Y) = H(Z | Y) = H(X)=2O 585 bitH(X,Z | Y)H(X | Y) + H(Z XY). 8955+2o 585二4。4805 bit2o 10 设一个系统传送10个数字，0, 1,-, 9o奇数在传送过程中以0. 5的槪 率错成另外一个奇数，其余正确接收，求收到一个数字平均得到的信息量。解:X 信道 135仏9 ；02468I(X;Y) = H(Y)-H(YX)因为输

5、入等概，由信道条件可知,信息论与编码理论习题签案P（y = ii为奇数）=右110爪訓为偶数）時G444+护即输出等概，则/（r）=iogioH（Y|X）二-工工/心儿）log（儿|兀） j二-工工P（X儿）logp（y,I兀）一工工pg儿）logp（儿I兀） j ，偶j f奇。工工/心兀）l°gp（” |兀）j f奇 工p（X）p®比）iogp（xl兀）工 工（兀）（儿丨兀）bg（儿|兀）匸1,3,5,7.9i*j f=1.3.5.7.9log 8x4x54二一x log 2x5+ x x10 2 10 2Z（X;X） = /（/）-H（Y I X） = log 10 -

6、1 = log5=2. 3219 bit2o 11令坷,，业为一等概消息集，各消息相应被编成下述二元码字©二0000, “2二0011, m3=0101, m4=0110,“5=1001, w6=1010, “7二1100, w8=1111通过转移概率为q的BSC传送。求：（a）接收到的第一个数字0与匚之间的互信息量。（b）接收到的前二个数字00与心之间的互信息量。（c）接收到的前三个数字000与匚之间的互信息量。（d）接收到的前四个数字0000与©之间的互信息量。解：信息论与编码理论习题答案1-p即/(H；0), /("JOO), /(«000), /

7、(mOOOO)P(o)二扣-P)x4 + “x4二 +oo2曲)週喘2叫亍二叫(i) bit2p(00) = A2(1-p)2 + 4(1 _ p)p + 2p訂二 184心;00)二log£291®.二log (1/?r 二21 + 10g(l- p) bit 1p(00)1/4p(000) = |(l-p)3 + 3(1-p)2 p + 3(l-p)p2+p3 = |ooI(“i;000)=3 1 + log(l-p) bitp(0000) = |(1 - p)4 +6(1-p)2p2 + p4o/(gOOOO)二log 律；"、-bit(1-py+ 6(i-

8、pyp+p42o 12 计算习题 2。9 中 /(Y;Z). /(X;Z). /(X,Y;Z 八 /(Y;Z|X)、/(X;Z|Y)。解：根据题2. 9分析、1 (3 |2166 f 21610 |216H(Z)二2(log216 +log + log + log +216216321662161015(21621(21625 |21627 f216、log+log+log+log) 21615216212162521627=3.5993 bit/(Y;Z)二H(Z) H(Z| Y)二H(Z) H(X)二仁 0143 bit /(X;Z)二 H(Z) H(Z | X) = H(Z)- H(F)

9、二0. 3249 b i t /(X9Y;Z) = H(Z)H(ZIXY) = H(Z) H(X)=1.O143 bit# / 31信息论与编码理论习题签案Z(y；Z I X)-H(Z I X)-H(z I XY) = H(Y)H(X)=0o 6894 bit/(X;Z I Y)-H(Z I Y) H(Z I XX)二H(X) H(X)二0 bit2。14 对于任意槪率事件集X,Y,乙证明下述关系式成立(a) H(Y,ZX) <H(YX) + H(ZX),给出等号成立的条件(b) H(Y,Z | X) = H(Y | X) + H(Z X,Y)(c) H(Z|X,y)<H(Z|X)

10、证明：(b) H(Y,Z| X)二一工工工”Ow)log#(z|x)x y z二一工工工P(RZ)logp(y | x)pz | xy>)x y z=SSZ(w)logI %)y -工工p(w)log pd I劝X 二= H(YX) + H(ZXY)(c) /匕以,丫)二一工工工/心2)log p(z | x)')y -二工工”5) X Pd I Q)log P(z | 6 X 二<工工卩(与)-p(z|x)logp(z|x)X yz=-工工！>5z)log pd I x)x y z二 H(Z|X)当| xy)- p(.z | X),即X给定条件下，Y与z相互独立时等

11、号成立(a) 上式(c)左右两边加上H(Y|X),可得H(Y | X) + H(Z X,Y) < H(丫 | X) + H(Z | X)于是H(Y,ZX) <HYX) + H(ZX)8 / 31信息论与编码理论习题答案11 / 311厂12. 28令概率空间X= 1 1，令Y是连续随机变量.已知条件概率密度为 .25 2.-2< y-x<2 Lp(y x) = ，求：0,其他(a) Y的概率密度做y)(b)(b) 若对Y做如下硬判决lyiV = Jo,-l<y <1一 1,y<-l求i(xy),并对结果进行解释.解：(a)由已知，可得.-3 <

12、y < 1 else.-l<y <3else1 /?(y|x =-1)=4 0.j. p(y|x = l)二”0.如二"(x = -1) p(y |x = -l) + p(x = 1) p(yx = i)11 - 8 11穴4 1-80-3 < y <-l-1 < y < 1Ij；log8x2 + lfilog4=20 5 bitc(.Yx)= - P(x = j) "(y 丨 x = - l)log p(y I x = -l)dy-(x = 1) DO I * = l)log p(y | x = l)dyTl拯扑-扛拯存=2 bi

13、tI(X;Y) = HC(Y) HC(Y | X)=0. 5 bit(c)由Q(y)可得到V的分布律1/101p1/41/21/4再由p(y 1x)可知V101p 0J | A=-1 )1/21/20p <v i a=o01/21/2/(V) = |log2 + ix21og4 = 1.5 bitH(VX) = -丄 Iog2 +丄 Iog2x2 二 1 bit2 2I(X;V) = H(V)-H(VX)= 0.5 bit2. 29 令0(x)和(x)是同一事件集U上的两个概率分布，相应的爛分别为HU 和 HU)?。(a) 对于0 几 1,证明Q(x) = A ft(x) + (1-2)

14、 Q2(x)是概率分布(b) H(U)是相应于分布 Q(x)的爛,试证明H(U)A H(t/) + (l_2) H(U)2证明：(a)由于Q(x)和Q2(x)是同一事件集U上的两个概率分布，于是<7i W >0, q2(x)>0又O<A<1,则q(x)=A (x) + (l-2) q2(x) >0J q(x)dx 二 J 勺(x>/x+ J (1 - A)q2 (.v>/a=1因此，2(x)是概率分布。 /(/) = -J切(x) + (1 -A)q2(x)Iog础(a) + (1 - Z)q2(x)"xX二-可 4 (x)10g (x

15、) + (1-Z)q2 (x)t/.rX一 (1 一 刃 j (x) logMs (X) + (1-刃肚X> -A j (x) log q、(x)dx -(1- 2)j q2 (x) log q2 (x)dx(引理 2)XX=2 H(U + (1-A) H(U)2信息论与编码理论习题签案第三章 信源编码离散信源无失真编码3.1试证明长为N的D元等长码至多有D(D" _个码字.证：在£)元码树上，第一点节点有£)个，第二级有I)?,每个节点对应一个码字，若最长码有N,则函数有二二D(D' _1),此时 台 1-DD-1所有码字对应码树中的所有节点。码长

16、为1的D个；码长为2的£>'个码长为N的£>"个D(D " _1)D-13o 2设有一离散无记忆信源 L若对其输出的长为100的事件 0.004, 0.996序列中含有两个或者少于两个的序列提供不同的码字。(a) 在等长编码下，求二元码的最短码长。(b) 求错误概率(误组率)。解：(a)不含勺的序列1个长为ioo的序列中含有1个的序列cnoo个长为100的序列中含有2个的序列C二二4950个所需提供码的总数M二1 +100+4950二5051于是采用二元等长编码- =12.3,故取N二13 logD(b) 当长度为100的序列中含有两

17、个或更多的时出现错误，因此错误概率为Pc = l -0 (0.996 )100- C!oo(0.004)(0.996)" - CQ(0.004)2 (0.996)9S二 7775xE12 / 31信息论与编码理论习题答案3.3 设有一离散无记忆信源，U= 1 3 ，其爛为H(U)考察其长为厶的输出序 <4'4 >列，当L>Lq时满足下式(a) 在5=0.05, £二01下求厶(b) 在 5二 1(T, £二10一'下求厶(c) 令T是序列叫的集合，其中16 / 31试求L二厶时情况(a) (b)下，T中元素个数的上下限。134解：

18、/(/) = - X loS Pk = - log 4 + - log - =0 o 81 bitEg)二 H(U)a,2 = EI(ak)-HiU)2 = EI(ak)2-HU)二工久(log/人)k二0. 471则根据契比雪夫大数定理(a)0.1x(0.05)2'6La2(b)71x1013(c) 由条件可知兀为典型序列，若设元素个数为，则根据定理其中&, h = 6可知（i） b'=,8 = 01, £ = b = 005,厶= 1884下边界:（1-<t,）2£（/（£/>-'，）=0.9x2143184上边界：

19、2厶(0/)+名)一 21620 24故 0.9x21431 84 <Mt < 21620-24（i i） <Jf =：£ = 10一6, £ = ”10= L = 4.71xlOH（1-= 0.9999x 2381x1oIJ2乙（円（）十名'）-23-82x1°h故0.9999x2381x1011 <Mt <23S2x1°u3.4 对于有4字母的离散无记忆信源有两个码A和码B,参看题表。字母概率码A码Bai0.411a20.30110830.2001100a40. 100011000(a) 各码是否满足异字头条件？

20、是否为唯一可译码？ 当收到1时得到多少关于字母的信息？(c) 当收到1时得到多少关于信源的平均信息？解：码A是异头字码，而B为逗点码，都是唯一可译码。码 A /（勺;1） = log," U = log, = 1.32 bitP）04码B码AU二 aa2,aa4 /（“;1）=工（色|1）/;1）二（ |1）/（6；1） + 0二1 32 bit=1码 B Z(m;1)=工 p(ak l)I(ak ;1) =0 bitJt=l(收到1后，只知道它是码字开头，不能得到关于U的信息。)3o 5令离散无记忆信源=< "1a3a4a5a6 a7a3a9"100.16

21、0.140.130.120.100.900.080.070.060.05» <(a) 求最佳二元码，计算平均码长和编码效率。(b) 求最佳三元码，计算平均码长和编码效率。解：(a)0000.16010a2 0.14ona3 0.13100aA 0.12noa5 0.10ina6 0.0900100.080011«s 0.071010cig 0.061011a10 0.050.270.2310010.420.310H(U)= 一工几 log几二3。234 bit 平均码长 亓=工几你二3. 26二/?=帀logDk效率 z;=w)= wl=992%R n log D信息

22、论与编码理论习题答案00010210122021221101110.430亓=工几吐二2。11(b)平均码长R = h logD=3o 344效率=竽=96.6%3.6令离散无记忆信源U = ai “°2>0.5.0.3.0.2(a) 求对U的最佳二元码、平均码长和编码效率。(b) 求对U的最佳二元码、平均码长和编码效率。(c) 求对的最佳二元码、平均码长和编码效率。 解：(a)18 / 31片二0。5X1+0. 3 X 2+2X0. 2=1.5H(U)= 2>Jog以=1485 bit信息论与编码理论习题答案22 / 31 = 99%R(b)离散无记忆 AH (U U

23、J=2H(U) =2o 97 bit1 p (a a )二 0 o 25, p (a a、)二0. 15, p (a a ) 0 o 19 p (a、a )二 0。15, p (a»a丿二0。091113.1p (a a3 ) =0. 06, p(a3ai ) =0. 1, p (a3a,)04二0. 06, p0.55 0100.250.250,204500010.150100.151100 1 .V 1111A 1 .V 10000a2a20.090001dg0.0601100.0601110.04亓2二=3n =- 1.520.15Q1W) 2.97 c oo = 二二0。99

24、n2 log D 3(b) 有关最佳二元类似略3o 7令离散无记忆信源ia)p(ajpa)j且 0 WP(a/WP (a?)W 。WP (a.) <1o 定义 Q_.二/>1,而Jl=lQfO,今按下述方法进行二元编码。消息a：的码字为实数Q；的二元数字表 示序列的裁短(例如1/2的二元数字表示序列为1/2->10000-,1/4T0100)，保留的裁短序列长度是大于或等于I (a&)的最小整数.对信源U =构造码。64勺.6“6.a7.a3% %, % % %6, %6, %6,(b) 证明上述编码法得到的码满足异字头条件，且平均码长亓满足H (U) W 亓 WH

25、(U)+1o解：(a)符号Q,LC04000011640001%1840010316400111440100383011a248210%34211(b)反证法证明异字头条件令k <r ,若畋是代，的字头，则Qk -Qk <2'nt又由 I(ak)<nk <I(ak) +1 可知，2" < pk < 2+1从而得 er-a<2 <Pk这与假设心是s的字头(即Q严Q严pQ相矛盾，故满足异字头条件。 由已知可得log < nk < log +1PkPk对不等号两边取概率平均可得工 Pk log X PZ < X 以

26、log 丄 +1k Pk kk Pk即 H(U)<n<H(U) + l3。8扩展源DMC,(060.4丿(a)求对U的最佳二元码、平均码长和编码效率。(b)求对I?的最佳二元码、平均码长和编码效率。(c) 求对的最佳二元码、平均码长和编码效率.(d) 求对u4的最佳二元码、平均码长和编码效率。解：(a)C1=0, C2=1,/(/) = 0.97 bit(b)“瞥 97%DMC信道00660.36010.24100.2411ag0.160,4010.6 0| | 11兀=2, n = l, 77 = 2 = 97%(c)信息论与编码理论习题答案信息论与编码理论习題答案0111100

27、0001100101a2ata21100a2a2a1101a卫心0.50434 / 31爲二2.944 亓二0.981二98. 85%(c) 略3。9设离散无记忆信源碍,冬试求其二元和三元0.3,.0.2,.0.15,.0.15,.0.1,.0.1Huffman 编码。解：pJ10.40.3 0oi a 0.3-!->1 0.211 a 02ooo a z o.i5001 a 01 10.1100 a. o.i101100010220210.3az0.2a0.153a0.154a0.1 Ja0.1110.220120103o 11设信源有K个等概的字母，其中K=6Z-2y,1 <a

28、 <2.今用Huffman编码法 进行二元编码。(a) 是否存在有长度不为j或j+1的码字，为什么？(b) 利用a和j表示长为j+1的码字数目。(c) 码的平均长度是多少？解：Huffman思想：将概率小的用长码，大的用短码，保证n X,当等概时， 趋于等长码。a) 对q = 1时，K二2，则用长度为j码表示；当a = 2时，用K二2二 用长度 为j+1码表示。平均码长最短，则当时，则介于两者之间，即 只存在j, j+1长的码字。b) 设长为j的码字个数为N“长度为j+1的码字数目为Nj+1,根据二元 Huffman编码思想(必定占满整个码树)，即Nj+Nju = K = ax2j x2

29、y+.+1x2_u+1) =1从而 y=(2 a)x2仃 A?+1 =(cr-l)x2y+1_119c) L = /V. j + N 屮(j + l)二 j + 2 K 3K田7a133.12设二元信源的字母概率为p=上,p（l） = - o若信源输出序列为 441011 0111 1011 0111（a）对其进行算术编码并进行计算编码效率。（b）对其进行LZ编码并计算编码效率.（3肯1）Pls)=解：（a）Jf（治+1） = F仙）+p仙）尸（如）根据递推公式 -可得如下表格"（"+】） =卩仙）+P（如）其中，F (1)二0, F (1)= %, p(0)% p (1)

30、二w.血）吨）0101341403 13X =4 416141339X = 一 16 46419327X =64 4256033 V134413547136 F137 承0374101384111394120394131414131141531241615081251351416= 0.0101100111100100 -从而C = 01W)=Rlog 4 + - log 4-=99.85% %(b)首先对信源序列进行分段：01111 0 11 01 111 011然后对其进行编码，编码字典如下所示段号短语1J编码1101000120000000311110011401210101511131

31、0111601141100170111611101一17R = f l log D =r =&7x4 416134/（/）= _log4 +-log-= 0.8113b i t443=空 = 46.36%R3.13 设DMS为U二e 6.S 1,各a .相应编成码字0.10.110和1110。试证明对足够长的信源输出序列，相应的码序列中0和1出现的概率相等. 解：概率信源符号码字1/201/4Cl2101/81101/81110设信源序列长为N,则相应码字长为（条件是N要足够长） N , N c N “L = xl + x2 x3 = N2 484相应码序列中0出现的次数Ln = xl

32、+xl + xl = N°2488p (0) = = -p (1) =1p(0)=-L 223o 14 设有一 DMS, U二0.9 0.1采用如下表的串长编码法进行编码信源输出序列0串长度(或中间数字)输出二元码字1000000110001001200107011181(a)求 H (U)o(b) 求对于每个中间数字相应的信源数字的平均长度;f。1(c) 求每个中间数字对应的平均长度万一。(d) 说明码的唯一可译性.解：(a) H(U) = -0.9log0.9-0.1 log0.1 = 0.469 bit 由已知可得下表先验 概率信源输出 序列0串长度 (或中间数字)输出二元码字

33、0o 11000000. 0901100010.0o110.1000.1010o 0531601100. 0478701110. 4381(b) 丘=lx0l + 2x0.9 +8x0.4305 =5.6953 bit(c) % =1x0.4305 + 4x(1 0.4305) = 2.7085 bit(d) 异字码头第四章信道及信道容童4.1计算由下述转移概率矩阵给定的DMC的容量。1一1一卩达到C需要输入等概, 它是一对称信道,-C = log 3 +p(jk)logp(yk)=log3 + (1 -p)log(l-p) + pogp = log3-H(p) bit/符号£ &#

34、163;2222pP口l_p_I711_.它是一对称信道 C = log 4 + 乎 log- x 2 + # log # x 2=2 + (1-p)log-_ + plog = l-H(p) bit/符号21-pP0(c)pl-P0001它是分信道' "P 和1的和信道P 1-卩Cv = log2 + (1 - p)log(l- p) = I-H(p)C2 = 0由 2c=2c*+2,可知C = logl+21_W(P> bit/符号4o 3求图中DMC的容量及最佳输入分布01334013343 £4 41 13 30丄4 发送符号1时等概率收到0,1,2,

35、传对与传错概率完全相同，即不携带任何信息量，于是信道简化为二元 纯删除信道丄413£4C = l q = l 1/4 = 3/4 bit/符号(b)由图知1-3 1-3 1-3 O 1-31-3 1-31-3 O1 - 3 o 1 一 3 为准对称当输入等槪，即e0=a=g2=l时达到信道容量c此时 Qo = © = d=#x£x2 = £rr3=i(川0)C = /(x = 0V) = 5>C/|0)log11£二丄 log £ + 丄 log £ + 丄 log 孑=Z log 2b i t / 符号3辽3Z3丄3

36、29934.5 N个相同的BSC级联如图。各信道的转移概率矩阵 P 1-/7 .令2 = px/ = o,r = o,i,.,/v,且0为 y-p p已知。(a)求0的表达式。(b) 证明Ns 时有© 1/2,且与0。取值无关，从而证明Wts时的级联信道容量C” t0(“>0) 解：N个信道级联后BSC可表示为N个级联可以看成N1个级联后与第N个级联信息论与编码理论习题签案 Pn = (1 - “T) 卩 + p、T (1 - 卩)=PT (1 - 2 卩)+ 同理可得Pnt = Pn4Q-2p)+p(1一2卩)+p2 = pl-(l-2p)+pPi = P从而Pn = PwQ

37、-2p)+P=Pn-2 (1 _ 2p) + p (1 - 2p) + p=Pn-2 (1 -2pf + p-(l-2p)+p=Pg (1 - 2)' + p (1 -2)2 + p (l-2p)+pN7= L(l 2p)AT + p工(1 2”/=0N-l =吃(1-2"/=0l_(l_2p)“ l-(l-2pf=p =1-(1-2p)2(a)Qn = Oo (1 - P v ) +(1 - Oo)P . v=Qo + Q-2Qo)Pn= Q + (1-2Q)1-(：2P)、(b)i_(i _2p)a，剋Q厂鹽 Q +(l-2Q)y1-2Q2信息论与编码理论习题签案因此与0

38、。无关。由于Qn = PXN = 0=px° = 0 (1 Pv ) + px0 = 1 PN = | 与 pxq = 0 = 2o 无关，因此 Pn =扌，c二o。4o 8 一 PCM语音通信系统，已知信号带宽W二4000 Hz,采样频率为2W,且采用 8级幅度量化,各级岀现的概率为1/2, 1/4, 1/8, 1/16, 1/32, 1/32,1/32, 1/32.试求所需的信息速率。解: H(U) = 一工以 log仇弓Iog2 + #log4 + *log8 + £logl6+存41og32 = bit9信息速率R = y；/(V) = 8000x- = 18000 bit/s4.9在数字电视编码中，若每帧为500行，每行划分成600个像素，每个像素采 用8电平量化，且每秒传送30帧时，试求所需的信息速率。解：每个像素信息量为/ = log8 = 3 bit每秒传输30帧，即30x500x600 = 9x10"个像素A/? = 9x106x3 = 2.7x107 bit/s4o 10带宽为3 kHZ,信噪比为30 dB的电话系统，若传送时间为3分钟，试估计 可能传送