Đề tài 17: các kỹ thuật phát hiện lỗi và sửa sai
Thành viên của nhóm 8:
1. Nguyễn Văn Dũng
2. Nguyễn Thúy Hà
3. Nguyễn Đức Tâm
4. Đỗ Thị Kim Thanh
Phát hiện lỗi và sửa sai
Mạng cần có khả năng truyền dữ liệu một cách chính xác. Một hệ thống
không đảm bảo được tính năng này thì không sử dụng được. Trong quá trình
truyền dữ liệu luôn bị tác động bởi nhiều yếu tố như nhiễu, vì vậy hệ thống cần có
độ tin cậy tốt với cơ chế phát hiện và sửa lỗi.
Việc phát hiện và sửa lỗi được thiết lập ở lớp kết nối dữ liệu hoặc lớp vận
chuyển trong mô hình OSI.
1. Tổng quan:
Khi dữ liệu được truyền đi giữa 2 DTE ( Data Terminal Equipment – thiết bị
đầu cuối xử lý số liệu) đây là thiết bị lưu trữ và xử lý thông tin. Trong hệ thống
truyền số liệu hiện đại thì DTE thường là máy tính hoặc máy fax hoặc là trạm cuối
(terminal). Như vậy tất cả các ứng dụng của người sử dụng (chương trình, dữ liệu)
đều nằm trong DTE. Chức năng của DTE thường lưu trữ các phần mềm ứng dụng,
đóng gói dữ liệu rồi gửi ra DCE ( thiết bị đầu cuối kênh dữ liệu – Data circuit
terminal equipment) hoặc nhận gói dữ liệu từ DCE theo một giao thức xác định
DTE trao đổi với DCE thông qua một chuẩn giao tiếp nào đó. Như vậy mạng
truyền số liệu chính là để nối các DTE lại cho phép chúng ta phân chia tài nguyên,
trao đổi dữ liệu và lưu trữ thông tin dung chung đặc biệt nếu các đường dây truyền
dẫn ở trong môi truyền xuyên nhiễu như mạng điện thoại công cộng, thì những tín
hiệu điện đại diện luồng bit rất dễ bị thay đổi do ảnh hưởng của các thiết bị điện
gần đó. Điều đó có nghĩa là tín hiệu đại diện cho bit 1 bị máy thu dịch ra như bit
nhị phân 0 và ngược lại.
Có hai phương pháp cho vấn đề này, đó là:
− Kiểm soát lỗi hướng tới (FEC-Forward Error Control): trong mỗi ký tự hay
mỗi frame dữ liệu được truyền đi có chứa thông tin bổ sung cần thiết để bên

Ngoài ra còn một số đơn vị đo khác, ít được sử dụng hơn:
FER (Frame Error Rate)
PER (Packet Error Rate)
Để xác định xác suất lỗi gói số liệu sử dụng công thức:
P
f
= 1 – (1 – P
b
) N với N – độ dài gói số liệu, đo bằng bit
P
f
≈ N.P
b
, nếu N.P
b
<<1
Thí dụ minh họa: cho N = 1000 bit, P
b
= 10-6
P
f
= 1 – (1 – P
b
)N = 1 – (1-10-6)1000 = 0.00095
Hay P
f
≈ N.P
b,
≈ 1000.10 – 6 ≈ 0.001.
3. Các kiểu lỗi:

