Algorithme de programmation dynamique qui calcule la séquence d'états la plus probable (chemin d'états de vraisemblance maximale) dans un treillis à états finis en accumulant récursivement des métriques de chemin additives et en retenant un seul chemin « survivant » par état à chaque pas de temps ; utilisé couramment pour la détection de séquence ML des codes convolutionnels et des canaux à états finis.

Principe

En exploitant la structure markovienne (à états finis) du treillis, l'algorithme de Viterbi évite l'énumération exponentielle des séquences d'états : à chaque pas il calcule des métriques de branche, les ajoute aux métriques de chemin prédécesseures et conserve uniquement le meilleur chemin entrant (survivant) par état, donnant une complexité linéaire en longueur de séquence et proportionnelle au nombre d'états.

Démonstration

Situation : décodage d'un code convolutionnel de taux 1/2 et longueur de contrainte K impliquant 2^(K−1) états de treillis. Reconnaissance : représentation du treillis et des métriques de branche issues d'indices reçus durs ou mous. Action : parcourir le treillis, mettre à jour les métriques de chemin, stocker les survivants, effectuer un rétro‑traçage après terminaison ou utiliser une fenêtre glissante pour émettre des bits décodés. Conséquence : l'algorithme fournit la séquence ML (optimale en séquence) sous le modèle de canal et de code supposé, avec coût de calcul croissant linéairement avec la longueur du cadre mais exponentiellement avec la mémoire de l'encodeur (nombre d'états).

Mauvaise application

Utiliser l'algorithme de Viterbi lorsque l'objectif est d'obtenir des probabilités MAP bit‑à‑bit (minimiser le taux d'erreur binaire) plutôt que l'optimisation de séquence, ou considérer la sortie de Viterbi comme fournissant des fiabilités bit sans traitement de sortie douce supplémentaire. L'erreur sémantique est de confondre optimalité de séquence et optimalité bit à bit et d'employer des survivants durs comme mesures probabilistes.

Conséquence

Le décodage Viterbi fournit la séquence d'états ML pour des modèles à états finis et minimise donc la probabilité d'erreur de séquence sous ces hypothèses ; il est efficace pour des nombres d'états modérés et constitue un fondement de nombreux récepteurs. Ses limites incluent la mémoire et le calcul croissants avec le nombre d'états, la latence de décodage due au rétro‑traçage et l'absence d'outputs mous directs (traitées par SOVA/BCJR) lorsqu'une fiabilité bit‑à‑bit est requise.

Inversion

Lorsqu'il s'agit de minimiser la probabilité d'erreur bit à bit ou lorsque des postérieurs mous sont requis pour un traitement itératif ultérieur, les algorithmes calculant des postérieurs symbole/bit (BCJR) ou les variantes Viterbi à sortie souple (SOVA) sont préférables. Pour des canaux à mémoire extrêmement longue, l'espace d'états du treillis peut devenir impraticable, imposant des approximations telles que l'état tronqué ou la fenêtre glissante.

Limite

Clairement dans : détection de séquence ou décodage pour codes convolutionnels et canaux à états finis représentés par un treillis de nombre d'états gérable. Cas limite : Viterbi tronqué ou fenêtre glissante qui réduit la croissance des états au prix de l'optimalité. Clairement hors : détecteurs symbole‑par‑symbole qui ignorent la mémoire du treillis, et algorithmes de calcul complet des postérieurs (BCJR) lorsque des postérieurs bit‑à‑bit sont nécessaires.

Tension sémantique

Optimalité de séquence vs optimalité bit‑à‑bit et complexité vs exactitude : Viterbi fournit une solution ML de séquence efficace mais ne minimise pas l'erreur bit ni ne fournit directement l'information postérieure complète ; atteindre d'autres métriques d'erreur ou sorties souples requiert d'autres algorithmes ou extensions plus coûteuses.

Synthèse

L'algorithme de Viterbi est la méthode canonique et efficace pour obtenir le chemin d'états ML dans des modèles à états finis : il transforme une recherche exponentielle en une récursion par pas, mais son usage suppose que l'optimalité au niveau de la séquence et la complexité d'états disponible compensent l'absence d'information postérieure bit‑à‑bit.