Xem mẫu

  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. L IM ð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 ngoà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 toán cao c p, xác su t th ng kê, lý thuy t thu t toán và m t 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ư c u trúc c a h th ng truy n tin, phân lo i môi trư ng truy n tin, v n ñ r i r c hóa các ngu n tin liên t c và các khái ni m v ñi u ch và gi i ñi u 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 ñ l p 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, ñi u ki n thi t l p, các phương pháp bi u di n, các thu t toá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ã n i 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 hoàn thi n hơn. Thái Nguyên, tháng 01 năm 2010 Thay m t 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 ñi n tho i c ñ nh và di ñ ng, h th ng m ng 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 ñi m toá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à t p 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, v t 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, m i 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 c a ngu n và ñích, các v n ñ v mã hóa và gi i mã, kh năng ch ng nhi u c a h th ng... C n chú ý r ng lý thuy t thông tin không ñi sâu vào vi c phân tích các c u 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 toán h c mô t quá trình truy n tin trên quan ñi m 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 toán mã hóa cơ b n, các nguyên t c mã ch ng nhi u... 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 ñi m này t i ñi m 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 ñi m ñ 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 (ñi n tín) - Vô tuy n ñi n (sóng ñi n t ) - Quang năng (cáp quang) - Sóng siêu âm (la-de) • Theo bi u hi n bên ngoà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 ñi m ñó, 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 ñi m này sang ñi m khác trong m t môi trư ng xác ñ nh. Hai ñi m này s ñư c g i là ñi m ngu n tin (information source) và ñi m 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 ñi n 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 toá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, ho c 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 ( x, y , z )  K ( x, y , z ) =  g ( x, y , z ) .  h ( x, y , z )  Các tin nguyên thu ph n l n là hàm liên t c c a 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 ñó S min , 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 ñi m 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 hoá trư c khi ñưa vào kênh thông thư ng ñ u qua thi t b mã hoá. Thi t b mã hoá 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 ñi m 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 B n ch t c a thông tin theo quan ñi m 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). M t 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 t p ñ 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: X (t ) = { x (t )}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 ñoá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 toá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) F ( x) = p( X < x); w( x) = 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à p ( x) = p ( X = x ) . N u 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 F ( x, y ) = p ( X < x;Y < y ); wxy ( x, y ) = . ∂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 toán h c) c a m t quá trình ng u nhiên X (t ) +∞ ∫ x(t )w( x)dx E ( X ) = X (t ) = −∞ 2. Tr trung bình bình phương +∞ ∫ x (t )w( x)dx 2 2 2 E ( X ) = X (t ) = −∞ 3. Phương sai +∞ 2 2 ( ) = ∫ ( x(t ) − E ( x) ) D( X ) = X − X w( x )dx −∞ 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 ñi m t1, t2 +∞ +∞ ∫ ∫ x x w( x(t ), x(t ))dx dx Bx (t1 , t2 ) = E ( X (t1 ), X (t2 ) ) = 12 1 2 1 2 −∞ −∞ N u hai quá trình X , Y khác nhau hai th i ñi m khác nhau, khi ñó +∞ +∞ ∫ ∫ xyw( x(t ), y (t ))dxdy Bxy (t1 , t2 ) = E ( X (t1 ), Y (t2 ) ) = 1 2 −∞ −∞ 8
  9. ð gi i quy t bài toá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ý t c 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 ñ l n ñ quan sát các bi n ng u nhiên d ràng hơn vì có ñi u 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: T 1 T →+∞ T ∫ X (t ) = Lim x (t ) dt 0 Tr trung bình bình phương: T 1 X (t ) = Lim ∫ x 2 (t ) dt 2 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 ñ l n ch không ph i vô cùng như v y v n tho mãn các ñi u 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ó: +∞ T 1 ∫ T →+∞ T ∫ X (t ) = x(t ) w( x) dx = Lim x(t ) dt 0 −∞ Tương t : +∞ T 1 X (t ) = ∫ x (t ) w( x )dx = Lim ∫ x 2 (t ) dt 2 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 − t1 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à m t 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 − t1 . Khi ñó ta có m i tương quan Bx (t1 , t2 ) = B (τ = t2 − t1 ) = B(τ ) = X (t ). X (t + τ ) +∞ +∞ T 1 = ∫ ∫ x1 x2 w( x1 , x2 ) dx1dx2 = Lim ∫ x(t ) x(t + τ )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 hoá 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 r i 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 ño n hóa theo th i gian, như thư ng g p trong các h th ng tin xung như: ñi u biên xung, ñi u t n xung ... không b lư ng t hóa. 4. Dãy ng u nhiên r i r c: Ngu n liên t c ñư c gián ño n theo th i gian ho c trong h th ng thông tin có xung lư ng t hoá. 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 ñi m này ñ n m t ñi m 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. V y 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 h t 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 h t 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 ngoà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ư ngoà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 ñi m chung, cơ b n ñ có th t ng quát hoá 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 d ng 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 Nc(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 Nn(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, S R ( t ) là thông tin thu SV (t ) S R (t ) Kênh tin Ta có bi u th c mô t nhi u trong trư ng h p t ng quát 11
  12. S R (t ) = N n (t ) SV (t ) + N c (t ) Trong th c t , ngoà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 ñó: S R (t ) = N n (t ).H (t ).SV (t ) + N c (t ) ð 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 ño n, n u là gián ño n 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 ñi m xu t hi n. Trong trư ng h p dao ñ ng liên t c, bi u th c t ng quát c a tín hi u có d ng sau: SV (t ) = a (t )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 . ði u 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 c a 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 m t toá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 toán này ñư c g i là bài toán thu hay ph c h i tín hi u t i ñi m thu. 1.6 M t 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 ñ l p 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 t i ñ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 r i 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à m t 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 R i 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 c a 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 S (t ) = a (t )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 ñi m nh t ñ nh. Nói m t cách khác là thay hàm tin liên t c b ng m t 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 ñi m gián ñ an. V n ñ ñ t ra ñây là xét các ñi u 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 ñi n, ñi n t b t kì ñóng m dư i tác ñ ng c a ñi n áp u (t ) nào ñó. Th i gian ñóng m ch c a rơ le là 1 τ , chu kỳ l y m u là T , t n su t l y m u là f = th i gian l y m u .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 ñi u ki n c a ñ nh lý l y 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 m t 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 ) +∞ ∫ S (t )e − j 2π f t n u: S ( f ) = dt −∞ +∞ ∫ S ( f )e − j 2π f t có tín hi u liên t c S (t ) = • Gi s 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 ñó f max 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 ( − f max , f max ) l y m u là f S v i f S ≥ 2 f max . Ta th y ngoài mi n t n s năng lư ng coi như b ng 0 nên: + f max ∫ S ( f )e − j 2 π f t df S (t ) = − f max • 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à f S = 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 max  t −   2 f max   n  n =+∞ S (t ) = ∑ S    n n =−∞  2 f max  2π f max  t −   2 f max   n    n   là các m u c a S (t ) l y t i t = trong ñó:  S  vi   2 f max   2 f max   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 c a 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 ( − f max , f max ) hoàn toàn ñư c xác ñ nh b ng cách l y m u v i t n s l y m u f S = 2 f max . 1.7.2 Khâu lư ng t hoá 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 ( S min , S max ) . Ta chia kho ng ( S min , S max ) thành n kho ng: Smin = S0 < S1 < S2 < ... < Sn = Smax 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 hoá v i m i m c lư ng t ∆ i = Si +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 hoá. ∆ i , (i = 0,..., n − 1) g i là m c lư ng t hoá. Smax − Smin , ∀i = 0,..., n − 1 , ta có qui lu t lư ng t hoá ñ u N 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 hoá. Th t th c hi n hai phép bi n ñ i này ph thu c vào ñi u ki n c th c a h th ng: • Lư ng t hoá sau ñó l y m u. • L y m u sau ñó lư ng t hoá. • Th c hi n ñ ng th i hai phép bi n ñ i trên. 1.8 ði u ch và gi i ñi u ch 1.8.1 ði u 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 ñi n (áp, dòng) và chuy n vào kênh. Khi mu n chuy n các tin y qua m t c ly l n, ph i cho qua m t phép bi n ñ i khác g i là ñi u ch . ð nh nghĩa: ði u ch là phép bi n ñ i nh m chuy n thông tin ban ñ u thành m t 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 ñi u ch : Các phương pháp ñi u ch cao t n thư ng dùng v i tín hi u liên t c • ði u ch biên ñ AM (Amplitude Modulation) • ði u ch ñơn biên SSB (Single Side Bande) • ði u t n FM (Frequency Modulation) • ði u pha PM (Phase Modulation) V i tín hi u r i r c, các phương pháp ñi u ch cao t n cũng gi ng như trư ng h p thông tin liên t c, nhưng làm vi c gián ño n 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 ñi u ch ð nh nghĩa: Gi i ñi u ch là nhi m v thu nh n, l c, tách thông tin nh n ñư c dư i d ng m t ñi n áp liên t c hay m t dãy xung ñi n 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 ñi u ch V phương pháp gi i ñi u ch nói cách khác là phép l c tin, tùy theo h n h p 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 M t 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 ngoà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 ñi n t , tín hi u s ,…. V m t toá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 vi cư ng ñ c c kỳ l n 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 v t lý hay cơ h c. 2.1.3 Tín hi u ñi u hoà Bi u hi n các lo i tín hi u tu n hoà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 S (t ) = 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 S (t ) = a cos ωt + b 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 ñ c c 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 b t 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 s c, vi c phân tích ñó g i là phép phân tích ph . N u tín hi u ñi u hoà có d ng: S (t ) = 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 ( jωt +ϕ ) ( jωt −ϕ ) (e + e ) N u tín hi u cho dư i d ng ph c S (t ) = 2 Khi ñó chúng ta có d ng ph ph c A/2 A/2 ω-ϕ 0 ω+ϕ Hình 2.2 20
nguon tai.lieu . vn