Теория информации
Конспект лекций
назад | содержание | вперед

4. ОПТИМАЛЬНОЕ ПОБУКВЕННОЕ КОДИРОВАНИЕ

 

4.3 Свойства оптимального побуквенного кода

Приведем некоторые свойства, которыми обладает любой оптимальный побуквенный код.

Лемма 1. Для оптимального кода с длинами кодовых слов  верно соотношение ,  если .

Доказательство (от противного). Пусть есть индексы  и  такие, что  при . Тогда

т.е. если поменяем местами  и , то получим код, имеющий меньшую среднюю длину кодового слова, что противоречит с оптимальности кода. Лемма 1 доказана.

Лемма 2 Пусть  – схема оптимального префиксного кодирования для распределения вероятностей P, . Тогда среди элементарных кодов, имеющих максимальную длину, существуют два, которые различаются только в последнем разряде.

Доказательство. Покажем, что в оптимальной схеме кодирования всегда найдется два кодовых слова максимальной длины. Предположим обратное. Пусть кодовое слово максимальной длины одно и имеет вид . Тогда длина любого элементарного кода не больше длины b, т.е. , . Поскольку схема кодирования префиксная, то кодовые слова  не являются префиксом b. С другой стороны, b не является префиксом кодовых слов . Таким образом, новая схема кодирования  также является префиксной, причем с меньшей средней длиной кодового слова , что противоречит оптимальности исходной схемы кодирования. Пусть теперь два кодовых слова  и  максимальной длины отличаются не в последнем разряде, т.е. . Причем  не являются префиксами для других кодовых слов  и наоборот. Тогда новая схема  также является префиксной, причем , что противоречит оптимальности исходной схемы кодирования. Лемма 2 доказана.

наверх

 


назад | содержание | вперед