Các khái niệm liên quan:
− Gap (kẽ hở): là vùng nằm giữa 2 vùng lỗi.
− Burst ( Bùng nổ) : là vùng trong đó BER cục bộ vượt quá một giá trị ngưỡng
nhất định. Burst bắt đầu và kết thúc bằng các lỗi.
− Burst interval (khoảng lỗi chum) : vùng giữa 2 vùng lỗi chum liên tiếp.
− Cluster: vùng không có bất kì một bit đúng nào xen giữa.
− Ký hiệu: 1 là bit đị lỗi, 0 là bit đúng (không bị lỗi), 0
x
là một dãy liên tiếp x
bit đúng.
Lỗi ở một số môi trường có khuynh hướng bùng nổ
- Mặt dễ giải quyết: số liệu máy tính luôn được gửi thành các khối bit. Giả sử
rằng kích thước khối là 1000 bit, và tỉ lệ là 0.001. Nếu các lỗi là độc lập thì
hầu hết các khói đều chứa lỗi. Nếu các lỗi xuất hiện một cách bùng nổ trong
100 khối, thì tính trung bình chỉ có một hoặc hai khối trong 100 khối bị ảnh
hưởng. khi đó việc giải quyết các khối bit bị lỗi sẽ trở nên đơn giản.
- Mặt khó: khó phát hiện và sửa hơn so với các lỗi cô lập.
4. Phát hiện sai trong truyền số liệu:
Phương pháp để phát hiện sai trong truyền số liệu là do dung dư thừa. Một cơ
chế dò tìm lỗi phải thảo mãn những yê cầu đặt ra cần phải gửi tất cả dữ liệu 2 lần.
Thiết bị nhận sau đó sẽ có thể thực hiện công việc so sánh bit-bit giữa hai phiên
bản dữ liệu. Bất kỳ sự khác nhau nào sẽ chỉ báo một lỗi và một cơ chế sửa lỗi phù
hợp sẽ được thiết lập tại đó. Hệ thống này sẽ hoàn thành một cách chính xác ( các
lỗi bit lẻ được đưa ra bằng đúng các bit trong cả hai tập dữ liệu là rất nhỏ), nhưng
cách này cũng khá chậm, không chỉ mất gấp đôi thời gian cho việc truyền dẫn mà
còn mất thời gian cho quá trình so sánh từng đơn vị bit-bit.
Khái niệm bao gồm thông tin bổ sung trong truyền dẫn chỉ dành cho mục đích
so sánh là một cách tốt. Nhưng thay vì lặp lại toàn bộ dòng dữ liệu, một nhóm nhỏ
hơn các bit có thể được ghép thêm vào cuối mỗi đơn vị. Kỹ thuật này được gọi là
dư thừa – redundancy bởi vì các bit phụ thêm là dư thừa đối với dữ liệu thông tin;

soát lỗi
Phương pháp kiểm tra
Kiểm tra bit chẵn lẻ (Prarity bit)
Kiểm tra tổng khối BSC (Block
sum check)
Kiêm tra CRC
( Cyclic redundancy check)
- Trước khi truyền dữ liệu đi, người ta thêm vào cuối bit 1 gọi là parity bit.
- Nếu tổng số bit 1 của xâu truyền đi là chẵn thì bit thêm vào là 0
- Nếu tổng số bit 1 của xâu truyền đi là lẻ thì bit thêm vào là 1
Ví dụ: Truyền xâu CDSPHD
C(67) = 1000011
D(68) = 1000100
S(83) = 1010011
P(80) = 1010000
H(72) = 1001000
+ Phương pháp kiểm tra ngang:
(1) C D S P H D
1 1 1 1 1 1 0
0 0 0 0 0 0 0
0 0 1 1 0 0 0
0 0 0 0 1 0 1
0 1 0 0 0 1 0
1 0 1 0 0 0 0
(2) C D S P H D Lỗi do mạng truyền thông
1 1 1 1 1 1 0 sinh ra
0 0 0 0 0 0 0
0 1 1 0 0 0
0 0 0 0 1 0 1
0 1 0 0 0 1 0

0 0 0 0 0 0
(3) C D S P H D
1 1 1 1 1 1
0 0 0 0 0

0 1 1 0 0
0 0 0 0 1 0
0 1 0 0 0 1
1 0 1 0 0 0
1 0 1 0 0 0
1
1
1
1 0 0 0 0 0
+ Kết hợp 2 phương pháp:
(1) C D S P H D
1 1 1 1 1 1 0
0 0 0 0 0 0 0
0 0 1 1 0 0 0
0 0 0 0 1 0 1
0 1 0 0 0 1 0
1 0 1 0 0 0 0
1 0 0 0 0 0 1
(2) C D S P H D
1 1 1 1 1 1 0
0 0 0 0 0 1
0 1 1 0 0 1
0 0 0 0 1 0 1
0 1 0 0 0 1 0
1 0 1 0 0 0 0

