Информатика / Кодирование информации

Циклический избыточный код CRC и остаток полинома

CRC дописывает к сообщению остаток полиномиального деления над GF(2). Сложение и вычитание выполняются XOR, поэтому проверочное слово делится на выбранный порождающий полином без остатка.

Опубликовано: 6 ноября 2026 г.Обновлено: 6 ноября 2026 г.

Формула

R(x)=M(x)x^r\bmod G(x),\qquad C(x)=M(x)x^r+R(x)\quad\text{в }\mathrm{GF}(2)

Схема Снятие старших степеней при XOR-делении

Каждая строка — остаток после очередного XOR:1101000 →0110000 →0011100 →0001010 →0000001. Последние три бита 001.

Обозначения

$M(x)$: полином информационных битов, биты коэффициентов
$G(x)$: порождающий полином степени r, биты коэффициентов
$R(x)$: остаток степени меньше r, r проверочных битов с ведущими нулями
$C(x)$: передаваемый кодовый полином, биты коэффициентов
$r$: степень генератора, битовые позиции

Условия применения

Операции идут над полем GF(2), старший бит строки соответствует старшей степени. В данном учебном варианте нет отражения битов, начального регистра и финального XOR. Генератор имеет степень r≥1, старший и свободный коэффициенты равны 1.

Ограничения

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

Подробное объяснение

CRC рассматривает битовую строку как полином над полем GF(2). Умножение на x^r добавляет r нулей, а деление выполняется XOR вместо обычного вычитания. Остаток R имеет меньше r бит и приклеивается к сообщению.

Приёмник делит всё слово на тот же G: корректная передача даёт остаток ноль. Один изменённый бит обычно меняет остаток, но CRC не исправляет ошибку и не гарантирует обнаружение произвольного повреждения.

Качество зависит от G: некоторые полиномы гарантированно ловят все одиночные ошибки и короткие пакеты ошибок. Нельзя заменять XOR обычным двоичным остатком с переносами.

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

Если ошибка E(x) добавлена к кодовому слову, приёмник фактически получает C(x)+E(x). Так как C делится на G, остаток зависит только от E. Это сразу объясняет необнаруживаемость ошибки, кратной генератору: ненулевое повреждение может иметь нулевой синдром.

Как пользоваться формулой

Запишите сообщение и генератор как полиномы GF(2), определите степень r и согласуйте, какой бит соответствует старшей степени.
Допишите к сообщению r нулевых битов, что соответствует умножению M(x) на x^r перед вычислением остатка.
Выполните длинное деление, заменяя вычитание XOR и не используя переносы; остаток дополните ведущими нулями до r бит.
Присоедините остаток к сообщению и проверьте деление полного слова на тот же генератор: в учебной схеме остаток должен стать нулём.

Историческая справка

Циклические коды связали битовые строки с полиномами над конечными полями. Такое представление позволяет описывать проверочные операции алгебраически: ошибки рассматриваются как добавление полинома, а проверка делимости превращается в вычисление остатка.

В цифровой аппаратуре длинное деление реализуется сдвиговым регистром и XOR-связями. Университетские материалы Cornell2017 года рассматривают CRC как механизм обнаружения повреждений, а RFC1662 1994 года задаёт практическую процедуру FCS для кадров PPP. Современные протоколы добавляют соглашения о порядке битов и начальных состояниях, поэтому сохранение названия полинома недостаточно для полной спецификации алгоритма.

Историческая линия формулы

CRC относится к традиции циклических кодов и полиномиальной арифметики GF(2). Здесь не приписывается авторство конкретной учебной строки современному стандарту. Генератор 1011 и отсутствие дополнительных параметров заданы только для прозрачного разбора деления.

Пример

Сообщение 1101 и генератор 1011 имеют полиномы M=x³+x²+1, G=x³+x+1. Степень r=3, поэтому расширенное сообщение 1101000. При делении XOR последовательно убираем старшие степени:1101000⊕1011000=0110000; затем 0110000⊕0101100=0011100. Далее 0011100⊕0010110=0001010, а 0001010⊕0001011=0000001. Остаток степени меньше 3 равен 001, а не 111. Передаваемое слово 1101|001=1101001. Ответ: проверочные биты 001. Повторное XOR-деление 1101001 на 1011 даёт 000, поскольку добавленный остаток компенсирует исходный. Обычный целочисленный остаток от деления 104 на 11 здесь неприменим: арифметика GF(2) не содержит переносов и займов.

Частая ошибка

Не заменяйте XOR-деление обычным целочисленным модулем. Не теряйте ведущие нули остатка:001 занимает три проверочных позиции. Не объявляйте нулевой синдром доказательством подлинности сообщения. Не сравнивайте учебный остаток с библиотечным CRC, не согласовав отражение битов, начальный регистр и финальный XOR.

Практика

Задачи с решением

Проверка готового слова

Условие. Разделите 1101001 на 1011 над GF(2).

Решение. Исходное расширение 1101000 имеет остаток 001, а добавление 001 по XOR уничтожает его. Полное деление даёт 000.

Ответ. 000; учебная проверка проходит.

Один повреждённый бит

Условие. В слове 1101001 изменился младший бит, получилось 1101000. Найдите синдром.

Решение. Ошибка E(x)=1. Остаток 1 при делении на генератор степени 3 остаётся 1, то есть 001.

Ответ. 001; ошибка обнаружена.

Дополнительные источники

https://bpb-us-w2.wpmucdn.com/sites.coecis.cornell.edu/dist/4/81/files/2017/03/ece4880_lecture10-1xqp87q.pdf
https://www.rfc-editor.org/rfc/rfc1662.html

Связанные формулы

Информатика

Расстояние Хэмминга между двоичными словами

$d(x,y)=\sum [x_i\ne y_i]$

Расстояние Хэмминга между двоичными словами: формула d(x,y)=\sum [x_i\ne y_i] помогает величины d, x_i, y_i заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата.

Информатика

Минимальное расстояние кода: сколько ошибок можно исправить

$t=\left\lfloor\frac{d_{\min}-1}{2}\right\rfloor$

Минимальное расстояние между разрешёнными кодовыми словами определяет гарантированное число исправляемых замен битов. Чтобы исправить любые t ошибок, нужно расстояние не меньше 2t+1.

Информатика

Граница Хэмминга: сколько слов помещается в исправляющий код

$M\sum_{j=0}^{t}\binom{n}{j}\le 2^n$

Граница Хэмминга ограничивает число слов M двоичного блочного кода длины n, исправляющего любые t замен. Области возможных повреждений вокруг разных слов должны помещаться среди всех двоичных строк без пересечений.