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

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

7 голосов
/ 27 сентября 2010

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

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?

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

1 Ответ

4 голосов
/ 21 декабря 2010

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

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

...