Бит чётности

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

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

Бит чётности добавляется к блоку данных (обычно к байту или слову) перед передачей или записью. Алгоритм его вычисления основан на подсчёте количества единичных битов в исходных данных.

Чётная чётность (Even Parity)

При использовании чётной чётности значение бита чётности устанавливается равным 0, если количество единиц в исходных данных уже чётное. Если количество единиц нечётное, бит чётности устанавливается в 1, чтобы общее количество единиц в блоке (данные + бит чётности) стало чётным.

Пример: Исходные данные: 1011 (три единицы — нечётное количество). Бит чётности: 1 (добавляем, чтобы стало 4 единицы — чётное). Результирующий блок: 10111.

Нечётная чётность (Odd Parity)

При нечётной чётности бит чётности устанавливается так, чтобы общее количество единиц в блоке было нечётным. Если в исходных данных количество единиц нечётное, бит чётности равен 0; если чётное — бит чётности равен 1.

Пример: Исходные данные: 1011 (три единицы — нечётное). Бит чётности: 0 (оставляем нечётное количество — 3 единицы). Результирующий блок: 10110.

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

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

Ограничения:

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

История

Концепция контроля чётности восходит к ранним этапам развития цифровых вычислительных машин и телекоммуникаций. Одним из первых применений стало использование перфолент и перфокарт в середине XX века.

Перфоленты и перфокарты

На перфолентах данные кодировались наличием или отсутствием отверстий в определённых позициях. Для повышения надёжности считывания часто использовалась проверка чётности. Например, в 7-битной кодировке ASCII на перфоленте восьмая дорожка часто отводилась под бит чётности. Если механизм считывания обнаруживал нарушение чётности, это могло указывать на износ ленты, загрязнение считывающей головки или ошибку в записи.

Развитие в компьютерной памяти

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

Современное состояние

В современных компьютерах бит чётности в оперативной памяти был в значительной степени вытеснен более совершенными методами коррекции ошибок, такими как ECC (Error-Correcting Code) память, которая может не только обнаруживать, но и исправлять однобитовые ошибки. Однако бит чётности продолжает широко применяться в:

• Интерфейсах передачи данных: UART (асинхронный последовательный интерфейс), RS-232, SPI (в некоторых реализациях).
• Протоколах связи: Modbus, CAN bus, некоторые варианты Ethernet.
• Системах хранения данных: RAID-массивы (RAID 3, RAID 4, RAID 5 используют бит чётности для восстановления данных при отказе одного диска, хотя это уже более сложная форма, чем простой бит чётности).
• Простых микроконтроллерах и встраиваемых системах, где вычислительные ресурсы ограничены.

Классификация

Бит чётности можно классифицировать по нескольким признакам:

По типу чётности

• Чётная чётность (Even Parity): Общее количество единиц в блоке (данные + бит чётности) чётное.
• Нечётная чётность (Odd Parity): Общее количество единиц в блоке нечётное.
• Нет чётности (No Parity): Бит чётности не используется. В этом случае его место может быть занято другим битом данных или быть фиксированным (например, всегда 0 или 1).

По положению в кадре данных

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

По способу вычисления

• Простой бит чётности: Вычисляется как XOR (исключающее ИЛИ) всех битов данных. Результат XOR равен 1, если количество единиц нечётное, и 0, если чётное. Это и есть бит чётности для чётной чётности.
• Инверсный бит чётности: Используется для нечётной чётности. Вычисляется как инверсия XOR всех битов данных.

Применение

Последовательные интерфейсы (UART)

В протоколе UART (Universal Asynchronous Receiver-Transmitter) бит чётности является опциональным. Он входит в состав кадра данных, который обычно выглядит так: стартовый бит, 5-9 битов данных, опциональный бит чётности, 1-2 стоп-бита. Приёмник проверяет чётность и может сигнализировать об ошибке.

Память с контролем чётности

В некоторых типах оперативной памяти (например, SIMM и DIMM с поддержкой чётности) каждый 8-битный байт дополняется 1 битом чётности. Такая память называется «память с чётностью» (parity memory). Она дороже обычной, но обеспечивает базовую защиту от ошибок. Однако, в отличие от ECC, она не может исправить ошибку.

RAID-массивы

В RAID-массивах (Redundant Array of Independent Disks) бит чётности используется для обеспечения избыточности. Например, в RAID 5 данные и биты чётности распределяются по всем дискам массива. При отказе одного диска данные могут быть восстановлены с помощью информации о чётности, хранящейся на остальных дисках. Это более сложная форма, чем простой бит чётности, так как она работает с блоками данных, а не с отдельными байтами.

Коды Хэмминга

Код Хэмминга является расширением идеи бита чётности. Он использует несколько контрольных битов, каждый из которых проверяет чётность определённой группы битов данных. Это позволяет не только обнаруживать, но и исправлять однобитовые ошибки. Например, код Хэмминга (7,4) использует 3 контрольных бита для 4 битов данных.

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

• В ранних компьютерах, таких как IBM System/360, контроль чётности был обязательным для всех операций ввода-вывода и памяти.
• В некоторых протоколах (например, в модемах) использовалась не только чётность, но и «маркерная чётность» (mark parity) и «пробельная чётность» (space parity), когда бит чётности всегда был равен 1 или 0 соответственно. Это использовалось для синхронизации или идентификации кадров.
• Бит чётности является одним из немногих методов помехоустойчивого кодирования, который может быть реализован аппаратно с минимальными затратами (всего несколько логических вентилей).

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

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

Источники

• Таненбаум Э., Уэзеролл Д. «Компьютерные сети». 5-е издание. — СПб.: Питер, 2012.
• Хэмминг Р. В. «Теория кодирования и теория информации». — М.: Радио и связь, 1983.
• Stallings W. «Computer Organization and Architecture: Designing for Performance». 10th Edition. — Pearson, 2015.
• Документация к микроконтроллерам AVR (Atmel) и STM32 (STMicroelectronics) — разделы, посвящённые UART и контролю чётности.
• Стандарт RS-232 (EIA/TIA-232).