Bài giảng Lý thuyết thông tin - Chương 3, Phần 1: Kênh rời rạc không phụ thuộc thời gian - Huỳnh Văn Kha

Nội dung text: Bài giảng Lý thuyết thông tin - Chương 3, Phần 1: Kênh rời rạc không phụ thuộc thời gian - Huỳnh Văn Kha

1. Ch ươ ng 3: Kờnh r i r c khụng ph thu c th i gian 3.1Kờnhvàdungl ư ngkờnh
2. 2 Hu ỳnh V ăn Kha 9/30/2010 Kờnhtruy nthụng • Kờnhtruy nthụnglàthi tb ho tđ ngtrờn inputđ cungc poutput • Thụngtinchuy nquakờnhlàm tdóycỏckýt . Nucỏckýt nàythu cv mtt ph uh nthỡta gilà kờnhr ir c • Trongtr ư ngh pt ngquỏt,phõnph ixỏcsu t caoutputkhụngnh ngph thu cvàovi c inputnàođ ư ctruy nquakờnh ,màcũnph thu cvào tr ngthỏic akờnht ith iđi minput đư ctruy n
3. 3 Hu ỳnh V ăn Kha 9/30/2010 Kờnhr ir ckhụngph thu cth igian • Nuphõnph ioutputc akờnhkhụngph thu c vàotr ngthỏic akờnht ith iđi minputđ ư c truy n,thỡkờnhđ ư clà khụngph thu cth i gian .Trongch ươ ngnày kờnh cúnghĩalà kờnh rir ckhụngph thu cth igian • Cúth đctr ưng kờnhr ir ckhụngph thu c th igian bngmatr ncỏcxỏcsu tcúđi uki n, gilà matr nkờnh
4. 4 Hu ỳnh V ăn Kha 9/30/2010 Matr nkờnh • Kýhi ucỏckýt inputlà: x1,x 2, ,x M • Kýhi ucỏckýt outputlà: y1,y 2, ,y L • Đt aij =p(y j|x i) thỡmatr n[ aij ]đ ư cg ilàma tr nkờnh • Inputlàbi nng unhiờnnờnoutputcũngv y • Bi ttr ư ccỏcxỏcsu tc ainputlà: p(x 1),p(x 2), ,p(x M), thỡs bi tcỏcxỏcsu tc aoutputvà cỏcxỏcsu tđ ngth ic ainputvàoutput
5. 5 Hu ỳnh V ăn Kha 9/30/2010 Dungl ư ngkờnh • Vim tkờnhchotr ư c,bi tinput X s tớnhđ ư c H(X),H(Y),H(X,Y),H(X|Y),H(Y|X) • Tađ nhnghĩa thụngtinx lýb ikờnh làl ư ng I(X|Y)=H(X)– H(X|Y) • Chỳý: I(X|Y)=I(Y|X)=H(Y)– H(Y|X)=H(X)+H(Y)– H(X,Y) • Thụngtinx lýb ikờnhph thu cvàophõn ph ixỏcsu tc ainput. Dungl ư ngkờnh đư c đnhnghĩalà:
6. 6 Hu ỳnh V ăn Kha 9/30/2010 Mts kờnhủ cbi t 1. Mtkờnhlà lossless nu H(X|Y)=0 vim i input 2. Mtkờnhlà deterministic nu H(Y|X)=0 vi miinput 3. Mtkờnhlà noiseless nunúv alà lossless va là deterministic 4. Mtkờnhlà useless nu I(X|Y)=0 vim i input
7. 7 Hu ỳnh V ăn Kha 9/30/2010 Kờnhủ ix ng( symmetric ) • Kờnhlà đix ng num idũngc amatr nkờnh đucựngm tt pcỏccons p’ 1,p’ 2, ,p’ L vàm i ctc amatr nkờnhcũngđ ucựngm tt pcỏc cons q’ 1,q’ 2, ,q’ M • Vớd y1 y2 y3 y1 y2 y3 y4 x1 1/21/31/6 x1 1/31/31/61/6 x2 1/61/21/3 x2 1/61/61/31/3 x3 1/31/61/2
8. 8 Hu ỳnh V ăn Kha 9/30/2010 Kờnhnh phõnủ ix ng 01– β 0 β [p(y |x )]= 1– β β β j i β 1– β 1 1 1– β
9. 9 Hu ỳnh V ăn Kha 9/30/2010 Tớnhch tkờnhủ ix ng • Dot pcỏc p’ j mihàngđ unh ư nhaunờn H(Y|X=x i) khụngph thu c i vàtacú: • Vy H(Y|X) khụngph thu cphõnph ixỏcsu t inputmàch ph thu cvàocỏc p(y j|x i) cakờnh
10. 10 Hu ỳnh V ăn Kha 9/30/2010 Dungl ư ngkờnhủ ix ng I(X|Y)=H(Y)– H(Y|X) • Do H(Y|X) khụngph thu c X nờnc cđ i H(Y) s làmc cđ i I(X|Y) • H(Y) đtc cđ ilàlog L khivàch khi Y cúphõn ph iđ ngxỏcsu t • Nh nxộtr ng,n u X cúphõnph iđ ngxỏcsu t thỡ Y cũngđ ngxỏcsu t,th tv y:
11. 11 Hu ỳnh V ăn Kha 9/30/2010 Dungl ư ngkờnhủ ix ng • Nh ư vykhiinputlàđ ngxỏcsu tthỡthụngtin x lýb ikờnhđ ix nglàc cđ i • Dungl ư ngkờnhđ ix nglà: • Vớd ,kờnhnh phõnđ ix ngcúdungl ư nglà: CBSC =1– H( β,1– β)
12. 12 Hu ỳnh V ăn Kha 9/30/2010 Tớnhdungl ư ngkờnh(t ngquỏt) • Ng ư itach ngminhđ ư cr ngluụnt nt iphõn ph iinputđ I(X|Y) đtmax • Tớnhdungl ư ngkờnhtrongtr ư ngh pt ng quỏtlàbàitoỏnph ct p,vàng ư itath ư ngs dngcỏcph ươ ngphỏps đ tớnh • Davàotớnhch t I(X|Y) làhàml itheophõn ph ixỏcsu tc a X,s dngph ươ ngphỏpgi i tớchng ư itatỡmđ ư ccụngth cđ tớnhdung lư ngkờnhtrongtr ư ngh pđ cbi tnh ư sau
13. 13 Hu ỳnh V ăn Kha 9/30/2010 ðnhlý3.1 Gi s matr nkờnhΠ cakờnhr ir ckhụngph thu cth igianlàmatr nvuụngkh ngh ch. 1 Gi qij làcỏcph nt hàng i ct j camatr nΠ . Gi s rngv im i k=1,2, ,M ,tacú:
14. 14 Hu ỳnh V ăn Kha 9/30/2010 ðnhlý3.1 Thỡkhiđúdungl ư ngkờnhlà: Vàphõnph ixỏcsu tinputđ lư ngthụngtinx lýb ikờnhđ tmaxnh ư trờnlà