Le domaine de l'invention est celui du traitement de signaux transmis dans un canal perturbé, ou susceptible de l'être.

Plus précisément, l'invention concerne un procédé de traitement du signal, mettant en oeuvre un algorithme de type MAP (pour"Maximum A Posteriori").

L'algorithme MAP est notamment présenté dans l'article de L. E. Baum et T.

Pertie, intitulé"Statistical Inference for Probabilistic Functions of Finite State Markov Chains" (en français, "Interférence statistique pour les fonctions probabilistes de chaînes de Markov à états finis"), Ann. Math. Stat. 37 : 1554- 1563,1966.

L'algorithme MAP, aussi appelé algorithme du Forward-Backward (FB), suscite actuellement beaucoup d'intérêt. En effet, cet algorithme permet notamment de décoder un code convolutif en associant une information de fiabilité aux bits décodés, et de nombreuses applications, telles que celles mettant en oeuvre un"turbo-code"par exemple, peuvent en tirer profit.

On rappelle rapidement ci-après le principe de l'algorithme MAP. Par algorithme MAP, on entend ici, et dans toute la suite du document, aussi bien les algorithme de type MAP, que les algorithmes qui en sont dérivés, et notamment les algorithmes de type Log-MAP et Max-Log-MAP.

De manière schématique, l'algorithme MAP peut être considéré comme la fusion des informations (les métriques de noeuds) générées par deux décodeurs de Viterbi modifiés travaillant en sens inverse sur les données. On rappelle que l'algorithme de Viterbi, couramment utilisé dans le domaine du décodage de signaux reçus, consiste à rechercher dans un treillis représentatif du codage, le chemin qui correspond à la séquence d'états la plus probable, c'est-à-dire celle qui est à la distance minimale de la séquence reçue. Cet algorithme est décrit dans l'article de G. D. Forney,"The Viterbi Algorithm", Proceedings of the IEEE, vol.

61, No. 3, mars 1973.

L'algorithme MAP permet de déterminer le rapport de vraisemblance de la probabilité a posteriori des états à l'instant k, 0 < k < K, d'une chaîne de Markov cachée à états finis, à partir d'observations yod {Yo,...,YK}. On définit généralement une chaîne de Markov comme une collection d'états aléatoires consécutifs enchaînés les uns aux autres, dans laquelle le passage d'un état à un autre est associé à une probabilité, appelée probabilité de transition.

