Kiểm soát lỗi và sửa lỗi bằng Mã hamming
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (312.77 KB, 7 trang )
Ph ng pháp ki m soát l i và ươ ể ỗ
s a l i b ng mã Hammingử ỗ ằ
I. Ch n s l ng bit s a l iọ ố ượ ử ỗ
Đ dò l i cho t mã M bít, ta c n t mã M+K bítể ỗ ừ ầ ừ
N u K =1, ta có th dò ra 1 l i đ n nh ng không th s aế ể ỗ ơ ư ể ử
N u 2ế
K
- 1 >= M + K , ta có th dò tìm, nh n d ng và s a t t c các l i ể ậ ạ ử ấ ả ỗ
bít đ n. ơ
Ví d : For M = 8:ụ
và K = 3: 2
3
– 1 = 7 < 8 + 3 (không dùng đ c)ượ
và K = 4: 2
4
– 1 = 15 > 8 + 4 (OK)
Vì th ta ph i ch n t mã là K =4, nh th , t mã s a l i nh ế ả ọ ừ ư ế ừ ử ỗ ỏ
nh t là 4ấ
II. V trí và cách tính các bit s a l iị ử ỗ
Bit position 12 11 10 9 8 7 6 5 4 3 2 1
Bit number 1100 1011 1010 1001 1000 0111 0110 0101 0100 0011 0010 0001
Data bit D8 D7 D6 D5 D4 D3 D2 D1
Check bit C8 C4 C2 C1
C1 là một bít chẳn lẻ kiểm tra tất cả các bít data tại vị trí xxx1
C1 = D1 ex-or D2 exor D4 ex-or D5 ex-or D7
C2 là một bít chẳn lẻ kiểm tra tất cả các bít data tại vị trí xx1x
C2 = D1 exor D3 exor D4 exor D6 exor D7
C4 là một bít chẳn lẻ kiểm tra tất cả các bít data tại vị trí x1xx
C4 = D2 exor D3 exor D4 exor D8
C8 là một bít chẳn lẻ kiểm tra tất cả các bít data tại vị trí 1xxx
C8 = D5 exor D6 exor D7 exor D8
III. Ví dụ
Dữ liệu = 00111001
Bít kiểm tra:
Kết hợp:
•
Giả sử chuỗi bít kiểm tra được tạo ra bằng cách sau
•
Giả sử bít dữ liệu thứ 3 bị lỗi và chuyển từ 0 -> 1. Như vạy
khi tính lại các bít kiểm tra, kết quả là:
•
Dùng phép toán X-OR của chuỗi bít kiểm tra cũ và mới, kết
quả là:
•
Vị trí số 6 bị lỗi đó là bít dữ liệu số 3.
IV. Cách tìm l i:ỗ
Lỗi bít đơn
Dò lỗi
