信息论与编码(第二版)习题答案,陈运,主编.doc

信息论与编码(第二版)习题答案,陈运,主编 2.3 居住某地区的女孩子有25%是大学生，在女大学生中有75%是身高160厘米以上的，而女孩子中身高160厘米以上的占总数的一半。假如我们得知“身高160厘米以上的某女孩是大学生”的消息，问获得多少信息量？ 解： 设随机变量X代表女孩子学历 X P(X) x1（是大学生） 0.25 x2（不是大学生） 0.75 设随机变量Y代表女孩子身高 Y P(Y) y1（身高160cm） 0.5 y2（身高160cm） P(Y) 0.5 y2（身高 log6 不满足信源熵的极值性。 解： 2 H ( X ) = ? p( x) log p( x) i i i 6 = ?(0.2 log 0.2 + 0.19 log 0.19 + 0.18 log 0.18 + 0.17 log 0.17 + 0.16 log 0.16 + 0.17 log 0.17) = 2.657 bit / symbol H ( X ) log 2 6 = 2.585 不满足极值性的原因是 6 p( xi ) = 1.07 1 。 i 2.7 证明：H(X3/X1X2) H(X3/X1)，并说明当X1, X2, X3是马氏链时等式成立。 证明： H ( X 3 / X1 X 2 ) ? H ( X 3 / X1 ) = ? p( xi1 xi 2 xi 3 ) log p( xi 3 / xi1 xi 2 ) + p( xi1 xi 3 ) log p( xi 3 / xi1 ) i1 i 2 i 3 i1 i 3 = ? p( xi1 xi 2 xi 3 ) log p( xi 3 / xi1 xi 2 ) + p( xi1 xi 2 xi 3 ) log p( xi 3 / xi1 ) i1 i 2 i 3 i1 i 2 i 3 =p( x x x ) p( xi 3 / xi1 ) i1i 2i 3 i1 i 2 i 3 p( xi 3 / xi1 xi 2 ) p( x ? p( x i1xi 3 / xi1 ) ? i 2xi 3 )?1? log2 e i1 i 2 i 3 ? p( xi3 / x i1x i 2 ) ? ? ? 1 i 2 i 3 p( x? = ?i1 xi 2 ) p( xi 3 / xi1 ) ? p( xi1 xi 2 xi 3 ) ? log2 e i i1 i 2 i 3 ? = ? ? p( x? ? ? i1 xi 2 ) i1 i 2? p( xi 3 / xi1 )? ? ?1? log2 e i 3 ? = 0 H ( X 3 / X1 X 2 ) H ( X 3 / X1 ) 当p( xi 3 / xi1 ) p( x?1 = 0时等式等等 i 3 / xi1 xi 2 ) ? p( xi 3 / xi1 ) = p( xi 3 / xi1 xi 2 ) ? p( xi1 xi 2 ) p( xi 3 / xi1 ) = p( xi 3 / xi1 xi 2 ) p( xi1 xi 2 ) ? p( xi1 ) p( xi 2 / xi1 ) p( xi 3 / xi1 ) = p( xi1 xi 2 xi 3 ) ? p( xi 2 / xi1 ) p( xi 3 / xi1 ) = p( xi 2 xi 3 / xi1 ) 等式等等的等等是X1 , X 2 , X 3是马 _氏链 2.8 证明：H(X1X2 。 Xn) H(X1) + H(X2) + + H(Xn)。 证明： H ( X 1 X 2 .X n ) = H ( X 1 ) + H ( X 2 / X 1 ) + H ( X 3 / X 1 X 2 ) + . + H ( X n / X 1 X 2 .X n?1 ) I ( X 2 ; X 1 ) 0 I ( X 3 ; X 1 X 2 ) 0 . 3 ? H ( X 2 ) H ( X 2 / X 1 ) ? H ( X 3 ) H ( X 3 / X 1 X 2 ) 4 I ( X N ; X 1 X 2 .X n?1 ) 0 ? H ( X N ) H ( X N / X 1 X 2 .X n?1 ) H ( X 1 X 2 .X n ) H ( X 1 ) + H ( X 2 ) + H ( X 3 ) + . + H ( X n ) 2.9 设有一个信源，它产生 0，1 序列的信息。它在任意时间而且不论以前发生过什么符号， 均按 P(0) = 0.4，P(1) = 0.6 的概率发出符号。 (1) 试问这个信源是否是平稳的？ (2) 试计算H(X2),并写出 H(X 3 /X 12XX )及 (3) 试计算H(XH；44信源中可能有的所有符号。 解： (1) 这个信源是平稳无记忆信源。因为有这些词语：“它在任意时间而且不论以前发生过什么符号” (2) H ( X 2 ) = 2H ( X ) = ?2 (0.4 log 0.4 + 0.6 log 0.6) = 1.942 bit / symbol H ( X 3 / X 1 X 2 ) = H ( X 3 ) = ? p( xi ) log p( xi ) = ?(0.4 log 0.4 + 0.6 log 0.6) = 0.971 bit / symbol i H = N lim ? H ( X N / X 1 X 2 .X N ?1 ) = H ( X N ) = 0.971 bit / symbol (3) H ( X 4 ) = 4H ( X ) = ?4 (0.4 log 0.4 + 0.6 log 0.6) = 3.884 bit / symbol X 4的所有符号： 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 11112.10 一阶马尔可夫信源的状态图如下图所示。信源 X 的符号集为0, 1, 2。(1) 求平稳后信源的概率分布； (2) 求信源的熵H。 解： (1) 5 1 有一个马尔可夫信源，已知p(x1|x1)=2/3，p(x2|x1)=1/3，p(x1|x2)=1，p(x2|x2)=0，试画出该信源的香农线图，并求出信源熵。 解：该信源的香农线图为： 2/3 (x1) 1(x2) 在计算信源熵之前，先用转移概率求稳定状态下二个状态x1和 x2 的概率p(x1)和p(x2) 立方程：p(x1)?p(x1x1)p(x1)+p(x1x2)p(x2) =2 p(x1)?p(x2) p(x2)?p(x2x1)p(x1)+p(x2x2)p(x2) = 3p(x1)?0p(x2)p(x1)?p(x2)=1 得p(x1)?马尔可夫信源熵H = ? 3 4 p(x2)?1 4 ?p(x)?p(x i I J j xi)logp(xjxi)得 H=0.689bit/符号 3 2设有一个无记忆信源发出符号A和B，已知p(A)?1。求： 4.p(B)?4 计算该信源熵； 设该信源改为发出二重符号序列消息的信源，采用费诺编码方法，求其平均信息传输速率； 又设该信源改为发三重序列消息的信源，采用霍夫曼编码方法，求其平均信息传输速率。 解：H(X)? ?p(x)logp(x) =0.812 bit/符号 i i X 发出二重符号序列消息的信源,发出四种消息的概率分别为 33p(AB)? p(AA)?4?4?164?4?16 339p(BB)?3 p(BA)?34?4?164?4?16 用费诺编码方法 代码组 bi BB 01 BA 10 2 AB 110 3 AA 111 3 2 无记忆信源 H(X)?2H(X)?1.624 bit/双符号 平均代码组长度 2=1.687 bit/双符号 H(X2)R2?=0.963 bit/码元时间 三重符号序列消息有8个,它们的概率分别为 1 p(AAB)?64p(BAA)?64 p(ABA)?p(AAA)?64p(BAB)?64 p(ABB)?64p(BBB)?p(BBA)?646464 用霍夫曼编码方法 代码组 bi BBBBBABABABBAABBAAABA AAA 2799964643364 0 0 1 (191 110 3 ) 1(64) 1101 3 64) 00100 3 6 1()111111 5 0 111110 5 4 1()0 11101 5 0111005 H(X3)?3H(X)=2.436 bit/三重符号序列 3=2.469码元/三重符号序列 H(X3) =0.987 bit/码元时间 R3= 3已知符号集合x1,x2,x3?为无限离散消息集合，它们的出现概率分别为 p(x1)? 2 ， p(x2)?1p(xi)?p(x3)?11 求： i2 用香农编码方法写出各个符号消息的码字（代码组）； 计算码字的平均信息传输速率； 计算信源编码效率。 解: 2 H(X)? ?p(x)logp(x)=2 bit/符号 i i I ?Pibi?=2码元/符号 I R? H(x) ?1bit/码元时间 R =100% C 二进制信道C=1 bit/码元时间信源编码的编码效率?= 对这八个符号作二进制码元的霍夫曼编码,写出各个码字,并求出编码效率。 解: H(X)? ?p(x)logp(x)=2552bit/符号,时间熵H X t ?2.552bit/s Rt=Ht?2.552bit/s 霍夫曼编码 符号pi代码组 bi C0.4 0 0 1 B0.