Automate de codage des données

Le fonctionnement de cet automate est décrit dans la figure 44 sous la forme d'un registre à décalage mémorisant les données $e(t)$ à émettre et générant par des fonctions ``ou exclusif'' les signaux $s_1(t)$ et $s_2(t)$.

Figure 44: Schéma de la génération des données émises dans un exemple simple de code convolutionnel

On peut aussi représenter ce fonctionnement sous la forme d'un graphe de transition (figure 45.

Figure 45: Automate représentant le fonctionnement du codeur

On peut en représenter le fonctionnement au cours du temps sous la forme d'un treillis (figure 46. Dans ce treillis, les états de l'automate sont représentés en abscisse et le temps en ordonnée. Une transition en fonction d'une entrée $e(t)$ est décrite par une branche indiquant la transition d'état sur laquelle on a aussi indiqué les sorties émises sous la forme $e(t)/s_(t)s_2(t)$. Dans cette représentation on donne l'état initial de l'automate qui sera unique et a priori connu du récepteur.

Figure 46: Réprésentation du fonctionnement sous la forme d'un treillis

Fonctionnement du récepteur Le récepteur possède un automate identique à celui de l'émetteur. L'objectif à atteindre est d'engendrer par cet automate une séquence aussi proche que possible (au sens de la distance de Hamming) de la séquence reçue.

Figure 47: Principe du décodage par le récepteur

Nous décrivons le fonctionnement sur un exemple. Supposons que la séquence émise $s_1(t)s_2(t)$ était

$$111000010101101100$$ (75)

et que la séquence reçue est $s''_1(t)s''_2(t)$

$$001000010101101100$$ (76)

(les deux premiers bits sont erronnés). Au début du décodage, l'automate du récepteur est dans le même état initial que celui de l'émetteur. A chaque instant $t$, il génère deux hypothèses possibles pour l'entrée: ($e'(t)=0$ et $e'(t)=1$, et pour chaque état possible, il produit deux sorties $s'_1(t)s'_2(t)$. On compare ces deux sorties à la séquence reçue $s''_1(t)s''_2(t)$ et on calcule la distance de Hamming entre ces deux signaux. A l'instant $t=0$, il y a un seul état possible $00$.
Pour $e(0)=0$, on génère $s'_1(0)=0, s'_2(0)=0$. La distance au signal reçu est égale à $0$.
Pour $e(0)=1$, on génère $s'_1(0)=1, s'_2(0)=1$. La distance au signal reçu est égale à $2$. A l'instant $t=1$, il y a deux états possibles ($00$ et $10$).
Dans l'état $00$, pour $e(0)=0$, on génère $s'_1(1)=0, s'_2(1)=0$. La distance au signal reçu : $1$.
Dans l'état $00$, pour $e(0)=1$, on génère $s'_1(1)=1, s'_2(1)=1$. La distance au signal reçu : $1$.
Dans l'état $10$, pour $e(0)=0$, on génère $s'_1(1)=1, s'_2(1)=0$. La distance au signal reçu : $2$.
Dans l'état $10$, pour $e(0)=1$, on génère $s'_1(1)=0, s'_2(1)=1$. La distance au signal reçu : $2$. La distance de Hamming porte sur les messages à partir de leur début et jusqu'à l'instant $t$. La distance de Hamming à l'instant $t$ est égale à la distance de Hamming à l'instant $t-1$ à laquelle on ajoute la distance entre $s'_1(t)s'_2(t)$ et $s''_1(t)s''_2(t)$. A l'instant $t=2$, il y a quatre états possibles ($00$ et $10$).
On effectue les mêmes calculs que précédemment pour ces quatre états, ce qui produit huit sorties possibles.
état $00$, pour $e(0)=0$, on génère $s'_1(1)=0, s'_2(1)=0$. La distance au signal reçu : $1$.
état $00$, pour $e(0)=1$, on génère $s'_1(1)=1, s'_2(1)=1$. La distance au signal reçu : $3$.
état $10$, pour $e(0)=0$, on génère $s'_1(1)=1, s'_2(1)=0$. La distance au signal reçu : $2$.
état $10$, pour $e(0)=1$, on génère $s'_1(1)=0, s'_2(1)=1$. La distance au signal reçu : $2$.
état $01$, pour $e(0)=0$, on génère $s'_1(1)=1, s'_2(1)=1$. La distance au signal reçu : $4$.
état $01$, pour $e(0)=1$, on génère $s'_1(1)=0, s'_2(1)=0$. La distance au signal reçu : $2$.
état $11$, pour $e(0)=0$, on génère $s'_1(1)=0, s'_2(1)=1$. La distance au signal reçu : $5$.
état $11$, pour $e(0)=1$, on génère $s'_1(1)=1, s'_2(1)=0$. La distance au signal reçu : $5$. On remarque qu'à l'instant $t=3$, l'automate est maintenant dans son régime permanent. Chaque état peut être atteint par deux entrées différentes. Par exemple, on peut atteindre
l'état $01$ à partir de l'état $10$ avec l'entrée $0$, la distance calculée pour ce chemin est $2$
l'état $01$ à partir de l'état $11$ avec l'entrée $0$, la distance calculée pour ce chemin est $5$. A ces deux chemins sont associés des distances en général différentes. Le principe de Viterbi est de ne retenir parmi ces deux chemins que celui qui correspond à la distance de Hamming la plus petite. Par exemple pour l'état $01$, on ne retient que le chemin provenant de l'état $10$ car il correspond à une distance de Hamming de $2$, l'autre chemin correspondant à une distance de Hamming de $5$. On sélectionne ainsi pour chacun des état un seul chemin entrant. On réitère l'opération jusqu'à la fin du message. En principe, il faut que la fin du message soit une séquence bien définie pour que l'état final de l'automate d'émission soit un état connu du récepteur. On compare alors les distances de Hamming entre séquences retenues pour chacun des états à l'instant final $T$ (une séquence par état) et on considère que le message émis était celui qui correspond à la distance la plus petite. La séquence ainsi retenue dans l'exemple est bien la séquence émise, malgré les deux erreurs dans le message reçu. La distance de Hamming entre le message reçu et le message qui est généré par la séquence d'entrées retenue est bien égale à $2$. L'intérêt majeur de cet algorithme est dû esssentiellement au résultat important de Viterbi: le chemin sélectionné par cette méthode permet de trouver la séquence d'entrée la plus vraisemblable lorsque le canal est sans mémoire (pas d'interférences entre données successives). Il donne la séquence $ê(t)$ qui maximise la fonction de vraisemblance

$$\sum_{t=0}^{T}\log_2 p[s''_1(t),s''_2(t)/e'(t)]$$ (77)

où $p[s''_1(t),s''_2(t)/e'(t)]$ est la probabilité d'avoir reçu $s''_1(t),s''_2(t)$ lorsque $e'(t)$ a été émis. Les codes convolutionnels sont bien adaptés à la correction d'erreurs isolées alors que les codes en blocs (Reed Solomon par exemple) sont mieux adaptés à la correction de paquets d'erreurs. En général, on associe les deux techniques comme dans le téléphone mobile GSM.

Figure 48: Sélection des chemins dans le treillis: parmi les deux chemins entrant dans un état, on sélectionne celui qui correspond à la distance de Hamming la plus petite