Генерация полиномиального ключа для crc
Со ссылкой на эту статью:https://www.digikey.com/eewiki/display/microcontroller/CRC+Basics
Полиномиальный ключ - важная часть CRC. Ключи - это не просто случайные многочлены; они генерируются с использованием набора математических формул и предназначены для увеличения количества ошибок, которые выявляет процесс CRC. Полином обычно определяется сетевым протоколом или внешним устройством. Поскольку имеется устоявшийся набор ключей, процессы определения ключей здесь не обсуждаются.
Однако я понимаю, как вычисляется CRC с заданным полиномиальным ключом, как генерировать полиномиальный ключ и гарантировать, что он может уловить как можно больше ошибок с заданным набором протоколов?
Я предполагаю, что полиномиальный ключ имеет какое-то отношение к:
- длина данных
- скорость передачи данных
- другие?
1 ответ
Часть об использовании математических формул для генерации полиномов CRC несколько вводит в заблуждение. Число 1 бит в полиноме CRC - это максимально возможное расстояние Хэмминга (HD) для полинома, и, как правило, фактическое расстояние Хэмминга будет меньше в зависимости от длины данных. Максимальное обнаружение ошибок по битам - это расстояние Хэмминга - 1.
Обычно полиномы CRC, которые обнаруживают большее количество битов, являются произведением нескольких простых полиномов. Например, для 32-битной CRC, которая может обнаруживать до 7 ошибок для данных + длина CRC = 1024 бит, 33-битный полином CRC 0x1f1922815 = 0x787*0x557*0x465*0x3*0x3. Фактор 0x3 обнаружит любое нечетное количество битовых ошибок, поэтому CRC необходимо обнаружить все возможные 6-битные ошибки в 1024 битах.
Я не знаю формулы для определения максимального обнаружения битовых ошибок, и, как правило, выполняется несколько оптимизированный поиск грубой силы. В качестве примера, скажем, 32-битный полином CRC проверяется, чтобы узнать, может ли он обнаружить все 6-битные ошибки для данных + длина CRC 1024 бит, количество возможных 6-битных шаблонов ошибок в 1024 битах - гребенка (1024,6) = 1 577 953 087 760 896. Чтобы уменьшить это до чего-то разумного, количество возможных 3-битных ошибок, comb(1024,3) = 178 433 024, используется для создания большой таблицы, каждая запись которой содержит CRC и 3-битные индексы. Таблица сортируется, а затем используется для проверки конфликтов, когда CRC 3-битного шаблона совпадает с CRC другого 3-битного шаблона. Также потребуется проверка на сбой для 4-битных шаблонов (проверка на конфликты между двумя разными 2-битными шаблонами).
Как правило, по мере уменьшения длины данных максимальное количество битов ошибки, гарантированно обнаруживаемых, увеличивается. Вот ссылка на набор полиномов CRC и их возможности обнаружения ошибок.
https://users.ece.cmu.edu/~koopman/crc/crc32.html
Страница заметок объясняет записи в таблице: