+2

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

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

2. Checksum - tính tổng kiểm tra

Checksum là một phương pháp phát hiện lỗi cơ bản và rộng rãi được sử dụng trong nhiều giao thức truyền thông. Phương pháp này thực hiện việc tính tổng của các đơn vị dữ liệu, thường là các byte hoặc word. Giá trị sum này sau đó sẽ được gửi kèm cùng với dữ liệu. Sau khi nhận, dữ liệu được tính tổng lại và so sánh với tổng đã gửi. Khi xảy ra sự khác biệt cũng đồng nghĩa rằng dữ liệu đã bị thay đổi trong quá trình truyền và xảy ra lỗi.

Xét ví dụ chuỗi bit dữ liệu được gửi là 10011001 11100010 00100100 1000010010011001\ 11100010\ 00100100\ 10000100, được chia thành 44 đoạn (segment), mỗi đoạn 88 bit.

Phía gửi (Sender) thực hiện sinh mã checksum: Thực hiện phép toán cộng giữa đoạn bit 1122. Kết quả thu được 101111011101111011, dư bit 11 bên trái tiếp tục cộng vào kết quả thu được 0111110001111100. Kết quả này tiếp tục được thực hiện phép toán cộng với đoạn bit 33, kết quả thu được thực hiện tiếp phép toán cộng với đoạn bit 44, cho tới khi kết thúc chuỗi dữ liệu gửi (Trong quá trình nếu có bit 11 dư ra sẽ mang cộng với kết quả). Cuối cùng thu được kết quả 0010010100100101, đảo bit kết quả này chính là mã checksum 1101101011011010.

Phía nhận (Receiver) thực hiện tương tự phía gửi, kết quả cuối cùng (không đảo bit như phía gửi) sẽ mang cộng với mã checksum nhận được, nếu thu được kết quả 0000000000000000 nghĩa là dữ liệu hợp lệ, ngược lại là đã xảy ra lỗi.

Chi tiết các bước bạn đọc có thể theo dõi qua hình ảnh sau:

image.png

Chương trình Python sau minh họa cho quá trình sinh mã checksum ở phía gửi:

def calculate_checksum(data_blocks):
    sum = '0' * 8  # Quy ước m = 8
    for block in data_blocks:
        # Hàm binary_addition thực hiện phép cộng các segments (lưu ý bit nhớ)
        sum = binary_addition(sum, block)

    # Thực hiện đảo bit tại bước cuối cùng
    checksum = ''.join('1' if bit == '0' else '0' for bit in sum)
    return checksum

Phương pháp checksum khá đơn giản, dễ hiểu, không yêu cầu nhiều tài nguyên nên phù hợp với các giao thức đơn giản. Tuy nhiên, checksum không thực sự an toàn do phép toán module sử dụng trong quá trình tính toán, có thể xảy ra trường hợp các bit "triệt tiêu" lẫn nhau.

Một bài tập nhỏ dành cho bạn đọc: Hãy tính mã checksum của chuỗi bit sau để xem có điều gì đặc biệt nhé: 10011000 11100010 00100100 1000010110011000\ 11100010\ 00100100\ 10000101

Ngoài ra, phương pháp checksum được thiết kế chỉ để phát hiện lỗi, nên không thể biết chính xác vị trí của bit lỗi cũng như số lượng bit bị lỗi.

3. Cyclic redundancy check (CRC) - Kiểm tra dư thừa vòng

Cyclic redundancy check là một kỹ thuật phức tạp hơn, cung cấp mức độ bảo vệ cao hơn so với sumcheck hoặc parity check. Phương pháp thực hiện dựa trên mã CRC, còn được gọi là mã đa thức. CRC coi các dãy bit dữ liệu thành hệ số của đa thức, từ đó có thể thực hiện các phép toán trên đa thức (có các hệ số 00 hoặc 11) thay thế việc thao tác bit. Các phép toán trên CRC đều không tính "nhớ" (cho phép cộng) hoặc "mượn" (cho phép trừ), thực tế phép cộng và trừ ở đây chính là phép XOR, ví dụ:

1101+1001=11011001=1101  1001=01001101 + 1001 = 1101 - 1001 = 1101\ \oplus\ 1001 = 0100

Đối với phép nhân và chia, các phép cộng và trừ trong đó đều được thay thế bởi phép XOR.

