Ein dynamischer Programmieralgorithmus, der die einzelwahrscheinlichste Zustandsfolge (den Maximum‑Likelihood‑Zustandspfad) in einem endlichen Zustands‑Trellis berechnet, indem er additive Pfadmetriken rekursiv aufsummiert und in jedem Zeitschritt pro Zustand genau einen Überlebenspfad (Survivor) behält; weit verbreitet für ML‑Sequenzdetektion von konvolutionalen Codes und endlichen Zustandskanälen.

Prinzip

Indem die markovsche (endliche Zustands‑) Struktur des Trellis genutzt wird, vermeidet der Viterbi‑Algorithmus die exponentielle Aufzählung von Zustandsfolgen: Er berechnet in jedem Schritt Zweigmetriken, addiert sie zu Vorgänger‑Pfadmetriken und behält nur den besten eingehenden Pfad pro Zustand, wodurch die Komplexität linear in der Sequenzlänge und proportional zur Anzahl der Zustände wird.

Demonstration

Situation: Decodierung eines Rate‑1/2‑konvolutionalen Codes mit Constraint‑Länge K, was 2^(K−1) Trellis‑Zustände ergibt. Erkennung: Trellis‑Darstellung der Zustandsübergänge und Zweigmetriken aus empfangenen harten oder weichen Beobachtungen. Aktion: Das Trellis durchlaufen, Pfadmetriken aktualisieren, Survivors speichern, Rückverfolgung nach Terminierung durchführen oder mit gleitendem Fenster decoded Bits ausgeben. Folge: Der Algorithmus liefert die ML‑Sequenz (sequenzoptimal) unter dem angenommenen Kanal‑ und Codemodell, mit Rechenaufwand, der linear mit der Rahmenlänge, aber exponentiell mit dem Encoder‑Speicher (Zustandszahl) wächst.

Fehlanwendung

Den Viterbi‑Algorithmus einzusetzen, wenn das Ziel bitweise MAP‑Wahrscheinlichkeiten (Minimierung der Bitfehlerrate) statt sequenzweiser ML‑Optimierung ist, oder das Viterbi‑Ergebnis als Posterior‑Bit‑Zuverlässigkeiten zu interpretieren ohne zusätzliche Soft‑Output‑Bearbeitung. Der semantische Fehler besteht darin, Sequenz‑Optimalität mit Bit‑Optimalität zu verwechseln und harte Survivors als Wahrscheinlichkeitsmaß zu missbrauchen.

Konsequenz

Viterbi‑Decodierung liefert die ML‑Zustandsfolge für endliche Zustandsmodelle und minimiert damit die Sequenzfehlerrate unter diesen Annahmen; sie ist effizient für moderate Zustandszahlen und grundlegend für viele Empfänger. Einschränkungen sind Speicher‑ und Rechenaufwand, der mit der Zustandszahl wächst, Latenz durch Rückverfolgung und das Fehlen direkter Soft‑Outputs (angegangen durch SOVA/BCJR‑Varianten), wenn bitweise Zuverlässigkeiten benötigt werden.

Umkehrung

Wenn die Minimierung der bitweisen Fehlwahrscheinlichkeit oder die Bereitstellung weicher Posterior‑Informationen erforderlich ist, sind Algorithmen, die symbol‑ oder bitweise Posterioren (BCJR) berechnen, oder Soft‑Output‑Viterbi‑Varianten (SOVA) vorzuziehen. Bei Kanälen mit extrem langer Gedächtnislänge kann der Trellis‑Zustandsraum unpraktikabel groß werden, wodurch Näherungen wie Trunkierung des Zustandsraums oder gleitende Fenster nötig sind.

Abgrenzung

Eindeutig innerhalb: Sequenzdetektion oder Decodierung für konvolutionale Codes und endliche Zustandskanäle, darstellbar durch einen Trellis mit handhabbarer Zustandszahl. Randfall: getrunkener oder gleitender Fenster‑Viterbi, der Zustandsexplosion reduziert, aber Optimalität opfert. Eindeutig außerhalb: symbolweise Detektoren ohne Trellis‑Speicher und vollständige Posterior‑Berechnungsalgorithmen (BCJR) wenn bitweise Posterioren benötigt werden.

Semantische Spannung

Sequenz‑Optimalität vs. bitweise Optimalität und Komplexität vs. Genauigkeit: Viterbi liefert eine effiziente ML‑Sequenzlösung, minimiert aber nicht die Bitfehlerrate und liefert keine direkten Posterioren; für andere Metriken oder Soft‑Outputs sind andere/erweiterte Algorithmen mit höheren Kosten erforderlich.

Synthese

Der Viterbi‑Algorithmus ist die kanonische effiziente Methode zur Ermittlung des ML‑Zustandspfads in endlichen Zustandsmodellen: Er wandelt exponentielle Sequenzsuche in eine pro‑Schritt Rekursion um, doch seine Wahl setzt voraus, dass sequenzbezogene Optimalität und verfügbare Zustandskomplexität das Fehlen bitweiser Posteriorinformation rechtfertigen.