Nierówność Krafta-McMillana

W teorii kodowania nierówność Krafta -McMillana daje warunek konieczny i wystarczający na istnienie kodu przedrostka (w wersji Leona G. Krafta) lub kodu jednoznacznie dekodowalnego (w wersji Brockwaya McMillana ) dla danego zestawu długości słów kodowych . Jego zastosowania do kodów prefiksów i drzew często znajdują zastosowanie w informatyce i teorii informacji .

Nierówność Krafta została opublikowana w Kraft (1949) . Jednak artykuł Krafta omawia tylko kody przedrostków i przypisuje analizę prowadzącą do nierówności Raymondowi Redhefferowi . Wynik został niezależnie odkryty w McMillan (1956) . McMillan udowadnia wynik dla ogólnego przypadku jednoznacznie dekodowalnych kodów i przypisuje wersję kodów prefiksów obserwacji mówionej z 1955 roku przez Josepha Leo Dooba .

Zastosowania i intuicje

Nierówność Krafta ogranicza długości słów kodowych w kodzie prefiksu : jeśli przyjmiemy wykładniczą długość każdego ważnego słowa kodowego, wynikowy zestaw wartości musi wyglądać jak funkcja masy prawdopodobieństwa , to znaczy musi mieć całkowitą miarę mniejszą lub równą do jednego. Nierówność Krafta można traktować w kategoriach ograniczonego budżetu, który można wydać na słowa kodowe, przy czym krótsze słowa kodowe są droższe. Wśród użytecznych właściwości wynikających z nierówności znajdują się następujące stwierdzenia:

Jeśli nierówność Krafta zachodzi przy ścisłej nierówności, kod ma pewną redundancję .
Jeśli nierówność Krafta zachodzi z równością, dany kod jest pełnym kodem.
Jeśli nierówność Krafta nie jest spełniona, kod nie jest jednoznacznie dekodowalny .
Dla każdego jednoznacznie dekodowalnego kodu istnieje kod prefiksu o takim samym rozkładzie długości.

Oświadczenie formalne

Niech każdy symbol źródłowy z alfabetu

{\ Displaystyle S = \ {\, s_ {1}, s_ {2}, \ ldots, s_ {n} \, \}}

być zakodowany w unikalny kod dekodowalny w alfabecie o długości słowa kodowego ${\ displaystyle r}$

{\ Displaystyle \ ell _ {1}, \ ell _ {2}, \ ldots, \ ell _ {n}.}

Następnie

{\ Displaystyle \ suma _ {i = 1} ^ {n} r ^ {- \ ell _ {i}} \ leqslant 1.}

I odwrotnie, dla danego zbioru liczb naturalnych $ell _ {2}, \ ldots, \ ell _ {n}}$ \ $,$ jednoznacznie dekodowalny kod w alfabecie o takich długościach słowa kodowego.

Przykład: drzewa binarne

9, 14, 19, 67 i 76 to węzły liściowe na głębokości odpowiednio 3, 3, 3, 3 i 2.

Każde drzewo binarne można postrzegać jako definiujące kod prefiksu dla liści drzewa. Stwierdza to nierówność Krafta

{\ Displaystyle \ suma _ {\ ell \ in {\ tekst {pozostawia}}} 2 ^ {- {\ tekst {głębokość}} (\ ell)} \ leqslant 1.}

Tutaj suma jest przejmowana przez liście drzewa, czyli węzły bez dzieci. Głębokość to odległość do węzła głównego. W drzewie po prawej stronie jest ta suma

{\ Displaystyle {\ Frac {1} {4}} + 4 \ lewo ({\ Frac {1} {8}} \ prawej) = {\ Frac { 3}{4}}\prostownik 1.}

Dowód

Dowód dla kodów prefiksów

Przykład drzewa binarnego. Czerwone węzły reprezentują drzewo prefiksów. Pokazano metodę obliczania liczby potomnych węzłów liścia w pełnym drzewie.

Najpierw pokażmy, że nierówność Krafta zachodzi zawsze, gdy kod dla $kodem$ przedrostkowym.

