PROJET MOCAT

Architecture générale du décodeur de Viterbi et implémentation

L'implémentation du décodeur de Viterbi se fera selon la structure suivante:

**Figure 6:** Décodeur de Viterbi
$\includegraphics[scale=0.8]{bloc_vit.ps}$

Les trois blocs ont été décrit précédemment :

BMC Calcul des Métriques de Branches
ACS Calcul des Métriques de Chemin et des survivants
SSU Stockage et remontés des survivants

Calcul des métriques de branches

Ce bloc calcule, comme nous l'avons vu précédemment, la vraisemblance des échantillons d'entrée par rapport aux valeurs attendues. Cette vraisemblance se traduit par une Métrique de Branche (MB) et à chaque noeud du treillis correspond une MB. Mais comme les n échantillons attendus ne peuvent prendre que deux valeurs ( 0 ou 1), il n'y a que 2ⁿ valeurs de MB possibles ( soit 4 pour un code 1/2).

**Figure 7:** Rom Métriques de Branche
$\includegraphics[scale=0.6]{rommb.ps}$

Selon le débit visé l'implémentation du calcul des MB peut être faite à l'aide d'un additionneur, si toutes les MB sont calculées en série, ou par une ROM si elles sont évaluées en parallèles.

Il peut être intéressant pour diminuer la complexité du décodeur de Viterbi d'effectuer la compression des MB (passer de b= 4 à 3 bits, pour des échantillons d'entrée sur e=3 bits). Cela peut aisément se faire par une ROM.

ACS: Calcul des Métriques de Chemin et des survivants

Ce bloc constitue le coeur de l'algorithme de Viterbi et remplit 4 fonctions:

calcul, mise à jour des métriques de chemin
choix du survivant
renormalisation
détermination du noeud de référence pour la remontée des survivants

calcul des métriques de chemin

Ce calcul traduit les probabilités cumulées de faire partie du chemin décrit par la séquence émise.

Pour ce calcul il nous faut donc faire l'addition des MC et des MB, la comparaison des deux MC obtenues et la sélection de la plus faible.
MC(2n) = min [ MC(n) + MB(0,0), MC(n+2^k-1) + MB(0,1) ]
MC(2n+1) = min [ MC(n) + MB(1,0), MC(n+2^k-1) + MB(1,1) ]

choix du survivant

Ensuite il faut que le résultat de la comparaison reflète l'état du bit sortant du registre à décalage du codeur. Par exemple si la decision relative au noeud (2n) est 1, cela signifie qu'entre les deux branches aboutissant au noeud, c'est la branche MC(n+2^k-1) qui a été sélectionnée. Et le bit sorti du registre lors de cette transition est bien un '1'.

renormalisation

Les métriques de chemin prennent des valeurs croissantes. Pour ne pas dépasser la valeur maximale du champ arithmétique désiré (2^c-1, avec c nombre de bits des MC), il est nécessaire de soustraire, à chaque fois que le seuil est atteint, une valeur commune à toutes les métriques de chemin. Cette opération s'appelle la renormalisation.

Elle peut s'effectuer de plusieurs manières. Il faut veiller dans tous les cas à ce que la métrique maximale reste bien maximale après renormalisation. Pour ce faire les métriques sont saturées à 2^c-1, ce qui n'affecte que les noeuds peu probables. La façon la plus simple d'effectuer la renormalisation consiste à définir:

un seuil de renormalisation, à partir duquel toutes les métriques sont renormalisées, en général fixé à 2^c-1.
un pas de renormalisation fixe, qui est la valeur à soustraite à toutes les métriques lorsque le seuil est atteint. On peut aussi soustraire systématiquement lors du calcul des Métriques Cumulées la métrique la plus faible, et ainsi toujours avoir une métrique nulle.

détermination du noeud de référence

Le noeud optimum est celui ayant la plus faible métrique de chemin. L'identifier signifie comparer toutes les métriques entre elles, ce qui est difficile si la fréquence de traitement est élevée. Une solution intermédiaire consiste à prendre un noeud sous optimal, ayant une métrique inférieure à un certain seuil. La solution la plus simple est de prendre un noeud de départ prédéfini et constant.

