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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Предварительные определения[править | править вики-текст]

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

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

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

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

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

Формулировка[править | править вики-текст]

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

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

\sum_{i=1}^n d^{\,-\ell_i} \leqslant 1.

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

Пример[править | править вики-текст]

Двоичные деревья[править | править вики-текст]

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

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

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

 \sum_{x \in \mathcal{L}} 2^{-\mathrm{depth}(x)} \leqslant 1,

где \mathcal{L} — множество листьев дерева, а \mathrm{depth}(x) — глубина листа x, число рёбер на пути от корня до x.

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

 \frac{1}{4} + 4 \left( \frac{1}{8} \right) = \frac{3}{4} \leqslant 1.

Примечания[править | править вики-текст]

  1. Kraft, Leon G. (1949), «A device for quantizing, grouping, and coding amplitude modulated pulses», Cambridge, MA: MS Thesis, Electrical Engineering Department, Massachusetts Institute of Technology, <http://dspace.mit.edu/handle/1721.1/12390>  (англ.)
  2. McMillan, Brockway (1956), "«Two inequalities implied by unique decipherability»", IEEE Trans. Information Theory Т. 2 (4): 115–116, doi:10.1109/TIT.1956.1056818, <http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1056818>  (англ.)

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]