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 - ilość sygnałów elementarnych, li - 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ść a1, a2, a3, a4. 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 7/8, 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
