Bài giảng Mạng máy tính - Chương 9: Phát hiện và sửa lỗi

CHƯƠNG 9

PHÁT HIỆN VÀ SỬA LỖI

Overview

n Mục đích của việc phát hiện và sửa lỗi

n Nguyên nhân gây ra lỗi khi truyền

n Phát hiện và sửa lỗi trong mô hình OSI

u Các loại lỗi

n Thực chất của lỗi tín hiệu

n Lỗi đơn bit

n Lỗi nhóm

LỖI ĐƠN BIT

n Thế nào gọi là lỗi đơn bit.

n Trường hợp xảy ra lỗi đơn bit?

l Tốc độ truyền dữ liệu là 1Mbps

l Thời bit là 1/1000000 s

l Thời gian của nhiễu phải ≤ 1/1000 000 s

Lỗi nhóm

n Thế nào là lỗi nhóm?

n Created on Domain Controllers

n Độ dài của lỗi nhóm?

n Reside in Active Directory

n Trường hợp xảy ra lỗi nhóm.

n Used to Control Resources in

the Domain

l Tốc độ truyền dữ liệu là 1Kbps

l Thời gian tồn tại nhiễu là 1/1000s.

l Số bit bị ảnh hưởng là 10 bit

u Phát hiện lỗi

n Các phương pháp dùng để

kiểm chứng thông tin

n Các phương pháp phát hiện

lỗi

l Phương pháp truyền lại.

l Phương pháp

Redundancy (dư thừa)

Vertical redundancy check (VRC)

n Bản chất của phương

pháp

n Quá trình thực hiện

n Các lỗi được phát hiện

1110111

1101111

o

1110010

r

1101100

l

1100100

d

w

11101110 11011110 11100100 11011000 11001001

Longitudinal redundancy check (LRC)

n Phương pháp kiểm tra.

n Các lỗi được phát hiện

n Phương pháp cải tiến

10101001

00111001

11011101

11100111

10101010

(LRC)

10100001 10001001

10101010

(LRC)

Longitudinal redundancy check (LRC)

n Phương pháp pháp cải tiến

Vị trí bit

Khối ký tự truyền đi

LRC

trong ký tựt

A

S

C

I

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

2

0

1

0

1

0

1

0

3

4

5

6

7

VRC

Tổ hợp lỗi không phát hiện được

Cyclic redundancy check (CRC) – Kiểm tra vòng

n Bản chất của phương

pháp

n Yêu cầu đối với dãy bit

CRC

n Quá trình phát sinh và

kiểm tra bằng CRS

Cyclic redundancy check (CRC) – Kiểm tra vòng

n Bộ sinh CRC

Cyclic redundancy check (CRC) – Kiểm tra vòng

n Bộ kiểm tra CRC

Cyclic redundancy check (CRC) – Kiểm tra vòng

n Đa thức sinh

l Biểu diễn dưới dạng đa thức

l Đa thức sinh và phát hiện lỗi.

- Đa thức sinh: G(x)

- Dữ liệu + G(x): T(x)

- Phát sinh lỗi:

T(x)+E(x)

Cyclic redundancy check (CRC) – Kiểm tra vòng

n Các lỗi được phát hiện

E(x) = xⁱ

E(x) = xⁱ+ x ^j= x ^j(x^{i− j}+1)

üTrường hợp lỗi đơn bit:

ü Hai lỗi đơn bit tách biệt :

üSô lẻ bit bị sai:

x⁵+ x²+1

E(x) chứa số lẻ số hạng:

üLỗi nhóm: Độ dài k :

Đa thức bậc r có đặc tính:

xⁱ(x^k−1+ ⋅⋅⋅+1)

- Phát hiện lỗi nhóm với độ dài r

- Không phát hiện các lỗi nhóm với

độ dài r = l +1

n Một số đa thức sinh

CHECKSUM

n Checksum generator –

Bộ sinh checksum

l Đơn vị dữ liệu được chia

thành k phân đoạn bằng

nhau gồm n bit.

l Các phân đoạn được cộng

với nhau sử dụng phép

toán bù một.

l Tổng được lấy phần bù và

trở thành checksum

l Checksum được ghép vào

cuối dữ liệu cần gửi và

được truyền đi.

CHECKSUM

n Checksum Checker –

Dữ liệu cần gửi:

10101001 00111001

Bộ kiểm tra checksum.

l Dữ liệu lại được chia

thành k phân đoạn bằng

nhau gồm n bit.

10101001

00111001

------------

l Các phân đoạn được

cộng với nhau sử dụng

phép bù một.

Tổng

11100010

Checksum 00011101

l Tổng được lấy phần bù.

Chuỗi bit được truyền đi là:

10101001 00111001

00011101

l Nếu kết quả bằng không:

không có lỗi

uSỬA LỖI

n CÁCH THỰC HIỆN:

l Truyền lại

l Sửa lỗi bằng các mã sửa sai

n Sửa lỗi đơn bit

l Số bit dư thừa cần có để phát hiện lỗi

- Trạng thái bit: có lỗi (1) , không lỗi (0)

- Sử dụng thêm một bit dư thừa để biểu thị trạng thái

l Số bit dư thừa được sử dụng để sửa lỗi

uSỬA LỖI

n Các bit dư thừa

l Số bit dư thừa là r

l Số bit dữ liệu là m

l Tổng các bit là n = m + r : Từ mã

n Khoảng cách Hamming

l Số các vị trí bit mà hai từ mã khác

nhau được gọi là khoảng cách

(distance) Hamming .

n Xác định khoảng cách

10001001

10110001

00111000

Hamming

l XOR hai từ mã

SỬA LỖI

n Ý nghĩa của khoảng cách

Hamming

Các từ mã hợp lệ:

0000000000 0000011111

1111100000 1111111111

l Nếu hai từ mã có khoảng cách

Hamming là d thì để biến đổi từ

mã này thành từ mã kia cần phải

có d lỗi đơn bit xảy.

n Tính chất phát hiện và sửa sai

Từ mã nhận được:

0000000111

l Để phát hiện d lỗi ta cần một mã

có khoảng cách ít nhất là d+1

Từ mã gốc

0000011111

l Để sửa sai d lỗi, ta cần một

mã có khoảng cách ít nhất là

2d +1

SỬA LỖI

n Tổng quát

Số các bit dữ

liệu

Số các bit dư

thừa

Tổng số bit

l Tổng số bit được truyền là

n = m +r

1

2

3

4

5

6

7

2

3

4

3

5

l r bit dư thừa cần phải có

khả năng để hiển thị n +1

trạng thái khác nhau.

6

l Điều kiện

7

2^r≥ m + r +1

9

10

11