• Chỉ sửa được sai một bit đơn.
- Khi các khối ký tự đang được truyền, xác suất một ký tự chứa lỗi bit gia
tăng.
- Xác suất một khối ký tự bị lỗi bit được gọi là tỉ lệ lỗi bit BER.
- Phương pháp này sử dụng một tập parity bit được tính từ toàn bộ khối ký
tự trong khung.
- Mỗi ký tự trong khung được phân phối một parity bit ( parity hàng ). Ngoài
ra một bit mở rộng được tính cho mỗi vị trí bit ( parity cột ) trong toàn bộ khung.
Tập các parity bit cho mỗi cột được gọi là ký tự kiểm tra khối BCC ( Block Check
Character )
Ví dụ:
Data Start Data Parity(even
)
stop
B1 B2 B3 B4 B5 B6 B7
H 1 0 0 0 0 0 0 1 1 0
E 1 1 0 0 0 0 0 1 0 0
L 1 0 1 0 0 0 0 1 0 0
L 1 0 1 0 0 0 0 1 0 0
O 1 1 1 0 0 0 0 1 1 0
BCC(odd) 1 1 0 1 1 1 1 0 1 0
3. Kiểm tra CRC ( cyclic redundancy check )
CRC (cyclic redundancy check) là một loại hàm băm, được dùng để sinh ra
giá trị kiểm thử, của một chuỗi bit có chiều dài ngắn và cố định, của các gói tin vận
chuyển qua mạng hay một khối nhỏ của tệp dữ liệu. Giá trị kiểm thử được dùng để
dò lỗi khi dữ liệu được truyền hay lưu vào thiết bị lưu trữ. Giá trị của CRC sẽ được
tính toán và đính kèm vào dữ liệu trước khi dữ liệu được truyền đi hay lưu trữ. Khi
dữ liệu được sử dụng, nó sẽ được kiểm thử bằng cách sinh ra mã CRC và so khớp
với mã CRC trong dữ liệu.
CRC là một loại mã phát hiện lỗi. Cách tính toán của nó giống như phép

Một bộ sinh CRC sử dụng phép chia modulor 2. Trong bước đầu tiên, số
chia 4 bit được trừ đi từ 4 bit đầu tiên của số bị chia. Mỗi bit của số chia được trừ
đi tương ứng với bit của số bị chia mà không cần nhớ sang bit tiếp theo cao hơn.
Trong ví dụ của , số chia 1101 được trừ từ 4 bit của số bị chia, 1001 cho kết quả là
100 (số 0 ở đầu của số dư được bỏ đi).
Các bít chưa được sử dụng tiếp theo từ số bị chia sau đó được chuyển xuống
dưới để tạo ra số các bit trong số dư bằng với số các bit ở số chia. Do đó, theo
bước tiếp theo là 1000-1101=101…
Trong quá trình này, số chia luôn bắt đầu với bit 1; số chia được trừ từ một
phần của số bị chia/số dư trước bằng nhau về độ dài; số chia chỉ có thể được trừ đi
từ số bị chia/số dư mà bit trái nhất của nó bằng 1. Tại bất kỳ thời điểm nào bit trái
nhất này của bị chia/số dư là 0, một chuỗi các số 0, có cùng chiều dài nhƣ số chia,
thay thế số chia trong bƣớc đó của toàn bộ quá trình. Ví dụ, nếu số chia có độ dài 4
bit, nó đƣợc thay thế bằng 4 số 0. (Chú ý rằng đang xử lý với các mẫu bit, chứ
không phải với các giá trị định lƣợng; 0000 không giống 0.). Hạn chế này có nghĩa
rằng tại bất kỳ bước nào bên trái nhất của phép trừ sẽ là 0-0 hoặc 1-1, cả hai đều
bằng 0. Vì vậy, sau phép trừ, bit bên trái nhất của số dư sẽ luôn dẫn tới 0, do đó bit
này được loại bỏ và bit tiếp theo chưa được sử dụng của số bị chia được đẩy xuống
để đưa ra số dư. Cần chú ý là chỉ có bit đầu tiên của số dư được loại bỏ- nếu bit
tiếp theo cũng là 0, nó vẫn được giữ lại, và số bị chia/số dư cho bước tiếp theo sẽ
bắt đầu với 0. Quá trình này lắp lại cho đến khi toàn bộ số bị chia được sử dụng.
Bộ kiểm tra CRC- CRC Checker
Bộ kiểm tra CRC thực hiện chức năng một cách chính xác như bộ sinh CRC. Sau
khi nhận được dữ liệu được ghép với CRC, nó tương tự thực hiện phép chia
modulor-2. Nếu số dư tất cả bằng 0, các bit CRC được bỏ đi và dữ liệu được chấp
nhận, nếu không dòng các bit nhận được bị bỏ đi và dữ liệu được gửi lại. giải sử
rằng không có lỗi xảy ra. Số chia do đó tất cả bằng 0 và dữ liệu được chấp nhận.
Các đa thức CRC
Bộ sinh CRC (số chia) thường được biểu diễn không chỉ ở dưới dạng chuỗi
các bit 0 và 1 mà còn là một đa thức đại số. Khuôn dạng của đa thức là hữu dụng vì