Код с проверкой на чётность¶

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

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

Основная идея кода с проверкой на чётность заключается во введении избыточности. Исходное сообщение, состоящее из k информационных бит, преобразуется в кодовое слово длиной n = k + 1 бит. Дополнительный бит, называемый битом чётности (parity bit), вычисляется по определённому правилу и добавляется в конец или в начало блока.

¶Чётная и нечётная чётность

Существует два основных варианта кода:

• Чётная чётность (even parity): бит чётности устанавливается таким образом, чтобы общее количество единиц в кодовом слове (включая сам бит чётности) было чётным. Если в исходных данных число единиц уже чётное, бит чётности равен 0; если нечётное — бит чётности равен 1.
• Нечётная чётность (odd parity): бит чётности устанавливается так, чтобы общее количество единиц в кодовом слове было нечётным. Если в исходных данных число единиц чётное, бит чётности равен 1; если нечётное — бит чётности равен 0.

Выбор между чётной и нечётной чётностью зависит от конкретной реализации и стандарта. Например, в асинхронном последовательном интерфейсе RS-232 часто используется нечётная чётность, а в некоторых системах памяти — чётная.

¶Пример кодирования

Рассмотрим передачу 8-битного байта данных 10110010. Количество единиц в нём равно 4 (чётное).

• Для чётной чётности бит чётности будет равен 0, так как число единиц уже чётное. Кодовое слово: 101100100.
• Для нечётной чётности бит чётности будет равен 1, чтобы сделать общее число единиц нечётным (5). Кодовое слово: 101100101.

¶Обнаружение ошибок

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

¶Возможности и ограничения

• Обнаруживает: любое нечётное количество ошибок (1, 3, 5 и т.д.) в одном кодовом слове.
• Не обнаруживает: чётное количество ошибок (2, 4, 6 и т.д.), так как при этом чётность блока не изменяется.
• Не исправляет: код с проверкой на чётность не позволяет определить, какой именно бит был искажён, а только сигнализирует о наличии ошибки. Для исправления ошибок требуются более сложные коды (например, коды Хэмминга).

¶История

Идея использования избыточного бита для контроля целостности данных восходит к ранним этапам развития вычислительной техники и телеграфии. Одним из первых практических применений стала система с перфолентами, где для обнаружения сбоев при считывании использовался контрольный бит. В 1940-х годах Ричард Хэмминг, работая в Bell Labs, разработал более совершенные коды, исправляющие ошибки, но простейший код с проверкой на чётность остаётся фундаментальным элементом теории кодирования.

¶Применение

Код с проверкой на чётность используется в различных областях, где требуется простой и быстрый контроль целостности данных:

• Последовательные интерфейсы: UART, RS-232, SPI (опционально) — для обнаружения ошибок при передаче байтов.
• Память компьютеров: в модулях оперативной памяти (RAM) с контролем чётности (parity RAM) — для обнаружения одиночных ошибок. В современных системах часто заменяется кодами коррекции ошибок (ECC).
• Системы хранения данных: в некоторых форматах записи на магнитные ленты и диски (например, RAID 3, 4, 5 используют контрольные суммы, но не бит чётности в чистом виде; однако принцип контроля чётности лежит в основе вычисления XOR-сумм в RAID-массивах).
• Сетевые протоколы: в некоторых простых протоколах (например, в протоколе передачи файлов XMODEM) используется контрольная сумма, но бит чётности мог применяться в более ранних версиях.
• Телеграфия и телетайпы: для обнаружения ошибок при передаче кода Бодо и других кодов.

¶Критика

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

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

• В некоторых ранних компьютерах, например в IBM 1620, использовалась десятичная арифметика с проверкой на чётность для каждой десятичной цифры, представленной в двоично-десятичном коде.
• Принцип контроля чётности лежит в основе вычисления XOR-сумм, которые используются в RAID-массивах для восстановления данных при отказе одного диска. В RAID 5, например, блок данных на каждом диске вычисляется как XOR блоков на остальных дисках, что позволяет восстановить информацию при выходе из строя одного диска.

¶Источники

• Хэмминг Р. В. Теория кодирования и теория информации. — М.: Радио и связь, 1983.
• Скляр Б. Цифровая связь. Теоретические основы и практическое применение. — М.: Вильямс, 2003.
• Таненбаум Э., Уэзеролл Д. Компьютерные сети. — 5-е изд. — СПб.: Питер, 2012.
• ГОСТ 34.10-2018. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи (раздел, посвящённый контрольным суммам).