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

1 莫尔斯电报系统中，若采用点长为 1 划长为 点和划出现的概率分别为 2/3 和 1/3，试求它的信息速率 (s)。 解 : 平均每 个 符号 长为 :秒 每个 符号的熵为 9 1 8 比特 /符号 所以 ， 信息速率为 44 比特 /秒 一个 8 元编码系统，其码长为 3，每个码字的第一个符号都相同 (用于同步 )，若每秒产生 1000 个码字，试求其信息速率(s)。 解 : 同步信号均相同不含信息 ,其余认为等概 ,每个码字的信息量为 3*2=6 比特 ； 所以 ， 信息速率为 600010006 比特 /秒 一对无偏的骰子，若告诉你得到的总的点数为： (a) 7； (b) 12。试问各得到了多少信息量 ? 解 : (a)一对 骰子总点数为 7 的概率是366所以 ， 得到的信息量为 66( 比特 (b) 一对骰子总点数为 12 的概率是361所以 ， 得到的信息量为 比特 过充分洗牌后的一付扑克 (含 52 张牌 )，试问： (a) 任何一种特定排列所给出的信息量是多少 ? (b) 若从中抽取 13 张牌，所给出的点数都不相同时得到多少信息量 ? 解 : (a)任一特定排列的概率为!521, 所以 ， 给出的信息量为 21lo g 2 比特 (b) 从中任取 13 张牌 ,所给 出的点数都不相同的概率为 1 3 1 31 3 1 35 2 5 21 3 ! 4 4 所以 ， 得到的信息量为 313522 C 比特 . 有一个非均匀骰子，若其任一面出现的概率与该面上的点数成正比，试求各点出现时所给出的信息量，并求掷一次平均得到的信息量。 解 :易证每次出现 i 点的概率为21i,(6,5,4,3,2,1,21lo g)(2612 丁植树一行，若有 3 棵白杨、 4 棵白桦和 5 棵梧桐。设这 12 棵树可随机地排列，且每一种排列都是等可能 的。若告诉你没有两棵梧桐树相邻时，你得到了多少关于树的排列的信息 ? 解 : 可能有的排列总数为 27720!5!4!3 !12 没有两棵梧桐树相邻的排列数可如下 图 求得， Y X Y X Y X Y X Y X Y X Y X Y 图中 X 表示白杨或白桦，它有37种排法， Y 表示梧桐树可以栽种的位置，它有58种排法，所以共有58*37=1960 种排法保证没有两棵梧桐树相邻，因此若告诉 你 没有两棵梧桐树相邻时，得到关于树 排列的信息为 19602 =特 某校入学考试中有 1/4 考生被录取， 3/4 考生未被录取。被录取的考生中有 50%来自本市，而落榜考生中有 10来自本市，所有本市的考生都学过英语，而外地落榜考生中以及被录取的外地考生中都有 40%学过英语。 (a) 当己知考生来自本市时，给出多少关于考生是否被录取的信息 ? (b) 当已知考生学过英语时，给出多少有关考生是否被录取的信息 ? (c) 以 x 表示是否落榜， y 表示是否为本市学生， z 表示是否学过英语， x、 y 和 z 取值为 0 或 1。试求 H(X)， H(Y|X)， H(Z| 解 : X=0 表示未录取， X=1 表示录取； Y=0 表示本市 ， Y=1 表示外地 ； Z=0 表示学过英语 ， Z=1 表示未学过英语，由此得 31( 0 ) , ( 1 ) ,44( 0 ) ( 0 ) ( 0 0 ) ( 1 ) ( 0 1 )3 1 1 1 1,4 1 0 4 2 514( 1 ) 1 ,55( 0 ) ( 0 ) ( 0 0 ) ( 1 ) ( 0 1 )1 4 4 0 1 3,5 5 1 0 0 2 51 3 1 2( 1 ) 1 ,2 5 2 5p x p xp y p x p y x p x p y z p y p z y p y p z 3 22221 3 1 3( ) ( 0 0 ) ( 0 0 ) ( 0 ) / ( 0 ) /1 0 4 5 81 1 1 5( 1 0 ) ( 0 1 ) ( 1 ) / ( 0 ) /2 4 5 8( 0 0 ) ( 1 0 )( ; 0 ) ( 0 0 ) l o g ( 1 0 ) l o g( 0 ) ( 1 )3535 88l o g l o 4 5 1 2a p x y p y x p x p yp x y p y x p x p yp x y p x y p x y p x yp x p x 比 特( ) ( 0 0 )( ( 0 0 , 0 ) ( 0 0 ) ( 0 1 , 0 ) ( 1 0 ) ) ( 0 ) / ( 0 )1 9 4 3 1 3 6 9( ) /1 0 1 0 1 0 4 2 5 1 0 4( 1 0 )( ( 0 0 , 1 ) ( 0 1 ) ( 0 1 , 1 ) ( 1 1 ) ) ( 1 ) / ( 0 )1 1 2 1 1 3 3 5( ) /2 2 5 4 2 5 1 0 4(;b p x zp z y x p y x p z y x p y x p x p zp x zp z y x p y x p z y x p y x p x p 22222222( 0 0 ) ( 1 0 )0 ) ( 0 0 ) l o g ( 1 0 ) l o g( 0 ) ( 1 )6 9 3 56 9 3 51 0 4 1 0 4l o g l o 4 1 0 4440 . 0 2 6 9 83 4 1( ) ( ) l o g l o g 4 0 . 8 1 1 34 3 4( ) ( 0 ) ( 0 0 ) l o g ( 0 0 ) ( 0 ) ( 1 0 ) l o g ( 1p x z p x zz p x z p x zp x p X p x p y x p y x p x p y x p y x 比 特比 特222 2 2 20)( 1 ) ( 0 1 ) l o g ( 0 1 ) ( 1 ) ( 1 1 ) l o g ( 1 1 )3 1 3 9 1 0 1 1 1 1l o g 1 0 l o g l o g 2 l o g 24 1 0 4 1 0 9 4 2 4 20 . 6 0 1 7p x p y x p y x p x p y x p y x 比 A、 B 两 组人中进行民意测验，组 A 中的人有 50%讲真话 (T)， 30%讲假话 (F)， 20%拒绝回答 (R)。而组 B 中有 30%讲真话，50%讲假话和 20%拒绝回答。设选 A 组进行测验的概率为 p，若以 I(p)表示给定 T、 F 或 R 条件下得到的有关消息来自组 A 或组B 的平均信息量，试求 I(p)的最大值。 解 :令 , ，则 4 比特得令同理0 3 6 4 )(l o )(l o g)(l o g)o o l o g)1(o g)1(o g)1(o o o o (l o g)(l o g)()();()(,()()()()(a 222223102231022222随机掷三颗骰子，以 X 表示第一颗骰子抛掷的结果，以 Y 表示第一和第二颗骰子抛掷的点数之和，以 Z 表示三颗骰子的点数之和 。试求 H(Z|Y)、 H(X|Y)、 H(Z| H()和 H(Z|X)。 解 :令 X=2,Z=2+ H(H(H( 6比特 H(X)= H(= 6特 H(Y)= H(3) = 6l 36l 336l 236l 36l 222222 = 特 H(Z)= H(2+)27216l o o o o o o o o 22222222= 特 所以 H(Z/Y)= H( 特 H(Z/X) = H(3)= 特 H(X/Y)=H(X)+H(Y/X) = 特 H(Z/H(Z/Y)= 特 H()=H(X/Y)+H(Z/=特 算习题 的 I (Y； Z)， I (X； Z)， I (Z)， I (Y； Z|X)和 I (X； Z|Y)。 解 :I(Y;Z)=H(Z) =H(Z)- H( 特 I(X;Z)=H(Z)=特 I(Z)=H(Z) =H(Z) =特 I(Y;Z/X)=H(Z/X)= H(3)3) =特 I(X;Z/Y)=H(Z/Y)=H(Z/Y) =0 有一个系统传送 10 个数字： 0, 1, , 9。奇数在传送时以 概率错成另外的奇数，而其它数字总能正确接收。试求收到一个数字平均得到的信息量。 解 :设系统输出 10 个数字 X 等概 ,接收数字为 Y, 5 显然 101)(101)()()(9190 H(Y)=特奇 奇奇奇偶18l o o l o g)()()(l o g)()(0)(l o g),()(l o g),()/(22,2222 xy I(X;Y)= 比特 令 , 一等概消息集，各消息相应被编成下述二元码字 : 000， 011， 101， 110 001， 010， 100， 111 通过转移概率为 p 的 送。试求 ： (a) 接收的第一个数字 0 与 间的互信息量。 (b) 接收的前二个数字 00 与 间的互信息量。 (c) 接收的前三个数字 000 与 间酌互信息量。 (d) 接收的前四个数字 0000 与 解 :（ a）接收前一个数字为 0 的概率 2180)0()()0( ii b i t 1(l o o g)0( )0(l o g)0;( 2212121 （ b）同理 4180)00()()00( ii b i t 1(l o (l o g)00( )00(l o g)00;( 24122121 （ c）同理 8180)0 0 0()()0 0 0( ii bi t 1(l (l 00( )000(l 00;( 28132121 （ d）同理 )1(6)1()0 0 0 0()()0 0 0 0( 42268180ii i 6 b i t (6)1()1(8l o g)1(6)1()1(l o g)0000()0000(l o g)0000;(令 X、 Y、 Z 是概率空间，试证明下述关系式成立。 (a) H() H(Y|X) H(Z|X)，给出等号成立的条件。 (b) H()=H(Y|X) H(Z| (c) H(Z| H(Z|X)，给出等号成立的条件。 解 : (b) )/()/()/(1l o g)()/(1l o g)()/()/(1l o g)()/(1l o g)()/(y zx y zx y zx y z (c) )/()/(1l o g)/()()/(1l o g)/()()/(y zx y z （由第二基本不等式） 或 0)1)/()/(l o g)/()()/()/(l o g)/()()/(1l o g)/()()/(1l o g)/()()/()/( y zx y zx y zx y z（由第一基本不等式） 所以 )/()/( ， 等号成立的条件为 )/()/( ,对所有 , ,即在给定 X 条件下 Y 与 Z 相互独立。 (a) )/()/()/()/()/( 7 等号成立的条件为 )/()/( ,对所有 , ,即在给定 X 条件 下 Y 与 Z 相互独立。 对于任意概率事件集 X、 Y、 Z，证明下述三角不等式成立。 H(X|Y) H(Y|Z)H(X|Z) H(X|Y)/H( H(Y|Z)/H(H(X|Z)/H(解 : (a) )/()/()/()/()/()/( (b) )()/()()/()/()()/()/()/()/()()/()()/(0)(,0)/()/()/()()/()/()/()/()/()()/()/()/()/()()/()/()/()/()()/()/()/()()/()/()()/()/()()/()()/()()/(注：ba 2 21 12122112121 0,0 d(X， Y)=H(X|Y) H(Y|X)为 X 和 Y 的信息距离，令 (X， Y)=H(X|Y) H(Y|X)/H( X 和 Y 的信息距离系数。试证明有关距离的三个公理： d(X， X)=0 d(X， Y) 0 d(X， Y)=d(Y， X) d(X， Y) d(Y， Z) d(X， Z) 解 : (a) 0)/()/(),( 0)/()/(),( b) ),()/()/()/()/(),( (c) 8 ),()/()/(),(),()/()/()/()/()/()/()/()/()/()/()/()/()/(),(),(定义 S(X， Y)=1 (X， Y)=I(X； Y)/H( X 和 Y 之间的信息相似度，证明： 0 S(X， Y) 1 S(X， X)=1 S(X， Y)=0， X 和 Y 独立时。 解 :(a) 1)(),(),()()/()/()()()()()()(),( 0);( 有 0);( 所以 1);(0 (b) 1)( )()( )/()()( ),(),( c) 当且仅当 X 和 Y 独立时， I（ X； Y） =0，所以 ， 当且仅当 X 和 Y 独立时， 0)( ),(),( 令 X Y Z 为马尔可夫链，证明： I(X； Z|Y)=0 I(Z)=I(Y； Z) I(Y； Z|X)=I(Y|Z) I(X； Z) I(Y； Z|X)I(Y； Z) 解 : X Y Z 为马尔可夫链，有 p(z/p(z/y),对所有 x,y,z。 )0);();();();()/;();();()()/(l o g)()()/(l o g)()()/()()/(l o g)()/()/(l o g)()/;();()()/(l o g)()()/(l o g)()()/(l o g)();(0)/()/(l o g)()/;( zz yz y xz y xz yz y xz y xz y x 若三个随机变量有如下关系： x y=z，其中 x 和 y 独立。试证明： H(X)H (Z) H(Y)H(Z) H(H(Z) 9 I(X； Z)=H(Z) H(Y) I(Z)=H(Z) I(X； H(X) I(Y； Z|X)=H(Y) I(X； Y|Z)=H(X|Z)=H(Y|Z) 解 : (a) H(X) H (Z) )()(0)()()/()();()()(l o g)()(l o g)()()(l o g)()/()(l o g)()/(l o g)()/()/()();(/ 即(b) H(Y) H(Z) )()(0)()()/()(),()()/()/()();(即同理(c) H( H(Z) )()()()/()();()()/()();(0)/(d) I(X； Z)=H(Z) H(Y) I(X;Z)=H(Z)=H(Z) (e) I(Z)=H(Z) )()/()();( 0)/( (f) I(X； H(X) )()/()();( 0)/( (g) I(Y； Z|X)=H(Y) H(Y/0 I(Y;Z/X)=H(Y/X)=H(Y/X)=H(Y) 10 (h) I(X； Y|Z)=H(X|Z)=H(Y|Z) I(X;Y/Z)=H(X/Z)=H(Y/Z) 而 H(X/0,H(Y/0 所以 I（ X； Y/Z） =H(X/Z） =H(Y/Z) # 明 )(概率矢量 ),( 21 的 上凸函数 ，即对 ， 0 1 和矢量 )()1()()1( 2121 证明： 1 1 1 1 2 1 2 2 1 2 2 21 2 1 1 2 1 2 1 2 2 1 21 2 1 2 1 211 1 2 21( , , . . . , ) , ( , , . . . , ) , 0 1(1 ) ( (1 ) , (1 ) , . . . , (1 ) )( (1 ) ) ( (1 ) ) l o g ( (1 ) )l o g ( (1 ) ) (1 )i i i i p p p P p p p p p p p P p p p pp p p p 设 1211 1 2 2111212l o g ( (1 ) )l o g (1 ) l o g( ) (1 ) ( )i i p p H 不 等 式 中 的 等 号 当 且 仅 当 时 成 立 . #用拉格朗日乘因子法求解下述泛函的极值。 Hn( , 1 解： 1211 2 1 21( 1 )12212( , , . . . , ) l n( , , . . . , , ) ( , , . . . , )l n 1 0 , 1 , 2 , . . . , ,11 , 1( , , . . . , ) ( , , . . . , ) l o g #nn n i n n n nH p p p p pp p p H p p p i n p p p p H nn n n 令 由 得 又极 大 值 为 11 令 U 是非负整数集合，事件 k U 的概率为 p(k)，且 0)(常数 )。试求使 H(U)为最大的分布 p(k)。 解： 121210000 1 1 2 1 20 0 01120010( ) l n , , . . . , , ) l n ,l n 1 0 ,1,1k k kk k p pp k p Ap p p p k p k p k p 约 束 条 件 为=1 和 设 f(由 得 由 约 束 条 件 和 得21 2 1101( ) , 0 , 1 , 2 , . . .( ) ( ) #e H P = , = 1 - =1 + A 1 + A 1 + 的 上 凸 函 数 , 此 时 为 极 大 设 X 是在 1， 1上为均匀分布的随机变量。试求 )， 2)和 3)。 解 : (a) 其它,011,)( 21 211121 (b) 令 其它,01,2 1)( 2 lo g)()(2102YC(c) 令3231,3 其它,01,61)()(32o o g)6l o g (61)6l o g (61)(l o g)()(221001332323232连续随机变量 X 和 Y 的联合概率密度为 其它00,0,11)( 2222求 )， )， Y)及 I(X； Y)。 解： 13 222222222222222222222( ) ( ) ( ) 1 ,2( ) ( ) ( ) 1 ,( ) ( ) l o g ( ) l n( ) ( ) l o g ( ) l n( ) (x xc y x f x y d y f x y d y x y f x y d x f x y d x y p x p x d p y p y d Y f x y 同 理) l o g ( ) l n ( )( ; ) ( ) ( ) ( ) l n #c c cf x y d x d y a Y H X H X H X 设 X 和 Y 为连续随机变量，且 X 的概率密度为 22 4/21)( 条件概率密度为22 3/)21()31()|( 中 x， y。试求 )， )， )和 I(X； Y)。 解： 2 2 220 ( 0 , 2 ) , 2 ,1( ) ( ) l o g ( ) l o g ( 4 )2 q x q x d x e 14 2 2 2 222222 2 211( ) / 3 ( ) / 3/42221( ) / 3/ 4 / 42( / ) ( ) ( / ) l o g ( / )1 1 1( ) l o g ( )2 3 31l o g ( 3 )21 1 1( ) ( ) ( / ) ( )2 3 2cy x y X q x p y x p y x d x d ye e e d x d y q x p y x d x e e d x e 2221( ) l o g ( 4 )21( ; ) ( ) ( / ) l o g ( 4 / 3 )21( / ) ( ) ( ; ) l o g ( 3 ) #2 Y H Y H Y Y H X I X Y e 设 x 为 0， 上分布的连续随机变量，且满足 0 )( ， 求实现最大微分熵的分布及相应的熵值。 解： 1 2 1 20001 2 1 20 0 00012( ) ( ) l n ( ) ,( ) ( )( ) , , ) ( ) l n ( ) ( ) ( )( ) ( ) ( 1 )( ) ( )( ) , , ) q x q x d xq x d x x q x d xq x q x q x d x x q x d x q x d x l n d x q x d xq x q 约 束 条 件 为=1 和 =s f(当 f( 为 最 大 值 时12( ) ( ) q x e, 在 约 束 条 件 下 取 得 最 大 值 , 此 时 15 12120000m a xm a ) ( ) ,1) ( ) , 0( ) l n l n 1 #x d x x q x d xe d xx e d q x e e e d x s 12 束 条 件 =1 和 =s 得= , 的 分 布 令概率空间 2/12/1 11X，令 Y 是连续随机变量。已知条件概率率密度为 其它0224/1)|( 试求 (a) Y 的概率密度 (y) (b) I(X； Y) (c) 若对 Y 作如下的硬判决： 1111011 求 I(X； Y)，并对结果进行解释。 解 :(a) 由已知， 其它,013,)( 411 其它,031,)( 411 其它,031,11,13,)1()1()1()1()()()()(8141816 （ b） b i t o o o g)( 231812114121381 g)( 23141212134121 b i ()();( (c)由 1,111,01,1可求得 V 的分布为 412141 101( 1,111,01,1求得 V 的条件分布为 )1,1(),1,1(),(,0)1,1(),1,0(),1,0(),1,1(),(,)/( 21.),;();()();(1)1/(l o g)1/()1()1/(l o g)1/()1()/(o o 22221241变换没有信息损失可见 i i i 第三章 离散信源无失真编码 :长为 n 码字的数目为 因此长为 N 的 D 元不等长码 至多有： 1)1(1 : 17 00)(o : )1(l o g)1()1;()1(l o g)1()1;(,)(0)()(l o g)()1(l o g)1;(1l o g)()1(l o g)1;()(.,.,)(24124143211121121121121 : （ a）二元 码 %o g)()(l o g)()(21012101i t 码效率平均码长（ b）三元 码 注意： K=10 为偶数，需要添一个概率为零 的虚假符号 18 %o o g)()(22101 :二元 码 （ a）二元 码 %o g)()(l o g)()(231231i t 码效率平均码长（ b） %o g)(2)(2)()(229121222i t 码效率平均码长（ c） %o g)(3)(3)()(23271321333i t : (a)根据唯一可 译码的判断方法可知 ,输出二元码字为异字头码 ,所以它是唯一可译码。 4 6 22 比特 19 (b)因为信源是二元无记忆信源，所以有 )()()()(21 其中 1,0,),(2121 4 3 0 4 6 7 2 ,1,10 4 7 8 2 9 6 ,1,10 5 3 1 4 4 ,1,10 5 9 0 4 ,1,10 6 5 6 ,1,17 2 ,1,10 8 ,1,1,1,188,1877,1766,1655,1544,1433,1322,1211,1100,10个中间数字相应的信源数字的平均长度 6 9 5 ,1801 ii i 中间数字 (c) 根据表有 1,4 8,27,26,25,24,23,22,21,20,2 可计算每个中间数字所对应的平均长度 ,2802 ii i 中间数字 由 二元码 /信源符号 编码效率为 信道及其容量 ： (a) 对称信道 (b) 对称信道 (c) 和信道 (课堂教学例题 )! ： (a): 可先假设一种分布 ,利用信道其容量的 充要条件 来计算 (课堂教学例题 ) (b): 准对称 信道 ！ ： 课堂教学例题 20 ：该题概率有误，应把 1/32 改为 1/64。 每个符号的熵为 ii g)( 281 采样频率 W=8000 以信息 速率 R 为 01 0 0H ( S ) ：每象点 8 电平量化认为各级出现的 概率相等，即 H(U)=3 以 信息 速率 R 为 760050030R ： 0001(l o S(1W l o H z,W： 31 高斯信道的信道容量为 C 。CR，R。，。高斯高斯高斯因则一定可以实现如故无法判定是否能实现的大小关系与信道容量但无法判定即的信道容量大于高斯信道因此时信道容量如该信道不是高斯信道不可实现如该信道是高斯信道所以4445422103,104,10410104)311(l o S(1W l o 离散信道编码定理 习题 ： 道 213161612131316121P 21 有 41)()(,21)( 321 131(416121)(31)6121(413121)(83)3161(412121)(32132)()()()(832121111111 21)()()()(313121212121 72)()()()(2476121313131 72)()()()(2473141323232 yw 73)()()()(2472141333333 yw 所以 最大后验概率译码 为： 33121 x,x 判为判为和 译码错误概率 为： 2411)211(41416121)(1)()()()( 3332131 大 似 然 译 码 准 则 译码为：332211 x,x,x 判为判为判为 ： 21)211(4121412121)(1)()(1)()(1)( 333222111 e 22 可见 ,最大似然译码的译码 错误概率 大于 最大后验概率译码 的译码 错误概率 。 第七章 信道编码 1. 设 (7,3)码的生成矩阵为 111100001101100011101G (1) 写出该码的一致校验矩阵 H； (2) 写出该码的所有许用码字； (3) 译码表” 伴随式 )译码表； (4) 写出接收矢量 R=1000001 的错误图样 ,并 译相应的 许用码字 ； (5) 写出 该码在 误转移概率为 p)中传输的 (平均 )正确 译码 概率 (6) 写出该码在 误转移概率为 p)中传输的 漏检概率 称不可检测错误概率 )的表达式 . 解 : (1) G 不为系统码形式 ,我们通过初等行变换变为系统码形式 111100001101100011101G 11110000101010011101100111001010110011101因此 1111000101010011000100110001H(2) 由 C=该码的 许用码字为 0000000,0111001,1101010,1010011,1011100,1100101,0110110,0001111 该码的 最小汉明距离为 4。 (3) 该码的 标准阵由 16 个陪集构成 , 在 误转移概率为 p1/2)应将重量最小的错误图样选作陪集首 , 故该码的标准译码表为 许用码字 0000000 (陪集首 ) 0111001 1101010 1010011 1011100 11001