Bài giảng Hệ thống thông tin công nghiệp - Chương 4.4: Bảo toàn dữ liệu

Hệ thống thông tin công nghiệp

1 g n ơ ư h C

4.4 Bảo toàn dữ liệu

N Ơ S H N M G N À O H

1/20/2006

, 4 0 0 2 ©

CuuDuongThanCong.com CuuDuongThanCong.com

https://fb.com/tailieudientucntt https://fb.com/tailieudientucntt

4.4 Bảo toàn dữ liệu

1. Vấn ₫ề bảo toàn dữ liệu 2. Phương pháp bit chẵn lẻ 3. Bit chẵn lẻ hai chiều 4. Mã vòng (CRC) 5. Nhồi bit

I

N Ơ S H N M G N À O H

, 4 0 0 4.4 Bảo toàn dữ liệu 2 ©

CuuDuongThanCong.com CuuDuongThanCong.com

https://fb.com/tailieudientucntt https://fb.com/tailieudientucntt

1. Vấn ₫ề bảo toàn dữ liệu

(cid:131) 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.

(cid:131) 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

(cid:131) Phát hiện lỗi là vấn ₫ề quan trọng hàng ₫ầu! (cid:131) Nguyên lý cơ bản: Bổ sung thông tin dự trữ

I

(redundancy) phục vụ kiểm soát lỗi

N Ơ S H N M G N À O H

, 4 0 0 4.4 Bảo toàn dữ liệu 2 ©

CuuDuongThanCong.com CuuDuongThanCong.com

https://fb.com/tailieudientucntt https://fb.com/tailieudientucntt

Các vấn ₫ề cần xem xét

(cid:131) 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?

(cid:131) Thuật toán xác ₫ịnh thông tin kiểm soát lỗi? (cid:131) 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

I

N Ơ S H N M G N À O H

, 4 0 0 4.4 Bảo toàn dữ liệu 2 ©

CuuDuongThanCong.com CuuDuongThanCong.com

https://fb.com/tailieudientucntt https://fb.com/tailieudientucntt

Một số khái niệm liên quan

(cid:131) 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.

(cid:131) 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)

(cid:131) Thời gian trung bình giữa hai lần lỗi TMTBF (MTBF = Mean

Time Between Failures): TMTBF = n/(v*R)

TMTBF

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

I

10-6

1 ngày

26 năm

10-10

N Ơ S H N M G N À O H

260 000 năm

10-14

, 4 0 0 4.4 Bảo toàn dữ liệu 2 ©

CuuDuongThanCong.com CuuDuongThanCong.com

https://fb.com/tailieudientucntt https://fb.com/tailieudientucntt

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

(cid:131) Khoảng cách Hamming: thông số ₫ặc trưng cho ₫ộ bền vững

dữ liệu.

(cid:131) Hiệu suất sử dụng ₫ường truyền

— 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.

(cid:131) Ví dụ 1:

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

I

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.

N Ơ S H N M G N À O H

, 4 0 0 4.4 Bảo toàn dữ liệu 2 ©

CuuDuongThanCong.com CuuDuongThanCong.com

https://fb.com/tailieudientucntt https://fb.com/tailieudientucntt

2. Bit chẵn lẻ (parity bit)

(cid:131) Ví dụ dùng parity chẵn:

Dãy bit nguyên bản: 1001101 Dãy bit gửi ₫i: Giả sử nhận ₫ược Giả sử nhận ₫ược

10011010 10111010 => Lỗi phát hiện ₫ược 11111010 => Lỗi không phát hiện ₫ược

(cid:131) 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ẻ

(cid:131) Khoảng cách Hamming: 2

I

N Ơ S H N M G N À O H

, 4 0 0 4.4 Bảo toàn dữ liệu 2 ©

CuuDuongThanCong.com CuuDuongThanCong.com

https://fb.com/tailieudientucntt https://fb.com/tailieudientucntt

Ví dụ: Khung UART

(cid:131) UART (Universal Asynchronous Receiver/Transmitter) ₫ược

sử dụng khá rộng rãi

Start

Stop

LSB

MSB

I

N Ơ S H N M G N À O H

, 4 0 0 4.4 Bảo toàn dữ liệu 2 ©

CuuDuongThanCong.com CuuDuongThanCong.com

https://fb.com/tailieudientucntt https://fb.com/tailieudientucntt

3. Bit chẵn lẻ hai chiều (bảo toàn khối)

1. 2. 3. 4. 5. 6. 7. p

0 0 1 0 1 1 1 1. 0

0 1 0 0 0 0 0 2. 1

1 0 1 1 1 0 1 3. 1

0 1 0 1 0 1 1 4. 0

1 1 0 1 1 0 1 5. 1

0 1 1 1 1 0 0 6. 0

0 0 1 1 0 0 1 7. 1

I

0 0 0 1 0 0 1 p 0

