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

Question

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

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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

Answer 4

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