Теория информации |
Конспект лекций |
4. ОПТИМАЛЬНОЕ ПОБУКВЕННОЕ КОДИРОВАНИЕ
4.3 Свойства оптимального побуквенного кода
Приведем некоторые свойства, которыми обладает любой оптимальный побуквенный код.
Лемма 1. Для оптимального кода с длинами кодовых слов верно соотношение
, если
.
Доказательство (от противного). Пусть есть индексы и
такие, что
при
. Тогда
т.е. если поменяем местами и
, то получим код, имеющий меньшую среднюю длину кодового слова, что противоречит с оптимальности кода. Лемма 1 доказана.
Лемма 2 Пусть – схема оптимального префиксного кодирования для распределения вероятностей P,
. Тогда среди элементарных кодов, имеющих максимальную длину, существуют два, которые различаются только в последнем разряде.
Доказательство. Покажем, что в оптимальной схеме кодирования всегда найдется два кодовых слова максимальной длины. Предположим обратное. Пусть кодовое слово максимальной длины одно и имеет вид . Тогда длина любого элементарного кода не больше длины b, т.е.
,
. Поскольку схема кодирования префиксная, то кодовые слова
не являются префиксом b. С другой стороны, b не является префиксом кодовых слов
. Таким образом, новая схема кодирования
также является префиксной, причем с меньшей средней длиной кодового слова
, что противоречит оптимальности исходной схемы кодирования. Пусть теперь два кодовых слова
и
максимальной длины отличаются не в последнем разряде, т.е.
. Причем
не являются префиксами для других кодовых слов
и наоборот. Тогда новая схема
также является префиксной, причем
, что противоречит оптимальности исходной схемы кодирования. Лемма 2 доказана.