Кодирование и помехоустойчивость

Кодирование: как информация превращается в символы

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

Кодирование — это представление информации с помощью условных знаков. Например, буквы можно заменить числами, изображение — набором пикселей, а звук — последовательностью чисел. В компьютере почти любые данные хранятся в двоичном виде, то есть с помощью 0 и 1.

Один двоичный разряд называется битом. Он может принимать два значения: 0 или 1. Восемь битов образуют байт. Если используется код фиксированной длины из n битов, то с его помощью можно записать 2ⁿ разных комбинаций.

1 бит → 2 комбинации: 0, 1
2 бита → 2² = 4 комбинации
3 бита → 2³ = 8 комбинаций
1 байт = 8 битов → 2⁸ = 256 комбинаций

Эта связь помогает решать обратные задачи: если нужно закодировать N вариантов, ищи наименьшее n, для которого 2ⁿ ≥ N. Потренироваться на похожих вопросах можно в бесплатной практике в личном кабинете.

Двоичный код и информационный объём

В школьных задачах встречаются два близких, но разных вопроса. Первый: сколько комбинаций можно получить при заданной длине кода. Второй: сколько разрядов потребуется для заданного числа объектов. Не смешивай их: в первом случае вычисляем 2ⁿ, во втором подбираем минимальное n.

Если все кодовые слова имеют одинаковую длину, код называют равномерным. Например, для 10 цифр нужен код длиной 4 бита, потому что 2³ = 8 недостаточно, а 2⁴ = 16 достаточно. Шесть комбинаций останутся неиспользованными, но это не ошибка: код просто содержит запас.

Когда алфавит содержит 32 символа, достаточно 5 битов: 2⁵ = 32. Для 33 символов уже потребуется 6 битов, поскольку 2⁵ < 33 ≤ 2⁶.

Алгоритм:
1. Определи количество вариантов N.
2. Подбери такое n, чтобы 2ⁿ ≥ N.
3. Проверь, что число меньшей степени двойки недостаточно.

Избыточный код и защита от ошибок

При передаче данных по сети или хранении на носителе символы могут измениться из-за помех. Например, вместо 0 возникнет 1. Если код использует только необходимые комбинации, получатель не узнает, была ли ошибка. Поэтому добавляют избыточность — дополнительные разряды, которые помогают обнаружить или исправить искажение.

Простейший пример — повторение каждого бита три раза. Тогда 0 записывается как 000, а 1 — как 111. Если один разряд испортился, большинство позволяет восстановить исходное значение: 010 читается как 0, а 101 — как 1. Цена такой защиты — увеличение объёма сообщения.

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

Способ	Идея	Что даёт
Повторение	Один бит передаётся несколько раз	Можно исправить одиночную ошибку
Бит чётности	Добавляется контроль единиц	Можно обнаружить часть ошибок
Контрольная сумма	Проверяется итоговое значение блока	Помогает выявить искажение данных

Расстояние между кодами и помехоустойчивость

Чтобы сравнивать устойчивость кодов, используют расстояние Хэмминга — количество позиций, в которых два кодовых слова различаются. Например, слова 10110 и 10011 отличаются в двух позициях, значит расстояние равно 2.

Минимальное расстояние между любыми двумя разрешёнными словами обозначают d. Если d = 1, одиночную ошибку надёжно обнаружить нельзя: изменённое слово может оказаться другим разрешённым словом. При d ≥ 2 любая одиночная ошибка переводит слово в запрещённую комбинацию, поэтому её можно обнаружить.

Для исправления ошибок требования строже. Код с минимальным расстоянием d может исправить не более чем ⌊(d − 1) ÷ 2⌋ ошибок. В школьных задачах часто достаточно запомнить идею: чем дальше разрешённые слова друг от друга, тем больше искажений код способен пережить.

d = 3 → обнаружение до 2 ошибок и исправление 1 ошибки
d = 4 → обнаружение до 3 ошибок и исправление 1 ошибки
Формула исправления: t = ⌊(d − 1) ÷ 2⌋

Разобранный пример и типичные ошибки

Решим задачу: нужно закодировать 20 различных символов равномерным двоичным кодом. Затем определим, что произойдёт, если к каждому биту добавить контрольный бит чётности.

Дано: N = 20 символов.
Ищем минимальное n: 2ⁿ ≥ 20.
2⁴ = 16 < 20, значит 4 битов недостаточно.
2⁵ = 32 ≥ 20, значит n = 5 битов.
Для 20 символов достаточно 5-битных кодовых слов.
Если к каждому слову добавить 1 бит чётности, длина станет 5 + 1 = 6 битов.
Ответ: 5 битов без проверки, 6 битов с битом чётности.

Первая частая ошибка — использовать 20 битов, будто один бит кодирует один символ. На самом деле комбинации строятся из всех разрядов сразу. Вторая — выбрать 4 бита только потому, что число 4 меньше 20. Нужно сравнивать степени двойки. Третья — считать, что контрольный бит увеличивает число исходных символов: он увеличивает длину сообщения, но не число кодируемых вариантов.

Если хочется закрепить именно такие алгоритмы, реши несколько заданий в личном кабинете с бесплатной практикой, а затем сравни ход решения с разбором.

Что запомнить

Бит принимает два значения, байт содержит 8 битов, а n битов дают 2ⁿ комбинаций. Для N вариантов выбирай минимальное n, при котором 2ⁿ ≥ N. Избыточность добавляют не ради увеличения сообщения, а чтобы обнаружить или исправить ошибки. Бит чётности помогает обнаружить часть искажений, а расстояние Хэмминга показывает запас прочности кода.

В задаче сначала выпиши, что кодируется: символы, сообщения или уже передаваемые разряды. Затем определи длину кодового слова, сравни степени двойки и только после этого учитывай проверочные биты. Такой порядок сокращает число случайных ошибок.

Следующий шаг: зарегистрируйся и реши 5 заданий бесплатно в личном кабинете. Если готовишься к экзамену, полезно также посмотреть подборки по ОГЭ или ЕГЭ, где похожие идеи встречаются в разных формулировках.