implémentation

L'implémentation de ce bloc est directement fonction de la fréquence de fonctionnement du décodeur.
Deux traitements sont possibles: le traitement parallèle ou le traitement série. Dans les deux cas la brique de base, ou le processeur élémentaire (PE), sera le bloc ACS.

Ce processeur élémentaire est en général un double ACS traitant le treillis par deux noeuds. La complexité de ce processeur élémentaire dépend des paramètres précédents. Si e=3, b=4 (nombre de bits des MB) alors c=7 (nombre de bits des MC) et la complexité s'estime par Cacs=(100 x c) = 700 portes.

**Figure 9:** ACS double
$\includegraphics[scale=0.7]{ACS_simple.ps}$

Le nombre de processeurs à utiliser va dépendre du débit visé. Pour un débit élevé on va utiliser un traitement parallèle alors que pour un débit faible on utilisera un traitement série.

Le traitement parallèle:
Il faut 2^k-1 processeurs élémentaire interconnectés entre eux (64 ACS, ou 32 ACS doubles pour k=7). La complexité est importante et la densité des portes faible à cause des multiples interconnexions entre les pe. Il faut aussi ajouter la gestion de la renormalisation et celle du noeud de départ. Enfin, 2^k-1 fils vont relier le bloc ACS au bloc SSU, pour le traitement des survivants.

Le traitement série:
Un seul pe traite les 2^k-1 noeuds en série. Il est indispensable d'associer au pe une mémoire de stockage des métriques de chemins, 2 métriques étant lues pendant que 2 sont écrites. Il faut deux groupes de mémoires fonctionnant en flip-flop (a en lecture et b en écriture, puis inversement). Cette gestion des RAM et du PE est complexe.

Le traitement mixte:
Une configuration intermédiaire est possible. Le problème consiste à allouer de façon optimale les noeuds à traiter aux différents processeurs élémentaires pour diminuer les interconnexions. Et il faut également solutionner le problème du stockage des Métriques Cumulées.

Stockage et remontée des survivants

Ce bloc assure le stockage, à chaque cycle, de 2^k-1 résultats de comparaison et permet de reconstituer la séquence émise par la relecture des survivants stockés.

Deux méthodes principales:

L'échange de registres. Cette méthode utilise pour chacun des 2^k-1 états du treillis un registre à décalage mémorisant les LT décisions du chemin conduisant à l'état considéré. Les différents registres sont interconnectés entre eux, de la même manière que le treillis défini par le code. A chaque durée symbole, les contenus des différents registres sont inter changés suivant la valeurs des survivants issus des ACS, le plus anciens des symboles de chaque registre étant dirigés vers le module de sortie.

**Figure 11:** Echange de registres
$\includegraphics[scale=0.5]{real_reg_exc.ps}$

Chaînage arrière. A partir du noeud de départ (soit fixe, soit le noeud ayant la métrique cumulée minimale) on reconstitue la séquence émise en retraçant, à travers le treillis, le chemin effectué par cette séquence. Ce chemin se matérialise par une suite de branches entre les différents noeuds par lequel le chemin passe. Les branches sont identifiées par le survivant. Si l'on concatène tous les survivants obtenus le long de ce chemin on reconstitue la séquence. Dans la méthode précédente on reconstitue instantanément la séquence alors qu'ici on la reconstitue pas à pas en utilisant un adressage similaire à l'adressage indirect informatique. Le noeud de départ de (k-1) bits, permet de choisir parmi les 2^k-1 survivants. La valeur du survivant va permettre de calculer la valeur du noeud antécédent, suivant que le survivant est 0 ou 1 on sélectionne une des deux branches qui arrivent au noeud. La nouvelle valeur du noeud est obtenu en décalant de 1 bit le noeud courant et en insérant le survivant.

**Figure 12:** Noeud suivant
$\includegraphics[scale=0.6]{chiane_arr.ps}$

$\beta = \frac{LT+d}{d}$

$\beta$

^k-1

mode mixte