Đã đăng vào Thứ Năm, 7:00 SA 5 phút đọc

Error detection - Kiểm soát lỗi (phần 1)

I. Mở đầu

Trong mạng máy tính, việc truyền tải thông tin giữa các thiết bị không chỉ cần đạt được hiệu suất cao mà còn phải đảm bảo độ chính xác và tin cậy. Tầng liên kết dữ liệu, hoạt động như một cầu nối giữa phần cứng mạng và các tầng mạng cao hơn, có nhiệm vụ quan trọng trong việc thực hiện mục tiêu này. Một trong những chức năng cốt lõi và thiết yếu của tầng liên kết dữ liệu là kiểm soát lỗi (error detection). Chức năng này giúp nhận diện và xử lý các lỗi có thể xảy ra trong quá trình truyền dữ liệu, từ đó đảm bảo tính toàn vẹn và độ tin cậy của dữ liệu được truyền đi.

Các phương pháp kiểm soát lỗi trong tầng liên kết dữ liệu không chỉ giúp phát hiện lỗi mà còn cung cấp cơ chế để sửa chữa hoặc yêu cầu truyền lại dữ liệu bị lỗi, từ đó tối đa hóa hiệu suất truyền tải và đảm bảo thông tin được truyền đi một cách chính xác nhất. Phần tiếp theo của bài viết sẽ tập trung vào việc khám phá các cơ chế và phương pháp kiểm soát lỗi, làm rõ cách thức hoạt động, tính hiệu quả của chúng trong việc duy trì tính toàn vẹn và độ tin cậy của dữ liệu trong mạng máy tính.

II. Các kiểu lỗi

Lỗi trong truyền dữ liệu có thể xuất hiện vì nhiều lý do, từ sự cố vật lý như nhiễu từ môi trường, suy giảm tín hiệu do khoảng cách, đến các lỗi kỹ thuật trong quá trình mã hóa, đóng gói dữ liệu, hoặc thậm chí là do lỗi phần mềm. Những lỗi này không chỉ gây ra sự mất mát thông tin mà còn có thể dẫn đến hiểu lầm thông tin, gây hậu quả nghiêm trọng đối với các ứng dụng yêu cầu độ chính xác và độ tin cậy cao. Chúng ta xem xét ba kiểu lỗi cơ bản:

Single-bit error - Lỗi đơn bit/lỗi một bit
Multiple-bit error - Lỗi đa bit/lỗi nhiều bit
Burst error - Lỗi bệt

Có thể một số tài liệu chỉ chia thành hai kiểu lỗi cơ bản là Single-bit error và Burst error, ở đây tôi xem xét chi tiết hơn dựa vào đặc điểm các kiểu lỗi.

1. Single-bit error

Chúng ta biết dữ liệu được truyền dưới dạng bit, tức các bit $0$ và $1$ . Chúng ta gọi dữ liệu chứa một lỗi single-bit khi đoạn dữ liệu đó chỉ bị lỗi ở một bit, tức duy nhất một bit bị sai (hay bị đảo) khi so sánh chuỗi bit trước khi truyền và sau khi nhận được.

2. Multiple-bit error

Giống với cái tên của nó, multiple-bit error có nghĩa rằng dữ liệu sau khi được truyền bị lỗi ở nhiều bit, tức là nhiều vị trí nhị phân bị đảo.

3. Burst error

Nhiều tài liệu gộp chung Multiple-bit error và Burst error thành một kiểu lỗi chung. Burst error trong bài viết này được định nghĩa rằng chuỗi dữ liệu sau khi bị truyền đã bị lỗi ở nhiều bit, và những bit bị lỗi này phải nằm liên tiếp nhau.

III. Các phương pháp phát hiện lỗi

1. Parity check - Kiểm tra tính chẵn lẻ

Parity check là cách phát hiện lỗi đơn giản và dễ dàng thực hiện nhất. Có hai phương pháp kiểm tra tính chẵn lẻ là Simple parity check và Two-dimensional parity check.

1.1. Simple parity check

Simple parity check sử dụng thêm một bit nằm ở cuối chuỗi dữ liệu - gọi là parity bit, parity bit này có hai dạng là parity bit chẵn hoặc parity bit lẻ. Parity bit chẵn đưa ra thông tin số bit $1$ trong chuỗi dữ liệu nhận phải là chẵn, parity bit lẻ đưa ra thông tin số bit $1$ trong chuỗi dữ liệu nhận phải là lẻ.

