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

1. Ch ươ ng4:Mãs asai 4.2 ngd nglýthuy tnhĩmcho mãki mtrach nl
2. 2 Hu ỳnh V ăn Kha 9/30/2010 Mãch nl • Mãch nl banđ uđ ư cxâyd ngr tđ ơngi n • Chotr ư cb mãg mcáct mã n bitnh phân. Mtbitch nl đư cthêmvàom it mãsao tngs bitm tm it mãlàch n(ho cl ) • Víd b mãbanđ ulà{00,01,10,11},thìb mã ch nl thuđ ư clà{000,011,101,110} • D dàngth yr ngm is truy nsai e bit,v i e l, đupháthi nđ ư c • Gi r1,r 2, ,r n làcácbitc am tt mã,s bit1 làch nđ ư cvi tlà r1 +r 2 + +r n =0 modulo2
3. 3 Hu ỳnh V ăn Kha 9/30/2010 ðnhnghĩa(mãch nl ) Choh ph ươ ngtrìnhtuy ntính Tpnghi mc ah trêng ilàm t b mãki mtra ch nl (hay b mãnhĩm ) Chú ý: Các aij ,r i làcács 0,1.Phépc ng,nhântheo modulo2đ ư cđ nhnghĩanh ư sau: 0+0=1+1=0;0+1=1+0=1; 1.1=1;1.0=0.1=0.0=0
4. 4 Hu ỳnh V ăn Kha 9/30/2010 Matr nch nl • Matr n A =[ aij ]g ilà matr nki mtrach nl • Nu A cĩh ng t vàcácc t j1, ,j t làđ cl ptuy n tínhthìcĩ n – t=k các rj (j≠j 1, ,j t) cĩth đư c ch ntùyý,vàtag ilàcác bitthơngtin • Cácbitth j1, ,j t gilàcác bitki mtra • Mikhichogiátr cacácbitthơngtintađ ư c mtt mãduynh t • B mãki mtrach nl cĩ 2k t mã
5. 5 Hu ỳnh V ăn Kha 9/30/2010 Víd 1 • Choh sau • Cĩth ch n r1,r 2,r 3 làmbitki mtravà r4,r 5,r 6 làmbitthơngtin • Cho r4 =0,r 5 =1,r 6 =0 .Tađ ư c r1 =1,r 3 =1,r 2 =1 .Vàt mãthuđ ư clà111010 3 • Chocácgiátr kháccho r4,r 5,r 6 tađ ư c 2 =8 t mã.Tồnb t mãđ ư cchotrongb ngsau
6. 6 Hu ỳnh V ăn Kha 9/30/2010 B mãki mtrach nl trongvd1 r1 r2 r3 r4 r5 r6 w1 0 0 0 0 0 0 w2 0 0 1 0 0 1 w3 1 1 1 0 1 0 w4 1 1 0 0 1 1 w5 1 1 0 1 0 0 w6 1 1 1 1 0 1 w7 0 1 1 1 1 0 w8 0 0 0 1 1 1
7. 7 Hu ỳnh V ăn Kha 9/30/2010 Vectorhi uch nh • Gi s dãybit r1,r 2, ,r n đư ctruy nquakênhnh phânđ ix ng,dãynh nđ ư clà r1’,r 2’, ,r n’ • Tatính T • Vàg ivectorc t c =( c1,c 2, ,c m) là vectorhi u ch nh ngv idãy v =( r1’,r 2’, ,r m’) • Dư id ngmatr nlà c = AvT • Chúý vT làkýhi uchochuy nv ca v
8. 8 Hu ỳnh V ăn Kha 9/30/2010 Musai • Gi s w =( r1,r 2, ,r n)đ ư ctruy nvàdãynh n đư clà v =( r1’,r 2’, ,r n’) • Dãy z = v – w =( r1’ – r1,r 2’ – r2, ,r n’ – rn)g i là musai ca w và v • Vectorhi uch nhc a v là c = A(zT + wT)= AzT + AwT = AzT • Nu z cĩgiátr 1t icácbitth j1,j 2, ,j e và0t i T cácbitcịnl ithìvector Az làt ngcácc tth j1, j2, ,j e ca A
9. 9 Hu ỳnh V ăn Kha 9/30/2010 Nhĩm(Group) Mtnhĩmlàm tt ph p G trênđĩcĩxácđ nh phéptống ilàphép“c ng”th amãntínhch t 1. a, b thu c G thì a+b cũngthu c G 2. (a+b)+c=a+(b+c) vim i a,b,c trong G 3. Cĩph nt 0trong G saocho a+0=0+a=a vim i a trong G 4. Vim i a trong G cĩph nt a trong G sao cho a+(a)=(a)+a=0 Nhĩm G gilàgiaohốnn u a+b=b+a ,v im i a,b trong G
10. 10 Hu ỳnh V ăn Kha 9/30/2010 Nhĩmvàmãki mtrach nl B • Gi n làt pcácdãynh phânchi udài n vi phépc nglàc ngt ngbitm ttheomod2.Thì B n làm tnhĩm • D dàngki mtrađ ư cr ngn u S làb mãki m trach nl thì S làm tnhĩm,vàg ilànhĩmcon B ca n • Th tv y,n u w1, w2 làcáct mãthì T T T A(w1 + w2) = Aw1 + Aw2 =0 • Cáctínhch tkhácđ ư csuyrat đnhnghĩa phépc ngtheomod2
11. 11 Hu ỳnh V ăn Kha 9/30/2010 ðnhlý4.4 B Cho S lànhĩmconc a n.Thì S làm tb mã ki mtrach nl ,nghĩalàt nt imatr nki mtra ch nl A saochocáct pcáct mãxácđ nhb i A là S. Nh ư vym tb mãki mtrach nl cĩth đng B nh tv im tnhĩmconc a n
12. 12 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhđ nhlý4.4 • Spcáct mãthànhmatr nMg m s hàng, n ct.Trongđĩ s làs t mã.Víd : r1 r2 r3 r4 r5 r6 w0 0 0 0 0 0 0 w1 1 0 1 0 0 1 w2 1 1 0 0 1 0 w3 0 1 0 1 0 1 w4 0 1 1 0 1 1 w5 1 1 1 1 0 0 w6 1 0 0 1 1 1 w7 0 0 1 1 1 0
13. 13 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhđ nhlý4.4 • Gi k làh ngc aMvà m=n– k.Thì k chínhlà s hàngt iđađ cl ptuy ntính,cũnglàs ct tiđađ cl ptuy ntính • Gi s k hàngđĩlà w1, w2, , wk.Thìt tc các cáct mãtrongScĩth vi td ư id ng • Ng ư cl im it mãcĩd ngtrênđ uthu cS(do Slànhĩm) • Màcác wi (i t 1đ n k)đ cl ptuy ntính.V yS cĩ 2k t mã
14. 14 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhđ nhlý4.4 • Gi s k ctcu ilàđ cl ptuy ntính.Khiđĩ m ctđ ucĩth vi td ư id ngt hptuy ntính ca k ctcu i • Hay
15. 15 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhđ nhlý4.4 • Nh ư vym it mãđ uth aA wT = 0 • Mckhác,dot pnghi mc aA wT = 0 cĩ 2k ph n t nênt pnghi mc aA wT = 0 chínhlàS • Đâylàđi uc nch ngminh
16. 16 Hu ỳnh V ăn Kha 9/30/2010 Víd • Xétvíd bêntrên,tas tìmmatr nch nl tươ ng ng • Cĩ8=2 3 t mã
    s hàngđ cl ptuy ntínht i đalà3 • Do w1, w2, w5 làh đcl ptuy ntínht iđa trongSnêntach cntìmmatr nAth achoba t mãnàylàđ • Xétmatr nQg mbat mãnàynh ư sau
