Кодирование и декодирование
Кодирование — это переход от исходной информации к её представлению с помощью символов выбранного кода, а декодирование — обратное восстановление сообщения по известному коду. Тема опирается на понятие кода и помогает решать задачи, где нужно построить таблицу соответствий, закодировать слово или однозначно прочитать последовательность символов.
Что такое кодирование
Любая информация может быть представлена знаками. Например, слово можно записать буквами русского алфавита, азбукой Морзе, двоичными последовательностями или сигналами разной длительности. Набор исходных объектов называют исходным алфавитом, а набор символов, используемых для записи результата, — кодовым алфавитом. Подробнее о знаках и способах их использования см. знаковую систему и кодовый алфавит.
Кодирование — это применение заранее заданного правила, которое каждому исходному объекту или сообщению ставит в соответствие его кодовое представление. Исходный объект может быть буквой, цифрой, цветом, командой или целым сообщением.
Декодирование — восстановление исходного объекта или сообщения по его кодовому представлению и известному правилу кодирования.
Обычно отдельному исходному символу соответствует кодовое слово — последовательность символов кодового алфавита. Например, при кодировании букв символами 0 и 1 кодовое слово буквы А может быть 00, а буквы Б — 11. Важно заранее знать таблицу или правило: сама последовательность символов ещё не объясняет, что она означает.
Правило перехода от сообщения к коду
Чтобы закодировать сообщение, сначала определяют, какие исходные символы в нём встречаются, затем находят для каждого символа соответствующее кодовое слово и записывают кодовые слова подряд. Если разделители между словами кода не используются, границы кодовых слов должны быть понятны из самого кода или восстанавливаться по правилу декодирования.
| Исходный символ | Кодовое слово |
|---|---|
| А | 00 |
| Б | 01 |
| В | 10 |
| Г | 11 |
Для таблицы выше слово «АВГ» кодируется так: А заменяется на 00, В — на 10, Г — на 11. Получается последовательность 001011. Обратная замена выполняется блоками по два символа: 00|10|11.
Если сообщение состоит из символов \(a_1,a_2,\ldots,a_n\), а их кодовые слова равны \(c(a_1),c(a_2),\ldots,c(a_n)\), то код сообщения получают конкатенацией: кодовые слова записывают подряд без изменения порядка.
Декодирование и однозначность
При декодировании нужно разделить полученную последовательность на кодовые слова, а затем заменить каждое слово исходным символом. Если длина всех кодовых слов одинакова, границы находятся легко: последовательность делят на блоки известной длины. Если длины различны, требуется дополнительное свойство кода или специальный алгоритм декодирования.
Код обладает однозначным декодированием, если любая допустимая кодовая последовательность может быть восстановлена не более чем одним исходным сообщением. Иначе одна и та же последовательность может иметь несколько расшифровок.
Например, пусть А кодируется как 0, а Б — как 01. Последовательность 01 можно прочитать как Б или как ААА? В данном наборе ААА даёт 000, поэтому не подходит; однако при добавлении символа В с кодом 1 последовательность 01 можно прочитать как АВ или Б. Такой код неоднозначен. Подробные условия и примеры рассмотрены на странице «Однозначность декодирования».
Код называется префиксным, если ни одно кодовое слово не является началом другого кодового слова. В таком коде последовательность можно читать слева направо: как только кодовое слово закончено, его граница однозначна. Это частный и удобный способ обеспечить однозначное декодирование; см. префиксный код.
В таблице А = 10, Б = 0, В = 11. Как закодировать слово «АБВ»?
Разобранный пример
Дана таблица: А = 1, Б = 01, В = 001, Г = 000. Закодируем слово «АВБ», а затем декодируем последовательность 0010101.
В этом примере кодовые слова имеют разную длину, но чтение слева направо возможно благодаря их структуре: ни одно слово не является префиксом другого. Например, после первого символа 0 нельзя остановиться, потому что кодового слова 0 нет; нужно продолжать чтение до 001, 01 или 000.
Длина кода и количество вариантов
Если кодовый алфавит содержит \(k\) символов, то количество кодовых слов длины \(n\) равно \(k^n\). Для двоичного кода (\(k=2\)) длины 3 существуют \(2^3=8\) различных слов: 000, 001, 010, 011, 100, 101, 110, 111.
Если все кодовые слова имеют одинаковую длину \(n\), то кодом можно представить не более \(k^n\) различных исходных символов. Поэтому для \(M\) объектов необходимо, чтобы \(k^n\ge M\). Минимальную длину фиксированного кода находят подбором наименьшего целого \(n\), удовлетворяющего этому неравенству.
Для кодирования \(M\) различных объектов кодовым алфавитом из \(k\) символов минимальная одинаковая длина кодового слова — наименьшее целое \(n\), для которого \(k^n\ge M\).
Например, для 10 цифр при двоичном кодировании: \(2^3=8<10\), а \(2^4=16\ge10\), значит, нужно не менее 4 бит на цифру. Часть из 16 возможных комбинаций останется неиспользованной.
Как решать экзаменационные задачи
- Выпишите исходный алфавит и кодовый алфавит.
- Составьте или внимательно прочитайте таблицу соответствий.
- Для кодирования заменяйте символы по одному и соединяйте результаты.
- Для декодирования найдите границы кодовых слов; при равной длине разбивайте строку на блоки.
- Проверьте длину результата, порядок символов и отсутствие лишних знаков.
1. Путают направление: кодирование идёт от сообщения к коду, декодирование — обратно. 2. Меняют порядок кодовых слов. 3. Теряют начальные нули: 001 нельзя автоматически превращать в 1. 4. Делят строку на блоки одинаковой длины, хотя длины кодовых слов различны. 5. Считают \(k\cdot n\) вместо \(k^n\) при подсчёте количества комбинаций. 6. Используют таблицу наоборот: если А = 101, это не означает, что 101 = любая буква без проверки.
После кодирования декодируйте полученную последовательность обратно. Если исходное сообщение восстановилось точно, порядок замен и границы кодовых слов, скорее всего, определены верно.
Связь с таблицами и деревьями кодирования
В простых задачах правило записывают в таблице кодирования. Для двоичных кодов с разной длиной удобно изображать последовательность выбора символов в дереве кодирования: движение влево может означать 0, а вправо — 1. Такой рисунок помогает увидеть, где заканчивается кодовое слово и почему некоторые коды нельзя помещать один внутрь другого.
Кодирование может быть равномерным, когда все кодовые слова имеют одну длину, или неравномерным, когда длины различаются. Равномерный код проще декодировать, а неравномерный иногда позволяет сократить среднюю длину сообщений, но требует внимательной проверки однозначности.
Проверь себя
Главное
- Кодирование переводит исходное сообщение в код, а декодирование восстанавливает сообщение.
- Кодовое слово соответствует исходному символу или объекту; код сообщения получают соединением кодовых слов.
- При одинаковой длине кодовых слов последовательность делят на равные блоки.
- Однозначность означает, что кодовая последовательность имеет не более одной расшифровки; префиксный код удобно декодировать слева направо.
- Количество слов длины \(n\) в алфавите из \(k\) символов равно \(k^n\).