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)

gdzie:

– wartościowość kodu (np. dla kodu trenrnego ),
– liczba sygnałów elementarnych,
– długość -tego sygnału elementarnego.

PrzykładEdytuj

kod   kod   kod  
  00 0 0
  01 100 10
  10 110 110
  11 11 11

W tym przypadku dla wszystkich kodów   gdyż zastosowano wszędzie kod binarny, natomiast   gdyż kody mają czteroelementowy alfabet wiadomość         Obliczając lewą stronę nierówności dla kodu   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   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   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żEdytuj