2015-05-20
205
а) Пусть 
– префиксный код, тогда для него существует кодовое дерево, висячим вершинам которого соответствуют кодовые слова. Рассмотрим фрагмент этого дерева (рис. 52).
Рис. 52
| Если убрать вершины  и  вместе с инцидентными ребрами, вершина  станет висячей, мы получим кодовое дерево для кода  , в котором кодовым словам соответствуют только висячие вершины, следовательно, код – префиксный.
|
Наоборот, если – префиксный, то вершина, соответствующая кодовому слову , висячая. Добавив к этой вершине два ребра, получим две висячие вершины и , а слово в код не входит, вновь получим кодовое дерево для префиксного кода.
б) Найдем цену кодирования кода .
.
