Khoảng cách hamming là gì, và làm thế nào để tôi xác định nó cho một chương trình CRC?

Question

Trong khi học tập cho một lớp học trong mạng máy tính, các prof nói về khoảng cách hamming giữa 2 từ mã hợp lệ trong một mã mẫu. Tôi đã đọc về khoảng cách hamming, và nó có ý nghĩa từ quan điểm của nói khoảng cách khác biệt giữa 2 dây. Ví dụ:

Code Word 1 = 10110 

Người gửi gửi mã từ 1 và có lỗi được giới thiệu và người nhận nhận được 10100. Vì vậy, bạn thấy bit thứ 4 bị hỏng. Điều này sẽ dẫn đến khoảng cách hấp dẫn là 1 vì:

Valid Code Word: 10110 
Error Code Word: 10100 
       ----- 
XOR    00010 

XOR của 2 chuỗi kết quả bằng 1, vì vậy khoảng cách hamming là 1. Tôi hiểu nó đến thời điểm đó. Nhưng sau đó prof yêu cầu:

• Khoảng cách hấp dẫn của giao thức CRC-16 bit chuẩn là gì?
• Khoảng cách hấp dẫn của giao thức bit CRC-32 chuẩn là gì?

Tôi hơi bối rối và tự hỏi có ai đó có thể giúp đỡ hay không. Cảm ơn.

Answer 1

Bạn có thể đã tìm ra nó ngay bây giờ, nhưng những gì anh ta yêu cầu rất có thể là số lỗi bit tối thiểu mà mã CRC sẽ không phát hiện được. Câu trả lời phụ thuộc vào chiều rộng, đa thức và độ dài của thông điệp. Ví dụ, đa thức CRC-32 nổi tiếng nhất (0x1EDC6F41) có khoảng cách Hamming 6 hoặc cao hơn cho các thông điệp lên tới 5.275 bit (Castaglioni, Bräuer, Herrmann: Tối ưu hóa các mã kiểm tra dự phòng chu kỳ với 24 và 32 bit chẵn lẻ, IEEE Giao dịch trên Truyền thông, vol 41 số 6, tháng 6 năm 1993) có nghĩa là nó được đảm bảo để phát hiện lên đến 5 bit lật trong một tin nhắn duy nhất của 5.275 bit hoặc ít hơn.

BTW, từ mã bao gồm tổng kiểm tra, vì vậy ví dụ của bạn không chính xác.