L'algorithme de Viterbi a permis à chaque téléphone mobile de décoder son propre signal

La communication numérique sur une liaison sans fil est un combat contre le bruit, qui peut corrompre les bits reçus par une antenne. Le remède évident consiste à ajouter un code correcteur d'erreurs, mais son décodage exige un moyen de déterminer, à partir d'un flux reçu bruité, quel message a réellement été envoyé.

L'algorithme de Viterbi de 1967 faisait exactement cela. Un encodeur convolutif contraint l'émetteur à parcourir un ensemble fini d'états, et le récepteur maintient un treillis de ces états ; à chaque étape, il ne conserve que le chemin le moins coûteux menant à chaque état, si bien qu'à la fin il a trouvé l'unique message le plus probable plutôt que de choisir chaque bit indépendamment.

En rendant praticables des codes de courte longueur de contrainte, l'algorithme a rendu la correction d'erreurs sans voie de retour suffisamment peu coûteuse pour être déployée dans de vraies radios. Il a transformé un vague « quel était le message ? » en une recherche propre par programmation dynamique, et il sert aujourd'hui à séparer la voix et les données du bruit de fond.

Choisir la séquence d'états cachée la plus probable

Ne conserver que l'unique chemin le moins coûteux menant à chaque état fait que la recherche prend un temps linéaire en la longueur du message.

Il récupère la séquence de maximum de vraisemblance à partir de données bruitées sans supputations bit par bit.

Les codes convolutifs n'apportent une véritable puissance de correction d'erreurs que lorsqu'ils sont décodés de cette manière.

Lorsqu'un signal est trop bruité pour être lu directement, reconstruisez l'unique séquence la plus probable dont il pourrait provenir ; la structure que vous avez ajoutée rend cette recherche presque sans effort.

L'algorithme de Viterbi est utilisé dans la grande majorité des téléphones mobiles dans le monde ainsi que dans les récepteurs satellites, l'enregistrement magnétique, la reconnaissance vocale et l'analyse de l'ADN ; Viterbi a ensuite cofondé Qualcomm en 1985, et l'algorithme a contribué à rendre praticables le CDMA et la téléphonie cellulaire numérique.