Nierówność Krafta-McMillana

Nierówność Krafta-McMillana – warunek konieczny, 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}^{K}r^{-l_{i}}\leqslant 1,$

gdzie:

$r$ – wartościowość kodu (np. dla kodu ternarnego $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}}$
$a_{1}$	00	0	0
$a_{2}$	01	100	10
$a_{3}$	10	110	110
$a_{4}$	11	11	11

W tym przypadku dla wszystkich kodów $r=2,$ gdyż zastosowano wszędzie kod binarny, natomiast $K=4,$ gdyż kody mają czteroelementowy alfabet wiadomość $a_{1},$ $a_{2},$ $a_{3},$ $a_{4}.$ Obliczając lewą stronę nierówności dla kodu ${\mathcal {A}},$ otrzymuje się 1, więc nierówność jest spełniona. Dodatkowo widać, ż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 wnioskuje się, ż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 widać, że czwarte słowo kodowe jest przedrostkiem słowa trzeciego, co eliminuje go z tych rozważań.

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

Zobacz też

• kod prefiksowy
• teoria informacji