Cyclic redundancy check hoạt động như sau:

  • Đầu tiên, hai bên gửi và nhận cần thống nhất một đa thức sinh (CRC generator) có bit cao nhất là 11.
  • Giả sử đa thức sinh có r+1r+1 bit, trước hết bên gửi cần ghép thêm rr bit vào sau dữ liệu gửi. rr bit này là vị trí của dư trong phép tính sẽ thực hiện ở bước sau.
  • Thực hiện phép chia dữ liệu gửi (có thêm rr bit 00 theo sau) cho đa thức sinh thu được dư DD (dài rr bit).
  • Đặt DD vào rr bit cuối dữ liệu gửi (vị trí rr bit 00) thu được dữ liệu cần gửi.
  • Bên nhận thực hiện chia dữ liệu nhận được cho đa thức sinh, nếu kết quả chia hết tức là quá trình truyền tải an toàn, ngược lại thì lỗi đã xảy ra.

Sơ đồ hoạt động của thuật toán như sau:

image.png

Chúng ta xem xét một ví dụ cụ thể hơn. Dữ liệu cần gửi là chuỗi bit 10100001010000, đa thức sinh quy ước là x3+1=1x3+0x2+0x+1x^3+1=1x^3+0x^2+0x+1 tương ứng với 10011001.

  • Bên gửi thêm 33 bit 00 vào sau 10100001010000 thu được 10100000001010000000.
  • Thực hiện phép chia 10100000001010000000 cho 10011001 thu được dư 011011, thay thế vào 33 vị trí cuối của dữ liệu thu được 10100000111010000011 sẽ được gửi đi.
  • Bên nhận kiểm tra lỗi bằng cách thực hiện phép chia 10100000111010000011 cho đa thức sinh 10011001, kết quả thu được dư 00, tức là quá trình gửi an toàn.

Chi tiết các bước tính toán bạn đọc có thể theo dõi trong hình ảnh sau (Ký hiệu @ thay cho phép XOR):

image.png

Chương trình Python minh họa cho quá trình tính toán phép chia:

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

image.png

Đa thức sinh thường có độ dài 8,12,168,12,16 hoặc 3232 bit. Trong tế bào ATM, CRC 88 bit được sử dụng trong 55 byte tiêu đề. Trong nhiều giao thức thường sử dụng đa thức sinh 3232 bit sau:

GCRC32=100000100110000010001110110110111G_{CRC-32}=100000100110000010001110110110111

Cyclic redundancy check được sử dụng rộng rãi trong các giao thức mạng, các thiết bị lưu trữ, và ứng dụng trong việc kiểm tra tính toàn vẹn của dữ liệu bởi tính hiệu quả cao trong việc phát hiện các lỗi phổ biến hoặc các lỗi có mô hình nhất định. Phần cứng hỗ trợ CRC có thể thực hiện kiểm tra lỗi rất nhanh, thậm chí ngay cả trong khi dữ liệu đang được truyền đi, không làm chậm tốc độ truyền dữ liệu. Sự đa dạng của các đa thức sinh CRC cho phép tùy chỉnh mức độ phức tạp của thuật toán để phù hợp với yêu cầu cụ thể của ứng dụng.

Tuy nhiên CRC chỉ phát hiện lỗi nhưng không sửa được chúng, cần kết hợp cơ chế khác như ARQ (Automatic Repeat reQuest) để sửa lỗi khi phát hiện lỗi thông qua CRC. Ngoài ra, khi sử dụng đa thức sinh có bậc cao để tăng độ tin cậy, độ phức tạp của thuật toán cũng tăng lên, yêu cầu nhiều tài nguyên tính toán hơn.

4. So sánh

Tính năng / Phương pháp Checksum Parity (Single & Multiple) CRC
Độ phức tạp Thấp Rất thấp Cao
Hiệu suất Trung bình Thấp Cao
Khả năng phát hiện lỗi Tốt với lỗi nhỏ Chỉ lỗi đơn giản Xuất sắc với nhiều loại lỗi
Phát hiện lỗi nhiều bit Trung bình Kém (chỉ Parity Multiple) Cao
Chi phí tính toán Thấp Thấp nhất Trung bình đến cao
Độ tin cậy Trung bình Thấp Cao
Ứng dụng Truyền thông đơn giản Thiết bị lưu trữ đơn giản Truyền thông và lưu trữ dữ liệu hiệu suất cao

Tài liệu tham khảo


All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.