Эффективность обнаружения ошибок (CRC, контрольная сумма и т. Д.)

Question

У меня есть гипотетическая ситуация с отправкой единиц данных, каждая из которых составляет тысячу байт. Частота отказов встречается редко, но при возникновении ошибки менее вероятна ошибка с одним битом и, скорее всего, ошибка в нескольких битах подряд.

Сначала я подумал об использовании контрольной суммы, но, по-видимому, это может пропустить ошибки бит, превышающие один бит. Проверка на четность не будет работать, поэтому CRC может быть лучшим вариантом.

Использует циклическую избыточность Проверка на тысячу байт? Или есть другие методы, которые будут работать лучше?

Answer 1

Cyclic Redundancy Checks (CRCs) являются популярными конкретно из-за их эффективности при обнаружении ошибок нескольких бит с гарантированной точностью.

Существуют различные конструкции для генерации полиномов CRC, где компромисс - это точность и вычислительная сложность. В вашем случае вы можете выбрать «самый быстрый», который соответствует вашим требованиям точности.

Возможно, вы захотите начать с этой статьи в Википедии по адресу Cyclic Redundancy Check.

Answer 2

Это нормально использовать CRC. Я не уверен, что вы подразумеваете под «эффективностью», но я думаю, что иногда CRC реализуется на аппаратных средствах (например, на карте Ethernet). В противном случае вы можете найти «оптимизированные» реализации (используя таблицу поиска).

Answer 3

CRC рассматривается другой вопрос здесь
When is CRC more appropriate to use than MD5/SHA1?
Он подходит для обнаружения случайных ошибок и легко осуществить.

Answer 4

Насколько велики ваши сектора дисков? Вероятно, не менее 512 байт. CRC - это проверенная временем схема аппаратного уровня ECC.

Полиномиальные алгоритмы CRC довольно эффективны для небольших количеств битовых ошибок. Точная точность математически вычислима. CRC также очень эффективен для работы на оборудовании, где относительно небольшое количество ворот и регистров сдвига может управлять работой «на лету».