Nierówność Krafta-McMillana

Z Wikipedii

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

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

[edytuj] Przykład

	kod	kod	kod
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 , 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 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 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.

[edytuj] Zobacz też

• kod prefiksowy
• teoria informacji
• teoria kodów