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

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

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

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

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

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

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

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

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

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

Приклад

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

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

де  — множина листя дерева, а  — глибина листка , тобто кількість ребер на шляху від кореня до .

Наприклад:

Література

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.