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

1、.第二章信息量和熵2.2 八元编码系统，码长为 3，第一个符号用于同步，每秒 1000 个码字，求它的信息速率。解：同步信息均相同，不含信息，因此每个码字的信息量为2log 8 =23=6 bit因此，信息速率为61000=6000 bit/s2.3掷一对无偏骰子， 告诉你得到的总的点数为： (a) 7; (b) 12。问各得到多少信息量。解： (1) 可能的组合为1 ， 6,2 ， 5,3 ，4,4 ，3,5 ，2,6 ， 161p(a) = =636得到的信息量1= log 6 =2.585 bit= logp( a)(2) 可能的唯一，为 6 ，6p(b) = 1361= log 36

2、=5.17 bit得到的信息量 = logp(b)2.4经过充分洗牌后的一副扑克（52 张），问：(a) 任何一种特定的排列所给出的信息量是多少？(b) 若从中抽取 13 张牌，所给出的点数都不相同时得到多少信息量？1解： (a)p(a) =1信息量 = log= log 52! =225.58 bitp( a)13!13种点数任意排列(b)413花色任选p(b) = 13! 413= 413A5213C5213信息量 = log C5213log 413 =13.208 bit.2.9随机掷 3 颗骰子， X 表示第一颗骰子的结果，Y 表示第一和第二颗骰子的点数之和，Z 表示3 颗骰子的点数

3、之和，试求H (Z | Y ) 、 H ( X | Y ) 、H ( Z | X ,Y) 、 H ( X , Z | Y ) 、 H ( Z | X ) 。解：令第一第二第三颗骰子的结果分别为x1 , x2 , x3 ， x1 ， x2 ， x3 相互独立，则 Xx1 ， Yx1x2 ， Zx1x2x3H ( Z | Y) = H (x3 ) = log 6=2.585 bitH ( Z | X ) = H ( x2 x3 ) = H (Y)=2 ( 1log 36+ 2 log 18+ 3 log 12+ 4 log 9+ 5log 36 )+ 6 log 63636363636536=3.

4、2744 bitH ( X | Y) = H ( X ) - I (X ; Y) = H ( X ) - H (Y) - H (Y | X ) 而 H (Y | X ) = H ( X ) ，所以 H ( X |Y ) = 2 H ( X ) - H (Y ) =1.8955 bit或 H ( X | Y) = H ( XY ) - H (Y ) = H ( X ) + H (Y | X ) - H (Y)而 H (Y | X ) = H ( X ) ，所以 H ( X | Y ) =2 H ( X ) - H (Y) =1.8955 bitH (Z | X ,Y) = H ( Z | Y)

5、= H ( X ) =2.585 bitH ( X , Z |Y) = H ( X |Y ) + H ( Z | XY ) =1.8955+2.585=4.4805 bit2.10设一个系统传送 10 个数字， 0，1， ，9。奇数在传送过程中以 0.5 的概率错成另外一个奇数， 其余正确接收， 求收到一个数字平均得到的信息量。解：XYi1,3,5,7,9信道i0,2,4,6,8I ( X ;Y ) = H (Y) - H (Y | X )因为输入等概，由信道条件可知，.p( yi i为奇数 )110p( yi i为偶数 )1( 11111)1102888810即输出等概，则 H (Y ) =

6、 log 10H (Y | X ) =p( xi y j) log p( y j| xi)ij=p( xiy j ) log p( y j| xi ) -p(xi y j ) log p( y j | xi )ji偶j i 奇=0-p(xiy j ) log p( y j| xi )ji 奇= -p(xi ) p( yi | xi) log p( yi | xi ) -p( xi ) p( y j | xi ) log p( y j | xi )i 1,3,5 ,7，9ij i1，3，5，7，91111145=log 25+2log 81021041 3= =1 bit44I ( X ; Y)

