Калькулятор CRC / XOR / деления по модулю 2 столбиком

Как пользоваться калькулятором CRC / XOR / Modulo-2

Чтобы вычислить CRC делением по модулю 2, выполните эти 4 шага:

• Введите двоичное сообщение (биты данных) в первое поле.
• Введите порождающий многочлен как двоичные биты во второе поле.
• Калькулятор добавляет (n − 1) нулевых битов, где n — длина генератора.
• Нажмите «Вычислить», чтобы XOR-ить сообщение вниз и прочитать остаток как CRC.

Частное обычно отбрасывается в работе с CRC — остаток — это контрольная сумма, добавляемая к сообщению перед передачей.

CRC и арифметика по модулю 2

Циклический избыточный код обнаруживает ошибки передачи, трактуя сообщение как большой двоичный многочлен и деля его на согласованный порождающий многочлен. Деление выполняется в арифметике по модулю 2 (GF(2)), где сложение и вычитание идентичны и равны XOR — без переносов и заимствований. Остаток этого деления — CRC. Когда получатель делит сообщение плюс CRC на тот же генератор, остаток 0 означает отсутствие обнаруженной ошибки. Этот калькулятор воспроизводит точно этот побитовый процесс.

Как работает CRC-деление по модулю 2

Калькулятор вычисляет CRC через пять внутренних действий:

• Добавляет (n − 1) нулевых битов к сообщению, где n — число битов генератора.
• Выравнивает генератор под крайней левой 1 текущего остатка.
• XOR-ит генератор в эти биты (вычитание по модулю 2 без заимствования).
• Сдвигается к следующей ведущей 1 и повторяет XOR-выравнивание.
• Останавливается, когда оставшихся битов меньше, чем у генератора; это CRC.

Каждый бит частного равен 1 там, где генератор XOR-ится, и 0 в остальных местах, но для CRC важен только итоговый остаток.

Формула CRC-деления

Калькулятор CRC / XOR / Modulo-2 вычисляет CRC = (M(x) · xⁿ⁻¹) mod G(x) в GF(2), где M(x) — сообщение, G(x) — генератор из n битов, а все сложения — XOR. Передаваемый кадр: M(x)·xⁿ⁻¹ + CRC, который G(x) делит нацело. На приёме нулевой остаток подтверждает целостность.

Примеры CRC / XOR

Эти примеры показывают деление по модулю 2 с XOR на каждом шаге.

Пример 1 — Сообщение 1101, генератор 101

1. Длина генератора 3, добавьте 2 нуля: 1101 становится 110100.
2. XOR-ьте 101 в ведущие биты повторно: 110100 → 011100 → 001000 → 000010.
3. Последние 2 бита, 10, — остаток CRC.

Пример 2 — Почему вычитание — это XOR

1. По модулю 2: 1 + 1 = 0 и 1 − 1 = 0, поэтому сложение и вычитание — одна операция.
2. Эта операция — побитовое XOR, без переноса и заимствования.
3. Каждый шаг деления — одно XOR генератора в текущие биты.

Пример 3 — Проверка получателем

1. Добавьте CRC к сообщению и разделите на тот же генератор.
2. XOR-ьте вниз точно как раньше.
3. Остаток 0 означает отсутствие обнаруженной ошибки.

Длина генератора 3, добавьте 2 нуля: 1101 становится 110100.
XOR-ьте 101 в ведущие биты повторно: 110100 → 011100 → 001000 → 000010.
Последние 2 бита, 10, — остаток CRC.

По модулю 2: 1 + 1 = 0 и 1 − 1 = 0, поэтому сложение и вычитание — одна операция.
Эта операция — побитовое XOR, без переноса и заимствования.
Каждый шаг деления — одно XOR генератора в текущие биты.

Добавьте CRC к сообщению и разделите на тот же генератор.
XOR-ьте вниз точно как раньше.
Остаток 0 означает отсутствие обнаруженной ошибки.

Разобранные задачи CRC

Как вычислить CRC для 10110 с генератором 1011?

Добавьте 3 нуля (длина генератора 4), получив 10110000, затем XOR вниз. Выровняйте 1011 под каждой ведущей 1 и XOR: 10110000 → 00100000 → после последовательных XOR последние 3 бита формируют остаток CRC. Остаток добавляется к 10110, чтобы весь кадр делился на 1011 без остатка.

Почему нулевой остаток означает целостность данных?

Отправитель выбирает CRC так, чтобы переданный кадр был точным кратным генератора. Любое кратное G(x), делённое на G(x), даёт остаток 0. Если биты изменятся в пути, кадр обычно перестаёт быть кратным, и деление получателя даёт ненулевой остаток, сигнализируя об ошибке.

Типичные ошибки CRC / modulo-2

CRC-деление по модулю 2 даёт 5 частых ошибок:

• Использование обычного двоичного вычитания с заимствованиями вместо XOR.
• Добавление неверного числа нулевых битов (должно быть длина генератора минус один).
• Выравнивание генератора под битом 0 вместо ведущей 1.
• Учёт переносов, как будто они существуют в арифметике GF(2).
• Сообщение частного как CRC вместо остатка.

Калькулятор CRC / XOR / Modulo-2 XOR-ит на каждом шаге, добавляет правильные нули и возвращает остаток как контрольную сумму.

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