Главная > Разное > Теория кодирования и теория информации
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

4.4. Построение мгновенных кодов

Ясно, что среди всех однозначно декодируемых кодов мгновенные коды предпочтительнее немгновенных, поскольку, как будет показано ниже (см. разд. 4.7), мгновенные коды не требуют дополнительных затрат. Поэтому рассмотрим задачу построения мгновенных кодов.

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

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

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

В этом коде использование для первого символа уменьшает число дальнейших возможностей. Используем вместо этого для Первых двух символов источника слова длины 2, полагая и

Тогда можно взять Поскольку осталось закодировать еще два символа источника, то в качестве кода для нельзя взять 11; вместо этого следует испробовать возможность и тогда Получим код: Этот код, очевидно, является мгновенным, поскольку никакое кодовое слово не служит префиксом никакого другого кодового слова. Для него легко построить дерево декодирования (рис.. 4.4.2).

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

Задача

4.4.1. Постройте аналогичный пример для шести слов.

4.4.2. Укажите вероятности, которые определяют, является ли более эффективным тот или другой код из этого раздела. Ответ:

<< Предыдущий параграф Следующий параграф >>
Оглавление