Nierówność Krafta-McMillana

Nierówność Krafta-McMillana jest warunkiem koniecznym, który musi spełniać kod, aby był jednoznacznie dekodowalny. Dodatkowo jest to warunek konieczny, ale nie wystarczający aby kod był dekodowalny bez opóźnień; tak więc istnieją kody które spełniają tą nierówność, lecz nie są jednoznacznie dekodowalne bez opóźnienia (są jednoznacznie dekodowalne ale z opóźnieniami).

$\sum_{i=1}^Kr^{-l_i}\leq1$

gdzie: r - wartościowość kodu (np. dla kodu ternrnego r=3), K - liczba sygnałów elementarnych, l_i - długość i-tego sygnału elementarnego

Przykład

	kod $\mathcal{A}$	kod $\mathcal{B}$	kod $\mathcal{C}$
a1	00	0	0
a2	01	100	10
a3	10	110	110
a4	11	11	11

Mamy więc w naszym przypadku dla wszystkich kodów r=2, gdyż zastosowaliśmy wszędzie kod binarny, natomiast K=4, gdyż nasze kody mają czteroelementowy alfabet wiadomość a₁, a₂, a₃, a₄. Obliczając lewą stronę nierówności dla kodu $\mathcal{A}$, otrzymujemy 1, więc nierówność jest spełniona. Dodatkowo widzimy, że ma on wszystkie ciągi kodowe o stałej długości i do tego każdy z nich jest inny. Na tej podstawie wnioskujemy, że jest to kod jednoznacznie dekodowalny, bez opóźnienia.

Dla kodu $\mathcal{B}$ lewa strona wynosi 1, więc ponownie spełniona jest nierówność Krafta-McMillana, lecz widzimy, że czwarte słowo kodowe jest przedrostkiem słowa trzeciego, co eliminuje go z naszych rozważań.

Natomiast dla kodu $\mathcal{C}$ lewa strona wynosi 9/8, czyli nierówność nie jest spełniona, możemy więc jednoznacznie określić, że nie jest to kod jednoznacznie dekodowalny bez opóźnienia.

Zobacz też

• kod prefiksowy
• teoria informacji
• teoria kodów