On peut ainsi considérer une chaîne de Markov {Xk} à valeurs dans un espace fini, E = {1,...N}, définie par une matrice de transition entre états II (yr..), de dimension NxN et une loi initiale v =(vi)i=1N définie par v = Prob[Xo = i], Vi E E. Selon la terminologie classiquement employée, une transition entre deux états Xk l et Xk est définie par un couple d'états, et est notée #k = (Xk-1,Xk). La matrice # est la matrice de transition entre états associée à {Xk} dont les éléments TC ; J sont définis par : #i,j = Prob[Xk = j/Xk-1 = il, pour tout i, j E E. (1) Dans toute la suite de ce document, on considère le cas des modèles de Markov cachés, pour lesquels on dispose d'observations bruitées {Yk} à valeur dans Sd, recueillies à travers un canal sans mémoire. En d'autres termes, conditionnellement aux transitions entres états Xk les observations {Yk} sont mutuellement indépendantes, et chaque observation Yk ne dépend que de la transition #k au même instant k. Par conséquent, le modèle de signal observé peut s'écrire sous la forme suivante : Yk = H(#k)+Bk (2) où H (.) représente la fonction de transfert du canal sans mémoire défini dans E et à valeur dans sRd, Xk = (Xk-1, Xk) est un couple d'états à l'instant k à valeur dans ExE, Yk représente une observation à l'instant k à valeur dans Rd et où Bk est un bruit additif blanc.

Dans le contexte des communications numériques, le modèle défini par l'équation (2) peut s'appliquer en égalisation : le canal H(.) représente alors le canal de transmission en bande de base et Xk représente une suite de symboles de l'alphabet de modulation dont la longueur est égale à la mémoire du canal.

Lors du décodage d'un code convolutif, H (. ) représente alors les polynômes générateurs du code, et Xk représente le contenu de la mémoire du codeur de canal.

On décrit désormais plus en détails la notion de rapport de vraisemblance calculé dans le cadre de l'algorithme MAP.

Le rapport de vraisemblance Ak d'un ensemble X appartenant à l'ensemble des parties de E est défini comme le rapport de la probabilité a posteriori de l'ensemble X sur la probabilité a posteriori du complémentaire de X dans E.

Le rapport de vraisemblance peut encore être exprimé sous la forme de l'équation suivante : où PAPk =P [Xk=ilYo=yo,..., YK=yx], OSkSK.

L'algorithme MAP est classiquement associé à une représentation en treillis des différents états à considérer. Ainsi, si l'on considère un codeur convolutif, l'algorithme MAP utilise, pour le décodage, la représentation en treillis de l'évolution temporelle du codeur. Le treillis est généralement représenté par un graphe, dont l'axe des abscisses figure le temps et l'axe des ordonnées représente les différents états possibles. Chaque noeud du treillis est donc associé à un état d'une part, et à un instant k d'autre part. Les transitions possibles entre les noeuds de deux instants successifs k et k+l sont représentés par des branches.

L'algorithme MAP fait intervenir deux variables intermédiaires, respectivement appelées variable"forward"et variable"backward". Ces variables propagées par l'algorithme MAP sont calculées récursivement, respectivement dans le sens direct ("forward") et indirect ("backward") par rapport au treillis, et permettent d'aboutir au calcul du rapport de vraisemblance à chaque instant k.

Ces variables"forward"et"backward", définies dans la suite du document, utilisent la probabilité d'observer Yk conditionnellement aux états Xk=j et Xn= !, exprimée par l'équation suivante : bi, j (Yk) = Prob[Yk = yk/Xk-1 = i,Xk = j] (5)

Cette probabilité est classiquement appelée métrique. Elle peut éventuellement dépendre de k, et est fonction de la densité de probabilité du bruit Bk.

L'algorithme MAP procède en trois étapes, à savoir une étape de récursion avant (ou"forward"), une étape de récursion arrière (ou"backward") et enfin, une étape de fusion des données.

La récursion"avant"consiste à calculer les probabilités a k de passer par les noeuds représentatifs des états Xi=i aux instants k, à partir des informations obtenues en parcourant le treillis dans le sens direct. La variable"forward"ak est ainsi définie comme la probabilité de l événement (Xi = i, Yo = Yon Yk = yk): αik = Prob[Xi = i,Y0 = y0,...,Yk = yk] (6) On peut démontrer que les CCik, 0 # k < K, se calculent récursivement de la façon suivante : aik+l<BR> <BR> j#E avec la valeur initiale αi0 = vi, #i # E.

De même, la récursion"arrière"consiste à calculer les probabilités ßik de passer par les noeuds représentatifs des états X ; i aux instants k, à partir des informations obtenues en parcourant le treillis dans le sens indirect. La variable "backward"ßik est ainsi définie comme la probabilité de l'événement (Xi = i,Yk+1 = yk+1,...,YK = yK): fi, = Prob[Xi = i,Yk+1 = yk+1,...,YK = yK] (7) On peut démontrer que les ßik, 0#k#K, se calculent récursivement de la façon suivante : ßik = ##i,jbi,j(Yk+1)ßjk+1<BR> <BR> j#e avec la valeur initiale ßiK=1,#i# E.

La troisième étape mise en oeuvre par l'algorithme MAP consiste à fusionner les résultats des deux récursions pour calculer la probabilité"a posteriori"des états, en calculant le rapport de vraisemblance des symboles détectés.

Le rapport de vraisemblance d'un ensemble d'états défini par l'équation (3) peut alors être exprimé en fonction des variables intermédiaires"forward"et "backward"sous la forme : Dans le contexte de la détection de symboles par exemple, l'ensemble X regroupe les états correspondant à l'émission d'un même symbole de la modulation. Dans le contexte de décodage de canal, l'ensemble X regroupe les états correspondant au même mot à l'entrée du codeur de canal.

L'algorithme MAP, bien que fournissant des résultats très performants, présente l'inconvénient d'être très complexe à mettre en oeuvre.

Notamment, la réalisation matérielle de l'algorithme MAP est très délicate, et les récepteurs implémentant cet algorithme sont par conséquent coûteux.

Les problèmes d'implémentation de l'algorithme MAP classique sont en partie dus à la forte dispersion des probabilités bik qui nécessite donc une grande précision pour le calcul des variables"forward"ak et"backward"ßik. En outre, le calcul du rapport de vraisemblance tel que défini par l'équation (3) ci-dessus impose d'effectuer des divisions qui sont coûteuses et peuvent poser des problèmes de stabilité.

Pour résoudre ces différents inconvénients de l'algorithme MAP, on a proposé des algorithmes de types Log-MAP ou Max-Log-MAP.

Néanmoins, les algorithmes de type Log-MAP ou Max-Log-MAP, comme les algorithmes de type MAP, restent très complexes à mettre en oeuvre, et nécessitent d'effectuer un grand nombre d'opérations lors du calcul du rapport de vraisemblance.

L'invention a notamment pour objectif de pallier ces inconvénients de l'art antérieur.

Plus précisément, un objectif de l'invention est de fournir une technique de traitement de signal mettant en oeuvre un algorithme MAP à complexité réduite par rapport aux techniques de l'art antérieur. Notamment, l'invention a pour

objectif de permettre une réduction du nombre de calculs mis en oeuvre, tant par les algorithmes de type MAP, que par les algorithmes de type Log-MAP ou Max- Log-MAP, en réalisant un meilleur rapport performance/complexité que dans l'art antérieur.

Un autre objectif de l'invention est de mettre en oeuvre une telle technique, permettant la conception de récepteurs moins complexes, et donc moins coûteux que dans l'art antérieur.

L'invention a encore pour objectif de fournir une telle technique qui réalise un compromis satisfaisant entre les exigences de faible complexité d'une part et de fiabilité des résultats d'autre part. En d'autres termes, l'invention cherche à fournir une méthode permettant de réduire systématiquement, avec une bonne qualité d'approximation, la complexité des algorithmes de types MAP, Log-MAP et Max-Log-MAP.

Ainsi, alors que les algorithmes de type MAP classiques nécessitent généralement la mise en oeuvre d'un nombre d'opérations en AL¢I, où L représente la longueur du canal de transmission, et où A représente le nombre de caractères de l'alphabet de modulation, l'invention vise à fournir une technique mettant en oeuvre un algorithme de type MAP mettant en oeuvre un nombre d'opérations en AM, où M<L-1, tout en conservant une bonne qualité d'approximation du rapport de vraisemblance.

L'invention a également pour objectif de mettre en oeuvre une telle technique qui permette une prise de décisions souples.

Ces objectifs, ainsi que d'autres qui apparaîtront par la suite, sont atteints à l'aide d'un procédé de traitement d'un signal mettant en oeuvre un algorithme de type MAP ("Maximum a posteriori") permettant de déterminer un rapport de vraisemblance Akx d'un ensemble d'états X d'un treillis à un instant k, à chacun desdits états étant associées au moins deux variables intermédiaires, respectivement appelées variable"forward"et variable"backward", propagées par ledit algorithme MAP et calculées récursivement respectivement dans un sens direct et dans un sens indirect audit instant k par rapport audit treillis.

Selon l'invention, un tel procédé comprend une étape de réduction du nombre d'états sélectionnés par ledit algorithme de type MAP lors d'un calcul dudit rapport de vraisemblance, et, pour au moins certains états non-sélectionnés, on affecte à ladite variable"forward"et/ou"backward"correspondante au moins une valeur déterminée, de façon à calculer un rapport de vraisemblance approché.

Ainsi, l'invention repose sur une approche tout à fait nouvelle et inventive de mise en oeuvre d'un algorithme MAP, permettant de simplifier les différentes étapes de traitement des signaux tout en maintenant une qualité de résultats satisfaisante. En effet, l'invention propose notamment de réduire le nombre d'états sélectionnés par l'algorithme MAP pour le calcul du rapport de vraisemblance, de façon à simplifier les différentes étapes mises en oeuvre lors d'un tel calcul, et d'attribuer aux variables intermédiaires manquantes des valeurs déterminées permettant de calculer un rapport de vraisemblance approché. L'invention repose donc sur un algorithme de type MAP approché, présentant un coût de calcul réduit par rapport aux algorithmes MAP classiques. Les récepteurs de signaux mettant en oeuvre un tel algorithme sont donc moins complexes à construire que les récepteurs de l'art antérieur.

Avantageusement, pour un instant k donné, ladite au moins une valeur déterminée a (k) affectée à ladite variable"forward"est telle que et/ou ladite au moins une valeur déterminée b (k) affectée à ladite variable"backward"est telle que 0< b (k) où Mk et Mk représentent un ensemble desdits états sélectionnés respectivement dans ledit sens direct et dans ledit sens indirect audit instant k, et où (Xik et ßik représentent respectivement lesdites variables"forward"et"backward"audit instant k.

Préférentiellement, pour un instant k donné, ladite valeur déterminée a (k) et/ou b (k) est unique et est affectée à au moins une variable"forward"a ; x et/ou "backward"ßik.

Selon une variante avantageuse de l'invention, on affecte une valeur constante auxdites variables"forward", respectivement"backward", de façon que

ledit algorithme de type MAP soit un algorithme unidirectionnel de type direct, respectivement indirect.

Selon une caractéristique avantageuse de l'invention, ladite étape de réduction du nombre d'états met en oeuvre un algorithme de recherche en treillis de type"breadth-first".

Selon une première variante préférentielle, ledit algorithme de type "breadth-first"est un algorithme de type M.

Selon une deuxième variante préférentielle, ledit algorithme de type "breadth-first"est un algorithme de type T, utilisant au moins un seuil.

Préférentiellement, ledit au moins un seuil est variable en fonction dudit instant k.

Avantageusement, on affecte audit seuil variable une valeur prédéterminée pour chaque instant k.

De manière préférentielle, pour chaque instant k, la valeur dudit seuil variable est déterminée par mise en oeuvre d'un algorithme adaptatif.

De manière avantageuse, ledit algorithme adaptatif est du type algorithme de gradient.

Selon une caractéristique avantageuse de l'invention, ledit treillis comprenant une pluralité de noeuds associés chacun à un desdits états et à un instant k donné, la valeur dudit seuil variable T à un instant (k+1) est déterminée par l'équation suivante : T (k + 1) = T (k)-H (M (k)-Mc) où T (k) représente la valeur dudit seuil variable audit instant k, M est le nombre de noeuds dudit treillis propagés visé, M (k) est le nombre de noeuds dudit treillis propagés audit instant k, et g est une constante positive représentative d'un gain d'apprentissage.

Préférentiellement, ledit algorithme adaptatif est du type algorithme de gradient à pas variable.

Avantageusement, ledit gain d'apprentissage F est fonction dudit instant k.

Préférentiellement, ledit algorithme de type"breadth-first"étant un algorithme de type M, lesdites valeurs déterminées a (k) et/ou b (k) affectées respectivement auxdites variables"forward"et/ou"backward", à un instant k donné sont données par les équations suivantes :

où Cf et cb sont deux constantes positives.

De manière préférentielle, ledit algorithme de type"breadth-first"étant un algorithme de type T, lesdites valeurs déterminées a (k) et/ou b (k) affectées respectivement auxdites variables"forward"et/ou"backward", à un instant k donné, sont données par les équations suivantes : a (k) = Tf (k)-c f b(k)=Tb(k)-cb où cf et cb sont deux constantes positives, et où T (k) et Tb (k) désignent la valeur dudit seuil variable audit instant k respectivement dans ledit sens direct et dans ledit sens indirect.

Avantageusement, ledit algorithme de type MAP appartient au groupe comprenant : les algorithmes de type MAP ; les algorithmes de type Log-MAP ; les algorithmes de type Max-Log-MAP.

On notera que les variables"forward"et"backward"peuvent avoir des définitions différentes selon le type d'algorithme utilisé (MAP, Log-MAP ou Max-Log-MAP), ainsi que détaillé dans la suite du document.

Préférentiellement, ledit algorithme de type MAP étant un algorithme unidirectionnel, ledit procédé met en oeuvre une étape de comparaison de décisions prises par ledit algorithme unidirectionnel avec des décisions correspondantes prises par un algorithme de type Viterbi, appelées décisions de Viterbi.

Par algorithme de type Viterbi, on entend ici, et dans toute la suite du document, un algorithme de Viterbi à nombre d'états réduit, auquel on associe une opération de"trace-back" (c'est-à-dire de décodage de l'algorithme). Ainsi, les décisions de Viterbi sont des décisions fournies par un algorithme à nombre d'états réduit, auquel est associé un"trace-back".

Selon une première caractéristique avantageuse, en cas de comparaison négative pour au moins une desdites décisions prises par ledit algorithme unidirectionnel, ledit procédé met en oeuvre une étape de substitution de ladite décision de Viterbi correspondante à ladite décision prise par ledit algorithme unidirectionnel, appelée décision substituée.

Préférentiellement, on affecte à la valeur absolue dudit rapport de vraisemblance associé à ladite décision substituée une valeur déterminée V.

Avantageusement, ladite valeur déterminée V est égale à la valeur absolue du rapport de vraisemblance moyen de la séquence.

V correspond donc à la moyenne des fiabilités, soit environ à la fiabilité moyenne de la séquence.

Selon une deuxième caractéristique avantageuse, en cas de comparaison négative pour au moins une desdites décisions prises par ledit algorithme unidirectionnel, ledit procédé met en oeuvre une étape de pondération dudit rapport de vraisemblance associé à ladite décision considérée, tenant compte de ladite décision de Viterbi.

Préférentiellement, Y étant un ensemble d'états associés à une décision D ; Y fournie par ledit algorithme de type Viterbi à un instant i, et Aj représentant le rapport de vraisemblance associé à Y à l'instant i, calculé par ledit algorithme unidirectionnel, au cours de ladite étape de pondération, on remplace AiY par Âi défini par ÃY = AiY + DjY x V, où V est une valeur déterminée.

L'invention s'applique avantageusement à l'un au moins des domaines appartenant au groupe comprenant : la détection de symboles ; - le codage/décodage de signaux ;

-le turbo-décodage ; -la turbo-détection ; le codage de source par quantification (notamment quantification en treillis).

L'invention concerne également un récepteur de signaux de communication comprenant des moyens de mise en oeuvre d'un algorithme de type MAP ("Maximum a posteriori") permettant de déterminer un rapport de vraisemblance AkX d'un ensemble d'états X d'un treillis à un instant k, à chacun desdits états étant associée au moins une variable intermédiaire, appartenant au groupe comprenant une variable appelée"forward"et une variable appelée"backward", propagées par ledit algorithme MAP et calculées récursivement respectivement dans un sens direct et dans un sens indirect audit instant k par rapport audit treillis.

Selon l'invention, un tel récepteur comprend des moyens de réduction du nombre d'états sélectionnés par ledit algorithme de type MAP en vue d'un calcul dudit rapport de vraisemblance, et, pour au moins certains états non-sélectionnés, on affecte à ladite variable"forward"et/ou"backward"correspondante au moins une valeur déterminée, de façon à calculer un rapport de vraisemblance approché.

D'autres caractéristiques et avantages de l'invention apparaîtront plus clairement à la lecture de la description suivante d'un mode de réalisation préférentiel, donné à titre de simple exemple illustratif et non limitatif, et des dessins annexés, parmi lesquels : la figure 1 présente un treillis représentatif d'une pluralité d'états associé à un algorithme MAP de l'invention ; la figure 2 présente un organigramme illustratif du principe de"trace-back" comparatif ou comparatif pondéré, mis en oeuvre selon l'invention en combinaison avec les algorithmes MAP unidirectionnels ; la figure 3 présente un synoptique des différentes étapes de calcul mises en oeuvre par l'algorithme de type MAP unidirectionnel de la figure 2, appliqué à la détection de symboles dans un alphabet de A mots, où

A=2Q ; la figure 4 illustre les différentes étapes de calcul des variables"forward" mises en oeuvre par un algorithme de type MAP bidirectionnel selon l'invention ; la figure 5 décrit les différentes étapes de calcul des variables"backward" mises en oeuvre par l'algorithme de la figure 3, ainsi que les différentes étapes de calcul des rapports de vraisemblance.

Le principe général de l'invention repose sur la réduction du nombre d'états sélectionnés lors du calcul du rapport de vraisemblance de l'algorithme MAP, de manière à élaborer un algorithme MAP simplifié. Une telle réduction est notamment réalisée, dans un mode de réalisation préféré de l'invention, par mise en oeuvre d'un algorithme de type"breadth-first".

Préalablement à la description détaillée des figures mentionnées ci-dessus, on présente le principe de la réduction d'états mise en oeuvre par l'invention, ainsi que les différentes équations établies par les inventeurs.

Dans un mode de réalisation préféré de l'invention, les inventeurs ont envisagé d'avoir recours aux algorithmes de type"breadth-first", et notamment aux algorithmes de type M et de type T pour implémenter des algorithmes MAP à nombre d'états réduit.

Tout comme l'algorithme de Viterbi (décrit notamment dans l'article de G.

D FORNEY « The Viterbi algorithm », Proceedings of the IEEE, vol 61, No 3, march 1973), l'algorithme M est un algorithme de recherche en treillis de type « breadth-first » (en français"largeur d'abord" ; un tel algorithme examine le coût associé à une famille d'états à chaque instant). L'algorithme de type M est notamment décrit par J. B Anderson et S. Mohan dans « Sequential Coding algorithms : A survey and cost analysis » (en français, "Algorithmes de codage séquentiels : enquête et analyse de coût"), IEEE Trans. on Communications, vol.

COM-32, Février 1984.

Pour chaque profondeur du treillis de la figure 1, l'algorithme de Viterbi ne conserve que le meilleur chemin passant par chaque noeud, illustré en trait épais sur la figure 1.

L'algorithme de type M conserve quant à lui les M meilleurs chemins passant par les M meilleurs noeuds, où M est un entier inférieur au nombre de noeuds du treillis de l'algorithme de Viterbi. Ainsi, lors de la mise en oeuvre de l'algorithme M, il est nécessaire de classer les noeuds du treillis (symbolisés par des points noirs sur le treillis de la figure 1) en fonction de leur métrique cumulée (on rappelle que la métrique cumulée des noeuds du treillis est équivalente à la variable"forward"), afin de sélectionner les M meilleurs noeuds.

L'algorithme de type T est également un algorithme de type"breadth-first", mais diffère de l'algorithme M par la méthode mise en oeuvre pour sélectionner les noeuds du treillis de la figure 1 propagés par l'algorithme. En effet, l'algorithme T sélectionne uniquement les noeuds du treillis associés à une métrique cumulée dont la distance à la meilleure métrique cumulée du treillis est inférieure à un seuil T.

Selon l'invention, on prévoit avantageusement d'introduire de nouveaux algorithmes T de type"breadth-first", à seuil variable. Pour ce faire, les inventeurs ont envisagé deux approches distinctes : - dans une première variante de réalisation de l'invention, on affecte un seuil, calculé a priori, à chaque transition (on rappelle qu'une transition d'un état à un autre est symbolisée par une branche du treillis de la figure 1). Ce seuil est calculé en tirant partie de la longueur finie de la séquence d'observation (sur le treillis de la figure 1, la séquence d'observation commence à l'instant k et se termine à l'instant k+4). Ainsi, si l'on considère un treillis de longueur K+1, pour lequel BMAX représente la valeur maximale des métriques de branche, on choisit le seuil T (k) tel que : T (k) < (K+l-k) BMAX et OkK ; - dans une deuxième variante de réalisation de l'invention, on fixe la valeur du seuil de l'algorithme T, en mettant en oeuvre un algorithme adaptatif. En

effet, un avantage de l'algorithme de type T, par rapport à l'algorithme M, est que, selon cet algorithme, il n'est pas nécessaire de classer les noeuds du treillis en fonction de leur métrique cumulée, pour sélectionner les meilleurs noeuds. L'algorithme de type T impose seulement de trouver le meilleur noeud du treillis, afin de normaliser les métriques cumulées de l'ensemble des noeuds du treillis. Dans cette deuxième variante de réalisation de l'invention, les inventeurs ont envisagé d'utiliser un algorithme adaptatif pour fixer le seuil de l'algorithme T, afin d'asservir sa complexité.

Par exemple, en utilisant un algorithme de gradient, on peut mettre le seuil à jour par l'équation suivante : T(k+1)=T(k)-µ (M (k)-Mc) (9) où Mc représente le nombre de noeuds propagés visé, M (k) le nombre de noeuds propagés à l'instant k, et où/ est une petite constante positive que l'on appelle le gain d'apprentissage.

On peut également généraliser l'algorithme au cas où, u dépend de k, comme c'est le cas pour les algorithmes de type gradient à pas variable.

On présente désormais plus en détails la mise en oeuvre de tels algorithmes de type"breadth-first"dans le cadre de la réduction du nombre d'états des algorithmes de type MAP.

Afin de pouvoir utiliser les algorithmes de type MAP avec un nombre d'états réduit, l'invention propose avantageusement d'affecter à chaque instant k une valeur par défaut a (k) et b (k) respectivement aux variables"forward"et "backward".

Soient Mkf et Mkb les ensembles des états sélectionnés respectivement dans le sens"forward"et"backward"à l'instant k.

Si l'état Xk = i fait partie de l'ensemble Mkf, c'est que cet état a été sélectionné à l'instant k.

Les variables"forward"ak étant associées à des probabilités, elles doivent N vérifier la condition de normalisation au = 1. On peut démontrer que si l'on i=l veut vérifier cette condition, alors il faut choisir a (k) tel que :

Il apparaît de manière évidente que les variables"forward"xkpour i 0 Mk ne sont pas accessibles (les états associés n'étant pas sélectionnés, par définition de Mkf), et l'on ne peut donc que déterminer des bornes de l'intervalle de variation de a (k). En faisant l'hypothèse que les Métats éléments de Mkf ont les M plus grandes probabilités a posteriori (ou APP), on borne a (k) par : Si l'on fixe a (k) à 0 quel que soit k, cela revient à considérer que les états non propagés ont une APP nulle et ne participent pas au calcul de la vraisemblance donné par l'équation (8). En d'autres termes, cela revient à attribuer une confiance absolue aux choix des M états propagés.

A contrario, si l'on fixe a (k) à sa valeur maximale, alors on attribue une confiance minimale au choix des M états propagés.

On peut appliquer le même raisonnement aux variables"backward", ce qui conduit à déterminer b (k) tel que : Les équations (11) et (12) ci-dessus peuvent être affinées dans le cadre de l'utilisation d'un algorithme de type M d'une part, et d'un algorithme à seuil de type T d'autre part.

En effet, lorsque l'on met en oeuvre un algorithme de type M, on dispose à chaque instant k, du classement des états sélectionnés dans le sens direct (ou "forward") et indirect (ou"backward") respectivement, en fonction des valeurs de ak et pl. Il est donc aisé de déterminer les valeurs de et donc d'affecter a a (k) et b (k) les valeurs suivantes : avec cf etcb deux constantes positives. Ces deux constantes Cf et cb permettent de régler la confiance que l'on accorde au choix des états propagés.

Dans le cas d'un algorithme de type T, c'est-à-dire lorsque les états propagés par l'algorithme sont sélectionnés par un seuil (fixe ou variant au cours du temps comme proposé précédemment), la détermination des minima des équations (11) et (12) nécessite une charge de calcul supplémentaire importante.

Par conséquent, les inventeurs proposent, pour cette classe d'algorithme, de fixer a (k) et b (k) par l'intermédiaire du seuil : a (k) = Tf (k)-Cf (15) b (k) = Tb (k)-cb (16) où Tf (k) représente le seuil dans le sens"forward"à l'instant k, et où T b (k) représente le seuil dans le sens"backward"à l'instant k (tels que définis par exemple par l'équation (9) ci-dessus), ebet cf étant deux constantes positives.

Dans la pratique, pour des raisons de simplicité d'implémentation, les algorithmes de type Log-MAP ou Max-Log-MAP sont souvent préférés aux algorithmes MAP classiques. En effet, le calcul du rapport de vraisemblance tel que défini par l'équation (3) ci-dessus nécessite, pour les algorithmes de type MAP classiques, d'effectuer des divisions qui sont coûteuses et peuvent poser des problèmes de stabilité. Pour cette raison, on préfère généralement utiliser les algorithmes travaillant dans le domaine logarithmique, qui propagent l'opposé du logarithme des variables"forward"et"backward", et aboutissent au calcul du logarithme du rapport de vraisemblance, encore appelé Log-vraisemblance (ou LLR pour"Log-Likelihood-Ratio") défini par : où PAPki = P[Xk = i/Y0 = y0,...,YK = yK],0#k#K.

Si l'on considère un codeur convolutif générant des symboles Xk, transmis par un canal bruité vers un récepteur qui reçoit des symboles Yk et implémente un algorithme de type Log-MAP pour décoder les bits reçus, le signe de LLRkX donne la valeur du bit décodé, et sa valeur absolue indique la qualité de la décision.

L'application du principe de la réduction d'états, présenté ci-dessus pour les algorithmes MAP classiques, aux algorithmes de type Log-MAP ou Max-Log- MAP est présentée brièvement ci-après.

Soient ai =-Log (αik) et ek =-Log (ßik) les variables logarithmiques "forward"et"backward". Selon l'invention, pour les algorithmes de types Log- MAP et Max-Log-MAP à nombre d'états réduit, les variables logarithmiques manquantes sont remplacées dans le sens"forward"et"backward"respectivement par a (k) et b (k) définis par : <BR> <BR> #(k)#Max(#ik) (17)<BR> <BR> <BR> <BR> <BR> iczm, f<BR> <BR> <BR> <BR> <BR> <BR> b (k) #Max(#ik) (18)<BR> <BR> <BR> <BR> ieMX Ainsi, selon l'invention, lorsque la réduction du nombre d'états de l'algorithme de type Log-MAP ou Max-Log-MAP est réalisée par mise en oeuvre d'un algorithme"breadth-first"utilisant un algorithme de tri (c'est-à-dire un algorithme de type M), on remplace les données manquantes respectivement dans le sens"forward"et"backward"par : a (k) = Max (ak) + c f (19) iEM ;<BR> <BR> <BR> <BR> <BR> <BR> # (k) Max Cb (20)<BR> <BR> <BR> <BR> i#Mib avec Cf et Cb deux constante positives.

En ce qui concerne les algorithmes"breadth-first"utilisant un seuil pour sélectionner les états propagés dans le sens"forward"et,"backward" (c'est-à-dire les algorithmes de type T), les données manquantes sont remplacées respectivement par : # (k)=#f(k)+#f (21) # (k) = T b (k) + cb (22) avec #f (k) et #b (k) respectivement les seuils"forward"et"backward" (variant éventuellement en fonction du temps k, comme proposé précédemment).

L'invention permet également de combiner au principe de la réduction d'états présenté précédemment, des aspects relatifs à la simplification des

algorithmes classiques de type MAP (c'est-à-dire MAP, Log-Map et Max-Log- MAP).

Comme mentionné précédemment, les algorithmes MAP, Log-MAP et Max-Log-MAP nécessitent la propagation des variables"forward"et"backward" respectivement dans le sens direct et indirect, par rapport au treillis associé.

Dans une variante de réalisation de l'invention, on propose de simplifier ces algorithmes en fixant les variables"forward"ou"backward"à une valeur prédéterminée, de préférence constante, de façon à élaborer des algorithmes dits unidirectionnels. Ainsi, en fixant les variables"forward", cxk ou ai à une valeur constante quelconque quels que soient k et i, on obtient des algorithmes MAP, Log-MAP et Max-Log-MAP dits"indirects". De même, en fixant la variable k "backward",,, a une valeur constante quelconque quels que soient k et i, on obtient des algorithmes dits"directs".

On peut alors appliquer le principe de la réduction d'états à ces algorithmes directs et/ou indirects, en mettant en couvre les algorithmes de type"breadth-first" décrits précédemment, de façon à obtenir des algorithmes directs et/ou indirects à nombre d'états réduit. Ainsi, dans le cas d'un algorithme MAP indirect par exemple, pour lequel toutes les variables"forward"ocik ont été fixées à une valeur constante, on remplace les variables"backward"manquantes ßik (correspondant à des états non sélectionnés) par une valeur b (k) prédéterminée, ainsi que décrit précédemment dans le document.

De telles méthodes de gestion des données manquantes permettent de rendre efficaces les algorithmes directs et indirects utilisant un nombre d'états réduit. En effet, lorsque le nombre d'états propagés est faible, il est probable que l'un au moins des ensembles sur lequel on calcule le rapport de vraisemblance défini par l'équation (3) soit vide.

La méthode proposée, selon laquelle on affecte des valeurs par défaut aux variables intermédiaires nécessaires au calcul du rapport de vraisemblance mais correspondant à des états non propagés du treillis, permet alors de déterminer le rapport de vraisemblance dès qu'il y a au moins deux états propagés dans le

treillis, et de lui affecter une valeur souple (encore appelée valeur"soft"). En effet, <BR> <BR> <BR> <BR> en affectant la valeur 0 à la probabilité d'un état non propagé, on obtient, pour les<BR> 0<BR> <BR> <BR> <BR> algorithmes de type MAP, des valeurs de rapport de vraisemblance en<BR> <BR> constante<BR> <BR> <BR> <BR> <BR> ou en constante Pour les algorithmes de type Log-MAP, on obtient des valeurs<BR> <BR> 0 de rapport de vraisemblance en- ou en +oxo.

Un inconvénient de ces algorithmes unidirectionnels, que les inventeurs ont identifié, est que les décisions prises par de tels algorithmes, c'est-à-dire le signe des rapports de vraisemblance définis par l'équation (3) (ou (3bis)), diffèrent généralement des décisions prises par les algorithmes mettant en oeuvre un"trace- back". (On rappelle que les algorithmes mettant en oeuvre un"trace-back" permettent une prise de décision correspondant au chemin le plus vraisemblable).

En effet, les états associés aux décisions prises par les différents algorithmes unidirectionnels peuvent ne pas être autorisés par la matrice de transition ici. Dans une variante de réalisation avantageuse de l'invention, on a donc envisagé d'utiliser conjointement un algorithme unidirectionnel à nombre d'états réduit avec un"trace back"comparatif ou comparatif pondéré.

Selon l'invention, le"trace back"comparatif consiste à comparer les décisions prises par un algorithme unidirectionnel aux décisions correspondantes prises par un algorithme de type Viterbi, ainsi qu'illustré en figure 2. On considère Y, un ensemble d'états associés à la décision D fournie par l'algorithme de type Viterbi à l'instant i. Soit A, l'instant i, calculée par l'algorithme unidirectionnel et di la décision correspondante prise par l'algorithme unidirectionnel.

Au cours d'une première étape référencée 21, on calcule le rapport de vraisemblance AY^, de façon à prendre une décision 0',.'pour l'algorithme unidirectionnel. On analyse (22) la décision D, Ycorrespondante pour l'algorithme de type Viterbi et on compare (23) ces deux décisions 4 et DY.

Si les deux décisions diffèrent, alors la décision prise par l'algorithme de type Viterbi remplace (25) celle de l'algorithme unidirectionnel. La valeur absolue des rapports de vraisemblance associés à ces décisions reste inchangée ou forcée à

une valeur V. V est soit fixée a priori à une valeur petite soit calculée pour chaque séquence. Dans ce dernier cas, on peut par exemple fixer V à la valeur absolue du rapport de vraisemblance moyen de la séquence.

Plutôt que de choisir brutalement entre la décision fournie par l'algorithme de type Viterbi D ; Y et celle produite par l'algorithme unidirectionnel on peut également faire une pondération de ces deux décisions : c'est ce que l'on appelle le principe du"trace back"comparatif pondéré, également illustré en figure 2.

Lors de l'étape de"trace back"comparatif pondéré, la vraisemblance AY est remplacée (24) par api définie par : AY = AY + DY x V (23) avec V égale à la valeur absolue du rapport de vraisemblance moyen calculée sur la séquence, ou fixée a priori.

On présente désormais, en relation avec la figure 3, un mode de réalisation des différentes étapes de calcul mises en oeuvre par un algorithme de type MAP logarithmique unidirectionnel selon l'invention, appliqué à la détection de symboles dans un alphabet de A mots, où A = 2Q.

Le vecteur CM (i) 31 contient les M (i) métriques cumulées correspondant aux M (i) états retenus à l'instant i stockés dans le vecteur State (i) 32 de taille M (i) fois Q bits.

Le bloc 33 « calcul BM et ACS » calcule les A. M (i) métriques cumulées associées aux A. M (i) états suivant les M (i) états du vecteur State (i) 32. Il effectue ensuite la sélection des meilleurs états convergeant vers le même noeud. Cette sélection consiste soit à sélectionner les états qui ont la plus petite métrique cumulée (dans le cas d'un algorithme de type Max-log-map unidirectionnel) soit à effectuer récursivement une opération de comparaison correction en utilisant la formule du logarithme Jacobien (dans le cas d'un algorithme de type Log-Map unidirectionnel).

Ainsi, dans le cas d'un algorithme unidirectionnel de type Max-Log-MAP, on procède en trois étapes successives :

a) Première étape : calcul de la métrique de branche BM(i, j) xln (bu (yk)), conformément à l'équation (5) décrite précédemment. On notera que la métrique de branche s'exprime simplement comme une distance euclidienne. b) Deuxième étape : accumulation.

On met à jour les variables rock ; (respectivement ßk) de manière simplifiée.

On considère, à l'instant k-1, deux noeuds Po et Pl associés respectivement aux variables"forward"aU, et A l'instant k suivant, on considère le noeud final associé à la métrique cumulée CMj (k). La métrique de branche du noeud Po <BR> <BR> <BR> <BR> (respectivement Pl) au noeud final est BM (Po (j), j) (respectivement BM (Pl (j), j). On a alors : #jk=max[(αP1(j)k-1+BM(P1(j),j)),(αP0(j)k-1+BM(P0(j),j))]. c) Troisième étape : sélection.

On choisit le meilleur chemin qui converge vers chaque noeud : c'est cette étape qui va permettre le"trace-back".

Pour un algorithme de type Log-MAP, les première et troisième étapes sont identiques, mais, au cours de la deuxième étape de mise à jour des variables "forward", on a : <BR> <BR> #jk=max[(αP1(j)k-1 +BM (P1(j),j)),(αP0(j)k-1+BM(P0(j),j))]+f(#αP1(j)k-1+BM(P1(j), j)-(αP0(j)k-1+BM(P0(j),j))#<BR> #jk=max[(αP1(j)k-1+BM(P1(j),j)),(αP0(j)k-1+BM(P0(j),j))]+f (#αP1(j)k-1+BM(P1(j),j)-(αP0(j)k-1+BM(P0(j),j))# où f(z)=ln(1+exp(-z)).

Les métriques des meilleurs n#uds sélectionnés par le bloc 33 « calcul BM <BR> <BR> <BR> <BR> et ACS » sont sauvegardées dans le vecteur TmpCM (i+l) 34. Le nombre d'états sélectionnés à cette étape est compris entre M (i) et A. M (i). Les états correspondants sélectionnés à cette étape sont stockés dans le vecteur TmpState (i+l) 35.

Le bloc 36 « sélection M ou T » permet de sélectionner les états propagés par l'algorithme MAP.

Si la réduction d'états met en oeuvre un algorithme de type T, le bloc 36 « sélection M ou T » sélectionne les états dont la distance de la métrique cumulée par rapport à la meilleure métrique cumulée est inférieure à un seuil T.

Si la réduction d'états met en oeuvre un algorithme de type M, le bloc 36 « sélection M ou T » sélectionne les M meilleurs états.

Dans le cas de l'algorithme de type T, le bloc 36 « sélection M ou T » calcule également le nouveau seuil T (i+l) en fonction du nombre d'états sélectionnés M (i) en appliquant le seuil T (i), comme décrit précédemment dans l'équation (9).

A l'issue de l'étape de sélection effectuée par le bloc référencé 36, on stocke dans le vecteur CM (i+1) 37, les M (i+1) métriques cumulées correspondant aux M (i+l) états retenus à l'instant i+l stockés dans le vecteur State (i+l) 38 de taille M (i+l) fois Q bits.

Le vecteur Survivor (i+1) 39, de taille N mots de Q bits contient l'indice des M (i) branches qui convergent sur les M (i) états retenus, stockés dans le vecteur State (i) 32. L'état sur lequel converge la branche gagnante du treillis est codé par l'adresse de stockage de l'indice de la branche, sur Q bits.

C'est avec l'ensemble des vecteurs Survivor (i+l) 39, pour i variant de 0 à K-1, que l'on effectue l'opération de"trace back", afin de déterminer les décisions à comparer ou à pondérer avec celles déterminées par le bloc 40 de calcul du LLR (pour"Log-Likelihood Ratio", ou rapport de vraisemblance logarithmique), ainsi que décrit précédemment en relation avec la figure 2.

On présente désormais, en relation avec la figure 4, un mode de réalisation du calcul des variables"forward"pour un algorithme logarithmique MAP bidirectionnel selon l'invention.

On rappelle que les algorithmes bidirectionnels de type Log-Map ou Max- Log-Map à nombre d'états réduit commencent, dans une première étape, par calculer récursivement les variables"forward", comme pour les algorithmes unidirectionnels.

La figure 4 illustre le calcul de la liste des états conservés et des métriques cumulées dans le sens direct ou"forward".

A la différences des algorithmes unidirectionnels présentés en figure 3, les métriques cumulées du vecteur CMF (i) 42, les états sélectionnés correspondants

du vecteur StateF (i) 43, et éventuellement le nombre d'états sélectionnés à chaque instant, sont stockés, afin d'être utilisés pour calculer les rapports de vraisemblance LLR lors de l'étape"backward".

Comme illustré par la figure 3, le vecteur CMF (i) 42 contient les MF (i) métriques cumulées correspondant aux MF (i) états retenus dans le sens"forward" à l'instant i stockés dans le vecteur StateF (i) 43 de taille MF (i) fois Q bits.

Le bloc 33 « calcul BM et ACS » calcule les A. MF (i) métriques cumulées associées aux A. MF (i) états suivant les MF (i) états du vecteur StateF (i) 43. Il effectue ensuite la sélection des meilleurs états convergeant vers le même noeud, selon un procédé similaire à celui décrit en relation avec la figure 3.

Les métriques des meilleurs noeuds sélectionnés par le bloc 33 « calcul BM et ACS » sont sauvegardées dans le vecteur TmpCMF (i+l) 44. Le nombre d'états sélectionnés à cette étape est compris entre MF (i) et A. MF (i). Les états correspondants sélectionnés à cette étape sont stockés dans le vecteur TmpStateF (i+l) 45.

Le bloc 36 « sélection M ou T » permet de sélectionner les états propagés par l'algorithme MAP.

Si la réduction d'états met en oeuvre un algorithme de type T, le bloc 36 « sélection M ou T » sélectionne les états dont la distance de la métrique cumulée par rapport à la meilleure métrique cumulée est inférieure à un seuil T.

Si la réduction d'états met en oeuvre un algorithme de type M, le bloc 36 « sélection M ou T » sélectionne les M meilleurs états.

Dans le cas de l'algorithme de type T, le bloc 36 « sélection M ou T » calcule également le nouveau seuil dans le sens"forward"TF (i+l) en fonction du nombre d'états sélectionnés MF (i) en appliquant le seuil TF (i), comme décrit précédemment dans l'équation (9).

A l'issue de l'étape de sélection effectuée par le bloc référencé 36, on stocke dans le vecteur CMF (i+l) 46, les MF (i+l) métriques cumulées correspondant aux MF (i+l) états retenus à l'instant i+l stockés dans le vecteur StateF (i+l) 47 de taille MF (i+l) fois Q bits.

Le calcul des métriques cumulées"backward"du vecteur CMB (i) 50 et des états sélectionnés stockés dans le vecteur StateB (i) 51 s'effectue de manière symétrique au calcul"forward", ainsi qu'illustré par la figure 5. La figure 5 présente également le calcul des LLR à partir des variables"forward" (métriques cumulées, liste d'états et éventuellement seuils) mémorisées dans le sens direct, et des nouvelles variables calculées dans les sens indirect.

Ainsi, le vecteur CMB (i) 50 contient les MB (i) métriques cumulées correspondant aux MB (i) états retenus dans le sens"backward"à l'instant i stockés dans le vecteur StateB (i) 51 de taille MB (i) fois Q bits.

Le bloc 33 « calcul BM et ACS » calcule les A. MB (i) métriques cumulées associées aux A. MB (i) états suivant les MB (i) états du vecteur StateB (i) 51. Il effectue ensuite la sélection des meilleurs états convergeant vers le même noeud, selon un procédé similaire à celui décrit en relation avec les figures 3 et 4.

Les métriques des meilleurs noeuds sélectionnés par le bloc 33 « calcul BM et ACS » sont sauvegardées dans le vecteur TmpCMB (i+l) 53. Le nombre d'états sélectionnés à cette étape est compris entre MB (i) et A. MB (i). Les états correspondants sélectionnés à cette étape sont stockés dans le vecteur TmpStateB (i+l) 52.

Le bloc 36 « sélection M ou T » permet de sélectionner les états propagés par l'algorithme MAP.

Si la réduction d'états met en oeuvre un algorithme de type T, le bloc 36 « sélection M ou T » sélectionne les états dont la distance de la métrique cumulée "backward"par rapport à la meilleure métrique cumulée est inférieure à un seuil T.

Si la réduction d'états met en oeuvre un algorithme de type M, le bloc 36 « sélection M ou T » sélectionne les M meilleurs états.

Dans le cas de l'algorithme de type T, le bloc 36 « sélection M ou T » calcule également le nouveau seuil dans le sens"backward"TB (i+l) en fonction du nombre d'états sélectionnés MB (i) en appliquant le seuil TB (i), comme décrit précédemment dans l'équation (9).

A l'issue de l'étape de sélection effectuée par le bloc référencé 36, on stocke dans le vecteur CMB (i+l) 54, les MB (i+l) métriques cumulées correspondant aux MB (i+l) états retenus à l'instant i+l stockés dans le vecteur StateB (i+l) 55 de taille MB (i+l) fois Q bits.

Le calcul du LLR 40 utilise les métriques cumulées du vecteur CMF (i) 42 et du vecteur CMB (i) 50, ainsi que les états sélectionnés stockés dans les vecteurs StateF (i) 43 et StateB (i) 51. Dans le sens"forward"les métriques cumulées du vecteur CMF (i) 42, les états du vecteur StateF (i) 43, et éventuellement les seuils TF (i) et le nombre d'états sélectionnés MF (i), sont mémorisés pour toute la séquence, c'est-à-dire pour i variant de 1 à K.

Le bloc « Calcul du LLR » 40 peut utiliser les seuils TF (i) et TB (i), dans le cas d'une réduction d'états par algorithme de type T, ou les moins bonnes métriques cumulées CMB (M) et CMF (M), dans le cas d'une réduction d'états par algorithme de type M, pour gérer les données manquantes, comme exposé précédemment. Tout comme pour les algorithmes unidirectionnels, le calcul du LLR utilise l'approximation Max-Log-Map ou la formule du logarithme Jacobien pour les algorithmes de type Log-Map.