Bài giảng Lý thuyết thông tin - Chương 2, Phần 4: 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 4: 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 h p kênh khơng b nhi u 2.4Xâyd ngb mãt i ưu
2. 2 Hu ỳnh V ăn Kha 9/30/2010 B đ 2.6 Gi s b mã C làt i ưutrongh cáccácb mã ti nt chophânb xácsu t p1, p 2, , p M;nĩi cáchkhác,gi s khơngb mãti nt nàocĩ chi udàit mãtrungbìnhnh hơnc a C.Khi đĩ C làt i ưutrongh cácb mãgi iđ ư c B đ 2.6chophéptathayvìtìmb mãt i ưu trongt pcácb mãgi iđ ư c,tach cntìmb mãt i ưutrongt pnh hơn,t pcácb mãti nt
3. 3 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhb đ 2.6 • Gi s tnt ib mãgi iđ ư c C’ cĩchi udàit mãtrungbìnhnh hơnc a C. Gi n’ 1,n’ 2, ,n’ M làcácđ dàit mãc a C’ • Theođ nhlý2.3 • Theođ nhlý2.2thìt nt ib mãti nt C’’ vi chi udàit mãl nl ư tlà: n’ 1,n’ 2, ,n’ M • Nh ư vycĩb mãti nt C’’ cĩchi udàit mã trungbìnhnh hơnc a C (vơlý)
4. 4 Hu ỳnh V ăn Kha 9/30/2010 B đ 2.7 • Cho C làb mãti nt nh phânv ichi udàicác t mãlà n1,n 2, ,n M. • Gi s cáctr ngtháiđ ư cs px ptheoth t gi md ntheoxácsu t(nghĩalà p1 ≥p 2 ≥ ≥ pM)vàtrongm inhĩmcĩcùngxácsu t,các tr ngtháiđ ư cx pth t tăngd ntheochi u dàit mã,nghĩalàn u pi =p i+1 = =p i+r thì ni ≤ ni+1 ≤ ≤n i+r • Nu C làt i ưutrongh cácb mãti nt thì C cĩ cáctínhch tsau:
5. 5 Hu ỳnh V ăn Kha 9/30/2010 B đ 2.7 a) Tr ngtháicĩxácsu tcaothìt mãt ươ ng ng cĩđ dàing nh ơn,nghĩalà pj >p k kéotheo nj ≤n k b) Hait mãc ahaitr ngtháicu icĩđ dàib ng nhau,nghĩalà nM1 =n M c) Trongs cáct mãcĩchi udài nM,cĩítnh t hait mãgi ngnhauhồntồn,ngo itr kýt cu icùngc achúng
6. 6 Hu ỳnh V ăn Kha 9/30/2010 Víd • Xétb mãnh phânsau X T mã x1 0 x2 100 x3 101 x4 1101 x5 1110 • B mãnàykhơngt i ưu
7. 7 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhb đ 2.7 • Ch ngminha): Nu pj >p k nh ưng nj >n k thì ch cnđ icáct mã v tríth j và k chonhau tas đư cb mã C’ cĩchi udàit mãtrungbình nh hơn.Th tv y: • Ch ngminhb): Chúýr ng nM1 ≤n M.N u nM >n M1,ch cnb đikýt cu ic at mãth M thìtađ ư cb mãti nt tth ơn
8. 8 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminhb đ 2.7 • Ch ngminhc): Gi s ng ư cl i,m ic pt mãđ dài nM đucĩítnh tm tkýt mã(khơng làkýt cu i)khácnhau.Khiđĩch cnb điký t mãcu icùngc am ttrongcáct mãđĩ,tas đư cb mã(v nlàti nt )t th ơn Chúý: Đ đơngi ntach nĩiv cáchxâyd ngb mãti nt nh phânt i ưu.Cáchxâyd ngb mã vinhi ukýt mãh ơncĩth xemtrongtàili u thamkh o
9. 9 Hu ỳnh V ăn Kha 9/30/2010 Xâyd ngb mãt i ưu(Huffman) • Spx pcác xi theoth t xácsu ttăngd n • Ghéphaitr ngthái xM1 và xM thànhm ttr ng thái,g ilà xM,M 1,v ixácsu t pM +p M1 • Gi s taxâyd ngđ ư cb mãti nt ti ưu C2 chot ptr ngtháim i • Xâyd ng C1 chot ptr ngtháibanđ unh ư sau: ▫ Cáct mãcho x1,x 2, ,x M2 vnnh ư trong C2 ▫ T mãcho xM1 và xM đư ct othànhb ngcách thêml nl ư t0,1vàot mãc a xM,M1 trong C2
10. 10 Hu ỳnh V ăn Kha 9/30/2010 Xâyd ngb mãt i ưu(Huffman) X p C1 n X p C2 n x1 p1 W1 n1 x1 p1 W1 n1 x2 p2 W2 n2 x2 p2 W2 n2 xM,M1 pM+p M1 WM,M1 nM,M1 xM2 pM2 WM2 nM2 xM1 pM1 [WM,M1 0] nM1 xM2 pM2 WM2 nM2 xM pM [WM,M1 1] nM
11. 11 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminh • Tas ch ngt C1 làb mãt i ưu • Gi s C1 khơngt i ưu.G i C1’ làb mãti nt ti ưuv icáct mã W’ 1,W’ 2, ,W’ M cĩđ dài n’ 1, n’ 2, ,n’ M • Theob đ 2.7b) n’ M1 =n’ M • Theob đ 2.7c),cĩítnh tm tc pt mãđ dài nM ch khácnhau kýt cu icùng • Khơngm ttínht ngquát,gi s W’ M1,W’ M là mtc pt mãnh ư vy(n uc nthi t,đ iv trí)
12. 12 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminh • Ghép xM,x M1 thành xM,M1 vàxâyd ngb mã C’ 2 nh ư sau • Cáct mãcho x1, ,x M2 vnnh ư trong C’ 1 • T mãcho xM,M1 chínhlà W’ M (hay W’ M1)b đi kýt cu i(g ilà U’ ) • Tas ch ngminh C’ 2 cĩchi udàit mãtrung bìnhnh hơnchi udàit mãtrungbìnhc a C2 • Vàdođĩtráiv igi thi tt i ưuc a C2
13. 13 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminh X p C’ 1 n X p C’ 2 n x1 p1 W’ 1 n’ 1 x1 p1 W’ 1 n1 x2 p2 W' 2 n’ 2 x2 p2 W’ 2 n2 xM,M1 pM+p M1 U’ n’ M1 =n’ M11 xM2 pM2 W’ M2 n’ M2 xM1 pM1 W’ M1 n’ M1 xM2 pM2 W’ M2 n’ M2 xM pM W’ M n’ M=n’ M1
14. 14 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminh • C’ 1 cĩchi udàit mãtrungbìnhnh hơn C1 • Theocáchxâyd ng C1 thì nM =n M1 dođĩ
15. 15 Hu ỳnh V ăn Kha 9/30/2010 Ch ngminh • Vy • Do nM11=n M,M1,nênv ph ichínhlàđ dàit mãtrungbìnhc a C2 vàtacĩđi uc nch ng minh
16. 16 Hu ỳnh V ăn Kha 9/30/2010 Víd x1 0.3 x1 0.3 x1 0.3 x2 0.25 x2 0.25 x2 0.25 x3 0.2 x3 0.2 x4,56 0.25 x4 0.1 x5,6 0.15 x3 0.2 x5 0.1 x4 0.1 x6 0.05 x3,456 0.45 x1,2 0.55 x1 0.3 x3,456 0.45 x2 0.25
17. 17 Hu ỳnh V ăn Kha 9/30/2010 x1,2 0 x3,456 1 x1 00 x1 00 x1 00 x3,456 1 x1 00 x2 01 x2 01 x2 01 x2 01 x4,56 10 x3 11 x3 11 x3 11 x5,6 100 x4 101 x4 101 x5 1000 x6 1001
18. 18 Hu ỳnh V ăn Kha 9/30/2010 Bàit p X Xác su t x1 0.3 x2 0.28 x3 0.15 x4 0.1 x5 0.06 x6 0.06 x7 0.05