Бит чётности и контрольная сумма

Урок о том, как один лишний бит и простое сложение помогают заметить, что данные исказились по дороге.

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

Зачем это нужно

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

Идея простая: пусть честный набор данных подчиняется некоторому условию. Тогда после ошибки условие нарушится, и приёмник это увидит. Чем «строже» условие, тем больше ошибок оно ловит — но и тем больше лишних битов нужно передавать. Это всегда компромисс между надёжностью и накладными расходами.

Бит чётности

Самый дешёвый способ обнаружения — добавить к группе битов ровно один контрольный, бит чётности (parity bit). Его выбирают так, чтобы общее число единиц во всей группе (вместе с контрольным битом) было чётным. Это называют чётной чётностью (even parity).

Пусть передаём байт 1011001 (семь информационных бит). Считаем единицы: их 4 — уже чётно. Значит, бит чётности равен 0, и в канал уходит 1011001 0. А для 1100001 единиц три — нечётно, поэтому бит чётности равен 1, чтобы довести их число до четырёх: уходит 1100001 1.

Формально бит чётности — это сумма всех информационных бит по модулю 2, то есть результат операции «исключающее ИЛИ» (XOR) над ними:

$$ p = b_1 \oplus b_2 \oplus \dots \oplus b_n $$

где $\oplus$ — сложение по модулю 2 ($0\oplus 0=0$, $1\oplus 0=1$, $1\oplus 1=0$). На приёмной стороне считают XOR уже всех бит вместе с контрольным. Если ошибок не было, результат равен нулю:

$$ b_1 \oplus \dots \oplus b_n \oplus p = 0 $$

Если же ровно один бит «перевернулся», сумма единиц изменит чётность, и XOR даст 1 — сигнал тревоги.

Что бит чётности умеет и чего не умеет

Бит чётности обнаруживает любое нечётное число ошибок (одну, три, пять...). Но он не видит чётное число ошибок: если перевернулись сразу два бита, число единиц снова станет чётным, и проверка пройдёт как ни в чём не бывало. И даже обнаружив ошибку, бит чётности не знает, какой именно бит испортился, — исправить он ничего не может. Это инструмент только обнаружения.

Контрольная сумма пакета

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

В простейшем варианте берут сумму байтов по модулю 256 (то есть младший байт обычной суммы):

$$ S = \left( \sum_{i=1}^{n} B_i \right) \bmod 256 $$

Разберём на числах. Пусть пакет — это байты 200, 100, 50. Их сумма равна 350, а $350 \bmod 256 = 94$. Значит, контрольная сумма пакета равна 94, её и приписывают в конец. Если при передаче 100 превратится в 101, приёмник получит сумму 351, $351 \bmod 256 = 95 \neq 94$ — ошибка поймана.

Как это работает

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

Посчитаем оба отпечатка на рабочем Python: бит чётности байта и контрольную сумму пакета. XOR здесь — оператор ^, а взятие по модулю — %.

def parity_bit(bits):
    p = 0
    for b in bits:
        p ^= b          # накапливаем XOR всех бит
    return p

data = [1, 0, 1, 1, 0, 0, 1]   # семь информационных бит
p = parity_bit(data)
frame = data + [p]
print("Данные:", data)
print("Бит чётности:", p)
print("Кадр в канал:", frame)
print("Единиц в кадре:", sum(frame), "(должно быть чётным)")

# Контрольная сумма пакета по модулю 256
packet = [200, 100, 50]
checksum = sum(packet) % 256
print("\nПакет:", packet)
print("Сумма:", sum(packet))
print("Контрольная сумма:", checksum)

# Имитируем ошибку: 100 пришло как 101
bad = [200, 101, 50]
print("Сумма с ошибкой:", sum(bad) % 256, "-- не совпала, ошибка поймана")

Вывод:

Данные: [1, 0, 1, 1, 0, 0, 1]
Бит чётности: 0
Кадр в канал: [1, 0, 1, 1, 0, 0, 1, 0]
Единиц в кадре: 4 (должно быть чётным)

Пакет: [200, 100, 50]
Сумма: 350
Контрольная сумма: 94
Сумма с ошибкой: 95 -- не совпала, ошибка поймана

Частые ошибки

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

Итоги

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