4.10. Расширения кода

В разд. 4.2 было определено расширение кода. Теперь покажем, что это понятие является полезным. Для определенности, рассмотрим пример, в котором имеется два символа источника с вероятностями Средняя длина кода равна 1. Кодирование

Для -кратного расширения берутся сразу два символа Кодирование

Здесь в четыре раза больше, чем Для сравнения приведем среднюю длину, нормированную делением на 2; она равна Следующее расширение, при котором берутся три символа, дает Беря по четыре символа за один раз, получаем среднюю длину кода, равную 0,93827.

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

Задача

4.10.1. Вычислите среднюю длину расширений, рассмотренных в этом разделе.