У теорії кодування нерівність Крафта - Макміллана дає необхідну і достатню умову існування і префіксних кодів з заданим набором довжин кодових слів.
Попередні визначення
Нехай задано дві довільно кінцеві множини, які називаються, відповідно, кодованим алфавітом і кодуючим алфавітом. Їх елементи називаються символами, а рядки (послідовності кінцевої довжини) символів — словами. Довжина слова — це кількість символів, з якого воно складається.
Як кодуючий алфавіт часто розглядається множина {0;1} — так званий двійковий або бінарний алфавіт.
Схемою алфавітного кодування (або просто (алфавітним) кодом) називається будь-яке відображення символів кодованого алфавіту в слова кодуючого алфавіту, які називають кодовими словами. Користуючись схемою кодування, кожне слово кодованого алфавіту можна зіставити з його кодом — конкатенацією кодових слів, що відповіднає кожному символу цього слова.
Код називається роздільним (або однозначно декодованим), якщо жодним двом словам кодованого алфавіту не може бути зіставлений один і той же код.
Префіксним кодом називається алфавітний код, в якому жодне з кодових слів не є префіксом жодного іншого кодового слова. Будь-який префіксний код є роздільним.
Формулювання
Нехай задані кодований і кодуючий алфавіти, що складаються з n і d символів, відповідно, і задані бажані довжини кодових слів: . Тоді необхідною і достатньою умовою існування роздільного і префіксного кодів, що володіють заданим набором довжин кодових слів, є виконання нерівності:
Ця нерівність і відома під назвою нерівності Крафта — Макміллана. Вперше вона була виведена Леоном Крафтом в своїй магістерській дипломній роботі в 1949 році, проте він розглядав лише префіксні коди, тому при обговоренні префіксних код цю нерівність часто називають просто нерівністю Крафта. У 1956 році Броквей Макміллан довів необхідність і достатність цієї нерівності для загальнішого класу кодів — роздільних кодів.
Приклад
Кореневе двійкове дерево - це таке дерво, в якому кожен вузол, що не є листом, має два і тільки два нащадки.
Будь-яке вкорінене двійкове дерево можна розглядати як графічний опис префіксного коду над двійковим алфавітом: символи кодованого алфавіту відповідають листам дерева, а шлях в дереві від кореня до листа задає його код (шлях складається з послідовності рухів «ліворуч» і «праворуч», які відповідають символам 0 і 1).
Для таких дерев нерівність Крафта — Макміллана стверджує, що:
де — множина листів дерева, а — глибина листка , тобто кількість ребер на шляху від кореня до кінцевої вершини (листа) .
Розглянемо дерево на Рис 1.
Для 4 листків маємо глибину - 3, а для вузла із значенням 76 глибина рівна 2, таким чином маємо нерівність:
Література
- Гашков, С. Б. Системи числення і їх вживання. — М. : МЦНМО, 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
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U teoriyi koduvannya nerivnist Krafta Makmillana daye neobhidnu i dostatnyu umovu isnuvannya i prefiksnih kodiv z zadanim naborom dovzhin kodovih sliv Poperedni viznachennyaNehaj zadano dvi dovilno kincevi mnozhini yaki nazivayutsya vidpovidno kodovanim alfavitom i koduyuchim alfavitom Yih elementi nazivayutsya simvolami a ryadki poslidovnosti kincevoyi dovzhini simvoliv slovami Dovzhina slova ce kilkist simvoliv z yakogo vono skladayetsya Yak koduyuchij alfavit chasto rozglyadayetsya mnozhina 0 1 tak zvanij dvijkovij abo binarnij alfavit Shemoyu alfavitnogo koduvannya abo prosto alfavitnim kodom nazivayetsya bud yake vidobrazhennya simvoliv kodovanogo alfavitu v slova koduyuchogo alfavitu yaki nazivayut kodovimi slovami Koristuyuchis shemoyu koduvannya kozhne slovo kodovanogo alfavitu mozhna zistaviti z jogo kodom konkatenaciyeyu kodovih sliv sho vidpovidnaye kozhnomu simvolu cogo slova Kod nazivayetsya rozdilnim abo odnoznachno dekodovanim yaksho zhodnim dvom slovam kodovanogo alfavitu ne mozhe buti zistavlenij odin i toj zhe kod Prefiksnim kodom nazivayetsya alfavitnij kod v yakomu zhodne z kodovih sliv ne ye prefiksom zhodnogo inshogo kodovogo slova Bud yakij prefiksnij kod ye rozdilnim FormulyuvannyaNehaj zadani kodovanij i koduyuchij alfaviti sho skladayutsya z n i d simvoliv vidpovidno i zadani bazhani dovzhini kodovih sliv l1 l2 ln displaystyle l 1 l 2 l n Todi neobhidnoyu i dostatnoyu umovoyu isnuvannya rozdilnogo i prefiksnogo kodiv sho volodiyut zadanim naborom dovzhin kodovih sliv ye vikonannya nerivnosti i 1nd ℓi 1 displaystyle sum i 1 n d ell i leqslant 1 Cya nerivnist i vidoma pid nazvoyu nerivnosti Krafta Makmillana Vpershe vona bula vivedena Leonom Kraftom v svoyij magisterskij diplomnij roboti v 1949 roci prote vin rozglyadav lishe prefiksni kodi tomu pri obgovorenni prefiksnih kod cyu nerivnist chasto nazivayut prosto nerivnistyu Krafta U 1956 roci Brokvej Makmillan doviv neobhidnist i dostatnist ciyeyi nerivnosti dlya zagalnishogo klasu kodiv rozdilnih kodiv PrikladDvijkovi dereva Koreneve dvijkove derevo ce take dervo v yakomu kozhen vuzol sho ne ye listom maye dva i tilki dva nashadki Bud yake vkorinene dvijkove derevo mozhna rozglyadati yak grafichnij opis prefiksnogo kodu nad dvijkovim alfavitom simvoli kodovanogo alfavitu vidpovidayut listam dereva a shlyah v derevi vid korenya do lista zadaye jogo kod shlyah skladayetsya z poslidovnosti ruhiv livoruch i pravoruch yaki vidpovidayut simvolam 0 i 1 Dlya takih derev nerivnist Krafta Makmillana stverdzhuye sho x L2 depth x 1 displaystyle sum x in mathcal L 2 mathrm depth x leqslant 1 de L displaystyle mathcal L mnozhina listiv dereva a depth x displaystyle mathrm depth x glibina listka x displaystyle x tobto kilkist reber na shlyahu vid korenya do kincevoyi vershini lista x displaystyle x Ris 1 Dvijkove derevo Rozglyanemo derevo na Ris 1 Dlya 4 listkiv mayemo glibinu 3 a dlya vuzla iz znachennyam 76 glibina rivna 2 takim chinom mayemo nerivnist 122 4 123 14 4 18 34 1 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 LiteraturaGashkov S B Sistemi chislennya i yih vzhivannya M MCNMO 2004 52 s ISBN 5 94057 146 8 Cover T M Thomas J A Elements of information theory 2006 P 116 ISBN 0 471 24195 4 PosilannyaKraft s inequality NIST http www codingtheory gorodok net seminars seminar 2010 pdf