Chương 3: Kênh rời rạc không phụ thuộc thời gian - Phương án giải mã tối ưu. Định lý căn bản của LTTT

Nội dung text: Chương 3: Kênh rời rạc không phụ thuộc thời gian - Phương án giải mã tối ưu. Định lý căn bản của LTTT

1. Ch ươ ng 3: Kênh r i r c khơng ph thu c th i gian 3.2Ph ươ ngángi imãt i ưu.Đ nh lýcănb nc aLTTT
2. 2 Hu ỳnh V ăn Kha 9/30/2010 Gi imã • Gi x1,x 2, ,x M và y1,y 2, ,y L lnl ư tlàcácký t inputvàoutput. • Mtph ươ ngángi imã làm tphépt ươ ng ng mikýt output yj vim tkýt input xj*.Khi nh nđ ư c yj tas gi imãthành xj* • Gi imãlàphânho cht pkýt outputthànhcác tp B1, ,B M saochom i y trong Bi s gi imã thành xi • Mtph ươ ngángi imãcĩth xemnh ư mtkênh deterministicv it pkýt inputlà y1,y 2, ,y L vàt pkýt outputlà x1,x 2, ,x M
3. 3 Hu ỳnh V ăn Kha 9/30/2010 Víd Xác X Y Z su t 1 1/2 x1 y1 x1 1 1/4 x2 y2 x2 1/2 1/4 x y x 3 1/2 3 3
4. 4 Hu ỳnh V ăn Kha 9/30/2010 Bàitốngi imã • Chotr ư cinput,xâyd ngph ươ ngángi imãsao choxácsu tsailành nh t • Gi s yj tươ ng ngv i xj* • Gixácsu tđúnglà p(e’) ,tacĩ: • Kênhvàinputchotr ư cnêncác p(y j) khơngđ i • Vim i yj chotr ư cch cnch n xj* saocho p(x j*|y j) làl nnh t
5. 5 Hu ỳnh V ăn Kha 9/30/2010 Tr ư ngh pinputđ ngxácsu t • Nuinputlàđ ngxácsu tthì • Vi y c đnhthìvi cc cđ i p(x i|y) tươ ngđ ươ ng vivi cc cđ i p(y|x i) • Nh ư vyv iphânph iđ uc ainputthìph ươ ng ángi imãt i ưulàv im i y chotr ư cch n xi saocho p(y|x i) làc cđ i • Tas xétk hơnv nđ nàytrongch ươ ng4
6. 6 Hu ỳnh V ăn Kha 9/30/2010 Víd • Xétmatr nkênh y1 y2 y3 x1 1/21/31/6 x2 1/61/21/3 x3 1/31/61/2 • Gis p(x 1)=½,p(x 2)=p(x 3)=¼ • Tìmph ươ ngángi imãt i ưuvàtínhxácsu tsai
7. 7 Hu ỳnh V ăn Kha 9/30/2010 ðnhlýcănb nc aLTTT • Gi s ngu nsinhradãycáckýt nh phânv i đnhl ư ngkhơngđ i R bit/giây,vàđ nhl ư ng truy nc angu nkhơngquá1bit/giây • Trong n giây,ngu nsinh nR kýt • Tngs mutincĩth cĩtrong n giâylà 2nR • Chúý 2nR cĩth khơngnguyên,trongtr ư ngh p đĩ,tal y[ 2nR ](ph nnguyênc a 2nR ) • Tacũngkhơngquantâmtr ư ngh ps kýt ca ngu nkhơngph ilà2.Vìn us kýt mãlà D và ngu nsinh S kýt /giây,thìtrong n giây,ngu n sinh DnS =2 nS log D.Vàcĩth xemnĩnh ư ngu n nh phânv iđ nhl ư ng R=S log D
8. 8 Hu ỳnh V ăn Kha 9/30/2010 ðnhlýcănb nc aLTTT • Thayvìtruy nt ngkýt quakênh,tas mãhĩa miblock n kýt • Dođ nhl ư ngtruy nkhơngquá1bit/giâynên s kýt mãmãhĩam iblockkhơngquá n kýt • Đ gi đnhl ư ngsinhc angu nlà R,tac n 2nR t mãchi udài≤ n • Ýt ư ngc ơ bnc ađ nhlýlàchotr ư c ε >0,n u ch n n đ ln,tacĩth tìmđ ư c 2nR t mãvà mtcáchgi imãsaochosais đu< ε,nghĩalà < ε btch pt mãnàođ ư ctruy nquakênh
9. 9 Hu ỳnh V ăn Kha 9/30/2010 ðnhlýcănb nc aLTTT • Cáigiáph itr làtac nph ich n giâytr ư ckhi mãhĩangu ntin,cũngcĩth ph it nthêmth i gianch dovi cmãhĩavàgi imã • Thêmvàođĩ,ph ươ ngánmãhĩavàgi imã trongđ nhlýnàyr tph ct pvàkhĩth chi n trongth ct
10. 10 Hu ỳnh V ăn Kha 9/30/2010 ðnhlýcănb nc aLTTT • Víd ,xét R=2/5 và n =5 .Trong 5 giây,s mu tincĩth cĩdongu nsinhralà 2nR =4 .G i chúnglà m1,m 2,m 3,m 4 • Tagánchom i mi mtdãynh phânđ dài≤5 m1 00000 m1 00 m2 01101 m2 01 m3 11010 m3 10 m4 10111 m4 11
11. 11 Hu ỳnh V ăn Kha 9/30/2010 ðnhlýcănb nc aLTTT • Vicáchmãhĩath hai,ch cnm tkýt b truy nsaicũngkhơngth nàopháthi nđ ư c • Vicáchmãhĩath hai,m ivi ctruy nsaim t kýt đucĩth pháthi nvàt đngs al iđ ư c • Nunh nđ ư cchu i v,tach cnch nt mã w saochos v tríkhácnhauc a w và v làítnh t • Chúýr nghait mãkhácnhaus khácnhau ít nh t3v trí.Dođĩm ivi ctruy nsaim tkýt s pháthi nvàs al iđ ư c
12. 12 Hu ỳnh V ăn Kha 9/30/2010 ðnhlýcănb nc aLTTT • Mt nchu i làm tdãy n kýt inputho coutput • Mt b mã(s,n) làm tt pg m s các nchu iinput x(1) , , x(s) cùngv im tph ươ ngángi imã,nghĩa làm thàmchot ươ ng ngm i nchu ioutputv i mttrongcác x(i) .Các x(i) gilàcáct mã • Mtph ươ ngángi imãlàm tphânho cht pcác noutputthànhcáct pconr inhau B1, ,B s,mà mi Bi gilàm t tpgi imã .Khinh nđ ư c (i) outputtrong Bi tas gi imãthành x
13. 13 Hu ỳnh V ăn Kha 9/30/2010 ðnhlýcănb nc aLTTT • Mi nchu iinputlàm ttr ngtháic avector ng unhiên X =( X1,X 2, ,X n) • Mi nchu ioutputlàm ttr ngtháic avector ng unhiên Y =( Y1,Y 2, ,Y n) • Gi s x(i) đư ctruy nquakênh,xácsu tsailà
14. 14 Hu ỳnh V ăn Kha 9/30/2010 ðnhlýcănb nc aLTTT • Xácsu tsaic ab mãlà • Xácsu tsaic cđ iđ ư cđ nhnghĩalà • Dođĩn u pm(e) ≤ε thìt mãnàocũngđ ư c truy nv isais ≤ε
15. 15 Hu ỳnh V ăn Kha 9/30/2010 ðnhlýcănb nc aLTTT • Mt b mã(s,n,λ) làm tb mã( s,n )saochoxác su tsaic cđ ilà ≤λ Địnhlýcănb ảnc ủaLTTT: Chotr ư cm tkênhr ir ckhơngph thu cth i gianv idungl ư ngkênhC>0vàm ts dươ ng a a R<C.Khiđĩt nt im tdãycácb mã 1, 2, A a nR , n, saocho n làm tb mã( [2 ],n,λn)và λn
    0khin
    ∞