Tài liệu C4 4 error checking

© 2004, HOÀNG MINH SƠN Chương 1 Hệ thống thông tin công nghiệp 4.4 Bảo toàn dữ liệu 1/20/2006 4.4 Bảo toàn dữ liệu © 2004, HOÀNG MINH SƠN 1. 2. 3. 4. 5. Vấn ₫ề bảo toàn dữ liệu Phương pháp bit chẵn lẻ Bit chẵn lẻ hai chiều Mã vòng (CRC) Nhồi bit 4.4 Bảo toàn dữ liệu © 2005 - HMS 2 1. Vấn ₫ề bảo toàn dữ liệu ƒ Phân loại lỗi — Lỗi phát hiện ₫ược, không sửa ₫ược — Lỗi phát hiện ₫ược nhưng sửa ₫ược, và — Lỗi không phát hiện ₫ược. ƒ Giải pháp — Giải pháp phần cứng — Giải pháp phần mềm (xử lý giao thức) => Bảo toàn dữ liệu © 2004, HOÀNG MINH SƠN ƒ Phát hiện lỗi là vấn ₫ề quan trọng hàng ₫ầu! ƒ Nguyên lý cơ bản: Bổ sung thông tin dự trữ (redundancy) phục vụ kiểm soát lỗi 4.4 Bảo toàn dữ liệu © 2005 - HMS 3 Các vấn ₫ề cần xem xét ƒ Chiều dài thông tin kiểm soát lỗi? — Dài hay ngắn thì tốt? — Tỉ lệ so với lượng thông tin ban ₫ầu? © 2004, HOÀNG MINH SƠN ƒ Thuật toán xác ₫ịnh thông tin kiểm soát lỗi? ƒ Biện pháp kiểm soát lỗi liên quan tới tính năng kỹ thuật nào? — — — — Độ tin cậy Hiệu suất sử dụng ₫ường truyền Tính ₫ơn giản Tính thời gian thực 4.4 Bảo toàn dữ liệu © 2005 - HMS 4 Một số khái niệm liên quan ƒ Tỉ lệ bit lỗi p là thước ₫o ₫ặc trưng cho ₫ộ nhiễu của kênh truyền dẫn, ₫ược tính bằng tỉ lệ giữa số bit bị lỗi trên tổng số bit ₫ược truyền ₫i. ƒ Tỉ lệ lỗi còn lại R là thông số ₫ặc trưng cho ₫ộ tin cậy dữ liệu của một hệ thống truyền thông, sau khi ₫ã thực hiện các biện pháp bảo toàn (kể cả truyền lại trong trường hợp phát hiện ra lỗi) ƒ Thời gian trung bình giữa hai lần lỗi TMTBF (MTBF = Mean Time Between Failures): TMTBF = n/(v*R) © 2004, HOÀNG MINH SƠN Ví dụ: Một bức ₫iện có chiều dài n = 100 bit ₫ược truyền liên tục với tốc ₫ộ 1200 bit/s 4.4 Bảo toàn dữ liệu R TMTBF 10-6 1 ngày 10-10 26 năm 10-14 260 000 năm © 2005 - HMS 5 ƒ Khoảng cách Hamming: thông số ₫ặc trưng cho ₫ộ bền vững của một mã dữ liệu — chính là khả năng phát hiện lỗi của một phương pháp bảo toàn dữ liệu. — HD có giá trị bằng số lượng bit lỗi tối thiểu mà không ₫ảm bảo chắc chắn phát hiện ₫ược trong một bức ₫iện. Nếu trong một bức ₫iện chỉ có thể phát hiện một cách chắc chắn k bit bị lỗi, thì HD = k+1. ƒ Hiệu suất sử dụng ₫ường truyền E = m (1-p)n/n m - Số lượng bit dữ liệu trong mỗi bức ₫iện n - Chiều dài bức ₫iện p - Tỉ lệ bit lỗi © 2004, HOÀNG MINH SƠN ƒ Ví dụ 1: m = 8 bit n = 11 bit (1 bit ₫ầu + 8 bit dữ liệu + 1 bit chẵn lẻ+ 1 bit cuối) p = 10-3 Hiệu suất truyền dữ liệu E = 0,72. 4.4 Bảo toàn dữ liệu © 2005 - HMS 6 2. Bit chẵn lẻ (parity bit) ƒ Ví dụ dùng parity chẵn: Dãy bit nguyên bản: Dãy bit gửi ₫i: Giả sử nhận ₫ược Giả sử nhận ₫ược 1001101 10011010 10111010 => Lỗi phát hiện ₫ược 11111010 => Lỗi không phát hiện ₫ược ƒ Hai kiểu parity: — Parity chẵn: Tổng số bit 1 trong bức ₫iện cuối cùng phải chẵn — Parity lẻ: Tổng số bit 1 trong bức ₫iện cuối cùng phải lẻ © 2004, HOÀNG MINH SƠN ƒ Khoảng cách Hamming: 2 4.4 Bảo toàn dữ liệu © 2005 - HMS 7 Ví dụ: Khung UART ƒ UART (Universal Asynchronous Receiver/Transmitter) ₫ược sử dụng khá rộng rãi 0 0 LSB © 2004, HOÀNG MINH SƠN Start 1 4.4 Bảo toàn dữ liệu 2 3 4 5 6 7 P MSB © 2005 - HMS Stop 1 8 © 2004, HOÀNG MINH SƠN 3. Bit chẵn lẻ hai chiều (bảo toàn khối) 1. 2. 3. 4. 5. 6. 7. p 1. 0 1 0 0 1 0 1 1 2. 1 0 0 1 0 0 0 0 3. 1 1 1 0 1 1 1 0 4. 0 1 0 1 0 1 0 1 5. 1 1 1 1 0 1 1 0 6. 0 0 0 1 1 1 1 0 7. 1 1 0 0 1 1 0 0 p 0 1 0 0 0 1 0 0 4.4 Bảo toàn dữ liệu © 2005 - HMS 9 © 2004, HOÀNG MINH SƠN Trường hợp xảy ra 1 lỗi 1. 2. 3. 4. 5. 6. 7. p 1. 0 1 0 0 1 0 1 1 2. 1 0 0 1 0 0 0 0 3. 1 1 1 1 1 1 1 0 4. 0 1 0 1 0 1 0 1 5. 1 1 1 1 0 1 1 0 6. 0 0 0 1 1 1 1 0 7. 1 1 0 0 1 1 0 0 p 0 1 0 0 0 1 0 0 4.4 Bảo toàn dữ liệu © 2005 - HMS 10 © 2004, HOÀNG MINH SƠN Trường hợp xảy ra 3 lỗi 1. 2. 3. 4. 5. 6. 7. p 1. 0 1 0 0 1 0 1 1 2. 1 0 0 1 0 0 0 0 3. 1 1 1 1 0 1 1 0 4. 0 1 0 1 0 1 0 1 5. 1 1 1 0 1 1 1 0 6. 0 0 0 1 1 1 1 0 7. 1 1 0 0 1 1 0 0 p 0 1 0 0 0 1 0 0 4.4 Bảo toàn dữ liệu © 2005 - HMS 11 © 2004, HOÀNG MINH SƠN Khoảng cách Hamming? 1. 2. 3. 4. 5. 6. 7. p 1. 0 1 0 0 1 0 1 1 2. 1 0 0 1 0 0 0 0 3. 1 1 1 1 0 1 1 0 4. 0 1 0 1 0 1 0 1 5. 1 1 1 0 1 1 1 0 6. 0 0 0 1 1 1 1 0 7. 1 1 0 0 1 1 0 0 p 0 1 0 0 0 1 0 0 4.4 Bảo toàn dữ liệu © 2005 - HMS 12 4. Mã vòng (CRC) © 2004, HOÀNG MINH SƠN ƒ CRC (Cyclic Redundancy Check ): thông tin kiểm lỗi (ở ₫ây ₫ược gọi là checksum) phải ₫ược tính bằng một thuật toán thích hợp, trong ₫ó giá trị mỗi bit của thông tin nguồn ₫ều ₫ược tham gia nhiều lần vào quá trình tính toán. ƒ CRC ₫ược sử dụng rộng rãi trong ₫a số các hệ thống truyền thông CN ƒ CRC còn ₫ược gọi là phương pháp ₫a thức, bởi nó sử dụng phép chia ₫a thức (nhị phân) 4.4 Bảo toàn dữ liệu © 2005 - HMS 13 Phép chia ₫a thức (nhị phân) ƒ Đa thức nhị phân: các hệ số là 0 hoặc 1, ví dụ — G = x7 + x6 + x5 + (0x4 + 0x3) + x2 + (0x1) + 1 — Viết gọn lại thành một dãy bit G = {11100101} ƒ Phép chia ₫a thức nhị phân ₫ược qui về các phép so sánh, sao chép và XOR (hay trừ không có nhớ) © 2004, HOÀNG MINH SƠN 1 0 1 0 - 1 0 0 1 = = = = 0 0 1 1 4.4 Bảo toàn dữ liệu © 2005 - HMS 14 Nguyên tắc thực hiện ƒ Hai bên qui ước một “₫a thức phát” G bậc n, ví dụ x3+x+1 tương ứng với dãy bit {1011}. ƒ Dãy bit mang thông tin nguồn I ₫ược thêm vào n bit 0 và coi như một ₫a thức nhị phân P. — Ví dụ thông tin nguồn là {110101} => {110101000} © 2004, HOÀNG MINH SƠN ƒ Lấy P chia cho G ƒ Phần dư R (lấy n chữ số) của phép chia ₫ược thay thế vào chỗ của n chữ 0 bổ sung trong P, tức là ta có D = P + R. R ₫ược gọi là checksum và D chính là dãy bit ₫ược gửi ₫i thay cho I. ƒ Giả sử dãy bit nhận ₫ược là D' không chia hết cho G => bức ₫iện chắc chắn bị lỗi. Nếu D' chia hết cho G, thì xác suất rất cao là bức ₫iện nhận ₫ược không có lỗi. 4.4 Bảo toàn dữ liệu © 2005 - HMS 15 Ví dụ minh họa © 2004, HOÀNG MINH SƠN ƒ ƒ ƒ ƒ ƒ ƒ Thông tin cần truyền I = 110101, ₫a thức G = 1011 (tức x3 + x + 1) Thêm 3 bit 0 vào thông tin nguồn I, ta có P = 110101000 Chia ₫a thức P : G 110101000 1011 -1011 111101 01100 -1011 01111 -1011 01000 -1011 001100 -1011 0111 Phần dư R Dãy bit ₫ược chuyển ₫i: D = P + R = 110101111 Giả sử dữ liệu nhận ₫ược là D' = 110101111 Chia ₫a thức D' : G 110101111 : 1011 = 111101 Phần dư 0000 -> Xác suất rất cao là không có lỗi 4.4 Bảo toàn dữ liệu © 2005 - HMS 16 5. Nhồi bit (Bit stuffing) ƒ Nguyên tắc thực hiện: — Bên gửi: Nếu trong dữ liệu có n bits 1 ₫ứng liền nhau thì thêm một bit 0 vào ngay sau ₫ó. Như vậy trong dãy bit ₫ược chuyển ₫i không thể xuất hiện n+1 bits 1 ₫i liền nhau. — Bên nhận: Nếu phát hiện thấy n bits 1 liền nhau mà bit tiếp theo là 0 thì ₫ược tách ra, còn nếu là bit 1 thì dữ liệu chắc chắn bị lỗi. © 2004, HOÀNG MINH SƠN ƒ Ví dụ với n = 5 (như ở CAN-Bus): — Thông tin nguồn I = 0111111 — Thông tin gửi ₫i D = 01111101 — Nếu thông tin nhận ₫ược D' = 01111101, bên nhận có thể coi xác suất cao không có lỗi — Nếu thông tin nhận ₫ược D' = 11111101, qua mẫu bit ₫ặc biệt bên nhận sẽ phát hiện ra lỗi. 4.4 Bảo toàn dữ liệu © 2005 - HMS 17 Sử dụng phối hợp các biện pháp bảo toàn dữ liệu ƒ Ví dụ dãy bit ban ₫ầu 101011000......1011010 ƒ Áp dụng CRC 101011000......1011010 01001101 parity Checksum ƒ Phân chia thành từng byte © 2004, HOÀNG MINH SƠN 10101100 ... 11011010 01001101 ƒ Bổ sung bit chẵn lẻ và các bit ₫ầu, bit cuối 4.4 Bảo toàn dữ liệu 01010110001 00101101011 parity 00100110101 © 2005 - HMS 18