Application aux Futurs Systèmes Multimédia par Satellite en Bande Ka'> A. Algorithme de Viterbi pour les CPM

A. Algorithme de Viterbi pour les CPM

Le but d'un algorithme de Viterbi consiste à estimer la séquence qui correspond au chemin de plus faible métrique dans le treillis. Dans notre cas, la métrique d'une transition est donnée par:

$\displaystyle d(r_k,c_k)=\left(r_k-m\right)\Lambda^{-1}\left(r_k-m\right)^{*}$

Cette distance est associée au produit scalaire défini par

$\displaystyle X\otimes Y=X\Lambda^{-1}Y$

Il apparît que le calcul de la métrique de tous les chemins (une suite de transitions) dans le treillis nécessite une très grande complexité et qu'elle est pratiquement irréalisable. L'algorithme de Viterbi permet une estimation quasi-optimale, au sens du maximum de vraisemblance, du chemin le plus court avec une complexité nettement plus réduite. Cet algorithme permet de calculer les métriques d'une façon progressive en fonction de l'avancement dans le treillis. Le processus de décodage peut se résumer comme suit:

On suppose que nous avons calculé toutes les métriques des chemins de l'instant 0 à l'instant .
Considérons, à l'instant , un chemin dans le treillis allant de 0 à . Sa métrique est égale à celle calculée entre 0 et augmentée de la métrique de la transition de à
De tous les chemins qui se joignent à un état donné dans le treillis, sachant qu'il y en a , on ne garde que celui ayant la plus faible métrique, ce chemin est dit Survivor Path. De cette façon, on ne garde que $pM^{L-1}$ chemins dans le treillis à chaque instant.
Une fois arrivé à la fin du treillis, on considère le chemin ayant la plus faible métrique parmi les $pM^{L-1}$ chemins survivants.

Pour de meilleures performances et pour éviter les effets de bord, le codeur impose les états de départ et d'arrivée (généralement à l'etat tout zéro).

exemple

On considère une CPM binaire avec une réponse en fréquence rectangulaire de longueur , la 2REC, avec un indice de modulation . Le treillis de cette CPM contient 4 états et 8 transitions. Une séquence de 8 bits est transmise en bande de base sur un canal gaussien, cette séquence est donnée par:

$\displaystyle U=1\;1\;1\;0\;1\;1\;1\;0$

Le rapport

est de $5 \,dB$ . Le signal transmis en bande de base ainsi que le signal reçu sont montrés sur la figure A.1.

**Figure A.1:** Signal temporel en bande de base de la 2REC binaire, h=1/2
$\includegraphics[width=10cm]{sig_temp_2rec.eps}$

La figure A.2 illustre les différents chemins survivants à chaque instant

ainsi que le seul chemin survivant qui posséde la distance minimale. Ce chemin permet la meilleure estimation de la séquence transmise.

**Figure A.2:** Convergence du treillis de la 2REC binaire
$\includegraphics[width=15cm,height=11cm]{treillis_convergence.eps}$

Les métriques de tous les chemins survivants à chaque instant sont données par le tableau A.1.

Tableau A.1: Evolution des métriques dans le treillis de la CPM 2REC binaire, h=1/2

EtatTemps	T	2T	3T	4T	5T	6T	7T	8T
1	-4.69	0.231	-18.9	-17.9	-22.5	-29.8	-27.2	-43.9
2	- 9.40	0.822	- 19.5	-21.5	- 17.6	- 34.1	- 25.0	- 38.1
3	- 1.49	- 13.3	- 11.2	- 22.9	-23.6	- 22.0	- 34.0	-31.1
4	5.96	- 17.0	-11.7	- 19.0	- 28.9	- 19.0	- 37.6	- 37.5

Les séquences reçues relativement à tous les chemins survivants sont illustrées par l'équation A.1. Le chemin qui se termine à l'état zéro est le chemin qui a la métrique la plus faible. Ce chemin correspond à une séquence reçue égale à celle transmise et donc la transmission s'est effectuée sans erreurs.

$\displaystyle \textrm{chemin} 1: \widetilde{U}_1=1\;1\;1\;0\;1\;1\;1\;0$
$\displaystyle \textrm{chemin} 2:\widetilde{U}_2=1\;1\;1\;0\;1\;1\;1\;1$
$\displaystyle \textrm{chemin} 3: \widetilde{U}_3=1\;1\;1\;0\;1\;1\;0\;0$			(A.1)
$\displaystyle \textrm{chemin} 4: \widetilde{U}_4=1\;1\;1\;0\;1\;1\;0\;0$

Back to the Homepage.