信息论与编码计算题

1、1.已知信源发出al和a2两种消息，且两种消息出现的概率相等。信宿接收到两种消息分 别为bl和b2。此消息在二元对称信道上传输，其错误概率为p(即发送al接收b2,或发送 a2接收bl的概率)，求互信息量I(a1;b1), I(a1;b2)。解：由于是二元对称信道上传输，其输入等概时，输出必等概，即p(b ) = p(b ) = 0.5(a ; b ) = I (b ) -1 (b I a ) = log PC I %)= log 2(1 - p) = 1 + log(1 - p )bit1111 1p(b )1I (a ; b ) = I (b ) -1 (b I a ) = log p (

2、七 I %)= log 2 p = (1 + log p)bit2221p(b2)2.中国国家标准局所规定的二级汉字共6763个。设前两千个汉字的使用频度相等，总 的出现概率为0.6,后4763个汉字的使用频度相等，总的出现概率为0.4。求平均每个汉字 所含的信息量。设每个汉字用一个16*16的二元点阵显示，试计算显示方阵所能表示的最大 信息。显示方阵的利用率是多少？ 解：根据题意，求平均每个汉字所含的信息量，即求信源熵H (X) 根据信源熵的定义：H(X) = -Z p)堕 p(xi)i0.6 , 0.60.40.4=-2000 xlog () - 4763 xlog ()200022000

3、47632 4763=12.4374bit / sym bol对于二元16*16的显示方阵Y，共有2256种显示状态，每种状态等概率出现达到方阵所能 表示的最大信息，则H (Y) =256bit/方阵显示方阵的利用率或显示效率为：门=兰 = 12.4374/256 = 0.0486 = 4.86%H (2)3 .已知二维随机变量XY的联合概率分布(土七)为：p(0,0)=p(1,1)=1/8，p(1,0)=p(0,1)=3/8o 求 H (X|Y)解：根据题意，已知联合概率分布，则：p(y ) = p(xy ) = 1/8 + 3/8 = 0.51i 1p( y 2) = p(xy 2) =

