26. Продолжаем кодировать

Определения и обозначения

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

Декодирование — восстановление исходного сообщения по его коду. При этом кодовые обозначения заменяют исходными символами, пользуясь тем же правилом, что и при кодировании. Это нужно, чтобы получатель мог прочитать сообщение в привычном виде. Если правило применить неверно, результат может отличаться от исходного.

Кодовая таблица — правило соответствия символов исходного сообщения и кодовых обозначений. В ней напротив каждого символа записан его код, например букве «А» может соответствовать 00. Таблица нужна, чтобы кодировать и декодировать сообщения одинаково. При работе важно смотреть, в каком направлении выполняется замена.

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

Как это устроено

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

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

Кодирование и декодирование взаимно обратны, поскольку первое заменяет символы кодами, а второе выполняет соответствующие замены в обратную сторону. Если таблица и границы кодов известны, после декодирования можно получить исходную последовательность символов. Это работает только при точном соблюдении одного правила на обоих этапах. Иначе часть кодов может быть понята неправильно, и сообщение изменится.

Каждый двоичный разряд может принимать два значения: 0 или 1. Поэтому один разряд даёт 2 комбинации, два разряда — 4, три — 8; при n разрядах их число равно 2ⁿ. Чтобы выбрать длину равномерного кода для алфавита, сравнивают число его символов с числом доступных комбинаций. Берут наименьшее n, при котором комбинаций хватает на все символы.

Код должен позволять однозначно восстановить исходное сообщение, иначе одна и та же последовательность кодов может читаться по-разному. Например, при кодах разной длины начало одного кода может совпасть с другим целым кодом, и границы символов станут неясны. Тогда даже правильная таблица не поможет однозначно прочитать запись. Поэтому при выборе кода проверяют не только число комбинаций, но и возможность определить, где заканчивается каждый код.

Сравнение способов кодирования

Сравнивайте сначала длину комбинаций, а затем выясняйте, как получатель определяет границы кодов. Равномерный код удобно читать по группам одинакового размера, тогда как для неравномерного требуется правило, исключающее двусмысленность. Преимущество каждого способа проявляется в зависимости от задачи.

Разбор задач

Кодируем слово по таблице

Условие: в таблице А = 00, Б = 01, В = 10, Г = 11. Закодируйте слово «БАГ». Слово состоит из трёх символов, и для каждого нужно найти отдельную комбинацию. Коды в результате следует записать в исходном порядке.

1. Первый символ — Б, по таблице ему соответствует 01.
2. Второй символ — А, его код равен 00.
3. Третий символ — Г, для него записываем 11.
4. Соединяем комбинации в том же порядке: 01, затем 00, затем 11.

Ответ: слову «БАГ» соответствует последовательность 010011. При проверке можно разделить запись на группы по два разряда и сопоставить их таблице в обратном направлении. Так восстанавливается исходное слово.

Выбираем длину равномерного кода

Условие: нужно закодировать алфавит из 10 символов равномерным двоичным кодом. Требуется найти минимальное число разрядов на один символ. Для n разрядов доступно 2ⁿ разных комбинаций, поэтому проверяем длины по возрастанию.

1. При одном разряде доступно 2¹ = 2 комбинации, этого недостаточно.
2. При двух разрядах их 2² = 4, а при трёх — 2³ = 8; оба варианта меньше 10.
3. При четырёх разрядах получаем 2⁴ = 16 комбинаций, значит, их хватает на все символы.
4. Меньшая длина не подходит, поэтому четыре разряда — минимальный вариант.

Ответ: каждому символу нужно назначить четырёхразрядный код. Шесть комбинаций останутся свободными, но это не мешает кодированию алфавита. Проверка состоит в сравнении числа символов с 2ⁿ.

Декодируем последовательность

Условие: кодовая таблица задаёт А = 0, Б = 10, В = 11. Декодируйте последовательность 01011 и объясните, почему иной вариант невозможен. Здесь длины кодов различаются, поэтому нельзя просто разбить запись на одинаковые группы. Нужно последовательно проверить, какой код начинается с очередного разряда.

1. В начале стоит 0, а это полный код буквы А, поэтому читаем А и переходим к оставшейся части.
2. После удаления первого разряда остаётся 1011. Она начинается с кода 10, то есть с буквы Б.
3. После удаления 10 остаётся 11, это код буквы В.
4. Получается разбиение 0 | 10 | 11; проверяем, можно ли начать запись иначе.

Ответ: последовательность декодируется как «АБВ». Другой вариант невозможен, потому что ни один код не начинается с 0, кроме кода А, а после него остаток также однозначно делится на 10 и 11. Если бы кодовая таблица допускала несколько разбиений, однозначно восстановить сообщение было бы нельзя.

Типичные ошибки

Кодирование путают с шифрованием, потому что в обоих случаях запись сообщения меняется. Но кодирование выполняют по правилу, которое предназначено для преобразования формы, а шифрование скрывает содержание. Проверить себя можно вопросом: нужно ли скрыть смысл от посторонних или лишь представить данные иначе? Во втором случае речь идёт о кодировании.

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

Некоторые считают, что n двоичных разрядов дают n вариантов. Ошибка возникает из-за смешения числа разрядов с числом комбинаций: каждый разряд имеет два значения, поэтому комбинации образуются всеми сочетаниями нулей и единиц. Проверка — посчитать их для первых случаев: 1 разряд даёт 2, 2 — 4, 3 — 8. Общая формула — 2ⁿ.

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

Связь с другими темами

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

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

• Кодирование преобразует исходное сообщение в код.
• Декодирование восстанавливает сообщение по коду.
• Кодовая таблица задаёт соответствие между символами и кодами.
• Двоичный код использует только 0 и 1.
• n двоичных разрядов позволяют получить 2ⁿ комбинаций.
• Хороший код должен обеспечивать однозначное декодирование.
• При работе с кодом нужно соблюдать одно и то же правило на всех этапах.