© 2004, HOÀNG MINH SƠN
Chương 1
Hệ thống
thông tin công nghiệp
1/20/2006
4.4 Bảo toàn dữ liệu
2
© 2004, HOÀNG MINH SƠN
4.4 Bảo toàn dữ liệu
© 2005 - HMS
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
3
© 2004, HOÀNG MINH SƠN
4.4 Bảo toàn dữ liệu
© 2005 - HMS
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
 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ữ

MTBF
(MTBF = Mean
Time Between Failures): T
MTBF
= n/(v*R)
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
RT
MTBF
10
-6
1 ngày
10
-10
26 năm
10
-14
260 000 năm
6
© 2004, HOÀNG MINH SƠN
4.4 Bảo toàn dữ liệu
© 2005 - HMS
 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.

Ví dụ: Khung UART
 UART (Universal Asynchronous Receiver/Transmitter) ₫ược
sử dụng khá rộng rãi
Start01234567PStop
0 LSB MSB 1
9
© 2004, HOÀNG MINH SƠN
4.4 Bảo toàn dữ liệu
© 2005 - HMS
3. Bit chẵn lẻ hai chiều (bảo toàn khối)
1. 2. 3. 4. 5. 6. 7. p
1.01001011
2.10010000
3.11101110
4.01010101
5.11110110
6.00011110
7.11001100
p01000100
10
© 2004, HOÀNG MINH SƠN
4.4 Bảo toàn dữ liệu
© 2005 - HMS
Trường hợp xảy ra 1 lỗi
1. 2. 3. 4. 5. 6. 7. p
1.01001011
2.10010000
3. 1 1 1 11110
4.01010101
5.11110110

p01000100
13
© 2004, HOÀNG MINH SƠN
4.4 Bảo toàn dữ liệu
© 2005 - HMS
4. Mã vòng (CRC)
 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)
14
© 2004, HOÀNG MINH SƠN
4.4 Bảo toàn dữ liệu
© 2005 - HMS
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ớ)
1 - 1 = 0
0 - 0 = 0
1 - 0 = 1
0 - 1 = 1
15

-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
17
© 2004, HOÀNG MINH SƠN
4.4 Bảo toàn dữ liệu
© 2005 - HMS
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.
 Ví dụ với n = 5 (như ở CAN-Bus):
— Thông tin nguồn I = 0111111
— Thông tin gửi ₫i D = 0111110
1