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