а) Пусть . Построим код
, переставив в коде
два кодовых слова:
.
Рассмотрим
откуда следует , то есть код
не оптимальный, что противоречит условию.
б) Пусть кодовое слово и имеет максимальную длину
, а кодового слова
нет. Рассмотрим фрагмент кодового дерева, построенного для этого кода (рис. 51).
![]() | Построим код ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
Вновь пришли к противоречию, получив взаимно-однозначный код с ценой меньшей, чем оптимальный код.
Следствие. В кодовом дереве для оптимального префиксного кода вероятности, приписанные вершинам предыдущего яруса, не меньше, чем вероятности, приписанные концевым вершинам следующего яруса.