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

Question

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

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

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

Answer 1

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

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

Возможно, вы захотите начать с этой статьи в Википедии, посвященной Проверка циклического резервирования.

Answer 2

CRC рассматривается в другом вопросе здесь
Когда CRC более уместно использовать, чем MD5 / SHA1?
Он подходит для обнаружения случайных ошибок и прост в реализации.

Answer 3

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

Answer 4

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

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