Сложение по модулю 2

Сложение по модулю 2 — это бинарная логическая операция, результат которой истинен (равен 1) тогда и только тогда, когда количество истинных (равных 1) операндов нечётно. В булевой алгебре эта операция также известна как «исключающее ИЛИ» (XOR, eXclusive OR). Сложение по модулю 2 является одной из фундаментальных операций в цифровой электронике, теории кодирования, криптографии и компьютерной арифметике.

Определение и обозначения

Операция сложения по модулю 2 обозначается символом ⊕ (плюс в кружке) или знаком ≠ (неравенство). В математической записи часто используется символ ⊕, а в программировании — оператор XOR, ^ (в языках C, C++, Java, Python) или ⊻. В булевой алгебре операция также может записываться как A XOR B.

Формально сложение по модулю 2 для двух операндов A и B определяется следующей таблицей истинности:

Для произвольного количества операндов результат равен 1, если количество единиц среди них нечётно, и 0 — если чётно. Например, 1 ⊕ 1 ⊕ 0 = 0 (две единицы — чётное число), а 1 ⊕ 0 ⊕ 1 ⊕ 0 = 0 (две единицы), 1 ⊕ 1 ⊕ 1 = 1 (три единицы — нечётное число).

Свойства

Сложение по модулю 2 обладает рядом важных алгебраических свойств, которые делают его удобным для практического применения:

• Коммутативность: A ⊕ B = B ⊕ A (порядок операндов не важен).
• Ассоциативность: (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C) (группировка операндов не влияет на результат).
• Нейтральный элемент: A ⊕ 0 = A (сложение с нулём не меняет значение).
• Обратный элемент: A ⊕ A = 0 (каждый элемент является обратным самому себе). Это свойство означает, что операция является инволюцией: повторное применение возвращает исходное значение.
• Дистрибутивность относительно конъюнкции: (A ⊕ B) ∧ C = (A ∧ C) ⊕ (B ∧ C) (умножение (конъюнкция) дистрибутивно относительно сложения по модулю 2).
• Связь с арифметическим сложением: A ⊕ B = (A + B) mod 2, где A и B — двоичные цифры (0 или 1). В двоичной арифметике сложение по модулю 2 — это сложение без переноса в старший разряд.

История

Понятие сложения по модулю 2 восходит к работам немецкого математика и философа Готфрида Вильгельма Лейбница, который в XVII веке разработал двоичную арифметику. Однако систематическое изучение булевой алгебры, частью которой является XOR, началось в середине XIX века с работ английского математика Джорджа Буля. В 1847 году Буль опубликовал трактат «Математический анализ логики», где заложил основы алгебры логики, хотя операция XOR в явном виде не выделялась.

В 1930-х годах американский математик Клод Шеннон в своей магистерской диссертации «Символический анализ релейных и переключательных схем» показал, что булева алгебра может быть реализована с помощью электрических реле и переключателей. Это открыло путь к созданию цифровых вычислительных машин. Операция XOR стала одной из базовых логических операций, реализуемых в цифровых схемах.

В 1940-х годах XOR активно применялась в криптографии, в частности, в шифре Вернама (одноразовый блокнот), где сообщение XORится с ключом той же длины. Этот метод, предложенный Гилбертом Вернамом в 1917 году, остаётся теоретически невзламываемым при правильном использовании.

Реализация в цифровой электронике

В цифровой логике операция XOR реализуется с помощью логического элемента «исключающее ИЛИ». На принципиальных схемах он обозначается символом =1 (в стандарте IEC 60617) или символом ⊕ (в стандарте ANSI). Логический элемент XOR имеет два входа и один выход.

Схемотехническая реализация

Элемент XOR может быть построен из базовых логических элементов (И, ИЛИ, НЕ). Одна из стандартных схем:

A ⊕ B = (A ∧ ¬B) ∨ (¬A ∧ B)

Другая распространённая реализация — на основе элемента «исключающее ИЛИ-НЕ» (XNOR), который является инверсной версией XOR. В интегральных микросхемах (например, серии 74xx) выпускаются готовые элементы XOR, такие как 74LS86 (четыре двухвходовых элемента XOR).

Применение в цифровых схемах

