Giáo trình Lý thuyết thông tin - Vũ Vinh Quang

Nội dung text: Giáo trình Lý thuyết thông tin - Vũ Vinh Quang

1. ðI H C THÁI NGUYÊN KHOA CƠNG NGH THƠNG TIN Vũ Vinh Quang – Ch biên Nguy n ðình D ũng, Nguy n Hi n Trinh, D ươ ng Th Mai Th ươ ng GIÁO TRÌNH LÝ THUY T THƠNG TIN THÁI NGUYÊN – N ĂM 2010 1
2. LI M ð U Giáo trình lý thuy t thơng tin đưc biên so n d a trên các bài gi ng đã đưc gi ng d y nhi u n ăm cho đ i t ưng là sinh viên chính quy ngành Cơng ngh thơng tin t i khoa Cơng ngh thơng tin ð i h c Thái Nguyên cùng v i vi c tham kh o m t s giáo trình c a các tr ưng ð i h c khác c ũng nh ư các tài li u n ưc ngồi. ð đ c giáo trình này, ng ưi đ c c n ph i đưc trang b đy đ các ki n th c v tốn cao c p, xác su t th ng kê, lý thuy t thu t tốn và mt ngơn ng l p trình c ơ b n (C ho c Pascal). Giáo trình đưc c u trúc g m 5 ch ươ ng Ch ươ ng 1 trình bày m t s khái ni m c ơ b n v lý thuy t thơng tin nh ư cu trúc ca h th ng truy n tin, phân lo i mơi tr ưng truy n tin, v n đ r i rc hĩa các ngu n tin liên t c và các khái ni m v điu ch và gi i điu ch . Ch ươ ng 2 đư a ra các khái ni m c ơ b n v tín hi u và các c ơ ch phân tích ph cho tín hi u, khái ni m v nhi u trong quá trình truy n tin. Ch ươ ng 3 trình bày các khái ni m c ơ b n v đ đo thơng tin, l ưng tin, entropi và m i quan h gi a l ưng tin và entropi, các cơng th c xác đnh lưng tin và entropi d a trên c ơ s c a lý thuy t xác su t, khái ni m v t c đ lp tin và thơng l ưng kênh trong quá trình truy n tin. Ch ươ ng 4 gi i thi u các khái ni m chung v mã hĩa, điu ki n thi t l p, các ph ươ ng pháp bi u di n, các thu t tốn mã hĩa c ơ b n, khái ni m v mã ch ng nhi u và mã tuy n tính. Ch ươ ng 5 c a giáo trình gi i thi u v m t s h m t mã ni ti ng trên th gi i đ ng ưi đ c tham kh o. Trong quá trình so n th o giáo trình ch c ch n khơng tránh kh i nh ng thi u xĩt v n i dung c ũng nh ư hình th c, nhĩm biên so n trân tr ng c m ơn nh ng ý ki n quý báu c a các b n đ c đ giáo trình đưc hồn thi n h ơn. Thái Nguyên, tháng 01 n ăm 2010 Thay mt nhĩm biên so n V ũ Vinh Quang 2
3. CH ƯƠ NG 1. NH NG KHÁI NI M C Ơ B N 1.1 Gi i thi u v lý thuy t thơng tin Trong th gi i ngày nay, chúng ta hàng ngày ph i ti p xúc v i r t nhi u các h th ng chuy n t i thơng tin khác nhau nh ư: Các h th ng truy n hình phát thanh, h th ng đin tho i c đ nh và di đng, h th ng mng LAN, Internet, các h th ng này đu v i m c đích là chuy n thơng tin t n ơi phát đn n ơi thu v i nh ng m c đích khác nhau. ð nghiên c u v các h th ng này, chúng ta c n ph i nghiên c u v b n ch t thơng tin, b n ch t c a quá trình truy n tin theo quan đim tốn h c, c u trúc v t lý c a mơi tr ưng truy n tin và các v n đ liên quan đn tính ch t b o m t, t i ưu hĩa quá trình. Khái ni m đ u tiên c n nghiên c u là thơng tin: thơng tin đưc hi u là tp h p các tri th c mà con ng ưi thu đưc qua các con đưng ti p nh n khác nhau, thơng tin đưc mang d ưi d ng n ăng l ưng khác nhau g i là v t mang, vt mang cĩ ch a thơng tin g i là tín hi u. Lý thuy t v n ăng l ưng gi i quy t t t v n đ xây d ng m ch, tín hi u. Nh ưng v n đ v t c đ , hi n t ưng nhi u, mi liên h gi a các d ng n ăng lưng khác nhau c a thơng tin ch ưa gi i quy t đưc mà ph i c n cĩ m t lý thuy t khác đĩ là lý thuy t thơng tin. Lý thuy t thơng tin là lý thuy t nh m gi i quy t v n đ c ơ b n c a quá trình truy n tin nh ư v n đ v r i r c hĩa ngu n, mơ hình phân ph i xác su t ca ngu n và đích, các v n đ v mã hĩa và gi i mã, kh n ăng ch ng nhi u ca h th ng Cn chú ý r ng lý thuy t thơng tin khơng đi sâu vào vi c phân tích các cu trúc v t lý c a h th ng truy n tin mà ch y u nghiên c u v các mơ hình tốn h c mơ t quá trình truy n tin trên quan đim c a lý thuy t xác su t th ng kê, đng th i nghiên c u v các nguyên t c và các thu t tốn mã hĩa c ơ b n, các nguyên t c mã ch ng nhiu 1.2 H th ng truy n tin Trong th c t , chúng ta g p r t nhi u các h th ng đ truy n thơng tin t đim này t i đim khác, trong th c t nh ng h th ng truy n tin c th mà con 3
4. ng ưi đã s d ng và khai thác cĩ r t nhi u d ng, khi phân lo i chúng ng ưi ta cĩ th d a trên nhi u c ơ s khác nhau. 1.2.1 Các quan đim đ phân lo i các h th ng truy n tin • Theo n ăng l ưng - Năng l ưng m t chi u ( đin tín) - Vơ tuy n đin (sĩng đin t ) - Quang n ăng (cáp quang) - Sĩng siêu âm (la-de) • Theo bi u hi n bên ngồi - H th ng truy n s li u - H th ng truy n hình phát thanh - H th ng thơng tin tho i • Theo d ng tín hi u - H th ng truy n tin r i r c - H th ng truy n tin liên t c Xu t phát t các quan đim đĩ, trong th c t trong nhi u l ĩnh v c đ c bi t là l ĩnh v c truy n thơng t n t i các khái ni m nh ư: H phát thanh truy n hình, h truy n tín hi u s , 1.2.2 S ơ đ truy n tin và m t s khái ni m trong h th ng truy n tin ðnh ngh ĩa: Truy n tin (transmission) : Là quá trình d ch chuy n thơng tin t đim này sang đim khác trong m t mơi tr ưng xác đ nh. Hai đim này s đưc g i là đim ngu n tin (information source) và đim nh n tin (information destination). Mơi tr ưng truy n tin cịn đưc g i là kênh tin (chanel). Sơ đ kh i ch c n ăng c a m t h th ng truy n tin t ng quát g m cĩ 3 thành ph n chính: Ngu n tin, kênh tin và nh n tin. NGU ỒN TIN KÊNH TIN NH ẬN TIN Trong đĩ: 4
5. • Ngu n tin: là n ơi s n sinh ra hay ch a các tin c n truy n đi, hay ngu n tin là t p h p các tin mà h th ng truy n tin dùng đ t o các b n tin khác nhau đ truy n tin. • Kênh tin: là mơi tr ưng lan truy n thơng tin. ð cĩ th lan truy n đưc thơng tin trong m t mơi tr ưng v t lý xác đnh, thơng tin ph i đưc chuy n thành tín hi u thích h p v i mơi tr ưng truy n lan. Nh ư v y ta cĩ th đ nh ngh ĩa kênh tin: Kênh tin là n ơi hình thành và truy n tín hi u mang tin đ ng th i đ y sinh ra các t p nhi u phá hu thơng tin. Trong lý thuy t truy n tin, kênh là m t khái ni m trìu t ưng đ i di n cho s h n h p gi a tín hi u và t p nhi u. T khái ni m này, s phân lo i kênh s d dàng h ơn, m c dù trong th c t các kênh tin cĩ r t nhi u d ng khác nhau. Ví d : - Truy n tin theo dây song hành, cáp đng tr c. - Tín hi u truy n lan qua các t ng đin ly. - Tín hi u truy n lan qua các t ng đ i l ưu. - Tín hi u truy n lan trên m t đ t, trong đ t. - Tín hi u truy n lan trong n ưc • Nh n tin : Là c ơ c u khơi ph c thơng tin ban đu t tín hi u thu đưc t đ u ra c a kênh ð tìm hi u chi ti t h ơn ta đi sâu vào các kh i ch c n ăng c a s ơ đ truy n tin và xét đn nhi m v c a t ng kh i. 1.3 Ngu n tin nguyên thu 1.3.1 Khái ni m chung ðnh ngh ĩa: Ngu n tin nguyên thu là t p h p nh ng tin ban đu mà h th ng thu nh n đưc ch ưa qua m t phép bi n đ i nhân t o nào. V m t tốn h c, các tin nguyên thu là nh ng hàm liên t c theo th i gian f (t) ho c là nh ng hàm bi n đi theo th i gian và m t s thơng s khác nh ư hình nh đen tr ng h(x, y,t) trong đĩ x, y là các to đ khơng gian, hoc nh ư các thơng tin khí t ưng g(λi ,t) trong đĩ λi là các thơng s khí t ưng nh ư nhi t đ , đ m, t c đ giĩ, 5
6. Thơng tin nguyên thu c ũng cĩ th là các h hàm theo th i gian và các thơng s nh ư tr ưng h p thơng tin hình nh màu:  f(, xyz , )  Kxyz(,,)=  gxyz (,,).  h(, x y , z ) Các tin nguyên thu ph n l n là hàm liên t c ca th i gian trong m t ng ưng ngh ĩa là cĩ th bi u di n m t thơng tin nào đĩ d ưi d ng m t hàm S( t ) t n t i trong quãng th i gian T và l y các giá tr b t k ỳ trong ph m vi ( S min , S max ) trong đĩ Smin, S max là ng ưng nh nh t và l n nh t mà h th ng cĩ th thu nh n đưc. Smax Smin Tin nguyên thu cĩ th tr c ti p đưa vào h th ng truy n tin nh ưng c n ph i qua các phép bi n đ i sao cho phù h p v i h th ng t ươ ng ng. Nh ư v y xét v quan đim truy n tin thì cĩ hai lo i tin và hai lo i h th ng t ươ ng ng: • Tin r i r c ng v i - Ngu n r i r c - Kênh r i r c • Tin liên t c ng v i - Ngu n liên t c - Kênh liên t c S phân bi t v b n ch t c a ngu n r i r c v i ngu n liên t c đưc hi u là s l ưng các tin trong ngu n r i r c là h u h n và s l ưng các tin trong ngu n liên t c là khơng đm đưc. 6
7. Nĩi chung các tin r i r c, ho c nguyên thu r i r c, ho c nguyên thu liên t c đã đưc r i r c hố tr ưc khi đư a vào kênh thơng th ưng đ u qua thi t b mã hố. Thi t b mã hố bi n đ i t p tin nguyên thu thành t p h p nh ng tin thích h p v i đc đim c ơ b n c a kênh nh ư kh n ăng cho qua (thơng lưng), tính ch t tín hi u và t p nhi u. 1.3.2 Bn ch t c a thơng tin theo quan đim truy n tin Ch cĩ quá trình ng u nhiên m i t o ra thơng tin. M t hàm g i là ng u nhiên n u v i m t giá tr b t kì c a đ i s , giá tr c a hàm là m t đ i l ưng ng u nhiên (các đi l ưng v t lí trong thiên nhiên nh ư nhi t đ mơi tr ưng, áp su t khơng khí là hàm ng u nhiên c a th i gian). Mt quá trình ng u nhiên đưc quan sát b ng m t t p các giá tr ng u nhiên. Quá trình ng u nhiên đưc coi là bi t rõ khi thu nh n và x lí đưc m t tp đ nhi u các giá tr đ c tr ưng c a nĩ. Gi s quá trình ng u nhiên X(t) cĩ m t t p các giá tr m u (hay cịn đưc g i là các bi n) x( t ) , khi đĩ ta bi u di n quá trình ng u nhiên b i: Xt()= xt () { }x∈ X Ví d : Quan sát th i gian vào m ng c a các sinh viên trong 1 ngày, ng ưi ta ti n hành ph ng v n 10 sinh viên, g i X là th i gian vào m ng, xk là th i gian vào m ng c a sinh viên th k, ( k = 1,2, ,10) ta thu đưc m u nh ư sau: X = {10, 50, 20,150,180, 30, 30, 5, 60, 0 } đơ n v tính (phút) Vi c đốn tr ưc m t giá tr ng u nhiên là khĩ kh ăn. Ta ch cĩ th tìm đưc quy lu t phân b c a các bi n thơng qua vi c áp d ng các qui lu t c a tốn th ng kê đ x lý các giá tr c a các bi n ng u nhiên mà ta thu đưc t các tín hi u. Quá trình ng u nhiên cĩ th là các hàm trong khơng gian 1 chi u, khi đĩ ta cĩ quy lu t phân ph i xác su t 1 chi u và hàm m t đ phân ph i xác su t đưc xác đ nh b i các cơng th c dF( x ) Fx()= pX ( < x ); wx () = dx 7
8. Trong đĩ: • x là bi n ng u nhiên • p(x) xác su t xu t hi n X= x trong quá trình ng u nhiên, th ưng đưc vi t là px()= pX ( = x ) . Nu quá trình ng u nhiên là các hàm trong khơng gian 2 chi u khi đĩ quy lu t ng u nhiên đưc bi u hi n b i các cơng th c ∂2 F Fxy(,)=<< pX ( xY ; yw ); (,) xy = . xy ∂x ∂ y Tươ ng t , ta c ũng cĩ các quy lu t phân ph i xác su t trong khơng gian nhi u chi u. Các đc tr ưng quan tr ng c a bi n ng u nhiên 1. Tr trung bình (kì v ng tốn h c) c a m t quá trình ng u nhiên X( t ) +∞ EX()= Xt () = ∫ xtwxdx ()() −∞ 2. Tr trung bình bình ph ươ ng +∞ EX2()= Xt 2 () = ∫ xtwxdx 2 ()() −∞ 3. Ph ươ ng sai +∞ 2 2 DX()=−() X X =∫ () xt ()()() − Ex wxdx −∞ 4. Hàm t ươ ng quan Mơ t m i quan h th ng kê gi a các giá tr c a 1 quá trình ng u nhiên các th i đim t 1, t 2 +∞ +∞ Bttx (,)12= EXt() (),() 1 Xt 2 = ∫ ∫ xxwxt 12 ((),()) 1212 xt dxdx −∞ −∞ Nu hai quá trình X, Y khác nhau hai th i đim khác nhau, khi đĩ +∞ +∞ Bxy (,) tt12= EXt() (),() 12 Yt = ∫ ∫ xywxt ((),()) 12 yt dxdy −∞ −∞ 8
9. ð gi i quy t bài tốn m t cách th c t , ng ưi ta khơng th xác đ nh t c th i mà th ưng l y tr trung bình c a quá trình ng u nhiên. Cĩ hai lo i tr trung bình theo t p h p và tr trung bình theo th i gian. Ta c n nghiên c u tr trung bình theo t p h p, tuy v y s g p nhi u khĩ kh ăn khi ti p nh n và x lý tc th i các bi n ng u nhiên vì các bi n ng u nhiên luơn bi n đ i theo th i gian. ð tính tr trung bình theo th i gian, ta ch n th i gian đ ln đ quan sát các bi n ng u nhiên d ràng h ơn vì cĩ điu ki n quan sát và s d ng các cơng th c th ng kê, khi đĩ vi c tính các giá tr trung bình theo th i gian đưc xác đnh b i các cơng th c: 1 T Xt()= Lim xtdt () T →+∞ ∫ T 0 Tr trung bình bình ph ươ ng: 1 T X2() t= Lim x 2 () tdt T →+∞ ∫ T 0 Khi th i gian quan sát T d n đ n vơ cùng thì tr trung bình t p h p b ng tr trung bình th i gian. Trong th c t ta th ưng ch n th i gian quan sát đ ln ch khơng ph i vơ cùng như v y v n tho mãn các điu ki n c n nh ưng đơ n gi n h ơn, khi đĩ ta cĩ tr trung bình theo t p h p b ng tr trung bình theo th i gian. Ta cĩ: +∞ 1 T Xt()= xtwxdx ()() = Lim xtdt () ∫T →+∞ ∫ −∞ T 0 Tươ ng t : +∞ 1 T X2() t= xtwxdx 2 ()() = Lim xtdt 2 () ∫T →+∞ ∫ −∞ T 0 Tr ưng h p này g i chung là quá trình ng u nhiên d ng theo hai ngh ĩa: • Theo ngh ĩa h p: Tr trung bình ch ph thu c kho ng th i gian quan sát τ =t2 − t 1 mà khơng ph thu c g c th i gian quan sát. 9
10. • Theo ngh ĩa r ng: G i là quá trình ng u nhiên d ng khi tr trung bình là mt h ng s và hàm t ươ ng quan ch ph thu c vào hi u hai th i gian quan sát τ =t2 − t 1 . Khi đĩ ta cĩ m i t ươ ng quan Bttx (,)12==−= B (τ tt 21 ) B () τ = XtXt ().( + τ ) +∞ +∞ 1 T =xxwxx12(,) 12 dxdx 12 = Lim xtxt ()() + τ dt ∫ ∫T →+∞ ∫ −∞ −∞ T −∞ Tĩm l i: ð nghiên c u đ nh l ưng ngu n tin, h th ng truy n tin mơ hình hố ngu n tin b ng 4 quá trình sau: 1. Quá trình ng u nhiên liên t c: Ngu n ti ng nĩi, âm nh c, hình nh là tiêu bi u cho quá trình này. 2. Quá trình ng u nhiên r i r c: là quá trình ng u nhiên liên t c sau khi đưc ri r c hĩa theo m c tr thành quá trình ng u nhiên r i r c. 3. Dãy ng u nhiên liên t c: ðây là tr ưng h p m t ngu n liên t c đã đưc gián đon hĩa theo th i gian, nh ư th ưng g p trong các h th ng tin xung nh ư: điu biên xung, điu t n xung khơng b l ưng t hĩa. 4. Dãy ng u nhiên r i r c: Ngun liên t c đưc gián đon theo th i gian ho c trong h th ng thơng tin cĩ xung l ưng t hố. 1.4 H th ng kênh tin 1.4.1 Khái ni m Nh ư chúng ta đã bi t: v t ch t ch cĩ th d ch chuy n t đim này đn mt đim khác trong m t mơi tr ưng thích h p và d ưi tác đng c a m t l c thích h p. Trong quá trình d ch chuy n c a m t dịng v t ch t, nh ng thơng tin v nĩ hay ch a trong nĩ s đưc d ch chuy n theo. ðây chính là b n ch t c a s lan truy n thơng tin. Vy cĩ th nĩi r ng vi c truy n tin chính là s d ch chuy n c a dịng các ht v t ch t mang tin (tín hi u) trong mơi tr ưng . Trong quá trình truy n tin, h th ng truy n tin ph i g n đưc thơng tin lên các dịng v t ch t t o thành tín hi u và lan truy n đi. Vi c tín hi u lan truy n trong m t mơi tr ưng xác đ nh chính là dịng các ht v t ch t ch u tác đ ng c a l c, lan truy n trong m t c u trúc xác đ nh c a 10
11. mơi tr ưng. Dịng v t ch t mang tin này ngồi tác đng đ d ch chuy n, cịn ch u tác đ ng c a các l c khơng mong mu n trong c ũng nh ư ngồi mơi tr ưng. ðây c ũng chính là nguyên nhân làm bi n đ i dịng v t ch t khơng mong mu n hay là nguyên nhân gây ra nhi u trong quá trình truy n tin. Nh ư v y: Kênh tin là mơi tr ưng hình thành và truy n lan tín hi u mang tin đng th i đĩ sinh ra các t p nhi u phá h y thơng tin. 1.4.2 Phân lo i mơi tr ưng truy n tin Kênh tin là mơi tr ưng hình thành và truy n lan tín hi u mang tin. ð mơ t v kênh chúng ta ph i xác đ nh đưc nh ng đ c đim chung, c ơ b n đ cĩ th t ng quát hố v kênh. Khi tín hi u đi qua mơi tr ưng do tác đ ng c a t p nhi u trong mơi tr ưng s làm bi n đ i n ăng l ưng, d ng c a tín hi u. M i mơi tr ưng cĩ m t dng t p nhi u khác nhau. V y ta cĩ th l y s phân tích, phân lo i t p nhi u đ phân tích, phân lo i cho mơi tr ưng (kênh) • Mơi tr ưng trong đĩ tác đ ng nhi u c ng là ch y u N c(t): Nhi u c ng là nhi u sinh ra m t tín hi u ng u nhiên khơng mong mu n và tác đng c ng thêm vào tín hi u đ u ra. Nhi u c ng là do các ngu n nhi u cơng nghi p sinh ra, luơn luơn t n t i trong các mơi tr ưng truy n lan tín hi u. • Mơi tr ưng trong đĩ tác đ ng nhi u nhân là ch y u N n(t): Nhi u nhân là nhi u cĩ tác đ ng nhân vào tín hi u, nhi u này gây ra do ph ươ ng th c truy n lan c a tín hi u, hay là s thay đ i thơng s v t lý c a b ph n mơi tr ưng truy n lan khi tín hi u đi qua. Nĩ làm nhanh, ch m tín hi u (th ưng sĩng ng n) làm tăng gi m biên đ tín hi u. • Mơi tr ưng g m c nhi u c ng và nhi u nhân 1.4.3 Mơ t s truy n tin qua kênh: Xét h th ng truy n tin trong đĩ SV (t) là thơng tin truy n, SR (t) là thơng tin thu SV ( t ) Kênh tin SR ( t ) Ta cĩ bi u th c mơ t nhi u trong tr ưng h p t ng quát 11
12. StR()= NtSt nV () () + Nt c () Trong th c t , ngồi các nhi u c ng và nhi u nhân, tín hi u c ũng ch u tác đng c a h s đ c tính xung c a kênh H( t ) do đĩ: StR()= NtHtSt n (). (). V () + Nt c () ðc tính kênh khơng lý t ưng này s gây ra m t s bi n d ng c a tín hi u ra so v i tín hi u vào g i là méo tín hi u và là m t ngu n nhi u trong quá trình truy n tin. Tín hi u vào c a kênh truy n hi n nay là nh ng dao đ ng cao t n v i nh ng thơng s bi n đ i theo quy lu t c a thơng tin. Các thơng s cĩ th là biên đ, t n s ho c gĩc pha, dao đ ng cĩ th liên t c ho c gián đon, n u là gián đon s cĩ nh ng dãy xung cao t n v i các thơng s xung thay đi theo thơng tin nh ư biên đ xung, t n s l p l i, th i đim xu t hi n. Trong tr ưng hp dao đ ng liên t c, bi u th c t ng quát c a tín hi u cĩ d ng sau: StatV ()= ()cos(ω t + β ()) t trong đĩ a( t ) là biên đ, ω : t n s gĩc, β (t ) : gĩc pha, các thơng s này bi n đ i theo quy lu t c a thơng tin đ mang tin và nhi u tác đ ng s làm thay đi các thơng s này làm sai l ch thơng tin trong quá trình truy n. Theo mơ hình m ng c a kênh tin, kí hi u p( y / x ) là xác su t nh n đưc tin y( t ) khi đã phát đi tin x( t ) , n u đ u vào ta đư a vào tin x( t ) v i xác su t xu t hi n là p( x ) ta nh n đưc đ u ra m t tin y( t ) v i xác su t xu t hi n p( y ) ng v i x( t ) . V i yêu c u truy n tin chính xác, ta c n ph i đm b o y( t ) ph i là tin nh n đưc t x( t ) t c là p( y / x )= 1 . ðiu này ch cĩ đưc khi kênh khơng cĩ nhi u. Khi kênh cĩ nhi u, cĩ th trên đu ra ca kênh chúng ta nh n đưc m t tin khác v i tin đưc phát, cĩ ngh ĩa là p( y / x )< 1 và n u nhi u càng l n thì xác su t này càng nh . Nh ư v y v mt tốn h c, chúng ta cĩ th s d ng xác su t p( y / x ) là m t tham s đ c tr ưng cho đc tính truy n tin c a kênh. 1.5 H th ng nh n tin 12
13. Nh n tin là đu cu i c a h th ng truy n tin. Nh n tin th ưng g m cĩ b nh n bi t thơng tin và x lý thơng tin. N u b ph n x lý thơng tin là thi t b t đ ng ta cĩ m t h th ng truy n tin t đ ng. Vì tín hi u nh n đưc đ u ra c a kênh là m t h n h p tín hi u và t p nhi u x y ra trong kênh, nên nĩi chung tín hi u ra khơng gi ng v i tín hi u đư a vào kênh. Nhi m v chính c n th c hi n t i nh n tin là t tín hi u nh n đưc y( t ) ph i xác đ nh đưc x( t ) nào đưc đưa vào đ u vào c a kênh. Bài tốn này đưc g i là bài tốn thu hay ph c h i tín hi u t i đim thu. 1.6 Mt s v n đ c ơ b n c a h th ng truy n tin Các v n đ lý thuy t thơng tin c n gi i quy t trong quá trình truy n tin là: hi u su t, đ chính xác c a quá trình truy n tin trong đĩ. 1.6.1 Hi u su t ( t c đ lp tin) Là l ưng thơng tin ngu n l p đưc trong m t đơ n v th i gian v i đ sai sĩt cho phép. 1.6.2 ð chính xác (hay kh n ăng ch ng nhi u c a h th ng) Là kh n ăng gi m t i đa sai nh m thơng tin trên đưng truy n, yêu c u ti đa v i b t k ỳ m t h th ng truy n tin nào là th c hi n đưc s truy n tin nhanh chĩng và chính xác. Nh ng khái ni m v lý thuy t thơng tin cho bi t gi i h n t c đ truy n tin trong m t kênh tin, ngh ĩa là kh i l ưng thơng tin l n nh t mà kênh cho truy n qua v i m t đ sai nh m nh tùy ý. Trong nhi u tr ưng h p ngu n tin nguyên th y là liên t c nh ưng dùng kênh r i r c đ truy n tin. V y ngu n tin liên t c tr ưc khi mã hĩa ph i đưc ri r c hĩa. ð xác minh phép bi n đ i ngu n liên t c thành ngu n r i r c là mt phép bi n đ i t ươ ng đươ ng 1–1 v m t thơng tin, tr ưc h t ta kh o sát c ơ s lý thuy t c a phép r i r c hĩa g m các đ nh lý l y m u và quy lu t l ưng t hĩa. 1.7 Ri r c hĩa m t ngu n tin liên t c Trong các h th ng truy n tin mà thi t b đ u và cu i là nh ng thi t b x lý thơng tin r i r c nh ư các h th ng truy n s li u thì khơng cho phép truy n tr c ti p tin liên t c. Do v y n u các ngu n tin là liên t c, nh t thi t tr ưc khi đư a tin vào kênh ph i thơng qua m t phép bi n đ i liên t c thành r i r c. Sau đĩ s áp d ng các ph ươ ng pháp mã hĩa đ đáp ng đưc các ch tiêu k thu t ca h th ng truy n tin c th . 13
14. Phép bi n đ i ngu n tin liên t c thành r i r c g m hai quá trình c ơ b n: • Quá trình r i r c hĩa theo th i gian hay là khâu l y m u. • Quá trình l ưng t hĩa. Cơ s lý thuy t c a phép bi n đ i này g m các đ nh lý l y m u và lu t lưng t hĩa nh ư sau. 1.7.1 Quá trình l y m u Gi s ngu n tin liên t c d ng tín hi u đưc bi u di n b ng hàm tin ph thu c th i gian St( )= at ( )cos(ω t + β ) Vi c l y m u m t hàm tin cĩ ngh ĩa là trích t hàm đĩ ra các m u t i nh ng th i đim nh t đ nh. Nĩi m t cách khác là thay hàm tin liên t c b ng mt hàm r i r c là nh ng m u c a hàm trên l y t i nh ng th i đim gián đ an. Vn đ đ t ra đây là xét các điu ki n đ cho s thay th đĩ là m t s thay th t ươ ng đươ ng. T ươ ng đươ ng đây là v ý ngh ĩa thơng tin, ngh ĩa là hàm thay th khơng b m t mát thơng tin so v i hàm đưc thay th . Vi c l y m u cĩ th th c hi n b ng m t r ơ le đin, đin t b t kì đĩng m d ưi tác đng c a đin áp u( t ) nào đĩ. Th i gian đĩng m ch c a r ơ le là 1 th i gian ly m u τ , chu k ỳ l y m u là T , t n su t l y m u là f = . T T S( t ) liên t c, ta thu đưc S*( t ) theo ngh ĩa r i r c (Hình 1.1) u(t) T τ S(t) S *(t) Hình 1.1 14
15. Trong k thu t, vi c l y m u ph i th a mãn m t s điu ki n c a đ nh lý ly m u trong khơng gian th i gian cho quá trình ng u nhiên cĩ b ăng t n h n ch . Sau đây chúng ta xét mt s khái ni m • Bi n đ i Fourier: hàm S( t ) đưc g i là cĩ bi n đ i Fourier là S( f ) +∞ nu: Sf()= ∫ Ste () − j2π f t dt −∞ +∞ • Gi s cĩ tín hi u liên t c St()= ∫ Sfe () − j2π f t df cĩ bi n đ i −∞ Fourier là S( f ) đưc g i là cĩ b ăng t n h n ch n u S( f )= 0 v i f> f max , trong đĩ fmax là t n s cao nh t c a tín hi u S( t ) . M t tín hi u nh ư th đưc bi u di n m t cách duy nh t b i nh ng m u c a S( t ) v i t n s ly m u là fS v i fS ≥ 2 f max . Ta th y ngồi mi n t n s (− fmax, f max ) năng l ưng coi nh ư b ng 0 nên: + fmax St()= ∫ Sfe () − j2π f t df − fmax • Tín hi u cĩ b ăng t n h n ch đưc l y m u v i t n s l y m u là fS = 2 f max cĩ th khơi ph c l i t các m u c a nĩ theo cơng th c n i suy sau: n   sin 2 π f t −   n=+∞ max n  2 fmax   S( t ) = ∑ S   n=−∞ 2 fmax  n  2π fmax  t −  2 fmax  n   n trong đĩ: S    là các m u c a S( t ) l y t i t = v i 2 fmax   2 fmax n = ,0 ± ,1 ± 2, 15
16. Nh ư v y n u th i gian l y m u đ dài và s m u đ l n thì n ăng l ưng ca tín hi u l y m u t ươ ng đươ ng v i n ăng l ưng c a tín hi u g c. Các k t qu trên đưc phát bi u b i đ nh lý sau đây: ðnh lý l y m u Shanon : Hàm S( t ) trong kho ng (− fmax, f max ) hồn tồn đưc xác đ nh b ng cách l y m u v i t n s l y m u fS = 2 f max . 1.7.2 Khâu l ưng t hố Gi thi t hàm tin S( t ) bi n thiên liên t c v i biên đ c a nĩ thay đ i trong kho ng (Smin, S max ) . Ta chia kho ng (Smin, S max ) thành n kho ng: Smin= SSS 0 << 1 2 << SSn = max Nh ư v y hàm tin liên t c S( t ) qua ph ươ ng pháp r i r c s bi n đ i thành S' ( t ) cĩ d ng bi n đ i b c thang g i là hàm l ưng t hố v i m i m c lưng t ∆=iS i+1 − Si i , ( = 0 n − 1). S l a ch n các m c ∆i thích h p s gi m s sai khác gi a S( t ) và S' ( t ) . S(t) S’(t) ∆i Hình 1.2 Phép bi n đ i S( t ) thành S'( t ) đưc g i là phép l ưng t hố. ∆i ,(i = 0, , n − 1) g i là m c l ưng t hố. S− S Nu ∆=max min , ∀=i 0, , n − 1 , ta cĩ qui lu t l ưng t hố đ u i n ng ưc l i ta g i là l ưng t hĩa khơng đ ng đ u. Do s bi n thiên S( t ) trong th c t th ưng là khơng đu nên ng ưi ta th ưng dùng qui lu t l ưng t khơng 16
17. đu. Vi c chia l ưi l ưng t khơng đu này ph thu c vào m t đ xác su t các giá tr t c th i c a S( t ) . Ta th ưng ch n ∆i sao cho các giá tr t c th i c a S( t ) trong ph m vi ∆i là h ng s . V m t th ng kê, phép l ưng t hĩa chính là vi c t o m u phân kho ng v i đ dài kho ng là ∆i và ng v i m i kho ng xác đnh t n s xu t hi n c a tín hi u trong kho ng, khi đĩ ta nh n đưc b ng phân kho ng c a tín hi u t ươ ng ng sau khi đã r i r c hĩa. Tĩm l i: Vi c bi n m t ngu n liên t c thành m t ngu n r i r c c n hai phép bi n đ i: l y m u và l ưng t hố. Th t th c hi n hai phép bi n đ i này ph thu c vào điu ki n c th c a h th ng: • Lưng t hố sau đĩ l y m u. • Ly m u sau đĩ l ưng t hố. • Th c hi n đ ng th i hai phép bi n đ i trên. 1.8 ðiu ch và gi i điu ch 1.8.1 ðiu ch Trong các h th ng truy n tin liên t c, các tin hình thành t ngu n tin liên t c đưc bi n đ i thành các đi l ưng đin (áp, dịng) và chuy n vào kênh. Khi mu n chuy n các tin y qua m t c ly ln, ph i cho qua m t phép bi n đ i khác g i là điu ch . ðnh ngh ĩa: ðiu ch là phép bi n đ i nh m chuy n thơng tin ban đ u thành mt d ng n ăng l ưng thích h p v i mơi tr ưng truy n lan sao cho n ăng l ưng ít b t n hao, ít b nhi u trên đưng truy n tin. Các ph ươ ng pháp điu ch : Các ph ươ ng pháp điu ch cao t n th ưng dùng v i tín hi u liên t c • ðiu ch biên đ AM (Amplitude Modulation) • ðiu ch đơn biên SSB (Single Side Bande) • ðiu t n FM (Frequency Modulation) • ðiu pha PM (Phase Modulation) Vi tín hi u r i r c, các ph ươ ng pháp điu ch cao t n c ũng gi ng nh ư tr ưng hp thơng tin liên t c, nh ưng làm vi c gián đon theo th i gian g i là manip hay khĩa d ch. G m các ph ươ ng pháp sau. • Manip biên đ ASK (Amplitude Shift Key) 17
18. • Manip t n s FSK (Frequency Shift Key) • Manip pha PSK (Phase Shift Key) 1.8.2 Gi i điu ch ðnh ngh ĩa: Gi i điu ch là nhi m v thu nh n, l c, tách thơng tin nh n đưc dưi d ng m t đin áp liên t c hay m t dãy xung đin r i r c gi ng nh ư đu vào v i m t sai s cho phép. Các ph ươ ng pháp gi i điu ch V ph ươ ng pháp gi i điu ch nĩi cách khác là phép l c tin, tùy theo h n hp tín hi u nhi u và các ch tiêu t i ưu v sai s ( đ chính xác) ph i đ t đưc mà chúng ta cĩ các ph ươ ng pháp l c tin thơng th ưng nh ư: • Tách sĩng biên đ, • Tách sĩng t n s • Tách sĩng pha 18
19. CH ƯƠ NG 2. TÍN HI U 2.1 Mt s khái ni m c ơ b n Tín hi u là các thơng tin mà con ng ưi thu nh n đưc t mơi tr ưng bên ngồi thơng qua các giác quan hay các h th ng đo l ưng. Ví d nh ư: Sĩng đa ch n, nh p tim c a b nh nhân, l ưu l ưng c a các dịng ch y hay âm thanh, sĩng đin t , tín hi u s , . V m t tốn h c, tín hi u đưc hi u nh ư m t hàm s ph thu c vào th i gian S( t ) . Sau đây chúng ta s nghiên c u các d ng tín hi u c ơ b n. 2.1.1 Tín hi u duy trì Th hi n s duy trì c a tín hi u v i c ưng đ khơng thay đ i theo th i gian, tín hi u đưc bi u hi n b ng hàm s a, t ≥ 0, I( t ) =  (2.1) 0,t < 0 trong đĩ a là c ưng đ c a tín hi u. Tín hi u duy trì th lo i tín hi u khơng thay đi trong su t quãng th i gian, ví d ti ng ù c a âm thanh, nh p phát manip v i giá tr khơng đ i, ánh sáng v i cùng m t c ưng đ , 2.1.2 Tín hi u xung Bi u hi n tín hi u xu t hi n đ t ng t trong kho ng th i gian c c nh v i cưng đ c c k ỳ ln sau đĩ khơng xu t hi n +∞,t = 0, ∂(t ) =  (2.2)  0,t ≠ 0. Tín hi u xung th ưng r t hay g p trong các tín hi u đo c a các thi t b vt lý hay c ơ h c. 2.1.3 Tín hi u điu hồ Bi u hi n các lo i tín hi u tu n hồn trong m t kho ng chu kì nào đĩ, đưc bi u di n b ng cơng th c t ng quát St( )= A cos(ω t + β ) (2.3) 19
20. ω 2π Trong đĩ: A là biên đ dao đ ng, f = là t n s , T = là chu k ỳ c a 2π ω dao đng c ơ b n. Dao đ ng c ơ b n cịn cĩ th bi u di n b ng cơng th c t ng quát h ơn Sta( )= cosω tb + sin ω t (2.4) Khi đĩ ta cĩ th bi u di n dao đ ng c ơ b n nh ư m t vect ơ trong h tr c t a đ cc hay d ưi d ng s ph c t ng quát S( t ) = re jω t v i j là đơ n v o. 2.2 Phân tích ph cho tín hi u Trong th c t , m t tín hi u ng u nhiên g m h u h n hay vơ h n các tín hi u đơn s c (nguyên t ), khi đĩ đ nghiên c u và x lý tín hi u ng u nhiên bt k ỳ, chúng ta ph i tìm cách tách t tín hi u ng u nhiên thành t ng tín hi u đơ n sc, vi c phân tích đĩ g i là phép phân tích ph . Nu tín hi u điu hồ cĩ d ng: St( )= A cos(ω t + ψ ) , khi đĩ chúng ta cĩ các khái ni m ph biên đ, ph pha và ph th c nh ư sau: A A ψ ψ ω ω ω Ph biên đ Ph pha Ph th c Hình 2.1 Trong các lo i ph trên, n ăng l ưng t p trung ch y u ω. A Nu tín hi u cho d ưi d ng ph c St( ) =() e(jtωϕ+ ) + e ( jt ωϕ − ) 2 Khi đĩ chúng ta cĩ d ng ph ph c A/2 A/2 ω-ϕ 0 ω+ϕ Hình 2.2 20
21. 2.2.1 Chu i Fourier và ph r i r c ðnh ngh ĩa 1 Cho 2 hàm s ϕ(x ), ψ ( x ) liên t c kh tích trên [a , b ] , đnh ngh ĩa b = ∫ ϕ ()()x ψ xdx (2.5) a đưc g i là tích vơ h ưng c a 2 hàm trên khơng gian C[a , b ] . Kí hi u b ϕ= ϕ 2 (x ) dx (2.6) [a , b ] ∫ a đưc g i là chu n c a ϕ(x ) trên C[a , b ] . ðnh ngh ĩa 2 Cho h hàm ϕ1(x ), ϕ 2 ( x ), , ϕ n ( x ), xác đnh liên t c trên [a , b ] . ∞ H (x ) đưc g i là h tr c giao n u th a mãn điu ki n {ϕk }1  0 , k≠ l =  2 (2.7)  ϕk ,k= l . ∞ H x đưc g i là h tr c chu n nu th a mãn điu ki n {ϕk ( ) }1 0 , k≠ l =  (2.8) 1 ,k= l . Nh n xét : V i m i h tr c giao b t k ỳ, luơn luơn t n t i phép bi n đ i v h tr c chu n b ng ϕk (x ) ϕk ():x = . (2.9) ϕk ðnh ngh ĩa 3 ∞ Cho h (x ) là m t h tr c giao và f( x ) là m t hàm s b t k ỳ {ϕk }1 xác đnh liên t c trên [a, b ], khi đĩ khai tri n 21
22. +∞ fx()= ∑ Akϕ k () x (2.10) k=1 đưc g i là khai tri n Fourier t ng quát thơng qua h tr c giao trong đĩ Ak đưc g i là h s khai tri n. ð xác đ nh các h s khai tri n, ta nhân hai v v i ϕn (x ) và l y tích phân trên đon [a, b ], ta đưc b+∞ b ∫fx()()ϕn xdx=∑ A kkn ∫ ϕ ()() x ϕ xdx ak=1 a ∞ Do tính ch t tr c giao c a h (x ) ta thu đưc {ϕk }1 b+∞ b b 2 ∫fx()()ϕn xdx=∑ A kkn ∫ ϕϕ ()() x xdxA = nn ∫ ϕ () xdx ak=1 a a 2 Hay f,ϕn= A n ϕ n Tc là b ∫ fx()ϕn () xdx f ,ϕn a An =2 = b . (2.11) ϕn 2 ∫ϕn (x ) dx a Cơng th c (2.7) là cơng th c xác đ nh h s khai tri n Fourier trong tr ưng h p t ng quát v i m t h tr c giao b t k ỳ. Sau đây ta xét m t s ví d áp d ng ph ươ ng pháp khai tri n v i các h tr c giao khác nhau +∞ Ví d 1 : Xét h kx trên đon 0,2 {sin }1 [ π ] Ta cĩ 2π1 2 π ∫sinkx sin lxdx= ∫ () cos( klx −−+ ) cos( klxdx ) = 0 , 02 0 22
23. 2π1 2 π ∫sin2 kxdx= ∫ () 1cos2 − kx dx = π . 02 0 Tc là 0 ,k≠ l , sinkx ,sin lx =  π ,k= l . +∞ Hay nĩi cách khác, h sin kx là tr c giao trên đon 0,2 π . Khi đĩ xét { }1 [ ] +∞ hàm f( x ) b t k ỳ, ta luơn cĩ khai tri n f() x= ∑ Ak sin kx trong đĩ k=1 1 2π Ak = ∫ f()sin x kxdx . π 0 +∞ Hồn tồn t ươ ng t , ta c ũng ch ng minh đưc các h hàm sin kx , { }1 +∞ sinkx ,cos lx là các h tr c giao trên các đon t ươ ng ng. { }1 2kπ x Tng quát, cĩ th ch ng minh r ng h ϕ (x )= sin ,( k = 1,2, ) tr c k T T T  giao trên đon − , . 2 2  Ví d 2 : Gi s quan sát tín hi u S( t ) tu n hồn vi chu k ỳ T trong kho ng T T  th i gian − ,  , xét h hàm 2 2  2π jk t T ϕk (t )= e , k =±± 0, 1, 2, T T  Ta cĩ th ch ng minh r ng h hàm {ϕ (t ) } tr c giao trên đon − ,  k 2 2  tc là 23
24. T 2 0,k≠ l , ϕϕkl,−=∫ ϕ k ()()t ϕ − l tdt =  T T, k= l . − 2 Khi đĩ s d ng ph ươ ng pháp khai tri n Fourier, ta khai trin hàm S( t ) thơng qua h hàm tr c giao +∞ St()= ∑ Akϕ k () t k=−∞ Trong đĩ: T T 2 2 2kπ − j t 1 1 T A0 =∫ StdtA(),k = ∫ Ste () dt . TT T T − − 2 2 Hay 2kπ 2 k π +∞ jt− jt  T T St( ) = A0 +∑ Aek + Ae− k  k=1   +∞  2ktπ 2 kt π  2 kt π 2 kt π   =+AA0 ∑ k cos + j sin  + A−k cos − j sin   k=1  T T  T T   +∞ 2ktπ 2 kt π =+A0 ∑() AAkk +−cos +− jAA() kk − sin k=1 T T +∞ 2ktπ 2 kt π =A0 +∑ akcos + jb k sin k=1 T T Trong đĩ TT T 12 22 2 ktπ 222 kt π A0 =∫ Stdta(),k = ∫ St ()cos dtb ,k = ∫ St ()sin dt TTT T TTT T − − − 2 2 2 24
25. 2kπ t Trong tr ưng h p tín hi u là hàm s ch n t c là hàm s S( t )sin là T hàm s l , khi đĩ h s bk ≡0, ∀ k = 1,2,3, Khi đĩ +∞ 2kπ t St( )= A0 + ∑ a k cos . k=1 T 2kπ t Hồn tồn t ươ ng t , n u tín hi u là hàm s l t c là hàm s S( t )cos là T hàm s l , khi đĩ h s ak ≡0, ∀ k = 0,1,2,3, Khi đĩ +∞ 2kπ t S() t= ∑ b k sin . k=1 T Nh n xét: + V i m t tín hi u tu n hồn v i chu k ỳ T thì h hàm 2π jk t T ϕk (t )= e , k =±± 0, 1, 2, đưc ch n là h tr c giao t ng quát trên đon T T  − , trong đĩ n u tín hi u là ch n thì h tr c giao đưc xác đ nh là 2 2  2kπ  +∞ cos t  cịn n u tín hi u là l thì h tr c giao đưc xác đ nh là T  0 2kπ  +∞ sin t  T  0 + ði v i m t tín hi u b t k ỳ thì chúng ta c n ph i xác đ nh chu k ỳ c a tín hi u c ũng nh ư tính ch t ch n l c a tín hi u tr ưc khi khai tri n. Ví d 3 : Phân tích ph cho tín hi u là dãy xung sau: A -τ -τ/2 τ/2 τ Hình 2.3 25
26. T T  Ta cĩ chu k ỳ c a tín hi u là T = 2τ . Xét trên đon − , , khi đĩ 2 2   τ τ  A, t ∈ − , ,  2 2  S( t ) =   τ τ  0,t ∉ − ,  .  2 2  Tín hi u S( t ) là hàm ch n. S d ng các cơng th c khai tri n v i h tr c giao 2kπ  +∞ +∞ kπ cos t  ta cĩ StA( )=0 + ∑ Ak cos t trong đĩ T  0 k=1 τ T τ 12 1 2 A A0 =∫ Stdt( ) = ∫ Adt = . 2τT 2 τ τ 2 − − 2 2 T τ 22kπ 1 2 k π 2 Ak π Ak =∫ St( )cos tdt = ∫ A cos tdt = sin 2τT τττ τk π 2 − − 2 2 2A  (− 1)l ,k = (2 l + 1), Hay Ak = kπ  0,k= 2 l . Nh ư v y ta cĩ khai tri n A+∞ 2 A (2 k + 1) π S( t )= +∑ ( − 1)k cos t . 2k=1 (2k + 1) π τ 2A/ π A/2 2A/3 π 0 0 2 π/T 4 π/T 6 π/T 8 π/T Hình 2.4 26
27. Ph c a tín hi u đưc mơ t b i hình 2.4 2.2.2 Tích phân Fourier và ph liên t c Vi tín hi u liên t c ta cĩ hàm S( t ) trong ph th i gian t ươ ng ng v i S( j ω ) trong ph t n s . S d ng cơng th c khai tri n Fourier trong tr ưng hp t ng quát, ta cĩ: +∞ Sj()ω = fSt[] () = ∫ Ste () − jω t dt (2.12) −∞ Ng ưc l i ta cĩ: 1 +∞ St()= fSj[] ()ω = ∫ Sjed () ωjω t ω (2.13) 2π −∞ Tưng t nh ư xét v i S( t ) ta cĩ ph c a S( j ω ) nh ư sau • Ph ph c: Sj()ω= A () ω + jB () ω . • Ph biên đ: =A2()ω + B 2 () ω . B(ω )  • Ph pha: = Arctg   . A(ω )  Ví d : Xét m t xung vuơng sau: A +∞ S(j ω) = ∫ S(t)e− jωt dt −∞ -τ/2 τ/2 Ta cĩ: Hình 2.5 τ ωτ +∞ 2 τω τω sin A − j j  Sj(ω )= Stedt () −jtω = Aedt − jt ω = e2 −= e 2  A τ 2 ∫ ∫ ωτ τ − jω   −∞ − 2 2 27
28. Aτ , t = 0,  Nh ư v y ph S( j ω ) =  2kπ Aτ  0,t = .  τ 0 2 π/τ 4 π/τ 6 π/τ Hình 2.6 2.2.3 Ph các tín hi u điu ch Tín hi u thơng tin mu n truy n đi xa phi nh tín hi u cao t n. ð tín hi u cao t n mang thơng tin ta ph i làm cho tín hi u cao t n bi n thiên theo qui lu t c a tín hi u thơng tin. Tín hi u cao t n cĩ d ng: Sta( )=0 cos(ω 0 t + β ) = a 0 cos ψ ( t ) (2.14) Ta cĩ th điu ch 2 thơng s biên đ a0 và gĩc ψ (t ) . V i gĩc ψ (t ) ta cĩ th điu ch theo t n s ω0 (g i là tín hi u điu t n) theo gĩc pha β (g i là điu pha). Sau đây chúng ta s xét chi ti t các ph ương pháp điu ch . Ph ươ ng pháp điu biên Trong ph ươ ng pháp điu biên, ta bi n đ i biên đ c a tín hi u cao t n theo qui lu t c a thơng tin u( t ) t c là bi n đ i cĩ ch a l ưng tin c n truy n, cịn t n s và gĩc pha khơng đi. Gi s tin cn truy n là u( t ) , khi đĩ ta cĩ cơng th c bi n đ i: St()[= a0 + Mut 0 ()]cos(ω 0 t + β ) (2.15) ∆a trong đĩ: M 0 = đưc g i là h s điu ch , trong k thu t điu ch , đ a0 thơng tin điu ch đ m b o đ chính xác, ta c n ch n M 0 ≤1. Hàm s u( t ) đưc g i là hàm tin, hàm tin th ưng ch n là hàm đơ n s c, n u hàm tin là các thơng tin ph c t p, ta ph i tách thành các tín hi u đơn s c b ng ph ươ ng pháp phân tích ph đã nghiên c u ch ươ ng tr ưc. Gi s u( t ) là hàm đơ n s c cĩ d ng m t dao đ ng điu hồ 28
29. u() t= cos( Ω t + θ ) Khi đĩ ta cĩ StaM( )=+ [0 0 cos( Ω+ tθ )]cos( ω 0 t + β ) =atMt00cos(ωβ ++ ) 0 cos( Ω+ θωβ )cos( 0 t + ) M M =atcos(ωβ ++ )0 cos[( ω +Ω+++ ) t θβ ]0 cos[( ω −Ω+− ) t βθ ] 0 02 0 2 0 =St1() + St 2 () + St 3 () Nh ư v y tín hi u qua quá trình điu biên s g m ba thành ph n, M t thành ph n S1( t ) dao đng v i t n s mang ω0 và 2 thành ph n S2( t ), S 3 ( t ) dao đng v i t n s biên (ω0 ± Ω ) . Biên đ c a t n s biên b ng nhau và M bng 0 . 2 a 0 M 0/2 M 0/2 ω0 - Ω ω0 ω0 + Ω Hình 2.7 Trong tr ưng h p tín hi u là khơng đơ n s c thì tín hi u điu biên là m t mi n, khơng ph i là ph v ch, đ th véc t ơ c a tín hi u điu biên nh ư sau C D θ A -θ B a 0 ϕ0 ω O Hình 2.8 Trong đĩ OA: Tín hi u mang 29
30. AB, AC: T n s biên OD: Tín hi u điu ch Nh n xét: • OD max khi AD=AB + AC = Ma 0 ⇒ OD = a 0 + Ma 0 = a 0 (1+M). ð khơng nhi u thì AD ≤ a 0 hay M ≤ 1. • OD // OA: Thì tín hi u hàm tin là đơ n s c và ph là ph v ch n u hàm tin khơng đơ n s c thì ph là m t mi n. • Theo đ th thì biên đ sĩng mang (a 0) ln chi m nhi u h ơn 70% n ăng lưng nên th ưng nén đ ti t ki m n ăng l ưng gi m hao phí. Ph ươ ng pháp điu t n Trong ph ươ ng pháp điu t n, ng ưi ta bi n đ i t n s c a sĩng mang theo tín hi u c a hàm tin u( t ) , t c là ω0:= ω 0 + ∆ ωu ( t ) . Trong đĩ h s ∆ω gi là h s điu t n. Xu t phát t cơng th c tích phân ψ(t ) = ω0 t + β = ∫ ω 0 dt Qua quá trình điu t n, ta nh n đưc ψ()[t=∫ ω0 +∆ω utdt ()] = ω 0 t +∆ ω ∫ utdt () Gi s sĩng mang cĩ d ng Sta()=0 cos(ω 0 t + β ) và hàm tin là hàm đơ n sc u( t )= cos( Ω t + θ ) . Khi đĩ qua ph ươ ng pháp điu biên Sta()=00 cos(ω t +∆ω ∫ utdta ()) = 00 cos( ω t +∆ω ∫ cos( Ω+ t θ ) dt ) ∆  =atcosω +ω sin( Ω+= ta θ )  cos() ψψ () tt + () 00Ω  012 Nh ư v y qua quá trình điu t n, pha c a sĩng mang đã đưc tách thành 2 thành ph n ψ1(t ) ch a t n s c a sĩng mang và thành ph n ψ 2 (t ) ch a thành ph n tin u( t ) . 30
31. Ph ươ ng pháp điu pha Tươ ng t nh ư ph ươ ng pháp điu t n, ph ươ ng pháp điu pha bi n đ i gĩc pha cĩ ch a hàm tin u( t ) cịn biên đ và t n s khơng đ i. Ta cĩ cơng th c bi n đ i trong tr ưng h p tín hi u đơn s c: ψωβ()tt=0 ++∆β utt () = ωβ 0 ++∆ β cos( Ω+ t θ ) Tc là Sta()=0 cos(ω 0 t ++∆ ββ cos( Ω+ t θ ) ) Nh n xét: V hình th c thì cĩ th coi tín hi u điu t n, điu pha gi ng nhau trong cơng th c t ng quát sau đây: Sta()=001 cos(ω t ++∆ βm cos( Ω+ t θ 1 ) ) (2.16) ∆ π Tín hi u điu t n thì ∆=ω ,β = βθ , =− θ , tín hi u điu pha thì m Ω 1 1 2 ∆=∆m β ,β1 = βθ , 1 = θ . 2.2.4 Phân tích tín hi u ng u nhiên Do các tín hi u ng u nhiên là các đi l ươ ng ng u nhiên tuân theo các quy lu t phân ph i xác đ nh nên vi c phân tích các tín hi u ng u nhiên d a trên c ơ s phân tích m i t ươ ng quan gi a các đ i l ưng ng u nhiên c a lý thuy t xác su t th ng kê. Ph ươ ng pháp phân tích t ươ ng quan Nh ư ch ươ ng tr ưc đã gi i thi u, tín hi u ng u nhiên x( t ) cĩ th i gian tn t i h u h n ph thu c vào τ . Hàm t ươ ng quan B(τ ) đưc tính theo cơng th c: +∞ Bx ()τ=∫ xtxt ()( + τ ) dt (2.17) −∞ Hàm t ươ ng quan ph n ánh m i liên h gi a tín hi u và b n thân nĩ sau khi d ch chuy n m t quãng th i gian τ. Th c ra do cĩ s bi n thiên nên ta xét trong quá trình d ng theo ngh ĩa r ng thì hàm Bx (τ ) đưc tính nh ư giá tr trung bình c a x( t ) và x( t +τ ) tc là 31
32. 1 +∞ Bx ()()(τ=+= xtxt τ ) Lim xtxt ()( + τ ) dt (2.18) T →+∞ ∫ T −∞ Hàm t ươ ng quan cĩ m t s tính ch t nh ư sau: 1. Hàm t ươ ng quan là m t hàm ch n Bx(τ )= B x ( − τ ). 2. Tr s hàm t ươ ng quan khi τ = 0 trùng v i cơng su t trung bình c a quá trình: +∞ 2 2 Bx (0)= xt () = ∫ xtdt () . −∞ 3. Giá tr hàm t ươ ng quan khi τ = 0 đt giá tr c c đ i Bx(0)≥ B x (),τ ∀ τ . 4. Nu hàm t ươ ng quan th a mãn điu ki n ≠0,τ = 0, Bx (τ ) =   0,τ ≠ 0. thì gi a x( t ) và x( t +τ ) khơng t n t i t ươ ng quan th ng kê 5. Khi τ → ∞ thì gi a x( t ) và x( t +τ ) s đ c l p v i nhau khi đĩ hàm t ươ ng quan s d n t i 0. ð th mơ t hàm t ươ ng quan cĩ d ng nh ư hình v Bx(0) Hình 2.9 τ Ph ươ ng pháp phân tích ph Quan sát các quá trình ng u nhiên ta ch cĩ th xác l p đưc ph ch y 32
33. T − jω t ST ()ω = ∫ Ste () dt (2.18) 0 Hàm t ươ ng quan: T B()τ= ∫ Ste ()− jω t dF () ω (2.19) −∞ dF 1 Trong đĩ = G(ω) dω 2π Ng ưi ta g i G( ω) là ph n ăng l ưng, khi đĩ 1 _ ∞ B()ω= ∫ Ged () ωjωτ ω (2.20) 2π −∞ Trong tr ưng h p này, G( ω) đưc xem nh ư là bi n đ i Fourier c a B( τ) _ ∞ G()ω= ∫ Bed () τ− jωτ τ (2.21) −∞ Do B( τ) và G( ω) là các hàm ch n nên ch l y giá tr cos(ωτ ) t c là 1 +∞ B()τ= ∫ G ()cos ω ωτ d ω ; π 0 +∞ G(ω )= 2∫ B ()cos τ ωττ d (2.22) 0 Nu τ = 0 thì: 1 +∞ B(0)= ∫ G (ω ) d ω 2π −∞ 2.3 Nhi u tr ng Các hi n t ưng xáo đ ng nhi t trong các ph n t c a m ch đin hay dây dn, ho c b c x trong khí quy n đ u gây ra m t loi tín hi u nhi u cĩ d i ph rt r ng g i là nhi u tr ng. Nhi u là thành ph n khơng th b qua khi nghiên cu v các kênh, nhi u tr ng c ũng là m t lo i tín hi u ng u nhiên. Qua đo đc 33
34. nghiên c u ta tìm đưc cơng th c tính m t đ phân b xác su t c a nhi u theo quy lu t c a phân ph i chu n Gauss x2 − 1 2 W( x ) = e 2σ (2.23) 2 2πσ Trong đĩ σ đưc g i là cơng su t trung bình c a nhi u. T đĩ ta th y quy lu t phân b xác su t c a nhi u đưc xác đ nh b i hàm phân ph i xác su t u t2 1− 1 Fupxu()()= ) =() 1() −Φ u 02 0 Dùng ph ươ ng pháp phân tích ph đ kh o sát nhi u, ta coi nhi u tr ng nh ư mt hàm ng u nhiên x( t ) trong kho ng (−∞; +∞ ) . Xét trong m t đon đ T T  dài − ,  cĩ k xung. Ng ưi ta đã phân tích và thu đưc k t qu : 2 2  k 2 2 k G()ω= Lim 2() S ω = 2 kS1 () ω trong đĩ k1 = Lim T →+∞ T T →+∞ T Khi đĩ ta g i G(ω ) là ph n ăng l ưng c a nhi u đưc xác đ nh theo S(ω ) c a t ng xung, trong th c t nhi u đ n m t giá tr nào đĩ s gi m nh khi ω → +∞ 34
35. CH ƯƠ NG 3. L ƯNG TIN, ENTROPI NGU N R I R C 3.1 ð đo thơng tin 3.1.1 Khái ni m đ đo ði v i m t đ i l ưng v t lý b t k ỳ, đ nghiên c u v đ i l ưng đĩ chúng ta ph i trang b m t đơn v xác đ nh đ ln c a đ i l ưng đĩ đưc g i là đ đo. M i đ đo ph i th a mãn 3 tính ch t sau: • ð đo là m t đ i l ưng khơng âm. • ð đo ph i cho phép ta xác đ nh đưc đ ln c a đ i l ưng đĩ. ð i lưng càng ln, giá tr đo đưc ph i càng cao. • ð đo ph i tuy n tính: t c là giá tr đo đưc c a đ i l ưng t ng c ng ph i b ng t ng giá tr c a các đ i l ưng riêng ph n khi s d ng đ đo này đ đo chúng. 3.1.2 ð đo thơng tin. Khi nghiên c u v thơng tin, hi n nhiên đây c ũng là m t đ i l ưng v t lý, vì v y chúng ta c ũng ph i xác đ nh m t đ đo cho thơng tin. ð xây d ng đ đo cho thơng tin chúng ta c n chú ý m t s v n đ sau đây: Theo b n ch t c a thơng tin thì hi n nhiên thơng tin càng cĩ ý ngh ĩa khi nĩ càng ít xu t hi n, nên đ đo c a nĩ ph i t l ngh ch v i xác su t xu t hi n ca tin hay nĩi cách khác hàm đ đo ph i là hàm t l ngh ch v i xác su t xu t hi n c a tin t c. Kí hi u x là tin vi xác su t xu t hi n là p( x ) . Khi đĩ hàm đ đo kí 1  hi u là I( x ) = f   là hàm t l ngh ch v i xác su t p( x ) . p( x )  Mt tin x s là khơng cĩ ý ngh ĩa n u chúng ta đã bi t v nĩ hay xác su t xu t hi n p( x )= 1 . Trong tr ưng h p này đ đo ph i b ng khơng t c là I( x )= 0 . Xét 2 tin x, y là đc l p th ng kê v i xác su t xu t hi n t ươ ng ng là px( ), py ( ) khi đĩ tin z= xy là tin khi xu t hi n đ ng th i 2 tin x, y cùng mt th i đim. Do đĩ theo tính ch t tuy n tính, chúng ta ph i cĩ 35
36. Ixy()= Ix () + Iy () . Nh ư v y đ xây d ng hàm đ đo thơng tin, ta th y hàm I( x ) ph i là hàm khơng âm và th a mãn đng th i c 3 điu ki n đã nêu. D th y trong t t c các hàm tốn h c đã bi t thì n u ch n 1  I()log x=a   , a > 1 p( x )  thì t t c các điu ki n đ u đưc th a mãn b i vì 1  Ix()log=a   ≥>∀≤ 0, a 1,0 px ()1. ≤ p( x )  1  I()log x=a   , a > 1 là hàm s ngh ch bi n v i xác su t p( x ) . p( x )  1  Ix()log=a   = 0,()1. px ≡ p( x )  1 1  I( xy )= loga = log a  pxy() pxpy ()()  1   1  =loga  + log a   =+Ix ()() Iy v i x, y đc l p. px()   py ()  Xu t phát t nh ng lý do trên, trong lý thuy t thơng tin, hàm s 1  Ix( )= loga  =− log a ( pxa ( )), > 1 (3.1) p( x )  đưc ch n làm đ đo thơng tin hay l ưng đo thơng tin c a m t tin c a ngu n. Trong cơng th c xác đ nh đ đo thơng tin này, c ơ s c a hàm logarit cĩ th ch n tùy ý th a mãn (a > 1) tuy nhiên ng ưi ta th ưng dùng các đơ n v đo nh ư sau: • Bit hay đơ n v nh phân khi c ơ s là 2. • Nat hay đơ n v t nhiên khi c ơ s là e. • Hartley hay đơ n v th p phân khi c ơ s là 10. 36
37. 3.2 Lưng tin c a ngu n r i r c 3.2.1 Mi liên h c a l ưng tin và lý thuy t xác su t Khái ni m thơng tin là m t khái ni m đưc hình thành t lâu trong t ư duy c a con ng ưi. ð di n t khái ni m này, ta gi thi t r ng trong m t tình hu ng nào đĩ, cĩ th x y ra nhi u s ki n khác nhau và vi c x y ra m t s ki n nào đĩ trong t p h p các s ki n cĩ th làm cho ta thu nh n đưc thơng tin. Mt tin đ i v i ng ưi nh n cĩ hai ph n • ð b t ng c a tin. • Ý ngh ĩa c a tin. ð so sánh các tin v i nhau, ta cĩ th l y m t trong hai ho c c hai n i dung trên làm th ưc đo. Nh ưng n i dung hay ý ngh ĩa c a tin mà ta cịn g i là tính hàm ý c a tin, khơng nh h ưng đ n các v n đ c ơ b n c a h th ng truy n tin nh ư t c đ hay đ chính xác. Nĩ chính là ý ngh ĩa c a nh ng tin mà con ng ưi mu n trao đ i v i nhau thơng qua vi c truy n tin. ð b t ng c a tin liên quan đn các v n đ c ơ b n c a h th ng truy n tin. Ví d : m t tin càng b t ng , s xu t hi n c a nĩ càng hi m, thì rõ ràng th i gian nĩ chi m trong m t h th ng truy n tin càng ít. Nh ư v y, mu n cho vi c truy n tin cĩ hi u su t cao thì khơng th coi các tin nh ư nhau n u chúng xu t hi n ít nhi u khác nhau. ð đ nh l ưng thơng tin trong các h th ng truy n tin, ta l y đ b t ng ca tin đ so sánh các tin v i nhau. Ta quy ưc r ng l ưng tin càng ln n u đ bt ng c a tin càng cao. ðiu này là h p lý vì khi ta nh n đưc m t tin đã bi t tr ưc thì xem nh ư khơng nh n đưc gì, và vi c nh n đưc m t tin mà ta ít cĩ hy v ng nh n đưc thì l i r t quý đ i v i chúng ta. Mi tin t c đưc th hi n qua m i s ki n. Các s ki n là các hi n t ưng ng u nhiên cĩ th đưc mơ t b i các quy lu t th ng kê. V m t truy n tin ta ch quan tâm đ n đ b t ng c a tin hay xác su t xu t hi n các ký hiu. ð nghiên c u v n đ này ta dùng các quy lu t th ng kê. Phép bi n đ i t ng quát trong h th ng truy n tin là phép bi n đ i c u trúc th ng kê c a ngu n 37
38. Bây gi chúng ta xem xét m i liên h gi a khái ni m tin t c v i lý thuy t xác su t. M t ngu n tin r i r c đưc xem nh ư m t t p h p các tin x(k ) hình thành b i nh ng dãy ký hi u h u h n xi là m t ký hi u ai b t k ỳ thu c (k ) (k ) ngu n A đưc g i đi th i đim t j . Tin x cĩ d ng: x = (x1 , x2 , , xn ) vi xác su t xu t hi n p(x (k ) ) . V m t tốn h c ngu n tin X c ũng đ ng ngh ĩa v i m t tr ưng xác su t hu h n g m các đim x (k ) . (k = 2,1 , , M ) trong khơng gian n chi u. M là tng s các đim đưc tính b ng M = m n . Phép bi n đ i t ng quát trong m t h th ng truy n tin là phép bi n đ i cĩ cu trúc th ng kê c a ngu n. Chúng ta cĩ th l y b t k ỳ m t khâu x lý tin t c nào đĩ trong h th ng nh ư r i r c hĩa, mã hĩa, điu ch , truy n lan, gi i điu ch , gi i mã đu cĩ th xem nh ư m t phép bi n đ i ngu n. Nĩi cách khác phép x lý đĩ đã bi n đ i c u trúc th ng kê c a t p tin đ u vào khâu h th ng tr thành m t t p tin m i v i m t c u trúc th ng kê mong mu n đ u ra. {A, p ( a ) } εεε {B, p ( b ) } Hình 3.1 Trong đĩ • {A, p(a)} là ngu n đ u vào v i b ch A và phân b xác su t các ký hi u p(a). • {B, p(b)} là ngu n đ u ra v i b ch B và phân b xác su t các ký hi u p(b) . Nu εεε là quy lu t bi n đ i thì ta cĩ m i quan h εεε = {B, p(b)}. Chúng ta cĩ th mơ t ngu n tin đ u vào b ng t p tin U = {u (i) } và quy (i) (i) lu t phân b xác su t các tin p(u ) . Trong đĩ u = (u1 ,u2 , , un ) , uk là các tin thu c A x y ra các th i đim tk . 38
39. Tươ ng t ngu n tin đ u ra đưc mơ t b ng t p tin V = {v (i) } v i quy (i) (i) lu t phân b xác su t p(v ) . Trong đĩ v = (v1 ,v2 , , vn ) , vk là m t ký hi u thu c b ch B x y ra tu n t th i đim tk . Các tin u (i) hay v ( j) đưc xem nh ư nh ng ph n t c a t p U hay V ; ho c nh ng b c a t p tích ð các c a n t p. Nh ư v y u (i) và v( j) l n l ưt là ph n t c a t p: U= X × Y × Z v i X = Y = Z = = A V= O × P × Q v i O = P = Q = = B Ngu n tin đưc xem nh ư khơng gian đim r i r c nhi u chi u, m i m t đim đ i di n cho m t tin. Phép bi n đ i ngu n chuy n m t khơng gian tin này sang m t khơng gian tin khác. Ví d phép r i r c hĩa, chuy n m t khơng gian tin liên t c thành khơng gian tin r i r c. Phép bi n đ i trong kênh c ũng cĩ th đưc xem nh ư nh ng phép bi n đi ngu n khác, tuy nhiên vì cĩ tác đng c a nhi u nên s chuy n đ i gi a các tin thơng th ưng khơng ph i là m t – m t Kt qu bi n đ i các tin trong kênh cĩ th đưc xem nh ư các ph n t c a tp tích X.Y . Quy lu t phân b xác su t các tin p(x, y) c a t p tích X.Y tùy thu c vào quy lu t phân b xác su t c a t p vào p(x) và tính ch t th ng kê ca kênh ngh ĩa là xác su t chuy n đ i t tin x thành tin y : p(y | x) . p(xy ) = p(x) p(y | x) . Nu cĩ ngu n tin v i s ký hi u b t k ỳ X = {x1 , x2 , , xm }. ðu ra thu đưc ngu n Y = {y1 , y2 , , yn }. Ta xét nh ư sau: x 1 y 1 x2 y2 (x i,y j) xi yj xm yn x 1 x 2 x i x m Hình 3.2 39
40. Phép bi n đ i trong kênh t o ra m t ngu n m i U = X.Y , v i các tin là các cp (xi , y j ) , trong đĩ xi ∈ X , y j ∈Y , theo quy lu t phân b xác su t p(xi , y j ) . Các tin (xi , y j ) là các đim r i r c trên m t ph ng XY . Theo lý thuy t xác su t, s liên h gi a các xác su t c a các ph n t trong t p X ,Y và U = X.Y cĩ th tính nh ư sau: p(x) = ∑ p(x, y ;) p(y) = ∑ p(x, y) y∈Y x∈X p(x, y) = p(x) p(y / x) = p(y) p(x / y) p(x) p(y / x) p(x / y) = ∑ p(x) p(y / x) y∈Y Ví d 1: Phép mã hĩa nh phân, cho m t ngu n tin U= { u0 ,u 1 , ,u 7 } dùng mã nh phân đ mã hĩa ngu n tin, v i phép mã hĩa nh ư sau: u0 → x0 y0 z0 u1 → x1 y0 z0 u2 → x0 y1 z0 u3 → x1 y1 z0 u4 → x0 y0 z1 u5 → x1 y0 z1 u6 → x0 y1 z1 u7 → x1 y1 z1 trong đĩ x0 = y0 = z0 = 0 ; x1 = y1 = z1 = 1; các mã hi u thi t l p như trên là các ph n t c a m t t p tích X.Y.Z và đưc đ i bi u b ng nh ng đim r i r c trong m t khơng gian 3 chi u. S liên h gi a quy lu t phân b xác su t trong các t p h p và t p tích đã cho trong lý thuy t xác su t nh ư sau: p(x) = ∑ p(x, y) = ∑ p(x, y, z) y∈Y y∈Y ;z∈Z p(y) = ∑ p(x, y) = ∑ p(x, y, z) x∈X x∈X ;z∈Z 40
41. p(z) = ∑ p(x, z) = ∑ p(x, y, z) x∈X x∈X ;y∈Y p(x, y) = ∑ p(x, y, z) z∈Z p(x, z) = ∑ p(x, y, z) y∈Y p(y, z) = ∑ p(x, y, z) x∈X p(x, y, z) = p(x) p(yz / x) = p(y) p(xz / y) = p(z) p(xy / z) Áp d ng các bi u th c trên trong vi c xác đ nh xác su t c a mã hi u, khi nh n đưc đ u ra c a b mã hĩa l n l ưt các ký hi u c a m t dãy nào đĩ. Gi s đ u ra nh n đưc dãy x1 y0 z1 . Hãy tính xác su t c a tin sau khi nh n đưc l n l ưt các ký hi u c a dãy. Xác su t c a tin ui sau khi nh n đưc ký hi u x1 đưc tính theo xác su t p(x1 , y, z) cĩ điu ki n p(y, z / x1 ) = trong đĩ p(x1 ) 1 1 1 1 1 p(x ) = p(u ) + p(u ) + p(u ) + p(u ) = + + + = 1 1 3 5 7 4 8 16 16 2 Xác su t c a tin ui sau khi nh n đưc ký hi u x1 , y0 tính theo xác su t cĩ p(x1 , y0 , z) 1 1 5 điu ki n sau: p(z / x1 , y0 ) = trong đĩ p(x1 , y0 ) = + = p(x1 , y0 ) 4 16 16 Xác su t c a tin ui sau khi nh n đưc ký hi u x1 , y0 , z1 ch cĩ kh p(x1 , y0 , z1 ) năng x y ra là u5 : p(u5 / x1 , y0 , z1 ) = = 1, cịn l i các tin khác đ u p(x1 , y0 , z1 ) cĩ xác su t b ng 0. K t qu tính tốn đưc cho trong b ng 3.1 41
42. Xác su t c a tin sau khi nh n đưc ký hiu ui p( u i ) XYZ x1 y0 z1 1/4 0 0 0 u0 x0 y 0 z 0 1/4 1/2 4/5 0 u1 x1 y 0 z 0 1/8 0 0 0 u2 x0 y 1 z 0 1/8 1/4 0 0 u3 x1 y 1 z 0 1/16 0 0 0 u4 x0 y 0 z 1 1/16 1/8 1/5 1 u5 x1 y 0 z 1 1/16 0 0 0 u6 x0 y 1 z 1 1/16 1/8 0 0 u7 x1 y 1 z 1 Bng 3.1 3.2.2 L ưng tin riêng, l ưng tin t ươ ng h , l ưng tin cĩ điu ki n Nh ư trong ph n tr ưc ta đã đ c p v đ đo thơng tin, hàm logarit đã đưc ch n đ đánh giá, đ nh l ưng các l ưng tin. ð i v i m i tin xi c a ngu n X đu cĩ l ưng tin riêng nh ư đã bi t: 1  I( x i )= log   p( x i )  Nu ngu n X thơng qua m t phép bi n đ i tr thành ngu n Y ví d thơng qua s truy n lan trong kênh thì phép bi n đ i đĩ cĩ th khơng ph i là 1-1. đu vào c a kênh là các tin xi ∈ X , các tin trong quá trình truy n lan trong kênh b nhi u phá ho i, làm cho s chuy n đ i t ngu n X sang ngu n Y khơng ph i là 1-1 . M t tin xi ∈ X cĩ th chuy n thành m t tin y j ∈Y đu ra c a kênh v i nh ng xác su t chuy n đ i khác nhau tùy thu c theo tính ch t nhi u trong kênh. 42
43. Bài tốn truy n tin trong tr ưng h p này đt ra là: Cho bi t c u trúc th ng kê c a ngu n X , tính ch t t p nhi u c a kênh bi u th d ưi d ng các xác su t chuy n đ i c a tin, khi nh n đưc m t tin y j ∈Y , hãy xác đnh tin tươ ng ng c a ngu n X . ðây là bài tốn th ng kê, l i gii kh ng đ nh là khơng cĩ đưc. L i gi i tìm đưc s cĩ d ng: v i tin y j ∈Y nh n đưc, tin nào c a ngu n X cĩ nhi u kh n ăng đã đưc phát đi nh t. Mu n gi i quy t v n đ này ta l n l ưt qua hai b ưc Bưc 1: Tính các l ưng tin v m t tin b t k ỳ xi ∈ X ch a trong tin y j ∈Y nh n đưc, l ưng tin đĩ g i là l ưng tin t ươ ng h gi a xi và y j . Mu n xác đ nh l ưng tin t ươ ng h ta ph i tìm l ưng tin ban đ u cĩ trong xi , sau khi th c hi n quá trình truy n tin ta cn xác đ nh tìm l ưng tin cịn l i trong xi , hi u hai l ưng tin này cho ta th y l ưng tin đã truy n t xi sang y j . Lưng tin ban đu là l ưng tin riêng đưc xác đ nh b ng xác su t tiên 1  nghi m c a tin: I( x i )= log   . p( x i )  Lưng tin b nhi u phá h y m t ph n đưc xác đnh b ng xác su t h u 1 nghi m I(xi | y j ) = log , l ưng tin này cịn g i là l ưng tin cĩ điu p(xi | y j ) ki n, trong quá trình truy n tin, l ưng tin đĩ chính là l ưng tin đã b t p nhi u phá h y khơng đ n đ u thu đưc. Nh ư v y l ưng tin t ươ ng h đưc tính theo cơng th c sau: p(xi | y j ) I(xi , y j ) = I(xi ) − I(xi | y j ) = log p(xi )   = log p(xi | y j /) ∑ p(y j ) p(xi | y j )  j  Bưc 2: ðem so sánh các l ưng tin t ương h v i nhau, và l ưng tin nào c c đi s cho bi t tin xi cĩ kh n ăng nhi u nh t chuy n thành y j trong quá trình truy n tin. 43
44. Trong tr ưng h p ph c t p M r ng khái ni m l ưng tin t ươ ng h trong tr ưng h p mã hĩa hay phép bi n đ i ph c t p h ơn. Lúc đĩ l ưng tin t ươ ng h c ũng đưc xác đ nh theo các cơng th c xác su t tiên nghi m và xác su t h u nghi m c a tin đang xét. Ví d m t phép bi n đ i kép X → Y → Z . Lưng tin ban đ u c a xi đưc xác đ nh theo xác su t ban đ u hay xác su t tiên nghi m. Sau khi nh n đưc tin y j , xác su t c a tin xi tr thành xác su t cĩ điu ki n p(xi | y j ) , và cu i cùng khi đã nh n đưc y j và zk thì xác su t c a xi là p(xi | y j zk ) . Nu ta xem p(xi ) là xác su t tiên nghi m và p(xi | y j ) là xác su t h u nghi m thì ta l i tr l i tr ưng h p bin đ i đơn gi n đã nĩi trên và cĩ l ưng tin t ươ ng h gi a xi và y j : I(xi , y j ) . Nu ta xem p(xi | y j ) là xác su t tiên nghi m và p(xi | y j zk ) là xác su t h u nghi m, ta s xác đ nh đưc l ưng tin t ươ ng h gi a xi và zk v i p(xi | y j zk ) điu ki n đã bi t y j : I(xi , zk | y j ) = log p(xi | y j ) Nu ta xem p(xi ) là xác su t tiên nghi m và p(xi | y j zk ) là xác su t hu nghi m thì l ưng tin t ươ ng h gi a xi và c p (y j , zk ) là: p(xi | y j zk ) I(xi , y j zk ) = log p(xi ) Mt cách tr c giác cĩ th nh n th y l ưng tin v xi ch a trong c p (y j , zk ) ph i bng l ưng tin v xi ch a trong y j c ng v i l ưng tin t ươ ng h v xi ch a trong zk khi đã bi t y j . ðiu này cĩ th đưc xác minh m t cách d dàng nh ư sau: p(xi | y j zk ) p(xi | y j ) I(xi , y j zk ) = log = I(xi , y j ) + I(xi , zk | y j ) p(xi ) p(xi | y j ) Nu thay th t các t p X ,Y, Z thì s cĩ các bi u th c m i nh ưng ý ngh ĩa hồn tồn khơng thay đi. 44
45. Ví d : Tính l ưng tin t ươ ng h gi a tin u5 và các ký hi u l n l ưt nh n đưc, trong ví d mã hĩa nh phân đã nêu trong ví d tr ưc 8/1 I(u , x ) = log = log 2 5 1 1/16 5/1 8 I(u , y | x ) = log = log 5 0 1 1/8 5 1 I(u , z | x y ) = log = log 5 5 1 1 0 1/ 5 Tng l ưng tin v u5 đưc bi t l n l ưt khi nh n x1 , y0 , z1 : log16 3.2.3 Tính ch t c a l ưng tin Tính ch t 1: Lưng tin riêng là m t đ i l ưng khơng âm (vì p(xi ) ≤ 1 nên − log p(xi ) ≥ 0 ). Nh ưng l ưng tin t ươ ng h cĩ th d ươ ng, cĩ th âm do ph thu c l ưng tin cĩ điu ki n. Tính ch t 2: Lưng tin riêng bao gi c ũng ln h ơn l ưng tin v nĩ ch a trong bt k ỳ ký hi u nào cĩ liên h th ng kê v i nĩ. Do v y khi xi và y đc l p th ng kê thì l ưng tin t ươ ng h b ng 0. L ưng tin t ươ ng h c c đ i khi p(y j | xi ) = 1 và b ng l ưng tin riêng. p (x | y ) p(y | x ) 1 I(x , y ) = log i j = log j i ≤ I( x )= log i j p (x ) p y i i ( j ) p( x i ) ðiu nĩi trên cho th y l ưng tin t ươ ng h mơ t s ràng bu c gi a x i và yj, n u s ràng bu c y càng ch t ch thì l ưng tin v xi ch a trong y j càng ln, hay l ưng tin v y j ch a trong xi c ũng t ăng lên. T đĩ c ũng cĩ th gi i thích ý ngh ĩa c a l ưng tin nh ư là l ưng tin t ươ ng h c c đ i gi a xi và y j . Tính ch t 3: Lưng tin c a m t c p (x iyj) b ng t ng l ưng tin riêng c a t ng tin tr đi l ưng tin t ươ ng h gi a chúng. I(xi y j ) = I(xi ) + I(y j ) − I(xi , y j ) Khi xi và y j đc l p th ng kê I(xi , y j ) = 0 ði v i tr ưng h p ngu n ph c t p U=XYZ: 45
46. I(xi | zk ) = −log p(xi | zk ) ≥ I(xi , y j | zk ) . Gi i thích l ưng tin riêng cĩ điu ki n I(xi | zk ) , I(y j | zk ) c ũng t ươ ng t nh ư gi i thích l ưng tin riêng. L ưng tin riêng cĩ điu ki n chính là l ưng tin t ươ ng h v i cùng m t điu ki n đã xác đnh m t cách đơn tr gi a các tin vi nhau. Lưng tin t ươ ng h cĩ th phân thành t ng c a nh ng l ưng tin tươ ng h khác: I(xi , y j zk ) = I(xi , y j ) + I(xi , zk | y j ) 3.2.4 Lưng tin trung bình Lưng tin riêng ch cĩ ý ngh ĩa đ i v i m t tin nào đĩ, nh ưng khơng ph n ánh đưc giá tr tin t c c a ngu n. Nĩi m t cách khác I( x i ) ch đánh giá đưc v m t tin t c c a m t tin khi nĩ đ ng riêng r , nh ưng khơng th dùng đ đánh giá v m t tin t c c a t p h p trong đĩ xi tham gia. Trong th c t điu ta quan tâm là giá tr tin t c c a m t t p h p ch khơng ph i giá tr tin t c mt ph n t nào đĩ trong t p h p. ð đánh giá hồn ch nh giá tr tin t c c a mt tin xi trong c b ng tin ta dùng khái ni m l ưng tin trung bình. ðnh ngh ĩa: Lưng tin trung bình là l ưng tin t c trung bình ch a trong m t ký hi u b t k ỳ c a ngu n đĩ cho. IX()= − ∑ px ()log() px (3.6) x∈ X Ví d : Mt ngu n tin cĩ hai ký hi u là x0 , x1 v i xác su t p(x0 ) = 99 % và p(x1 ) = 1% . Nh ư v y khi nh n m t tin ta bi t g n nh ư ch c ch n là đĩ là x0 , tin này khơng cịn b t ng nên giá tr tin t c r t nh . Th nh ưng xét l ưng tin riêng c a x1 : I( x 1 )= − log0,01 ≈ 6,64 (bit/kí hi u) ðĩ là giá tr r t l n, điu đĩ khơng ph n ánh đúng giá tr c a tin nh ư đã xét trên. N u xét l ưng tin trung bình: I(X ) = − p(x0 )log p(x0 ) − p(x1 )log p(x1 ) = ,0 066 + ,0 014 = 0,08 (Bit/kí hi u) Nh ư v y l ưng tin trung bình r t nh ph n ánh đúng th c t giá tr c a ngu n tin. 46
47. Ta c ũng cĩ khái ni m l ưng tin t ươ ng h trung bình: p( x | y ) IXY(,)= ∑ pxy (,)log (3.7) x∈ X; y ∈ Y p( x ) Lưng tin cĩ điu ki n trung bình: IXY( /)= ∑ pxy (,)log(|) pxy (3.8) x∈ X; y ∈ Y Ta cĩ quan h gi a các l ưng tin trung bình: IXY(,)= IX () − IXY (|) IXY(,)= IYX (,)0 ≥ ði v i tr ưng h p ngu n ph c t p U= XYZ p( x | yz ) IXYZ(, )= ∑ pxyz (,,)log x∈ XyYz; ∈ ; ∈ Z p( x ) (3.9) p( x | yz ) IXYZ(,/)= ∑ pxyz (,,)log x∈ XyYz; ∈ ; ∈ Z p( x | y ) 3.3 Entropi c a ngu n r i r c 3.3.1 Khái ni m entropi Khi nh n đưc m t tin ta s nh n đưc m t l ưng tin trung bình, đng th i đ b t ng v tin đĩ c ũng đã đưc gi i thốt, cho nên đ b t ng và l ưng tin v ý ngh ĩa v t lý trái ng ưc nhau, nh ưng v s đo thì gi ng nhau và đưc xác đnh theo cơng th c sau: 1 H (x) = log p(x) ð b t ng trung bình c a m t tin thu c ngu n X (entropi c a ngu n) đưc xác đ nh theo cơng th c sau: H (X ) = −∑ p(x)log p(x) (3.11) x∈X 3.3.2 Tính ch t c a entropi Tính ch t 1: Entropi là m t đ i l ưng khơng âm: H(X) ≥ 0 47
48. Tính ch t 2: H(X) = 0 khi ngu n cĩ m t ký hi u b t k ỳ cĩ xác su t xu t hi n bng 1 và xác su t xu t hi n t t c các ký hi u cịn l i b ng khơng. Ngh ĩa là ngu n cĩ m t tin luơn đưc xác đ nh, nh ư v y giá tr thơng tin c a ngu n b ng khơng. Tính ch t 3: Entropi c c đ i khi xác su t xu t hi n c a các ký hi u b ng nhau Ch ng minh: Các giá tr p(x) làm c c đ i hàm H (X ) = −∑ p(x)log p(x) x∈X vi điu ki n ∑ p(x) = 1 c ũng chính là các giá tr p(x) làm c c đ i hàm x∈X   Φ= − ∑ p(x)log p(x) + λ ∑ p(x) −1 λ đưc g i là nhân t Lagrange. Các X  X  giá tr p(x) làm c c đ i hàm Φ th a mãn điu ki n: ∂Φ ∂Φ = 0 v i m i giá tr p(x) hay = −log p(x) − log e + λ =0 v i m i ∂p(x) ∂p(x) giá tr p(x) . Tc là các giá tr p(x) b ng nhau v i t t c các tin c a ngu n, và khi đĩ giá tr c c đ i c a H (X ) s là log 2 m n u l y đơn v là bit và ngu n cĩ m tin. Nu ngu n cĩ m ký hi u đ ng xác su t thì xác su t xu t hi n m t ký hi u là 1/ m khi đĩ: H (X ) = log m 3.3.3 Entropi đng th i và Entropi cĩ điu ki n Entropi đng th i Entropi đng th i là đ b t ng trung bình c a m t c p( x,y ) b t k ỳ trong t p tích XY . Theo đnh ngh ĩa v entropi cĩ: HXY(,)= − ∑ pxy (,)log(,) pxy (3.12) x∈ X; y ∈ Y Entropi cĩ điu ki n Khi c n đánh giá s ràng bu c th ng kê gi a các c p (x , y ) ta dùng khái ni m entropi cĩ điu ki n H( X | Y ) ho c H( Y | X ) . ðĩ là đ b t đ nh trung bình c a m t ký hi u b t k ỳ x∈ X khi đĩ bi t b t k ỳ m t ký hi u 48
49. y∈ Y . Xu t phát t các xác su t cĩ điu ki n p( x | y ) và p( y | x ) c ũng nh ư theo đnh ngh ĩa v entropi ta cĩ bi u th c đ nh ngh ĩa sau: HXY(|)= − ∑ pxy (,)log(|) pxy x∈ X; y ∈ Y (3.13) HYX(|)= − ∑ pxy (,)log(|) pyx x∈ X; y ∈ Y So sánh v i các bi u th c đ nh ngh ĩa cho các entropi, ta cĩ quan h sau: HXY(,)= HX () + HYX (|) (3.14) HXY(,)= HY () + HXY (|) Tr ưng h p ngu n ph c t p ði v i mã hĩa hay truy n tin ph c t p h ơn ta m r ng khái ni m entropi cho nh ng t p tích mà s các t p h p thành nhi u h ơn hai, ch ng h n tr ưng h p c a t p tích XYZ ta cĩ đnh ngh ĩa v entropi đ ng th i và cĩ điu ki n m r ng nh ư sau: HXYZ( )= − ∑ pxyz (,,)log(,,) pxyz x∈ XyYz; ∈ ; ∈ Z (3.15) HXYZ(| )= − ∑ pxyz (,,)log(|.) pxyz x∈ XyYz; ∈ ; ∈ Z 3.3.4 Entropi ngu n Markov Ngu n Markov gi vai trị quan tr ng trong l ĩnh v c truy n thơng. Nĩ đưc đ c tr ưng b i quan h p(x | x , x , ) = p(x | x ) trong đĩ x in jn−1 kn−2 in jn−1 in là ký hi u xi c a ngu n X xu t hi n th i đim n. ðiu này cĩ ngh ĩa là xác su t t o ra m t ký hi u nào đĩ t i th i đim n ch ph thu c vào ký hi u đã t o ra th i đim th n-1 và khơng ph thu c vào các ký hi u đã t o ra các th i đim n-2, n-3, Ti th i đim n, ngu n cĩ th tr ng thái j v i xác su t p(x / x ) jn in−1 nào đĩ khi th i đim n-1 ngu n đã tr ng thái i. Xác su t p(x / x ) = p g i là xác su t chuy n đ i t tr ng thái i sang jn in−1 ji m tr ng thái j, trong đĩ ∑ p ji = 1 ( m là s tin thu c ngu n). j=1 49
50. Xác su t đ ngu n tr ng thái j t i th i đim n là: m p(x j ) = ∑ p(xi ) p ji j = 2,1 , , m n n−1 i=1 Bi u di n d ưi d ng ma tr n ta cĩ :  p(x )   p(x )  1n 1n−1  p11 p12 p1m        p(x ) p(x ) p p p  2n   2n−1   21 22 2m  Ρn =   Ρn−1 =   Τ =          p(x )  p(x ) p p p  mn   mn−1   m1 m2 mn  T Mi quan h trên cĩ th vi t : Ρn = Τ Ρn−1 Nu ngu n đang tr ng thái i thì s cĩ m t đ bt đ nh v tr ng thái c a ngu n th i đim sau, đĩ là tr ng thái j, tr ng thái này là m t trong các tr ng thái cĩ th c a ngu n. Giá tr trung bình c a đ b t đ nh này đưc xác đ nh b i m entropi H i = −∑ p ji log p ji j=1 Nu tính t i t t c các tr ng thái ca ngu n, entropi c a ngu n là giá tr trung bình c a entropi ngu n X m i tr ng thái : H = ∑ p(xi )H i 3.4 Mi quan h gi a l ưng tin t ươ ng h trung bình và Entropi p( x | y ) IXY( , )=∑ pxy ( , )log = ∑ pxy ( , )(log pxy ( | ) − log px ( )) xXyY∈∈; p( x ) xXyY ∈∈; =∑pxy(,)log(|) pxy − ∑ pxy (,)log() px xXyY∈∈, xXyY ∈∈, =HX() − HXY (|) Vy : IXY(,)= HX () − HXY (|) IXY(,)= HY () − HYX (|) Suy ra IXY(,)= HX () + HY () − HXY (,) Nu X,Y đ c l p th ng kê thì : I( X , Y )= 0 50
51. Và ta c ũng ch ng minh đưc HX()≥ HXY (|) HY()≥ HY (|) X Ví d : Cho s ơ đ truy n tin : p( y0 | x 0 ) x0 y0 p( y1 | x 0 ) p( y | x ) 0 1 p(y | x ) x y 1 p( y | x ) 1 1 1 Hình 3.3 1 3 Bi t : px()= ;() px = 04 1 4 pyx(00 | )== pyx (|)2/3; 11 pyx (| 10 ) == pyx ( 91 |)1/3 + Tính Entropi đu vào c a kênh : HX( )=− ( px (0 )log px ( 0 ) + px ( 1 )log px ( 1 )) = 0,81 + Tính Entropi đu ra : py(0 )= pxpyx ()( 0 00 | ) + pxpyx ()( 101 |) = 0,417 py()1= pxpyx ()( 0 10 | ) + pxpyx ()( 111 | ) = 0,583 HY()=− ( py (0 )log py ( 0 ) + py ( 1 )log py ( 1 )) = 0,98 + Tính H(X,Y) Áp d ng cơng th c : HXY(,)= − ∑ pxy (,)log(,) pxy x∈ X; y ∈ Y pxy(00 , )= pxpy ( 0 )( 00 | x ) = 0,17 pxy(01 , )= pxpyx ( 0 )( 10 | ) = 0,08 pxy(,10 )= pxpy ()( 1 01 | x ) = 0,25 pxy(,11 )= pxpy ()( 1 11 | x ) = 0,5 51
52. H( X , Y )= 1,73 + Tính H( X | Y ) HXY( | )= HXY ( , ) − HY ( ) =−= 1,73 0,98 0,75 3.5 Tc đ l p tin ngu n r i r c và thơng l ưng kênh r i r c 3.5.1 Tc đ l p tin • Khái ni m Ngồi thơng s c ơ b n c a ngu n là Entropi ta th y s hình thành thơng tin nhanh hay ch m đ đưa vào kênh l i tu ỳ thu c vào b n ch t v t lý c a ngu n nh ư quán tính, đ phân bi t Cho nên s ký hi u l p đưc trong m t đơn v th i gian r t khác nhau. Ví d : con ng ưi vì k t c u c a c ơ quan phát âm h n ch nên m t giây ch phát âm đưc t 5-7 âm ti t trong l i nĩi thơng th ưng, trong khi máy đin báo cĩ th t o ra t 50-70 ký hi u trong m t giây. Nh ư v y thơng s th hai c a ngu n là t c đ thi t l p tin R (L ưng thơng tin ngu n l p đưc trong m t đơn v th i gian), T c đ thi t l p tin t i đu vào kênh b ng tích c a entropi H (X ) v i s ký hi u n0 l p đưc trong mt đơn v th i gian, trong tr ưng h p dùng loga c ơ s hai thì đơ n v c a R là bit/sec. R = n0 H (X ) (3.16) Nh ư v y mu n nâng cao R thì ho c là t ăng n0 ho c là t ăng H (X ) . T ăng n0 ph thu c vào thi t b ph n c ng. T ăng H (X ) ta cĩ th thay đ i c u trúc th ng kê c a ngu n nh ư v y s đơn gi n khơng t n kém. Ta đã bi t n u xác su t xu t hi n các ký hi u b ng nhau thì H (X ) c c đi, do v y ta dùng phép mã hố đ th c hi n vi c này mã hố ngu n tin ban đu thành ngu n tin mã hố sao cho xác su t các ký hi u t ươ ng đươ ng nhau. Ví d : Cho ngu n tin X = {x1 , x2 , x3 , x4 } v i xác su t t ươ ng ng là : p(x1 ) = ;2/1 p(x2 ) = ;4/1 p(x3 ) = ;8/1 p(x4 ) = 8/1 H (X ) = 8/7 52
53. Nu cĩ m t tin g m các ký hi u : x1 x1 x4 x2 x1 x2 x1 x3 . ð cĩ H (X ) c c đ i ph i cĩ xác su t các ký hi u b ng nhau b ng 1/8 Mu n v y ta mã hố ngu n X trên thành ngu n Ynh ư sau : x1 = y0 x = y y 2 1 0 x3 = y1 y1 y0 x4 = y1 y1 y1 Ta đưc dãy các ký hi u c a tin : y0 y0 y1 y1 y1 y1 y0 y0 y1 y0 y0 y1 y1 y0 Ngu n này cĩ H (Y ) = 1 Mã hố ngu n này thành ngu n Z v i các ký hi u sau : z1 = y0 y0 z = y y 2 0 1 z3 = y1 y0 z4 = y1 y1 Ta đưc dãy các ký hi u c a tin : z1 z4 z4 z1 z3 z2 z3 Xác su t các ký hi u c a ngun Z b ng nhau và b ng 1/4 nên : H (Z) = log 4 = 2 Vy b ng phép mã hố ngu n X thành ngu n Z ta cĩ th nâng Entropi ca ngu n X là H (X ) = 7/4 thành Entropi H (Z) = 2 mà v n đ m b o l ưng tin trong các b n tin đưc b o tồn và cĩ cùng giá tr là 14 (bit) • ð d ư c a ngu n ð ch ra s chênh l ch gi a entropi c a ngu n và giá tr c c đ i cĩ th cĩ c a nĩ ta dùng đ d ư c a ngu n: RHX=()max − HX () (3.17) Ngồi ra cũng cĩ th dùng đ d ư t ươ ng đi c a ngu n đ đánh giá: HX()− HX () HX () r =max =1 − (3.18) HX()max HX () max 53
54. 3.5.2 Thơng l ưng kênh Thơng l ưng kênh C là l ưng tin c c đ i kênh cho đi qua trong m t đơn v th i gian mà khơng gây ra sai nh m. Vy: C= R max ðơ n v c a thơng l ưng kênh là bit/giây. Nh ư v y R≤ C Nhi m v c a mã hố th ng kê là b ng cách mã hố đ thay đ i Entropi ca ngu n đ thay đ i t c đ l p tin R sao cho x p x v i C , g i là ph i h p gi a ngu n v i kênh v ph ươ ng di n t c đ truy n tin. Khi truy n tin trong kênh cĩ nhi u thì nhi m v c a mã hĩa là l i d ng điu ki n R C đưc, đĩ là gi i h n c a vi c mã hố. Trong tr ưng h p mã hố sao cho R = C đưc g i là ph ươ ng pháp mã hố t i ưu. Sau khi mã hố ta cĩ H (X ) max . Gi a H (X ) max và H (X ) ban đu ta cĩ đ chênh l ch g i là đ d ư t ươ ng đi c a ngu n. HX()− HX () HX () r =max =1 − (3.19) HX()max HX () max Vy phép mã hố t i ưu c ũng cĩ th coi là ph ươ ng pháp làm gi m đ d ư ca ngu n ban đ u. 54
55. Thơng l ưng kênh r i r c cĩ nhi u Thơng th ưng t c đ l p tin bé h ơn nhi u so vi thơng l ưng kênh, nhi m v c a mã hĩa th ng kê là thay đi t c đ l p tin c a ngu n b ng cách thay đi entropi, đ t c đ l p tin ti m c n v i thơng l ưng, g i là ph i h p vi ngu n và kênh v ph ươ ng di n t c đ truy n tin. Trong tr ưng h p tin nh n đưc sau khơng ph thu c nh ng tin nh n đưc tr ưc, nĩi cách khác chúng đ c l p th ng kê v i nhau thì đ chính xác ca tin truy n đi trong kênh ch cịn b nh h ưng c a nhi u là gi m đi, khi đĩ tc đ l p tin t i đ u ra c a kênh đưc đ nh ngh ĩa nh ư sau: R= nIXY0(,) = nHX 0 (() − HXY (|)) (3.20) n0 H (X | Y ) v m t đ l n là l ưng tin b nhi u phá h y trong m t đơn v th i gian, v y mu n nâng cao t c đ l p tin thì nh t thi t ph i thay đ i thơng s c a ngu n. Lúc đĩ l ưng tin t i đa mà kênh cho đi qua khơng x y ra sai nh m s là t c đ l p tin c c đ i trong kênh cĩ nhi u: C= nHX0(() − HXY ( |)) max (3.21) ð d ư t ươ ng đi cịn cĩ th đưc xác đ nh theo cơng th c sau: R r = 1− ; Hi u qu s d ng kênh: λ = 1− r c C c c 55
56. CH ƯƠ NG 4. LÝ THUY T MÃ 4.1 Khái ni m mã và điu ki n thi t l p mã Trong các h th ng truy n tin r i r c ho c truy n các tín hi u liên t c nh ưng đã đưc r i r c hĩa, b n tin th ưng ph i thơng qua m t s phép bi n đi hay cịn g i là mã hĩa phía ngu n phát, phía thu tin cn ph i thơng qua nh ng phép bi n đ i ng ưc l i là gi i mã. S mã hĩa thơng tin cho phép ta ký hi u hĩa thơng tin hay s d ng các ký hi u quy ưc đ bi u di n b n tin d ng phù h p cho n ơi s d ng. Chính nh mã hĩa, ta cĩ th hi n th đưc thơng tin, thơng tin cĩ b n ch t là các khái ni m. ð i v i m t h th ng truy n tin, vi c mã hĩa cho phép t ăng tính h u hi u và đ tin c y c a h th ng truy n tin, ngh ĩa là t ăng t c đ truy n tin và tăng kh n ăng ch ng nhi u c a h th ng. Khi t c đ l p tin R c a ngu n cịn cách xa thơng l ưng C c a kênh, nhi m v c a mã hĩa là bi n đ i tính th ng kê c a ngu n làm cho t c đ l p tin ti p c n v i kh n ăng truy n c a kênh. Trong tr ưng h p truy n tin trong kênh cĩ nhi u, điu c n quan tâm nhi u là đ chính xác c a s truy n tin, hay các tin truy n đi ít b sai nh m. ðây chính là nhi m v th hai c a mã hĩa. Trong ch ươ ng này, tr ưc tiên ta đ c p t i các khái ni m và đnh ngh ĩa v mã: th nào là mã hi u? các thơng s c ơ b n c a mã hi u là gì? các điu ki n và yêu c u đ i v i mã hiu là gì? 4.1.1 Mã hi u và các thơng s c ơ b n ðnh ngh ĩa: Mã hi u là m t ngu n tin v i m t s ơ đ th ng kê đưc xây d ng nh m tho mãn m t s yêu c u do h th ng truy n tin đ t ra nh ư t ăng t c đ lp tin, t ăng đ chính xác cho các tin Nh ư v y mã hi u chính là m t t p h u h n các ký hi u riêng hay b ng ch riêng cĩ phân b xác su t th a mãn m t s yêu c u quy đ nh. - Vi c mã hố là phép bi n đ i 1 – 1 gi a các tin c a ngu n đưc mã hố vi các t mã do các d u mã t o thành. Cho ngu n S (A,P) v i A- t p kí hi u ngu n, P-xác su t t ươ ng ng. Khi đĩ phép mã hĩa là song ánh f: A -> M, M là t p các t mã t ươ ng ng. 56
57. - S các ký hi u khác nhau trong b ng ch c a mã g i là c ơ s mã ( m) mi ký hi u cĩ m t s tr nào đĩ tu ỳ theo c u trúc c a b mã (ví d mã nh phân m = 2 s d ng hai ký hi u là 0 và 1, đĩ là lo i mã đưc dùng r ng rãi nh t. - S các ký hi u trong m t t mã g i là đ dài t mã n. N u các t mã trong b mã cĩ đ dài b ng nhau g i là mã đng đ u, đ dài t mã khơng b ng nhau g i là mã khơng đu. Mã khơng đu ta cĩ khái ni m đ dài trung bình ca t mã tính nh ư sau: N n= ∑ pxn(i ) i (4.1) i=1 Trong đĩ: p(xi ) : Xác su t xu t hi n c a tin xi đưc mã hố thành t mã th i ni : ð dài t mã ng v i tin xi N : T ng s t mã c a b mã t ươ ng ng v i t ng s các tin xi S t mã N chính là t ng s các t mã cĩ trong m t b mã sau khi mã hố m t ngu n nào đĩ. V i b mã đu theo lý thuy t ta cĩ N = m n Ví d : M t b mã nh phân m i t mã cĩ đ dài 5 bit ta cĩ N = 2 5 = 32 t Nu ta dùng h t các t mã hay N = mn g i là mã đy, n u ta dùng s t mã N < mn g i là mã v ơi. Nh ư v y trong th c t s d ng ta th y cĩ th cĩ hai lo i mã. V i mã đu các t mã hay b sai nh m gi a t này v i t khác nên dùng b mã này ta ph i nghiên c u cách phát hi n sai và s a sai. V i mã khơng đu ta ph i ch n đ dài các t mã sao cho đ dài trung bình c a t mã là ng n nh t g i là mã th ng kê t i ưu. - Giá tr riêng hay cịn g i là tr c a m i ký hi u mã. M i mã hi u cĩ m ký hi u mã khác nhau, n u c ơ s c a nĩ là m. M i ký hi u mã là m t d u hi u riêng, và chúng đưc gán m t giá tr xác đ nh theo m t đ đo xác đ nh, các giá tr này đưc g i là các giá tr riêng c a các ký hi u mã và ký hi u là a, trong tr ưng h p s , m i ký hi u mã đưc gán m t giá tr riêng n m trong kho ng t 0 t i m-1. - Ch s v trí ca ký hi u mã trong t mã: ta g i m t v trí mã là m t ch trong t mã đ đ t m t ký hi u mã vào đĩ. M t t mã cĩ n ký hi u mã s cĩ n 57
58. v trí mã. M t v trí mã nh phân cịn đưc g i là v trí nh phân hay m t bit. Mt v trí mã th p phân cịn đưc g i là m t v trí th p phân hay m t digit. Ch s v trí là s hi u c a v trí mã trong t mã theo m t cách đánh s c th . Hi n nay ta th ưng đánh s v trí mã bên ph i nh t c a t mã là v trí 0 và sau đĩ c dch sang trái m t v trí thì ch s v trí t ăng thêm m t. - Tr ng s v trí ωi (i=1 n) là m t h s nhân làm thay đi giá tr c a ký hi u mã khi nĩ n m các v trí khác nhau. Tr ng s v trí này ph thu c vào mi mã hi u c th . Trong tr ưng h p s , tr ng s v trí là l ũy th a b c ch s v trí c a c ơ s c a mã. - Tr ng s c a t mã b: là t ng các giá tr c a các ký hi u mã cĩ trong t mã. n−1 b= ∑ a kω k (4.2) k=0 trong đĩ ak là giá tr riêng c a ký hi u mã v trí k. Trong tr ưng h p mã hi u n−1 k là h đ m thì tr ng s c a t mã là: b = ∑ak m k =0 - Kho ng cách mã D: Kho ng cách mã là kho ng cách gi a hai tr ng s ca hai t mã tùy vào vi c đnh ngh ĩa giá tr riêng và tr ng s v trí c a các ký hi u mã, ta s cĩ nh ng đ nh ngh ĩa khác nhau cho kho ng cách mã. 4.1.2 ðiu ki n thi t l p b mã Ta đã nĩi trong ph n trên là m i t mã là m t t h p mã dùng đ mã hĩa mt tin hay m t kh i tin c a ngu n. V n đ là cĩ điu ki n nào ràng bu c đ mt t h p mã s đưc hay khơng đưc dùng làm m t t mã. Nh ng điu ki n này s đưc g i là điu ki n thi t l p mã, chúng s th hi n nh ư th nào và ki m tra chúng nh ư th nào là v n đ chúng ta s ph i xác đ nh trong ph n này. Tr ưc h t ta s phát bi u nh ng điu ki n thi t l p mã và sau đĩ s đi tìm th hi n c a chúng và cách ki m tra chúng. • ðiu ki n chung Các tin truy n đi đưc mã hố thành dãy các ký hi u liên ti p, khi nh n tin ta ph i gi i mã đưc đ thu đưc thơng tin. Mun v y các ký hi u ph i đưc s p x p theo quy lu t nào đĩ đ tách đúng thơng tin ban đ u. Ví d : ta cĩ 4 tin a, b, c, d đưc mã hố b ng b mã nh phân nh ư sau: 58
59. a=00 b=01 c=10 d=11 Mt tin ‘aaabcdb’ đưc mã hố nh ư sau: ‘00000001101101’ và truy n đi . Khi nh n đưc tin và gi i mã, n u xác đ nh đưc g c c a dãy ký hi u trên, chúng ta ch cĩ th tách m t cách duy nh t thành dãy tin ban đu b ng cách t g c tr đi chia thành t ng nhĩm hai ký hi u mã t ươ ng ng. Nh ư v y b mã trên cho phép phân tích các t mã m t cách duy nh t và đưc g i là mã phân tách đưc. Cũng tin trên n u ta mã b ng b mã khác: a=0 b=01 c=101 d=1 Vn ngu n trên mã theo b mã này ta đưc: ‘00001101101’. Khi nh n tin và gi i mã ta cĩ th gi i mã nh ư sau: ‘aaaaddbdb’ ho c ‘aaabcdb’. Nh ư v y tin nh n đưc s sai l c so v i ngu n vì v y b mã này khơng dùng đưc. V y khái ni m mã phân tách đưc đ nh ngh ĩa nh ư sau: S t n t i quy lu t cho phép tách đưc m t cách duy nh t dãy các ký hi u mã thành các t mã đưc g i là điu ki n thit l p mã chung cho b mã. B mã th a mãn điu ki n thi t l p mã cịn đưc g i là b mã phân tách đưc. • ðiu ki n riêng cho t ng loai mã (mã đu và khơng đu) ði v i m i b mã cịn t n t i nh ng điu ki n riêng ph i đưc th a mãn khi thi t l p nĩ. - Vi mã khơng đu (mã th ng kê t i ưu) ta ph i ch n b mã sao cho đt đưc đ dài trung bình mã t i thi u. - Vi mã đu (mã s a sai) thì b mã cĩ kh n ăng phát hi n và s a sai càng nhi u càng t t. Các điu ki n riêng cho m i b mã chính là nh ng điu ki n v hình th c, v yêu c u k thu t ho c ch tiêu k thu t riêng mà b mã c n đ t đưc. Các điu ki n này là khác nhau v i m i lo i mã c th . 59
60. 4.2 Các ph ươ ng pháp bi u di n mã 4.2.1 Bi u di n b ng b ng li t kê (B ng đ i chi u mã) ðây là cách trình bày b mã đơ n gi n nh t. Ng ưi ta dùng b ng li t kê nh ng tin c a ngu n và mã t ươ ng ng c a nĩ, b ng li t kê cĩ ưu đim là cho th y c th t c th i tin và t mã nh ưng cĩ nh ưc đim là c ng k nh và khơng cho th y t m quan tr ng khác nhau c a t ng t mã. Ví d : Bi u di n mã bng b ng nh ư sau: Tin a1 a2 a3 a4 a5 T mã 00 01 100 1010 1011 4.2.2 Bi u di n b ng t a đ mã Mi t mã cĩ hai thơng s cĩ th xác đ nh duy nh t mà khơng b nh m ln gi a các t mã v i nhau đĩ là đ dài n và tr ng s b, ngh ĩa là khơng t n t i hai t mã bng nhau đ ng th i c đ dài n và tr ng s b. Mt t a đ mã là m t bi u di n d a trên hai thơng s c a t mã là đ dài t mã n và tr ng s b đ l p m t m t ph ng cĩ hai t a đ , trên đĩ m i t mã đưc bi u di n b ng m t đim. Tr ng s b c a t mã là t ng trng s các ký hi u trong t mã. Tr ng s b đưc tính theo cơng th c: n−1 k b = ∑ak m (4.3) k =0 k: Là s th t c a ký hi u th k trong t mã ak: Là tr c a ký hi u th k (ví d mã nh phân cĩ hai tr là 0 và 1) m: Là c ơ s mã (mã nh phân m = 2) Ví d 1: Tính tr ng s c a các t mã nh phân sau: T mã 1011 ta cĩ b = 1.2 0 + 1. 2 1 + 0. 2 2 + 1. 2 3 = 11 T mã 011 ta cĩ b = 1. 2 0 + 1. 2 1 + 0. 2 2 = 3 Ví d 2 : Cho các t mã sau : a1 = 00 n1 = 2 b 1 = 0 a2 = 10 n2 = 2 b 2 = 2 a3 = 100 n3 = 0 b 3 = 4 a4 = 101 n4 = 3 b 4 = 5 60
61. • ðnh lý. Khơng cĩ hai t mã mã hĩa hai tin khác nhau c a cùng m t b mã th a mãn đng th i n i = n j và b i = b j ( i ≠ j ) 4.2.3 ð hình mã Các ph ươ ng pháp đ hình s d ng m t đ hình đ bi u di n m t mã hi u, nĩ cho phép trình bày mã m t cách g n h ơn các b ng mã đng th i cho th y rõ các tính ch t quan tr ng c a mã hi u m t cách tr c quan h ơn. Các ph ươ ng pháp bi u di n mã hi u b ng đ hình g m cĩ cây mã và đ hình k t cu. • Bi u di n b ng cây mã Cây mã là mt đ th hình cây bi u di n mã cĩ các nút và nhánh, cây cĩ mt nút g c duy nh t t m t nút cĩ nhi u nh t là m nhánh (m là c ơ s mã) m i nhánh là tr c a ký hi u, m i nhánh k t thúc m t nút cao h ơn. Nút cu i là đc tr ưng cho m t t mã hình thành t các tr trên các nhánh. Các t mã m c trên cĩ t m qua tr ng cao h ơn các t mã m c d ưi. Ví d : Cĩ cây mã nh phân cĩ 5 t mã sau: Mc 0 0 1 Mc 1 0 1 0 Mc 2 00 01 0 1 Mc 3 Mc 3 100 0 1 Mc 4 1010 1011 Hình 4.1 Trong ví d trên cho th y khi nhìn vào cây mã ta bi t cây mã cĩ ph i là cây mã đng đ u hay khơng đ ng đ u, lo i mã đy hay v ơi. • ð hình k t c u Ph ươ ng pháp này ta dùng m t đ th cĩ h ưng g m các nút và các nhánh, m i nhánh là m t cung cĩ h ưng, m i t mã là m t chu trình theo chi u c a cung đi t g c. Ph ươ ng pháp này bi u di n t mã g n nh và tr c quan 61
62. Ví d : Bi u di n b mã nh phân b ng đ th : G c 1 1or 0 0 0 0 1or 0 1 Hình 4.2 Sơ đ này ta cĩ 5 t mã sau: 00, 01, 100, 1010, 1011 ð hình k t c u khơng nh ng dùng đ mơ t b n thân t mã mà cịn dùng đ xét cách v n hành thi t b mã hĩa và gi i mã nh ư là m t đ th mơ t tr ng thái c a thi t b . 4.2.4 Ph ươ ng pháp hàm c u trúc mã Ph ươ ng pháp này nĩi lên m t đc tính quan tr ng c a mã là s phân b các t mã cĩ đ dài khác nhau, ký hi u b ng G(ni ) : s t mã cĩ đ dài là ni . T hàm c u trúc cĩ th phân bi t đưc mã đu ho c khơng đ u. C ũng t hàm cu trúc ta hồn tồn cĩ th xác đ nh đưc b mã cĩ th a mãn điu ki n phân tách đưc hay khơng. 4.3 Mã cĩ tính phân tách đưc, mã cĩ tính prefix Trong m c này ta xét các tiêu chu n đưc s d ng đ đánh giá m t mã hi u cĩ th a mãn điu ki n thi t l p mã hay khơng. Ta bi t r ng điu ki n chung đ thi t l p mã là mã ph i phân tách đưc cho nên tiêu chu n thi t l p mã chính là tiêu chu n đ mã phân tách đưc hay chính là nh ng tiêu chu n cho phép tách đúng t ng t mã t chu i mã nh n đưc. Lưu ý gi a t mã và tin đưc mã hĩa cĩ quan h 1-1 thì vi c gi i mã phía thu s bao g m vi c tách đúng t mã và chuy n ng ưc t mã thành tin tươ ng ng. 62
63. Vi c chuy n t mã thành tin đưc th c hi n nh m t s ơ đ gi i mã xác đnh. Vi c tách đúng các t mã là m t thu t tốn ki m tra tính đúng c a m t s tiêu chu n đưc g i là điu ki n phân tách c a mã hi u, vic ki m tra này s b t đ u t ký hi u mã đu tiên c a chu i cho đ n khi cĩ th c t đưc m t t mã thì nĩ s c t t mã và l i coi ký hi u ti p sau làm ký hi u đ u tiên c a chu i đ ki m tra ti p. Mt trong nh ng cách ti p cn c ơ b n nh t là trong b ng mã, hãy ch n 1 t mã trùng v i ph n đ u c a xâu mã sau đĩ xĩa ph n đ u c a xâu mã và g p kí hi u t ươ ng ng vào xâu g c, quá trình s d ng khi xâu mã đĩ b xĩa h t. Thu t tốn gi i mã cĩ th mơ ph ng như sau Procedure Giai_Ma; Input st:string;{Xau da ma hoa} x:array[1 N] of char;{Bang ki hieu} b:array[1 N] of string;{Bang ma tuong ung} Output xaugoc:string;{xau goc ban dau} BEGIN xaugoc:=’’; while length(st)>0 do for i:=1 to N do if b[i]=copy(st,1,lenght(b[i])) then begin xaugoc:=xaugoc+x[i]; delete(st,1,lenght(b[i])); end; END; 4.3.1 ðiu ki n đ mã phân tách đưc Ta th y khi nh n đưc m t dãy ký hi u mã đ cĩ th phân tách t mã mt cách duy nh t và đúng đn b mã ph i tho mãn điu ki n c n và đ là: “ Bt k ỳ dãy t mã nào c a b mã c ũng khơng đưc trùng v i m t dãy t mã khác ”. Ví d : Cho b mã cĩ các t mã sau: 00 01 11 100 1010 1011 63
64. Nu nh n đưc dãy: ‘1000101001011101101’ Ta ch cĩ th tách đưc duy nh t thành: ‘100-01-01-00-1011-1011-01’. Nh ư v y b mã trên là lo i b mã phân tách đưc Khái ni m đ ch m gi i mã là s ký hi u nh n đưc c n thi t ph i cĩ mi phân tách đưc m t t mã. ð ch m gi i mã cĩ th là h u h n nh ưng cũng cĩ th là vơ h n. ð xác đ nh tính phân tách đưc c a mt b mã và đ ch m gi i mã h u h n hay vơ h n ta xây d ng b ng th nh ư sau: Bưc 1 : S p x p các t mã vào c t đ u tiên c a b ng (c t 1) Bưc 2 : So sánh các t mã ng n v i các t mã dài h ơn trong c t 1, n u t mã ng n gi ng ph n đ u t mã dài thì ghi ph n cịn l i trong t mã dài sang c t 2. Bưc 3 : ði chi u các t h p mã trong c t 2 v i các t mã trong c t 1 l y ph n cịn l i ghi vào c t ti p theo (c t 3). Bưc 4 : ði chi u các t h p mã trong c t 3 v i các t mã trong c t 1 th c hi n gi ng nh ư trên cho đn khi cĩ m t c t tr ng thì d ng. ðiu ki n c n và đ đ mã cĩ th phân tách là trong c t j ≥ 2 khơng cĩ t h p nào trùng v i m t t mã trong c t 1. ð rõ h ơn v thu t tốn ta quan sát các ví d sau: Ví d 1: 1 2 3 00 - - 01 - - 100 - - 1010 - - 1011 - - Bng th cĩ các c t t th 2 là r ng nên b mã này phân tách đưc, đ ch m gi i mã c a b mã này b ng đ dài t mã. Nh ư v y cĩ th nĩi cách khác là đ cĩ tính phân tách đưc điu ki n c n và đ là b t k ỳ t mã nào c ũng khơng đưc trùng v i ph n đ u c a t mã khác trong cùng b mã. 64
65. Ví d 2: 1 2 3 4 5 10 0 1 0 100 1 11 00 01 - 0 1 011 - 00 11 Trong các c t t 2,3, c a b ng th này khơng cĩ t h p mã nào trùng v i các t mã trong c t 1, nh ưng cĩ th đin các c t j đn vơ h n mà khơng g p c t tr ng. B mã này phân tách đưc nh ưng vì đ ch m gi i mã là vơ h n nên trong tr ưng h p này cĩ th coi b mã là khơng phân tách đưc. ð ch m gi i j−1  j mã đưc tính theo cơng th c sau: n≤ T ≤ n . Trong đĩ j là 2minch  2 m ax s hiu c t r ng; nmin, n m ax t ươ ng ng là đ dài t mã ng n nh t và đ dài t mã dài nh t. 4.3.2 Mã cĩ tính prefix Trong các lo i mã cĩ tính phân tách đưc, lo i mã mang nhi u đ c đim cĩ ích cho vi c khai thác s d ng và đưc nghiên c u nhi u là mã cĩ tính prefix. Prefix c a m t t h p mã là b ph n c a t h p mã đĩ sau khi b đi m t hay nhi u ký hi u t bên ph i Ví d 1: Cho t h p mã: 01100 1110 Cĩ các prefix sau: 01100111 0110011 011001 01100 0110 011 01 0 65
66. Mã cĩ tính prefix đưc đ nh ngh ĩa như sau: Mt b mã đưc g i là mã cĩ tính prefix n u b t k ỳ t mã nào c ũng khơng ph i là ph n đ u c a b t k ỳ mt t mã khác trong b mã. Khi bi u di n b ng cây mã, ta nh n th y b mã cĩ tính prefix khi các t mã ch là nút lá. Mã đy là b mã cĩ tính prefix . Ví d 2: Cây mã sau bi u di n m t b mã prefix 0 1 0 1 1 00 0 1 010 011 Hình 4.3 4.3.3 Bt đ ng th c Kraft ð đưa ra đưc điu ki n t ng quát v tính phân tách đưc c a t mã, ta cĩ nh n xét sau đ i v i mã cĩ tính prefix v i c ơ s mã là m : G )1( ≤ m G )2( ≤ m 2 − mG )1( G )3( ≤ m3 − m 2G )1( − mG )2( G(n) ≤ m n − m n−1G )1( − − mG (n − )1 n G( j) Vì v y: ∑ j ≤ 1 hay cĩ th vi t t ươ ng đươ ng nh ư sau: j=1 m N 1 ∑ ≤ 1 . B t đ ng th c này đưc g i là B t đ ng th c Kraft. Trong đĩ N ni i=1 m là s t mã t ươ ng ng v i s tin c a ngu n, ni là đ dài t mã mã hĩa tin ui . Ng ưc l i m t dãy s nguyên n1, n 2 , , n N th a mãn B t đ ng th c Kraft thì s t n t i b mã cĩ tính prefix nh th t c t o mã prefix, điu này cĩ th m r ng cho t t c các lo i mã phân tách đưc cĩ ho c khơng cĩ tính prefix. 66
67. Th t c t o mã prefix Bưc 1 : S p x p các t mã theo th t t ăng d n c a t mã: n1≤ n 2 ≤ ≤ n N ; xây d ng cây đ y đ , m i nút cĩ m nhánh, đ cao là nN +1. Bưc 2 : m c n1 ch n m t nút b t k ỳ, và gán mã là t mãC1 và xĩa các nút k sau nĩ. Bưc 3 : L p l i B ưc 2 đ i v i m c n2, n 3 , , n N ta đưc các t mã C1, C 2 , , C N . 4.4 Mã th ng kê t i ưu 4.4.1 Gi i h n đ dài trung bình c a t mã • Gi i h n d ưi Ta ph i xác đ nh đ dài trung bình c a t mã đ đ t đưc tiêu chu n t i ưu nh ư đã phân tích trên. Gi s cĩ ngu n tin U = {u1 ,u2 , , u N } v i các xác su t t ươ ng ng p(ui ) l ưng tin trung bình là H (U ) . Ta ch n b mã X cĩ c ơ s m sao cho các xác su t p(xi ) x p x b ng nhau, khi đĩ l ưng tin c a m t ký hi u mã là : I(X ) = log m Trong tr ưng h p mã nh phân thì ta cĩ I(X ) = 1 (bit/k.h) Nu t mã cĩ đ dài ni thì l ưng tin ch a trong t mã s là ni log m . Nu các t mã cĩ đ dài khơng b ng nhau thì l ưng tin s b ng n log m trong đĩ n là đ dài trung bình c a t mã. Mã hố ngu n U trên v i b mã X . ð đ m b o khơng b m t mát thơng tin thì 1 log N N p( u i ) 1 1 nmIunilog≥ () ii ⇔ ≥ ⇒ ∑ npu ii ()≥ ∑ pu ()log i logmi=1 log m i = 1 pu (i ) H( U ) Vì v y : nlog m≥ HU ( ) ⇒ n ≥ log m 67
68. Nh ư v y đ dài trung bình c a t mã khơng nh h ơn t s entropi c a ngu n và l ưng tin trung bình c c đ i c a m t ký hi u mã. Vi mã nh phân ta cĩ n ≥ H(U), đĩ là gi i h n d ưi c a đ dài trung bình c a t mã. Du ‘=’ x y ra khi ni = I(ui ) . Nu mã hĩa tin b ng m t mã nh phân cĩ chi u dài ni thì l ưng tin ch a trong t mã s là ni bit. Nu l y đ dài trung bình t mã thì ta s đưc l ưng tin trung bình ch a trong t mã. Thơng th ưng I(ui ) khơng ph i là s nguyên nên điu ki n trên ch là điu ki n gi i h n mà d a vào đĩ cĩ th xây d ng đưc các thu t tốn xác đ nh mã th ng kê t i ưu. • Gi i h n trên ð th a mãn tiêu chu n c a mã th ng kê t i ưu thì đ dài trung bình ph i cĩ gi i h n sau: H (U ) H (U) ≤ n ≤ +1 (4.4) log m log m Mã nh phân thì: H (U ) ≤ n ≤ H (U ) +1. Nh ư v y cĩ th xây d ng b mã v i đ dài trung bình khơng l n h ơn t s entropi c a ngu n v i l ưng tin trung bình c c đ i ch a trong m t ký hi u cng 1 đơn v . Tĩm l i b mã cĩ đ dài trung bình n tho mãn các điu ki n trên g i là mã th ng kê t i ưu. M t b mã nh ư v y ph i tho mãn nh ng đ c đim sau: • Các ký hi u ph i cĩ cùng xác su t. • S xu t hi n c a các ký hi u trong t mã là đc l p v i nhau t c là xác su t xut hi n c a ký hi u sau khơng ph thu c vào s cĩ m t c a các ký hi u ra tr ưc. 4.4.2 Tiêu chu n mã th ng kê t i ưu Nh ư đã đ c p ph n tr ưc v chi u dài trung bình c a t mã, tiêu chu n c a mã th ng kê t i ưu là đt đ n chi u dài trung bình c a t mã t i thi u. ðây là m t h ưng l n c a mã hĩa (mã nén d li u). Do các tin c a ngu n tin cĩ xác su t xu t hi n khác nhau, nên vi c dùng các t mã cĩ đ dài nh đ mã hĩa cho các tin cĩ xác su t xu t hi n cao s làm cho s ký hi u c n 68
69. thi t đ mã hĩa cho m t chui các tin nh h ơn và tính kinh t cao h ơn. Tính kinh t c a b mã đưc đo b ng cơng th c H(U ) ρ = ) (4.5) n log m Vy nguyên t c c ơ b n c a mã th ng kê t i ưu da trên c ơ s : đ dài t mã ni t l ngh ch v i xác su t xu t hi n p(ui ) ngh ĩa là các t mã dài s dùng đ mã hĩa cho các tin cĩ xác su t xu t hi n nh và ng ưc l i. 4.4.3 Mã th ng kê Fano –Shanon Fano và Shanon đã đc l p nghiên c u và đ xu t ph ươ ng pháp xây d ng b mã th ng kê t i ưu, b n ch t c a hai ph ươ ng pháp là t ươ ng đươ ng nhau. ð thu n ti n trong vi c trình bày, các b mã xây d ng đưc t các thu t tốn này cĩ c ơ s mã m = 2 • Ph ươ ng pháp mã theo Fano Gi s cĩ ngu n tin U = {u1 ,u2 , , u N } v i các xác su t t ươ ng ng p(ui ) i = 2,1 , , N uk u1 u2 u3 uN pk p1 p2 p3 pN Nhà tốn h c Fano đ xu t thu t tốn mã hố nh ư sau: Bưc 1: S p x p các tin u i theo th t gi m d n c a xác su t. Bưc 2: Chia các tin làm hai nhĩm cĩ xác su t x p x b ng nhau. Nhĩm đ u ly tr 0, nhĩm sau l y tr 1. Bưc 3: L p l i b ưc 2 đ i v i các nhĩm con cho t i khi t t c các nhĩm ch cịn l i m t tin thì k t thúc thu t tốn. ð rõ h ơn v thu t tốn, ta xét ví d sau: Cho ngu n tin U g m 7 tin: U = {u1 ,u2 , , u7 } p(u ) Ln 1 Ln 2 Ln 3 Ln 4 Ln 5 T mã ui i 0,34 0 0 00 u1 0,23 0 1 01 u2 69
70. 0,19 1 0 10 u3 0,10 1 1 0 110 u4 0,07 1 1 1 0 1110 u5 0,06 1 1 1 1 0 11110 u6 0,01 1 1 1 1 1 11111 u7 ð dài trung bình c a t mã: n = 0,01.5 + 0,06 .5 + 0,07.4 + 0,10. 3 + 0,19. 2 + 0,23. 2 + 0,34 .2 = 2,41 H (U ) Tr s kinh t ρ = = 2,37 /2,41 = 0,98. n Nh n xét: 1. Vi c s p x p ngu n theo xác su t gi m d n nh m m c đích đ y các tin cĩ xác su t cao lên đu b ng cùng v i vi c chia đơi ngu n d n t i các l p trên s k t thúc r t nhanh, vì v y các tin cĩ xác su t cao s cĩ đ dài t mã ng n dn t i đ dài trung bình c a b mã là nh . 2. ð ph c t p c a thu t tốn ph thu c vào vi c s d ng thu t tốn s p xp. N u s d ng thu t tốn s p x p đ quy thì đ ph c t p s là O( n log n ) . 3. Xu t phát t thu t tốn Fano, ta cĩ th m rng cho vi c t o b mã v i cơ s m b t k ỳ b ng cách trong b ưc 2 ta chia thành m l p và l y các tr t 0 đn m −1 4. Trong tr ưng h p khi cĩ nhi u tin v i xác su t b ng nhau c ũng nh ư cĩ nhi u ph ươ ng án phân l p thì b mã thu đưc cĩ th khơng duy nh t. Thu t tốn trên đưc mơ ph ng b i ch ươ ng trình sau: Program Fano; uses wincrt; var st:string; A:array[1 255] of char; Ma:array[1 255] of string[20]; P:array[1 255] of real;; n,i,j,k:integer; Procedure Input; 70
71. Begin write(‘cho xau can ma hoa:’);readln(St); end; Procedure Output; var k:integer;xauma:string; Begin xauma:=’’; for i:=1 to length(st) do for k:=1 to n do if st[i]=a[k] then xauma:=xauma+ma[k]+’ ‘; writeln(‘Ket qua ma hoa’); writeln(xauma); end; Procedure Create; var s:set of char; Begin n:=0;s:=[]; for i:=1 to length(st) do if not (St[i] in S) then Begin n:=n+1; A[n]:= St[i]; S:=S+[St[i]]; end; for i:=1 to n do P[i]:=0; for i:=1 to n do begin for k:=1 to length(St) do if A[i]=St[k] then P[i]:= p[i]+1; P[i]:=P[i]/length(st); end; for i:=1 to n do Ma[i]:= ‘’; end; 71
72. Procedure Sorting; var i,j,tgp:integer; TgA: char; Begin For i:=1 to n-1 do For j:=i+1 to n do If P[i] =S/2; For i:=l to K do Ma[i]:=Ma[i]+’0’; For i:=K+1 to r do Ma[i]:=Ma[i]+’1’; Mahoa_fano(l,k); Mahoa_fano(k+1,r); End; End; BEGIN Input; create; 72
73. Sorting; Mahoa_fano(1,n); Output; Readln; END. • Ph ươ ng pháp mã theo Shanon Xét ngu n U v i b ng phân ph i xác su t: uk u1 u2 u3 uN pk p1 p2 p3 pN Nhà tốn h c Shanon đ xu t thu t tốn mã hĩa nh ư sau: Bưc 1 : S p x p các tin ui theo th t gi m d n c a xác su t. Bưc 2 : Tính F(ui ) theo cơng th c: i−1 F(ui ) = ∑ p(u j ) n u i ≥ 2 j=0 F(ui ) = 0 n u i = 1 b ưc này ta đã gi thi t các tin đưc s p x p theo th t gi m d n ca xác su t: p(u1 ) ≥ p(u2 ) ≥ ≥ p(u N ) Bưc 3 : Tính đ dài t mã mã hố tin ui theo cơng th c sau: 1−n −ni i I(ui ) ≤ ni ≤ I(ui ) +1 ho c 2 ≤ p(ui ) ≤ 2 Bưc 4 : Chuy n đ i F(ui ) tính đưc B ưc 2 t h th p phân sang h nh phân. Bưc 5 : Xác đnh t mã (ni ,bi ) b ng cách l y ni ký hi u nh phân ngay sau du ph y. ð rõ h ơn v thu t tốn ta xét ví d sau : Cho ngu n tin U g m 7 tin: U = {u1 ,u2 , , u7 } u i u1 u2 u3 u4 u5 u6 u7 p(ui ) 0,34 0,23 0,19 0,10 0,07 0,06 0,01 73