4.3. Мгновенные коды

Изучим следующий код: Посмотрим, как приемник декодирует сообщения, посылаемые в этом коде. Приемник использует конечный автомат или, что эквивалентно, дерево решений. Автомат начинает действовать из начального состояния (рис. 4.3.1); первая принятая двоичная цифра вызовет переход автомата либо в концевое состояние если цифра равна 0, либо во вторую точку ветвления, если цифра равна 1. Следующая принятая двоичная цифра вызовет либо переход в концевое состояние если цифра равна 0, либо в третью точку ветвления, если цифра равна 1. Далее, если третья цифра равна 0, то произойдет переход в концевое состояние а если третья цифра равна 1, то в концевое состояние . В каждом концевом состоянии выдается, конечно, соответствующий символ и происходит возврат в начальное состояние. Заметим, что каждый бит принятой последовательности просматривается только один раз, и концевые состояния дерева — это четыре символа источника:

Рис. 4.3.1. Дерево декодирования

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

Следующий код обладает однозначным декодированием, но не является мгновенным, поскольку нельзя решить, когда кончается кодовое слово, не иследуя последующие биты: Это предыдущий код с перевернутыми кодовыми словами. Причина неприятностей состоит в том, что некоторые кодовые слова являются префиксами (иначе говоря, совпадают с начальными частями) других кодовых слов.

Рассмотрим последовательность Ее можно декодировать только начиная с конца и сопоставлять каждым трем единицам символ до тех пор, пока не будет достигнуто первое кодовое слово. Только после этого ему можно сопоставить один

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

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