7、 = H (Y) - H (Y | X ) = log 10 -1=log 5=2.3219 bit2.11 令 u1, u 2 ,， u8 为一等概消息集，各消息相应被编成下述二元码字u1=0000， u2 =0011， u3 =0101， u4 =0110，u5 =1001， u6 =1010， u7 =1100， u8 =1111通过转移概率为p 的 BSC 传送。求：(a)接收到的第一个数字0 与 u1之间的互信息量。(b)接收到的前二个数字00 与 u1 之间的互信息量。(c)接收到的前三个数字000 与 u1之间的互信息量。(d)接收到的前四个数字0000 与 u1之间的互信息量。

8、解：.即 I (u1 ;0) ， I (u1 ;00) ， I (u1 ;000) ， I (u1 ;0000)p(0) = 1 (1 p)4 + 1 p 4 = 1882p(0 | u1 )= log1p=1+ log(1p) bitI (u1;0) = log1p(0)2p(00) =1 2(1p) 24(1p) p2 p2 =184I (u1;00) =log p( 00 | u1 ) = log (1p) 2= 21log(1 p) bitp(00)1/ 4p(000) = 1 (1p) 33(1p) 2 p3(1p) p2p3 = 188I (u1;000) =31+ log(1p)

9、 bitp(0000 ) = 1(1p)46(1p) 2 p 2p 4 8I (u1;0000) = log8(1p) 4bit(1 p)46(1p)2p2p42.12计算习题 2.9 中 I (Y; Z ) 、 I ( X ; Z ) 、 I (X , Y; Z ) 、 I (Y; Z | X ) 、 I ( X ; Z |Y ) 。解：根据题2.9 分析H (Z ) =2(1log 216+ 3 log 216 + 6 log 216 + 10 log 216 +216216321662161015216+212162521627216loglog+log+log)216152162121

10、62521627=3.5993 bitI (Y; Z ) = H ( Z) - H (Z | Y) = H (Z ) - H ( X ) =1.0143 bitI ( X ; Z ) = H ( Z ) - H ( Z | X ) = H ( Z ) - H (Y) =0.3249 bitI ( X ,Y; Z ) = H (Z ) - H (Z | XY ) = H ( Z ) - H ( X ) =1.0143 bit.I (Y; Z | X ) = H ( Z | X ) - H (Z | XY ) = H (Y) - H ( X ) =0.6894 bitI ( X ; Z |Y )

11、= H ( Z |Y) - H (Z | XY ) = H ( X ) - H ( X ) =0 bit2.14对于任意概率事件集X,Y,Z，证明下述关系式成立(a) H (Y, Z | X )H (Y | X ) + H (Z | X ) ，给出等号成立的条件(b) H (Y, Z | X ) = H (Y | X ) + H (Z | X , Y)(c) H ( Z | X ,Y)H ( Z | X )证明： (b)H (Y, Z | X ) =-p(xyz) log p( yz | x)xyz=-p(xyz) log p( y | x) p( z | xy)xyz=-p( xyz) lo

12、g p( y | x) -p( xyz) log p( z | xy)xyzxyz= H (Y | X ) + H ( Z | XY )(c)H (Z | X ,Y) =-p(xyz) log p( z | xy)xyz=p( xy) -p(z | xy) log p( z | xy) xyzp( xy) -p( z | x) log p( z | x) xyz=-p( xyz) log p(z | x)xyz= H ( Z | X )当 p(z | xy) = p( z | x) ，即 X 给定条件下， Y 与 Z 相互独立时等号成立(a) 上式 (c)左右两边加上 H (Y | X ) ，

13、可得H (Y | X ) + H (Z | X ,Y )H (Y | X ) + H ( Z | X )于是 H (Y, Z | X )H (Y | X ) + H (Z | X )1,12.28 令概率空间 X1, 1，令 Y 是连续随机变量。已知条件概率密度为22.14, 2y x 2p( y | x)，求：0, 其他(a)Y 的概率密度( y)(b) I ( X ; Y)(c) 若对 Y 做如下硬判决1,y1V0,1y 11,y1求 I ( X ;V ) ，并对结果进行解释。解： (a)由已知，可得13y 1p( y | x1) =40else11y3p( y | x1) =40else

