Worldlex Wiki Identifié par John Wozencraft , le décodage séquentiel est une technique de décodage les codes convolutifs à longue contrainte . Bien que moins précis que l' algorithme de Viterbi , il permet d'économiser une quantité substantielle de mémoire . Il a notamment été utilisé pour décoder un code convolutif lors de la mission Pioneer 9 en 1968 .
Le décodage séquentiel explore le code arborescent de manière à minimiser le coût de calcul et les besoins en mémoire pour stocker l'arbre.
Il existe différentes approches de décodage séquentiel, selon le choix de la métrique et de l'algorithme. Les métriques comprennent :
- Métrique de Fano
- Métrique de Zigangirov
- Métrique de Gallager
Les algorithmes comprennent :
- Algorithme de pile
- Algorithme de Fano
- Algorithme de Creeper
Pour un canal binaire symétrique (avec une probabilité d'erreur ), la métrique de Fano peut être dérivée via le théorème de Bayes . Nous cherchons à suivre le chemin le plus probable étant donné un état exploré de l'arbre et une séquence reçue . En utilisant le langage des probabilités et le théorème de Bayes, nous voulons choisir le maximum parmi :
Nous introduisons maintenant la notation suivante :
Nous exprimons la vraisemblance comme (en utilisant la vraisemblance du canal symétrique binaire pour les premiers bits, suivie d'une distribution a priori uniforme sur les bits restants).
Nous exprimons la distribution a priori en fonction du nombre de choix de branches effectués, , et du nombre de branches issues de chaque nœud, .
Donc:
On peut également maximiser le logarithme de cette probabilité, c'est-à-dire
Cette dernière expression est la métrique de Fano. Il est important de noter qu'elle comporte deux termes : l'un basé sur le nombre de bits incorrects et l'autre sur le nombre de bits corrects. On peut donc mettre à jour la métrique de Fano simplement en ajoutant pour chaque bit incorrect et pour chaque bit correct.
taux de coupure de calcul
Pour que le décodage séquentiel soit un bon choix d'algorithme de décodage, le nombre d'états explorés doit rester faible (sinon, un algorithme explorant délibérément tous les états, comme l' algorithme de Viterbi , peut être plus approprié). Pour un niveau de bruit donné, il existe un débit de codage maximal, appelé débit de coupure de calcul, où la limite de retour arrière est finie . Pour le canal binaire symétrique :
Algorithmes
Algorithme de pile
L'algorithme le plus simple à décrire est l'« algorithme de pile », qui consiste à stocker les meilleurs chemins trouvés jusqu'à présent. Le décodage séquentiel peut introduire une erreur supplémentaire par rapport au décodage de Viterbi lorsque le chemin correct possède ou plusieurs chemins de score supérieur ; dans ce cas, le meilleur chemin est retiré de la pile et n'est plus pris en compte.
Algorithme de Fano
Le célèbre algorithme de Fano (du nom de Robert Fano ) nécessite très peu de mémoire et se prête donc parfaitement aux implémentations matérielles. Cet algorithme explore l'arbre en partant d'un point unique, en remontant et en descendant.
- L'algorithme de Fano est un algorithme de décodage séquentiel qui ne nécessite pas de pile.
- L'algorithme de Fano ne peut opérer que sur un arbre de code car il ne peut pas examiner la fusion des chemins.
- À chaque étape de décodage, l'algorithme de Fano conserve les informations relatives à trois chemins : le chemin actuel, son prédécesseur immédiat et l'un de ses chemins successeurs.
- Sur la base de ces informations, l'algorithme de Fano peut passer du chemin actuel à son prédécesseur immédiat ou au chemin successeur sélectionné ; par conséquent, aucune pile n'est nécessaire pour mettre en file d'attente tous les chemins examinés.
- Le mouvement de l'algorithme de Fano est guidé par un seuil dynamique entier d'une taille de pas fixe Δ.
- Seul le chemin dont la métrique est supérieure ou égale à John Wozencraft et B. Reiffen, Décodage séquentiel , ISBN0-262-23006-2
- Rolf Johannesson et Kamil Sh. Zigangirov, Fondements du codage convolutionnel (chapitre 6), ISBN0-470-27683-5