Кодирование и декодирование информации

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

«По каналу связи передаются сообщения из букв А, Б, В, Г, Д. Используется двоичный код, удовлетворяющий условию Фано; известны коды А — 0, Б — 10, В — 110. Укажи кратчайший код буквы Г, если код буквы Д тоже должен существовать».

Все такие задачи решаются одним рисунком — деревом кодов: на нём видно, какие коды заняты и где осталось место. Сначала разберём, что сказано в условии:

Почти всё время будем кодировать четыре буквы А, Б, В, Г одной таблицей: А — 0, Б — 10, В — 110, Г — 111. Тема состоит из четырёх подтем — у каждой своя страница. Идём по ним по порядку:

1. Код и условие Фано — ты сейчас здесь.
2. Кодовое дерево и кратчайший код — как найти самый короткий свободный код.
3. Место для всех букв и сумма длин — почему нужно оставить место всем буквам, и ответ задачи темы: 1110.
4. Длина закодированного слова — как сделать закодированное сообщение короче.

Код сопоставляет каждой букве алфавита последовательность знаков. Представим, что нужно передавать сообщения из четырёх букв: А, Б, В, Г. Этот набор разрешённых символов называется алфавитом сообщения. Здесь слово «алфавит» означает просто набор символов, которые могут встречаться: это могут быть буквы, цифры, цвета или условные сигналы.

Пусть устройство передаёт только два знака: 0 и 1. Тогда каждой букве нужно сопоставить некоторую последовательность этих знаков. Например:

Такая таблица задаёт правило кодирования. Кодовое слово — последовательность знаков, которая обозначает один символ исходного алфавита. Например, 110 — кодовое слово буквы В.

Здесь важно различать обычное слово, например БАВ, и кодовое слово одной буквы, например 110. Чтобы закодировать обычное слово, заменяем каждую букву её кодом и соединяем результаты:

БАВ → 10 | 0 | 110 → 100110.

Вертикальные черты стоят только для объяснения. Обычно в передаваемой последовательности разделителей между кодами нет. Декодирование — обратная операция: по последовательности 100110 нужно восстановить БАВ.

Длина кодового слова — количество знаков в нём, а сам код — последовательность, а не число. У 0 длина 1, у 10 — 2, у 110 — 3, у 00101 — 5.

Поскольку используются два знака, код называется двоичным. Один двоичный знак в такой записи занимает один бит. Поэтому «длина 5 двоичных знаков» и «длина 5 бит» в этих задачах означают одно и то же.

Несколько важных договорённостей:

• одна и та же буква во всех местах сообщения имеет один и тот же код;
• разные буквы должны иметь разные коды;
• кодовые слова непустые;
• заданные в условии коды менять нельзя.

Ещё одна тонкость: кодовое слово — прежде всего последовательность знаков, а не число. Записи 1, 01 и 001 как двоичные записи чисел обозначают одно и то же значение — единицу. Но как кодовые слова это три разные последовательности разной длины. Ведущие нули в кодах удалять нельзя.

Равномерный код режут на куски одной длины, неравномерный так прочитать нельзя. Если все кодовые слова имеют одинаковую длину, код называется равномерным. Например, А — 00, Б — 01, В — 10, Г — 11. Получив 011011, мы просто разбиваем его на группы по два знака: 01 | 10 | 11 — и получаем БВГ. Границы кодовых слов известны заранее: через каждые два знака начинается следующая буква.

Если длины различаются, код называется неравномерным. Такова наша таблица А — 0, Б — 10, В — 110, Г — 111. Теперь разрезать сообщение на равные части нельзя: нужно другое правило, которое позволит находить границы букв.

Зачем вообще использовать разные длины? Чтобы частые символы передавать короткими кодами и тем самым уменьшать длину сообщения. Это разберём в подтеме 4.

Разных кодов у букв ещё недостаточно: одну строку можно разрезать по-разному. Рассмотрим таблицу А — 0, Б — 01, В — 1. Все три кода различаются. Но что означает последовательность 01?

Одному переданному сообщению соответствуют два разных исходных. Получатель не может определить, какое из них было отправлено.

Код годится, только если любую запись можно прочитать единственным способом: одного удачно прочитанного слова мало.

В задании 4 обычно используется удобное требование, которое гарантирует однозначность, — условие Фано.

Условие Фано: ни одно кодовое слово не должно быть началом другого кодового слова. Последовательность 01 является началом последовательности 0110, потому что первые два знака 0110 — это именно 01.

При проверке двух кодовых слов нас интересует один случай: более короткое полностью совпадает с началом более длинного.

Последняя пара особенно важна. Последовательность 010 находится в конце 0010, но условие Фано запрещает именно совпадение с началом.

Ещё одна тонкость: общие начальные знаки разрешены. Коды 010 и 011 оба начинаются с 01. Это не нарушает условие Фано, потому что 01 не является отдельным кодом какой-либо буквы. Запрещено не «иметь общее начало», а целиком совпадать с началом другого кодового слова.

Условие Фано позволяет читать сообщение слева направо, не заглядывая вперёд. Вернёмся к таблице А — 0, Б — 10, В — 110, Г — 111. Читаем сообщение слева направо и накапливаем знаки.

1. Если накопилось 0, мы сразу узнаём А. Ждать продолжения не нужно: никакая другая буква не имеет кода, начинающегося с 0.
2. Если накопилось 1, буква ещё не определена: такого кодового слова в таблице нет. Читаем дальше.
3. Если получилось 10, узнаём Б. Продолжения, которое превратило бы 10 в код другой буквы, быть не может.

Так происходит после каждой буквы: первое совпавшее кодовое слово уже и есть буква.

Новый код проверяют в обе стороны. Пусть уже существует код А — 010. Нельзя добавить код Б — 01: новый код является началом существующего 010. Но нельзя добавить и 0101: существующий код 010 является началом нового.

Поэтому для каждого нового кандидата нужно задать два вопроса:

1. Не является ли новый код началом какого-нибудь существующего?
2. Не является ли какой-нибудь существующий код началом нового?

Проверка только одного направления — распространённая ошибка. При этом код 011 добавить можно: у 010 и 011 общие первые два знака, но затем они расходятся. А одинаковый код 010 второй букве назначить нельзя: две буквы стали бы неразличимыми.

• Кодовое словопоследовательность 0 и 1 для одной буквы; ведущие нули — её часть
• Длина кодачисло знаков в кодовом слове
• Неравномерный кододну запись можно разрезать на коды по-разному
• Условие Фанони один код не начало другого; общее начало и совпадение с концом разрешены
• Новый кодпроверяют в обе стороны: не начало ли он чужого и не начинается ли с чужого