17. 17 Hu ỳnh V ăn Kha 9/30/2010 Víd • Bac tcu ilàđ cl ptuy ntính,vi tbac tđ u thànht hptuy ntínhc abac tcu inh ư sau • Ctđ utiên • Suyra a1 =a 2 =a 3 =1
18. 18 Hu ỳnh V ăn Kha 9/30/2010 Víd • Tươ ngt chohaic tcịnl i • Suyra b1 =b 2 =1,b 3 =0 và c1 =c 3 =1,c 2 =0
19. 19 Hu ỳnh V ăn Kha 9/30/2010 Víd • Vành ư vy • Matr nAlà
20. 20 Hu ỳnh V ăn Kha 9/30/2010 Lpth ươ ng(coset) • Cho S lànhĩmconc anhĩm G ,thìl pth ươ ng ngv iph nt z làm tt ph pmàcácph nt canĩcĩd ng z + w,v i w nmtrong S.L p th ươ ng ngv i z kýhi ulà z + S • Víd S ={0000,0101,1110,1011},thì ▫ 0110+ S ={0110,0011,1000,1101} ▫ 1000+ S =0110+ S ▫ 1111+ S ={1111,1010,0001,0100} ▫ 0000+ S = S • Cácl pth ươ ngho cr inhauho ctrùngnhau
21. 21 Hu ỳnh V ăn Kha 9/30/2010 Bngcácl pth ươ ng w0 w1 w2 w3 0000 0101 1110 1011 0110 0011 1000 1101 1111 1010 0001 0100 0010 0111 1100 1001
22. 22 Hu ỳnh V ăn Kha 9/30/2010 B đ 4.5 Chob mãch nl S.N ucĩt mã wi vàm usai z saocho d(wi + z, wi)≤ d(wi + z, wj) vim it mã wj. Thìkhiđĩ d(w + z, w)≤ d(w+ z, w’) vim it mã w, w’ Tath yr ngm tm usaiho clà luơns ađ ư c ho clà luơnkhơngs ađ ư c
23. 23 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhb đ 4.5 • D dàngki mtrađ ư cr ng d(v1 + v3, v2 + v3)= d(v1, v2) • Dođĩ
24. 24 Hu ỳnh V ăn Kha 9/30/2010 ðnhlý4.6 Đ xâyd ngph ươ ngángi imãc cti ukho ng cách,thìtrongm il pth ươ ng,tach cnch n cácm usai z cĩs kýt 1c cti u.Khiđĩm i dãynh nđ ư ccĩd ng z + w (w làt mã)thìs đư cgi imãthành w Ch ứng minh: Tacĩ TheoB đ 4.5tacĩđi uc nch ngminh
25. 25 Hu ỳnh V ăn Kha 9/30/2010 Víd w0 w1 w2 w3 0000 0101 1110 1011 1000 1101 0110 0011 0001 0100 1111 1010 0010 0111 1100 1001
26. 26 Hu ỳnh V ăn Kha 9/30/2010 ðnhlý4.7 Ttc cácdãytrongcùngm tl pth ươ ngc ab mãnhĩm S đucĩcùngm tvectorhi uch nh Haidãytronghail pth ươ ngkhácnhaucĩcác vectorhi uch nhkhácnhau Davàohaiđ nhlý4.6và4.7tach ngminhđ ư c đnhlý4.8sau.Đ nhlý4.8chophépvi cgi imã nhanhh ơn.Đĩlàthayvìph il ưutr tồnb 2n dãy nh phân,tach cnl ưucácvectorhi uch nhvàcác musait ươ ng nglàđ
27. 27 Hu ỳnh V ăn Kha 9/30/2010 ðnhlý4.8 Vi cgi imãtheocáchlàmc cti ukho ngcáchcĩ th th chi ntheocáchsau 1. Vim idãy v nh nđ ư c,tatínhcácvector hi uch nh c tươ ng ng T 2. Trongt tc cácdãy z th a Az = c,gi s z0 cĩ s kýt 1ítnh t,tagi mã v thành v – z0
28. 28 Hu ỳnh V ăn Kha 9/30/2010 Víd Vimatr nki mtrach nl Lpb nggi imã