Giáo trình Truyền dữ liệu - Nguyễn Trung Lập
212 trang
11700
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Truyền dữ liệu - Nguyễn Trung Lập", để 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_truyen_du_lieu_nguyen_trung_lap.pdf
Nội dung text: Giáo trình Truyền dữ liệu - Nguyễn Trung Lập
- L I NĨI ð U Giáo trình đư c biên so n nh m ph c v cho sinh viên chuyên ngành Ði n t Vi n thơng. N i dung g m chín chương, tr ng tâm đi vào ph n c ng đ ng th i cĩ gi i thi u m t s giao th c c a h th ng truy n d li u. Chương 1 và 2 ơn t p m t s ki n th c cơ b n cĩ b sung m t s khái ni m m i chu n b cho các chương ti p theo. Chương 3 t p trung v n đ mã hĩa, phân tích tính ch t và kh năng các lo i mã, thi t k các lo i m ch t o mã. Chương 4, 5 và 6 tìm hi u các IC cùng giao th c truy n đ ng b , b t đ ng b đ ng th i kh o sát các chu n giao ti p dùng trong truy n d li u. Chương 7 bàn v bi n pháp truy n d li u nh đư ng dây đi n tho i, k thu t dùng trong modem. Chương 8 trình bày các phương pháp đa h p. Chương 9 đ c p đ n k thu t truy n tín hi u s trên h th ng thơng tin. Tìm hi u ho t đ ng c a các IC CODEC. Theo ch quan c a tác gi , s s p x p các chương v i th t như trên là h p lý. Như chúng ta đã bi t, v n đ truy n thơng đã và đang phát tri n r t nhanh v i k thu t ngày càng hồn h o nên nh ng gì vi t ra ngày hơm nay cĩ th khơng hồn tồn thích h p trong tương lai. Tuy nhiên ph n ki n th c cơ b n hàm ch a trong giáo trình luơn luơn v n là n n t ng cho s phát tri n sau này Ðây cũng là mong mu n mà ngư i vi t hy v ng mang đ n cho các em sinh viên. M c dù giáo trình đư c vi t cho đ i tư ng là sinh viên chuyên ngành Ði n t Vi n thơng, nhưng v i nh ng ai cĩ quan tâm t i ph n c ng c a các h th ng truy n d li u cũng cĩ th tìm th y đây đơi đi u b ích. Cu i cùng tác gi xin thành th t cám ơn Th c sĩ Ðồn Hịa Minh đã đ c và đĩng gĩp nhi u ý ki n quý báu đ giáo trình cĩ th hồn thành. Ngư i vi t Nguy n Trung L p
- M C L C CHƯƠNG I: NH NG KHÁI NI M CƠ B N 1.1 VÀI DỊNG L CH S . 1.2 NH NG KHÁI NI M CHUNG . 1.3 H TH NG TRUY N TƯƠNG T . 1.4 H TH NG TRUY N S . 1.5 H TH NG M VÀ MƠ HÌNH OSI . CHƯƠNG 2 MÃ HĨA VÀ ðI U CH : 2.1 PH T N C A TÍN HI U . 2.2 MÃ HĨA . 2.3 ðI U CH . CHƯƠNG 3: CÁC LO I MÃ TRONG TRUY N D LI U: 3.1 MÃ NH PHÂN C A CÁC CH S . 3.2 CÁC MÃ PHÁT HI N L I . 3.3 MÃ NÉN D LI U . 3.4 M T MÃ . CHƯƠNG 4: TRUY N N I TI P B T ð NG B : 4.1 H TH NG TRUY N D LI U . 4.2 M U TÍN HI U TRONG TRUY N B T ð NG B . 4.3 VÀI IC TH C HI N GIAO TH C B T ð NG B . CHƯƠNG 5: CÁC CHU N GIAO TI P: 5.1 GIAO TI P DÙNG DỊNG ðI N VỊNG 20mA . 5.2 CHU N GIAO TI P RS 232D . 5.3 CHU N GIAO TI P RS 449, 422A&423A . CHƯƠNG 6: TRUY N N I TI P ð NG B 6.1 GIAO TI P GI A DTE VÀ DCE ð NG B . 6.2 CÁC GIAO TH C ð NG B .
- 6.3 KH O SÁT VÀI IC LSI TRUY N ð NG B . 6.4 KI M TRA H TH NG THƠNG TIN . CHƯƠNG 7: TRUY N TÍN HI U B NG SĨNG MANG TƯƠNG T : MODEMS 7.1 D N NH P. 7.2 CƠ S K THU T LIÊN QUAN. 7.3 M T S MODEM ð NG B VÀ B T ð NG B . 7.4 VÀI MODEM DÙNG M CH LSI . CHƯƠNG 8: C C PHƯƠNG PHÁP ðA H P 8.1 ðA H P T N S . 8.2 ðA H P TH I GIAN . CHƯƠNG 9 TRUY N TÍN HI U TƯƠNG T B NG SĨNG MANG S : 9.1 H TH NG TRUY N S . 9.2 ðI U MÃ XUNG . 9.3 ðI U CH VI PHÂN VÀ DELTA . 9.4 2914 COMBO CHIP . WWW.UPDATESOFTS.COM – 2006
- CHƯƠNG 1 NH NG KHÁI NI M CƠ B N N i dung : 1.1 VÀI DỊNG L CH S . 1.2 NH NG KHÁI NI M CHUNG . 1.3 H TH NG TRUY N TƯƠNG T . 1.4 H TH NG TRUY N S . 1.5 H TH NG M VÀ MƠ HÌNH OSI . 1 . 1 VÀI DỊNG L CH S : Thơng tin d li u là phương pháp truy n thơng dùng mã nh phân thay cho tín hi u. Cĩ th coi l ch s thơng tin d li u b t đ u vào năm 1837 v i s phát minh đi n tín c a Samuel F. B. Morse. Ðĩ là h th ng truy n các xung đi n bi u di n cho các d u ch m, v ch (tương đương v i các s nh phân 1, 0) trên các đư ng dây đ ng nh các máy cơ đi n. Các t h p khác nhau c a các mã này thay cho các ch , s , d u đư c g i là mã Morse. B n đi n tín đ u tiên đư c phát hi n Anh do Charles Wheatstone và William Cooke th c hi n nhưng h th ng c a h ph i dùng 6 đư ng dây. Năm 1840, Morse đăng ký sáng ki n v đi n tín M và đ n năm 1844 thì đư ng dây đi n tín đ u tiên đư c thi t l p gi a Baltimore và Washington D.C Năm 1849, b n tin đ u tiên đư c in nhưng v i v n t c r t ch m, cho đ n năm 1860 v n t c in đ t đư c là 15 bps. Cơng ty Ði n tín Mi n Tây (Western Union Telegraph Company) đư c thi t l p năm 1850 Rochester, New York cho phép th c hi n vi c trao đ i thơng tin gi a các cá nhân. Năm 1874, Emile Baudot thi t k đư c máy phát dùng phương pháp đa h p, cĩ th truy n cùng lúc 6 b n tin trên cùng m t đư ng dây. Năm 1876, Alexander Graham Bell đã đưa đi n tín lên m t bư c phát tri n m i: s ra đ i c a đi n tho i. Thay vì chuy n b n tin thành các chu i mã Morse, Bell đã cho th y r ng ngư i ta cĩ th truy n th ng tín hi u đi n đ c trưng cho ti ng nĩi trên các đư ng dây. Nh ng h th ng đi n tho i đ u tiên c n các c p đư ng dây khác nhau cho hai ngư i mu n trao đ i thơng tin v i nhau, m t ngư i ph i n i đi n tho i c a mình vào đúng đư ng dây n i v i đi n tho i c a ngư i mà mình mu n liên l c. D n d n s k t n i đư c th c hi n b i các t ng đài cơ khí r i t ng đài đi n t , s . . . . Ngư i ta khơng cịn bi t h th ng ho t đ ng th nào, ch c n quay (bây gi thì b m) s và đư c k t n i. Năm 1899, Marconi thành cơng trong vi c phát tin b ng vơ tuy n.
- Cĩ th nĩi đi n tín là phương ti n duy nh t đư c dùng đ phát tin đi xa cho đ n năm 1920, lúc đài phát thanh thương m i đ u tiên ra đ i. Năm 1945, đánh d u m t s ki n quan tr ng đĩ là vi c phát minh ra chi c máy tính đi n t đ u tiên: chi c ENIAC (Electronic Numerical Integrator And Calculator). Ðư c thi t k đ tính đ n đ o ph c v cho Th chi n th II, ENIAC là thi t b đ u tiên cĩ th x lý thơng tin dư i d ng đi n. M c dù ENIAC khơng gi m t vai trị tr c ti p trong vi c thơng tin d li u nhưng nĩ cho th y r ng các tính tốn và quy t đ nh chính xác cĩ th th c hi n đư c nh tín hi u đi n, m t kh năng quan tr ng trong h th ng thơng tin hi n nay. Sau đĩ Ð i h c Harvard liên k t v i cơng ty IBM (International Business Machines Corporation) đã cho ra đ i nh ng chi c máy tính đa d ng, đi u khi n t đ ng đ u tiên. Ð n năm 1951 thì s lư ng các ch ng lo i máy tính gia tăng r t nhi u (ngư i ta đánh giá s gia tăng này cĩ t c đ t l v i hàm mũ) và nhu c u trao đ i thơng tin trong m i ngư i cũng gia tăng v i m c đ tương t . Nhưng cho đ n năm 1968 cơng ty AT & T xem như đ c quy n: ch các thi t b do chính cơng ty s n xu t m i đư c n i vào h th ng thơng tin qu c gia. Vào th i đi m này, Hi p h i thơng tin liên bang (FCC : Federal Communication Commission) c a M , thơng qua Tịa án t i cao đã ký quy t đ nh Carterfone, cho phép các thi t b c a các nhà ch t o khác đư c n i vào h th ng, quy t đ nh này đã tác đ ng th t s đ n s ra đ i c a m t k ngh m i: k ngh thơng tin d li u. Theo th i gian s phát tri n c a k ỵ ngh này đã đưa đ n nh ng h th ng thơng tin d li u s đư c th c hi n nh ng kho ng cách đáng k . Và bây gi ,v i s phát tri n vũ b o c a máy tính , cơng ngh ch t o IC đa ch c năng, kh năng to l n c a cáp quang và h th ng v tinh đ a tĩnh, thơng tin d li u s đã tr thành ph bi n và cĩ m t s c m nh đ n kỳ l , nĩ cĩ th th a mãn nhi u yêu c u v thơng tin liên l c c a m i ngư i trên tồn c u trong m t kho ng th i gian r t ng n. Chương này đ c p đ n m t s khái ni m chung và tìm hi u m t cách sơ lư c các h th ng truy n tương t , h th ng truy n s cùng m t s tính ch t cơ b n c a chúng. 1 . 2 NH NG KHÁI NI M CHUNG : 1.2.1. Tin t c, d li u và tín hi u. 1.2.2 Băng thơng . 1.2.3 Hình tr ng h th ng và các phương th c liên l c . 1.2.4 Các phương pháp truy n . 1.2.5. Các phương pháp d n kênh . 1.2.1 Tin t c, d li u và tín hi u (Information, Data & Signal): D li u: bao g m các s ki n, khái ni m hay các ch th đư c di n t dư i m t hình th c thích h p cho vi c thơng tin, thơng d ch hay x lý b i con ngư i hay máy mĩc. Tin t c: Ý nghĩa mà con ngư i qui cho d li u theo các qui ư c c th . Tin t c cĩ th bi u th b i ti ng nĩi, hình nh, các văn b n, t p h p các con s , các ký hi u, thơng qua nĩ con ngư i hi u nhau . . Trong h th ng truy n thơng, thư ng ngư i ta khơng phân bi t d li u và tin t c.
- Tín hi u: Là tin t c, d li u đã đư c chuy n đ i, x lý (b i các b ph n mã hĩa và /ho c chuy n đ i) cho phù h p v i mơi trư ng truy n thơng. Cĩ hai lo i tín hi u: tín hi u tương t và tín hi u s . Tín hi u tương t : cĩ d ng sĩng như (H.1.1a), đĩ là các đ i lư ng đi n cĩ b t c giá tr nào trong m t kho ng th i gian xác đ nh. Tín hi u tương t quen thu c cĩ d ng hình sin. M t tín hi u tương t cĩ th đư c s hĩa đ tr thành tín hi u s . Tín hi u s : cĩ d ng sĩng như (H.1.1b), đĩ là tín hi u mà biên đ ch cĩ m t trong hai giá tr duy nh t, tương ng v i hai tr ng thái logic đ c trưng b i hai s 0 và 1 trong h nh phân. H th ng truy n tín hi u này là h th ng truy n nh phân. Trong các h th ng truy n s , ta cịn g p tín hi u cĩ d ng như (H.1.1c). Ðây chưa ph i là tín hi u s nhưng nĩ cũng ch cĩ các giá tr nh t đ nh mà ngư i ta cĩ th s hĩa b ng các s nh phân nhi u bít hơn. Trong trư ng h p c a (H 1.1c) tín hi u cĩ th cĩ m t trong b n giá tr 0, 1, 2, 3; đ cĩ th mã hĩa tín hi u này c n các s nh phân hai bít, h th ng truy n tín hi u này là h th ng truy n nh phân hai bít. (a) (b) (c) (H 1.1) Tín hi u trên đư ng truy n, g i là sĩng mang, cĩ th là lo i tương t hay s và đư c dùng đ truy n d li u tương t hay d li u s . Thí d : Ti ng nĩi là lo i d li u tương t và đư c truy n trên h th ng đi n tho i b i tín hi u tương t (H 1.2a); nh ng d li u cĩ ngu n g c là s , thí d như mã ASCII c a các ký t đư c bi u di n dư i d ng nh ng xung đi n nh phân đư c truy n b i tín hi u tương t nh MODEM (Modulator/Demodulator) (H 1.2b). Tín hi u tương t s qua m ch CODEC (Coder/Decoder) đ đư c s hĩa (H 1.2c) và d li u s cĩ th đư c truy n th ng qua h th ng s (H 1.2d). Ngu n Tín hi u truy n Ti ng nĩi ðI N → Tín hi u tương → THO I t (a) Tín hi u s MODEM → Tín hi u tương t → (b)
- Tín hi u tương t CODEC → Tín hi u s → (c) D li u s H. T. S → Tín hi u s → (d) (H 1.2) Nhi u: là các tín hi u ngồi ý mu n, xu t hi n trong h th ng ho c trên đư ng truy n. Dư i nh hư ng c a nhi u, tín hi u tương t b bi n d ng và tín hi u s cĩ th b l i. Cư ng đ tín hi u: Cư ng đ c a tín hi u thư ng đư c bi u di n b i cơng su t ho c đi n áp trên t ng tr t i c a nĩ. Ta ph i nĩi tín hi u cĩ cơng su t 133mW ho c cĩ biên đ 100mV trên t ng tr 75 . T s cư nng đ hai tín hi u: dùng mơ t đ l i ho c đ suy gi m c a h th ng, thư ng đư c bi u di n b ng đơn v Decibel (dB) xác đ nh theo thang logarithm: T s tín hi u = 10log dB S ti n l i c a đơn v dB là ngư i ta cĩ th xác đ nh đ l i (hay đ suy gi m) c a m t h th ng g m nhi u t ng n i chu i (cascade) b ng cách c ng các đ l i c a các t ng v i nhau. Ngư i ta thư ng bi u th cơng su t tuy t đ i c a m t tín hi u b ng cách so sánh v i m t tín hi u chu n cĩ cơng su t 1W : Cơng su t tín hi u = 10log dB Ngồi ra, ngư i ta cịn dùng đơn v dBm đ xác đ nh cư ng đ tín hi u so v i tín hi u chu n cĩ cơng su t 1mW : Cơng su t tín hi u = Bm 10log M t tín hi u cĩ cơng su t 1W tương đương v i 0 dB và 30dBm. Thí d : Tín hi u cĩ biên đ 100mV 75 tương đương v i 0,133 mW, tính theo dBm là: 10log(0,133/1mW) = 8,76 dBm. D u tr cho bi t m c tín hi u là 8,76 dBm dư i 1mW. Lưu ý, trong chuy n đ i đơn v ph i đ ý đ n t ng tr t i c a tín hi u. Bi u th c P = ( V 2/R ) cĩ th đư c dùng đ tính đi n áp hi u d ng ho c t s đi n áp. Trong các h th ng đi n tho i t ng tr t i thư ng dùng là 600 . Thí d : Tín hi u 100mV trên t i 75 tương đương v i 282mV, n u t i là 600 . Th t v y, 600 , đi n áp c a tín hi u xác đ nh b i : V2 = P.R = 0,133.10 3.600 = 0,079 = 0,282 V = 282 mV
- V = N u các tín hi u cĩ chung t ng tr t i thì : T s tín hi u = 20log dB T s tín hi u nhi u SNR (Signal to Noise Ratio) Ð đánh giá ch t lư ng c a tín hi u và cũng là ch t lư ng c a h th ng truy n tín hi u đĩ ngư i ta dùng t s tín hi u trên nhi u SNR. Ðây là t s cơng su t tín hi u cĩ ích trên cơng su t tín hi u nhi u, thư ng tính b ng dB (ho c dBm). N u tín hi u 2 dBm cĩ m c nhi u là 20 dBm, thì t s SNR là 22 dBm. Nĩi cách khác m c tín hi u l n hơn m c nhi u 22 dBm. Thí d : V i tín hi u s như (H.1.1b), SNR t i thi u ph i là bao nhiêu đ cĩ th phân bi t đư c tín hi u m t cách rõ ràng ( nh hư ng c a nhi u cịn ch p nh n đư c)? Ð i v i tín hi u như (H.1.1b), gi s biên đ ng v i m c 1 là 1 V và 0 V cho m c 0, m t l i s phát sinh n u m c 0 đư c phát đi mà nhi u cĩ giá tr dương l n hơn 0,5 V và n u m c 1 phát đi mà nhi u cĩ biên đ âm và tr tuy t đ i l n hơn 0,5 V. Như v y giá tr t i đa cho phép c a nhi u là 0,5 V so v i tr t i đa c a tín hi u là 1 V và t s SNR t i thi u là: SNR MIN = M t h th ng hay m ch t t khi cĩ kh năng nâng cao t s tín hi u nhi u SNR theo yêu c u. 1.2.2 Băng thơng : Băng thơng c a tín hi u là d i t n s trong đĩ ch a h u h t cơng su t c a tín hi u. Khái ni m này cho ta xác đ nh ph t n h u ích c a tín hi u n u tín hi u đĩ ch a m t ph t n quá r ng. Băng thơng c a kênh truy n là d i t n s c a tín hi u mà đ suy gi m kho ng vài dB (thư ng là 3 dB) so v i giá tr c c đ i khi tín hi u đĩ truy n qua h th ng. Ð suy gi m 3 dB tương ng v i đi m n a cơng su t. M t kênh truy n t t ph i cĩ băng thơng l n hơn băng thơng c a tín hi u, đi u này khi n cho tín hi u đư c tái t o khơng b méo d ng và suy gi m đáng k trong quá trình truy n. 1.2.3 Hình tr ng h th ng và các phương th c liên l c : V hình tr ng, h th ng thơng tin cĩ th cĩ d ng : Ði m đi m (Point to point): Thí d liên l c gi a máy tính và máy in Nhi u đi m (Multipoint): H th ng nhi u đi m cĩ th cĩ m t trong các d ng: sao (star), vịng (ring) và multidrop * M ng hình sao (H 1.3a): Thu n l i trong liên l c vì đài th c p truy xu t tr c ti p đài sơ c p nhưng giá thành cao vì ph i s d ng đư ng dây riêng. * M ng vịng (H 1.3b) : Thơng tin ph i đi theo vịng t đài sơ c p đ n đài th c p. N u cĩ m t đài h ng, h th ng ngưng làm vi c.
- * M ng multidrop (H 1.3c): Các đài th c p n i chung m t đư ng dây vào tr m sơ c p V phương th c th c liên l c, gi a các máy phát và thu trong m t h th ng thơng tin cĩ th th c hi n theo 1 trong 4 phương th c: Ðơn cơng (Simplex transmission, SX): thơng tin ch truy n theo m t chi u. N u l i x y ra máy thu khơng cĩ cách nào yêu c u máy phát phát l i. Trong h th ng này thư ng máy thu cĩ trang b thêm b ROP (Read Only Printer) đ hi n th thơng tin nh n đư c. Bán song cơng (Half duplex transmission, HDX): Tín hi u truy n theo hai hư ng nhưng khơng đ ng th i. H th ng thơng tin dùng Walkie Talkie là m t thí d c a phương th c liên l c bán song cơng. Các máy truy n bán song cơng cĩ m t nút n đ phát (push to send), khi ch đ phát thì ph n thu b vơ hi u hĩa và ngư c l i. Song cơng (full duplex transmission, FDX): Tín hi u truy n theo hai chi u đ ng th i. H th ng này thư ng cĩ 4 đư ng dây, 2 dây cho m i chi u truy n. Phương th c này đư c dùng trong h th ng đi m đi m (point to point) Song cơng tồn ph n (Full/Full duplex, F/FDX): Ðài sơ c p cĩ kh năng phát tín hi u t i m t đài th c p đ ng th i nh n thơng tin t m t đài th c p khác. Phương th c này gi i h n trong h th ng nhi u đi m (multipoint) (H 1.3) 1.2.4 Các phương pháp truy n : Ð truy n tín hi u ngư i ta cĩ th dùng m t trong hai phương pháp: phương pháp truy n d i n n và phương pháp đi u ch . Phương pháp truy n d i n n : Tín hi u đư c truy n cĩ cùng d i t n v i tín hi u ngu n. Thí d trong đi n tho i, tín hi u âm thanh h u ích cĩ t n s trong kho ng 300 3000 Hz đư c truy n đi mà khơng cĩ s bi n đ i nào v ph t n c a nĩ.
- Phương pháp đi u ch : Ðây là phương pháp cho phép d i ph t n c a tín hi u ngu n đ n m t kho ng t n s khác phù h p v i kênh truy n và tránh đư c nhi u do giao thoa (nghĩa là các ph t n cách nhau m t kho ng đ đ khơng ch ng lên nhau). 1.2.5 Các phương pháp d n kênh : Ð cĩ th truy n nhi u tín hi u cĩ cùng d i n n (nhi u kênh) trên m t đư ng truy n mà khơng gây nh hư ng l n nhau, ngư i ta ph i d n kênh. Cĩ hai phương pháp d n kênh: phương pháp đa h p phân t n s và phương pháp đa h p phân th i gian . (H 1.4) mơ t hai phương pháp d n kênh. (H 1.4) D n kênh theo phương pháp đa h p phân th i gian (TDM: Time Division Multiplexing) (H 1.5) minh h a phương pháp TDM . (H 1.5) Khĩa chuy n m ch đư c s d ng đ n i tu n t m i tín hi u c n truy n đ n đư ng truy n trong m t kho ng th i gian nh t đ nh. Dĩ nhiên các khĩa chuy n m ch máy phát (d n kênh) và máy thu (phân kênh) ph i ho t đ ng đ ng b đ các máy thu thu đúng tín hi u c a nĩ. D n kênh theo phương pháp đa h p phân t n s (FDM: Frequency Division Multiplexing). (H 1.6) minh h a phương pháp FDM cho 3 kênh truy n (3 tín hi u tương t ). T n s sĩng mang c a m i b đi u ch c a m i kênh đư c ch n l a sao cho m i tín hi u đã đư c đi u ch chi m m t d i t n riêng trong c ph t n c a đư ng truy n và ph i đư c cách ly
- theo qui đ nh. Ð th c hi n đư c vi c này ngư i ta dùng các m ch c ng hư ng LC cĩ t n s c ng hư ng khác nhau cho m i kênh truy n. Các h th ng truy n thanh và truy n hình s d ng phương pháp d n kênh này. (H 1.6) 1 . 3 H TH NG TRUY N TƯƠNG T : (H 1.7) mơ t m t h th ng truy n tương t dùng phương pháp đi u ch (n u truy n d i n n thì khơng c n b đi u ch và gi i đi u ch ). Trong h th ng này tín hi u trên đư ng truy n là tín hi u tương t . B ph n chuy n đ i máy phát bi n tin t c thành tín hi u tương t , sau khi đư c x lý (như l c, khu ch đ i, ph i h p tr kháng ) s qua b ph n đi u ch đ d i ph t n; cu i cùng b ph n giao ti p chu n b tín hi u phát tương thích v i mơi trư ng truy n hay kênh truy n. Các cơng vi c đư c th c hi n theo chi u ngư c l i máy thu. (H 1.7) 1 . 4 H TH NG TRUY N S : 1.4.1 Sơ đ kh i . 1.4.2 V n t c truy n tín hi u . 1.4.3 Truy n n i ti p và song song .
- 1.4.4 Truy n đ ng b và b t đ ng b . 1.4.1 Sơ đ kh i : (H 1.8) mơ t m t h th ng truy n s . Tín hi u trên đư ng truy n c a h th ng là tín hi u s , t c các đi n áp tương ng cho các m c 0 và 1 c a các mã nh phân bi u th cho tin t c. B ph n chính c a h th ng là b ph n bi n đ i A →D (Analog to Digital Converter, ADC) máy phát (bi n tín hi u tương t thành tín hi u s ) và bi n đ i D →A (Digital to Analog Converter, DAC) máy thu (bi n tín hi u s thành tín hi u tương t ). Vi c truy n tín hi u s đư c th c hi n b ng cách phát tu n t các mã nh phân này. (H 1.8) 1.4.2 V n t c truy n tín hi u (Baud rate) : M t trong nh ng đ c trưng quan tr ng đ đánh giá ch t lư ng m t h th ng truy n s là v n t c truy n tín hi u, đư c tính b ng baud. Baud là v n t c thay đ i tr ng thái sĩng mang (s l n thay đ i sĩng mang trong m t giây) cịn g i là v n t c đi u ch (baud rate). Trong th c t ngư i ta hay dùng đơn v bit/s (bps) là v n t c truy n bit (bit rate), t c s bit mà h th ng truy n trong m t giây. Trong h th ng truy n nh phân (tín hi u c n truy n cĩ d ng (H 1.1b)), sĩng mang ch đư c đi u ch b i m t trong hai tr ng thái c a tín hi u, v n t c bit và v n t c tín hi u b ng nhau (s bit/s = s baud). Trong h th ng truy n nh phân hai bit (Thí d , dùng s nh phân hai bit mã hĩa tín hi u cĩ d ng (H 1.1c)), s lư ng bit s g p đơi s tín hi u (v n t c thay đ i bit nhanh g p đơi v n t c thay đ i sĩng mang), như v y s bit/s g p đơi s baud. Thí d : Tính v n t c truy n tín hi u (H 1.1c), n u th i gian tương ng v i m t giá tr c a tín hi u là T = 0,0001s. V n t c truy n tín hi u = s baud = 1/T = 1/0,0001 = 10.000 baud. V n t c truy n bit br = 2.baud = 20.000 bit/s 1.4.3 Truy n n i ti p và song song : Tùy theo cách th c đưa tín hi u ra đư ng truy n mà ta cĩ hai cách truy n: song song và n i ti p. (H.1.8) mơ t hai cách truy n. Truy n n i ti p: tín hi u l n lư t đư c phát đi t ng bít trên cùng m t đư ng dây. T c đ truy n ch m nhưng ít t n kém hơn so v i cách truy n song song.
- Truy n song song: mã ký t đư c g i đi dư i d ng song song, nghĩa là các bít đư c phát đi đ ng th i trên các đư ng truy n. T c đ truy n song song khá nhanh nhưng ph i t n nhi u đư ng dây. Do đĩ, cách truy n này đư c dùng trong th c t khi ph n phát và thu g n nhau. (a) (b) (H1.9) 1.4.4 Truy n đ ng b và b t đ ng b : Trong các h th ng truy n s các tín hi u cĩ th truy n theo ch đ đ ng b và b t đ ng b . Hai ch đ truy n này khác nhau ch y u vi c th c hi n s đ ng b và do đĩ đưa t i cách đ nh d ng tín hi u truy n khác nhau. Truy n đ ng b : Trong ch đ đ ng b d li u truy n đư c hình thành theo các d ng c đ nh. Thí d các ký t đư c mã hố b ng mã ASCII và b n tin đư c truy n thành t ng kh i (block), s đ ng b đư c th c hi n nh ng kho ng th i gian gi a các kh i c a b n tin. Do truy n m t l n c b n tin nên v n t c truy n khá l n, t 2400 bps, 4800 bps, 9600 bps cho đ n h ng Mbps. M t b t l i c a cách truy n đ ng b là máy phát ph i g i tín hi u xung đ ng h đ đ ng b máy thu. N u vi c này khơng th c hi n đư c thì máy thu ph i thi t k m t vịng khĩa pha (PLL) đ ph c h i xung đ ng b t dịng d li u. Truy n b t đ ng b : Trong ch đ b t đ ng b d ng c a d li u truy n khơng c đ nh. (H 1.10) cho ta 3 d ng c a tín hi u thư ng g p trong cách truy n b t đ ng b . (H 1.10a) là 3 b n tin a,b,c đư c truy n tu n t . Các b n tin dài ng n khác nhau và cách nhau khơng đ u.
- (H 1.10b) là trư ng h p th i gian T c a các b n tin gi ng nhau nhưng kho ng cách các b n tin thì b t kỳ, khơng ph i là b i s c a T. Trong hai trư ng h p này băng thơng c n thi t tùy thu c vào d li u. (H 1.10c) là m t d ng khác c a tín hi u thư ng g p trong các b n tin phát b ng phương pháp quét (thí d trong các máy FAX). Trong trư ng h p này băng thơng c a h th ng tùy thu c vào đ phân gi i tín hi u ch khơng tùy thu c vào d li u. Trong t t c các trư ng h p đ t o s đ ng b máy phát ph i g i kèm các xung đ ng b đ u và cu i m i ký t (trong (H 1.10a) đĩ là các xung S ho c T ). (H 1.10) 1.5 H TH NG M VÀ MƠ HÌNH OSI : S phát tri n c a lãnh v c thơng tin liên l c v i k thu t truy n s li u đã tr nên ph bi n trên tồn c u. Vi c thơng tin ngày càng nhi u, yêu c u v đ chính xác và đ tin c y ngày càng cao. Ð b o đ m đi u này các h th ng thơng tin ph i tuân th m t s qui đ nh v t t c các khía c nh như t c đ truy n, phương pháp mã hĩa, qui t c gán đ a ch , các bi n pháp th c hi n khi cĩ l i v. v . . . T p h p t t c các qui đ nh mà các h th ng thơng tin ph i tuân theo g i là các giao th c (protocols). Nh cĩ giao th c, các h th ng khơng tương thích nhau cĩ th liên l c v i nhau. Ð i v i m t h th ng ch cĩ hai ph n t thì giao th c r t đơn gi n. V n đ tr nên ph c t p và khĩ khăn khi ch ng lo i các h th ng và các ph n t c a h th ng tăng lên. M t t p h p các giao th c cho phép hai h th ng b t kỳ nào cũng cĩ th liên l c v i nhau b t ch p c u trúc bên trong c a nĩ, g i là m t H TH NG M . T ch c đ nh chu n qu c t (International Standards Organization, ISO) đã quan tâm t i v n đ k t n i các thi t b khác nhau t năm 1977 và đ n năm 1984 thì mơ hình tham chi u cho vi c k t n i các h th ng m ra đ i, g i t t là mơ hình OSI (Reference Model for Open Systems Interconnection). Mơ hình OSI là mơ hình phân t ng đư c xây d ng d a trên các nguyên t c ch y u sau đây: S t ng càng h n ch càng t t Ranh gi i gi a các t ng b o đ m vi c tương tác và mơ t các d ch v là t i thi u và cĩ th chu n hĩa giao di n tương ng.
- Các ch c năng khác nhau và các cơng ngh s d ng khác nhau ph i đư c tách bi t trong các t ng khác nhau Khi thay đ i ch c năng ho c giao th c trong m t t ng khơng nh hư ng đ n các t ng khác. M i t ng ch cĩ ranh gi i và giao di n v i t ng ngay trên và dư i nĩ. Cĩ th chia m t t ng thành các t ng con khi c n thi t. Và các t ng con cũng cĩ th đư c h y b trong trư ng h p khơng c n n a. K t qu ta đư c mơ hình OSI g m 7 t ng T ng cao nh t liên quan đ n vi c lý gi i khái ni m và ngơn ng cịn các t ng th p hơn nĩi v các qui t c truy n thơng tin gi a các b ph n (máy phát và máy thu). Trong m i t ng ngồi nh ng qui đ nh ph i th c hi n ngay trong chính b n thân t ng đĩ cịn cĩ nh ng qui đ nh d ch v đưa lên t ng trên k ti p. Máy phát và thu c n ph i th ng nh t các qui t c áp d ng trong t ng tương ng, cĩ nghĩa là chúng ph i làm vi c theo cùng m t th th c. Thơng tin đi u khi n c a m i t ng đư c ghép vào b n tin máy phát và đư c tách ra máy thu t ng tương ng, dĩ nhiên các thơng tin này ch đư c máy thu hi u khi chúng cùng s d ng m t giao th c. (H 1.11) cho ta th y s phân c p này. H th ng A H th ng B T ng 7 T ng 7 Application ng d ng Ki u n i logic ↓ T ng 6 T ng 6 Presentation Trình bày ↓ T ng 5 T ng 5 Session Giao d ch ↓ T ng 4 T ng 4 Transport V n chuy n ↓ T ng 3 T ng 3 Network M ng ↓ T ng 2 T ng 2 Data link Liên k t DL ↓ T ng 1 T ng 1 Physical V t lý ↓← →
- K t n i v t lý (H 1.11) T ng 1 : T ng v t lý (physical layer) Qui đ nh v các tính ch t v t lý c a h th ng. T ng v t lý liên quan đ n nhi m v truy n dịng bit khơng c u trúc qua đư ng truy n v t lý, truy nh p đư ng truy n v t lý nh các phương ti n cơ, đi n, hàm (ch c năng), th t c. T ng 2 : T ng liên k t d li u (data link layer) Cung c p phương ti n đ truy n thơng tin qua liên k t v t lý b o đ m đ tin c y. T ng này qui đ nh các ch c năng c a kênh s li u trên m t đư ng truy n gi a hai đi m c a h th ng thí d nh ng qui đ nh v s đ ng b hĩa, đ c tính c a khung d li u, đánh s khung, ki m tra l i, ki m tra lu ng d li u trong quá trình liên l c. T ng 3: T ng m ng (network layer) Qui đ nh các ch c năng m ng như ch n đư ng, gán đ a ch , chuy n ti p thơng tin, th c hi n vi c ki m sốt lu ng d li u, tách/h p d li u khi c n thi t. Giao th c trong t ng này đi u khi n vi c truy n thơng qua các m ng trong h th ng v i cơng ngh chuy n m ch thích h p. T ng 4 : T ng v n chuy n (transport layer) Qui đ nh các ch c năng truy n d li u gi a hai đ u mút (end to end) như t c đ truy n, x p th t các thơng tin, t ch c s tái t o b n tin (ki m tra l i, ph c h i các t b m t trong quá trình liên l c ). Giao th c trong t ng này cũng cĩ th th c hi n vi c ghép kênh (multiplexer), tách/h p d li u khi c n thi t. T ng 5 : T ng giao d ch (session layer) Cung c p phương ti n qu n lý truy n thơng gi a các ng d ng. Giao th c c a t ng này qui đ nh các th t c thi t l p cu c đ i tho i gi a hai bên, cĩ trách nhi m thi t l p, duy trì, đ ng b hĩa và k t thúc cu c đ i tho i. T ng 6 : T ng trình bày (presentation layer) T ng này xác đ nh các qui t c ngơn ng và cĩ trách nhi m đ m b o s li u thu đư c cĩ m t cú pháp cĩ th d ch đư c trong quá trình ng d ng. Nĩi cách khác t ng này mơ t các phương pháp trình bày d li u như mã hĩa, gi i mã, nén d li u Thí d mã ASCII 8 bít dùng cho màn hình là m t qui đ nh thu c t ng 6 này. T ng 7: T ng ng d ng (application layer) T ng này qui đ nh các ng d ng th c t , đưa ra các th t c cho vi c x lý s li u c a b n thân ngư i s d ng như cách th c x lý t , so n văn b n T ng này cũng qui đ nh nh ng th t c cho ngư i s d ng cĩ th truy nh p đư c vào mơi trư ng. T ng ng d ng là t ng duy nh t khơng ph i ph c v t ng trên.
- CHƯƠNG 2 MÃ HỐ VÀ ðI U CH . N i dung: 2.1 PH T N C A TÍN HI U . 2.2 MÃ HĨA . 2.3 ðI U CH . Trong truy n thơng, tin t c và d li u là t t c nh ng gì c n trao đ i, chúng cĩ th là ti ng nĩi, hình nh, t p h p các con s , các ký hi u, các đ i lư ng đo lư ng . . . đư c đưa vào máy phát đ phát đi hay nh n đư c máy thu. Tín hi u chính là tin t c đã đư c x lý đ cĩ th truy n đi trên h th ng thơng tin. Vi c x lý bao g m chuy n đ i, mã hĩa và đi u ch . Chuy n đ i là bi n các tin t c dư i d ng khơng đi n thành ra tín hi u đi n. Mã hĩa là gán cho tín hi u m t giá tr nh phân và đ c trưng b i các m c đi n áp c th đ cĩ th truy n trên kênh truy n và ph c h i máy thu. Ði u ch là dùng tín hi u c n truy n đ làm thay đ i m t thơng s nào đĩ c a m t tín hi u khác, tín hi u này th c hi n nhi m v mang tín hi u c n truy n đ n nơi thu nên đư c g i là sĩng mang (carrier wave). M c đích c a s đi u ch là d i ph t n c a tín hi u c n truy n đ n m t vùng ph t n khác thích h p v i tính ch t c a đư ng truy n và nh t là cĩ th truy n đ ng th i nhi u kênh cùng m t lúc (đa h p phân t n s ). Chương này đ c p đ n s đi u ch và mã hĩa. Nhưng trư c tiên, chúng ta c n nh c l i m t s tính ch t c a tín hi u qua vi c phân tích tín hi u khơng sin thành t ng c a các tín hi u hình sin và lưu ý đ n m i quan h t n s th i gian c a tín hi u. 2 . 1 PH T N C A TÍN HI U : Trong m t h th ng thơng tin t n t i 3 d ng tín hi u v i ph t n khác nhau: Lo i th nh t là các tín hi u cĩ tính tu n hồn cĩ d ng hình sin ho c khơng. M t tín hi u khơng sin là t ng h p c a nhi u tín hi u hình sin cĩ t n s khác nhau. K t qu này cĩ đư c b ng cách dùng chu i Fourier đ phân tích tín hi u. Lo i th hai là các tín hi u khơng cĩ tính tu n hồn mà cĩ tính nh t th i (thí d như các xung l c), lo i tín hi u này đư c kh o sát nh bi n đ i Fourier.
- Lo i th ba là tín hi u cĩ tính ng u nhiên, khơng đư c di n t b i m t hàm tốn h c nào. Thí d nhu các lo i nhi u, đư c kh o sát nh phương ti n xác su t th ng kê. Các lo i tín hi u, nĩi chung, cĩ th đư c xét đ n dư i m t trong hai lãnh v c : Lãnh v c th i gian: Trong lãnh v c này tín hi u đư c di n t b i m t hàm theo th i gian, hàm này cho phép xác đ nh biên đ c a tín hi u t i m i th i đi m. Lãnh v c t n s : Trong lãnh v c này ngư i ta quan tâm t i s phân b năng lư ng c a tín hi u theo các thành ph n t n s c a chúng và đư c di n t b i ph t n. Trong gi i h n c a mơn h c, chúng ta ch đ c p đ n hai lo i tín hi u đ u. 2.1.1 Ph t n gián đo n 2.1.2 Ph t n liên t c . 2.1.1 Ph t n gián đo n : Tín hi u cĩ tính tu n hồn đơn gi n nh t là tín hi u hình sin v(t)=V m sin( ωt+ φ) = V msin(2 πft+ φ) Tín hi u này cĩ ph t n là m t v ch duy nh t cĩ biên đ V m t i t n s f (H 2.1) (H2.1) Các d ng tín hi u tu n hồn khác cĩ th phân tích thành t ng các tín hi u hình sin, như v y ph t n c a chúng ph c t p hơn, g m nhi u v ch các t n s khác nhau. Tín hi u thư ng g p cĩ d ng hình ch nh t mà b i phép phân tích thành chu i Fourier ta th y ph t n bao g m nhi u v ch các t n s cơ b n f và các h a t n 3f, 5f, 7f (H 2.2). (a) (H 2.2) (b) Tín hi u (H 2.2.a) phân tích thành chu i Fourier: v = V i ω = 2 π / T = 2 πf T & f l n lư t là chu kỳ và t n s c a tín hi u ch nh t.
- Lưu ý , n u d i tín hi u (H 2.2.a) lên m t kho ng V theo tr c tung thì ph t n cĩ thêm thành ph n m t chi u (H 2.3) (b) (a) (H 2.3) v = V + Xét trư ng h p chu i xung ch nh t v i đ r ng τ << T , ta cĩ tín hi u và ph (H 2.4) v = v i x = τπ / T (a) ( b) Ph t n trong trư ng h p τ = 0,1T (H 2.4) Nh n th y biên đ c a h a t n th n xác đ nh b i: Vn= (H 2.4.b) là ph t n c a tín hi u (H 2.4.a) cho trư ng h p τ = 0,1 T. Trong trư ng h p này t n s đ u tiên c a tín hi u cĩ biên đ đ t tr 0 là 10f. N u xem băng thơng BW c a tín hi u là kho ng t n s mà biên đ tín hi u đ t giá tr 0 đ u tiên (vì năng lư ng tín hi u t p trung trong kho ng t n s này) ta cĩ: BW xác đ nh b i: sin(nx) = 0
- nx = π ⇒ nπτ / T = π ⇒ n / T =1/ τ hay BW=nf = n / T =1/ τ 2.1.2 Ph t n liên t c : Ð i v i chu i xung trên khi T càng l n kho ng cách ph v ch càng thu h p l i và khi T → ∞ , chu i xung tr thành m t xung duy nh t và ph v ch tr thành m t đư ng cong liên t c cĩ d ng bao hình c a biên đ ph trư c đây (H 2.5). Ðư ng cong xác đ nh b i: V(f) = V τ (a) (b) (H 2.5) 2.2. MÃ HỐ: Vi c t o mã đ cĩ tín hi u trên các h th ng s cĩ th th c hi n m t cách đơn gi n là gán m t giá tr đi n th cho m t tr ng thái logic và m t tr khác cho m c logic cịn l i. Tuy nhiên đ s d ng mã m t cách cĩ hi u qu , vi c t o mã ph i d a vào m t s tính ch t sau: Ph t n c a tín hi u: N u tín hi u cĩ ch a t n s cao thì băng thơng c a tín hi u và c a h th ng ph i r ng N u tín hi u cĩ thành ph n DC cĩ th gây khĩ khăn trong ghép n i, thí d khơng th ghép tín hi u cĩ thành ph n DC qua bi n th và k t qu là khơng cách ly đi n đư c. Trong th c t , s truy n thơng x u nh t các c nh c a băng thơng. Vì các lý do trên, m t tín hi u t t ph i cĩ ph t n t p trung gi a m t băng thơng khơng quá r ng và khơng nên ch a thành ph n DC. S đ ng b Thư ng máy thu ph i cĩ kh năng nh n ra đi m b t đ u và k t thúc c a m t bít đ th c hi n s đ ng b v i máy phát. Nên nh là trong ch đ truy n đ ng b , máy phát và thu khơng t o ra xung đ ng h riêng r mà máy thu ph i ph c h i xung này t chu i d li u phát đ s d ng. Như v y tín hi u truy n ph i t o đi u ki n cho máy thu ph c h i xung đ ng h n trong chu i d li u, c th là ph i cĩ s bi n đ i gi a các m c thư ng xuyên. Kh năng dị sai Ð tin c y trong m t h th ng thơng tin là r t c n thi t do đĩ máy thu ph i cĩ kh năng dị sai đ s a ch a mà vi c này cĩ th c hi n d dàng hay khơng cũng tùy vào d ng mã.
- Tính mi n nhi u và giao thoa Các d ng mã khác nhau cho kh năng mi n nhi u khác nhau. Thí d mã Bipolar AMI là lo i mã cĩ kh năng phát hi n đư c nhi u. M c đ ph c t p và giá thành c a h th ng Các đ c tính này c a h th ng cũng tùy thu c vào d ng mã r t nhi u. 2.2.1 Các d ng mã ph bi n. 2.2.2 K thu t ng u nhiên hĩa. 2.2.1 Các d ng mã ph bi n : Dư i đây gi i thi u m t s d ng mã thơng d ng và đư c s d ng cho các m c đích khác nhau tùy vào các yêu c u c th v các tính ch t nĩi trên (H 2.6) Nonreturn to zero Level (NRZ L) 0 = m c cao 1 = m c th p Ðây là d ng mã đơn gi n nh t, hai tr điên th cùng d u (đơn c c) bi u di n hai tr ng thái logic. Lo i mã này thư ng đư c dùng trong vi c ghi d li u lên băng t . Nonreturn to zero inverted (NRZI) 0 = chuy n m c đi n th đ u bít 1 = khơng chuy n m c đi n th đ u bít (H 2.6) NRZI là m t thí d c a mã vi phân: S mã hĩa tùy vào s thay đ i tr ng thái c a các bít liên ti p ch khơng tùy thu c vào b n thân bít đĩ. Lo i mã này cĩ l i đi m là khi gi i mã máy thu dị s thay đ i tr ng thái c a tín hi u thay vì so sánh tín hi u v i m t tr ngư ng đ xác đ nh tr ng thái logic c a tín hi u đĩ và k t qu cho đ tin c y cao hơn. Bipolar AMI
- 0 = khơng tín hi u (hi u th = 0) 1 = hi u th âm ho c dương, luân phiên thay đ i v i chu i bít 1 liên ti p Pseudoternary 0 = hi u th âm ho c dương, luân phiên thay đ i v i chu i bít 0 liên ti p 1 = khơng tín hi u (hi u th = 0) Hai lo i mã cĩ cùng tính ch t là s d ng nhi u m c đi n th đ t o mã (Multilevel Binary), c th là 3 m c: âm, dương và khơng. L i đi m c a lo i mã này là: D t o đ ng b máy thu do cĩ s thay đ i tr ng thái c a tín hi u đi n m c dù các tr ng thái logic khơng đ i (tuy nhiên đi u này ch th c hi n đ i v i m t lo i bit, cịn lo i bít th hai s đư c kh c ph c b i k thu t ng u nhiên hĩa) Cĩ đi u ki n t t đ dị sai do s thay đ i m c đi n th c a các bít liên ti p gi ng nhau nên khi cĩ nhi u xâm nh p s t o ra m t s vi ph m mà máy thu cĩ th phát hi n d dàng. M t khuy t đi m c a lo i mã này là hi u su t truy n tin kém do ph i s d ng 3 m c đi n th . Manchester 0 = Chuy n t cao xu ng th p gi a bít 1 = Chuy n t th p lên cao gi a bít Differential Manchester Luơn cĩ chuy n m c gi a bít 0 = chuy n m c đ u bít 1 = khơng chuy n m c đ u bít Hai mã Manchester và Differential Manchester cĩ cùng tính ch t : m i bít đư c đ c trưng b i hai pha đi n th (Biphase) nên luơn cĩ s thay đ i m c đi n th t ng bít do đĩ t o đi u ki n cho máy thu ph c h i xung đ ng h đ t o đ ng b . Do cĩ kh năng t th c hi n đ ng b nên lo i mã này cĩ tên Self Clocking Codes. Do m i bít đư c mã b i 2 pha đi n th nên v n t c đi u ch (Modulation rate) c a lo i mã này tăng g p đơi so v i các lo i mã khác, c th , gi s th i gian c a 1 bít là T thì v n t c đi u ch t i đa ( ng v i chu i xung 1 ho c 0 liên ti p) là 2/T. 2.2.2 K thu t ng u nhiên hĩa (Scrambling techniques) : Ð kh c ph c khuy t đi m c a lo i mã AMI là cho m t m c đi n th khơng đ i khi cĩ m t chu i nhi u bít 0 liên ti p, ngư i ta dùng k thu t ng u nhiên hĩa. Nguyên t c c a k thu t này là t o ra m t s thay đ i đi n th giã b ng cách thay th m t chu i bít 0 b i m t chu i tín hi u cĩ m c đi n th thay đ i, dĩ nhiên s thay th này s đưa đ n các vi ph m lu t bi n đ i c a bít 1, nhưng chính nh các bít vi ph m này mà máy thu nh n ra đ cĩ bi n pháp gi i mã thích h p. Dư i đây gi i thi u hai d ng mã đã đư c ng u nhiên hĩa và đư c dùng r t nhi u trong các h thơng tin v i kho ng cách r t xa và v n t c bit khá l n: B8ZS : là mã AMI cĩ thêm tính ch t: chu i 8 bít liên t c đư c thay b i m t chu i v i 2 mã vi ph m lu t đ o bít 1 N u trư c chu i 8 bit 0 là xung dương, các bit 0 này đư c thay th b i 000 + 0 + N u trư c chu i 8 bit 0 là xung âm, các bit 0 này đư c thay th b i 000 + 0 +
- HDB3 : là mã AMI cĩ thêm tính ch t: chu i 4 bít liên t c đư c thay b i m t chu i v i 1 mã vi ph m lu t đ o bít 1 S thay th chu i 4 bít c a mã HDB3 cịn theo qui t c sau: C c tính c a xung trư c S bít 1 t l n thay th cu i đĩ cùng L ch n 000 +00+ + 000+ 00 Ngồi ra h th ng Telco cịn cĩ hai lo i mã là B6ZS và B3ZS d a theo qui lu t sau: B6ZS: Thay chu i 6 bit 0 b i 0 + 0 + hay 0 + 0 + sao cho s vi ph m x y ra bit th 2 và th 5 B3ZS: Thay chu i 3 bit 0 b i m t trong các chu i: 00 +, 00 , 0 hay + 0 +, tùy theo c c tính và s bit 1 trư c đĩ (tưong t như HDB3). Lưu ý là k thu t ng u nhiên hĩa khơng làm gia tăng lư ng tín hi u vì chu i thay th cĩ cùng s bit v i chu i đư c thay th . (H 2.7) là m t thí d c a mã B8ZS và HBD3. B = Valid bipolar signal; V = Bipolar violation (H 2.7) 2.3 ÐI U CH : Bi n đi u hay đi u ch là quá trình chuy n đ i ph t n c a tín hi u c n truy n đ n m t vùng ph t n khác b ng cách dùng m t sĩng mang đ chuyên ch tín hi u c n truy n đi; m c đích c a vi c làm này là ch n m t ph t n thích h p cho vi c truy n thơng tin, v i các t n s sĩng mang khác nhau ngư i ta cĩ th truy n nhi u tín hi u cĩ cùng ph t n trên các kênh truy n khác nhau c a cùng m t đư ng truy n. M t cách t ng quát, phương pháp đi u ch là dùng tín hi u c n truy n làm thay đ i m t thơng s nào đĩ c a sĩng mang (biên đ , t n s , pha ). Tùy theo thơng s đư c l a
- ch n mà ta cĩ các phương pháp đi u ch khác nhau: đi u ch biên đ (AM), đi u ch t n s (FM), đi u ch pha ΦM, đi u ch xung PM . . . 2.3.1 ði u ch biên đ 2.3.2 ði u ch gĩc . 2.3.3 ði u ch xung . 2.3.1 Ði u ch biên đ ( Amplitude Modulation, AM ) : Xét tín hi u cao t n e(t)=A c cos( ωct + θ) (1) Tín hi u AM cĩ đư c b ng cách dùng tín hi u g(t) làm bi n đ i biên đ c a e(t). Bi u th c c a tín hi u AM là: eAM (t) = [A c +g(t)] cos ωct (2) Ð đơn gi n, ta b qua θ là lư ng khơng đ i trong AM. Nh ng tính ch t cơ b n c a AM d dàng đư c xác đ nh n u ta bi t tín hi u g(t). Xét g(t) là tín hi u h t n: g(t)= E m cos ωmt (3) Như v y: eAM (t)=(A c + E m cos ωmt )cos ωct = A c [1+ (E m /A c )cos ωmt ]cos ωct =A c [1+m a cos ωmt] cos ωct (4) Trong đĩ m a = E m/A c g i là ch s bi n đi u (H 2.8) v d ng sĩng và ph t n c a tín hi u AM. (a) (H 2.8) (b) Ð th y đư c ph t n ta tri n khai h th c (4) e AM (t) = A ccos ωct + (m aAc/2)cos( ωc+ωm)t + (m aAc /2)cos( ωc ωm)t (5) T (H 2.8b) ta th y băng thơng c a tín hi u đã đi u ch b ng hai l n t n s c a tín hi u h t n và đư c chia ra làm hai băng c nh. Ði u ch biên đ là m t quá trình tuy n tính nên m i t n s c a tín hi u h t n t o ra m t băng thơng và trong trư ng h p tín hi u h t n g m nhi u t n s khác nhau thì băng thơng c a tín hi u bi n đi u là: BW = 2f m(max) fm (max) là t n s h t n cao nh t.
- D li u s cĩ th đư c truy n b ng phương pháp đi u ch AM, trong trư ng h p này g i là k thu t d i biên (ASK, Amplitude Shift Keying). Bit 1 đư c truy n đi b i sĩng mang cĩ biên đ E 1 và bít 0 b i sĩng mang biên đ E 2. (H 2.9) minh h a tín hi u ASK (H 2.9) 2.3.2 Ði u ch gĩc (Angle modulation) : Ta cũng b t đ u v i sĩng mang chưa đi u ch : e(t)= A ccos( ωct + f)= A ccos Φ(t) (6) N u ωc thay đ i tương ng v i ngu n thơng tin, ta cĩ tín hi u đi u ch t n s (FM) và n u Φ(t) thay đ i ta cĩ tín hi u đi u ch pha ( ΦM). Hai k thu t đi u ch này cơ b n gi ng nhau và đư c g i chung là đi u ch gĩc. 2.3.2.1 Ði u ch t n s . 2.3.2.2 Ði u ch pha . 2.3.2.1 Ði u ch t n s (FM) : T n s ω(t) là giá tr bi n đ i theo th i gian c a Φ(t), nghĩa là: ω(t) = (7) V y t n s c a tín hi u chưa đi u ch là: ω(t) = (8) Gi s tín hi u đi u ch là g(t), theo đ nh nghĩa c a phép đi u ch t n s , t n s t c th i c a sĩng mang là: ω(t)= ωc [1+ g(t) ] (9) Thay (9) vào (7): Φ(t) = (10) Thay vào pt (6): e (t) = FM (11) Bi u th c (11) cho th y tín hi u g(t) đư c l y tích phân trư c khi đư c đi u ch . Xét trư ng h p g(t) là tín hi u h t n cĩ d ng hình sin: g(t) = cos ωm(t) (12)
- ω là đ di t n và ωm là t n s c a tín hi u h t n Ф(t) = = ωct + m f sinω mt v i m f = ω /ω m là ch s đi u ch . Ðĩ là t s c a đ di t n và t n s c a tín hi u đi u ch (h t n). eFM (t) = A c cos{ ω ct + m f sinω mt} (13) Ð th y ph t n c a sĩng FM ta tri n khai bi u th c (13): e FM (t) = A cJ0(m f) cosω ct + A cJ2n (m f) [ cos(ω ct + 2ncosω mt) + cos(ω ct 2ncosω mt)] A cJ2n+1 (m f) { cos[ω c t + (2n+1)cosω mt] cos[ω ct (2n+1)cosω mt]} (14) J là hàm Bessel theo m f và n cĩ m i tr nguyên t 0 đ n ∞. T (14) ta th y sĩng FM g m thành ph n cơ b n cĩ t n s c a sĩng mang và biên đ cho b i s h ng th I , J 0(m f) , và các băng c nh cho b i các s h ng cịn l i. Vì n l y m i giá tr t 0 đ n ∞ nên ph t n c a sĩng FM r ng vơ h n, tuy nhiên do năng lư ng tín hi u gi m r t nhanh v i t n s cao nên ngư i ta xem băng thơng trong FM x p x b ng: BW = 2(m f ω m + ω m ) = 2( ω + ω m ) rad/s (H 2.10) cho d ng sĩng và ph t n c a sĩng FM (H2.10) Cũng như trong trư ng h p AM, tín hi u d li u s cũng đư c truy n b ng phương pháp FM. K thu t này đư c g i là k thu t d i t n (FSK: Frequency Shift Keying). FSK đư c dùng r ng rãi trong truy n s li u. Trong FSK bít 1 đư c truy n đi b i t n s f m và bít 0 b i t n s f s ví d , trong h th ng truy n s d ng tiêu chu n c a h ng Bell bít 1 đư c truy n b i t n s 1070 Hz (f m) và bít 0 b i t n s 1270 Hz (f s). (H 2.11) minh h a tín hi u đi u ch FSK
- (H 2.11) 2.3.2.2 Ði u ch pha (ФM ) : T phương trình (6) n u gĩc pha Ф(t) thay đ i theo tín hi u thơng tin ta cĩ đi u ch pha. V y: e PM (t) = A c cos[ω c t + m p g(t)] (15) Trong đĩ m p là đ d i pha c c đ i T n s t c th i cho b i: ω i (t) = dФ(t)/dt = ω c + m p N u g(t) cĩ d ng cos ωmt thì: ωi(t) = ω c m pωmsin ω m t (16) ePM (t) = A c cos[ω ct m p ω msin ω m t ] (17) So sánh (17) và (13), xem m p là ch s đi u ch pha, tương đương v i m f trong FM, ta cĩ th xác đ nh đư c băng thơng c a tín hi u ФM BW = 2(ω m + m pω m ) rad/s (18) mpωm = ωep là đ di t n tương đương c a ФM So sánh (11) và (15) ta th y k thu t c a FM và ФM cĩ cùng cơ s . Ði m khác bi t là trong FM ta l y tích phân c a tín hi u h t n trư c khi đi u ch cịn trong ФM thì khơng. Ði u ch pha là k thu t r t t t đ truy n s li u. Trong k thu t d i pha, PSK (Phase Shift Keying), các bít 1 và 0 đư c bi u di n b i các tín hi u cĩ cùng t n s nhưng cĩ pha trái ngư c nhau. (H 2.12) mơ t m t tín hi u FSK. (H 2.12) 2.3.3 ÐI U CH XUNG ( PULSE MODULATION) :
- Ðây là phương pháp dùng tín hi u h t n đi u ch sĩng mang là tín hi u xung (cĩ t n s cao hơn), cịn g i là phương pháp l y m u tín hi u h t n. M c dù các tín hi u tương t đư c l y m u b i các giá tr r i r c, nhưng các m u này cĩ th cĩ b t c giá tr nào trong kho ng bi n đ i c a tín hi u h t n nên h th ng truy n tín hi u này là h th ng truy n tương t ch khơng ph i h th ng truy n s . Tùy theo thơng s nào c a xung thay đ i theo tín hi u h t n, ta cĩ : Ði u ch biên đ xung (pulse amplitude modulation, PAM), đi u ch v trí xung (pulse position modulation, PPM), đi u ch đ r ng xung (pulse width modulation, PWM). 2.3.3.1 Ði u ch biên đ xung . 2.3.3.2 Ði u ch th i gian xung . 2.3.3.1 Ði u ch biên đ xung ( PAM) : Khi m t chu i xung h p v i t n s l p l i cao p(t) đư c đi u ch biên đ b i tín hi u sin t n s th p m(t), ta cĩ s đi u ch biên đ xung. Tín hi u sau khi đi u ch là tích c a hai tín hi u m(t).p(t) cĩ d ng sĩng là các xung v i biên đ thay đ i theo d ng sĩng h t n m(t) (H 2.13). (H 2.13) a. M u PAM t nhiên . b. M u PAM đ nh ph ng. a / M u PAM t nhiên (Natural PAM sampling) : Khi biên đ xung đã đi u ch cĩ đ nh theo d ng c a tín hi u m(t), ta cĩ m u PAM t nhiên (H 2.13). K t qu c a ph n 2.1.1 cho th y tín hi u p(t) cĩ th phân tích thành các thành ph n: V o + Σ V n.cos(nω st) v i V 0 = V τ / T s là thành ph n DC và ωs = 2 π / T s là t n s c a p(t). Như v y, m(t).p(t) bao g m: m(t).V o = m(t).V τ / T s và m(t). ΣVn.cos(n ωst) Tĩm l i, tích m(t).p(t) cĩ ch a d ng sĩng c a tín hi u đi u ch (tín hi u c n truy n) trong thành ph n t n s th p m(t).V 0 và cĩ th ph c h i b ng cách cho sĩng mang đã đi u ch qua m t m ch l c h thơng.
- Thành ph n h a t n cĩ d ng V nm(t)cos(n ωst) tương t như tín hi u đi u ch 2 băng c nh tri t sĩng mang (Double Sideband Suppressed Carrier, DSBSC). Ph t n c a tín hi u PAM v i h t n là m(t) = sin ωmt cĩ d ng như (H 2.14) (H 2.14) Trong (H 2.14) M(f) là ph t n c a tín hi u d i n n và fm là t n s cao nh t c a tín hi u này. T (H 2.14) ta cũng th y t i sao t n s xung l y m u fs ph i ít nh t hai l n l n hơn fm . N u M(f) đư c ph c h i t m ch l c h thơng, đ phân cách t M(f) t i d i t n k c n ph i l n hơn 0, nghĩa là W > 0 W = f s f m f m > 0 hay f s > 2 f m b / M u PAM đ nh ph ng (Flat top PAM) : Ðây là m u PAM đư c dùng r ng rãi do d t o ra sĩng đi u ch . D ng sĩng cho (H 2.15) các xung sau khi đi u ch cĩ đ nh ph ng ch khơng theo d ng c a h t n. (H 2.15) M c dù khi ph c h i tín hi u t m ch l c h thơng s cĩ bi n d ng do đo n đ nh ph ng nhưng vì b r ng xung thư ng r t nh so v i chu kỳ T s nên bi n d ng khơng đáng k . N u s bi n d ng là đáng k thì cũng cĩ th lo i b b ng cách cho tín hi u đi qua m t m ch bù tr . Tín hi u PAM ít đư c dùng đ phát tr c ti p do lư ng thơng tin c n truy n ch a trong biên đ c a xung nên d b nh hư ng c a nhi u. PAM thư ng đư c dùng như là m t bư c trung gian trong m t phương pháp đi u ch khác, g i là đi u mã xung (pulse code modulation, PCM) và đư c dùng trong đa h p th i gian đ truy n (TDM). 2.3.3.2 Ði u ch th i gian xung (Pulse time Modulation, PTM) : Ði u ch th i gian xung bao g m b n phương pháp (H 2.16). Ba phương pháp đ u t p trung trong m t nhĩm g i là đi u ch đ r ng xung (Pulse width modulation, PWM) (H
- 2.16d, e, f), phương pháp th tư là đi u ch v trí xung (Pulse position modulation, PPM) (H 2.16g). Ba phương pháp đi u ch đ r ng xung khác nhau đi m c nh lên, c nh xu ng hay đi m gi a xung đư c gi c đ nh trong khi đ r ng xung thay đ i theo tín hi u đi u ch . Phương pháp th tư, PPM là thay đ i v trí xung theo tín hi u đi u ch trong khi b r ng xung khơng đ i. (H 2.16) minh h a cho các cách đi u ch này. Lưu ý là k thu t PTM tưong t v i đi u ch FM và ΦM , tín hi u cĩ biên đ khơng đ i nên ít b nh hư ng b i nhi u. Ph t n c a tín hi u đã đi u ch b ng phương pháp PWM, PPM gi ng như ph t n c a tín hi u đi u ch FM (H 2.16h), nghĩa là cĩ nhi u h a t n nên khi s d ng PWM và PPM ngư i ta ph i gia tăng t n s xung l y m u ho c gi m đ di t n (đ gi i h n băng thơng c a tín hi u và tăng s kênh truy n).
- (H 2.16) CHƯƠNG 3 CÁC LO I MÃ TRONG TRUY N D LI U . N i dung: 3.1 MÃ NH PHÂN C A CÁC CH S . 3.2 CÁC MÃ PHÁT HI N L I . 3.3 MÃ NÉN D LI U . 3.4 M T MÃ . Tin t c bao g m các văn b n, s li u, hình nh . . . . c n đư c mã hĩa b ng t p h p các s nh phân trư c khi đư c chuy n đ i thành các tín hi u s đ truy n đi M t y u t quan tr ng trong h th ng thơng tin là đ chính xác, thi u y u t này h th ng xem như khơng cĩ giá tr s d ng, nên kèm theo b n tin thư ng ph i thêm vào các t mã cĩ kh năng phát hi n l i và th m chí s a đư c l i. Ngồi ra, n u s lư ng bít dùng đ mã hĩa cùng m t đ i tư ng càng ít thì v i cùng v n t c truy n, lư ng thơng tin truy n c a h th ng càng l n mà l i h n ch đư c kh năng x y ra l i. Do đĩ vi c gi m s lư ng bít dùng mã hĩa cũng là m t v n đ c n đư c quan tâm. Chương này bàn đ n m t s phương pháp mã hĩa d li u ph bi n đ t o các lo i mã cĩ kh năng phát hi n l i, phát hi n và s a l i, các lo i mã nén. 3.1 MÃ NH PHÂN C A CÁC CH S : Ð bi u di n các ch và s ngư i ta dùng các mã nh phân. M t s nh phân n bít bi u th đư c 2 n ký t (ch , s , các d u hi u ) Các b mã ph bi n trong truy n d li u là : mã Baudot, mã ASCII và mã EBCDIC
- 3.1.1 Mã Baudot. 3.1.2 Mã ASCII. 3.1.3 Mã EBCDIC. 3.1.1 Mã Baudot : Là b mã nh phân dùng 5 bít đ bi u di n ch s và m t s d u hi u. B ng 3.1 B mã Baudot Mã Ch D u/S Mã Ch D u/S 11000 A 11101 Q 1 10011 B ? 01010 R 4 01110 C : 10100 S BELL 10010 D $ 00001 T 5 10000 E 3 11100 U 7 10110 F ! 01111 V ; 01011 G & 11001 W 2 00101 H # 10111 X / 01100 I 8 10101 Y 6 11010 J ' 10001 Z " 11110 K ( 11111 LTRS LTRS 01001 L ) 11011 FIGS FIGS 00111 M . 00100 SPC SPC 00110 N , 00010 CR CR 00011 O 9 01000 LF LF 01101 P 0 00000 NULL NULL V i n = 5 ch cĩ 2 5 = 32 mã khác nhau, khơng đ đ bi u di n các ký t ch và s nên m t s mã ph i bi u th c hai và chúng đư c phân bi t b ng cách kèm theo ký t FIGS ho c LTRS trư c. Thí d : mã c a đo n văn NO. 27 cĩ d ng như sau : LTRS N O FIGS . SPC 2 7 11111 00110 00011 11011 00111 00100 11001 11100 Khi dùng mã Baudot đ truy n b t đ ng b , s bít stop luơn luơn là 1,5 3.1.2 Mã ASCII : Là b mã thơng d ng nh t trong truy n d li u . Mã ASCII dùng s nh phân 7 bít nên cĩ 2 7 = 128 mã, tương đ i đ đ di n t các ch , s và m t s d u hi u thơng d ng. T đi u khi n dùng trong các giao th c truy n thơng thư ng l y trong b ng mã ASCII. Khi truy n b t đ ng b dùng mã ASCII s bít stop là 1 ho c 2. B ng 3.2 trình bày mã ASCII cùng các t đi u khi n. * T đi u khi n trong văn b n:
- BS (Back space): ch cơ ch in hay con tr đư c d i lui m t v trí. Nĩ cĩ th đư c dùng đ in 2 ký t m t v trí (thư ng dùng đ g ch dư i) hay đ in đ m m t ký t (in 1 ký t 2 l n cùng v trí). Trên màn hình (CRT) ch sau s thay cho ch trư c. HT (Horizontal Tab): ch cơ ch in hay con tr đư c d i t i v trí tab k c n hay v trí d ng. LF (Line Feed): ch cơ ch in hay con tr đư c d i xu ng đ u dịng k . VT (Vertical Tab): ch cơ ch in hay con tr đư c d i đ n dịng k c a chu i dịng đã đánh d u. FF (Form Feed): ch cơ ch in hay con tr đư c d i đ n đi m b t đ u c a trang (màn nh) sau CR (Cariage Return): ch cơ ch in hay con tr đư c d i đ n đi m b t đ u trên cùng m t dịng B ng 3.2 Mã ASCII Bit 765 → 000 001 010 011 100 101 110 111 Bit 4321 ↓ 0 1 2 3 4 5 6 7 0000 0 NUL DLE SP 0 @ P ' p 0001 1 SOH DC1 ! 1 A Q a q 0010 2 STX DC2 " 2 B R b r 0011 3 ETX DC3 # 3 C S c s 0100 4 EOT DC4 $ 4 D T d t 0101 5 ENQ NAK % 5 E U e u 0110 6 ACK SYN & 6 F V f v 0111 7 BEL ETB ` 7 G W g w 1000 8 BS CAN ( 8 H X h x 1001 9 HT EM ) 9 I Y i y 1010 A LF SUB * : J Z j z 1011 B VT ESC + ; K [ k { 1100 C FF FS , N ^( ) n ~ 1111 F SI US / ? O _( ←) o DEL Thí d : ký t D là 1000100 = 44H Ý nghĩa các t trong b ng mã ASCII * T đi u khi n trong truy n thơng SOH (Start of Heading): b t đ u c a ph n đ u b n tin. Nĩ cĩ th ch a đ a ch , chi u dài b n tin hay d li u dùng cho ki m tra l i. STX (Start of Text): b t đ u văn b n đ ng th i k t thúc ph n đ u. Thư ng đi đơi v i ETX.
- ETX (End of Text): k t thúc văn b n EOT (End of Transmission): ch m d t truy n ENQ (Enquiry): yêu c u m t đài xa t xác đ nh (identify itself). ACK (Acknowledge) : t phát b i máy thu đ báo cho máy phát đã nh n b n tin đúng. NAK (Negative Acknowledgment): t phát b i máy thu đ báo nh n b n tin sai. SYN (Synchronous/Idle): dùng b i m t h th ng truy n đ ng b đ th c hi n đ ng b . Khi khơng cĩ d li u đ phát, máy phát c a h th ng đ ng b phát liên t c các t SYN ETB (End of Transmission Block): ch s ch m d t m t kh i c a b n tin. * Information separator FS (File Separator), GS (Group Separator), RS (Record Separator), US (United Separator): Dùng cho s phân cách. Ch đ u ch thành đư c phân cách (F: File, G: Group, R: Record (b ng ghi), U: Unit (đơn v )) * Miscellaneous (Linh tinh) NUL (Null): ký t r ng, dùng l p đ y kho ng tr ng khi khơng cĩ d li u BEL (Bell): dùng khi c n báo s lưu ý. SO (Shift Out): ch các t h p mã theo sau đư c thơng d ch b i ký t ngồi t p h p ký t chu n cho t i khi g p t Shift In. SI (Shift In): ch t p h p mã theo sau đư c thơng d ch b i ký t chu n. DEL (Delete): dùng b t SP (Space): kho ng cách t DLE (Data Link Escape): dùng đ ch s thay đ i nghĩa c a các t theo sau. Nĩ cĩ th cung c p m t s đi u khi n ph , hay cho phép g i ký t d li u cĩ m t t h p bít b t kỳ. DC1, DC2, DC3, DC4 (Device Control): t dùng cho s đi u khi n thi t b . CAN (Cancel): ch d li u đ t trư c nĩ khơng cĩ giá tr , do dị đư c l i. EM (End of Medium): ch s k t thúc v m t v t lý c a m t card, băng hay mơi trư ng khác. SUB (Substitute): thay th m t t b l i ho c khơng cĩ giá tr ESC (Escape) : t tăng cư ng đ cung c p m t mã m r ng. 3.1.3 Mã EBCDIC (Extended BCD Information Code) : Là b mã 8 bít đư c dùng r ng rãi trong h th ng thơng tin dùng máy tính IBM. B ng 3.3 trình bày mã EBCDIC và các ký t đi u khi n. Vì mã ký t chi m 8 bít nên mu n dùng parity ph i dùng bít th 9 (các thanh ghi trong các USART thư ng cĩ 8 bít) do đĩ mã EBCDIC thư ng đư c dùng trong nh ng ch c năng đ c bi t như trong các ng d ng đ h a. B ng 3.3 Mã EBCDIC High 0 1 2 3 4 5 6 7 8 9 A B C D E F Lơw 0 NULL DLE DS SP & 0 1 SOH DC1 SOS a J A J 1 2 STX DC2 FS SYN b k s B K S 2 3 ETX DC3 c l t C L T 3
- 4 PF RES BYP PN d m u D M U 4 5 HT NL LF RS e n v E N V 5 6 LC BS ETB UC f o w F O W 6 7 DEL IL ESP EOT g p x G P X 7 8 CAN h q y H Q Y 8 9 RLF EM i r z I R Z 9 A SMM CC SM ! ‘ : B VT $ # C FF IFS DC4 * % @ D CR IGS ENQ NAK ( ) , E SO IRS ACK + = F SI IUS BEL SUB ? “ Các mã đi u khi n khơng cĩ trong ASCII là : PF Punch Off CC Cursor Control LC Lower Case IFS Interchange File Separator UC Upper Case IGS Interchange Group Separator RLF Reverse Line Feed IUS Interchange Unit Separator SMM Start of Manual Message IRS Interchange Record Separator RES Restore DS Digit Selector NL New Line SOS Start of Significance ID Idle BYP Bypass SM Set Mode RS Reader Top PN Punch On 3.2 CÁC MÃ PHÁT HI N L I : Nh m phát hi n l i ngư i ta thêm vào dịng d li u các bít ki m tra. Phương pháp này g i chung là ki m tra l i dư th a (Redundancy error check methode), t dư th a đư c dùng vì các bít thím vào khơng ph i là ph n thơng tin c n g i đi. 3.2.1 Ki m tra ch n l . 3.2.2 Ki m tra dư th a theo chu kỳ. 3.2.3 Mã Hamming. 3.2.1 Ki m tra ch n l : Dùng ki m tra ch n l đ dị ra m t bít sai : Ðây là phương pháp ki m tra đơn gi n nh t, b ng cách thêm vào sau chu i d li u (thư ng là m t ký t ) m t bít sao cho t ng s bít 1 k c bit thêm vào là s ch n (ho c l ), máy thu ki m tra l i t ng s này đ bi t cĩ l i hay khơng. Phương pháp đơn gi n nên ch t lư ng khơng cao, n u s l i là ch n thì máy thu khơng nh n ra. Dùng ki m tra ch n l đ dị sai hai bít :
- Vì m i l n th c hi n ki m tra ch n l cho phép dị ra m t bít l i nên ta cĩ th nghĩ r ng n u th c hi n nhi u phép ki m tra đ ng th i cho phép dị đư c nhi u l i. Thí d , đ dị ra 2 l i c a m t chu i d li u cĩ th th c hi n hai phép ki m tra, m t v i các bít ch n và m t v i các bít l . Cho chu i d li u: 01101000 L n lư t th c hi n ki m tra ch n v i các bít v trí 1, 3, 5, 7 và các bít v trí 2, 4, 6, 8. G i P 1 và P 2 là các bít ki m tra: P1=0+1+1+0 = 0 và P2=1+0+0+0 = 1. Chu i d li u phát: 01101000 01. Máy thu dị ra l i khi 2 bít liên ti p b sai. Tuy nhiên, n u hai bít sai đ u là 2 bít ch n (ho c 2 bít l ) thì máy thu cũng khơng dị ra. Dùng ki m tra ch n l đ dị ra m t chu i bít sai : Ðơi khi nhi u làm sai c m t chu i d li u (ta g i là burst errors), đ dị ra đư c chu i bít sai này, ngư i ta b t chư c cách lưu và truy n d li u c a máy tính (lưu t ng bít c a m t byte trong các chip riêng đ truy n trên các đư ng khác nhau và nơi nh n s tái h p) đ th c hi n vi c ki m tra. Chu i d li u s đư c chia ra thành các khung (frames), th c hi n ki m tra cho t ng khung, thay vì phát m i l n m t khung, ngư i ta phát các t h p bít cùng v trí c a các khung, nhi u cĩ th làm h ng m t trong các t h p này và chu i bít sai này cĩ th đư c nh n ra máy thu. Thí d dư i đây minh h a cho vi c ki m tra phát hi n chu i d li u sai: G i Nh n S Bit parity S Bit parity khung c a t ng khung c a t ng (hàng) hàng (hàng) hàng 1 0 1 1 0 1 1 → 1 0 1 1 0 1 1 2 1 0 0 0 1 0 Nhi u tác 2 1 0 0 0 1 0 3 0 1 1 1 0 1 đ ng vào 3 0 1 1 0 0 1* 4 1 1 0 0 1 1 c t 4, 4 1 1 0 0 1 1 5 0 1 0 1 0 0 làm cho 5 0 1 0 0 0 0* 6 1 0 1 1 1 0 t t c 6 1 0 1 0 1 0* 7 0 1 1 0 0 0 các bit = 0 7 0 1 1 0 0 0 8 0 0 1 1 1 1 → 8 0 0 1 0 1 1* 9 1 0 0 1 1 1 9 1 0 0 0 1 1* 10 1 1 0 0 0 0 10 1 1 0 0 0 0 S c t 1 2 3 4 5 6 S c t 1 2 3 4 5 6 Máy thu dị ra các khung cĩ l i (các bít parity cĩ d u *) nhưng khơng xác đ nh đư c c t nào b sai do đĩ ph i yêu c u máy phát phát l i t t c các c t Ki m tra kh i: M t c i ti n c a ki m tra ch n l là ki m tra kh i (Block Check Character, BCC). B n tin đư c vi t thành kh i và vi c ki m tra ch n l đư c th c hi n theo c 2 chi u d c (Vertical Redundancy Check, VRC) và ngang (Longitudinal Redundancy Check, LRC)
- G i các bít c a m i ký t là b ij (i=1, , n là th t các bít trong ký t ; j=1, , m là th t c a ký t ) Rj là bít parity c a ký t th j, gi s ch n parity ch n, ta cĩ : Rj = b 1j + b 2j + + b nj Ci là bít parity c a t t c bít th i C i = b i1 + b i2 + + b im + T p h p các bít R j (j = 1, ,m) dùng ki m tra chi u d c và t p h p các bít C i (i = 1, ,n) dùng ki m tra chi u ngang. (H 3.1) cho ta d ng c a kh i d li u cĩ th c hi n ki m tra ch n theo chi u ngang và d c. bít 1 2 . . . . . . . bít n Parity Character 1 B11 B21 . . . . . . . Bn1 R1 10110111 ↓VRC Character 2 B12 B22 . . . . . . . Bn2 R2 11010111 00111010 11110000 10001011 Character m B1m B2m . . . . . . . bnm Rm 01011111 Paritycheck C1 C2 . . . . . . . Cn Cn+1 01111110 char. ←LRC (H 3.1) Phương pháp ki m tra kh i cho phép phát hi n và s a m t l i vì xác đ nh đư c v trí c a l i đĩ, chính là giao đi m c a hàng và c t cĩ bít sai. Máy thu cĩ kh năng phát hi n hai l i sai trên cùng m t hàng ho c c t nhưng khơng xác đ nh đư c v trí bít l i. Ví d hai bít 1 và 3 c a ký t th nh t cùng sai thì bít ki m tra VRC khơng phát hi n đư c nhưng bít LRC thì th y ngay. N u bây gi cĩ thêm các bít 1 và 3 c a ký t th 5 cùng sai thì máy thu s khơng phát hi n đư c, như v y cũng cịn trư ng h p khơng phát hi n đư c l i n u s l i là m t s ch n theo nh ng v trí xác đ nh nào đĩ, tuy nhiên trư ng h p này r t hi m x y ra. Tĩm l i, dùng ki m tra ch n l cho phép phát hi n l i trong m t s trư ng h p, tuy nhiên hi u su t phát s b gi m và ch đư c dùng trong các h th ng cĩ v n t c truy n th p (b t đ ng b ). Trong các h th ng truy n đ ng b ngư i ta hay s d ng mã CRC , mã này cho phép dị l i r t hi u qu và hi u su t truy n cũng cao. 3.2.2 Ki m tra dư th a theo chu kỳ :
- Ð c i thi n hơn n a vi c ki m tra l i ngư i ta dùng phương pháp ki m tra dư th a theo chu kỳ (Cyclic Redundancy Check, CRC) Nguyên t c t o mã CRC : Xét khung d li u g m k bít và n u ta dùng n bít cho khung ki m tra FCS (Frame check sequence) thì khung thơng tin k c d li u ki m tra g m (k+n) bít sao cho (k+n) bít này chia đúng cho m t s P cĩ (n+1) bít ch n trư c (dùng phép chia Modulo 2). máy thu khi nh n đư c khung d li u, l i mang chia cho s P này và n u phép chia đúng thì khung d li u khơng ch a l i. * Nh c l i m t s tính ch t c a phép tốn Mod 2 : Phép c ng Mod 2 là phép c ng nh phân khơng nh , dư i đây là thí d v phép c ng và phép nhân 1111 11001 + 1010 x 11 0101 11001 11001 101011 Phép c ng Mod 2 đư c th c hi n b i c ng EX OR Phép tr Mod 2 gi ng như phép c ng Nhân Mod 2 m t s v i 2 n tương ng v i d i s đĩ n bít v bên trái và thêm n bít 0 vào bên ph i s đĩ, thí d 11001* 2 3 = 11001000 Phép chia Mod 2 đư c th c hi n gi ng như phép chia thư ng nhưng nh là phép tr trong khi chia đư c th c hi n như phép c ng. 3.2.2.1. Xác đ nh mã CRC dùng thu t tốn Mod 2. 3.2.2.2. Dùng phép bi u di n đa th c. 3.2.2.3. Kh năng dị sai c a mã CRC. 3.2.2.4. M ch t o mã CRC. 3.2.2.1. Xác đ nh mã CRC dùng thu t tốn Mod 2 : G i T = (k+n) bít là khung thơng tin đư c phát , v i n < k M = k bít d li u, k bít đ u tiên c a T F = n bít c a khung FCS, n bít cu i c a T P = (n+1) bít, s chia trong phép tốn S T đư c t o ra b ng cách d i s M sang trái n bít r i c ng v i s F : T = 2 nM + F Chia s 2 nM cho P ta đư c : n 2 Q là s thương và R là s dư Vì phép chia th c hi n v i s nh phân nên s dư luơn luơn ít hơn s chia 1 bít. Ta dùng s dư này làm s F, nghĩa là : T = 2 nM + R. máy thu khi nh n đư c kh i d li u, mang chia cho P, k t qu s dư s = 0 :
- Vì R + R = 0 nên T / P = Q Như v y dùng s dư R c a phép chia 2 nM cho P làm ký t ki m tra trong khung FCS thì ch c ch n T s chia đúng cho P n u b n tin khơng cĩ l i. Thí d : Cho M = 1010001101 (10 bít) P = 110101 (6 bít) S ph i tìm R (5 bít) cho khung FCS đư c xác đ nh như sau : Nhân M v i 2 5 cho : 101000110100000 Th c hi n phép chia cho P 1101010110 110101 110101 ↓ 0111011 110101 ↓↓ 00111010 110101 ↓↓ 00111110 110101 ↓↓ 00101100 110101 ↓ 0110010 110101 ↓ 0001110 ← R Ta cĩ R = 01110, c ng v i 2 5M, s cho s T phát đi là : T = 101000110100000 + 01110 = 101000110101110 N u b n tin khơng cĩ l i T ph i chia đúng cho P. Th c hi n phép chia T/P ta th y s dư = 0 Tĩm l i, đ cĩ m t khung FCS n bít , ngư i ta ph i dùng m t s P cĩ n+1 bít đ t o s R cĩ n bít dùng cho khung FCS. P đư c g i là đa th c sinh (generator polynomial), d ng c a nĩ do các giao th c qui đ nh, t ng quát P ph i cĩ bít đ u và bít cu i là bít 1. 3.2.2.2. Dùng phép bi u di n đa th c : Ð th y quá trình hình thành mã CRC, ta cĩ th dùng phép bi u di n m t s nh phân dư i d ng m t đa th c c a bi n x v i h s là các s nh phân và b c c a x là giá tr ch v trí c a s nh phân đĩ. Ví d s nh phân 110101 cĩ th bi u di n b i 1.x 5 + 1.x 4 + 0.x3 + 1. x 2 + 0.x 1 + 1.x 0 = x 5 + x 4 + x 2 + 1 Chú ý mã s n bít cho b c cao nh t c a đa th c là n 1 Quá trình hình thành mã CRC th c hi n như sau :
- G i M là đa th c bi u di n thơng tin c n truy n P là đa th c sinh, b c n (ch a n+1 bit) Th c hi n phép chia n x Khung thơng tin truy n đ c trưng b i T(x) = x n M(x) + R(x) Lưu ý là nhân M(x) v i xn tương đương v i vi c d i M(x) sang trái n bít máy thu th c hi n phép chia T(x) cho P(x) s dư ph i b ng khơng L y l i thí d trên, b n tin 1010001101 tương ng v i đa th c M(x) = x 9 + x 7 + x 3 + x 2 +1 S chia P = 110101 (6 bít) tương ng v i đa th c P(x) = x 5 + x 4 + x 2 +1 x 5M(x) = x 14 + x 12 + x 8 + x 7 + x 5 Th c hi n phép chia : x 9 + x 8 + x 6 + x 4 + x 2 +x x5 + x 4 + x 2 +1 x 14 + x 12 + x 8 + x 7 + x 5 x 14 + x 13 + x 11 + x 9 x 13 + x 12 + x 11 + x 9 + x 8 + x 7 + x 5 x 13 + x 12 + x 10 + x 8 x 11 + x 10 + x 9 + x 7 + x 5 x 11 + x 10 + x 8 + x 6 x 9 + x 8 + x 7 + x 6 + x 5 x 9 + x 8 + x 6 +x 4 x 7 + x 5 + x 4 x 7 + x 6 + x 4 + x 2 x 6 + x 5 + x 2 x 6 + x 5 + x 3 + x x3 + x 2 + x = R(x) R(x) = x 3 + x 2 + x tương ng v i 01110 3.2.2.3. Kh năng dị sai c a mã CRC : M t l i x y ra m t v trí nào đĩ trong khung d li u làm đ o bít v trí đĩ c a khung, đi u này tương đương v i phép tính EX OR bít đĩ và bít 1 (vì 0+1=1 và 1+1=0). N u g i E là m t khung cĩ s lư ng bit b ng v i khung d li u, trong đĩ ch các v trí c a bít l i = 1 và các bít khác = 0 thì khung thơng tin Tr nh n đư c cĩ th vi t. Tr = T + E.
- Thí d : T = 11010111010 D ng đa th c: T(x) = x 10 + x 9 + x 7 + x 5 + x 4 + x 3 + x Gi s b n tin sai các bít x 7 , x 5 và x 4 Khung E cĩ d ng: E = 00010110000 E(x) = x 7 + x 5 + x 4 Khung d li u nh n đư c: Tr = 11000001010 Tr(x) =x 10 + x 9 + x 3 + x Lưu ý phép c ng Modulo 2, tương ng v i phép tốn EX OR, nên x 7+x 7=(1+1)x 7 = 0 Ta cĩ: Máy thu khơng nh n ra l i khi nào Tr(x) chia đúng cho P(x), hay ch khi E(x) chia đúng cho P(x). V y v i đi u ki n nào thì E(x) chia h t cho P(x)? Ta s xét m t s trư ng h p c th : @ Gi s b n tin ch sai m t bít, đa th c E(x) cĩ d ng xi, i là m t s nguyên, E(x) chia đúng cho P(x) ch khi P(x) cũng cĩ d ng x n. Ngư i ta đã ch n P(x) cĩ ít nh t là 2 s h ng nên E(x) khơng th chia đúng cho P(x). V y Mã CRC luơn luơn cho phép máy thu dị ra m t bít sai. @ Gi s b n tin sai m t chu i , nhưng cĩ t ng s bít sai là s l : đa th c E(x) ch a s l bít 1 nên E(1) =1. M t khác, gi s (x+1) là th a s c a P(x), ta cĩ th vi t P(x) = (x+1)*H(x), H(x) là m t đa th c. Ta cũng gi s l i này khơng đư c dị ra, nghĩa là E(x) chia đúng cho P(x), hay E(x) = P(x)*K(x). Thay P(x) = (x+1)*H(x) vào E(x) đư c E(x) = (x+1)*H(x)*K(x), bi u th c này cho E(1) = 0. Ði u này trái v i gi thi t trên, hay nĩi cách khác, máy thu s dị ra l i n u ta ch n P(x) sao cho chia đúng cho (x+1). V y Máy thu s luơn luơn dị ra l i g m nhi u bít và cĩ t ng s bít l i là s l n u ta ch n P(x) chia đúng cho (x+1). @ Gi s nhi u làm sai m t đo n d li u cĩ chi u dài m ( b c n c a P(x)) Gi s chu i bít sai cĩ v trí t th i đ n th i+m 1, E(x) cĩ d ng: E(x) = x i+m 1 + . . . . +x i = x i*(x m 1+ . . . +1) P(x) khơng là th a s c a xi nên E(x) ch chia đúng cho P(x) khi x m 1+ . . . +1 chia đúng cho P(x). Vì m ≤ n hay m 1 n T k t qu trên
- Nhưng bây gi m 1≥ n nên x m 1+ . . . +1 cĩ th chia đúng cho P(x). V y v n đ là cĩ bao nhiêu cơ h i đ đi u này x y ra. Trư ng h p m 1 = n hay (m=n+1). Vì b c c a P(x) là n nên đ cĩ phép chia đúng P(x) ph i cĩ d ng x n+ . . . . . +1 v i các s h ng gi a x n và 1 ph i hồn tồn gi ng v i các s h ng c a x m 1+ . . . . . +1 thì máy thu khơng dị đư c l i. Cĩ n 1 s h ng gi a x n và 1 nên cĩ 2n 1 t h p và n u các t h p này cĩ xác su t x y ra như nhau thì xác su t máy thu khơng nh n đư c l i s là 1/2 n 1. Trư ng h p m > n+1, ta ch p nh n k t qu xác su t này là 1/2 n. L y thí d mã CRC 32 (n=32), xác su t khơng dị ra m t l i cĩ chi u dài >33 bit là 1/2.10 32 (tương đương v i kh năng dị ra l i là 99,99999998%). Tĩm l i v i n càng l n vi c máy thu khơng dị ra l i càng r t khĩ x y ra. 3.2.2.4. M ch t o mã CRC : Thu t tốn mod 2 đư c th c hi n b i c ng EX OR. D i bít đư c th c hi n b i thanh ghi d ch. Quan sát phép tính chia Mod 2 c a s 2 nM cho P(x) đ cĩ R(x) ta th y đây là s k t h p c a s d i bít c a s 2 nM v i phép c ng Mod 2 c a s P(x). Trong thí d trên, đ t o mã CRC v i P(x) = 110101, ngư i ta dùng m ch (H 3.2): Cho chu i d li u là s 2 nM (g m 15 bit, 101000110100000) vào m ch, sau 15 l n d i bít, k t qu trên các thanh ghi d ch chính là R(x). M ch t o mã trong trư ng h p này g m 5 thanh ghi d ch, ký hi u A(x 5), B(x 4), C(x 3), D(x 2), E(x) . M ch t o mã CRC đư c th c hi n như sau: Thanh ghi d ch ch a n bít, b ng v i chi u dài c a khung FCS. Cĩ nhi u nh t n c ng EX OR. S cĩ m t hay khơng c a c ng EX OR tương ng v i s cĩ m t c a s h ng lũy th a b c n trong đa th c P(x) (Riêng b c cao nh t (n) c a đa th c khơng k ) (H3.2) A B C D E Bít vào
- B t 0 0 0 0 0 đ u 0 0 0 0 1 1 Bư c 1 0 0 0 1 0 0 Bư c 2 0 0 1 0 1 1 Bư c 3 0 1 0 1 0 0 Bư c 4 1* 0* 1 0* 0 0 Bư c 5 1 1 1 0 1 0* B n tin o g i Bư c 6 0 1 1 1 0 1 Bư c 7 1 1 1 0 1 1 Bư c 8 0 1 1 1 1 Bư c 9 1 1 1 1 1 0 Bư c 0 1 0 1 1 1 10 1 0 1 1 0 0 Bư c 1 1 0 0 1 0 11 0 0 1 1 1 0 5 bit 0 thêm vào Bư c 0 1 1 1 0 0 12 0 Bư c 13 Bư c 14 Bư c 15 41444444424444443 s dư Trong thí d trên P =110101 = x 5 + x 4 + x 2 + 1, nên m ch ch a ba c ng EX OR các v trí tương ng v i 1, x 2 và x 4 (x 5 ng v i thanh ghi d ch cu i cùng FFA). Ðư ng h i ti p t x 5 v x 4, x 2 và 1 (x 0) đ th c hi n phép c ng Mod 2 v i s P(x) như nĩi trên. Trong 5 bư c đ u tiên, các bit cĩ tr ng s l n c a M(x). 2 n xu t hi n ngã ra các FFD m t cách bình thư ng. T bư c th 6 các k t qu ph i k đ n tác d ng c a c ng EX OR, thí d bư c th 6 ngõ ra E chính là c ng Mod 2 c a tín hi u vào (bit 0) và tín hi u ngã ra A trư c đĩ (bit 1), t c th c hi n EX OR hai bít 0 và 1 ta đư c bit 1. Ngã ra D (bit 0) EX OR v i ngã ra A (bit 1) đ đư c bit 1 ngã ra C. Ngã ra B(bit 0) EX OR v i ngã ra A (bit 1) đ đư c bit 1 ngã ra A. Trên hình v các bit EX OR v i bit ngã ra A đư c đánh d u. Tương t như th , sau15 l n d ch (bư c 15), d li u ngã ra các FF chính là mã CRC (s dư R = 01110). Ngã ra A là MSB. Cĩ 4 da th c P(x) đư c dùng đ t o mê CRC thơng d ng: CRC_12 = x 12 +x 11 + x 3 + x 2 + x + 1 CRC_16 = x 16 +x 15 + x 2 + 1 CRC_CCITT = x 16 +x 12 + x 5 + 1 CRC_32 = x 32 + x 26 + x 23 + x 22 + x 16 + x12 + x 11 + x 10 + x 8+ x 7 + x 5 + x 4 + x 2+ x +1
- CRC_12 dùng truy n v i ký t 6 bit và khung FCS dài 12 bit. CRC_16 & CRC_CCITT dùng truy n ký t 8 bit và khung FCS dài 16 bit. ( M và Âu châu). CRC_32 Dùng trong m ng c c b (LAN) và m t s ng d ng c a DOD (Department Of Defense). 3.2.3 Mã Hamming : Mã Hamming là m t bư c phát tri n c a ki m tra ch n l và cĩ kh năng s a sai do xác đ nh đư c v trí l i. S lư ng bít c a mã Hamming tùy thu c s lư ng bít c a chu i d li u. Ta cĩ th lý lu n như sau đ xác đ nh s lư ng bít c a mã Hamming. G i m là s bít c a chu i d li u và n là s bít c a mã Hamming, t ng s bít phát đi là m+n V i n = 1 ta xác đ nh đư c 1 trong 2 k t qu : chu i d li u sai ho c đúng nhưng khơng bi t v trí l i. V i n = 2, 1 trong 4 trư ng h p x y ra: 2 phép ki m tra đ u cho k t qu đúng, 2 phép ki m tra đ u cho k t qu sai, phép ki m tra th nh t sai, phép ki m tra th hai đúng và ngư c l i. 4 trư ng h p này cho phép k t lu n đư c 1 bít sai 1 trong 3 v trí. V i n=3, cĩ 8 kh năng x y ra và ta cĩ th k t lu n đư c 1 bít sai 1 trong 7 v trí. V i s n b t kỳ, cĩ 2 n kh năng x y ra và ta cĩ th k t lu n đư c 1 bít sai 1 trong 2n 1 v trí. V y đ cĩ th phát hi n 1 l i t i 1 v trí c th thì s n nh nh t đư c ch n ph i th a: 2n 1 ≥≥≥ m + n hay 2 n ≥≥≥ m + n + 1 Các bít c a mã Hamming chèn vào v trí 2 n và dùng cho ki m tra ch n l . Các bít khác là bít thơng tin (d li u). Dư i đây là m t ví d đ th y cách xác đ nh mã Hamming: Gi s chu i d li u c n truy n g m 4 bít như sau : 1 0 1 0 V i m = 4 , ta ch n n = 3, b t đ ng th c trên đư c th a G i các bít c a mã Hamming là H 1 H 2 và H 4 (1, 2, 4 là các v trí mà ta s đ t 3 bít c a mã Hamming vào dịng d li u). G i các bít dịng d li u là X 3, X 5, X 6, X 7. T h p các bít d li u và bít mã, ta đươc 1 2 3 4 5 6 7 H 1 H 2 X 3 H 4 X 5 X 6 X 7 Gi s ta ch n Parity ch n, các bít mã s đư c xác đ nh như sau: H1⊕ X 3 ⊕ X5 ⊕ X 7 = 0 H1 =X 3 ⊕ X5 ⊕ X 7 = 1 ⊕ ( 0 ⊕ 0 ) = 1 ⊕ 0 = 1 Tương t : H2 = X 3 ⊕ X6 ⊕ X 7 = 1 ⊕ ( 1 ⊕ 0 ) = 1 ⊕ 1 = 0 H4 = X 5 ⊕ X6 ⊕ X 7 =0 ⊕ ( 1 ⊕ 0 ) = 0 ⊕ 1 B n tin bao g m bít mã tr thành: 1 0 1 1 0 1 0 máy thu đ ki m tra ngư i ta th c hi n các phép tốn:
- C1 = H1⊕ X 3 ⊕ X5 ⊕ X 7 C2 = H2⊕ X 3 ⊕ X6 ⊕ X 7 C4 = H4⊕ X 5 ⊕ X6 ⊕ X 7 N u C 1=C 2=C 4=0, khơng cĩ l i x y ra N u C 1 = 1, C 2 = C 4 = 0, m t trong các bít 1, 3, 5, 7 b l i. Nhưng C 2 = C 4 = 0 cĩ nghĩa là các bít 2, 3, 6, 7 và 4, 5, 6, 7 đã đúng. V y bít sai ph i là bít 1 Lý lu n tương t ta cĩ các trư ng h p khác. Thí d n u C 1= C 2 = C 4 = 1 thì bít l i là bít 7 Thí d b n tin nh n đư c là 1 0 1 1 1 1 0 M ch dị sai s tính C 1 , C 2 , C 4 như sau: C1 = H 1⊕ X 3 ⊕ X5 ⊕ X 7 = 1 ⊕ 1 ⊕ 1 ⊕ 0=1 C 2 = H 2 ⊕ X 3 ⊕ X6 ⊕ X 7 = 0 ⊕ 1 ⊕ 1 ⊕ 0=0 C4 = H4⊕ X 5 ⊕ X6 ⊕ X 7 = 1 ⊕ 1 ⊕ 1 ⊕ 0=1 Vì ch bít X 5 thu c c C 1 và C 4 nên bít sai là bít th 5 Quan sát t h p C 4 C 2 C 1 ta th y C 4 C 2 C 1 = 101 = (5) 10 . Như v y giá tr cĩ đư c c a t h p này cho ta bi t v trí bít sai c n s a ch a. N u t h p này b ng 0 ch ng t b n tin nh n đúng. Mã Hamming cĩ th đư c phát tri n đ dị ra hai bít sai và s a đư c m t bit l i. 3.3 MÃ NÉN D LI U : M t v n đ cũng luơn đư c quan tâm trong truy n d li u là làm th nào đ gi m thi u s bít c n thi t đ truy n m t b n tin. Như ta đã bi t, phương pháp đi u ch vi phân, ngồi tác d ng t t v m t đ ng b cịn cĩ tác d ng gi m s bít đi r t nhi u n u thơng tin cĩ tính l p l i. M t phương pháp khác là mã hĩa Run Length. Phương pháp này cho phép ngư i ta phát đi các mã thay cho các chu i ký t cĩ tính l p l i kèm theo mã đi u khi n báo cho bên thu s l n l p l i, nh mã này mà bên thu cĩ th t o l i tồn b chu i thơng tin đã truy n. Mã đ h a trong h th ng Videotex dùng m t b ng mã hình h c đ phát đi các đ h a c a máy tính ho c hình nh video. M i hình đư c phát đi là t p h p các hình cơ b n v i v trí, màu s c và kích thư c xác đ nh. Các hình cơ b n là các vịng trịn, hình ch nh t Ði u này làm gi m r t nhi u s bít c n thi t so v i vi c ph i phát đi t ng t a đ và màu c a t ng đi m trên màn hình. 3.3.1 Mã Huffman. 3.3.2 Mã Run length. 3.3.3 Mã vi phân. 3.3.1 Mã Huffman : Mã Huffman l i d ng xác su t x y ra c a các ký t khác nhau mà gán các t mã ng n cho các ký t cĩ xác su t x y ra l n và ngư c l i. Thí d , thay vì dùng 7 bít đ mã t t c các ký t như mã ASCII, ngư i ta ch gán 2 bít cho ch E và 10 bít cho ch Z, b i l , trong ti ng
- Anh xác su t xu t hi n ch E r t l n so v i xác su t xu t hi n ch Z. Mã này cịn cĩ tên Mã ph thu c t n s (frequency dependent code) V i phương pháp này s bít trung bình dùng cho m i ký t s gi m. Nhưng do các mã dài ng n khác nhau, đ máy thu phân bi t đư c, ngư i ta ph i ch n các t mã ng n sao cho khơng trùng v i các bít đ u c a các t mã dài hơn. G i là tính ti n t (prefix property). Gi i thu t Huffman: Dư i đây là các bư c t o mã Huffman Tương ng v i m i d ki n liên k t m t cây nh phân ch a duy nh t m t nút. m i cây ghi t n s xu t hi n mà ta g i là tr ng lư ng c a cây. Tìm hai cây nh nh t. N u cĩ nhi u hơn hai, ta ch n ng u nhiên hai cây trong s các cây cĩ tr ng lư ng nh nh t, ghép chúng l i thành m t cây đơn v i nút g c m i. T ng tr ng lư ng hai cây này là tr ng lư ng c a cây m i. L p l i các bư c cho t i lúc ch cịn m t cây duy nh t. Các cây ban đ u tr thành các lá c a cây nh phân cu i cùng này. Ta bi t r ng đ i v i cây nh phân thì ch cĩ m t đư ng duy nh t t g c cho t i lá. V i m i lá, đư ng t g c đ n nĩ chính là mã Huffman tương ng. Mã này xác đ nh b ng cách ghi tr 0 cho nhánh bên trái và 1 cho nhánh bên ph i (ho c ngư c l i). Thí d 1: Thi t l p mã Huffman cho các ký t A, B, C, D, E v i t n s xu t hi n l n lư t là 0,25; 0,15; 0,10; 0,20; 0,30. (H 3.3a) là cây v i 5 nút đơn ban đ u và tr ng lư ng tương ng. (H 3.3b) ghép 2 cây B và C thành m t cây m i v i tr ng lư ng là t ng tr ng lư ng cây B và C (0,25) Bư c ti p theo ta cĩ th ghép cây m i hình thành v i cây D hay cây A v i D. (H 3.3c) ghép cây m i v i D đ đư c m t cây tr ng lư ng là 0,45. (H 3.3d) ghép cây E và A Cu i cùng, ghép hai cây m i t o đ đư c m t cây duy nh t, Ghi tr 0 và 1 vào các nhánh (H 3.3e). (H3.3) Ta đư c b ng mã sau: Ký t Mã
- A 01 B 110 C 111 D 10 E 00 Chi u dài trung bình c a t mã cĩ th tính như sau: 0,25*2 + 0,15*3 + 0,10*3 + 0,20*2 + 0,30*2 = 2,25 bít/ký t Do cĩ s ch n ng u nhiên khi các d ki n cĩ cùng tr ng lư ng nên k t qu cĩ th cho các b ng mã khác nhau. Tuy nhiên, k t qu cu i cùng c a các b mã khác nhau ph i cho cùng chi u dài trung bình c a t mã. Thí d 2: Mã hố giá tr nhi t đ trong kho ng t 20 °C đ n 30 °C v i xác su t cho trong (H 3.4). Thay vì th c hi n các cây nh phân như trên, ta cĩ th d a vào xác su t c a các giá tr nhi t đ mà l p m t đ h a đ th c hi n vi c mã hĩa sao cho các giá tr cĩ xác su t l n s dùng t mã ng n nh t cĩ th cĩ. Các s ki n (là các giá tr nhi t đ ) đư c li t kê theo xác su t gi m d n (H 3.4a) Ta b t đ u b ng cách gán hai bít 0 và 1 cho 2 s ki n cĩ kh năng x y ra ít nh t, sau đĩ hai s ki n này đư c t h p thành m t s ki n cĩ xác su t b ng t ng hai xác su t c a hai s ki n đĩ, các s ki n đư c s p x p theo th t gi m d n và th t c l p l i t dư i lên và t trái sang ph i cho đ n khi hai s ki n cu i cùng đư c k t h p. T mã c a các s ki n đư c vi t b ng cách dị theo các đư ng c a sơ đ theo chi u ngư c l i, t ph i qua trái. Cu i cùng ta cĩ b ng mã (H 3.4b) T mã trung bình: 0,21*2 + 0,17*3 + 0,15*3 + 0,12*3 + 0,1*3 + 0,06*4 + 0,05*4 + 0,04*5 + 0,03*6 + 0,02*6 =3,18 bít/s ki n S bít dùng mã hĩa đã gi m kho ng 20%. M t ưu th c a phương pháp Huffman là cĩ th l p trình đ th c hi n vi c mã hĩa. Tr l i Thí d 1, bây gi gi s chu i ký t đư c phát đi là A B E C A D B C, tương ng v i chu i bít 01110001110110110111, máy thu khi nh n đư c chu i d li u s th c hi n vi c gi i mã như th nào ? Nh vào tính ti n t c a các mã, máy thu s l n lư t đ c các bít cho t i khi g p m t chu i con các bít tương ng v i m t mã s d ng l i, gi i mã ký t này, sau đĩ ti p t c đ c chu i d li u k ti p đ tìm ra ký t th hai. . .
- (a) (H3.4) (b) 3.3.2 Mã Run length : Mã Huffman tuy cĩ làm gi m s bít truy n đi nhưng nĩ địi h i d li u ph i đư c t p h p thành t ng nhĩm hay ký t đ xác đ nh t n s l p l i c a các nhĩm hay ký t này. Vi c này đơi khi r t khĩ th c hi n đ i v i m t s lo i d li u thí d như d li u t m t b n fax, tín hi u mã hình nh . . . L y thí d trư ng h p b n fax, d li u đư c phát đi khơng ph i là các ký t mà là các bít tương ng v i đi m sáng t i trên t gi y, như v y ph i cĩ m t k thu t phù h p đ nén chu i d li u này, đĩ chính là mã Run length. Mã Run length đư c t o ra b ng cách quan sát chu i bit 0 (ho c 1) liên ti p và thay th chi u dài chu i bít này b i m t s nh phân. máy thu khi nh n đư c các s nh phân s thay các s này b i các bít 0 (ho c 1) đ ng th i chèn các bít khác lo i vào. Thí d ta ph i t o mã Run length cho chu i d li u sau b ng cách dùng s 4 bít thay cho s bit 0 liên ti p: Dịng d li u 0 . . . 0 1 0 . . . 0 1 1 0 . . . 0 1 0 . . . 0 1 1 0 . . . 0 91 bít S bít 0 liên ti p 14 9 20 30 11 Run length (nh phân) 1110 1001 0000 1111 0101 1111 1111 0000 0000 1011 40 bít Run length (th p phân) 14 9 0 15 5 15 15 0 0 11 Nh n xét cách t o mã : 1 bít 1 gi a các chu i bít 0 s khơng đư c mã, máy thu t đ ng chèn bít 1 này vào khi ph c h i d li u. N u cĩ 2 bít 1 liên ti p, ta xem như cĩ 1 chu i g m khơng bít 0 gi a 2 bít 1 này và ph i đư c thay th b i s 0000. N u s s 0 nhi u hơn 15 ta ph i dùng 2 s nh phân thay cho chu i này (20=15+5; 30=15+15). máy thu khi g p chu i b n bít 1 nĩ ph i hi u là ph i l y t ng s này v i các s phía sau, n u s sau cùng cũng g m 4 bít 1, máy thu ph i đư c báo b ng chu i 4 bít 0 theo sau (trư ng h p sau s 30)
- N u chu i d li u b t đ u b ng bit 1 thì máy phát s g i đi 4 bít 0 đ u tiên. K thu t nén này ch cĩ hi u qu khi chu i d li u ch a r t nhi u m t lo i bit. Ngồi ra, k thu t nén Run length cũng đư c dùng mã hĩa các chu i ký t gi ng nhau b ng cách thay m i chu i ký t liên ti p b ng con s ch đ dài đ ng trư c ký t đĩ. Thí d , v i chu i HHHHHFFFFFFFFYYYYYYYYYYYYYGGGGGGGGGG S cĩ mã là: 5H8F13Y10G 3.3.3 Mã vi phân (Differential encoding) : Cịn g i là mã tương đ i (Relative encoding) Trong nhi u trư ng h p, các d li u liên ti p nhau thay đ i r t ít . Thí d trư ng h p mã tín hi u hình nh trong k thu t video, do ph i x lý 30 bán nh (khung) trong m t giây đ t o nh đ ng, nên chi ti t c a các nh khơng khác nhau bao nhiêu, thay vì ph i nén tín hi u t ng khung ngư i ta nghĩ t i vi c xác đ nh s khác nhau c a các khung liên ti p, mã thơng tin này và g i đi. Nguyên t c c a mã vi phân như sau: khung th nh t đư c phát đi đ ng th i lưu b đ m c a máy phát và thu. Máy phát s so sánh khung th hai v i khung th nh t này, mã s khác bi t và phát đi dư i d ng m t khung. Máy thu khi nh n khung th hai, nh các mã ch s khác bi t mà so sánh v i khung th nh t (đã lưu trư c đĩ) đ tái t o khung th hai, đ ng th i nĩ lưu khung th hai này trong b đ m và quá trình ti p t c v i các khung m i. (H 3.5) là m t thí d minh h a. 5 7 6 2 8 6 6 3 5 6 5 7 6 2 8 6 6 3 5 6 5 7 6 2 8 6 6 3 5 6 6 5 7 5 5 6 3 2 4 7 6 5 7 6 5 6 3 2 3 7 6 5 8 5 5 6 3 3 3 7 8 4 6 8 5 6 4 8 8 5 8 4 6 8 5 6 4 8 8 5 8 4 6 8 5 6 4 8 8 5 5 1 2 9 8 6 5 5 6 6 5 1 3 9 8 6 5 5 7 6 5 1 3 9 7 6 5 5 8 6 5 5 2 9 9 6 8 9 5 1 5 5 2 9 9 6 8 9 5 1 5 5 2 9 9 6 8 9 5 1 Khung th nh t Khung th nhì Khung th ba 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Khung phát đi là sai Khung phát đi là sai bi t gi a khung th bi t gi a khung th nhì và khung th nh t ba và khung th nhì (H 3.5) D li u g m các s nguyên đư c bi u di n trong m t khung 2 chi u, chúng khơng mang m t ý nghĩa c th nào, m c đích c a thí d là đ hi u cách t o mã. Khung th nh t ch a m t t p h p các s nguyên và khung th hai ch a m t t p h p các s nguyên khác khung th nh t m t ít.
- Trong hình, các khung n m dư i khung th hai và th ba là khung ch a các mã vi phân, s 0 ch khơng cĩ s khác bi t d li u c a 2 khung, s 1ch d li u khung sau l n hơn khung trư c 1 đơn v và s 1 ch ngư c l i. Dĩ nhiên cĩ th s d ng các s khác hơn là 1 và 1. Thí d cho ta th y s xu t hi n m t chu i dài các bít 0 và cĩ th đư c nén nh phương pháp Run length. 3.4 M T MÃ : Trong nhi u trư ng h p, b n tin c n đư c gi bí m t đ i v i đ tam nhân thì vi c mã hĩa đư c th c hi n dư i d ng m t: b n tin đư c mã b i m t khĩa mà ch hai ngư i liên h trong trao đ i thơng tin bi t đ s d ng khi mã hĩa và gi i mã. G i b n tin ban đ u là P (Plaintext), b n tin đã cài m t mã là C (Ciphertext) thì C = Ek(P), E và k là gi i thu t và khĩa t o mã ( Algorithm & Encryption key). Nơi nh n, nh n b n tin C và ph c h i l i P v i gi i thu t và khĩa là D và k ’ : P =D k’(C) = D k’ E k(P). Trong đa s trư ng h p (nhưng khơng ph i luơn luơn) k=k’. Gi i thu t và khĩa càng ph c t p thì đ an tồn c a b n tin càng cao. Chúng ta s xét m t s cách t o m t mã t đơn gi n đ n ph c t p. 3.4.1.Mã Caesar 3.4.2. Mã đa m u t . 3.4.3. Mã chuy n v . 3.4.4. Mã DES. 3.4.1. Mã Caesar (Caesar cipher) : Cịn g i là mã m u t đơn (mono alphabetic cipher) Ðây là lo i m t mã cĩ s m nh t và đơn gi n nh t. Ngư i ta s thay các ký t c a b n tin b ng các ký t khác theo m t qui lu t nào đĩ, thí d b ng cách c ng m t s nguyên vào mã ASCII c a các ký t ta s cĩ m t b n tin m t. Thí d c ng 1 vào mã ASCII ta s cĩ ký t B thay cho A, C thay cho B . . . . Và nơi nh n s gi i mã b ng cách tr 1 cho các mã nh n đư c trư c khi tra b ng mã ASCII. Vì gi i thu t t o mã quá đơn gi n nên b n tin cĩ th đư c gi i mã m t cách d dàng mà khơng c n bi t trư c khĩa. Thí d , trong ti ng Anh, các ký t E, T, O và N là các ký t thư ng xu t hi n nhi u l n trong các văn b n nên khi g p b n mã ngư i ta cĩ th thay các ký t l p l i nhi u l n b ng các ký t này. Sau vài th nghi m cĩ th th y đư c qui lu t và suy ra b n tin. Ð minh h a, gi s m t ngư i nh n đư c b n tin sau: {;RSDR\SFF\,PMRU \YP\,U \NSML \ SVVPIMY \ $234567890 Trư c nh t ngư i ta li t kê các ký t thư ng x y ra : \ (7 l n), S (4 l n), R, P và M (3 l n), như v y ngư i ta cĩ th thay th các ký t S, R, P, M b i E, T, O, A và N (in đ m):
