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

3. ПОБУКВЕННОЕ КОДИРОВАНИЕ

 

3.3 Неравенство Крафта

 

Теорема (Крафт). Для того, чтобы существовал побуквенный двоичный префиксный код с длинами кодовых слов  необходимо и достаточно, чтобы


 

Доказательство. Докажем необходимость. Пусть существует префиксный код с длинами. Рассмотрим полное двоичное дерево. Каждая вершина закодирована последовательностью нулей и единиц (как показано на рисунке).

 

Рисунок 2 Полное двоичное дерево с помеченными вершинами

 


В этом дереве выделим вершины, соответствующие кодовым словам. Тогда любые два поддерева, соответствующие кодовым вершинам дерева, не пересекаются, т.к. код префиксный. У i-того поддерева на r-том уровне –  вершин. Всего вершин в поддереве . Тогда  , .

Докажем достаточность утверждения. Пусть существует набор длин кодовых слов такой, что . Рассмотрим полное двоичное дерево с помеченными вершинами. Пусть длины кодовых слов упорядочены по возрастанию . Выберем в двоичном дереве вершину  на уровне . Уберем поддерево с корнем в вершине . В оставшемся дереве возьмем  вершину  на уровне и удалим поддерево с корнем в этой вершине и т.д. Последовательности, соответствующие вершинам  образуют префиксный код. Теорема доказана.
Пример 3.3.1. Построить префиксный код с длинами  для алфавита . Проверим неравенство Крафта для набора длин



Неравенство выполняется и, следовательно, префиксный код с таким набором длин кодовых слов существует. Рассмотрим полное двоичное дерево с  помеченными вершинами и выберем вершины дерева, как описано выше в доказательстве теоремы Крафта. Тогда элементарные коды могут быть такими: . (Возможен и другой выбор элементарных кодов). Нетрудно видеть, что полученный код является префиксным, поскольку ни одно кодовое слово не является префиксом другого кодового слова.


 

 

Рисунок 3 Построение префиксного кода с заданными длинами

 

Процесс декодирования может быть организован следующим образом. Просматриваем полученное сообщение, двигаясь по дереву. Если попадем в кодовую вершину, то выдаем соответствующую букву и возвращаемся в корень дерева и т.д.

 

наверх

 


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