Chuong 3 Mo hinh OSI - Mục đích chính của một hệ thống truyền thông là sự trao đổi dữ liệu giữa hai đối Show Preview textCHƯƠNG 9:PHÁT HIỆN VÀ SỬA LỖIViệ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 CÁC DẠNG LỖICó 2 dạng lỗi: Lỗi một bit và lỗi nhiều bit (burst)+ 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. 0000 0 010 (STX: start of text) khi bị sai 1 bit dữ liệu nhận được 0000 1 010 (LF: line feed) 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. Hình 9. Nhiễu bệt thường xuất hiện trong truyền nối tiếp. 9 PHÁT HIỆN LỖI+ Mã thừa (Redundancy) Hình 9. Ý 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. 9 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. Nếu E=1 dữ liệu sai, E=0 dữ liệu đúng. E 1 R1R 2 1 D1LED 2 1 1 1 1 0 0 0 0 0 01 00 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: 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) Ví dụ 2: Giả sử ký tự tạo được từ Ví dụ 1 được máy thu nhận được như sau: Máy thu đếm số bit 1 và nhận ra có số bit 1 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,
9 LRCLRCKiể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 Hình 7 LRC 10101010 Original data plus LRC Original data
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. Hình 9. Tuy nhiên, có nhiễu bệt độ dài tám bit xuất hiện, làm một số bit bị lỗi: Khi máy thu kiểm tra LRC, một số bit không theo đúng parity chẵn và toàn khối bị loại (các giá trị sai được in đậm) + Hiệu năng :
9 CRC (CYCLIC REDUNDANCY CHECK): + Sơ đồ khối của Bên phát và Bên thu của phương pháp CRC: Divisor: số chia (đa thức sinh), có số bit là n+1 ; Dữ kiện cho trước, giống nhau ở bên phát và bên thu. CRC: số dư của phép chia bên phát, có số bit là n. Remainder: số dư phép chia bên thu. Nếu số dư này zêrô dữ liệu thu không bị sai, ngược lại dữ liệu thu bị sai. Data: Dữ liệu cần mã hoá lỗi CRC. Data 00.. Số chia CRC n bits n + 1 bits n bits Số dư Bên phát m bits Thương số Hình 9. Các bit thừa trong dạng mã hoá CRC có được bằng cách chia đơn vị dữ liệu với một số chia (divisor) cho trước và dư số là CRC. Yêu cầu đối với CRC gồm hai yếu tố: Có số bit nhỏ hơn số bit bộ chia 1 bit. Được gắn vào cuối chuỗi dữ liệu + Các bước tìm CRC: Thêm n bit ‘0’ vào đơn vị dữ liệu, số n này nhỏ hơn một so với (n+1) bit của bộ chia (divisor). Dữ liệu mới này được chia cho số chia dùng phép chia nhị phân. Kết quả có được chính là CRC. CRC với n bit của bước hai thay thế các bit 0 gắn ở cuối đơn vị dữ liệu (CRC có thể chứa toàn bit ‘0’). + Tại máy thu: Đơn vị dữ liệu đến máy thu với phần đầu là dữ liệu, tiếp đến là CRC. Máy thu xem toàn chuỗi này là một đơn vị và đem chia chuỗi cho cùng số chia đã được dùng tạo CRC. Khi chuỗi dữ liệu đến máy thu không lỗi, thì bộ kiểm tra CRC có số dư là 0 và chấp nhận đơn vị dữ liệu này. Khi chuỗi bị thay đổi trong quá trình truyền, thì số dư sẽ khác không và bộ thu không chấp nhận đơn vị này. 9.5 Bộ tạo CRC Bộ CRC dùng phép chia modulo–2. Trong bước đầu, bộ chia bốn bit được trừ đi. Mỗi bit trong bộ chia được trừ với các bit tương ứng mà không ảnh hưởng đến bit kế tiếp. Trong Ví dụ này, bộ chia 1101, được trừ từ bốn bit của số bị chia 100, có được 100 (bit 0 đầu bị bỏ qua). Bước kế tiếp, lấy 1000 – 1101, thực hiện tương tự nhu phép chia. Trong quá trình này, bộ chia luôn bắt đầu với bit 1; và hệ thống thực hiện phép chia theo cách trừ nhị phân không có số nhớ (tức là 0 – 0 = 0; 1 – 1 = 0; 0 – 1 = 1; 1 – 0 =1). Hình 9. Số dư bên thu là Zêrô Dữ liệu Y đúng.
9. 2 Bộ kiểm tra CRC Bộ này hoạt động giống hệt như bộ phát. Sau khi nhận được giữa liệu có gắn thêm phần CRC, mạch thực hiện lại phép chia modulo – 2. Nếu kết quả là 0, cắt bỏ phần CRC và nhận dữ liệu; ngược lại thì loại bỏ dữ liệu và yêu cầu gởi lại. Giả sử là không có lỗi, dư số là 0 và dữ liệu được chấp nhận. Hình 9. 9. 3 Các đa thức: Bộ tạo CRC (bộ chia) thường không chỉ là chuỗi các bit 1 và 0, nhưng tạo ra từ đa thức đại số. Các đa thức này tiện lợi vì hai lý do: Chúng thường ngắn và thường được dùng để chứng minh các ý niệm toán học trong quá trình CRC. Đa thức của bộ chia: ∑ (ký số. xi); với i là vị trí của ký số, i= 0÷ n; bộ chia có n+1 bit. Quan hệ giữa chuỗi đa thức với biểu diễn nhị phân được minh họa ở hình sau: Một đa thức sinh của bộ chia cần được chọn theo các đặc tính sau: - Không được chia hết cho thức x - Chia đúng cho đa thức (x + 1) Hình 9. Ví dụ 6: Cho một khối dữ liệu có 16 bit: 10101001 00111001. Mã hoá lỗi chuỗi dữ liệu trên dùng phương pháp checksum 8 bit. Tìm checksum và chuỗi dữ liệu phát. Giải: Chia dữ liệu thành 2 phần, mỗi phần 8 bit 10101001 00111001 00011101 Checksum 10101001 00111001 11100010 00011101 Tổng Lấy bù 1 Chuỗ dữ liệu phát 9.6 Bộ kiểm tra Checksum: Máy thu thực hiện các bước như sau: Bộ kiểm tra checksum sẽ chia các đơn vị dữ liệu thành k phần mỗi phần n bit (giống như bên phát). Cộng các phần trên, được tổng (Sum). Lấy bù 1 của tổng. Nếu kết qủa lấy bù là zêrô thì dữ liệu thu không bị sai, nguợc lại dữ liệu bị sai. Ví dụ 7: Giả sử máy thu nhận được chuỗi bit được mã hoá lỗi dạng checksum. Dữ liệu này đúng hay sai? Giải: Chia dữ liệu thành 3 phần, mỗi phần 8 bit Ví dụ 8: Giả sử máy thu nhận được chuỗi bit được mã hoá lỗi dạng checksum. Dữ liệu này đúng hay sai? Giải: Chia dữ liệu thành 3 phần, mỗi phần 8 bit Bù 1 của tổng khác zêrô nên dữ liệu thu bị sai Ví dụ 9: sai 2 bit 0, 1 của 2 phân đoạn có vị trí giống nhau. 1010100100111101000110011111111100000000Tổng Bù 1 Sai không phát hiện được Hiệu năng : Checksum phát hiện được tất cả các lỗi bit lẻ cùng như hầu hết các bit chẵn. Tuy nhiên, nếu một hay nhiều bit trong phân đoạn bị hỏng và bit tương ứng hay bit có giá trị đảo trong phân đoạn thứ hai cũng bị lỗi, thì khi lấy tổng, không nhận ra thay đổi và máy thu không phát hiện lỗi được. Nếu bit cuối trong một phân đoạn là 0 và bi đổi thành 1 khi truyền, thì ta không thể phát hiện ra lỗi nếu bit 1 cuối của phân đoạn thứ hai cũng chuyển thành 0. 9 SỬA LỖICó hai cách sửa lỗi là: Khi phát hiện một lỗi, máy thu phải yêu cầu máy phát truyền lại dữ liệu. Máy thu dùng các mã sửa lỗi, để sửa tự động một số lỗi. Bảng B cho thấy một số khả năng của các giá trị m và r tương ứng. Số lượng bit dữ liệu ( m ) Số lượng bit dư ( r ) Tổng số bit ( m+r ) 1 2 3 2 3 5 3 3 6 4 3 7 5 4 9 6 4 10 7 4 11 Mã Hamming Ta đã xem xét số lượng bit cần thiết để phủ toàn bộ trạng thái bit lỗi có thể có khi truyền. Nhưng điều còn lại là phải xử lý như thế nào để biết được trạn thái đang xuất hiện? R.W cung cấp một giải pháp thực tiển. Định vị của các bit dư Mã Hamming có thể được áp dụng vào đơn vị dữ liệu có chiều dài bất kỳ dùng quan hệ giữa dữ liệu và các bit dư đã được khảo sát trước đây. Thí dụ, mã 7 bit ASCII cần có 4 bit dư được thêm vào phần cuối đơn vị dữ liệu hay phân bố vào bên trong các bit gốc. Các bit này được đặt ở các vị trí 1, 2, 4 ,8,.... (2n). Ta gọi các bit này lần lượt là r 1 , r 2 , r 4 và r 8. Hình 9. Trong mã Hamming, mỗi bit r là bit VRC của một tổ hợp các bit dữ liệu ; r 1 là bit VRC của một tổ hợp bit; r 2 là một bit trong một tổ hợp bit khác và cứ thế tiếp tục. Tổ hợp được dùng để tính toán mỗi giá trị trong bốn bit r này trong chuỗi bảy bit được tính toán như sau: r 1 (bit 1), 3, 5, 7, 9, 11 ; tổng số bit 1 là một số chẵn r2 (bit 2), 3, 6, 7, 10, 11 ; tổng số bit 1 là một số chẵn r4 (bit 4), 5, 6, 7 ; tổng số bit 1 là một số chẵn r8 (bit 8), 9, 10, 11 ; tổng số bit 1 là một số chẵn Mỗi bit dữ liệu có thể tính đến trong nhiều hơn một lần tính VRC. Thí dụ, trong chuỗi trên, mội bit dữ liệu gốc được tính đến trong ít nhất hai tập, trong khi r chỉ được tính một lần. Để tìm các mẫu trong chiến lược tính toán này, hảy xem cách biểu diễn của mỗi vit trí bit. Bit r 1 được tính dùng tất cả các vị trí bit có cách biểu diễn nhị phân có 1 trong vị trí tận cùng bên phải. Bit r 2 được tính dùng tất cả các vị trí bit có cách biểu diễn nhị phân có 1 trong vị trí thứ hai bên phải và tiếp tục như vẽ trong hình 9. Hình 9. 9.7 Các bit dư Ví dụ: Cho một dữ liệu 1001101, tìm chuỗi dữ liệu được mã hoá dạng Hamming. Giải: Xác định số bit dư: số bit của dữ liệu là m=7; Suy ra số bit dư r theo bất đẳng thức: 2 r m+r+ m= 7 2 r 7+r+1 ; chọn r= Tính toán các giá trị r: Hình 9. r4 bên thu, 0, 0, 1, 0 ; tổng số bit 1 là một số chẵn → r 4 = r8 bên thu, 1, 0, 0, 1 ; tổng số bit 1 là một số chẵn → r 8 = Vậy vị trí sai là giá trị thập phân của số nhị phân r 8 r 4 r 2 r 1 bên thu, r 8 r 4 r 2 r 1 =0111 2 = 7 10 , Vậy vị trí sai là 7, sửa bit ở vị trí 7: ‘0’ ‘1’ TÓM TẮT Lỗi truyền dẫn thường được phát hiện tại lớp vật lý trong mô hình OSI Lỗi truyền dẫn thường được sửa trong lớp kết nối dữ liệu trong mô hình OSI Lỗi có thể được chia ra thành:
Redundancy là ý niệm nhằm gởi thêm các bit dư dùng trong phát hiện lỗi Có bốn phương pháp kiểm tra lỗi thông thường là:
Trong VRC, một parity bit được thêm vào đơn vị dữ liệu VRC chỉ có thể phát hiện một bit và các bit lẻ bị lỗi; không thể phát hiện số bit chẵn. Trong LRC, có một dữ liệu thừa theo sau một đơn vị dữ liệu n bit CRC, phương pháp mạnh nhất trong phương pháp kiểm tra lỗi dùng bit dư, có cơ sở là phép chia nhị phân Checksum được dùng trong giao thức cấp cao hơn (TCP/IP) để phát hiện lỗi Để tính checksum, thì cần: a. Chia dữ liệu thành nhiều phần nhỏ b. Cộng các phần này lại dùng phương pháp bù một c. Lấy bù của tổng cuối cùng, đây chính là checksum Tại máy thu, khi dùng phương pháp checksum, dữ liệu và checksum phải được cộng lại thành giá trị 0 khi không có lỗi Mã Hamming là phương pháp sửa lỗi một bit dùng các bit thừa. Số bit là hàm của độ dài đơn vị dữ liệu Trong mã Hamming, một đơn vị dữ liệu m bit thì dùng công thức 2 r m r 1 để xác định r, số bit dư cần có. |
