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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Попередні визначення[ред.ред. код]

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

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

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

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

Формулювання[ред.ред. код]

Нехай задані кодований і кодуючий алфавіти, що складаються з n і d символів, відповідно, і задані бажані довжини кодових слів: l_1, l_2,...,l_n. Тоді необхідною і достатньою умовою існування роздільного і префіксного кодів, що володіють заданим набором довжин кодових слів, є виконання нерівності:

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

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

Приклад[ред.ред. код]

Двійкові дерева[ред.ред. код]

Будь-яке вкорінене двійкове дерево можна розглядати як графічний опис префіксного коду над двійковим алфавітом: символи кодованого алфавіту відповідають листю дерева, а шлях в дереві від кореня до листа задає її код (путь складається з послідовності рухів «ліворуч» і «праворуч», які відповідають символам 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.

Література[ред.ред. код]

Посилання[ред.ред. код]