信息與編碼理論課后習題答案

1 莫爾斯電報系統(tǒng)中，若采用點長為 1 劃長為 點和劃出現(xiàn)的概率分別為 2/3 和 1/3，試求它的信息速率 (s)。 解 : 平均每 個 符號 長為 :秒 每個 符號的熵為 9 1 8 比特 /符號 所以 ， 信息速率為 44 比特 /秒 一個 8 元編碼系統(tǒng)，其碼長為 3，每個碼字的第一個符號都相同 (用于同步 )，若每秒產(chǎn)生 1000 個碼字，試求其信息速率(s)。 解 : 同步信號均相同不含信息 ,其余認為等概 ,每個碼字的信息量為 3*2=6 比特 ； 所以 ， 信息速率為 600010006 比特 /秒 一對無偏的骰子，若告訴你得到的總的點數(shù)為： (a) 7； (b) 12。試問各得到了多少信息量 ? 解 : (a)一對 骰子總點數(shù)為 7 的概率是366所以 ， 得到的信息量為 66( 比特 (b) 一對骰子總點數(shù)為 12 的概率是361所以 ， 得到的信息量為 比特 過充分洗牌后的一付撲克 (含 52 張牌 )，試問： (a) 任何一種特定排列所給出的信息量是多少 ? (b) 若從中抽取 13 張牌，所給出的點數(shù)都不相同時得到多少信息量 ? 解 : (a)任一特定排列的概率為!521, 所以 ， 給出的信息量為 21lo g 2 比特 (b) 從中任取 13 張牌 ,所給 出的點數(shù)都不相同的概率為 1 3 1 31 3 1 35 2 5 21 3 ! 4 4 所以 ， 得到的信息量為 313522 C 比特 . 有一個非均勻骰子，若其任一面出現(xiàn)的概率與該面上的點數(shù)成正比，試求各點出現(xiàn)時所給出的信息量，并求擲一次平均得到的信息量。 解 :易證每次出現(xiàn) i 點的概率為21i,(6,5,4,3,2,1,21lo g)(2612 丁植樹一行，若有 3 棵白楊、 4 棵白樺和 5 棵梧桐。設這 12 棵樹可隨機地排列，且每一種排列都是等可能 的。若告訴你沒有兩棵梧桐樹相鄰時，你得到了多少關于樹的排列的信息 ? 解 : 可能有的排列總數(shù)為 27720!5!4!3 !12 沒有兩棵梧桐樹相鄰的排列數(shù)可如下 圖 求得， 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 表示第一顆骰子拋擲的結(jié)果，以 Y 表示第一和第二顆骰子拋擲的點數(shù)之和，以 Z 表示三顆骰子的點數(shù)之和 。試求 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 有一個系統(tǒng)傳送 10 個數(shù)字： 0, 1, , 9。奇數(shù)在傳送時以 概率錯成另外的奇數(shù)，而其它數(shù)字總能正確接收。試求收到一個數(shù)字平均得到的信息量。 解 :設系統(tǒng)輸出 10 個數(shù)字 X 等概 ,接收數(shù)字為 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 通過轉(zhuǎn)移概率為 p 的 送。試求 ： (a) 接收的第一個數(shù)字 0 與 間的互信息量。 (b) 接收的前二個數(shù)字 00 與 間的互信息量。 (c) 接收的前三個數(shù)字 000 與 間酌互信息量。 (d) 接收的前四個數(shù)字 0000 與 解 :（ a）接收前一個數(shù)字為 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 的信息距離系數(shù)。試證明有關距離的三個公理： 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 的 上凸函數(shù) ，即對 ， 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 是非負整數(shù)集合，事件 k U 的概率為 p(k)，且 0)(常數(shù) )。試求使 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 + 的 上 凸 函 數(shù) , 此 時 為 極 大 設 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ù)隨機變量 X 和 Y 的聯(lián)合概率密度為 其它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ù)隨機變量，且 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， 上分布的連續(xù)隨機變量，且滿足 0 )( ， 求實現(xiàn)最大微分熵的分布及相應的熵值。 解： 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 是連續(xù)隨機變量。已知條件概率率密度為 其它0224/1)|( 試求 (a) Y 的概率密度 (y) (b) I(X； Y) (c) 若對 Y 作如下的硬判決： 1111011 求 I(X； Y)，并對結(jié)果進行解釋。 解 :(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 碼字的數(shù)目為 因此長為 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 為偶數(shù)，需要添一個概率為零 的虛假符號 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)根據(jù)唯一可 譯碼的判斷方法可知 ,輸出二元碼字為異字頭碼 ,所以它是唯一可譯碼。 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個中間數(shù)字相應的信源數(shù)字的平均長度 6 9 5 ,1801 ii i 中間數(shù)字 (c) 根據(jù)表有 1,4 8,27,26,25,24,23,22,21,20,2 可計算每個中間數(shù)字所對應的平均長度 ,2802 ii i 中間數(shù)字 由 二元碼 /信源符號 編碼效率為 信道及其容量 ： (a) 對稱信道 (b) 對稱信道 (c) 和信道 (課堂教學例題 )! ： (a): 可先假設一種分布 ,利用信道其容量的 充要條件 來計算 (課堂教學例題 ) (b): 準對稱 信道 ！ ： 課堂教學例題 20 ：該題概率有誤，應把 1/32 改為 1/64。 每個符號的熵為 ii g)( 281 采樣頻率 W=8000 以信息 速率 R 為 01 0 0H ( S ) ：每象點 8 電平量化認為各級出現(xiàn)的 概率相等，即 H(U)=3 以 信息 速率 R 為 760050030R ： 0001(l o S(1W l o H z,W： 31 高斯信道的信道容量為 C 。CR，R。，。高斯高斯高斯因則一定可以實現(xiàn)如故無法判定是否能實現(xiàn)的大小關系與信道容量但無法判定即的信道容量大于高斯信道因此時信道容量如該信道不是高斯信道不可實現(xiàn)如該信道是高斯信道所以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) 寫出 該碼在 誤轉(zhuǎn)移概率為 p)中傳輸?shù)?(平均 )正確 譯碼 概率 (6) 寫出該碼在 誤轉(zhuǎn)移概率為 p)中傳輸?shù)?漏檢概率 稱不可檢測錯誤概率 )的表達式 . 解 : (1) G 不為系統(tǒng)碼形式 ,我們通過初等行變換變?yōu)橄到y(tǒng)碼形式 111100001101100011101G 11110000101010011101100111001010110011101因此 1111000101010011000100110001H(2) 由 C=該碼的 許用碼字為 0000000,0111001,1101010,1010011,1011100,1100101,0110110,0001111 該碼的 最小漢明距離為 4。 (3) 該碼的 標準陣由 16 個陪集構(gòu)成 , 在 誤轉(zhuǎn)移概率為 p1/2)應將重量最小的錯誤圖樣選作陪集首 , 故該碼的標準譯碼表為 許用碼字 0000000 (陪集首 ) 0111001 1101010 1010011 1011100 11001