Algorytm Viterbiego

Ten artykuł od 2012-11 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Algorytm Viterbiego – algorytm dekodujący, o strategii programowania dynamicznego, opracowany przez Andrew Viterbiego i opublikowany przez niego w 1967 roku w IEEE Transactions on Information Theory, IT-13 w artykule Error bounds for convolutional codes and an asymptotically optimum decoding algorithm (s. 260–269).

Jego pierwszym zastosowaniem było, i nadal jest, dekodowanie kodów splotowych. Jednak stosowany jest również w innych zaawansowanych technologiach telekomunikacyjnych, np. jako odbiornik nieliniowy dla kanału z interferencją międzysymbolową.

Stosowany jest także w kontekście ukrytych modeli Markowa (ang. HMM) do dekodowania sekwencji stanów ukrytych, które z największym prawdopodobieństwem mogły dać sekwencję obserwacji.

Działanie tego algorytmu oparte jest o kryterium najwyższej wiarygodności, a jego ideą jest to, że optymalna ścieżka dojścia przez dekoder do aktualnego stanu składa się ze ścieżki o najmniejszej metryce dojścia do któregoś ze stanów poprzednich oraz przejścia do aktualnego stanu. Jak widać proces ten można wyrazić iteracją.

Im dłuższy czas obserwacji i działania tego algorytmu, tym bardziej wiarygodny wynik otrzymujemy. Można jednak zauważyć, że już po mniej więcej 3L do 5L krokach (gdzie L jest długością wymuszenia kodu) otrzymujemy na wykresie kratowym, wspólną ścieżkę, tzw. pień, dla kolejnych stanów. Możemy więc ograniczyć opóźnienie dekodowania właśnie do tego okresu i przyjąć wynik za wystarczająco dokładny.

Algorytm Viterbiego sprawdza się zarówno w przypadku dekodowania twardo-, jak również miękkodecyzyjnego (przy użyciu algorytmu SOVA – Soft Output Viterbi Algorithm).

Nie jest on jedynym algorytmem dekodowania kodów splotowych, aczkolwiek na pewno najbardziej popularnym ze względu na łatwość jego realizacji sprzętowej.