Bài giảng Lý thuyết thông tin - Chương 4, Phần 1: Mã sửa sai - Huỳnh Văn Kha

Nội dung text: Bài giảng Lý thuyết thông tin - Chương 4, Phần 1: Mã sửa sai - Huỳnh Văn Kha

1. Ch ươ ng4:Mós asai 4.1Kho ngcỏchHammingvàch n Hamming
2. 2 Hu ỳnh V ăn Kha 9/30/2010 Gi ithi u • ch ươ ngnàytach xộtkờnhnh phõnđ ix ng • Cỏcinputc akờnhđ ư cch nt mtt pcỏct mónh phõnchi udài n,nghĩalàt pcỏcdóy n kýt 0và1 • Gi s cỏct móxu thi nv ixỏcsu tb ngnhau • Dol icúth xyra btc v trớnàoc achu i inputnờnoutputlàt p 2n dóynh phõnđ dài n • Bàitoỏnđ utiờnlàtỡmph ươ ngỏngi imót i ưu chob mónúitrờn
3. 3 Hu ỳnh V ăn Kha 9/30/2010 Gi ithi u • Kýhi ucỏct móvàcỏcchu ioutputl nl ư tlà w1, w2, ., ws và v1, v2, • Ph ươ ngỏngi imót i ưulàph ươ ngỏnlàmc c ti uxỏcsu tsai • Khinh nđ ư c v,nh ư tađóbi t,ph ươ ngỏngi i mót i ưulàch n w saocho p( w|v) ccđ i • Nh ưngdocỏct mócúcựngxỏcsu tnờnc cđ i p( w|v) tươ ngđ ươ ngv ivi cc cđ i p( v|w)
4. 4 Hu ỳnh V ăn Kha 9/30/2010 Kho ngcỏchHamming • Tađ nhnghĩa kho ngcỏch d( v1, v2) gi ahaidóy nh phõn n kýt v1, v2 làs v trớmà đúkýt móc a v1, v2 khỏcnhau • Vớd : v1 =011011, v2 =110001 Thỡ d( v1, v2)=3 • Nuinputlà w vàoutputlà v thỡkhiđúkờnhđó truy nsaiđỳng d( w, v) kýt .Dođún uxỏcsu t truy nsaic akờnhlàβ,thỡ
5. 5 Hu ỳnh V ăn Kha 9/30/2010 Ccủ i p(v|w) • Tas sosỏnh p(v|w1)và p(v|w2) • Đt d1 =d (w1,v), d2 =d (w2,v),tacú • Chỳý,đ iv ikờnhnh phõnđ ix ngtaluụngi s 0 1.V y p(v|w1)> p(v|w2)khivàch khi d1 < d2 • Vy p(v|w )c cđ ikhi d(v,w )c cti u
6. 6 Hu ỳnh V ăn Kha 9/30/2010 ðnhlý4.1 Gi s b móchokờnhnh phõnđ ix ngg m s t móđ dài n cúxỏcsu tnh ư nhau.Ph ươ ngỏngi i mót i ưulàph ươ ngỏnlàm ccti ukho ng cỏch .Nghĩalàv im idóy v nh nđ ư c,b gi i mós ch nt mó w saochokho ngcỏch d(w,v ) lành nh t Nucúnhi uh ơnm tc cti uthỡch nt mónào trongs đúcũngkhụng nhh ư ngđ nxỏcsu t sai
7. 7 Hu ỳnh V ăn Kha 9/30/2010 Vớd • Chob mó w1 =00000 w2 =10011 w3 =11100 w4 =01111 • Tỡmph ươ ngỏngi imót i ưukhinh nđ ư c v = 01011, v’=00110?
8. 8 Hu ỳnh V ăn Kha 9/30/2010 Tớnhch tc akho ngcỏch Tacúth ki mch ngr ngkho ngcỏchHamming làm tmetric,nghĩalàth acỏctớnhch tsau a. d(v1, v2)≥0, d(v1, v2)=0khivàch khi v1 = v2 b. d(v1, v2)= d(v2, v1) c. d(v1, v3)≤ d(v1, v2)+ d(v2, v3) Btđ ngth ccu icựnglàb tđ ngth ctamgiỏc • Dotagi imódóy v thànht móg nv i v nh t nờnxu thi nkhỏini mb mó“t t”làb mó cúcỏct mó“ xa”nhau
9. 9 Hu ỳnh V ăn Kha 9/30/2010 B ủ 4.2 Gi w1,w 2, ,w s làcỏct mónh phõnchi udài n,và e làm ts nguyờnd ươ ng.Gi s d( wi, wj)≥2e+1 ,v im i i≠j Thỡkhiđú,m is truy nsaikhụngquỏ e bitđ u cúth sađ ư c. Nu d( wi, wj)≥2e ,v im i i≠j ,thỡm is truy n saikhụngquỏ e1 bitđ ucúth sađ ư cvàm i s truy nsai e bitđ ucúth phỏthi nđ ư c, nh ưngch ưach cs ađ ư c
10. 10 Hu ỳnh V ăn Kha 9/30/2010 B ủ 4.2 Ng ư cl i,b mócútớnhch tm is truy nsai khụngquỏ e bitđ us ađ ư cthỡph ith amón d( wi, wj)≥2e+1 ,v im i i≠j Mtb mócútớnhch tm is truy nsaikhụng quỏ e1 bitđ us ađ ư c,vàm is truy nsai khụngquỏ e bitđ uphỏthi nđ ư cthỡph ith a món d( wi, wj)≥2e ,v im i i≠j
11. 11 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhb ủ 4.2 wi wj wi wj d( wi, wj)=2e+1 d( wi, wj)=2e • Gi s w đư ctruy nvàchu inh nđ ư clà v. Xột w’làt mókhỏc w • Đutiờngi s kho ngcỏchc cti uc ahait móớtnh tlà 2e+1 ,tacú d(w,v)+ d(w’, v) ≥d (w,w’) ≥2e+1
12. 12 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhb ủ 4.2 • Đ b gióimó v thành w’ thỡ d(w,v) ≥e +1. Nghĩalàđ gi imósaithỡph itruy nsaiớtnh t e+1 kýt • Nukho ngcỏchgi ahait móớtnh tlà2 e thỡ d(w,v)+ d(w’, v) ≥d (w,w’) ≥2e • Nusaiđỳng e kýt và d(w’, v)= e thỡgi imó thành w hay w’đ uđ ư c,nghĩalàcúth sai • Nusaiớth ơn e kýt thỡ d(w,v)lành nh tvàs gi imóđỳng. • Chi ung ư cl it ươ ngt
13. 13 Hu ỳnh V ăn Kha 9/30/2010 Ch nHamming Khi e lnthỡkho ngcỏchgi acỏct mócũngl n hơnvàd nt is t móớtđi.Cõuh iđ tralàcú nhi unh tbaonhiờut mótrongm tb mócú th sađ ư cm is truy nsaikhụngquỏ e kýt Địnhlý4.3: Nub móch a s dóynh phõnchi udài n cúth sasaim is truy nsaikhụngquỏ e kýt ,thỡ:
14. 14 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhủ nhlý4.3 • Gicỏct mólà w1, w2, , ws.V cỏc“m tc u” “tõm” wi “bỏnkớnh” e.M i“m tc u”nh ư vy ch at tc dóynh phõn v th a d(wi,v)≤ e • Dob mós ađ ư cm is truy nsai e kýt nờn cỏc“m tc u”làr inhau • S dóynh phõntrongm im tc ulà • Dođú
15. 15 Hu ỳnh V ăn Kha 9/30/2010 Chỳý • C đnh e,n vàg i s làs nguyờnl nnh tth a đi uki nđ nhlý4.3thỡch ưach ct nt ib mó sasaiđ ư c e kýt ch a s t móchi udài n • Vớd ,n u e=1 , n=4 tacú 2n/(1+n)=16/5 vàs nguyờnl nnh tth alà s=3 • Tuynhiờnkhụngcúb mónàos asaiđ ư c1ký t màcús t mónhi uh ơn2(ki mtra) • Vych nHamminglà đi uki nc n nh ưng ch ưa đ chos tnt ic ac ab mós asai e kýt