Giáo trình Lý thuyết thông tin

pdf

136 trang huongle 2370

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Lý thuyết thông tin", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_ly_thuyet_thong_tin.pdf

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

ð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
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
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
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
• 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
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
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
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
ð 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
• 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
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
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
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
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
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
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
đ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
• 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
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
ω 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
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
+∞ 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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
- 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
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
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
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
• ð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
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
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
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
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
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
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
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
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
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
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
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
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