Я видел 8-битные, 16-битные и 32-разрядные CRC.
В какой момент мне нужно перейти к более широкому CRC?
Моя реакция кишки заключается в том, что она основана на длине данных:
EDIT: Посмотрите на страницу Википедии о CRC и Lott ответ, вот что мы имеем:
< 64 bytes: 8-битный CRC
< 16K байтов: 16-разрядный CRC
< 512M байт: 32-разрядный CRC
Это не тема исследования. Это действительно хорошо понято: http://en.wikipedia.org/wiki/Cyclic_redundancy_check
Математика довольно проста. 8-разрядный CRC загружает все сообщения до одного из 256 значений. Если ваше сообщение имеет длину более нескольких байтов, вероятность того, что несколько сообщений, имеющих одинаковое значение хэша, будет повышаться все выше и выше.
16-битный CRC аналогичным образом дает вам один из 65 536 доступных хеш-значений. Каковы шансы любых двух сообщений, имеющих одно из этих значений?
32-разрядный CRC дает вам около 4 миллиардов доступных хэш-значений.
Из статьи в википедии: "максимальная общая длина блока равна 2**r − 1". Это в битах. Вам не нужно делать много исследований, чтобы увидеть, что 2**9 - 1 составляет 511 бит. Используя CRC-8, несколько сообщений длиной более 64 байтов будут иметь одинаковую контрольную сумму CRC.
Эффективность CRC зависит от нескольких факторов. Вам нужно не только выбрать РАЗМЕР CRC, но и использовать GENERATING POLYNOMIAL. Существуют сложные и неинтуитивные компромиссы в зависимости от:
Вывод полиномиального кода циклического избыточного кода для встроенных сетей, Филипп Коопман и Тридиб Чакраварти, опубликованный в материалах Международной конференции 2004 года по надежным системам и сетям, дает очень хороший обзор и дает несколько рекомендаций. Он также предоставляет библиографию для дальнейшего понимания.
http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf
Я думаю, что размер CRC больше связан с тем, насколько уникален CRC, который вам нужен, а не размер входных данных. Это связано с конкретным использованием и количеством элементов, на которых вы вычисляете CRC.
CRC следует выбирать конкретно для длины сообщений, это не просто вопрос размера CRC: http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf
Выбор длины CRC по сравнению с размером файла в основном имеет значение в тех случаях, когда у человека более вероятный вход, который отличается от "правильного" ввода тремя или меньшими битами, чем для того, чтобы иметь массовый разброс. Учитывая два входа, которые существенно различаются, вероятность ложного совпадения будет составлять около 1/256 при большинстве форм 8-битного контрольного значения (включая CRC), 1/65536 с большинством форм 16-битной контрольной величины (включая CRC) и т.д. Преимущество CRC исходит от обработки входов, которые очень похожи.
С 8-битным CRC, полином которого генерирует два периода длины 128, доля одиночных, двойных или тройных битовых ошибок в пакете, короче, чем тот, который не обнаружен, не будет 1/256 - он будет нуль. Аналогично, с 16-битным CRC периода 32768, используя пакеты 32768 бит или меньше.
Если пакеты больше, чем период CRC, однако, двухбитовая ошибка будет не обнаружена, если расстояние между ошибочными битами будет кратно периоду CRC. Хотя это может показаться не очень вероятным сценарием, при отправке длинного пакета с CRC8, CRC8 будет хуже улавливать двойные битовые ошибки, чем при улавливании "пакетов полностью скремблированных" ошибок. Если двубитовые ошибки являются вторым наиболее распространенным режимом отказа (после однобитовых ошибок), это было бы плохо. Однако, если что-то, что искажает некоторые данные, скорее всего, повредит многие из них, низкое поведение CRC с двубитными ошибками может быть проблемой без проблем.