Зачем использовать генераторный многочлен, как этот x^8 +x^2 +x+1 для CRC-8?
Зачем использовать генератор полинома, как этот G(x) =x^8 +x^2 +x+1 для CRC-8. Если это оптимально, как мы можем это доказать. или используя этот полином G(x) = x^5 + x^4 + x^2 + 1 для CRC-5-ITU.
1 ответ
Выбранный полином определяет способность CRC к обнаружению ошибок. Эта возможность измеряется в расстоянии Хэмминга, которое представляет собой минимальное количество битовых ошибок, которые могут быть внесены в сообщение, оставляя CRC без изменений. Это было бы ложным срабатыванием, когда CRC говорит, что сообщение в порядке, но это не так. Также важно то, сколько таких битовых комбинаций существует при каждом количестве битовых ошибок, называемых весами Хэмминга. Это определяет вероятность того, что ошибка из n битов приведет к ложному положительному результату.
Koopman и соавторы провели исчерпывающий поиск по всем возможным многочленам, чтобы найти те, которые имеют наибольшие расстояния Хэмминга и наименьшие веса Хемминга для различных длин сообщений. Например, приведенный вами полином 8-й степени, используемый в CRC Рекомендации МСЭ-Т I.432.1, хорош, но не лучший, который вы можете выбрать. Полином x8+ x6+ x3+ x2+1 обеспечивает расстояние Хемминга 3 для более длинных сообщений. На этих двух страницах представлены самые последние результаты Купмана.
Другой ответ здесь предполагает, что "оптимальный полином зависит от используемого набора входных данных". Единственным аспектом данных, от которого зависит возможность обнаружения ошибок полинома CRC, является длина блока, к которому применяется CRC. Благодаря свойству линейности CRC, способность обнаружения ошибок фактически полностью независима от данных в сообщении. Если вы исключаете или два сообщения одинаковой длины, то CRC этого нового сообщения будет являться эксклюзивным или CRC исходных двух сообщений. Поэтому, как только вы найдете минимальный набор ошибок, которые оставляют CRC без изменений, этот набор ошибок может быть применен к любому сообщению одинаковой длины, чтобы получить ложноположительный результат.