Bài giảng Chương 2: Bài toán mã trường hợp kênh không bị nhiễu - Định lý cho bài toán mã trong

Nội dung text: Bài giảng Chương 2: Bài toán mã trường hợp kênh không bị nhiễu - Định lý cho bài toán mã trong

1. Ch ươ ng 2: Bài tốn mã tr ư ng h p kênh khơng b nhi u 2.3Đ nhlýchobàitốnmãtrong tr ư ngh pkênhkhơngb nhi u
2. 2 Hu ỳnh V ăn Kha 9/30/2010 M đu • Bi nng unhiên X cĩcáctr ngthái x1, x 2, , x M vixácxu tt ươ ng ng p1, p 2, , p M • Cáct mãcho x1, x 2, , x M là W1, W 2, , W M cĩ đ dàil nl ư tlà n1, n 2, , n M • Tpcáckýt mãlà{ a1, a 2, , a D} • Tas xâyd ngb mãđ ccti uhĩachi udàit mãtrungbình • Đutiênlàtìmch nd ư il nnh t,sauđĩtìm cáchti ng nt ich nd ư iđĩ.Vàcu icùnglà xâyd ngthu ttốnđ tìmb mãt i ưu
3. 3 Hu ỳnh V ăn Kha 9/30/2010 ðnhlý2.4 (ð nhlýchobàitốnmãtrong tr ư ngh pkênhkhơngb nhi u) Gi làchi udàit mãtrungbìnhc amtb mã gi iđ ư cb tkỳchobi nng unhiên X.Khi đĩ: Dub ngx yrakhivàch khi:
4. 4 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhđ nhlý2.4 • Đt: Thìcác qi cĩt ngb ng1.Ápd ngm nhđ 1.1
5. 5 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhđ nhlý2.4 • Dub ngtrongb tđ ngth c(*)x yrakhivàch khi: • Dob mãlàgi iđ ư cnên Vàtađ ư c • Ti ptheo,n u,thì
6. 6 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhđ nhlý2.4 • Ng ư cl i,n uthìt (*)tađ ư c Nh ưng Vy,vàt ( ),tađ ư c
7. 7 Hu ỳnh V ăn Kha 9/30/2010 B mãt i ưutuy tđ i • B mãlàmchod ub ngtrongđ nhlý2.4x yra đư cg ilàb mãt i ưutuy tđ i • Víd X Xác su t T mã x1 1/2 0 x2 1/4 10 x3 1/8 110 x4 1/8 111
8. 8 Hu ỳnh V ăn Kha 9/30/2010 B mãt i ưutuy tđ i • B mãt i ưutuy tđ iph ith amãn • Trongtr ư ngh pt ngquátch ưach cxâyd ng đư cb mãt i ưutuy tđ i,docác ni nh ư trên ch ưach clàs nguyên • Tuynhiên,tahồntồncĩth xâyd ngđ ư cb mãti nt cĩchi udàit mãtrungbìnhg n bngch nd ư i H(X) /log D nh ư kh ngđ nhc a đnhlýsau
9. 9 Hu ỳnh V ăn Kha 9/30/2010 ðnhlý2.5 Chotr ư cbi nng unhiên X,v iđ khơng ch cch nlà H(X) .Khiđĩt nt ib mã ti nt cho X,saochochi udàit mã trungbìnhth amãn
10. 10 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhđ nhlý2.5 • Ch n ni làs nguyênth amãn • Khiđĩlog pi ≥ni log D,suyra • Vytheođ nhlý2.2thìt nt ib mãti nt ng vicác ni ch nnh ư trên
11. 11 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhđ nhlý2.5 • Ti ptheo,ta ư cl ư ngchi udàit mãtrung bình.Nhânhaiv cho pi ril yt ngtheo i ta đư c • Vàtacĩk tlu nc ađ nhlý
12. 12 Hu ỳnh V ăn Kha 9/30/2010 Mãhĩatheoblock • Theođ nhlý2.5,taluơnxâyd ngđ ư cb mã ti nt cĩchi udàitrungbìnhnh hơnch nd ư i H(X) /log D cngthêm1kýt mã • Tuynhiêntacĩth làmt th ơnth nudùng ph ươ ngpháp mã hĩa theo block • Nghĩalàtakhơngmãhĩat ngtr ngthái xi ca X,màs mãhĩat ngnhĩm s cáctr ngthái • Nĩicáchkhác,tas xâyd ngb mãchovector ng unhiên Y = (X 1, X 2, , X s).Trongđĩcác Xi là đcl pvàcĩcùngphânph ixácsu tnh ư X
13. 13 Hu ỳnh V ăn Kha 9/30/2010 Mãhĩatheoblock Y=(X , X ) p T mã X p T mã 1 2 x1x1 9/16 0 x1 3/4 0 x1x2 3/16 10 x2 1/4 1 x2x1 3/16 110 x2x2 1/16 111
14. 14 Hu ỳnh V ăn Kha 9/30/2010 Mãhĩatheoblock • Tas ki mch ngr ngvi cmãhĩatheoblocks làmgi mchi udàit mãtrungbìnhchom t tr ngtháic a X • Theođ nhlý2.5,tas xâyd ngđ ư cb mãti n t cho Y vichi udàit mãtrungbìnhth a • Nh ưngdocác Xi đcl pvàcùngphânph ixác su tv i X nêntacĩ: H(Y) = H(X 1) + H(X 2) + + H(X s) = sH(X)
15. 15 Hu ỳnh V ăn Kha 9/30/2010 Mãhĩatheoblock • Nh ư vy • chínhlàs kýt mãtrungbìnhđ mãhĩa mttr ngtháic aX • T trêntath ycĩth gn H(X) /log D tùyý • Vy H(X) /log D chínhlàs kýt mãtrungbình (l ytrongb D kýt mã)c cti udùngđ mã hĩam ttr ngtháic a X
16. 16 Hu ỳnh V ăn Kha 9/30/2010 Mtýnghĩac a H(X) • Trongtr ư ngh p D=2 ,tath y H(X) chínhlàs kýt mãtrungbìnhc cti udùngđ mãhĩa1 tr ngtháic a X • Mtb mãnh phânti nt s tươ ng ngv im t dãycáccâuh i“ yes no ”dùngđ xácđ nhtr ng tháic a X • Trongđĩs câuh iđ xácđ nh xi chínhb ng chi udài ni cat mãt ươ ng ng • Vy H(X) cĩth xemlàs câuh itrungbìnhc c ti udùngđ xácđ nhtr ngtháic a X
17. 17 Hu ỳnh V ăn Kha 9/30/2010 yes x Víd 1 x1? no yes x2 X T mã x 00 yes x4 1 x1 x 01 or 2 x4? x ? x3 11 2 no yes x5 x4 100 no x 101 x 5 4 no or x3 x5?