Зачем использовать многочлен генератора, такой как G (x) = x^8 + x^2 + x + 1 для CRC-8. Если это оптимально, то как мы можем это доказать. или , используя этот полином G (x) = x^5 + x^4 + x^2 + 1 для CRC-5-ITU.Зачем использовать многочлен генератора, такой как x^8 + x^2 + x + 1 для CRC-8?
Выбранный полином определяет способность обнаружения ошибок CRC. Эта способность измеряется на расстоянии Хэмминга, что является минимальным количеством ошибок в битах, которые могут быть введены в сообщении, оставив CRC без изменений. Это будет ложным положительным, когда CRC говорит, что сообщение в порядке, но это не так. Также важно, сколько таких битовых шаблонов существует при каждом количестве битовых ошибок, называемых весом Хэмминга. Это определяет вероятность ошибки n бит приводит к ложному срабатыванию.
Exhaustive searches over all possible polynomials have been done by Koopman, et al, чтобы найти тех, кто имеет самые большие расстояния Хэмминга и самые маленькие весы Хэмминга для различных длин сообщений. Например, полином степени 8, который вы цитируете, used in the ITU-T Recommendation I.432.1 CRC, хорош, но не самый лучший, который вы могли бы выбрать. Многочлен х + х + х + X + 1 обеспечивает расстояние Хэмминга 3 для более длинных сообщений. Эти twopages обеспечивают последние результаты Koopman.
Другой ответ здесь предполагает, что «оптимальный многочлен зависит от используемого набора входных данных». Единственным аспектом данных, на которые зависит способность обнаружения ошибок полинома CRC, является длина блока, на который применяется CRC. Из-за свойства линейности CRC функция обнаружения ошибок фактически является полностью независимой данных в сообщении. Если вы являетесь эксклюзивным или двумя сообщениями одинаковой длины, CRC этого нового сообщения будет эксклюзивным или CRC исходных двух сообщений. Поэтому, как только вы найдете минимальный набор ошибок, которые оставляют CRC неизменным, тогда этот набор ошибок может быть применен к любому сообщению той же длины, чтобы получить ложноположительный.