Algorytm Viterbiego
Algorytm Viterbiego to dekodujący algorytm, który opiera się na strategii programowania dynamicznego. Został on stworzony przez Andrew Viterbiego i opublikowany w 1967 roku w czasopiśmie IEEE Transactions on Information Theory w artykule pt. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm (s. 260–269).
Pierwotnym zastosowaniem tego algorytmu było dekodowanie kodów splotowych, a jego rola w tej dziedzinie trwa do dziś. Oprócz tego, algorytm ten jest wykorzystywany w wielu zaawansowanych technologiach telekomunikacyjnych, na przykład jako nieliniowy odbiornik w kanałach z interferencją międzysymbolową.
Algorytm Viterbiego znajduje również zastosowanie w kontekście ukrytych modeli Markowa (ang. HMM), gdzie służy do dekodowania sekwencji stanów ukrytych, które mają największe prawdopodobieństwo wygenerowania danych obserwacji.
Jego działanie opiera się na kryterium najwyższej wiarygodności, a kluczową ideą jest to, że optymalna ścieżka prowadząca przez dekoder do aktualnego stanu składa się z najkrótszej metryki dojścia do jednego z poprzednich stanów oraz przejścia do stanu bieżącego. Proces ten można przedstawić w formie iteracji.
W miarę wydłużania czasu obserwacji i działania algorytmu, uzyskiwane wyniki stają się coraz bardziej wiarygodne. Warto zauważyć, że już po czasie wynoszącym od około 3L do 5L kroków (gdzie L oznacza długość wymuszenia kodu), na wykresie kratowym możemy dostrzec wspólną ścieżkę, znaną jako pień, dla kolejnych stanów. Dzięki temu możemy ograniczyć opóźnienie dekodowania do tego okresu i uznać wynik za wystarczająco dokładny.
Algorytm Viterbiego sprawdza się zarówno w przypadku dekodowania twardego, jak i miękkodecyzyjnego (przy zastosowaniu algorytmu SOVA – Soft Output Viterbi Algorithm).
Chociaż algorytm Viterbiego nie jest jedynym sposobem dekodowania kodów splotowych, jest z pewnością najbardziej popularnym, głównie ze względu na prostotę jego implementacji sprzętowej.