Załóżmy, że ${\ Displaystyle \ ell _ {1} \ leqslant \ ell _ {2} \ leqslant \ cdots \ leqslant \ ell _ {n}}$ . Niech $A}$ $Displaystyle A}$ $Displaystyle$ będzie pełnym drzewem głębokości (a więc każdy węzeł na poziomie ${\ displaystyle <\ ell _ {n}}$ $) ZA$ ma $liście$ $r}$ dzieci, podczas gdy węzły na poziomie ). Każde słowo o długości $}$ -ary alfabetu odpowiada węzłowi w tym drzewie na głębokości ℓ $\ Displaystyle$ $\ ell \ leqslant \ ell _ {n$ . ja ${\ displaystyle i}$ th słowo w kodzie prefiksu odpowiada węzłowi $i}}$ ; pozwalać $A_ {i}}$ $być$ zbiorem wszystkich węzłów liści (tj. węzłów na głębokości $poddrzewie$ zakorzeniony w ${\ displaystyle v_ {i}}$ . To poddrzewo ma wysokość , mamy ${\ Displaystyle \ ell _ {n} - \ ell _ {i}}$

{\ Displaystyle | A_ {i} | = r ^ {\ ell _ {n} - \ ell _ {i}}.}

Ponieważ kod jest kodem prefiksu, te poddrzewa nie mogą współdzielić żadnych liści, co oznacza, że

{\ Displaystyle A_ {i} \ cap A_ {j} = \ varnothing \ quad i \ neq j.}

$\ Displaystyle r ^ {\ ell _ {n}$ , że całkowita liczba węzłów na głębokości wynosi , $mamy$ r }

{\ Displaystyle \ lewo | \ bigcup _ {i = 1} ^ {n} A_ {i} \ prawo | = \ suma _ {i = 1} ^{n}|A_{i}|=\sum _{i=1}^{n}r^{\ell _{n}-\ell _{i}}\leqslant r^{\ell _{n }}}

z czego wynika wynik.

I odwrotnie, biorąc pod uwagę dowolną uporządkowaną sekwencję liczb naturalnych , ${\ displaystyle n}$

{\ Displaystyle \ ell _ {1} \ leqslant \ ell _ {2} \ leqslant \ cdots \ leqslant \ ell _ {n}}

$\ ell _ {i}}$ przedrostka o długości słowa kodowego równej każdemu, $displaystyle$ dowolnie słowo o długości wykluczając wszystkie słowa o większej długości, które mają to jako przedrostek. Ponownie zinterpretujemy to w kategoriach węzłów liściowych $Displaystyle \ ell _ {n}}$ drzewa głębokości $.$ \ Najpierw wybierz dowolny węzeł z pełnego drzewa na głębokości ${\ Displaystyle \ ell _ {1}}$ ; odpowiada pierwszemu słowu naszego nowego kodu. Ponieważ budujemy kod prefiksu, wszyscy potomkowie tego węzła (tj. wszystkie słowa, które mają to pierwsze słowo jako prefiks) stają się nieodpowiednie do włączenia do kodu. Rozważamy potomków na głębokości $tj$ . Węzły liści wśród potomków) są $, które$ z rozważań Następna iteracja wybiera (ocalały) węzeł na głębokości ${2}}$ $\ Displaystyle$ i usuwa tak dalej Po $usunęliśmy$ łącznie

{\ Displaystyle \ suma _ {i = 1} ^ {n} r ^ {\ ell _ {n} - \ ell _ {i}}}

węzły. Pytanie brzmi $,$ czy musimy usunąć więcej węzłów liści, niż faktycznie mamy dostępnych - w procesie budowania kodu. Ponieważ zachodzi nierówność Krafta, rzeczywiście mamy

{\ Displaystyle \ suma _ {i = 1} ^ {n} r ^ {\ ell _ {n} - \ ell _ {i}} \ leqslant r ^{\ell _{n}}}

iw ten sposób można zbudować kod prefiksu. Należy zauważyć, że ponieważ wybór węzłów na każdym etapie jest w dużej mierze arbitralny, ogólnie można zbudować wiele różnych odpowiednich kodów prefiksów.

Dowód przypadku ogólnego

Teraz udowodnimy, że nierówność Krafta zachodzi zawsze, gdy $kodem$ jednoznacznie dekodowalnym. (Nie trzeba udowadniać odwrotności, ponieważ udowodniliśmy to już dla kodów prefiksów, co jest silniejszym twierdzeniem).

Oznacz do $\ Displaystyle C = \ suma _ {i = 1} ^ {n} r ^ {- l_ {i}}}$ . Ideą dowodu jest uzyskanie górnej granicy dla $tylko$ ${\ displaystyle m \ in \ mathbb {$ dla wszystkich $} \ Displaystyle m}$ } gdyby do $\ Displaystyle C \ równoważnik 1}$ . Przepisz ${\ displaystyle C ^ {m}}$ jako

{\ Displaystyle {\ rozpocząć {wyrównane} C ^ {m} & = \ lewo (\ suma _ {i = 1} ^ {n} r ^ {-l_ {i}} \ prawej) ^ {m} \\& =\suma _{i_{1}=1}^{n}\suma _{i_{2}=1}^{n}\cdots \suma _{i_{m}=1}^{n}r^ {-\left(l_{i_{1}}+l_{i_{2}}+\cdots +l_{i_{m}}\right)}\\\end{wyrównane}}}

