Lỗi phát hiện lỗi (CRC, Checksum, v.v.)

Question

Tôi có một tình huống giả định về việc gửi đơn vị dữ liệu, mỗi đơn vị một nghìn byte. Tỷ lệ thất bại là hiếm nhưng khi một lỗi xảy ra nó ít có khả năng là một lỗi bit duy nhất và nhiều khả năng là một lỗi trong một vài bit liên tiếp.

Lúc đầu, tôi nghĩ đến việc sử dụng tổng kiểm tra, nhưng dường như có thể bỏ sót các lỗi bit lớn hơn một chút. Kiểm tra chẵn lẻ sẽ không hoạt động hoặc vì vậy CRC có thể là lựa chọn tốt nhất.

Đang sử dụng Kiểm tra dự phòng tuần hoàn trên một nghìn byte có hiệu quả không? Hay có phương pháp nào khác có hiệu quả hơn không?

Answer 1

Kiểm tra dự phòng tuần hoàn (CRC) phổ biến cụ thể vì hiệu quả của chúng trong việc phát hiện nhiều lỗi bit với độ chính xác được đảm bảo.

Có các thiết kế khác nhau để tạo các đa thức CRC trong đó sự cân bằng là chính xác so với độ phức tạp tính toán. Trong trường hợp của bạn, bạn có thể chọn "nhanh nhất" đáp ứng yêu cầu của bạn về tính chính xác.

Bạn có thể muốn bắt đầu với bài viết Wikipedia này trên Cyclic Redundancy Check.

Answer 2

Việc sử dụng CRC là điều bình thường. Tôi không chắc chắn những gì bạn có ý nghĩa bởi 'hiệu quả', nhưng tôi nghĩ rằng đôi khi CRC được thực hiện trong phần cứng (ví dụ như trên card Ethernet). Nếu không, bạn có thể thấy việc triển khai 'tối ưu hóa' (sử dụng bảng tra cứu).

Answer 3

CRC được bao phủ trong một câu hỏi ở đây
When is CRC more appropriate to use than MD5/SHA1?
Nó phù hợp cho việc phát hiện các lỗi ngẫu nhiên và dễ dàng để thực hiện.

Answer 4

Khu vực đĩa của bạn lớn đến mức nào? Có lẽ ít nhất 512 byte. Và CRC là một lược đồ thời gian được vinh danh cho ECC cấp phần cứng.

Thuật toán đa thức CRC cổ phiếu khá hiệu quả đối với số lỗi bit nhỏ. Độ chính xác chính xác là tính toán toán học. CRC cũng rất hiệu quả để làm trong phần cứng, nơi một số lượng tương đối nhỏ các cổng và thanh ghi thay đổi có thể quản lý công việc một cách nhanh chóng.