信息论与编码课后作业答案.pdf

2.1 一 个 马 尔 可 夫 信 源 有 3 个 符 号u1,u2,u3， 转 移 概 率 为 ：p(u1|u1)=1/2， p(u2|u1)=1/2，p(u3|u1)= 0，p(u1|u2)=1/3，p(u2|u2)= 0，p(u3|u2)= 2/3， p (u 1 |u 3 ) = 1/ 3， p (u 2 |u 3) = 2/ 3，p (u 3 |u 3 ) = 0，画出状态图并求出各符号稳态概率。 解：状态图如下 状态转移矩阵为： 1/21/20 1/302/3 1/32/30 p = 设状态 u1，u2，u3稳定后的概率分别为 W1，W2、W3 由 1231 WP=W W +W+W= 得 1231 132 23 123 11 233 12 23 2 3 1 W+W+ 1W =W W+W=W W=W W+W+W = 计算可得 1 2 3 10 25 9 25 6 25 W W W = = = 2.2 由符号集0，1组成的二阶马尔可夫链，其转移概率为：p(0|00)=0.8，p(0|11)=0.2， p (1| 00) =0.2， p (1|11) =0.8， p (0| 01) =0.5， p (0|10) =0.5， p (1| 01)=0.5， p (1|10) =0.5。 画出状态图，并计算各状态的稳态概率。 解：p(0|00)=p(00|00)= 0.8p(0|01)=p(10|01)= 0.5 p (0 |11)= p (10 |11)= 0.2 p(0|10) =p(00|10) =0.5 p(1|01) =p(11|01) = 0.5 p(1|00) =p(01|00) = 0.2 p(1|11)=p(11|11)=0.8 p(1|10) =p(01|10) =0.5 u1u2 u3 1/2 1/2 1/3 2/3 2/3 1/3 于是可以列出转移概率矩阵： 0.80.200 000.50.5 0.50.500 000.20.8 p = 状态图为： 0 00 1 1 01 1 0.8 0.2 0.5 0.5 0.5 0.5 0.2 0.8 设各状态 00，01，10，11 的稳态分布概率为 W1,W2,W3,W4有 4 1 i=1 i WP=W W = 得 131 132 243 244 1234 0.5 0.20.5 0.50.2 0.50.8 1 0.8WW=W WW=W WW=W WW=W W+W+W+W + + + + = 计算得到 1 2 3 4 5 14 1 7 1 7 5 14 W W W W = = = = 2.5 居住某地区的女孩子有 25%是大学生，在女大学生中有 75%是身高 160 厘米 以上的，而女孩子中身高 160 厘米以上的占总数的一半。假如我们得知“身高 160 厘米以上的某女孩是大学生”的消息，问获得多少信息量？ 解： 设随机变量 X 代表女孩子学历 Xx1（是大学生）x2（不是大学生） P(X)0.250.75 设随机变量 Y 代表女孩子身高 Yy1（身高160cm）y2（身高160cm） P(Y)0.50.5 已知：在女大学生中有 75%是身高 160 厘米以上的 即：p(y/x)= 0.75 bit 11 求：身高 160 厘米以上的某女孩是大学生的信息量 即： bit p p(x)p(y/x I(x/y1.415 0.5 log 0.250.75 (y) )= logp(x/y)= log ) 1 111 1111 = 2.7 设有一离散无记忆信源，其概率空间为 12340123 3/81/41/41/8 Xxxxx P = = （1）求每个符号的自信息量 （2）信源发出一消息符号序列为202120130213001203210110321 010021032011223每个符号携带的信息量求该序列的自信息量210，和平均 解： 122 1 ) = log 1 log 8 1.415 p(x)3 I(xbit= 同理可以求得I(x2) = 2bit,I(x3) = 2bit,I(x3)= 3bit 因为信源无记忆，所以此消息序列的信息量就等于该序列中各个符号的信息量之和 就有：I=14I(x1)+13I(x2)+12I(x3)+6I(x4)=87.81bit 平均每个符号携带的信息量为 87.81 1.95 45 =bit/符号 2.13 有两个二元随机变量X和Y，它们的联合概率为 Y X x1=0x2=1 y1=01/83/8 y2=13/81/8 并定义另一随机变量Z = XY（一般乘积），试计算： (1) H(X), H(Y), H(Z), H(XZ), H(YZ)和H(XYZ)； (2) H(X/Y), H(Y/X), H(X/Z), H(Z/X), H(Y/Z), H(Z/Y), H(X/YZ), H(Y/XZ) 和H(Z/XY)； (3) I(X;Y), I(X;Z), I(Y;Z), I(X;Y/Z), I(Y;Z/X)和I(X;Z/Y)。 bit/symbolp(yp(yH(Y p(y)p(x y)p(x y p(y)=p(x y)+p(x y bit/symbolp(xp(xH(X p(x)p(x y)p(x y p(x)=p(x y)+p(x y j jj i ii )log)1 ) 2 1 8 1 8 ) 2 1 88 ) )log)1 ) 2 1 8 1 8 ) 2 1 88 ) 22212 12111 22122 21111 = = 3 +=+= = 1 + 3 = = = 3 +=+= = 1 + 3 = Z = XY的概率分布如下： symbolp z P Z k k 0.544 bit/ 8 log 1 8 1 8 log 7 8 7 (z)H(Z) 8 1 8 7 10 (Z) 2 21 = = += = z= = 解（1） symbolp(x z p(x z)=p(z p(z)p(x z)+p(x z p(x z)=p(z)p(x z p(z)p(x z)p(x z p(x z)=p(x p(x z p(x)p(x z)+p(x z ik ikik 1.406 bit/ 8 log 1 8 1 8 log 3 8 3 2 log 1 2 1 )logp(x z)H(XZ) 8 ) 1 ) 8 3 8 ) ) )0.5 )= 0 ) 222 22212 11112 12111 111 21 21111 = = += = = = 7 0.5= += = = symbolp(y z p(y z)=p(z p(z)p(y z)+p(y z p(y z)=p(z)p(y z p(z)p(y z)p(y z p(y z)=p(y p(y z p(y)p(y z)+p(y z jk jkjk 1.406 bit/ 1 8 log 1 8 3 8 log 3 82 log 11 2 )logp(y z)H(YZ) 8 ) 1 ) 3 88 ) ) )0.5 )= 0 ) 222 22212 11112 12111 111 21 21111 = = += = = = 7 0.5= += = = p x y zx y z p x y z)p(x y p x y z)p(x y z p x y z p x y z p x y z )=p(x z)+p( )1/8( )=p(x y)( )0( )0( )0( 11111121 11111 11211111 212 221 211 = + = = = symbol x y zp(x y zH(XYZ p x y z)=p(x y p x y zx y z p x y z p x y z)=p(x y p x y zx y z)=p(x y p x y z)p(x z)p(x y z ijk ijkijk 1.811 bit/ 8 log 1 8 1 8 log 3 8 3 8 log 3 8 3 8 log 1 8 1 )logp() 8 ) 1 ( )=p(x y)p( )0( 8 ) 3 ( )p( 8 3 82 )( 2 22222 22222122 122 12112 12212112 11111121 = = + = = + = = + = 1 1 = (2) symbolH symbolH bit/symbolH symbolH symbolH symbolH symbolH symbolH symbolH symbolp(x y ij ijij (Z/XY)=H(XYZ)H(XY)1.811 1.811= 0 bit/ (Y/XZ)=H(XYZ)H(XZ)1.811 1.406= 0.405 bit/ (X/YZ)=H(XYZ)H(YZ)1.811 1.406= 0.405 (Z/Y)=H(YZ)H(Y)1.4060.406 bit/ (Y/Z)=H(YZ)H(Z)1.4060.544= 0.862 bit/ (Z/X)=H(XZ)H(X)1.4060.406 bit/ (X/Z)=H(XZ)H(Z)1.4060.544 = 0.862 bit/ (Y/X)=H(XY)H(X)1.8110.811 bit/ (X/Y)=H(XY)H(Y)1.8110.811 bit/ 1.811 bit/ 8 log 1 8 1 8 log 3 8 3 8 log 3 8 3 8 log 1 8 1 )logp(x y)H(XY) 2 = = = 1= = 1= = 1= 1= = = += (3) bit/symbolI bit/symbolI bit/symbolI symbolI(Y;Z)=H(Y)H(Y/Z symbolI(X;Z)=H(X)H(X/Z symbolI (X;Z/Y)=H(X/Y)H(X/YZ)0.811 0.405= 0.406 (Y;Z/X)=H(Y/X)H(Y/XZ)0.8620.405= 0.457 (X;Y/Z)=H(X/Z)H(X/YZ)0.8620.405= 0.457 )0.862= 0.138 bit/ )0.8620.138 bit/ (X;Y)H(X)H(X/Y)0.8110.189 bit/ = = = =1 =1 =1= 2.16 黑白传真机的消息元只有黑色和白色两种，即 X=黑，白，一般气象图上，黑色的出 现概率 p(黑)0.3，白色出现的概率 p(白)0.7。 （1）假设黑白消息视为前后无关，求信源熵 H(X)，并画出该信源的香农线图 （2） 实际上各个元素之间是有关联的，其转移概率为： P(白|白)0.9143，P(黑|白)0.0857， P(白|黑)0.2，P(黑|黑)0.8，求这个一阶马尔可夫信源的信源熵，并画出该信源的香农线 图。 （3）比较两种信源熵的大小，并说明原因。 解： （1） 22 1010 0.3log0.7log0.8813 37 H(X)=+=bit/符号 P(黑|白)=P(黑) 黑白 0.7 0.3 0.70.3 P(黑|黑)P(黑) P(白|黑)P(白) （2）根据题意，此一阶马尔可夫链是平稳的（P(白)0.7 不随时间变化，P(黑)0.3 不随时 间变化） 212 222 2 1 )p(xi,yj)log ) 0.9143 0.7log 1 0.0857 0.7log 11 0.3log 0.91430.08570.2 1 0.3log 0.8 p(xi,yj ij H(X)=H(X|X= =+ 0.2 +0.8 0.512bit/符号 P(白|白)P(白) 2.32 一阶马尔可夫信源的状态图如图 213 所示，信源 X 的符号集为（0，1，2） 。 （1）求信源平稳后的概率分布 P(0),P(1),P(2) （2）求此信源的熵 （3）近似认为此信源为无记忆时，符号的概率分布为平稳分布。求近似信源的熵 H(X)并与 H进行比较 01 2 p/2 1-p 1-p p/2 p/2 p/2 p/2 p/2 1-p 图2-1 3 解:根据香农线图,列出转移概率距阵 /2/2 /21/2 /2/21 ppp P= ppp ppp 1 令状态 0,1,2 平稳后的概率分布分别为 W1,W2,W3 3 1 i=1 i WP=W W = 得到 1231 1232 123 (1p) 22 p) 22 1 W+ pW + pW =W pW W+ pW =W W+W+W + (1 = 计算得到 1 3 1 3 1 3 W W W = = = 由齐次遍历可得 )= 3 1 H(1p, p , p )= (1p)log 1 og 2 pl 322 i i WiH(X|W 1pp H(X)=+ H(X ,) = log3 =1.58bit/符号 由最大熵定理可知H(X) 存在极大值 或者也可以通过下面的方法得出存在极大值: H(X)2 1 log(1p) + 1p (1)+ loglog 1222(1p) p ppp = p +p = 11 2(1p)22(1p) p = +又0p1所以 2(1p) p 0,+当 p=2/3 时1 2(1p) p = 0p 2/3p1 时 ) = log0 2(1p) (Xp p H 所以当 p=2/3 时H(X) 存在极大值,且 H(X)max= 1.58bit/符号 所以H(X)H(X , ) 3.1 设二元对称信道的传递矩阵为 3 2 3 1 3 1 3 2 (1) 若P(0)= 3/4,P(1)= 1/4，求H(X), H(X/Y), H(Y/X)和I(X;Y)； (2) 求该信道的信道容量及其达到信道容量时的输入概率分布； 解： 1) =H(X)H(X/Y)= 0.811 0.7490.062 bit/symbolI bit/symbolH I=H(X)H(X/Y)=H(Y)H(Y/X bit/symbolp(y p(y)p(x y)p(x y)=p(x)p(y/x)p(x)p(y/x p(y)=p(x y)p(x y)p(x)p(y/x)+p(x)p(y/x bit/symbol p(y/xpH(Y/X symbolp(xH(X j j ij jiiji i i (X;Y) (X/Y)=H(X)H(Y)+H(Y/X)= 0.8110.980+ 0.918 = 0.749 )(X;Y) )= (0.5833log0.58330.4167log0.4167)0.980 H(Y) 0.4167 3 2 4 1 3 1 4 ) 0.5833 343 2 4 ) 0.918 )log10 3 lg 2 3 2 43 lg 1 3 1 43 lg 1 3 1 43 lg 2 3 2 4 (x)p(y/x)log) )= 0.811 bit/ 4 log 1 4 1 4 log 3 4 ) 22 22212122212 21211112111 2 22 = =+= = 3 +=+= = 3 + 1 1 =+ = + 1 + 1 + 3 = ( 3 = += ( 3 = 2) 222 112 maxI(X;Y) = loglog 2 +( lg 2 lg)log 10 = 0.082 3333 mi bit/symbolC=mH=+ 其最佳输入分布为 1 2 i p(x) = 3.3 在有扰离散信道上传输符号 0 和 1，在传输过程中每 100 个符号发生一个错 误，已知 P(0)=P(1)=1/2，信源每秒内发出 1000 个符号，求此信道的信道容量。 由题意可知该二元信道的转移概率矩阵为： 0.990.01 0.010.99 P = 为一个 BSC 信道 所以由 BSC 信道的信道容量计算公式得到： 2 1 log 1 =0.92 1000C=920bit/sec i i i t Cpbit/sign p C t = = logsH(P) = log2 = 1C = 3-6 设有扰离散信道的传输情况分别如图 317 所示。求出该信道的信道容量。 XY 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 图3-1 7 解： 11 22 11 22 11 22 11 22 00 00 00 00 对称信道 log(Y|a) i C=mH 1 log42log2 2 = 取 2 为底C=1bit/符号 3-12题（略） ， 概率分别为 l/2， l/4， 1/8， 1/16， 1/32， 1/64， 1/128， 1/128， 试编成这样的码：000，001，010，011，100，101，110，111 的码。求：(1) 信源的符号熵 H(X)； (2) 出现一个“1”或一个“0”的概率；(3) 这种码的编码效率；(4) 相应的香农码和费诺码；(5) 该码的 编码效率。 5.6 某信源有 8 个符号 ,a a 12,a3,?,a8 解：解： （1）（bit/信源符号） 8 1.984 ii i H X() = = p log p = = (2) 每个信源使用 3 个二进制符号， 出现 0 的次数为： 出现 1 的次数为： 所以：P(0)= ，P(1)= (3) 因为K = = 3，所以 = = 0.661 (4) 相应的香农编码 信 源 符 号 xi 符 号 概 率 pi 累 加 概 率 Pi -Logp(xi) 码长 Ki 码字 x11/2 0110 x21/4 0.5 2210 x31/8 0.75 33110 x41/16 0.875 441110 x51/32 0.938 5511110 x61/64 0.969 66111110 x71/128 0.984 771111110 x81/128 0.992 7711111110 相应的费诺码 信源符 号 xi 符 号 概 率 pi 第一次 分组 第二次 分组 第三次 分组 第四次 分组 第五次 分组 第六次 分组 第 七 次 分组 二元码 x1 1/200 x2 1/4010 x3 1/8 0 110 x4 1/16 0 1110 x5 1/32 0 11110 x6 1/64 0 111110 x7 1/128 0 1111110 x8 1/128 1 1 1 1 1 1 1 11111110 （5）香农码和费诺码相同 平均码长为（码符号/信源符号） 编码效率为： 1 2 Log(2) 1 4 +Log(4) 1 8 +Log(8) 1 16 +Log(16) 1 32 +Log(32) 1 64 +Log(64) 1 128 Log(128)+ 1 128 +Log(128)=1.984 （5）香农码和费诺码相同 平均码长为 编码效率为： 5-11 （1）信源熵 （2）香农编码： 信 源 符 号 xi 符 号 概 率 pi 累 加 概 率 Pi -Logp(xi)码长Ki码字 x10.3201.644200 x20.220.322.1843010 x30.180.542.4743100 x40.160.722.6443101 x50.080.883.64441110 x60.040.964.644511110 平均码长： 编码效率为 （3） 费诺编码为 信源符 号xi 符号概 率 pi 1234编码码长 x10.32 0 0002 x20.221012 x30.18 1 0102 x40.16 1 01103 x50.08 1 011104 x60.04111114 平均码长为： 编码效率： x10.320.320.380.400.601012 x20.220.220.320.380.40102 x30.180.180.220.32112 x40.160.160.180003 x50.080.1200104 x60.0400114 平均码长为： 编码效率： （4）哈夫曼编码 信源符号 xi 符 号 概 率 pi 编码过程编码 码 长 6.4 设二元(6,3)码的生成矩阵为： 100011 010001 001110 G = = 试给出其一致校验矩阵。 解：解： k =GI P H = T P I n k 001100 101010 100011 6.5 设二元(7,4)码的生成矩阵为： 1000111 1001001 0010011 0001110 G = = (1) 求该码的所有码字； (2) 求该码的一致校验矩阵； (3) 作出该码的标准阵列； 解：(1)所有码字如下表： 0000000 0100101 1000111 1100010 00011100101011 1001001 1101100 0010011 0110110 1010100 1110001 00111010111000 1011010 1111111 (2) 110110 101101 111001 H = (3) =G 1