Bài giảng Lý thuyết thông tin - Chương 2, Phần 2: Bài toán mã trường hợp kênh không bị nhiễu - Huỳnh Văn Kha

Nội dung text: Bài giảng Lý thuyết thông tin - Chương 2, Phần 2: Bài toán mã trường hợp kênh không bị nhiễu - 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.2S tnt ic ab mãti nt và gi iđ ư c
2. 2 Hu ỳnh V ăn Kha 9/30/2010 M đu • Chobi nng unhiên X cĩcácgiátr x1,x 2, ,x M. Tpcáckýt mã a1,a 2, ,a D • Chotr ư ccács nguyênd ươ ng n1,n 2, ,n M • Bàitốnđ tralà:cĩth xâyd ngb mãgi i đư csaochot mã ngv i xk cĩchi udàilà nk? • Mãti nt cĩth gi imãt ngb ư c • Trongbàitốnkênhkhơngb nhi u,mãgi i đư ccĩth quyv mãti nt • Đutiêntas xéts tnt ic ab mãti nt ,sau đĩm rngchob mãgi iđ ư c
3. 3 Hu ỳnh V ăn Kha 9/30/2010 Víd • Víd 1: M=3,D=2,n 1 =1,n 2 =2,n 3 =3
   Cĩth ch nb mã{0,10,110} • Víd 2: M=3,D=2,n 1 =n 2 =1,n 3 =2
   Khơngcĩb mãgi iđ ư cnàoth ayêuc ubài tốn(s ch ngminhsau) • Khinàocĩth xâyd ngđ ư cb mãth ayêu cu,khinàokhơng?
4. 4 Hu ỳnh V ăn Kha 9/30/2010 ðnhlý2.2 Mtb mãti nt vichi udàicáct mã n1, n2, , n M làt nt ikhivàch khi Trongđĩ D làs cáckýt mã
5. 5 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhđ nhlý2.2 • Câyb cDkíchth ư ck làm th th ngcácđi m vàđo nth ng • Midãy s đư ct othànht cáckýt trong{ 0,1, ,D– 1}cĩchi udàikhơngl nh ơn k đư cbi u di nb im tđi m Vs khácnhau • Nudãy t cĩđ ư cdothêmduynh tm tkýt vàosau s thìn i Vs và Vt bngm tđo nth ng • Cácđi m ngv idãycĩchi udài k gilàcác đi mng n cacâykíchth ư c k
6. 6 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhđ nhlý2.2 00 000 00 0 01 001 0 02 010 10 01 Câyb c 011 Câyb c2 1 11 3kích kíchth ư c3 th ư c2 100 12 10 101 20 1 110 2 21 11 22 111
7. 7 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhđ nhlý2.2 • Gi s n1 ≤n 2 ≤ ≤n M • Mit mãđ ư cđ ngnh tv im tđi mtrêncây bc D kíchth ư c nM 0 Cây ngv ib 10 mã{0,10,111} 1 11 111
8. 8 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhđ nhlý2.2 • Dob mãlàti nt nênkhiđi m P đidi ncho mtt mã,thìkhơngđi mnàotrênnhánhb t đut P đidi nchom tt mãkhác • Đi m ngv it mãchi udài nk s che đi mng nc acây • S đi mng nb tồnb b mãche≤T ngs các đi mng nc acây
9. 9 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhđ nhlý2.2 • Ng ư cl i,gi s và n1 ≤n 2 ≤ ≤n M • Ch nđi mb tkỳtrêncây ngv idãycĩchi u dài n1.Đi mnàycheđi mng n • Cịnl iítnh t1đi mng n,ch nđ ư cđi m ng vi n2.Lúcđĩ,dota ch nđ ư cđi m ngv i n3.Vàc th chođ nh t
10. 10 Hu ỳnh V ăn Kha 9/30/2010 M rngchob mãgi iđ ư c • Đi uki n đnhlý2.2cũnglàđi uki nc nvà đ chos tnt ic ab mãgi iđ ư c • Dob mãti nt làgi iđ ư cnênch cnch ng minhđ nhlýsaulàđ . Đnhlý2.3: Nub mãgi iđ ư ccĩchi udàit mãl n lư tlà n1, n 2, , n M thì:
11. 11 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhđ nhlý2.3 • Gi ωj làs t mãchi udài j và r làchi udàil n nh tc acáct mã,tacĩ: • Vim is t nhiên n chotr ư c,nhânphânph i vàrútg n,tađ ư c:
12. 12 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhđ nhlý2.3 • Trongđĩ: • Nk chínhlàt ngs mutinđ ư ct othànht n tr ngthái xi saochođo nmãc acácm utinnày đucĩchi udài k • B mãlàgi iđ ư cnênm idãykýt mãt ươ ng ngv inhi unh tm tm utin • Nk khơngv ư tquát ngs cácdãykýt mãcĩ chi udài k
13. 13 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhđ nhlý2.3 k • Nh ư vy Nk ≤ D vàtacĩ: • Lycănb c n: • Cho n ti nravơc ctađ ư cđi uc nch ngminh