Der Viterbi-Algorithmus ist ein 1967 von Andrew J. Viterbi veröffentlichter Decodieralgorithmus für Faltungscodes. Er findet in einem Trellis-Diagramm den Pfad mit der größten Wahrscheinlichkeit — die Maximum-Likelihood-Decodierung: Statt alle möglichen Sequenzen durchzuprobieren, verwirft er schrittweise aussichtslose Teilpfade und bleibt dadurch auch bei langen Nachrichten praktikabel.
So arbeitet der Algorithmus
Das Trellis hat pro Zeitschritt 2m Zustände (m = Speicherstufen des Codes). Der Viterbi-Algorithmus läuft in drei Phasen:
- Metrik-Berechnung: Für jeden Zustandsübergang wird eine Pfadmetrik aus der Distanz zwischen empfangenem und erwartetem Codebit gebildet — bei Hard Decision die Hamming-Distanz, bei Soft Decision eine euklidische Distanz beziehungsweise ein Log-Likelihood-Wert.
- Pfadauswahl (Survivor): Von den ankommenden Pfaden jedes Zustands überlebt nur der mit der kleinsten Metrik, alle anderen werden verworfen.
- Rückverfolgung (Traceback): Am Ende wird der durchgehend günstigste Pfad rückwärts verfolgt und daraus die decodierte Bitfolge abgelesen.
Der Rechenaufwand wächst nur linear mit der Nachrichtenlänge — jeder Zeitschritt kostet einen Vergleich pro Zustand, unabhängig davon, wie viele Takte vergangen sind.
Hard Decision vs. Soft Decision
Bei Hard Decision entscheidet der Demodulator vor der Decodierung bereits hart auf 0 oder 1; bei Soft Decision reicht er mehrstufige Vertrauenswerte weiter. Soft Decision mit unquantisierten Werten bringt je nach Kanal rund 2 dB Codiergewinn gegenüber Hard Decision und ist in modernen Empfängern Standard.
Anwendungen
Der Viterbi-Algorithmus decodiert die Faltungscodes von GSM, UMTS, WLAN (802.11a/g) und DVB-T. Dieselbe Dynamische-Programmierung-Idee steckt auch in der Sprach- und Mustererkennung mit verborgenen Markov-Modellen (HMM). Verwandte Grundlagen: Kanalcodierung, Vorwärtsfehlerkorrektur, Turbo-Code.