Нерівність Крафта - Макміллана

У теорії кодування нерівність Крафта - Макміллана дає необхідну і достатню умову існування і префіксних кодів з заданим набором довжин кодових слів.

Попередні визначення

Нехай задано дві довільно кінцеві множини, які називаються, відповідно, кодованим алфавітом і кодуючим алфавітом. Їх елементи називаються символами, а рядки (послідовності кінцевої довжини) символів — словами. Довжина слова — це кількість символів, з якого воно складається.

Як кодуючий алфавіт часто розглядається множина {0;1} — так званий двійковий або бінарний алфавіт.

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

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

Префіксним кодом називається алфавітний код, в якому жодне з кодових слів не є префіксом жодного іншого кодового слова. Будь-який префіксний код є роздільним.

Формулювання

Нехай задані кодований і кодуючий алфавіти, що складаються з n і d символів, відповідно, і задані бажані довжини кодових слів: ${\displaystyle l_{1},l_{2},...,l_{n}}$. Тоді необхідною і достатньою умовою існування роздільного і префіксного кодів, що володіють заданим набором довжин кодових слів, є виконання нерівності:

${\displaystyle \sum _{i=1}^{n}d^{\,-\ell _{i}}\leqslant 1.}$

Ця нерівність і відома під назвою нерівності Крафта — Макміллана. Вперше вона була виведена Леоном Крафтом в своїй магістерській дипломній роботі в 1949 році, проте він розглядав лише префіксні коди, тому при обговоренні префіксних код цю нерівність часто називають просто нерівністю Крафта. У 1956 році Броквей Макміллан довів необхідність і достатність цієї нерівності для загальнішого класу кодів — роздільних кодів.

Приклад

Двійкові дерева

Кореневе двійкове дерево - це таке дерво, в якому кожен вузол, що не є листом, має два і тільки два нащадки.

Будь-яке вкорінене двійкове дерево можна розглядати як графічний опис префіксного коду над двійковим алфавітом: символи кодованого алфавіту відповідають листам дерева, а шлях в дереві від кореня до листа задає його код (шлях складається з послідовності рухів «ліворуч» і «праворуч», які відповідають символам 0 і 1).

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

${\displaystyle \sum _{x\in {\mathcal {L}}}2^{-\mathrm {depth} (x)}\leqslant 1,}$

де ${\displaystyle {\mathcal {L}}}$ — множина листів дерева, а ${\displaystyle \mathrm {depth} (x)}$ — глибина листка ${\displaystyle x}$, тобто кількість ребер на шляху від кореня до кінцевої вершини (листа) ${\displaystyle x}$.

Рис 1: Двійкове дерево

Розглянемо дерево на Рис 1.

Для 4 листків маємо глибину - 3, а для вузла із значенням 76 глибина рівна 2, таким чином маємо нерівність:

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

Література

• Гашков, С. Б. Системи числення і їх вживання. — М. : МЦНМО, 2004. — 52 с. — .
• Cover, T. M., Thomas, J. A. Elements of information theory. — 2006. — P. 116. — .

Посилання

• Kraft’s inequality (NIST)
• http://www.codingtheory.gorodok.net/seminars/seminar%2010.pdf