Известно ли, что полином CRC хорош для обнаружения проскальзывания битов?

Информация о «хороших» полиномах CRC легко доступна, например:

https://checksumcrc.blogspot.com/2015/07/significantly-updated-crc-data.html

Однако вся информация, которую мне удалось найти, основана на обнаружении ошибок с относительно коротким «расстоянием Хэмминга» — ошибок, возникающих в результате нескольких перевернутых битов. Я работаю с коммуникационным средством, которое время от времени страдает от «промаха бита» — бит теряется, сдвигая все последующие биты. Промах одного бита в 1024-битной передаче может привести к сотням ошибочных битов, как определено расстоянием Хэмминга. К сожалению, известно, что рекомендуемый 32-битный полином CRC для передачи размером до 1024 бит улавливает только все ошибки расстояния Хэмминга 6:

https://users.ece.cmu.edu/~koopman/crc/

Если что-то известно о полиномах CRC, которые хорошо ловят битовые ошибки, я хотел бы узнать об этом.


crc crc32
person AlpineCarver    schedule 15.02.2019    source источник
comment
Я думал, что все CRC будут делать это. Они зависели от позиции бита, а не только от его значения.   -  person user207421    schedule 15.02.2019
comment
Да, как правило, все CRC улавливают пропуски битов, однако разные полиномы CRC работают по-разному. В цитируемом исследовании были найдены оптимальные полиномы, основанные на определенных типах ошибок (которые не включают проскальзывания битов). Я просто ищу любую информацию о производительности полинома CRC при наличии проскальзывания битов. Известное мне исследование выполняет перебор всех экземпляров определенного класса ошибок. Теоретически кто-то мог бы провести такое исследование, используя промахи битов, а не флипы битов, и я надеюсь, что кто-то это сделал. Если нет, вероятно, хороший материал для докторской степени. Тезис.   -  person AlpineCarver    schedule 15.02.2019
comment
Существуют коды исправления ошибок, специально предназначенные для обработки проскальзывания битов, но вопрос касается обнаружения ошибок (а не исправления) проскальзывания битов. Предполагая, что сбой не приводит к необнаруженным всем нулям или полученному сообщению нулевой длины, ошибка CRC будет примерно 1/2 ^ n для n-битного CRC, как ответил Марк Адлер.   -  person rcgldr    schedule 16.02.2019

Ответы (1)


arrow_upward
2
arrow_downward

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

person Mark Adler    schedule 15.02.2019
comment
Спасибо за ответ. Не могли бы вы указать мне на какие-либо исследования, подтверждающие это утверждение? - person AlpineCarver; 16.02.2019
comment
Не то, что я знаю из. Это очевидно. - person Mark Adler; 16.02.2019