вычисление CRC всего файла вероятность необнаруженной ошибки

Я читал несколько статей о том, что вероятность того, что код CRC не будет обнаружен, не зависит от размера сообщения, а относится только к битам CRC. 2^(-32) for 32bit CRC

Мои вопросы:

  1. зачем нам нужны более широкие CRC? даже если мы планируем использовать 16-битную CRC для всего файла, вероятность наличия необнаруженной ошибки почти равна нулю, и мы можем обнаружить все ошибки в файле.
  2. Зачем нужно, чтобы при использовании 32-битной CRC размер файла был меньше 2 ^ 32 (512 МБ), означает ли это, что если у нас есть пакетная ошибка, вызывающая более 512 МБ изменений файла, CRC не может обнаружить это?
Источник

1 ответ

Решение

  1. Вероятность обнаружения случайного шаблона ошибок для 16-битной CRC составляет около 2^(-16) (1/65536). 32-битный CRC уменьшает это до 2^(-32) (1 / 4 миллиарда).

  2. Все CRC обнаруживают одиночную битовую ошибку независимо от размера файла. Если целью является 32-битный CRC, который гарантированно обнаруживает любую двухбитную комбинацию ошибок, максимальный размер файла + CRC составляет 2^32-1 бит. Если размер, включая CRC, составляет>= 2^32 бита, то при возникновении 2-битной ошибки в бите [i+0] и бите [i+2^32-1] ошибка не будет обнаружена. Если целью является CRC, который обнаруживает все 3 битовых ошибки, что обычно выполняется при наличии в CRC как минимум 2 простых полиномиальных множителей, одним из которых является (x+1), который обнаружит любое нечетное количество битовых ошибок, и 31-битный коэффициент, который обнаружит любую 2-битную ошибку, если размер файла + CRC <= 2^31-1 бит. По мере увеличения количества ошибок, которые гарантированно исправляет CRC, максимальный размер файла + CRC уменьшается. Взгляните на стол в "CRC Zoo". Это список полиномов CRC,за которым следует максимальное количество битов данных (не включая CRC) для обнаружения всех 2, 3, 4, 5, ... битовых ошибок (расстояние Хэмминга 3, 4, 5, 6,...).

https://users.ece.cmu.edu/%7Ekoopman/crc/crc32.html

Еще одна проблема - это вероятность отсутствия ошибок в переданных или записанных данных. Это зависит от частоты ошибок и размера данных. Если частота ошибок для байта равна e, то вероятность нулевых ошибок означает отсутствие ошибок во всех байтах, или (1 - e)^n, где n - количество байтов. Чтобы справиться с ситуациями, когда вероятность ошибок значительна, используется некоторый тип кода исправления ошибок, чтобы уменьшить вероятность неисправимой ошибки.

Источник
Другие вопросы по тегам