Bài gi ng: Truy n s li u ả ề ố ệ Ch ng 9: Phát hi n và s a l iươ ệ ử ỗ
CH NG 9:ƯƠ
PHÁT HI N VÀ S A L I Ệ Ử Ỗ
Vi c phát hi n và s a l i đ c thi t l p ệ ệ ử ỗ ượ ế ậ ở l p k t n i d li uớ ế ố ữ ệ ho c ặl p v nớ ậ
chuy nể trong mô hình OSI.
9.1 CÁC D NG L IẠ Ỗ
Có 2 d ng l i: L i m t bit và l i nhi u bit (burst)ạ ỗ ỗ ộ ỗ ề
Errors
burst
Single-bit
+ L i m t bit:ỗ ộ Ch có m t bit b sai trong m t đ n v d li u (byte, ký t , đ nỉ ộ ị ộ ơ ị ữ ệ ự ơ
v d li u, hay gói)ị ữ ệ
Ví d : ụthay đ i t 1 ổ ừ 0 ho c t 0 ặ ừ 1.
00000010 (STX: start of text) khi b sai 1 bit d li u nh n đ c ị ữ ệ ậ ượ 00001010 (LF: line
feed)
01000000
0 thay đ i thành ổ1
01010000
nh nậg iở
L i m t bit ỗ ộ ít xu t hi nấ ệ trong ph ng th c truy n n i ti p. Th ng xu t hi n trongươ ứ ề ố ế ườ ấ ệ
truy n song song. ề
+ L i b t:ỗ ệ có hai ho c nhi u bit sai trong đ n v d li u.ặ ề ơ ị ữ ệ
Nhi u b t không có nghĩa là các bit b l i liên t c, chi u dài c a b t tính t bit saiễ ệ ị ỗ ụ ề ủ ệ ừ
đ u tiên cho đ n bit sai cu i. M t s bit bên trong b t có th không b sai.ầ ế ố ộ ố ệ ể ị
00100010 11000010
10111010 11000010
Received
Sent
Bits corrupted by burst error
Hình 3
Length of burst
error (5 bits)
Hình 9.1
Nhi u b t th ng xu t hi n trong truy n n i ti p. ễ ệ ườ ấ ệ ề ố ế
Biên d ch: Nguy n Vi t Hùng ị ễ ệ Trang 135
Bài gi ng: Truy n s li u ả ề ố ệ Ch ng 9: Phát hi n và s a l iươ ệ ử ỗ
9.2 PHÁT HI N L IỆ Ỗ
+ Mã th a (Redundancy)ừ
Checking
function
Accept
Reject
101000000001010101010 1011101
Generating
function
101000000001010101010
1011101
Data
Redundancy check
Data & redundancy check
Receiver Sender
Hình 4
•Ý t ng thêm các thông tin ph vào trong b n tin ch nh m m c đích giúpưở ụ ả ỉ ằ ụ
ki m tra l i.ể ỗ
•Mã th a s đ c lo i b sau khi đã xác đ nh xong đ chính xác c a quáừ ẽ ượ ạ ỏ ị ộ ủ
trình truy n. ề
Có b n d ng ki m tra l i c b n dùng mã th a trong truy n d li u:ố ạ ể ỗ ơ ả ừ ề ữ ệ
•VRC (vertical redundancy check): ki m tra tính ch n l c a t ng bit ‘1’ trongể ẵ ẻ ủ ổ
m t ộđ n v d li u.ơ ị ữ ệ
•LRC (longitudinal redundancy check): ki m tra tính ch n l c a t ng các bitể ẵ ẻ ủ ổ
‘1’ trong m t kh i.ộ ố
•CRC (cyclic redundancy check) : ki m tra chu kỳ d .ể ư
•Checksum: ki m tra t ng.ể ổ
Ba d ng đ u, VRC, LRC, và CRC th ng đ c thi t l p trong l p v t lý đ dùngạ ầ ườ ượ ế ậ ớ ậ ể
trong l p k t n i d li u. D ng checksum th ng đ c dùng trong các l p trên.ớ ế ố ữ ệ ạ ườ ượ ớ
Detection methods
ChecksumVRC CRC
LRC
9.3 VRC (ki m tra parity (ch n/lể ẵ ẻ)
Thêm m t bit (0 ho c 1) vào đ n v d li u sao cho t ng s bit ‘1’ là m t sộ ặ ơ ị ữ ệ ổ ố ộ ố
ch n.ẵ
Đ c đi m:ặ ể M t bit th a ộ ừ (bit parity) đ c g n thêm vào các đ n v d li u sao choượ ắ ơ ị ữ ệ
t ng s bit ‘1’ trong đ n v d li u (bao g m bit parity) là m t s ch n (even).ổ ố ơ ị ữ ệ ồ ộ ố ẵ
•Gi s ta mu n truy n đ n v d li u nh phân ả ử ố ề ơ ị ữ ệ ị 1100001 [ASCII là a (97)];
1100011 [ASCII là c (99)];
•Ta th y t ng s bit 1 là 3 (a), t c là m t s l ; t ng s bit 1 là 4 (c), t c là m tấ ổ ố ứ ộ ố ẻ ổ ố ứ ộ
s ch n.ố ẵ
•Tr c khi truy n, ta cho đ n v d li u qua b t o bit parity, đ g n thêm vàoướ ề ơ ị ữ ệ ộ ạ ể ắ
đ n v d li u m t bit, làm t ng s bit 1 ơ ị ữ ệ ộ ổ ố là s ch nố ẵ .
Biên d ch: Nguy n Vi t Hùng ị ễ ệ Trang 136
Bài gi ng: Truy n s li u ả ề ố ệ Ch ng 9: Phát hi n và s a l iươ ệ ử ỗ
•H th ng ệ ố truy n d li u v i parity bitề ữ ệ ớ này vào đ ng truy n: ườ ề 11000011,
11000110
•Thi t b thu, sau khi nh n s đ a đ n v d li u sang hàm ki m tra parityế ị ậ ẽ ư ơ ị ữ ệ ể
ch n. ẵ
•N u d li u nh n đ c có t ng s bit 1 là s ch n thì ch p nh n.ế ữ ệ ậ ượ ổ ố ố ẵ ấ ậ
•N u d li u nh n đ c có t ng s bit 1 là s l thì lo i toàn đ n v d li u.ế ữ ệ ậ ượ ổ ố ố ẻ ạ ơ ị ữ ệ
Checking function
Is total number of 1s even?
Even-parity
generator
1100001 1
1100001
1
Data
Sender
Receiver
VRC
Hình 6
Hình 9.2
+ M ch t o bit Parity ch n (VRC): ạ ạ ẵ
Ví d : ụM ch t o bit VRC c a m t d li u 7 bit: 1100001ạ ạ ủ ộ ữ ệ
d0
d2
d3
d1
d5
d4
d6
VRC
0 1
1
1
1
1
0
0
00
1
1
1
+ M ch ki m tra bit Parity ch n (VRC): ạ ể ẵ
Ví d : ụM ch ki m tra VRC c a m t d li u 8 bit: 1100001ạ ể ủ ộ ữ ệ 1.
N u E=1 d li u sai, E=0 d li u đúng.ế ữ ệ ữ ệ
Biên d ch: Nguy n Vi t Hùng ị ễ ệ Trang 137
Bài gi ng: Truy n s li u ả ề ố ệ Ch ng 9: Phát hi n và s a l iươ ệ ử ỗ
E
R 1
R
12
D 1
L E D
12
1
1
1
1
0
0
0
0
0
1
0
0
0
0
0
Ví d 1:ụ
Gi s ta mu n truy n t ả ử ố ề ừ “world” trong mã ASCII, năm ký t này đ c mã hóa nhự ượ ư
sau:
1110111 1101111 1110010 1101100 1100100
w o r l d
B n ký t đ u có s bit m t là ch n, nên có bit parity là 0, còn ký t cu i có s bit 1ố ự ầ ố ộ ẵ ự ố ố
là l nên có bit parity là 1 (các bit parity đ c g ch d i)ẻ ượ ạ ướ
11101110 11011110 11100100 11011000 11001001
Ví d 2:ụ
Gi s ký t t o đ c t Ví d 1 đ c máy thu nh n đ c nh sau:ả ử ự ạ ượ ừ ụ ượ ậ ượ ư
11101110 11011110 11100100 11011000 11001001
Máy thu đ m s bit 1 và nh n ra có s bit m t là ch n và l , phát hi n có l i, nênế ố ậ ố ộ ẵ ẻ ệ ỗ
lo i b n tin và yêu c u g i l i.ạ ả ầ ở ạ
+ Hi u năngệ:
•VRC có th phát hi n l i 1 bitể ệ ỗ .
•Đ ng th i cũng có th phát hi n các l i b t mà t ng s bit sai là s l (1, 3,ồ ờ ể ệ ỗ ệ ổ ố ố ẻ
5, v,v....)
Ví d : ụ
1000111011,
- N u có ba bit thay đ i thì k t qu s là l và máy thu phát hi n ra đ c:ế ổ ế ả ẽ ẻ ệ ượ
1111111011: 9 0110 0111011:7
- Tr ng h p hai bit b l i: 1ườ ợ ị ỗ 110111011:8 1100011011:6 1000011010:4
Máy thu không phát hi n đ c ra l i và ch p nh n.ệ ượ ỗ ấ ậ
Biên d ch: Nguy n Vi t Hùng ị ễ ệ Trang 138
Bài gi ng: Truy n s li u ả ề ố ệ Ch ng 9: Phát hi n và s a l iươ ệ ử ỗ
9.4 LRC
LRCKi m tra m t kh i bit. Kh i bitể ộ ố ố đ c s p x p thành b ng (hàng và c t). ượ ắ ế ả ộ
+T o LRC:ạ
Ví d :ụ G i m t kh i có ở ộ ố 32 bit
- S p x p d li u thành 4 hàng và 8 c t.ắ ế ữ ệ ộ
- Tìm bit VRC cho m i c t ỗ ộ
- T o m t hàng m i g m 8 bit, đó là LRCạ ộ ớ ồ
- G i kèm LRC vào cu i d li u.ở ố ữ ệ
11100111 11011101 00111001 10101001
11100111 11011101 00111001 10101001 10101010
11100111
11011101
00111001
10101001
10101010LRC
Hình 7
Original data plus LRC
Original data
+ Ki m tra LRCể
Ví d : Thu m t kh i có ụ ộ ố 40 bit
- S p x p d li u nh n đ c thành 5 hàng và 8 c t (gi ng bên phát).ắ ế ữ ệ ậ ượ ộ ố
- Tìm bit VRC cho m i c t, n u VRC b ng 1 thì d li u b sai.ỗ ộ ế ằ ữ ệ ị
- N u VRC c a m i c t b ng 0 thì d li u đúng.ế ủ ỗ ộ ằ ữ ệ
- N u LRC bên thu là zêrô thì d li u đúng. Ng c l i d li u b sai.ế ữ ệ ươ ạ ữ ệ ị
D li u đúngữ ệ
11100111
11011101
00111001
10101001
10101010
LRC
Bên
thu
D li u nh nữ ệ ậ
11100111 11011101 00111001 10101001 10101010
00000000
Biên d ch: Nguy n Vi t Hùng ị ễ ệ Trang 139