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

6.9. Примеры расширений

Предположим, что алфавит источника состоит из двух символов роятностями Энтропия равна

Код Хаффмена дает так что средняя длина кодового слова равна 1. Код Шеннона — Фано дает и средняя длина равна

В разд. 4.10 приведена средняя длниа кодов Хаффмена для некоторых расширений. Для кода Шеннона — Фано при расширении кратности 2, имеем

Средняя длина

Оказывается, что в данном случае можно вычислить коды Шеннона — Фано для всех расширений. Для -кратного расширения имеем:

Для нахождения имеем

Пусть наименьшее целое число, большее Тогда средняя длина кода:

Известно, что разложение бинома можно записать в любом из двух видов:

Дифференцируя второе разложение и умножая на получаем

Полагая в (6.9.3) и имеем

Поэтому где из

Приведем небольшую таблицу значении включив в последний столбец параметры кодов Хаффмена:

(см. скан)

Из соотношения (6.5.3) нижняя граница равна Параметры кодов Шеннона — Фано приближаются к этой границе нерегулярно, однако, как

показывает предыдущий результат (см. разд. 6.8), в конце концов они достигают этой границы.

Подведем итоги рассмотрения.

1. Из неравенств (6.5.3) и Крафта следует, что для любого мгновенного кода

2. Из неравенства (6.6.3) следует, что

3. В разд. 4.10 показано, что вследствие оптимальности кода Хаффмена

4. Согласно (6.8.2) для -кратного расширения справедливы неравенства

На основании пп. 1—4 получаем, что для -кратного расширения

где средняя длина кода Хаффмена для -кратного расширения и средняя длина кода Шеннона — Фано для -кратного расширения. Таблица является экспериментальным подтверждением этого результата. Последние неравенства ясно показывают, почему в разд. 6.7 можно было утверждать, что потери при переходе от оптимальных кодов Хаффмена к кодам Шеннона — Фано несущественны при больших Однако при небольших эти потери могут оказаться существенными.

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