14、( y) = p(x1)p( y | x1) + p( x1) p( y | x1)13y1811y1=411y380else(b)11211H C (Y) =log 84log 4 =2.5 bit831H C (Y | X ) =p(x1)1p( y | x1) log p( y | x1) dy3p( x1)31) log p( y | x1)dyp( y | x1=111log1131123 4dy1 4log dy =2 bit424I ( X ; Y) = H C (Y ) - H C (Y | X ) =0.5 bit.(c) 由 ( y) 可得到 V 的分布律V-101p1/4

15、1/21/4再由 p( y | x) 可知V-101p(V|x=-1)1/21/20p(V| x=1)01/21/21log 21bitH (V )2 log 4 1.524H (V | X )1 1 log 21 log 22=1 bit222I ( X ;V ) = H (V )H (V | X ) = 0.5 bit2.29令 Q1 (x) 和 Q 2 ( x) 是同一事件集U 上的两个概率分布，相应的熵分别为H (U )1 和 H (U ) 2 。(a)对于 01，证明 Q ( x) =Q1 (x) +(1) Q2 (x) 是概率分布(b) H (U ) 是相应于分布 Q( x) 的熵

16、，试证明 H (U )H (U ) 1 + (1) H (U )2证明： (a) 由于 Q1 ( x) 和 Q2 ( x) 是同一事件集 U 上的两个概率分布，于是q1 ( x)0， q2 ( x)0q1 ( x)dx =1，q2 ( x)dx =1xx又 01，则q(x) =q1 ( x) + (1) q2 ( x)0q( x)dx =q1 ( x)dx+(1)q2 (x)dx =1xxx因此， Q( x) 是概率分布。(b)H (U ) = q1 ( x)(1)q2 (x) log q1 ( x)(1) q2 ( x)dxx=q1 ( x) log q1 (x)(1) q2 ( x)dxx

17、.(1) q2 (x) log q1 ( x)(1)q2 ( x)dxxq1 (x) log q1 ( x)dx(1) q2 ( x) log q2 ( x)dx（引理 2）xx=H (U )1 + (1) H (U ) 2.第三章 信源编码 离散信源无失真编码3.1 试证明长为 N 的 D 元等长码至多有 D (D N1)个码字。D1证：在 D 元码树上，第一点节点有 D 个，第二级有 D 2 ，每个节点对应一ND i = D (1DN) = D ( DN1) ，此个码字，若最长码有N ，则函数有1i 11DD时，所有码字对应码树中的所有节点。码长为 1 的 D 个；码长为 2 的 D 2

18、个， ，码长为 N 的 D N 个ND i = D ( DN1) 个总共i 1D13.2 设有一离散无记忆信源 Ua1 ,a2。若对其输出的长为 100的事件序0.004,0.996列中含有两个或者少于两个a1 的序列提供不同的码字。(a) 在等长编码下，求二元码的最短码长。(b) 求错误概率（误组率）。解 : (a)不含 a1 的序列 1 个长为 100 的序列中含有1 个 a1 的序列 C1001=100 个长为 100 的序列中含有2 个 a1 的序列 C1002=4950 个所需提供码的总数 M=1+100+4950=5051于是采用二元等长编码Nlog M=12.3，故取 N =13

19、log D(b)当长度为 100 的序列中含有两个或更多的a1 时出现错误，因此错误概率为Pe =1 C1000(0.996)100 - C1001 (0.004)(0.996)99C1002 (0.004) 2 (0.996)98= 7.77510 3.a1, a23.3设有一离散无记忆信源，U= 1 , 3，其熵为 H (U ) 。考察其长为 L 的输出4 4序列，当 LL0 时满足下式PrI (u L )H (U )L(a)在=0.05， =0.1下求 L0(b)在=103， =8 下求L010(c)令 T 是序列 u L 的集合，其中I (uL )H (U )L试求 L= L0 时情况

20、 (a)(b)下， T 中元素个数的上下限。解： H (U ) =pk log pk = 1 log 43 log 4 =0.81 bit443E I (ak ) = H (U )I 2 = E I (ak )H (U ) 2 = E I ( ak )2 - H 2 (U )=pk (log pk )2H 2 (U )k=0.471则根据契比雪夫大数定理I (u L )2PrH (U )IL2L20.471(a) L =I=18842(0.05)20.12(b) L2 = 8 0.471 3 2 =4.71 101310(10 )(c) 由条件可知 uL 为典型序列，若设元素个数为 M T ，

21、则根据定理I(1) 2L ( H (U )M T2 L( H (U ) )其中，可知.(i)0.1 ，0.05， L1884下边界： (1)2 L (H (U ) )0.9 21431.84上边界： 2 L( H (U ) ) = 21620. 24故 0.9 21431.84M T21620. 24(ii)10 6 ，10 3 ， L4.71 1011(1)2 L( H ( U )0.999923. 81 10112L ( H (U ) = 23.82 1011故0.999923. 81 1011M T23.82 10113.4 对于有 4 字母的离散无记忆信源有两个码A 和码 B，参看题表

22、。字母概率码 A码 Ba0.4111a0.301102a30.2001100a40.100011000(a) 各码是否满足异字头条件？是否为唯一可译码？(b) 当收到 1 时得到多少关于字母 a1 的信息？(c) 当收到 1 时得到多少关于信源的平均信息？解：码 A 是异头字码，而B 为逗点码，都是唯一可译码。码 AI (a1;1)log 2p(a1 |1)log 211.32bitp( a1 )0.4码 BI (a1;1)log 2p(a1 |1) p(1)log 2p(a1 ,1)log0.40bitp(a1 ) p(1)p(a1 ) p(1)0.4 1码 A U= a1 ,a2 , a3

23、 , a4 4I (u;1)p(ak |1) I (ak ;1) = p(a1|1) I (a1 ;1)0=1.32 bitk 1.4码 BI (u;1)p( ak | 1) I (ak ;1) =0 bitk 1（收到 1 后，只知道它是码字开头，不能得到关于U 的信息。）3.5 令离散无记忆信源Ua1a2a3a4a5a6a7a8a9a100.160.140.130.120.100.900.080.070.060.05(a) 求最佳二元码 ,计算平均码长和编码效率。(b) 求最佳三元码 ,计算平均码长和编码效率。解： (a)0.58010.4210.3100.2710.2300.191000

24、a10.160.1501010a20.140011a30.1301100a40.120.111110a50.100111a60.0910010a70.0800011a80.0711010a90.0601011a100.051H (U )pk log pk =3.234 bit平均码长npk nk =3.26= R n log Dk效率H (U )H (U )99.2%Rn log D.(b)0.4300.3310.24200a10.16001a 20.14102a 30.13210a 40.1200.11 112a 50.10220a 60.09021a 70.08122a 80.072110

25、a 90.060111a100.051平均码长npk nk =2.11kRn log D =3.344效率H (U )96.6%Ra1. a2.a3.3.6 令离散无记忆信源U0.5.0.3.0.2(a) 求对 U 的最佳二元码、平均码长和编码效率。2(b) 求对 U 的最佳二元码、平均码长和编码效率。3(c) 求对 U 的最佳二元码、平均码长和编码效率。解： (a)0.5011a10.5100a20.3001a30.21n =0.5 1+0.3 2+20.2=1.5H (U )p k log pk1.485 bit.1.H (U )99%R(b)离散无记忆H(U 1 U 2 )=2H(U)=

26、2.97 bitp(a1 a1 )=0.25, p(a1 a2 )=0.15, p(a1 a 3 )=0.1, p(a 2 a1 )=0.15, p(a 2 a 2 )=0.09p(a 2 a 3 )=0.06, p(a3 a1 )=0.1, p(a3 a 2 )=0.06, p(a3 a 3 )=0.040.55010.4510.300.25110a1a10.2500.210.150001a1a20.151010a2 a10.1500.11110a1a30.10111a3a10.110000 a2 a20.0900001a2 a30.0610110 a3a20.0600111a3a30.04

27、1n2pk nk3n2n1.52H (U 1U 2 ) = 2.97 =0.99n2 log D3(c) 有关 U 3 最佳二元类似 略3.7令离散无记忆信源a1. a2. a kUp(a1 ) p(a 2 ) p( ai ).i1且 0P(aP(a) P(a)1Q =02kik 1下述方法进行二元编码。消息 a k 的码字为实数 Q k 的二元数字表示序列的截短（例如 1/2 的二元数字表示序列为 1/210000 ，1/40100 ） ,保留的截短序列长度 n k 是大于或等于 I(a k )的最小整数。a1. a2.a3. a4.a5.a6 .a 7.a8 .(a) 对信源 U1 111

28、1111构造码。4,4,8, 8,16 ,16 ,16,16(b) 证明上述编码法得到的码满足异字头条件，且平均码长n 满足H(U) n H(U)+1。解： (a)符号QiLCa8040000a714000116a61400108a534001116a41401004a3330118a242108a132114(b) 反证法证明异字头条件令 kk，若 ak 是 ak 的字头，则 QkQ k2 nk又由 I (ak )nkI (ak ) 1可知，2 nkpk2 nk 1从而得 QkQk2 nkpk这与假设 ak 是 ak 的字头（即 QkQkpk ）相矛盾，故满足异字头条件。由已知可得.log1

29、nklog 11pkpk对不等号两边取概率平均可得pk log1pk nkpk log 11kpkkkpk即H (U )nH (U )1a1. a23.8 扩展源 DMC ， U0.6,0.4(a)求对 U 的最佳二元码、平均码长和编码效率。2(b)求对 U的最佳二元码、平均码长和编码效率。3(c)求对 U 的最佳二元码、平均码长和编码效率。4(d)求对 U的最佳二元码、平均码长和编码效率。解： (a) C10 ， C 2 =1， n =1H (U )0.97 bitH (U )R97%(b) DMC 信道0.600.41100a1a10.360101a1a20.24010a2 a10.241

30、11a2 a20.16n2 2 ， n1 ，H (U )97%n(c).0.50410.496010.288001a1a1a10.21610.20400.1920.1610111a1a1a 20.1441000a1a2 a10.1440001a 2a1a10.1441100a1a2 a20.0960101a 2 a1a 20.09611100a 2 a2 a10.09601101a 2a 2 a 20.0641n3 =2.944n =0.981=98.85%(d) 略3.9设离散无记忆信源Ua1 ,.a2 ,.a3 ,.a4 ,.a5 ,.a6 试求其二元和三元0.3,.0.2,.0.15,.

31、0.15,.0.1,.0.1Huffman 编码。解：.0.40.610.3001a 10.310.211a 20.2000a 30.150001a 40.151100a 50.10101a60.1101a 10.3110.2200a 20.2001a 30.15102a 40.15220a 50.1021a 60.113.11 设信源有 K 个等概的字母 ,其中 K=2 j ,12。今用 Huffman 编码法进行二元编码。（a）是否存在有长度不为j 或 j+1 的码字，为什么？（b）利用和 j 表示长为 j+1 的码字数目。（c）码的平均长度是多少？解： Huffman 思想：将概率小的用长码，大的用短码，保证n ，当等概时，趋于等长码。a)对1时， K=2 j ，则用长度为j 码表示；当2 时，用 K=2 j+1，用长度为 j+1 码表示。平均码长最短，则当12 时，则介于两者之间，即只存在 j ，j+1 长的码字。b) 设长为 j 的码字个数为 Nj ，长度为 j+1 的码字数目为 Nj+1，根据二元 Huffman 编码思想（必定占满整个码树） ，即.N jN j 1K2 jN j2 jN j 12 ( j 1)1从而 N j(2) 2 j ， N j 1(1) 2 j 1c）1j1( j 1) = j 22LN jN j 1K