Bài giảng Mạng máy tính - Chương 8: Tầng liên kết dữ liệu (Phần 1)
Tầng Liên kết dữ liệu
HAMMING CODE - 1
Mỗi hamming code
có M bit, đánh số từ 1 đến M
Bit parity: log2M bits, tại cá c vị trí lũy thừa của 2
Dữ liệu thật được đặt tại cá c vị trí khô ng là lũy thừa của 2
VD: M = 7
log27 = 3: dùng 3 bits làm bit parity (1, 2, 4)
Có 4 vị trí có thể đặt dữ liệu (3, 5, 6, 7)
Đặc điểm:
sửa lỗi 1 bit
nhận dạng được 2 bit lỗi
Sửa lỗi nhanh hơn Parity code 2 chiều
2
HAMMING CODE - 2
Bên gởi:
Chia dữ liệu cần gởi đi thành cá c khối dữ liệu (với số bit là
số vị trí có thể đặt vào Hamming Code)
Với mỗi khối dữ liệu ➔ tạo 1 Hamming Code
Đặt cá c bit dữ liệu vào cá c vị trí khô ng phải là lũy thừa của 2 trong
Hamming Code
lưu ý: vị trí được đánh số từ 1 đến M
Tí nh lấy bits
Tí nh giá trị của cá c bit parity
3
HAMMING CODE – 3
Ví dụ:
M = 7
Dùng parity lẻ
Thô ng tin cần gởi: 1011
1 0 1 1
Thông tin cần gửi:
1
3
0
5
1
6
1
7
1
2
4
Vị trí
20 21
22
Tính lấy bits:
3 =
21 + 20 = 0 1 1
+ 20 = 1 0 1
5 = 22
6 = 22 + 21 +
7 = 22 + 21 + 20 = 1 1 1
= 1 1 0
4
HAMMING CODE - 4
1 0 1 1
Thông tin cần gửi:
1
1
0
1
1
1
1
2
2
3
3
4
4
5
5
6
6
7
7
Vị trí
20 21
22
Vị trí 20:
• Xét cột 20 trong lấy bit ➔
lấy bits:
các vị trí có bit 1
• Lấy các bit DL tại các vị trí
có bit 1 trong lấy bit ➔ tính
bit parity cho các bit dữ liệu
này
3 =
21 + 20 = 0 1 1
+ 20 = 1 0 1
5 = 22
6 = 22 + 21 +
7 = 22 + 21 + 20 = 1 1 1
= 1 1 0
5
HAMMING CODE - 5
1 0 1 1
Thông tin cần gửi:
1
1
0
2
1
3
0
5
1
6
1
7
4
Vị trí
20 21
22
lấy bits:
3 =
21 + 20 = 0 1 1
+ 20 = 1 0 1
5 = 22
6 = 22 + 21 +
7 = 22 + 21 + 20 = 1 1 1
= 1 1 0
6
HAMMING CODE - 6
1 0 1 1
Thông tin cần gửi:
1
1
0
2
1
3
1
4
0
5
1
6
1
7
Vị trí
20 21
22
lấy bits:
3 =
21 + 20 = 0 1 1
+ 20 = 1 0 1
5 = 22
6 = 22 + 21 +
7 = 22 + 21 + 20 = 1 1 1
= 1 1 0
7
HAMMING CODE - 7
Dữ liệu cần gởi: 1011
Dữ lệu gởi: 1011011
8
HAMMING CODE - 8
Bên nhận: với mỗi Hamming Code
Điền cá c bit Hamming Code nhận vào cá c vị trí từ 1 đến M
Tí nh lấy bit
Kiểm tra cá c bit parity
Nếu tại bit 2i phá t hiện sai ➔ đánh dấu Error, hệ số ki = 1
Ngược lại, đánh dấu No Error = 0, hệ số ki = 0
Vị trí bit lỗi: pos = 2i*ki
9
HAMMING CODE – 9
1 0 1 1 0 0 1
Thông tin nhận:
Vị trí
1
1
0
2
1
3
1
4
0
5
0
6
1
7
20 21
22
Tính lấy bits:
3 =
21 + 20 = 0 1 1
+ 20 = 1 0 1
5 = 22
6 = 22 + 21
7 = 22 + 21 + 20 = 1 1 1
= 1 1 0
10
HAMMING CODE – 10
1 0 1 1 0 0 1
Thông tin nhận:
Vị trí
1
1
0
2
1
3
1
4
0
5
0
6
1
7
20 21
22
Tính lấy bits:
3 =
21 + 20 = 0 1 1
4 = 22 +
6 = 22 + 21
+20
= 1 0 1
= 1 1 0
Odd parity: Khô ng có lỗi
11
HAMMING CODE – 11
1 0 1 1 0 0 1
Thông tin nhận:
Vị trí
1
1
0
2
1
3
1
4
0
5
0
6
1
7
20 21
22
Tính lấy bits:
3 =
21 + 20 = 0 1 1
+ 20 = 1 0 1
5 = 22
6 = 22 + 21
7 = 22 + 21 + 20 = 1 1 1
= 1 1 0
Odd parity: LỖI
12
HAMMING CODE – 12
1 0 1 1 0 0 1
Thông tin nhận:
Vị trí
1
1
0
2
1
3
1
4
0
5
0
6
1
7
20 21
22
Tính lấy bits:
3 =
21 + 20 = 0 1 1
+ 20 = 1 0 1
5 = 22
6 = 22 + 21
7 = 22 + 21 + 20 = 1 1 1
= 1 1 0
Odd parity: LỖI
13
HAMMING CODE – 13
22 21 20
3 =
21 + 20 = 0 1 1
+ 20 = 1 0 1
5 = 22
6 = 22 + 21
= 1 1 0
7 = 22 + 21 + 20 = 1 1 1
E = error in column
NE = no error in column
E E NE
1 1 0
= 6
➔ Lỗi bit thứ 6 trong Hamming Code
Dữ liệu nhận đúng: 1011011
Dữ liệu thật: 1011
14
HAMMING CODE – CÁ CH 2
Lưu ý: số bit Parity ràng buộc theo công
thức
2p >= d + p + 1
p: số bit Parity
d: số bit data
Ví dụ:
d= 7 => p = 4 => M= d + p= 11
d= 4 => p = 4 => M = d + p= 8
M= 8, log28= 3 => p= 3 => d= 5: không thỏa
công thức => p= 4 => d= 4
15
HAMMING CODE – CÁ CH 2
Tạo từ mã Hamming Code như sau:
Đánh dấu tất cả vị trí lũy thừa của 2 là bit
parity (vị trí 1, 2, 4, 8, 16, 32, 64, ...)
Tất cả vị trí còn lại là bit dữ liệu sẽ được mã
hóa (vị trí 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15,
17, ...)
Giá trị bit Parity được tính dựa vào tính chẵn
lẻ của một số bit dữ liệu trong từ mã. Vị trí bit
Parity sẽ xác định luân phiên chuỗi các bit
được tính hay bỏ qua.
16
HAMMING CODE – CÁ CH 2 (TT)
Vị trí 1: lấy 1 bit, bỏ qua 1 bit... (1,3,5,7,9,11,13,15,...)
Vị trí 2: lấy 2 bits, bỏ qua 2 bits...
(2,3,6,7,10,11,14,15,...)
Vị trí 4: lấy 4 bits, bỏ qua 4 bits...
(4,5,6,7,12,13,14,15,20,21,22,23,...)
Vị trí 8: lấy 8 bits, bỏ qua 8 bits... (8-15,24-31,40-
47,...)
Vị trí 16: lấy 16 bits, bỏ qua 16 bits... (16-31,48-
63,80-95,...)
Bit Parity có giá trị 1 khi tổng số bit 1 ở những vị trí
nó kiểm tra là số lẻ (odd) và ngược lại.
17
HAMMING CODE – CÁ CH 2 (TT)
Ví dụ dữ liệu cần gửi: 1001 1010
2p >= d + p + 1
d= 8 => P= 4
1 2 3 4 5 6 7 8 9 10 11 12
1
0 0 1
1 0 1 0
d9 d10 d11 d12
18
p1 p2
p4
p8
d3
d5 d6 d7
HAMMING CODE – CÁ CH 2 (TT)
Xác định p1: (lấy 1, bỏ 1)
vị trí 1,3,5,7,9,11 ,
giá trị ? 1 0 1 1 1
4 số 1=> chẵn => p1 = 0
1 2 3 4 5 6 7 8 9 10 11 12
1
0 0 1
1 0 1 0
p1 p2
p4
p8
d3
d5 d6 d7
d9 d10 d11 d12
19
HAMMING CODE – CÁ CH 2 (TT)
Xác định p2: (lấy 2, bỏ 2)
vị trí 2,3,6,7,10,11
giá trị ?1 01 01
3 số 1 => lẻ => p2 = 1
1 2 3 4 5 6 7 8 9 10 11 12
0
1
0 0 1
1 0 1 0
p1 p2
p4
p8
d3
d5 d6 d7
d9 d10 d11 d12
20
Tải về để xem bản đầy đủ
24 trang
9400
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Mạng máy tính - Chương 8: Tầng liên kết dữ liệu (Phần 1)", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_mang_may_tinh_chuong_8_tang_lien_ket_du_lieu_phan.pdf
