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

4.9. Частные случаи кодов Хаффмена

Интересно рассмотреть несколько частных случаев кода Хаффмена. Первый случай, если все символы источника равновероятны и если их число точно равно то (двоичный) код Хаффмена является блочным, все кодовые слова которого имеют одну и ту же длину (рис. 4.9.1). Если число символов источника не равно точно то получаем укороченный блочный код (см. Разд. 4.6).

Более интересным является второй случай. Предположим, что сумма вероятностей двух наименее вероятных символов источника

больше, чем вероятность наиболее вероятного символа, . В процессе построения кода Хаффмена (см. рис. 4.9.1) соответствующий склеенный символ перейдет в первую строку списка кодовых слов. Далее два следующих символа с наименьшими вероятностями склеиваются и переходят в первую строку следующего списка и т. д.

Рис. 4.9.1

Рис. 4.9.2. Два возможных случая

Если первоначальное число символов является точной степенью двойки, то в процессе перехода к коду для двух символов каждый символ пройдет через одинаковое число этапов разделения, так что каждое кодовое слово получит при этом одинаковое число двоичных символов. Таким образом, снова получается блочный код. Если не является точной степенью 2, то незначительное изменение этого процесса приводит к укороченному блочному коду (см. разд. 4.6).

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

Если, например, вероятности весьма различны, так что

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

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

Задача

4.9.1 (Трудная). Обсудите, что происходит в случаях, промежуточных между двумя основными случаями.

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