Контрольная сумма с низкой вероятностью ложного отрицания
В данный момент я использую простую схему контрольной суммы, которая просто добавляет слова в буфер. Во-первых, мой вопрос заключается в том, какова вероятность ложного отрицания, то есть система-получатель вычисляет ту же контрольную сумму, что и система-отправитель, даже если данные отличаются (повреждены).
Во-вторых, как я могу уменьшить вероятность ложных негативов? Какова лучшая схема проверки чека для этого. Обратите внимание, что каждое слово в буфере имеет размер 64 бита или 8 байтов, что является длинной переменной в 64-битной системе.
2 ответа
Предполагая правильную реализацию контрольной суммы, тогда вероятность того, что случайно выбранная входная строка столкнется с эталонной входной строкой, составляет 1 на 2n, где n - длина контрольной суммы в битах.
Однако, если вы говорите о вводе, который отличается от оригинала небольшим количеством битов, то вероятность коллизии, как правило, намного, намного ниже.
Одна из возможностей - взглянуть на тезис Т. Максино под названием " Эффективность контрольных сумм для встроенных сетей" (PDF), в котором содержится анализ некоторых известных контрольных сумм.
Однако обычно лучше использовать CRC, которые имеют дополнительные преимущества, такие как обнаружение ошибок пакета.
Для них статья П. Купмана " Выбор кода с циклическим избыточным кодом (CRC) для встроенных сетей" (PDF) является ценным ресурсом.