Bài giảng Lý thuyết thông tin - Chương 2, Phần 1: Các khái niệm căn bản - Huỳnh Văn Kha

Nội dung text: Bài giảng Lý thuyết thông tin - Chương 2, Phần 1: Các khái niệm căn bản - Huỳnh Văn Kha

1. Ch ươ ng 2: Bài tốn mã tr ư ng hp kênh khơng b nhi u 2.1Tínhgi iđ ư cc am tb mã
2. 2 Hu ỳnh V ăn Kha 9/30/2010 Gi i thi u bài tốn mã • Bi n ng u nhiên X nh n các giá tr x1,x 2, ,xM (g ilàcác tr ngthái ca X)v ixác su t tươ ng ng p1,p 2, ., pM • Dãy hu hn các giá tr ca X gi là mu tin (message ) • Tp hp {a1,a 2, ,a D}gi là tp các ký t mã (codecharacter ) • Mi xi tươ ng ngv im tdãyh uh ncáckýt mãg ilà t mã (characterword ) • Tpcáct mãg ilà b mã (code )
3. 3 Hu ỳnh V ăn Kha 9/30/2010 Gi ithi ubàitốnmã • Gi s cáct mãlàkhácnhau • Mutindobi n X sinhrađ ư cmãhĩathành mtdãycáct mã • Mctiêuc abàitốnlàc cti uhĩachi udài trungbìnhc amã • Chi udàic at mã ngv i xi là ni, i=1,2, ,M . Mctiêulàc cti uhĩa:
4. 4 Hu ỳnh V ăn Kha 9/30/2010 Mãti nt vàmãgi iđ ư c • Xétb mãnh phân x1 0 x2 010 x3 01 x4 10 • Dãy010cĩth tươ ng ngv im ttrongbam u tin: x2,x 3x1,x 1x4.Nênkhơngth gi imã • Cncĩm ts gi ih ntrêncáct mãc a1b mã
5. 5 Hu ỳnh V ăn Kha 9/30/2010 Mãti nt vàmãgi iđ ư c • B mãg ilà gi iđ ư c num idãyh uh ncác t mãđ ut ươ ng ngv inhi unh tm tm utin • Dãy A gilà ti nt cadãy B nudãy B cĩth đư cvi td ư id ng AC ,v i C làm tdãynàođĩ • B mãti nt làb mãcĩtínhch t:khơngt mã nàolàti nt cat mãkhác • B mãti nt làgi iđ ư c,nh ưngb mãgi iđ ư c ch ưach clàb mãti nt • B mãti nt cĩth đư cgi imãt ngb ư c
6. 6 Hu ỳnh V ăn Kha 9/30/2010 Mãti nt vàmãgi iđ ư c • B mãsaulàb mãti nt x1 0 x2 100 x3 101 x4 11 • B mãsaulàgi iđ ư cnh ưngkhơnglàti nt x1 0 x2 01
7. 7 Hu ỳnh V ăn Kha 9/30/2010 Gi ithu tki mtratínhgi iđ ư c • Gi S0 làt pcáct mãbanđ u • Xétt tc cácc pt mãtrong S0.N ucĩcáct mã Wi, Wj saocho Wj =W iA,choh ut A vào tp S1 • Gi s cĩt p Sn1 (n>1 ).N ucĩ W trong S0 và A trong Sn1 saocho A=WB ,cho B vào Sn.N ucĩ W’ trong So và A’ trong Sn1 saocho W’=A’B’ ,cho B’ vào Sn • Địnhlý2.1: Mtb mãlàgi iđ ư cn uvàch nukhơng tpnàotrongcáct pS 1,S 2,S 3, ch ab t kỳt mãnào
8. 8 Hu ỳnh V ăn Kha 9/30/2010 Thu ttốnki mtratínhgi iđ ư c x1 a x2 c x3 ad x4 abb x5 bad x6 deb x7 bbcde
9. 9 Hu ỳnh V ăn Kha 9/30/2010 Thu ttốnki mtratínhgi iđ ư c S0 S1 S2 S3 S4 S5 S6 S7 a d eb de b ad d eb c bb cde bcde ad • Sn rngv im i n>7 abb • ad thu c S5 nênb mãlàkhơng bad gi iđ ư c deb • abbcdebad cĩth gi imãthành bbcde x1x7x5 ho c x4x2x6x3
10. 10 Hu ỳnh V ăn Kha 9/30/2010 Tìmdãymãkhơnggi iđ ư c • Dãycáckýt mãcĩth đidi ncho2m utin đư cg ilà dãymãkhơnggi iđ ư c • Tas khơngch ngminhđ nhlý2.1nh ưngs ch racáchtìmdãymãkhơnggi iđ ư c • Gi s Sn ch at mã W.Ti nhànhng ư cl i,ta tìmđ ư cdãy: A0,W 0,A 1,W 1, ,A n,W n
11. 11 Hu ỳnh V ăn Kha 9/30/2010 Tìmdãymãkhơnggi iđ ư c • A0,W 0,W 1, ,W n làcáct mã, Ai ε Si (i=1,2, , n), W0 =A 0A1,A n =W n • Vim i i=1,2, ,n 1 thìho c Ai =W iAi+1 ho c Wi =A iAi+1 • Víd trên,tacĩ: A5 =adε S5 A4 =bε S4 A3 =deε S3 W5 =ad W4 =bad W3=deb A2 =cdeε S2 A1 =bbε S1 A0 =a W2 =c W1 =bbcde W0 =abb
12. 12 Hu ỳnh V ăn Kha 9/30/2010 Tìmdãymãkhơnggi iđ ư c • Taxâyd nghaidãy,m tdãyb tđ uv i A0W1, dãykiab tđ uv i W0 • Nu Ai =W iAi+1 ,thêm Wi+1 vàocu idãych a Wi • Nu Wi =A iAi+1 ,thêm Wi+1 vàocu idãykhơng ch a Wi • Ti pt cnh ư vyđ n Wn • Ng ư itach ngminhđ ư cr nghaidãyt o thànhnh ư trênlàm t,vàchínhlàdãymãkhơng gi iđ ư cc ntìm
13. 13 Hu ỳnh V ăn Kha 9/30/2010 Tìmdãymãkhơnggi iđ ư c • A0W1 =abbcde W0 =abb • W1 =A 1A2
    thêm W2 vào W0 • A0W1 =abbcde W0W2 =abb c • A2 =W 2A3
    thêm W3 vào W0W2 • A0W1 =abbcde W0W2W3 =abbc deb • W3 =A 3A4
    thêm W4 vào A0W1 • A0W1W4 =abbcde bad W0W2W3 =abbcdeb • W4 =A 4A5
    thêm W5 vào W0W2W3 • A0W1W4 =abbcdebad W0W2W3W5 =abbcdeb ad
14. 14 Hu ỳnh V ăn Kha 9/30/2010 • Chúý:Tathêmcác Wi vàocácdãyng nh ơn x1 abc 010 x2 abcd 0001 x3 e 0110 x4 dba 1100 x5 bace 00011 x6 ceac 00110 x7 ceab 11110 x8 eabd 101011