Кодирование и декодирование сообщений

Кодирование и обратная задача

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

Простейший способ кодирования — заменять каждый символ сообщения его условным обозначением: числом, набором символов или другой буквой. Именно так устроены и шифр Цезаря, и азбука Морзе, и компьютерные кодировки символов, с которыми вы уже знакомы.

Пример таблицы кодирования

Разбор примера

Закодируем слово «ВАГ» по таблице выше, заменяя каждую букву соответствующим ей числовым кодом по порядку.

Декодирование выполняется в обратную сторону по той же таблице: каждому коду сопоставляется буква. Например, последовательность кодов 2 1 2 по нашей таблице превращается в слово «БАБ». Если бы таблица была другой, то и расшифровка получилась бы иной — поэтому ключ так важен.

Условие однозначности

Правило Фано. Чтобы код читался однозначно даже без разделителей между символами, ни одно кодовое слово не должно быть началом другого кодового слова. Если это условие нарушено, то одну и ту же цепочку можно прочитать по-разному.

Например, если букву А закодировать как 1, а букву Б как 11, то цепочку 11 можно прочитать и как «АА» (два раза по одному), и как «Б» (одно слово из двух единиц). Это и есть нарушение однозначности. Чтобы его избежать, либо вводят разделители, либо подбирают коды так, чтобы выполнялось условие Фано.

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

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

Равномерные и неравномерные коды

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

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

Кратко о главном

• Кодирование переводит сообщение в код по таблице соответствия.
• Декодирование восстанавливает исходное сообщение из кода.
• Ключ (таблица) должен быть общим для отправителя и получателя.
• Условие Фано обеспечивает однозначность чтения кода без разделителей.