Ví dụ, chuỗi bit dữ liệu cần truyền ban đầu là $1001001$ , quy ước parity bit thực hiện kiểm tra là parity bit chẵn. Ban đầu chuỗi có $3$ bit $1$ (lẻ), nên parity bit có giá trị $1$ (Để cho tổng số lượng bit $1$ là $4$ - chẵn). Trong trường hợp quy ước dùng parity bit lẻ, thì parity bit có giá trị là $0$ , tổng số bit $1$ trong chuỗi vẫn là $3$ , đảm bảo là số lẻ.

Chương trình Python minh họa cho parity check:

def parity_check(data):
    parity = 0
    for number in data:
        parity ^= number  # XOR operation for parity
    return parity

Lược đồ sau minh họa cho quá trình parity check:

Bằng cách sử dụng parity bit, bên nhận có thể "chắc chắn" một điều rằng dữ liệu nhận được luôn phải có tổng số bit $1$ là chẵn (hoặc luôn lẻ). Do đó khi thông tin này bị sai lệch, chắc chắn quá trình truyền đã xảy ra lỗi.

Tuy nhiên, bên nhận chỉ biết rằng chuỗi dữ liệu có lỗi chứ không biết vị trí chính xác của bit bị lỗi. Bên nhận chỉ có thể yêu cầu bên gửi gửi lại dữ liệu chứ không thể tự sửa lỗi. Ngoài ra, một nhược điểm chí mạng khác của của phương pháp này là có thể đưa ra kết quả sai, ví dụ, có hai bit $1$ bị lỗi (đảo thành $0$ ), thì parity check cho kết quả không lỗi, vì tính chẵn lẻ không đổi!

1.2. Two-dimensional parity check

Two-dimensional parity check mở rộng ý tưởng của simple parity check bằng cách áp dụng kiểm tra parity cả theo chiều ngang (hàng) và chiều dọc (cột). Phương pháp này không chỉ phát hiện lỗi mà còn có khả năng xác định vị trí của bit lỗi trong trường hợp single-bit error.

Ví dụ, chuỗi bit dữ liệu cần gửi là $101011111001110$ ( $15$ bit), chia làm $3$ hàng và $5$ cột. Thực hiện thêm các parity bit cho mỗi hàng để đảm bảo rằng số bit $1$ trong mỗi hàng là chẵn:

1 0 1 0 1 | 1
1 1 1 1 0 | 0
0 1 1 1 0 | 1

Tiếp theo thêm parity bit cho mỗi cột để đảm bảo rằng số bit $1$ trong mỗi cột cũng là chẵn:

1 0 1 0 1 | 1
1 1 1 1 0 | 0
0 1 1 1 0 | 1
- - - - -
0 0 1 0 1

Và một parity bit ở vị trí $(3, 5)$ là $0$ :

1 0 1 0 1 | 1
1 1 1 1 0 | 0
0 1 1 1 0 | 1
- - - - -
0 0 1 0 1   0

Chuỗi bit dữ liệu được gửi đi lúc này sẽ là $101011\ 111100\ 011101\ 001010$ . Dựa vào việc kiểm tra tính chẵn lẻ của số bit $1$ ở mỗi hàng và mỗi cột, bên nhận có thể kiểm tra khả năng lỗi hay không của dữ liệu.

Xét trường hợp single-bit error, bit ở vị trí $(1,1)$ bị lỗi:

1 0 1 0 1 | 1
1 0 1 1 0 | 0
0 1 1 1 0 | 1
- - - - -
0 0 1 0 1   0

Rõ ràng bên nhận có thể nhận thấy hàng $1$ và cột $1$ cho kết quả parity check error, từ đó lấy giao của hàng và cột lỗi thu được bit ở vị trí $(1,1)$ bị lỗi. Như vậy two-dimensional parity check có thể sửa được bit lỗi trong trường hợp single-bit error.

Xét trường hợp có $2$ bit lỗi, bit ở vị trí $(1,1)$ và $(1,2)$ bị lỗi:

1 0 1 0 1 | 1
1 0 0 1 0 | 0
0 1 1 1 0 | 1
- - - - -
0 0 1 0 1   0

Lúc này, bên nhận sử dụng two-dimensional parity check chỉ thu được kết quả cột $1$ và cột $2$ chứa bit lỗi, nhưng kiểm tra theo hàng thì không có hàng nào chứa bit lỗi cả nên không thể tìm ra chính xác vị trí các bit lỗi để sửa lỗi.

Như vậy, two-dimensional parity check chỉ khắc phục một phần nhược điểm của simple parity check chứ không phải là phương pháp kiểm tra đạt hiệu quả hoàn toàn trong việc sửa lỗi.