Giáo trình lý thuyết thông tin - Chủ biên Vũ Vinh Quang

Chia sẻ: Manh Tuan | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

156
lượt xem 36
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo Giáo trình lý thuyết thông tin ( Chủ biên Vũ Vinh Quang ) dành cho sinh viên chuyên ngành Công nghệ thông tin

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình lý thuyết thông tin - Chủ biên Vũ Vinh Quang

ð 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
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
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
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
• 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
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
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
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
ð 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
• 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
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
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
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
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
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
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
ñ 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
• 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
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
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