Теория информации |
Конспект лекций |
3. ПОБУКВЕННОЕ КОДИРОВАНИЕ
3.3 Неравенство Крафта
Теорема (Крафт). Для того, чтобы существовал побуквенный двоичный префиксный код с длинами кодовых слов необходимо и достаточно, чтобы
Доказательство. Докажем необходимость. Пусть существует префиксный код с длинами. Рассмотрим полное двоичное дерево. Каждая вершина закодирована последовательностью нулей и единиц (как показано на рисунке).
Рисунок 2 Полное двоичное дерево с помеченными вершинами
В этом дереве выделим вершины, соответствующие кодовым словам. Тогда любые два поддерева, соответствующие кодовым вершинам дерева, не пересекаются, т.к. код префиксный. У i-того поддерева на r-том уровне – вершин. Всего вершин в поддереве
. Тогда
,
.
Докажем достаточность утверждения. Пусть существует набор длин кодовых слов такой, что . Рассмотрим полное двоичное дерево с помеченными вершинами. Пусть длины кодовых слов упорядочены по возрастанию
. Выберем в двоичном дереве вершину
на уровне
. Уберем поддерево с корнем в вершине
. В оставшемся дереве возьмем вершину
на уровне
и удалим поддерево с корнем в этой вершине и т.д. Последовательности, соответствующие вершинам
образуют префиксный код. Теорема доказана.
Пример 3.3.1. Построить префиксный код с длинами для алфавита
. Проверим неравенство Крафта для набора длин
Неравенство выполняется и, следовательно, префиксный код с таким набором длин кодовых слов существует. Рассмотрим полное двоичное дерево с помеченными вершинами и выберем вершины дерева, как описано выше в доказательстве теоремы Крафта. Тогда элементарные коды могут быть такими:
. (Возможен и другой выбор элементарных кодов). Нетрудно видеть, что полученный код является префиксным, поскольку ни одно кодовое слово не является префиксом другого кодового слова.
Рисунок 3 Построение префиксного кода с заданными длинами
Процесс декодирования может быть организован следующим образом. Просматриваем полученное сообщение, двигаясь по дереву. Если попадем в кодовую вершину, то выдаем соответствующую букву и возвращаемся в корень дерева и т.д.