Nierówność Krafta-McMillana

Niektóre z zamieszczonych tu informacji wymagają weryfikacji. Uwagi: patrz dyskusja. Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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)

${\displaystyle \sum _{i=1}^{K}r^{-l_{i}}\leqslant 1,}$

gdzie:

${\displaystyle r}$ – wartościowość kodu (np. dla kodu ternarnego ${\displaystyle r=3}$),

${\displaystyle K}$ – liczba sygnałów elementarnych,

${\displaystyle l_{i}}$ – długość ${\displaystyle i}$-tego sygnału elementarnego.

Przykład

W tym przypadku dla wszystkich kodów ${\displaystyle r=2,}$ gdyż zastosowano wszędzie kod binarny, natomiast ${\displaystyle K=4,}$ gdyż kody mają czteroelementowy alfabet wiadomość ${\displaystyle a_{1},}$ ${\displaystyle a_{2},}$ ${\displaystyle a_{3},}$ ${\displaystyle a_{4}.}$ Obliczając lewą stronę nierówności dla kodu ${\displaystyle {\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 ${\displaystyle {\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 ${\displaystyle {\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