Interested Article - Неравенство Крафта — Макмиллана

В теории кодирования , неравенство Крафта — Макмиллана даёт необходимое и достаточное условие существования и префиксных кодов , обладающих заданным набором длин кодовых слов.

Предварительные определения

Пусть заданы два произвольных конечных множества , которые называются, соответственно, кодируемым алфавитом и кодирующим алфавитом . Их элементы называются символами , а строки (последовательности конечной длины) символов — словами . Длина слова — это число символов, из которого оно состоит.

В качестве кодирующего алфавита часто рассматривается множество — так называемый двоичный или бинарный алфавит.

Схемой алфавитного кодирования (или просто (алфавитным) кодом ) называется любое отображение символов кодируемого алфавита в слова кодирующего алфавита, которые называют кодовыми словами . Пользуясь схемой кодирования, каждому слову кодируемого алфавита можно сопоставить его код конкатенацию кодовых слов, соответствующих каждому символу этого слова.

Код называется (или однозначно декодируемым ), если никаким двум словам кодируемого алфавита не может быть сопоставлен один и тот же код.

Префиксным кодом называется алфавитный код, в котором ни одно из кодовых слов не является префиксом никакого другого кодового слова. Любой префиксный код является разделимым.

Формулировка

Теорема Макмиллана (1956) .

Пусть заданы кодируемый и кодирующий алфавиты, состоящие из и символов, соответственно, и заданы желаемые длины кодовых слов: . Тогда необходимым и достаточным условием существования разделимого и префиксного кодов, обладающих заданным набором длин кодовых слов, является выполнение неравенства:


Это неравенство и известно под названием неравенства Крафта — Макмиллана . Впервые оно было выведено Леоном Крафтом в своей магистерской дипломной работе в 1949 году , однако он рассматривал только префиксные коды, поэтому при обсуждении префиксных кодов это неравенство часто называют просто неравенством Крафта . В 1956 году Броквэй Макмиллан доказал необходимость и достаточность этого неравенства для более общего класса кодов — разделимых кодов.

Пример

Двоичные деревья

Пример двоичного дерева. Его листья -- вершины с номерами 9, 14, 19, 67 и 76, находятся на глубинах 3, 3, 3, 3 и 2, соответственно.

Любое укоренённое двоичное дерево можно рассматривать как графическое описание префиксного кода над двоичным алфавитом: символы кодируемого алфавита соответствуют листьям дерева, а путь в дереве от корня до листа задаёт его код (путь состоит из последовательности движений «влево» и «вправо», которые соответствуют символам 0 и 1).

Для таких деревьев неравенство Крафта — Макмиллана утверждает, что:

где — множество листьев дерева, а — глубина листа , число рёбер на пути от корня до .

Для дерева на рисунке справа имеем:

Примечания

  1. Kraft, Leon G. (1949), , Cambridge, MA: MS Thesis, Electrical Engineering Department, Massachusetts Institute of Technology от 22 апреля 2009 на Wayback Machine (англ.)
  2. McMillan, Brockway (1956), , IEEE Trans. Information Theory , 2 (4): 115—116, doi : (англ.)

Литература

  • Гашков, С. Б. . — М. : МЦНМО, 2004. — 52 с. — ISBN 5-94057-146-8 .
  • Cover, T. M., Thomas, J. A. Elements of information theory. — 2006. — P. 116. — ISBN 0-471-24195-4 .

Ссылки

Источник —

Same as Неравенство Крафта — Макмиллана