4、1/8 + 3/8 = 0.54 随机变量X, Y的联合概率分布如表所示，求联合熵H(XY)和条件熵H(YIX)。解：01p(x.)1Y、01/41/41/211/201/2p( y.)3/41/41,、，1、1 1、1 1、1、3, 一H (XY)=-(方 log 云 + 4 log 云 + 2 log-2) = 2 bit / symbol由X, Y的联合概率分布可以求得X的边缘概率分布(如上表)和条件概率分布以气)H(X | Y) = -ZZ p(xy)log p(x | y )i j= -ZZ p(xiyj)log2i jp( xy )p( y,)p(x y 儿,p(x y )+ p(

5、x y )log 2 p(y0)0 12 p(y1) _p(x y 儿,p(x y )一 _ + p(x y )log 1 02 p(y )1 12 p(y )L01 J=0.125log 0.25 + 0.375log 0.75 + 0.375log 0.75 + 0.125log 0.252222=0.6556所 sym bol=-p(x0 y0)log-+ p心)log(如下表)文一-_y0101/21/2110H(Y I X) = -ZZ p(七七)logp(yj I 七)i j= -1/4log1/2 - 1/4log1/2 - 1/2log1=1/25.一信源有 6 种输出状态，概

6、率分别为:p(A)=0.5, p(B)=0.25, p(C)=0.125, p(D)=p(E)=0.05, p(F)=0.025，试计算H( X),求消息序列ABABBA的信息量，并与长度为6的消息序列熵相 比较。解：根据信息熵的定义，该信源输出的信息熵为：H (X) = Z p (x )log p (x )iii=P (A)log P (A) P (B)log P (B) p (C )log p (C)P( Q)log P (D) p (E )log P( E) p (F )log p( F)=0.5log2 + 0.25 log4 + 0.125log8 + 2 x 0.05 log 20

7、 + 0.025 log 40=1.94bit / sym bol消息ABABBA所含的信息量为：I (ABABBA) = 3/(A) = 3/(B) = 3log2 + 3log4 = 9bit6位长消息序列熵为：H(X6) = 6H(X) = 11.64bit显然6位长的消息序列熵比消息序列ABABBA所含的信息量大。6.一给定X, Y的联合概率分布如下表所示，试求：0101/31/3101/3H(X),H(Y)H(XIY),H(YIX)H(XY)I(X;Y)解：根据联合概率分布，可求得边缘概率分布为:p(X=0)=p(XY=00)+p(XY=01)=1/3+1/3=2/3p(X=1)=

8、p(XY=10)+p(XY=11)=0+1/3=1/3p(Y=0)=p(XY=00)+p(XY=10)=1/3+0=1/3p(Y=1)=p(XY=01)+p(XY=11)=1/3+1/3=2/3H(X)=-2/3log2/3-1/3log1/3=0.918bit/symbolH(Y)=-1/3log1/3-2/3log2/3=0.918bit/symbolH(X|Y)=1/3H(X|Y=0)+2/3H(X|Y=1)=0.667bitH(Y|X)=H(X|Y)=0.667bitH(XY)=-3*1/3log1/3=1.585bit/symbolI(X;Y)=H(X)-H(X|Y)=0.918-0

9、.667=0.251bit/symbol7.设有一离散无记忆信源X,其概率空间为:XP( X)x112X314，求该信源的熵率及其二次扩展信源的熵。解：单符号离散信源熵:H(X) = Z p(尤)logp(x )=上log2 + 上log4 + 上log4 = 1.5bit / symbol i i 244i二次扩展信源：H(X2) = 2H(X) = 2x 1.5 = 3bit/2symbols1.设一个二元一阶马尔可夫信源，信源符号集为X=0, 1,信源输出符号的条件 概率为：p(0l0)=0.25, p(0l1)=0.5, p(1l0)=0.75, p(1l1)=0.5写出状态转移矩阵；

10、画出状态图；求各状态稳态分布；求各符号稳态分布；求信源的熵率。解：根据题意，共有两种状态与之对应，s0 = 0,s1 = 1,由信源输出符号的条件概率可 得信源的状态转移矩阵为：0.25 0.75一_ 0.50.5 _画出其状态转移图如下：设状态的平稳分布为w =叫叮,由于该马尔可失链是齐次遍历的,有：WP=W,即：-0.25 0.75, w -12 0.50.50.25w + 0.5w = w 0.75w + 0.5w = ww + w = 1V 12解得:w = 0.4w = 0.6p(0) = p(0| s )p(s ) + p(0| s )p(s ) = 0.25 x 0.4 + 0.

11、5 x 0.6 = 0.4 0011p(1) = p(1| s )p(s ) + p(1| s )p(s ) = 0.75 x 0.4 + 0.5 x 0.6 = 0.6 0011H = H = H(X I X ) = -ZZp(s )p(s Is )logp(s Is )21i j ij ii j=0.4 x 0.25log0.25 - 0.4 x 0.75log0.75 - 0.6 x 0.5log0.5 - 0.6 x 0.5log0.5如设有一个二元二阶马尔可夫信源，其信源符号集为X=0, 1,输出符号的条件概率为：p(0I00)=p(1I11)=0.8p(1I00)=p(0I11)=

12、0.2p(0I01)=p(0I10)=p(1I01)=p(1I10)=0.5写出状态转移矩阵；画出状态图；求各状态稳态分布；求各符号稳态分布；求信源熵。解：根据题意，可能的状态有：s1=00, s2=01, s3=10, s4=11。但由于信源只可能发出0或者1， 所以信源下一时刻只可能转移到其中的两种状态之一。故信源的状态转移矩阵为： TOC o 1-5 h z 0.80.200000.50.5P =0.50.500000.20.8状态转移图略 设状态的平稳分布为：W = (*,W2,%,wj，根据马尔可夫遍历的充要条件WP=W，有:0.8w + 0.5w = w0.2 w + 0.5w =

13、 w1320.5w + 0.2w = w2430.5w + 0.8w = w且满足w + w + w + w = 1w = 5/14w = 1/72w = 1/73w4 =5/14p(0) = 0.8p(s ) + 0.5p(s ) + 0.5p(s ) + 0.2p(s ) = 0.5 1234p(1) = 1 - 0.5 = 0.5H = H = H = p(s)H(X I s.) = 0.80bit/symbol3一个三元一阶马尔可夫信源的基本符号为0、1、2,这3个符号等概率出现，并且具有相同的转移概率。写出状态转移矩阵；画出状态图；求各符号稳态分布；求各状态稳态分布；求信源极限熵。解

14、：根据题意，可能的状态有：s1=0, s2=1, s3=2。由于信源等概率发出0、1、2三信符号， 故信源的状态转移矩阵为：-1 1 3 3 3P =111 3 3 3 1 1 1 _ _ _L 3 3 3状态转移图略 设状态的平稳分布为：W = (% % w3)，根据马尔可夫遍历的充要条件WP=W，有: TOC o 1-5 h z 111w + w + w = w3132331且满足* + 2 + ”3 = 1111w + w + w = w 3132332111w + w + w = w31323331 解之得 w1 = w2 = w3 = 3符号稳态分布：p(0) = p(0 Is )

15、p (s ) + p(0 Is ) p( s ) + p(0 Is ) p( s )= TOC o 1-5 h z 1122333p(1) = p(11 s )p(s ) + p(11 s )p(s ) + p(11 s )p(s ) = 3p(2) = p(21 s )p(s ) + p(21 s )p(s ) + p(21 s )p(s )=-1122333H = H =-ZZ p(s. Is,)p(s )logp(s )信源的极限熵为：1 /=9 x x log 3 = log 3bit / symbol4 .-有一马尔可夫信源，已知状态转移概率：p(s1Is1)=2/3 p(s2Is1

16、)=1/3 p(s1Is2)=1p(s2Is2)=0。写出状态转移矩阵;画出状态图；求各状态稳态分布;求信源极限熵。解：根据题意，状态转移矩阵为：2 113 31 0状态转移图(略)设状态的平稳分布为W = (*,七)，由于该马尔可失链是齐次遍历的，有：WP=W，即:2_* * 七一11w = wI 3 12且满足w1 + w2 = 1w = 0.75= 0.25信源的极限熵为：H = H =-ZZ p(s | s )p(s )log p(s )i j3=x 0.75log_ + x 0.75 log 3 +1 x 0.25 log1 = ?2 301111011110111103，且输入信源

17、分布为等概率分布，设2,1，1 .设输入符号集与输出符号集为X=Y=0，失真矩阵为求 Dmax,Dmin 及 R(D)。解：D =Z p(x)min(b(x,j) = 0 minx jDmax3=min(Z p(x)d(x, j)=-j4x由于失真矩阵对称且输入信源等概分布，则有与之相同的信道转移矩阵，设为:1 3aaaaa1 3aaaaa1 3aa1 3a平均失真度为:D = p(xy)d(xy) = p(y x)p(x)d(xy) = ：p(y I x)d(xy)1sc=x 12oc = 3oc4得 a = D31 1 1R(D) = /(X; Y) = log4 - H(1 一。, 33

18、 0,3 Z)1113 332.设二元信源为00.50.50,失真矩阵为们= aa八，试求该信源的Dmax,Dmin及 R(D)0解：D = (x) min(d(x, y) = 0 minx yD = min(Z p(x)d(x, y) = amaxzy x由于失真矩阵对称，在输入等概的情况下，有相同类型的信道转移矩阵，设为:1- Pp 1 一则睥心)仆y) = p(别所S y)=加+ ；热=paD有 P = (2分) aR(Q) = log 2 - H (g) = 1 - H () aa3.设输入符号集为乂=0, 1,输出符号集为Y=0, 1。定义失真函数为: d(0,0)=d(l,l)=0

19、 d(0,l)=d(l,0)=l试求失真矩阵d,当输入等概时，求Dmax,Dmin, R(D)解：根据已知识条件，失真矩阵为：D = S p(x)minG(x,j)= 0 minD = minmaxX( )1in p(x)d(x,y)=- 由于失真矩阵对称，输入等概，则信道矩阵具有同样的对称性，设为:1 aa 一a1 a_平均失真 D = Z p(xy)d(xy) =aR (D) = I (X; Y) = 1 H (1 D, D)4.三元信源输入符号集为0, 1, 2且输入等概率分布，失真函数4寸为:当i=j时，d。= 0 , 当i勺时，d。= 1，(i,j=0,1,2)。写出其失真矩阵；求率

20、失真函数及其定义域。 解：根据题意可得其失真矩阵为：一0 1 1 0 11 1 0D = Z p(x) min(d (x, y) = 0 min x yDmax=min(Z p(x)d(x, y) = 2y x3由于失真矩阵对称且输入信源等概分布，则有与之相同的信道转移矩阵，设为:1 一 2aa aa1 一 2aaa a1 一 2a平均失真度为:D = Z p(xy)d(xy) = p(y I x)p(x)d(xy) =1 p(y1 x)d (xy)41 ,=x 6a = 2a 3得a = D2 11、R (D) = I (X ;Y) = log3 - H (1 D D D)A A5.设输入符

21、号与输出符号为X = Y = 0,1,2,3，且输入符号等概分布。设失真矩阵为:0.211110.411110.611110.8求Dmax, Dmin, R(Dmax),R(Dmin)及其所对应的转移概率矩阵。解：根据Dmin和Dmax的定义：D =Ep(x)mind(x, y) = 0.2x 1 + 0.4x 1 + 0.6x 1 + 0.8x 1 = 0.5 min & y4444x1111111 一 1 一D = minZ p(x)d(x, y) = min0.2 x + 3 x ,0.4 x + 3 x ,0.6 x + 3 x ,0.8 x + 3 x y x=0.85Dmin所对应

22、的转移概率矩阵为：匕Dmax所对应的转移概率矩阵为：Pp10000100001000011000100010001000Dmin所对应的转移概率矩阵为：p =Dmax所对应的转移概率矩阵为：Pp =+1 x 310一_010012,1 x 1+0 x 2 = 13333因此：R(Dmin) = I(X;Y) = log4 = 2bit/symbolp1R(Dmax) = I(X;Y) = H(Y) - H(YI X) = 0bit/symbolp26.设输入输出符号集为X=Y=0, 1,输入概率分布p(0)=l/3, p(l)=2/3。失真矩阵为求Dmax, Dmin, R(Dmax),R(D

23、min)及其所对应的转移概率矩阵。解：根据Dmin和Dmax的定义：D . = p(x) mind(x, y) = 0 x 3 + 0 x 3 = 0 xyD= min p (x)d (x, y) = min0 xmax y x1 当转移概率矩阵为 pi 时，p(y) = p(0) = p(01 x)p(x) + p(01 x )p(x )= TOC o 1-5 h z 1112232p(y ) = p(1) = p(11 x)p(x) + p(11 x )p(x )=-211223当转移概率矩阵为 P2 时，p(y ) = p(0) = p(0l x )p(x ) + p(01 x )p(x

24、 ) = 011122p(y ) = p(1) = p(1l x)p(x) + p(1l x )p(x ) = 121122因此:R(Dmin) = I(X;Y) = ZZ p(y | x )p(x )log pj I j pi. . j jp(y.)p1i ji12| 323log3 + 3log2 = log3- 3R(Dmax) = I(X;Y) = H(Y) - H(Y l X) = 0P20.57.输入等概分布，失真矩阵为d =1，求Dmax，Dmin, R(Dmax),R(Dmin)及其所2 1对应的转移概率矩阵。x1 = 0.752解：根据Dmin和Dmax的定义: TOC o

25、1-5 h z D =Z p (x) mind (x, y) = 0.5 x +1 min2y匕xD = min p(x)d (x, y) = min0.5 x + 2 x ,1 x +1 x = 1 max y2222x八 1 0Dmin所对应的转移概率矩阵为：p = 0 10 1Dmax所对应的转移概率矩阵为：P =八120 11 当转移概率矩阵为 P1 时，p(y) = p(0) = p(0| x)p(x) + p(0| x )p(x )=- 1112221p(y ) = p(1) = p(1| x)p(x) + p(1| x )p(x )=211222当转移概率矩阵为 P2 时，p(y

26、 ) = p(0) = p(0| x )p(x ) + p(0| x )p(x ) = 011122p(y ) = p(1) = p(1| x)p(x) + p(1| x )p(x ) = 121122因此：R( D min) = I (X; Y) = log 2 = 1bit / symbolP1R(Dmax) = I(X;Y) = H(Y) - H(YI X) = 0Pp设有扰离散信道的输入端是以等概率出现的A、B、C、D4个字母，该信道的正确传输 概率为0.5，错误传输概率平均分布在其他3个字母上。写出该信道的信道矩阵，并计算该 信道的信道容量。解：根据题意，该有扰离散信道的信道矩阵为：

27、11112666111162661111662611116662从信道矩阵可以看出，该信道是均匀信道，故其信道容量为:C = log2 4 - H (0.5) - 0.5log2 3 = 0.21bit / symbol设有两个离散二元对称信道，错误概率均为p。求这两个二元对称信道的信道矩阵 及其级联信道矩阵，并计算该级联信道的信道容量，并指明在什么情况下能达到信道容量。解：根据题意，两个二元对称信道的信道矩阵为：两个信道级联之后的信道矩阵为两个信道矩阵之积，所以:P = PP =1 - p p I1 - pP=(1 一 p)2 + p22P (1 - P)1 2_ P 1 - p_|_P 1 - P_ 2p (1 - p)(1 一 p)2 + p2所以级联信道仍然是一个二元对称信道，其信道容量为:C = 1 - H (2p(1 - p)由于信道矩阵当在输入等概分布时，达到信道容量。设有扰离散信道的输入端是以等概率出现的A，B，C，D4个字母。该信道的正确 传输概率为1/2,错误传输概率平均