Бит чётности

Как считается бит чётности

Возьмите байт данных и посчитайте в нём единицы. При схеме чётной чётности (even parity) дополнительный бит выбирают так, чтобы общее число единиц вместе с ним стало чётным; при нечётной (odd parity) — нечётным. Байт 1011001 содержит четыре единицы: при чётной схеме бит чётности равен 0, при нечётной — 1.

Математически бит чётности — это XOR всех бит блока. Одна инструкция на любом процессоре, одна логическая схема из каскада элементов «исключающее ИЛИ» в железе. Дешевле механизма контроля не существует в принципе, и в этом вся его ценность: он появился тогда, когда каждый транзистор был на счету, и по той же причине выжил в микроконтроллерах.

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

Что ловится, а что проскакивает

Формально расстояние Хэмминга между любыми двумя корректными кодовыми словами при такой схеме равно 2. Отсюда прямое следствие: обнаруживается одна ошибка, исправляется ноль. Общее правило кодирования гласит, что для обнаружения d ошибок нужно кодовое расстояние d + 1, а для исправления — 2d + 1. Бит чётности стоит на нижней ступени этой лестницы.

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

Есть приём, который выжимает из чётности больше, — двумерная схема. Данные раскладывают в матрицу, считают чётность по каждой строке и по каждому столбцу. Тогда одиночная ошибка выдаёт себя сразу двумя несовпадениями: номер сбойной строки и номер сбойного столбца дают точную координату бита, и его достаточно перевернуть. Получается уже корректирующий код, хотя и с большой избыточностью. Ровно эта идея, доведённая до ума через пересекающиеся проверочные группы, превратилась в код Хэмминга.

Где бит чётности встречается

Последовательный порт. Формат вида 8N1 или 7E1 в настройках COM-порта расшифровывается как «8 бит данных, без чётности, 1 стоп-бит» и «7 бит данных, чётная чётность, 1 стоп-бит». Второй вариант — наследие эпохи, когда ASCII занимал ровно 7 бит, а восьмой оставался свободным именно под контроль. Промышленные весы, сканеры и кассовые принтеры до сих пор настраиваются этими строчками.

Оперативная память. Серверные модули с ECC несут больше одного контрольного бита, но исторически первыми были именно модули с чётностью — 9 микросхем вместо 8. Современный ECC на схеме SEC-DED хранит 8 проверочных бит на 64 бита данных и умеет исправлять одиночную ошибку и обнаруживать двойную.

Дисковые массивы. RAID 5 хранит блок чётности, посчитанный XOR по всем дискам полосы. При отказе одного диска утраченные данные восстанавливаются тем же XOR — это тот же бит чётности, только применённый к целым блокам, а не к битам внутри байта.

Штриховые и двумерные коды пошли другим путём. В линейных символиках роль контроля играет контрольная цифра по модулю: у EAN-13 это взвешенная сумма с коэффициентами 1 и 3, у Code 39 — контроль по модулю 43. Логику такой проверки разбирает термин контрольная цифра штрих-кода. В QR-кодах избыточность построена на кодах Рида — Соломона и задаётся уровнями коррекции L, M, Q и H, потому что печатному коду нужна не сигнализация об ошибке, а реальное восстановление данных под грязью и царапинами.

Чётность в общей картине методов контроля

Разложите методы по стоимости и возможностям, и место чётности станет очевидным. Один бит на байт (12,5% избыточности) — обнаружение одиночной ошибки. Три проверочных бита на четыре информационных в коде Хэмминга (75% избыточности) — исправление одной ошибки. Тридцать два бита CRC на кадр в 1500 байт (0,3% избыточности) — обнаружение любых пакетов до 32 бит. Тридцать два байта SHA-256 — криптографическая гарантия, что данные не подменил человек, а не только шум.

Ни один из методов не заменяет другие: они решают разные задачи и стоят разного. Чётность годится там, где канал короткий, ошибки редки и одиночны, а протокол умеет запросить повтор. Как только появляется злоумышленник, вся эта арифметика перестаёт работать, и нужен криптографический хеш SHA-256 или электронная подпись. Выбор между этими уровнями сводится к тому, сколько избыточности данных вы готовы добавить к полезной нагрузке, а сама двоичная арифметика держится на одном-единственном бите.

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

Чётная или нечётная чётность лучше?

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

Может ли бит чётности исправить ошибку?

Сам по себе нет — он сообщает только факт искажения, но не его позицию. Исправление появляется, когда проверочных бит несколько и их проверочные группы пересекаются: тогда набор несовпадений однозначно указывает на сбойный бит. Это и есть код Хэмминга. Другой вариант — двумерная чётность по строкам и столбцам, где пересечение сбойной строки и сбойного столбца даёт координату бита.

Почему в настройках COM-порта чаще всего стоит 8N1?

Потому что современные протоколы поверх последовательного порта несут собственную проверку — CRC в Modbus RTU, контрольные суммы в фирменных протоколах кассового оборудования. Дублировать её битом чётности незачем: он отъедает пропускную способность и всё равно ловит меньше. Чётность оставляют там, где протокол верхнего уровня примитивен и своей проверки не имеет.

Используется ли чётность в QR-кодах?

Нет, в явном виде не используется. Данные защищены кодами Рида — Соломона, служебные поля — кодами BCH, а маска выбирается по штрафным очкам за неудачные визуальные шаблоны. Причина в задаче: печатный код сканируется однократно, повторную передачу запросить не у кого, поэтому нужна не сигнализация об ошибке, а восстановление до 30% символов при уровне H.

Насколько чётность увеличивает объём данных?

При схеме «один бит на байт» избыточность составляет 12,5%: на восемь информационных бит приходится девять переданных. Для сравнения, CRC-32 на килобайтном кадре добавляет около 0,4%, а уровень коррекции H в QR-коде тратит на избыточность примерно 30% ёмкости символа. Чётность дешева в вычислениях, но по объёму на длинных блоках она неэффективна.