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 можно было утверждать, что потери при переходе от оптимальных кодов Хаффмена к кодам Шеннона — Фано несущественны при больших 
Однако при небольших 
эти потери могут оказаться существенными.
