CRC без отражения: остаток двоичного полинома
Построить учебное кодовое слово над GF(2), показав деление XOR и проверку нулевого остатка без скрытых параметров CRC-стандарта.
Ваш пример
Разбор примера
Остаток 001; кодовое слово 1101001
- Степень полинома r = 3.
- К сообщению добавлены r нулей и выполнено деление XOR.
- Повторное деление кодового слова даёт 000.
Метод и условия расчёта
Приписываем r нулей, где r — степень порождающего полинома.
Деление по модулю 2 заменяет вычитание операцией XOR. Остаток из r бит заменяет приписанные нули.
Теория к методу
В полиномиальной модели CRC сообщение умножают на x в степени числа проверочных битов, затем находят остаток деления на порождающий полином. Добавленный остаток делает полное кодовое слово кратным этому полиному над полем из двух элементов.
Прочитайте двоичную строку слева направо как коэффициенты от старшей степени к младшей. Полином начинается и заканчивается единицей; его степень на единицу меньше длины записи. Припишите к сообщению столько нулей, какова эта степень. Это соответствует сдвигу сообщения и освобождает младшие места для контрольных битов. Начальные нули сообщения сохраняют смысл длины записи, хотя не меняют формальный полином.
Пример: Для сообщения 1101 и генератора 1011 степень равна трём. Делим 1101000 по модулю два и получаем остаток 001.
Кодовое слово 1101001 делится на 1011 без остатка. Контрольная часть содержит именно три бита, поэтому запись 1 вместо 001 была бы неполным описанием кадра.
Вопросы по теме
Совпадёт с CRC-32 файла?
Нет. Здесь нет отражения битов, начального регистра, финального XOR и формата байтов; это явно заданная полиномиальная модель.
Нулевой остаток исключает любую ошибку?
Нет. Ошибки, кратные порождающему полиному, не обнаруживаются этим кодом.
Безопасность и надёжность данных: объяснения, примеры и практика
Основа объяснения
Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.