Nierówność Krafta-McMillana


Nierówność Krafta-McMillana w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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)

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

gdzie:

r {\displaystyle r} – wartościowość kodu (np. dla kodu trenrnego r = 3 {\displaystyle r=3} ), K {\displaystyle K} – liczba sygnałów elementarnych, l i {\displaystyle l_{i}} – długość i {\displaystyle i} -tego sygnału elementarnego.

Przykład | edytuj kod

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

Na podstawie artykułu: "Nierówność Krafta-McMillana" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy