Что такое расстояние Хэмминга и как его определить для схемы CRC?

Question

Во время обучения на уроке по компьютерным сетям профессор говорил о расстоянии Хэмминга между двумя действительными кодовыми словами в примере кода. Я читал о расстоянии Хэмминга, и это имеет смысл с точки зрения разницы расстояний между двумя строками. Например:

Code Word 1 = 10110 

Отправитель отправляет кодовое слово 1, и возникает ошибка, и получатель получает 10100. Таким образом, вы видите, что 4-й бит был поврежден. Это приведет к расстоянию Хэмминга 1, потому что:

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

XOR двух строк приводит к одному 1, поэтому расстояние Хэмминга равно 1. Я понимаю это до этого момента. Но тогда проф спрашивает:

• Каково расстояние Хемминга стандартного битового протокола CRC-16?
• Каково расстояние Хемминга стандартного битового протокола CRC-32?

Я немного запутался и подумал, может ли кто-нибудь помочь. Благодарю.

Answer 1

Вы, наверное, уже поняли это, но он, скорее всего, попросил указать минимальное количество битовых ошибок, которые код CRC не обнаружит. Ответ зависит от ширины, полинома и длины сообщения. Например, самый известный полином CRC-32 (0x1EDC6F41) имеет расстояние Хемминга 6 или лучше для сообщений длиной до 5 275 бит (Castaglioni, Bräuer, Herrmann: оптимизация кодов проверки циклическим избыточным кодом с 24 и 32 битами четности, IEEE "Транзакции в области коммуникаций", том 41, № 6, июнь 1993 года), что означает, что гарантированно можно обнаружить до 5 перевернутых бит в одном сообщении длиной 5 275 бит или менее.

Кстати, кодовое слово включает в себя контрольную сумму, поэтому ваш пример неверен.