Viterbi-Algorithmus

Der Viterbi-Algorithmus ist ein Algorithmus der dynamischen Programmierung zur Bestimmung der wahrscheinlichsten Sequenz von verborgenen Zuständen bei einem gegebenen Hidden Markov Model (HMM) und einer beobachteten Sequenz von Symbolen. Diese Zustandssequenz wird auch als Viterbi-Pfad bezeichnet. Er wurde von Andrew J. Viterbi 1967 zur Dekodierung von Faltungscodes entwickelt, er fiel quasi als Nebenprodukt bei der Analyse der Fehlerwahrscheinlichkeit von Faltungscodes ab. G. D. Forney leitete daraus 1972 den Optimalempfänger für verzerrte und gestörte Kanäle her. Der Viterbi-Algorithmus wird heutzutage zum Beispiel in Mobiltelefonen oder Wireless LANs zur Fehlerkorrektur der Funkübertragung verwendet, ebenso in Festplatten, da bei der Aufzeichnung auf die Magnetplatten ebenfalls Übertragungsfehler entstehen. Der Algorithmus ist in der Nachrichtentechnik und Informatik weit verbreitet: Die Informationstheorie, Bioinformatik, Spracherkennung und Computerlinguistik verwenden häufig den Viterbi-Algorithmus.