• Сумматоры: В полусумматоре и полном сумматоре XOR используется для вычисления суммы двух двоичных цифр без учёта переноса.
• Компараторы: Схемы сравнения двух двоичных чисел на равенство используют XOR для поразрядного сравнения: если все разряды равны (XOR даёт 0), числа равны.
• Генераторы псевдослучайных чисел: Регистры сдвига с линейной обратной связью (LFSR) используют XOR для формирования обратной связи.
• Контроль чётности: XOR применяется для вычисления бита чётности (parity bit) в системах передачи данных. Например, для 8-битного слова бит чётности вычисляется как XOR всех битов.

Применение

Криптография

Сложение по модулю 2 является основой многих криптографических алгоритмов. В шифре Вернама (одноразовый блокнот) открытый текст XORится с ключом, имеющим ту же длину. При правильном использовании (ключ истинно случайный, используется один раз) этот шифр является абсолютно стойким. В современных алгоритмах симметричного шифрования, таких как AES (Advanced Encryption Standard), XOR используется на этапе сложения с раундовым ключом (AddRoundKey). В поточных шифрах (например, RC4, Salsa20) XOR применяется для объединения потока данных с гаммой (псевдослучайной последовательностью).

Теория кодирования

В теории кодирования XOR используется для построения кодов с обнаружением и исправлением ошибок. Например, код Хэмминга использует XOR для вычисления контрольных битов. В RAID-массивах (Redundant Array of Independent Disks) уровня 5 и 6 XOR применяется для вычисления избыточности (parity), позволяющей восстановить данные при отказе одного диска. В кодах Рида — Соломона и других линейных кодах XOR является одной из основных операций.

Компьютерная арифметика

В процессорах операция XOR реализована на аппаратном уровне как одна из базовых арифметико-логических операций. Она используется для:

• Обнуления регистров: инструкция XOR EAX, EAX (в архитектуре x86) обнуляет регистр EAX, так как A ⊕ A = 0.
• Перестановки значений: трюк с XOR позволяет обменять значения двух переменных без использования временной переменной (например, a = a ^ b; b = a ^ b; a = a ^ b;).
• Проверки чётности: вычисление бита чётности для слова.
• Маскирования битов: XOR с маской позволяет инвертировать выбранные биты числа.

Графика и обработка изображений

В компьютерной графике XOR используется для операций над пикселями. Например, в режиме XOR-рисования (XOR mode) повторное рисование той же фигуры в том же месте восстанавливает исходное изображение. Это свойство используется для создания анимации курсора мыши или выделения областей. В стеганографии XOR может применяться для встраивания скрытых сообщений в младшие биты изображения.

Интересные факты

• В языке программирования Python операция XOR обозначается символом ^. Например, 5 ^ 3 даёт 6 (101 XOR 011 = 110).
• В криптографии свойство A ⊕ A = 0 используется для создания «слепых» подписей и протоколов с нулевым разглашением.
• В теории игр XOR применяется в анализе игры «Ним» (Nim), где выигрышная стратегия основана на вычислении XOR-суммы размеров кучек.
• В цифровой обработке сигналов XOR используется в фазовых детекторах и схемах фазовой автоподстройки частоты (ФАПЧ).

Критика и ограничения

Хотя XOR является мощным инструментом, его применение имеет ограничения. В криптографии использование XOR без должной случайности ключа (например, повторное использование одного и того же ключа) делает шифр уязвимым для атак на основе известного открытого текста. В цифровых схемах реализация XOR требует большего количества транзисторов по сравнению с базовыми элементами И или ИЛИ, что увеличивает энергопотребление и задержки. В некоторых приложениях (например, в RAID-массивах) XOR может быть недостаточен для защиты от множественных ошибок, что требует использования более сложных кодов, таких как код Рида — Соломона.

Источники

• Буль, Дж. «Математический анализ логики» (1847).
• Шеннон, К. «Символический анализ релейных и переключательных схем» (1938).
• Вернам, Г. «Шифрование с помощью одноразового блокнота» (1917).
• Хэмминг, Р. «Коды с обнаружением и исправлением ошибок» (1950).
• Таненбаум, Э., Уэзеролл, Д. «Компьютерные сети» (5-е издание, 2011).
• Шнайер, Б. «Прикладная криптография» (2-е издание, 1996).