N Ơ S H N M G N À O H

, 4 0 0 4.4 Bảo toàn dữ liệu 2 ©

CuuDuongThanCong.com CuuDuongThanCong.com

https://fb.com/tailieudientucntt https://fb.com/tailieudientucntt

Trường hợp xảy ra 1 lỗi

1. 2. 3. 4. 5. 6. 7. p

0 0 1 0 1 1 1 1. 0

0 1 0 0 0 0 0 2. 1

1 1 1 1 1 0 1 3. 1

0 1 0 1 0 1 1 4. 0

1 1 0 1 1 0 1 5. 1

0 1 1 1 1 0 0 6. 0

0 0 1 1 0 0 1 7. 1

I

0 0 0 1 0 0 1 p 0

N Ơ S H N M G N À O H

, 4 0 0 4.4 Bảo toàn dữ liệu 2 ©

CuuDuongThanCong.com CuuDuongThanCong.com

https://fb.com/tailieudientucntt https://fb.com/tailieudientucntt

Trường hợp xảy ra 3 lỗi

1. 2. 3. 4. 5. 6. 7. p

0 0 1 0 1 1 1 1. 0

0 1 0 0 0 0 0 2. 1

1 1 0 1 1 0 1 3. 1

0 1 0 1 0 1 1 4. 0

1 0 1 1 1 0 1 5. 1

0 1 1 1 1 0 0 6. 0

0 0 1 1 0 0 1 7. 1

I

0 0 0 1 0 0 1 p 0

N Ơ S H N M G N À O H

, 4 0 0 4.4 Bảo toàn dữ liệu 2 ©

CuuDuongThanCong.com CuuDuongThanCong.com

https://fb.com/tailieudientucntt https://fb.com/tailieudientucntt

Khoảng cách Hamming?

1. 2. 3. 4. 5. 6. 7. p

0 0 1 0 1 1 1 1. 0

0 1 0 0 0 0 0 2. 1

1 1 0 1 1 0 1 3. 1

0 1 0 1 0 1 1 4. 0

1 0 1 1 1 0 1 5. 1

0 1 1 1 1 0 0 6. 0

0 0 1 1 0 0 1 7. 1

I

0 0 0 1 0 0 1 p 0

N Ơ S H N M G N À O H

, 4 0 0 4.4 Bảo toàn dữ liệu 2 ©

CuuDuongThanCong.com CuuDuongThanCong.com

https://fb.com/tailieudientucntt https://fb.com/tailieudientucntt

4. Mã vòng (CRC)

(cid:131) 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.

(cid:131) CRC ₫ược sử dụng rộng rãi trong ₫a số các hệ thống

truyền thông CN

(cid:131) 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)

I

N Ơ S H N M G N À O H

CuuDuongThanCong.com CuuDuongThanCong.com

https://fb.com/tailieudientucntt https://fb.com/tailieudientucntt

Phép chia ₫a thức (nhị phân)

(cid:131) Đ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}

(cid:131) 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ớ) 1 - 1 = 0 0 - 0 = 0 1 - 0 = 1 0 - 1 = 1

I

N Ơ S H N M G N À O H

CuuDuongThanCong.com CuuDuongThanCong.com

https://fb.com/tailieudientucntt https://fb.com/tailieudientucntt

Nguyên tắc thực hiện

(cid:131) 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}.

(cid:131) 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}

(cid:131) Lấy P chia cho G (cid:131) 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.

I

N Ơ S H N M G N À O H

(cid:131) 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.

CuuDuongThanCong.com CuuDuongThanCong.com

https://fb.com/tailieudientucntt https://fb.com/tailieudientucntt

Ví dụ minh họa

111101

(cid:131) Thông tin cần truyền I = 110101, ₫a thức G = 1011 (tức x3 + x + 1) (cid:131) Thêm 3 bit 0 vào thông tin nguồn I, ta có P = 110101000 (cid:131) Chia ₫a thức P : G 110101000 1011 -1011 01100 -1011 01111 -1011 01000 -1011 001100 -1011 0111 Phần dư R

I

110101111 : 1011 = 111101

D = P + R = 110101111 D' = 110101111

N Ơ S H (cid:131) Dãy bit ₫ược chuyển ₫i: N M (cid:131) Giả sử dữ liệu nhận ₫ược là G N À (cid:131) Chia ₫a thức D' : G O H

Phần dư 0000 -> Xác suất rất cao là không có lỗi

CuuDuongThanCong.com CuuDuongThanCong.com

https://fb.com/tailieudientucntt https://fb.com/tailieudientucntt

5. Nhồi bit (Bit stuffing)

(cid:131) 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.

(cid:131) Ví dụ với n = 5 (như ở CAN-Bus): = =

I D

0111111 01111101

— Thông tin nguồn — Thông tin gửi ₫i — Nếu thông tin nhận ₫ược D' = 01111101, bên nhận có