Nierówność Krafta-McMillana

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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, li - długość i-tego sygnału elementarnego

Przykład[edytuj | edytuj kod]

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ść a1, a2, a3, a4. 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ż[edytuj | edytuj kod]