Проверка чётности

Проверка чётности — это операция определения чётности числа, то есть его способности делиться на два без остатка. В более широком смысле, в теории информации и вычислительной технике, под проверкой чётности понимают метод контроля целостности данных, основанный на подсчёте количества единичных битов в двоичной последовательности (бите чётности). Проверка чётности является простейшей формой обнаружения ошибок при передаче или хранении информации.

Математическая основа

В математике чётность — это фундаментальное свойство целого числа. Число называется чётным, если оно делится на 2 (например, −4, 0, 2, 8). Число называется нечётным, если оно не делится на 2 (например, −3, 1, 5, 9). Формально, целое число \( n \) является чётным, если существует целое число \( k \) такое, что \( n = 2k \). Соответственно, \( n \) нечётно, если \( n = 2k + 1 \).

Проверка чётности в математике сводится к анализу последней цифры числа в десятичной системе счисления (для чётности достаточно, чтобы последняя цифра была 0, 2, 4, 6 или 8) или к вычислению остатка от деления на 2. В программировании эта операция выполняется с помощью оператора взятия остатка (% или mod): если n % 2 == 0, то число чётное.

Проверка чётности в информатике и телекоммуникациях

В цифровых системах проверка чётности (parity check) используется для обнаружения однократных ошибок в блоках данных. Метод основан на добавлении к передаваемому блоку одного дополнительного бита — бита чётности (parity bit). Значение этого бита выбирается таким образом, чтобы общее количество единиц в блоке (включая сам бит чётности) было чётным (чётная чётность, even parity) или нечётным (нечётная чётность, odd parity).

Принцип работы

1. Передатчик: подсчитывает количество единичных битов в передаваемом блоке данных (например, в байте). Если используется чётная чётность, и количество единиц чётно, бит чётности устанавливается в 0; если нечётно — в 1. Для нечётной чётности — наоборот.
2. Приёмник: после получения блока данных (включая бит чётности) снова подсчитывает количество единиц. Если оно не соответствует ожидаемому (чётное/нечётное), фиксируется ошибка.

Пример

Пусть передаётся байт данных 10110010 (четыре единицы). Для чётной чётности бит чётности будет равен 0 (общее количество единиц — 4, чётно). Передаётся последовательность 101100100. Если при передаче один бит изменится, например, третий бит слева станет 0, то приёмник получит 100100100 (три единицы). При проверке чётной чётности обнаружит несоответствие (три единицы — нечётно) и зафиксирует ошибку.

Ограничения

• Обнаружение только нечётного числа ошибок: если в блоке данных исказится чётное количество бит (например, два), то бит чётности останется верным, и ошибка не будет обнаружена.
• Невозможность исправления ошибки: метод указывает на наличие ошибки, но не определяет, какой именно бит был искажён.
• Не защищает от ошибок в самом бите чётности: искажение бита чётности также приведёт к ложному срабатыванию.

Виды и применение

• Вертикальная проверка чётности (VRC): применяется к каждому байту или символу. Используется в асинхронной последовательной передаче (например, в протоколах UART, RS-232).
• Продольная проверка чётности (LRC): вычисляется для всех байтов блока данных по каждому битовому столбцу. Позволяет обнаруживать некоторые типы групповых ошибок.
• Матричная проверка чётности: комбинация вертикальной и продольной проверок. В некоторых случаях позволяет не только обнаружить, но и локализовать однократную ошибку (на пересечении строки и столбца с неверной чётностью).

До появления более сложных кодов коррекции ошибок (например, кодов Хэмминга, CRC) проверка чётности была основным методом контроля целостности в оперативной памяти (память с контролем чётности), в магнитных лентах и ранних дисковых накопителях. В современных системах проверка чётности часто используется как часть более сложных схем (например, в RAID-массивах, где биты чётности позволяют восстанавливать данные при отказе одного диска).

Проверка чётности в криптографии

В криптографии проверка чётности может использоваться как часть некоторых алгоритмов. Например, в шифре Вернама (одноразовый блокнот) проверка чётности открытого текста и шифротекста может быть использована для атаки, если ключ не является истинно случайным. В асимметричной криптографии, в частности в алгоритме RSA, чётность зашифрованного сообщения может быть использована для атаки по выбранному шифротексту (атака Блехенбахера), что позволяет восстановить открытый текст.

Проверка чётности в электронике

В цифровых микросхемах проверка чётности реализуется с помощью логических элементов «исключающее ИЛИ» (XOR). Каскадное соединение элементов XOR позволяет подсчитать количество единиц в двоичной последовательности: если на выходе логическая единица, то количество единиц нечётно; если ноль — чётно. Такие схемы называются сумматорами по модулю 2 или генераторами/проверяльщиками чётности (parity generator/checker). Примеры микросхем: 74HC280 (9-битный генератор/проверяльщик чётности).

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

• В ранних персональных компьютерах (например, IBM PC/AT) память с контролем чётности была стандартом. При обнаружении ошибки система выдавала сообщение «Parity Error» и останавливалась. Позднее, для снижения стоимости, производители перешли на память без контроля чётности, полагаясь на более редкие ошибки.
• В некоторых протоколах (например, в CAN-шине) используется бит чётности для проверки кадра, но в сочетании с другими механизмами (CRC, бит-стаффинг).
• Проверка чётности лежит в основе более мощных кодов, таких как коды Хэмминга, которые могут исправлять однократные ошибки. Код Хэмминга использует несколько битов чётности для разных групп битов данных.

Источники

• Таненбаум Э., Уэзеролл Д. «Компьютерные сети». 5-е изд. — СПб.: Питер, 2012.
• Хэмминг Р. В. «Теория кодирования и теория информации». — М.: Радио и связь, 1983.
• ГОСТ 28147-89 «Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования».
• Intel 8251A Programmable Communication Interface Datasheet.
• Stallings W. «Cryptography and Network Security: Principles and Practice». 7th ed. — Pearson, 2017.