Информатика · объяснение и практика

Как получить CRC делением двоичных полиномов

Вычислить систематический CRC-остаток над GF(2), проверить делимость кодового слова и отличить учебную модель от параметризованного стандарта.

Синие фигурные скобки держат между собой оранжевый квадрат.

Вузовский уровень · Все вузовские темы

В теме Безопасность и надёжность данных · Учебная карта

Главная мысль

В полиномиальной модели CRC сообщение умножают на x в степени числа проверочных битов, затем находят остаток деления на порождающий полином. Добавленный остаток делает полное кодовое слово кратным этому полиному над полем из двух элементов.

Метод и условия

Прочитайте двоичную строку слева направо как коэффициенты от старшей степени к младшей. Полином начинается и заканчивается единицей; его степень на единицу меньше длины записи. Припишите к сообщению столько нулей, какова эта степень. Это соответствует сдвигу сообщения и освобождает младшие места для контрольных битов. Начальные нули сообщения сохраняют смысл длины записи, хотя не меняют формальный полином.

Делите как обычные многочлены, но вычитание коэффициентов замените XOR. Когда текущий старший бит равен единице, совместите с ним старшую единицу порождающего полинома и выполните XOR всего его блока. После прохода останется меньше битов, чем длина полинома. Запишите остаток в точно заданном числе мест, сохранив ведущие нули. Эти биты заменяют нули, приписанные к исходному сообщению. Отрицательных коэффициентов и переносов между разрядами здесь нет.

Проверка и типичная ошибка

Проверка выполняется повторным делением полного кодового слова на тот же полином. Остаток должен стать нулевым. Однако нулевой остаток не означает, что любая возможная ошибка исключена. Если полином ошибки кратен порождающему, ошибочное слово также пройдёт эту проверку. Способность обнаруживать классы ошибок зависит от выбора полинома и длины блока, поэтому случайный короткий генератор не заменяет обоснованную спецификацию.

Не сравнивайте этот ответ непосредственно с CRC файла, пока не согласованы все параметры. Реальные форматы дополнительно задают порядок битов и байтов, отражение, начальное состояние регистра и финальное преобразование. В данном инструменте этих скрытых операций нет: он показывает только указанное полиномиальное деление. Соответственно, это не криптографический хеш и не механизм защиты от намеренной подделки. Для ручной проверки полезно выбрать короткое сообщение, проследить каждый XOR и отдельно убедиться, что степень полученного остатка меньше степени генератора. Потеря ведущего нуля остатка меняет длину контрольной части при передаче.

Пример

Для сообщения 1101 и генератора 1011 степень равна трём. Делим 1101000 по модулю два и получаем остаток 001.

Кодовое слово 1101001 делится на 1011 без остатка. Контрольная часть содержит именно три бита, поэтому запись 1 вместо 001 была бы неполным описанием кадра.

От чтения к действию

А теперь — вы

Какую операцию используют вместо вычитания коэффициентов в GF(2)?

Частые вопросы

Совпадёт с CRC-32 файла?

Нет. Здесь нет отражения битов, начального регистра, финального XOR и формата байтов; это явно заданная полиномиальная модель.

Нулевой остаток исключает любую ошибку?

Нет. Ошибки, кратные порождающему полиному, не обнаруживаются этим кодом.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться