III. Các Phương Pháp Phát Hiện Lỗi (Tiếp Theo)

2. Checksum - Tính Tổng Kiểm Tra

Checksum là một trong những phương pháp phát hiện lỗi được áp dụng rộng rãi trong các giao thức truyền thông. Kỹ thuật này hoạt động bằng cách tính tổng các đơn vị dữ liệu, thường là byte hoặc word, và gửi kèm giá trị tổng này với dữ liệu. Khi nhận dữ liệu, bên nhận sẽ tính toán tổng và so sánh với tổng đã gửi. Nếu có sự khác biệt, điều này có nghĩa là dữ liệu có thể đã bị thay đổi trong quá trình truyền tải, dẫn đến lỗi.

Ví dụ: Nếu chuỗi bit dữ liệu gửi là 10011001 11100010 00100100 10000100, nó sẽ được chia thành các đoạn 8 bit. Từ đó, bên gửi sẽ tính toán mã checksum. Quá trình này bao gồm việc cộng tất cả các đoạn bit lại với nhau, sau đó đảo bit kết quả để được mã checksum. Ở bên nhận, quá trình diễn ra tương tự và kết quả cuối cùng sẽ được kiểm tra với mã checksum đã nhận được. Nếu mọi thứ hợp lệ, kết quả sẽ là chuỗi toàn 0.

Chương trình Python sau đây minh họa quá trình tạo mã checksum:

def calculate_checksum(data_blocks):
    sum = '0' * 8  # Quy ước m = 8
    for block in data_blocks:
        sum = binary_addition(sum, block)
    checksum = ''.join('1' if bit == '0' else '0' for bit in sum)
    return checksum

Checksum có ưu điểm là đơn giản và tiêu tốn ít tài nguyên, nhưng nó không phải là phương pháp an toàn nhất vì nó có thể xảy ra tình trạng các bit triệt tiêu lẫn nhau. Điều quan trọng là checksum chỉ phát hiện lỗi mà không thể biết vị trí hoặc số lượng bit bị lỗi.

Bài Tập Nhỏ: Hãy tự tính mã checksum của chuỗi bit 10011000 11100010 00100100 1000010110011000 để xem có gì đặc biệt.

3. Kiểm Tra Dư Thừa Vòng (Cyclic Redundancy Check - CRC)

Cyclic redundancy check là phương pháp phát hiện lỗi phức tạp hơn so với checksum, cung cấp mức độ an toàn cao hơn. Kỹ thuật này dựa vào mã CRC, còn được gọi là mã đa thức. Trong CRC, dữ liệu được coi như hệ số của một đa thức, từ đó thực hiện các phép toán trên các hệ số nhị phân (0 hoặc 1).

Cyclic redundancy check hoạt động theo các bước sau:

1. Hai bên gửi và nhận phải thống nhất một đa thức sinh.
2. Bên gửi thêm một số bit 0 vào cuối dữ liệu.
3. Thực hiện phép chia dữ liệu cho đa thức sinh để tìm ra dư.
4. Dư được thêm vào vị trí các bit 0 ở cuối dữ liệu để tạo dữ liệu gửi đi.
5. Bên nhận cũng thực hiện phép chia và kiểm tra dư để xác định lỗi.

Ví dụ: Dữ liệu gửi là 101000010100001010000, đa thức sinh là 100110011001. Khi gửi đi, dữ liệu này sẽ được xử lý để tạo ra dữ liệu kèm dư trước khi truyền đi.

Chương trình Python dưới đây minh họa cách tính toán phép chia trong CRC:

def crc_remainder(input_bitstring, polynomial_bitstring):
    polynomial_bitstring = polynomial_bitstring.lstrip('0')
    len_input = len(input_bitstring)
    input_padded_array = list(input_bitstring + '0'*(len(polynomial_bitstring)-1))
    while '1' in input_padded_array[:len_input]:
        cur_shift = input_padded_array.index('1')
        for i in range(len(polynomial_bitstring)):
            input_padded_array[cur_shift + i] = str(int(polynomial_bitstring[i] != input_padded_array[cur_shift + i]))
    remainder = ''.join(input_padded_array)[len_input:]
    return remainder

CRC được sử dụng rộng rãi trong các giao thức mạng và các thiết bị lưu trữ do tính hiệu quả cao trong việc phát hiện lỗi phổ biến. Tuy nhiên, nó chỉ phát hiện mà không sửa lỗi, do đó cần kết hợp với các cơ chế khác như ARQ để sửa lỗi.

4. So Sánh Các Phương Pháp Phát Hiện Lỗi

Tài Liệu Tham Khảo

• GeeksforGeeks - Error Detection in Computer Networks
• Computer Networks - Andrew S. Tanenbaum
• Computer Networking: A Top-Down Approach, 7th Edition
  source: viblo