Rozważ wszystkie m -moce , w postaci słów $kropki s_ {i_ {m}}}$ $}$ $\ Displaystyle s_ {i_ {1}} s_ {i_ {2}$ , gdzie ${\ Displaystyle i_ {1}, i_ {2}, \ kropki, i_ {m}}$ to indeksy między 1 a ${\ styl wyświetlania n}$ . Zauważ, że od czasu S s $s_ {i_ {1}} s_ {i_ {2}} \ kropki s_ {i_ { m}}=s_{j_{1}}s_{j_{2}}\dots s_{j_{m}}}$ implikuje ${\ Displaystyle i_ {1} = j_ {1}, i_ {2} = j_ {2}, \ kropki, i_ {m} = j_ {m}}$ . Oznacza to $, że$ odpowiada dokładnie jednemu słowu w . To pozwala nam przepisać równanie na

\ Displaystyle C ^ {m} = \ suma _ {\ ell = 1} ^ {m \ cdot \ ell _ {max}} q_ { \ell}\,r^{-\ell}}

gdzie ${\ Displaystyle q_ {\ ell}}$ to liczba słów kodowych o długości ${\ Displaystyle S ^ {m}} i$ ${\ Displaystyle \ ell}$ i ${\ Displaystyle \ ell _ { max}}$ to długość najdłuższego słowa kodowego w ${\ displaystyle S}$ . Dla $Displaystyle$ alfabetu są tylko możliwe długości $r ^ {\ ell}}$ ${\ Displaystyle \ ell}$ , więc ${\ Displaystyle q _ {\ ell} \ równoważnik r ^ {\ ell}}$ . Korzystając z tego, wyznaczamy górną granicę ${\ displaystyle C ^ {m}}$ :

{\ Displaystyle {\ rozpocząć {wyrównane} C ^ {m} & = \ suma _ {\ ell = 1} ^ {m \ cdot \ ell _ {max}} q_ {\ ell} \, r ^ {- \ ell }\\&\leq \sum _{\ell =1}^{m\cdot \ell _{max}}r^{\ell }\,r^{-\ell }=m\cdot \ell _{ max}\end{wyrównane}}}

Biorąc $pierwiastek$ , otrzymujemy

{\ Displaystyle C = \ suma _ {i = 1} ^ {n} r ^ {- l_ {i}} \ równoważnik \left(m\cdot \ell _{max}\right)^{\frac {1}{m}}}

Ta granica obowiązuje dla dowolnego ${\ Displaystyle m \ in \ mathbb {N}}$ . Prawa strona to 1 asymptotycznie, więc ${\ Displaystyle \ suma _ {i = 1} ^ {n} r ^ {- l_ {i}} \ równoważnik 1}$ musi się trzymać ( w przeciwnym razie nierówność zostałaby złamana na wystarczająco dużą skalę ${\ displaystyle m}$ ).

Alternatywna konstrukcja dla konwersacji

Biorąc pod uwagę ciąg liczb naturalnych, ${\ displaystyle n}$

{\ Displaystyle \ ell _ {1} \ leqslant \ ell _ {2} \ leqslant \ cdots \ leqslant \ ell _ {n}}

spełniając nierówność Krafta, możemy skonstruować kod przedrostka w następujący sposób. Zdefiniuj i- ^te słowo kodowe, do _ja , jako pierwsze ${\ Displaystyle \ ell _ {i}}$ po punkcie podstawy (np. Przecinek dziesiętny) w podstawowej reprezentacji r ℓ

{\ Displaystyle \ suma _ {j = 1} ^ {i-1} r ^ {- \ ell _ {j}}.}

Zauważ, że według nierówności Krafta suma ta nigdy nie jest większa niż 1. Stąd słowa kodowe przechwytują całą wartość sumy. Dlatego dla j > ja , pierwsze $przedrostków$ C _j tworzą większą liczbę niż C _ja , więc kod jest wolny .

Notatki

Kraft, Leon G. (1949), Urządzenie do kwantyzacji, grupowania i kodowania impulsów z modulacją amplitudy , Cambridge, MA: MS Thesis, Electrical Engineering Department, Massachusetts Institute of Technology , hdl : 1721.1/12390 .

McMillan, Brockway (1956), „Dwie nierówności wynikające z wyjątkowej możliwości rozszyfrowania”, IEEE Trans. Inf. Teoria , 2 (4): 115–116, doi : 10.1109/TIT.1956.1056818 .

Zobacz też