FR2776873A1 - Procede de detection d'une sequence de symboles discrets a partir d'un signal d'observation, et processeur de viterbi mettant en oeuvre un tel procede - Google Patents

Abstract

La détection des symboles d'une séquence sur la base d'un signal d'observation (R) est effectuée selon un algorithme de Viterbi à sorties souples, à l'aide d'un treillis. Pour affecter une vraisemblance (LAMBDAm ) à une estimation discrète (Dm ) d'un symbole, on se fonde sur un calcul de la différence entre la métrique du chemin optimal déterminé selon l'algorithme de Viterbi et la métrique d'un chemin concurrent, qui est optimale parmi tous les chemins conduisant à une décision différente pour le symbole en question, les métriques étant considérées sur la longueur du treillis.

Description

PROCEDÉ DE DETECTION D'UNE SÉQUENCE DE SYMBOLES DISCRETS

À PARTIR D'UN SIGNAL D'OBSERVATION,

ET PROCESSEUR DE VITERBI METTANT EN (EUVRE UN TEL PROCEDÉ

La présente invention concerne le domaine des transmissions numériques. On considère la transmission d'une information de nature numérique, c'est-à-dire sous forme de symboles prenant un nombre fini ND de valeurs d0,...dND-1, et de manière discrète au cours du temps: c'est donc une séquence de symboles numériques Dm (m=0,1,2,... )

appartenant à un alphabet défini Idi, 0<i<ND}.

Le rôle du détecteur, au sens de la présente invention, est de fournir des estimations des symboles successifs Dm d'une séquence à détecter à partir d'un signal d'observation "codé" disponible au niveau d'un récepteur. Le "codeur", qui fournit au détecteur le signal d'observation représentatif de la séquence à détecter doit être pris au sens le plus général: il peut être vu comme une boite noire, développée par le concepteur ou non. Ce peut être par exemple un codeur correcteur d'erreurs (dans ce cas, le signal observation est également une séquence numérique, et le "détecteur" est un décodeur correcteur), ou un ensemble codeur correcteur - modulateur - canal de propagation - démodulateur (le signal observation est alors une suite numérique entachée d'erreurs), ou encore l'ensemble plus simple modulateur - canal de propagation

(le "détecteur" est alors un démodulateur).

Le détecteur est à entrées rigides ("hard inputs") si le signal d'observation qu'il traite est une séquence numérique de symboles à valeurs discrètes, et à entrées souples ("soft inputs") si le signal d'observation est une séquence de valeurs échantillonnées et quantifiées, ou d'estimations discrètes assorties de pondérations respectives représentant les confiances qu'on a dans ces estimations. Le détecteur est à sorties souples ("soft outputs") si les estimations de symbole qu'il délivre sont assorties de pondérations respectives représentant les confiances qu'on a dans ces estimations, et à sorties rigides ("hard outputs") s'il délivre simplement des

estimations discrètes.

Dans les systèmes de transmission réels, il est courant de traiter des signaux possédant une mémoire, c'est-à-dire que le segment du signal portant l'information à un instant donné dépend non seulement de cette information au même instant, mais aussi de l'information passée ou des segments passés du signal. Si cette mémoire vérifie certaines propriétés, notamment le fait qu'existe un treillis décrivant le processus de production du signal d'observation, alors le récepteur peut décider des symboles d'information véhiculés par le signal d'observation au sens du maximum de vraisemblance, grâce à l'algorithme de Viterbi (voir G.D. Forney, Jr., "The Viterbi Algorithm", Proc. IEEE, Vol.61, No.3, mars 1973, pages 268-278) ou à l'algorithme MAP (Maximum A

Posteriori) également exposé dans l'article de G.D.

Forney. Diverses versions de l'algorithme MAP sont

décrites dans les références suivantes: K. Abend et B.D.

Fritchman, "Statistical Detection for Communication Channels with Intersymbol Interference", Proc. IEEE,

Vol.58, No.5, mai 1970, pages 779-785; R.W. Chang et J.C.

Hancock, "On Receiver Structures for Channels Having Memory", IEEE Trans. on Information Theory, Vol.IT-12 No.4, octobre 1966, pages 463-468; et L.R. Bahl et al, "Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate", IEEE Trans. on Information Theory, Vol.IT- 20,

mars 1974, pages 284-287.

Il arrive également que l'on cascade des "codeurs" COD1,COD2,...,CODN dans les systèmes de transmission (par exemple plusieurs codeurs correcteurs d'erreurs, ou un ou plusieurs codeurs correcteurs d'erreurs suivis par un modulateur et un canal de propagation), avec souvent des opérations d'entrelacement intermédiaires. Dans ce cas (système concaténé à mémoire), le récepteur considéré peut consister en une cascade de décodeurs/détecteurs élémentaires DECN,DECN_1,...,DEC1. Ce récepteur est optimal au sens du maximum de vraisemblance si les décodeurs/détecteurs DECp sont à sorties souples (pour p>l) et à entrées souples, le décodeur/détecteur DECp (p>l) associant à chaque estimation discrète d'un symbole décodé Dm de la séquence à détecter (cette séquence est celle délivrée par le codeur CODp_1) une pondération représentée par la vraisemblance égale ou proportionnelle au logarithme du rapport entre la probabilité que le symbole Dm de la séquence inconnue corresponde effectivement à son estimation fournie par le décodage et la probabilité que le symbole Dm soit différent de son estimation, les probabilités en question étant des probabilités conditionnelles, avec la connaissance du signal d'observation disponible. Dans ce cas, les sorties souples de chaque décodeur/détecteur constituent les signaux d'observation" pour le décodeur/détecteur suivant, et l'information de vraisemblance n'est pas

perdue.

L'algorithme de Viterbi a pour avantage que sa mise en ouvre par un circuit ou un processeur n'entraîne pas de grandes difficultés, étant donné la simplicité des opérations effectuées: multiplications, additions/ soustractions, comparaisons. En outre, la régularité des treillis permet souvent d'utiliser des astuces de programmation ou d'organisation de la mémoire, qui facilitent encore la mise en oeuvre de l'algorithme. Ceci explique que son utilisation soit aujourd'hui très répandue dans diverses catégories de détecteurs. Mais, dans sa version traditionnelle, il ne fournit pas la vraisemblance des estimations discrètes qu'il délivre, de sorte qu'il ne permet pas le traitement optimal dans le

cas d'un système concaténé à mémoire.

En revanche, l'algorithme MAP, par essence, fournit les vraisemblances des symboles qu'il estime, mais il pose de sérieuses difficultés d'implémentation: calculs d'exponentielles, nécessité de connaître la variance du bruit, sensibilité aux erreurs sur cette variance, problèmes d'analyse numérique pour ses très

petites valeurs...

Pour les systèmes concaténés à mémoire évoqués ci-

dessus, il a été proposé plusieurs méthodes de pondération des estimations produites par un détecteur de Viterbi. Des exemples de telles méthodes, dites "SOVA" (Soft Output Viterbi Algorithm), sont: - une méthode consistant à prendre comme vraisemblance d'une estimation la différence entre la métrique accumulée au niveau d'un noeud du treillis correspondant à cette estimation et la métrique du meilleur chemin correspondant à une estimation discrète différente (voir C. Berrou et ai, "A Low Complexity Soft-Output Viterbi Decoder Architecture", Proc. ICC'93, Genève, mai 1993). Cette technique

simple est couramment employée, mais très sous-

optimale; - l'algorithme de Hagenauer, décrit dans J. Hagenauer et P. Hoeher, "A Viterbi Algorithm with Soft-Decision Outputs and its Applications", Proc. Globecom'89, Dallas, novembre 1989, pages 47.1.1-47.1.7; - l'algorithme de Battail, décrit dans le brevet américain 4 328 582; - le SOVA optimal (OSA) ou sous-optimal (SSA) décrit

dans Y. Li, B. Vucetic et Y. Sato, "Optimum Soft-

Output Detection for Channels with Intersymbol Interference", IEEE Trans. on Information Theory,

Vol.IT-41, No.3, mai 1995, pages 704-713.

A l'exception de l'OSA, chacune de ces méthodes SOVA apporte une dégradation de performances par rapport à

l'algorithme MAP.

Les algorithmes de Hagenauer, de Battail et de Li, Vucetic et Sato s'apparentent au MAP en ce qu'ils

effectuent les calculs dans le domaine des probabilités.

En conséquence, ils impliquent le calcul d'exponentielles, ce qui rend peu attractive leur mise en ouvre à l'aide de circuits ou de processeurs, même si les exponentielles

sont remplacées par des approximations.

Un but principal de la présente invention est de proposer une méthode SOVA de complexité raisonnable, permettant une évaluation des vraisemblances des symboles estimés par un détecteur de Viterbi, et qui apporte peu de dégradation de la probabilité d'erreur par rapport au cas

optimal de l'algorithme MAP.

L'invention propose ainsi un procédé de détection d'une séquence de symboles discrets à partir d'un signal d'observation dont la production peut être décrite à l'aide d'un treillis de NE états Ee (0<e<NE) et NB branches Bb (0<b<NB), chaque branche ayant un état de départ et un état d'arrivée parmi les NE états et étant associée à un unique Q-uplet de symboles discrets, Q étant un entier au moins égal à 1, le treillis comportant des chemins formés chacun par une succession de branches, chaque chemin ayant une métrique définie par une somme de métriques élémentaires relatives aux branches successives qui le forment, et étant associé à une unique séquence possible de symboles discrets formée par la succession des Q-uplets auxquels sont respectivement associées les branches successives formant ledit chemin, dans lequel le signal d'observation est traité par segments temporels successifs, le traitement effectué pour un segment n du signal d'observation comprenant: - pour chacune des NB branches Bb (O<b<NB), l'obtention d'une métrique élémentaire correspondant à une combinaison entre le segment n du signal d'observation et un signal de référence associé à la branche Bb, et le calcul d'une métrique de branche accumulée MBAb(n) en ajoutant la métrique élémentaire obtenue à une métrique d'état accumulée MEAe(n-1) relative à l'état de départ Ee de la branche Bb; et - pour chacun des NE états Ee (0Se<NE), la mise à jour de la métrique d'état accumulée MEAe(n), prise égale à un optimum des métriques de branche accumulées MBAb(n) relatives à celles des branches Bb qui ont l'état Ee comme état d'arrivée, et la mémorisation d'une identification d'une branche survivante pour laquelle ledit optimum est atteint, dans lequel, après avoir traité des segments successifs du signal d'observation, on sélectionne l'un des NE états EeO et un chemin optimal xopt du treillis formé en remontant les branches survivantes depuis l'état sélectionné, et on estime au moins un symbole discret Dm de la séquence à détecter par la valeur d'un symbole correspondant de la séquence à laquelle est associé le chemin optimal sélectionné, et dans lequel, pour chaque symbole Dm de la séquence à détecter, estimé après la sélection d'un état EeO et d'un chemin optimal Copt, on calcule une différence de métriques minimale entre le chemin optimal et un chemin concurrent associé à une séquence dont le symbole correspondant au symbole Dm a une valeur autre que l'estimation retenue pour le symbole Dmt et on détermine la vraisemblance Am de l'estimation du symbole Dm en

fonction de la différence de métriques minimale calculée.

-7 La vraisemblance Am de l'estimation d'un symbole Dm peut notamment être prise égale ou proportionnelle à la

différence de métriques minimale calculée pour ce symbole.

Les inventeurs ont observé (par simulation) que ce procédé de détection offre des performances proches du MAP en ce qui concerne le taux d'erreur. Son autre avantage est d'utiliser le même type d'opérations simples que l'algorithme de Viterbi classique (uniquement additions/soustractions et comparaisons). Sa complexité lui est comparable: la quantité de calculs requise pour obtenir les vraisemblances équivaut approximativement à celle requise par l'algorithme de Viterbi à sorties discrètes. Mais il a le grand avantage de produire les vraisemblances des décisions. On sait que sur un simple canal gaussien, on peut avoir un gain allant jusqu'à près de 3 dB (pour les grands rapports signal-sur-bruit) sur chacun des étages de décodage. L'intérêt de disposer d'un

tel procédé est donc grand.

Les applications visées sont les concaténations de décodage, parmi lesquelles: - une démodulation d'un système à mémoire, qui doit être suivie d'un décodage à entrées souples d'un code convolutif (avec ou sans entrelacement) ou d'un code en bloc; le système à mémoire peut être une transmission sur un canal à interférence entre symboles, et/ou une modulation à phase continue (CPM: "continuous phase modulation", dont un exemple est la GMSK: "gaussian minimum shift keying") ou linéaire; - deux (ou plus) décodages souples de codes convolutifs concaténés (avec ou non présence d'entrelacement entre les codes); un exemple d'application dans ce cas est le décodage des turbo-codes; ou encore le décodage souple d'un code convolutif suivi du décodage souple d'un code en bloc; - le décodage souple d'un code convolutif, suivi d'un décodeur d'images ou de parole, qui aurait besoin de connaître la qualité des symboles (binaires ou non) décodés, afin d'améliorer la qualité du signal restitué (exemple: décodeur de parole dans un système de radiocommunication cellulaire de type GSM); dans un système de reconnaissance de formes (reconnaissance d'images, de caractères ou de parole) utilisant la modélisation par chaînes de Markov cachées (et qui utilise donc généralement un algorithme de Viterbi pour prendre sa décision) et ayant besoin de connaître la vraisemblance de la décision (par exemple pour justement ne pas prendre de décision dans le cas o la vraisemblance n'atteint

pas un certain seuil).

Dans un mode de réalisation préféré du procédé, lors des traitements effectués pour LO+L1 segments temporels successifs n- r du signal d'observation jusqu'à un segment n (n-L0-Ll<n-r<n), L0 étant un entier positif ou nul et L1 étant un entier strictement positif, on mémorise pour chaque branche b (0<b<NB) l'écart 8b(n- r)=IMBAb(n-r)-MEAe(n-r)I entre la métrique de branche accumulée MBAb(n- r) et la métrique d'état accumulée MEAe(n-r) mise à jour pour l'état d'arrivée Ee de la branche Bb. Après le traitement de Ll segments successifs du signal d'observation jusqu'à un segment n et la sélection d'un état Eeo, on procède à un calcul récursif sur la base des écarts de métriques mémorisés lors des traitements effectués pour les LO+ L1 segments précédents n-r (n-L0-Ll<n-r<n), pour déterminer la différence de métriques minimale relativement à chaque symbole Dm estimé à l'aide de la séquence à laquelle est associé le chemin optimal déterminé en remontant les branches survivantes

depuis l'état sélectionné.

Dans ces conditions, on peut, après le traitement de L1 segments successifs du signal d'observation jusqu'à un segment n et la sélection d'un état, estimer QxL1 symboles Dm relatifs aux Li segments antérieurs n-r tels que n-L0-Ll<n-r<n-L0, et déterminer les vraisemblances respectives des estimations de ces QxL1 symboles Dm, les estimations de Q symboles relatifs à un segment antérieur n-r étant respectivement formées par les valeurs du Q-uplet de symboles auquel est associée la (r+l)-ième branche survivante du chemin optimal parcouru en remontant

depuis l'état sélectionné.

Les paramètres L0 et Ll sont choisis selon le compromis recherché entre l'espace mémoire nécessaire à l'exécution du procédé et la quantité de calculs à effectuer. Avantageusement, une fois qu'on a sélectionné un état Ee0 après le traitement de LI segments successifs du signal d'observation jusqu'à un segment n, on initialise des notes d'état Xe relatives aux NE états Ee (0<e<NE) selon Xe=IMEAe(n)-MEAeO(n)I, puis on exécute les opérations suivantes pour chaque valeur de l'entier r allant de 0 à

LO+L-1:

- la sélection de la branche survivante Bbo mémorisée, pour l'état sélectionné EeG, lors du traitement effectué pour le segment n-r, suivie par la mise à jour de l'état sélectionné EeO pris comme étant l'état de départ de la branche survivante sélectionnée Bbo; - pour chacune des NB branches Bb (O<0b<NB), le calcul d'une note de branche Zb en ajoutant à la note d'état Xe relative à l'état d'arrivée Ee de la branche Bb l'écart de métriques 8b(n-r) mémorisé pour la branche Bb; - pour chacun des NE états Ee (0<e<NE), la mise à jour de la note d'état Xe, prise égale à la plus petite des notes de branche Zb calculées pour celles des branches Bb qui ont l'état Ee comme état de départ; - si rÄL0, l'estimation de Q symboles de la séquence à détecter, par les valeurs du Q-uplet de symboles auquel est associée la branche survivante sélectionnée BbO; et - si r>L0, pour chaque estimation di retenue pour l'un des Q symboles Dm, la détermination de la différence de métriques minimale comme étant la plus petite des notes de branche Zb calculées pour celles des branches Bb qui sont associées à des Q-uplets dont le symbole correspondant au symbole Dm a une valeur di différente de

l'estimation di.

Un autre aspect de la présente invention se rapporte à un processeur de Viterbi, comprenant des moyens de calcul de métriques élémentaires et des moyens de traitement séquentiel adaptés à la mise en ouvre du procédé ci-dessus. Un tel processeur de Viterbi peut notamment faire partie d'un démodulateur de signal numérique, ou encore d'un décodeur tel qu'un décodeur

correcteur d'erreurs.

L'invention sera mieux comprise à la lecture de la

description détaillée ci-après d'exemples de réalisation

non limitatifs, en référence aux dessins annexés, dans lesquels: - les figures 1 et 2 sont des diagrammes d'un exemple de treillis de démodulation et d'un exemple de treillis de décodage correcteur d'erreurs; - la figure 3, constituée en plaçant les figures 3A, 3B et 3C les unes au-dessus des autres, est un organigramme d'un procédé de détection conforme à l'invention; - les figures 4 et 5 sont des schémas synoptiques l1 d'un émetteur de radiocommunication, et d'un récepteur correspondant mettant en ouvre l'invention; - les figures 6 et 7 sont des schémas synoptiques d'un émetteur de signal numérique, et d'un récepteur correspondant mettant en ouvre l'invention; et - la figure 8 est un graphique illustrant l'amélioration des performances procurée par la mise en oeuvre de l'invention dans un exemple de démodulateur numérique. Un processus de Markov, modélisant la production d'un signal d'observation R à partir d'une séquence de symboles discrets Do,D1,...,Dm,... peut être décrit par un treillis possédant NE états Ee (0<e<NE) et NB branches élémentaires Bb (O<0b<NB). Chaque symbole discret de la séquence peut prendre un nombre ND de valeurs distinctes d0,dl,...,dND-. Chaque branche Bb a un état de départ Ep<b) et un état d'arrivée ES(b) (0<P(b)<NE, 0<S(b)<NE), et est associée à un unique Q-uplet de symboles discrets didec( (b,Q-1, Q étant un entier au moins égal à 1. A chaque couple formé par un état Ee et un Q-uplet de symboles correspond une unique branche Bb associée à ce

Q-uplet et ayant l'état Ee comme état de départ (e=P(b)).

A titre d'illustration, la figure 1 montre un tel treillis à NE=3 états et NB=12 branches, dans lequel l'état de départ EP(b) d'une branche Bb a pour index le quotient de la division euclidienne de b par 4 (P(b) = b div 4), et l'état d'arrivée ES<b) d'une branche Bb a pour index le reste de la division euclidienne de b par 3 (S(b) = b mod 3). Chaque branche Bb est associée à deux bits qui correspondent par exemple au reste de la division euclidienne de b par 4 (b mod 4). Dans cet exemple, les symboles peuvent être soit quaternaires (Q=I, ND=4, avec idec(b,0) = b mod 4), soit binaires (ND=2, Q=2, avec

idec(b,q) = bit de poids 2q de b mod 4).

La figure 2 montre un autre exemple de treillis à NE=4 états et NB=8 branches, dans lequel P(b) = b div 2, et S(b) = b mod 4. Dans cet exemple, les symboles sont binaires (ND=2, Q=l, avec idec(b,0) = b mod 2). On considère un treillis de ce genre développé sur L étapes relatives à L segments temporels successifs n du signal d'observation R (0<n<L), correspondant à LxQ symboles de la séquence à détecter. Les segments successifs du signal d'observation présentent éventuellement des recouvrements. Chaque chemin dans le treillis, qui consiste en une succession de branches Bb(0),Bb(1),... Bb(L_1) telles que S[b(n-1)]=P[b(n)] pour 0<n<L-1, est associé à une unique séquence possible de LxQ symboles consistant en la succession des Q-uplets auxquels

sont respectivement associées les branches Bb(o),Bb(l),...

Bb(L-1)-

Le treillis décrit la production du signal d'observation en ce sens que la loi de probabilité d'un segment n du signal d'observation est déterminée par la branche Bb(n) empruntée dans le treillis à l'étape n correspondante, ou en d'autres termes par l'état de départ EP [b (n)] qui garde une certaine mémoire des symboles antérieurs et par le Q-uplet de symboles auquel est associée la branche Bb(n). La détection selon le maximum de vraisemblance consiste dès lors à identifier le chemin optimal dans le treillis, c'est-à-dire la succession de branches qui maximise la probabilité d'occurrence du signal d'observation recueilli. Les symboles estimés sont alors extraits de la séquence à laquelle est associé ce

chemin optimal.

L'identification du chemin optimal revient à une maximisation (ou à une minimisation selon les conventions employées) d'une métrique accumulée le long du chemin, égale à une somme de métriques élémentaires calculées pour les branches successives formant le chemin, les métriques élémentaires rendant compte de la dépendance probabiliste entre les segments du signal d'observation et les branches. Désignons par M(a) la métrique d'un chemin a du treillis développé sur les L étapes, par CBb(n) l'ensemble des chemins du treillis qui empruntent la branche Bb à l'étape n, par CEe(n)= UCBb(n) l'ensemble des chemins du 0Ob<NB S(b)=e treillis qui arrivent à l'état Ee à l'étape n, et par MEAe(n,a) la métrique d'un chemin a de CEe(n) accumulée

jusqu'à l'étape n seulement.

On considère ci-après le cas o la métrique élémentaire MBb(n) calculée pour la branche Bb à l'étape n est le produit scalaire Re(<sblrn>) entre le segment n du signal d'observation R (segment formé d'échantillons réels ou complexes notés rn) et un signal de référence sb réel ou complexe associé à la branche Bb, les signaux de référence sb étant établis de façon que l'optimisation des métriques soit une maximisation (ce serait une minimisation si, avec les mêmes signaux de référence Sb, on retenait comme métrique élémentaire le carré de la distance euclidienne entre le segment rn et le signal de

référence Sb' soit lrn- Sb1).

L'algorithme de Viterbi tire parti du fait que le "meilleur" chemin de l'ensemble CEe(n), c'est-à-dire celui qui optimise (maximise dans le cas considéré) la métrique totale M(a) sur les L étapes, optimise aussi la métrique MEAe(n,a). En conséquence, à chaque étape n (n allant de 0 à L-1), il suffit de mémoriser, pour chaque état Ee, la métrique accumulée: MEAe (n) = max [MEAe(n,c) = max [MBAb(n)] (1) r= 6CE.(fl) Ob<NB S(b)=e ainsi que l'index surve(n) de la branche, dite branche survivante, ayant l'état Ee comme état d'arrivée et pour laquelle la métrique de branche accumulée, définie par MBAb(n) = MEAp(b)(n-l) + MBb(n), est optimale: surve(n) = argmax[MBAb(n)] (2) Ob<NB S(b)=e Au bout des L étapes, l'algorithme de Viterbi sélectionne l'un des NE états, et construit le chemin optimal en remontant les branches survivantes depuis cet état

sélectionné.

L'état sélectionné peut être celui pour lequel la métrique d'état accumulée MEAe(L-1) est optimale si aucune condition aux limites n'est imposée. I1 peut encore être un état prédéterminé si la séquence se termine par des symboles connus. De façon semblable, l'initialisation de l'algorithme, par les valeurs des métriques MEAe(-1), dépend de la connaissance qu'on a a priori du commencement

de la séquence à détecter.

On désigne maintenant par MXe(n) la "meilleure" des métriques totales des chemins arrivant à l'état Ee à l'étape n, et par MZb(n) la "meilleure" des métriques totales des chemins passant par la branche Bb à l'étape n: MXe(n) = max [M(x)] = max [MZb(n)] (3) a eCEe(n) O<b<NB S(b)=e MZb(n) = max [M(c)] (4) C eCBb(n) On désigne enfin par CD (n)= UCBb(n) l'ensemble des O<b<NB idec(b,q)=i chemins du treillis qui sont associés à des séquences dont le symbole Dm de position m=nQ+q prend la valeur di (0<i<ND, 0<q<Q, O<n<L), et par MDq (n) la "meilleure" des métriques totales des chemins de l'ensemble CDq (n) MDq (n) = max [M(e)] = max [MZb(n)] (5) 0_<b<NB ECD' (n) q idec(b, q)=i L'algorithme de Viterbi classique ne calcule pas les quantités MXe(n), MZb(n) et MDq (n). Néanmoins, à chacune des étapes n, le chemin optimal (xOpt qu'il détermine passe par la branche BbO(n) qui optimise la quantité MZb(n), et arrive à l'état EeO(n) qui optimise la quantité MXe(n): bO(n) = argmax[Mzb(n)] (6) O<b<NB eO(n) = argmax[MXe(n)] (7) O<e<NE La vraisemblance de l'estimation di d'un symbole Dm=DnQ+q obtenue par l'algorithme de Viterbi est proportionnelle au rapport logarithmique de probabilités conditionnelles: kPr( Dm di Rg) LLR ln Z exp(2 M(c)/a2) aE CD"(n) soit: LLRim = ln qN (8)

M ND-1

y Y exp(2 M(c)/t2) Ji=o a CD (n) o C2 est la variance du bruit contenu dans le signal d'observation. En approchant les sommes d'exponentielles par l'exponentielle la plus grande, approximations qui se compensent dans une large mesure au numérateur et au dénominateur, l'expression (8) devient: LLRm nexp(2 M(xopt)/o2) LLRm ln ND-1 (9) E exp(2 MDi (n)/a2) j=o j#i Si les symboles estimés sont binaires (ND=2), on peut donc prendre comme vraisemblance de l'estimation di du symbole Dm la quantité: ltAm:rM(opt) - MDq (n)I (10) = M(copt) - MDq (n) t).LLRm (11) ou une quantité proportionnelle, di' étant la décision différente de l'estimation retenue di. La vraisemblance pourra également être évaluée selon la relation (10) dans un cas non binaire (ND>2), di' étant alors la "meilleure" décision différente de l'estimation retenue di: i' = argmax [MDI (n)] (12) 0<j<ND jÉi La métrique optimale M (cspt) est calculée par l'algorithme de Viterbi classique, contrairement à la

métrique MDq (n) du chemin concurrent.

Pour accéder à la métrique MDq (n) du chemin concurrent, il est possible de procéder à un calcul récursif des quantités MXe (n) et MZb(n), de la manière suivante: - à chaque étape n du parcours du treillis dans le sens direct, mémoriser pour chaque branche Bb (0<b<NB) l'écart de métriques 8b (n) =IMBAb (n) -MEAs(b) (n) j= MEAS(b) (n) -MBAb (n); - après la sélection d'un état eO à l'étape n, obtenir les métriques MXe(n)=MEAe(n) pour 0<e<NE; - à chaque étape n-r du parcours du treillis dans le sens inverse (r=0,1,...), exécuté après la sélection d'un état à l'étape n, calculer pour chaque branche Bb (0<b<NB) la métrique MZb(n-r)=MXs(b)(n-r)+6b(n-r) puis, pour 0<e<NE, calculer: MXe(n-r-1)= max MZb(n-r) (13) Ob<NB P(b)=e On dispose ainsi des métriques MZb(n) définies dans la relation (4), en ayant simplement mémorisé les écarts 6b(n) (ou des quantités permettant de les retrouver aisément) et en ayant exécuté un nombre limité d'opérations peu complexes (additions/soustractions, comparaisons). A partir des métriques MZb(n), il est facile de déduire les métriques MDq (n) conformément à la relation (5), d'identifier les métriques MDq (n) des chemins concurrents pour chaque symbole estimé, et donc de

fournir une bonne mesure des vraisemblances.

Si, dans un cas non binaire (ND>2), il s'avère que des chemins concurrents conduisant à des décisions " i différentes di #di ont des métriques proches MDq (n) z MDq (n) < MD (n)=M(aop), une option est d'améliorer l'approximation de la vraisemblance par rapport à l'expression (10) en retranchant un terme correctif. Dans le pire cas, o les métriquesoptimales relatives à toutes les décisions possibles sont égales (MD" (n)=MDq (n) Vi',i"Éi), la plus petite différence de métriques M(acopt)-MDq (n) devient, d'après la relation (9): M(aop) - MDq (n). [LLRm + ln(ND-1)] (14) Le terme correctif peut être proportionnel à a2 (qui doit alors être estimé), avec un coefficient multiplicateur qui décroît de (1/2).ln(ND- l) à 0 avec la dispersion des

métriques des chemins concurrents.

Si la mise en ouvre de l'algorithme de Viterbi est fondée sur une métrique élémentaire à minimiser, telle que le carré de la distance euclidienne, il va de soi que les maxima des relations (1) à (7), (12) et (13) doivent être remplacés par des minima, les écarts de métriques âb(n) étant égaux à MBAb(n)-MEAs(b)(n), et la vraisemblance Am selon le relation (10) devenant: Am = MDq (n) - M(acopt) o2.LLRi (15) La figure 3 illustre un exemple de réalisation d'un procédé selon l'invention, dans lequel, pour limiter encore les calculs, on ne calcule pas explicitement les métriques MXe(n), MZb(n) (relations (3) et (4)), mais les différences entre la métrique M(caopt) du chemin optimal déterminé selon l'algorithme de Viterbi et ces métriques MXe(n), MZb(n)À Le procédé illustré par la figure 3 comporte, pour le parcours direct dans le treillis, une boucle principale

sur l'index n des segments du signal d'observation reçu.

Un parcours inverse ("backtracking") est effectué dans le treillis toutes les LI itérations dans cette boucle, le premier parcours inverse étant effectué à l'issue des LO+L1 premières itérations. Les paramètres entiers L0 et LI sont choisis tels que 1<L1<L et 0<LO<L- L1. Lors du parcours inverse effectué à l'issue des L0+kxL1 premières itérations (k>1), on calcule les estimations des symboles DQ.(k-l). L1 à DQ k Li1_ et les vraisemblances correspondantes. Les écarts de métriques 8b(n) et les branches survivantes surve(n) sont mémorisés pendant LO+L1 itérations consécutives dans la boucle afin d'être disponibles pour chaque parcours inverse. Les autres grandeurs calculées peuvent n'être mémorisées que pendant l'itération courante (en conséquence, on abandonne la référence à n dans les notations employées sur la figure 3

pour ces grandeurs).

Le nombre LO+L1 détermine donc la taille de la mémoire requise pour le calcul des vraisemblances. En général, L0 pourra être égal à la profondeur de troncature (notée 6 dans l'article précité de G.D. Forney) à partir de laquelle il est très probable que tous les chemins survivants aient fusionné. Une grande valeur de Ll conduit à une taille de mémoire relativement importante, mais limite les calculs à effectuer. A la limite, si Ll=L (L0=0), le parcours inverse n'est effectué qu'une fois, en nécessitant la sauvegarde des écarts de métriques Èb(n) sur toute la longueur L du treillis. Inversement, une petite valeur de Ll limite la taille de mémoire, mais requiert davantage de calculs. A la limite, si L1=1, un parcours inverse de profondeur L0+1 est effectué à chaque itération à partir de n=L0, pour n'estimer que Q symboles

à la fois.

Dans l'itération n de la boucle principale, MEAe (0<e<NE) représente la métrique d'état MEAe(n-1) accumulée jusqu'à l'étape n-l, et We représente la métrique d'état accumulée MEAe(n) calculée au cours de l'étape n. Avant de procéder à une nouvelle itération (initialisation 11 par n=0, ou incrémentation de l'index n à l'étape 13), les métriques d'état accumulées MEAe sont mises à jour à l'étape 10 ou 12. A l'étape 12, la mise à jour consiste simplement à prendre MEAe=We pour 0<e<NE. A l'étape 10, les valeurs MEAe(-1) relatives aux conditions initiales sont adoptées. Dans l'exemple représenté sur la figure 3A, on n'a aucune connaissance a priori de l'état de départ, de sorte que les métriques MEAe sont toutes initialisées à la même valeur (0) à l'étape 10. Si l'état de départ est connu (par exemple parce que la séquence à détecter est précédée par une séquence de synchronisation connue), on peut affecter une métrique initiale nulle à cet état connu et des métriques arbitrairement faibles (-c) aux autres états. Dans chaque itération n, on commence par donner des valeurs arbitrairement faibles (- c) aux variables We, et par initialiser à 0 l'index de branche b (étapes 14 et ). Pour chaque valeur de b, la métrique élémentaire MB=MBb(n) est calculée à l'étape 16, dans l'exemple considéré par le produit scalaire entre le segment rn du signal d'observation et le signal de référence sb associé à la branche Bb. A l'étape 17, la métrique de branche accumulée MBAb=MBAb(n) est calculée en ajoutant la métrique élémentaire MB à la métrique d'état accumulée MEAp(b) relative à l'état de départ de la branche Bb. A l'étape 18, la métrique de branche accumulée MBAb précédemment calculée est comparée à la variable Ws(b). On prend survS(b) (n)=b et WS(b)=MBAb à l'étape 19 seulement si MBAb>We. Ensuite, l'index de branche b est comparé au nombre de branches NB à l'étape 20. Si b<NB-l, l'index b est incrémenté d'une unité à l'étape 21, avant de revenir

à l'étape 16 pour le traitement de la branche suivante.

Quand b=NB-l à l'étape 20, les nouvelles métriques d'état accumulées sont contenues dans les variables We, et les branches survivantes dans les variables surve(n) qui sont gardées en mémoire. L'opération suivante 22 est la mémorisation des écarts de métriques ôb(n)=Ws(b)-MBAb pour

chacune des branches Bb (0<b<NB).

Si n<L-1 et si n n'est pas de la forme L0+kxLl-l, avec k entier supérieur ou égal à 1 (test 23), l'itération n dans la boucle principale se termine par le retour aux

étapes 12 et 13.

Un parcours inverse est effectué dans le treillis lorsque le test 23 montre que n=LO+kxLl-1 (ou que n=L-1). Ce parcours inverse commence à l'étape 24 (figure

3B) par la sélection d'un état EeO.

Si on n'a aucune connaissance a priori quant à l'état final, l'état sélectionné EeO est celui pour lequel la métrique d'état WeO, accumulée jusqu'à l'itération n de la boucle principale, est maximale. A l'étape 25, des notes d'états Xe sont respectivement prises égales aux différences We0 We pour 0<e<NE, c'est-à-dire Xe=M (aopt)- MXe(n). Si l'état à la fin de la séquence est connu (par exemple parce que la séquence à détecter est suivie par une séquence de synchronisation connue), alors c'est cet état connu EeO qui est sélectionné à l'étape 24 lors de l'itération finale n=L-1, une note d'état nulle étant alors affectée à cet état Ee0 à l'étape 25, et des notes d'état arbitrairement grandes étant affectées aux autres états (ce qui revient à prendre Xe=M(copt)-MXe(n) si des métriques élémentaires arbitrairement petites sont affectées aux branches conduisant à un état autre que Ee0

à la fin de la séquence).

Le parcours inverse dans le treillis comporte une seconde boucle, indexée par un entier r croissant de 0 à LO+Ll-1. Dans chaque itération r de cette seconde boucle, on calcule une note de branche Zb égale à M(aOpt)-MZb(n-r) pour chaque branche Bb (0<b<NB), et, si r<LO+Ll-1, on calcule de nouvelles notes d'état Ye respectivement égales

à M(Opt)-MXe(n-r-1) pour l'itération suivante (0<e<NE).

Dans l'itération r de cette seconde boucle, qui se rapporte à l'itération n-r de la boucle principale, la quantité Xe désigne la note de l'état Ee calculée à l'itération r-1 (ou initialisée à l'étape 25 si r=0), égale à M(copt)-MXe(n-r). Avant de procéder à une nouvelle itération dans cette seconde boucle (initialisation 26 par r=0, ou incrémentation de l'index r à l'étape 28), les notes d'état Xe sont mises à jour à l'étape 25 ou 27. A l'étape 27, la mise à jour consiste simplement à prendre X =Ye Dans chaque itération r de la boucle du parcours inverse, on commence par sélectionner la branche survivante BbO mémorisée pour l'état sélectionné Ee0, puis par sélectionner un nouvel état Ee0 correspondant à l'état de départ Ep(bO) de la branche survivante sélectionnée (étapes 29 et 30). Des valeurs arbitrairement grandes (+o) sont attribuées aux variables Ye (0<e<NE), puis l'index de branche b est initialisé à O (étapes 31 et 32). Pour chaque valeur de b, la note de branche Zb est calculée à l'étape 33 en lisant dans la mémoire la valeur de l'écart de métriques 8b(n-r), et en ajoutant la valeur lue à la note XS(b) de l'état d'arrivée de la branche Bb. A l'étape 34, la variable YP(b) est prise égale à la note de branche Zb si Zb est inférieure à la précédente valeur de cette variable YP(b)' et maintenue inchangée dans le cas contraire. L'index de branche b est ensuite comparé au nombre de branches NB dans le treillis à l'étape 35. Si b<NB-1, l'index de branche b est incrémenté à l'étape 36 avant de revenir à l'étape 33 pour le calcul de la prochaine note de branche. Quand b=NB-1 à l'étape 35, le calcul des notes de branche Zb et des nouvelles notes d'état Ye est terminé. Si r<LO et n<L-1 (test 37), l'itération r dans la boucle du parcours inverse se

termine par le retour aux étapes 27 et 28.

Sinon (rÄL0 ou n=L-1), on procède aux estimations des symboles de rangs m=Qx(n-r) à m=Qx(n-r+l)-l, et aux calculs de vraisemblance correspondants, comme représenté

sur la figure 3C.

Pour chacun des Q symboles à estimer, repéré par l'index q (0<q<Q, q étant initialisé à 0 à l'étape 39), la position m=Qx(n-r)+q est déterminée à l'étape 40, de même que l'index i de la valeur estimée di du symbole Dmr donné par i=idec(bO,q), bO étant l'index de la branche survivante sélectionnée à l'étape 29 précédente. Une note de décision Ai est initialisée à une valeur arbitrairement grande (+x) pour chacune des décisions possibles di (0<j<ND), puis on initialise à O l'index de branche b (étapes 41 et 42). Pour chaque valeur de b, telle que la branche Bb conduise à une décision dJ pour le symbole de rang q (étape 43), la note de branche Zb est comparée à la variable Ai à l'étape 44. La variable Ai est mise à jour avec la note de branche Zb si cette note Zb est inférieure à la précédente valeur de cette variable Ai, et maintenue inchangée sinon. A l'étape 45, l'index de branche b est comparé au nombre de branches NB du treillis: si b<NB-1, l'index de branche b est incrémenté à l'étape 46 avant de revenir à l'étape 43 pour le traitement de la prochaine branche. Quand b=NB-1 à l'étape 45, le calcul des notes de décision Ai est terminé, et on a Ai=0 et, pour j-i, Ai=M(copt)-MD3 (n-r) o't q Le détecteur peut alors délivrer, à l'étape 47, l'estimation Dm=di du symbole Dm, ainsi que la vraisemblance associée Am, égale à la plus petite des notes de décision Ai pour jÉi. Cette vraisemblance Am correspond à la différence de métriques minimale entre le chemin optimal a.opt et le "meilleur" chemin concurrent relativement au symbole Dm, telle que définie dans la

relation (10).

Tant que tous les symboles relatifs à l'itération r du parcours inverse n'ont pas été estimés (q<Q-1 lors du test 48), on incrémente l'index q à l'étape 49 avant de revenir à l'étape 40. Quand q=Q-1 au test 48, l'index r

est comparé à la profondeur du parcours inverse (test 50).

Si r<L0+Ll-1, l'itération r dans la boucle du parcours

inverse se termine par le retour aux étapes 27 et 28.

Quand r=L0+Ll-1, l'index n de l'itération dans la boucle principale est comparé à la longueur L de la séquence à l'étape 51. Si n<L-1, l'itération n se termine par le retour aux étapes 12 et 13. La procédure d'estimation des symboles de la séquence est achevée quand

n=L-1 à l'étape 51.

On notera que la procédure d'estimation illustrée par la figure 3 se prête bien à diverses astuces de programmation permettant d'en simplifier ou d'en accélérer l'exécution. Par exemple, les traitements 16-19, 33-34 et 43-44 exécutés pour les différentes branches Bb du treillis peuvent être totalement ou partiellement exécutés en parallèle. D'autre part, la régularité de la structure de beaucoup de treillis utilisables (comme par exemple ceux des figures 1 et 2) peut permettre de simplifier la

procédure dans de nombreux cas.

Avantageusement, les écarts de métriques 8b(n), qu'il est nécessaire de mémoriser, sont stockés dans une unité de mémoire organisée en mode dernier entré - premier sorti (LIFO). Ceci permet de simplifier largement, voire de supprimer, le mécanisme d'adressage dans cette unité de mémoire par l'organisme de calcul. En effet, on note que les écarts de métriques Èb(n) sont lus dans la mémoire aux étapes 33 dans l'ordre inverse de celui dans lequel ils ont été écrits aux étapes 22. Il en est de même des

identifications surve(n) des branches survivantes.

Les figures 4 et 5 illustrent la mise en oeuvre de

l'invention dans un démodulateur de signal numérique.

La figure 4 montre schématiquement un émetteur de radiocommunication ayant à transmettre des symboles numériques ap. Un codeur de canal 60 traite le flux numérique {ap} conformément à un code à redondance dont les propriétés permettent la détection et/ou la correction d'erreurs de transmission. Une unité 61 effectue, de façon classique, un entrelacement des symboles délivrés par le codeur 60 afin d'améliorer les performances du code correcteur en présence d'erreurs de transmission survenant par paquets. Le modulateur 62 reçoit les symboles Dm issus de l'unité d'entrelacement 61, ainsi qu'une séquence de synchronisation prédéfinie. Il est ainsi formé des trames successives de signal numérique incluant chacune une ou plusieurs séquences de synchronisation et une ou plusieurs

sequences de symboles d'information Dm.

A titre d'exemple, le modulateur 62 peut appliquer aux trames de signal une modulation à phase continue (CPM) quaternaire d'indice de modulation h=1/3, avec une

impulsion de phase de durée égale à quatre temps symbole.

Une telle modulation peut être décrite par un treillis tel que celui de la figure 1, lorsque l'impulsion de phase est modélisée comme limitée à son temps symbole central dans la conception du récepteur (voir B.E. RIMOLDI, "A Decomposition Approach to CPM", IEEE Trans. on Information

Theory, Vol.34, No.2, mars 1988, pages 260-270).

Le signal de sortie du modulateur 62 est converti en analogique en 63, puis en un signal radio par un étage 64. Le signal radio ainsi émis est capté par un récepteur tel que celui représenté sur la figure 5, après avoir

suivi un canal de propagation.

Le récepteur de la figure 5 comporte un étage radio 66 qui restitue, après les filtrages adéquats, un

signal en bande de base, numérisé par un convertisseur 67.

Le signal numérique en bande de base est un signal complexe fourni au démodulateur 68, qui comprend d'une part une unité 69 de synchronisation et d'estimation de canal, et d'autre part un processeur de Viterbi 70. Sur la base des séquences de synchronisation introduites par l'émetteur dans les trames de signal, l'unité 69 fournit au processeur 70 l'information de synchronisation lui permettant de repérer les segments rn du signal numérique en bande de base formant le signal

d'observation R utilisé dans le procédé selon l'invention.

L'unité 69 procède également à une estimation de la réponse du canal afin de délivrer les signaux de référence Sb utilisés dans la mise en ouvre de l'algorithme de Viterbi. En l'absence d'interférence entre symboles, l'unité 69 estime simplement un nombre complexe représentant l'atténuation et la phase introduites par le canal, et le multiplie par des impulsions prédéfinies pour fournir les signaux de références sb. S'il est tenu compte d'une interférence entre symboles, c'est une réponse impulsionnelle du canal qui est estimée par l'unité 69 et convoluée avec les impulsions prédéfinies pour former des

signaux de référence sb.

Le processeur de Viterbi 70 calcule les estimations Dm des symboles Dm fournis au modulateur 62 de l'émetteur, et les vraisemblances correspondantes Am conformément au procédé exposé ci- dessus. Les métriques de branches élémentaires MBb(n), calculées selon la convention produit scalaire, peuvent être produites par un banc de filtres adaptés 71 du processeur 70, recevant le signal en bande de base R et dont les coefficients sont définis par les signaux de référence sb. Le processeur 70 comprend en outre une unité de traitement séquentiel 72 qui exécute les calculs selon l'algorithme de Viterbi à sorties souples (SOVA) précédemment décrit, et une unité de mémoire 73 de type LIFO, dans laquelle l'unité SOVA 72 écrit et lit les écarts de métriques 6b(n) et les

indications surve(n) des branches survivantes.

Avec la modulation CPM considérée, le procédé est exécuté avec ND=4, Q=l si le codeur de canal 60 délivre des symboles quaternaires, et avec ND=2, Q=2 si les

symboles de sortie du codeur de canal 60 sont des bits.

Comme symbolisé par la flèche f sur la figure 5, les symboles estimés par l'unité SOVA 72 peuvent être fournis en rétroaction à l'unité 69 d'estimation du canal, dans le cas o la variabilité du canal de propagation

requiert qu'il soit estimé de manière adaptative.

En sortie du démodulateur 68, une unité de désentrelacement 75 opère la permutation de symboles inverse de celle effectuée par l'unité d'entrelacement 61 de l'émetteur, et délivre les estimations souples des symboles désentrelacés au décodeur de canal 76 dual du codeur 60. Le fait que ce décodeur 76 soit à entrées souples permet d'obtenir un gain appréciable en termes de taux d'erreurs dans les estimations âp des symboles ap transmis par l'émetteur. Le décodeur 76 peut être à sorties rigides. Il peut également être à sorties souples (dans ce cas, il peut notamment mettre en oeuvre l'invention) si une information de vraisemblance est utile

dans le traitement ultérieur des symboles décodés.

Les figures 6 et 7 illustrent une autre application de l'invention dans une chaîne de transmission numérique. La figure 6 montre un émetteur de signal numérique comportant deux étages de codage. Un premier codeur 80, ou

"codeur interne", reçoit les symboles ap à transmettre.

Après un entrelacement par une unité 81, les symboles Dm délivrés par le codeur interne 80 sont fournis à un second codeur 82, ou "codeur externe". Le flux de symboles délivrés par le codeur externe 82 est envoyé sur un canal de transmission qui peut être de nature quelconque (il peut notamment comprendre un modulateur, un canal de propagation et un démodulateur, par exemple comme décrit en référence aux figures 4 et 5; il peut également comprendre une mémoire dans laquelle l'information transmise serait stockée pendant une période plus ou moins longue). Le codeur externe 82 traite le flux numérique {Dm} conformément à un code à redondance dont les propriétés permettent la détection et/ou la correction d'erreurs de transmission. Le codeur interne 80 peut lui aussi être un codeur à redondance (les deux étages 80, 82 appliquent

alors un code produit, ou turbocode).

A titre d'illustration, le codeur externe 82 peut fonctionner selon un code convolutif, qu'il est usuel de décoder au moyen de l'algorithme de Viterbi. C'est par exemple le code convolutif CC(2,1,3), de rendement 1/2 et de longueur de contrainte 3, auquel cas le treillis de

décodage peut être celui représenté sur la figure 2.

Le récepteur représenté sur la figure 7 reçoit du canal de transmission le signal d'observation R distribué en segments successifs recouvrants rn. Dans l'exemple évoqué du code convolutif CC(2,1,3), chaque segment rn couvre six bits du signal émis. Si le canal de transmission se termine par un démodulateur tel que le démodulateur 68 de la figure 5, chaque échantillon du signal d'observation R correspond à une valeur réelle dont le signe représente l'estimation d'un bit de sortie du codeur externe 82 et dont la valeur absolue correspond à

la vraisemblance associée.

Le décodeur externe 84 du récepteur de la figure 7 comprend une unité 85 de calcul des métriques élémentaires MBb(n), une unité 86 de traitement séquentiel SOVA et une unité de mémoire 87 de type LIFO pour contenir les écarts de métriques b (n) et les indications surve(n) des branches survivantes. Chaque signal de référence sb consiste en six bits de valeur signée 1 correspondant à deux bits associés à l'état de départ ES(b) et au bit associé à la branche Bb (soit b mod 2). Ces six bits signés sont multipliés par les échantillons de chaque segment rn puis sommés par l'unité 85 pour fournir les métriques élémentaires MBb(n). L'unité SOVA 86 fonctionne de la manière précédemment décrite pour délivrer les estimations Dm des bits d'entrée Dm du codeur externe 82, et les vraisemblances correspondantes Am' Ces estimations et vraisemblances sont désentrelacées par une unité 88 qui opère la permutation inverse de celle de l'unité 81 de l'émetteur. Le décodeur interne 89, dual du codeur interne 80, peut alors opérer le décodage requis, à décisions rigides ou souples âp, en bénéficiant de l'information de vraisemblance A. sur ses entrées souples. Il en résulte un gain sur le taux

d'erreurs binaire global.

Dans une autre réalisation, le codeur interne 80 est un codeur de source. Dans ce cas, il traite non pas un flux de symboles ap, mais un signal (audio, video...) à coder. C'est par exemple un codeur de parole. Le décodeur associé 89 pourra exploiter l'information de vraisemblance Am en fonction de la nature de l'information transportée par les bits concernés. Par exemple, pour certains paramètres d'un codeur de source, il peut être préférable d'effectuer une extrapolation sur la base de paramètres précédemment reçus plutôt que d'accepter une nouvelle

valeur du paramètre associée à une vraisemblance faible.

La figure 8 montre des résultats obtenus en simulant un exemple de système de transmission selon les figures 4 et 5, dans lequel: le codeur de canal 60 applique un code convolutif CC(2,1,3) aux symboles binaires ap; l'unité 61 applique un entrelacement par blocs de taille (20,14); le modulateur 62 applique une CPM quaternaire d'indice h=1/3; le démodulateur 68 estime des symboles quaternaires (ND=4, Q=1) en évaluant les vraisemblances selon la relation (10) à partir d'un treillis selon la figure 1; et le décodeur 76 fonctionne selon l'algorithme de Viterbi classique à entrées souples et sorties rigides. D'autre part, le démodulateur 68 opère deux démodulations, l'une du début de la trame vers la fin et l'autre de la fin de la trame vers le début, et le décodeur 76 assure les décodages des deux séries d'estimations pondérées ainsi obtenues, pour sélectionner finalement le jeu symboles âp qui fait l'objet du plus petit nombre de corrections d'erreurs sur la trame (cf. EP-A-0 821 500). Les courbes de la figure 8 ont été obtenues en simulant un canal de Rayleigh à évanouissements plats, avec une fréquence Doppler égale à 2,6x10-3 fois la fréquence des symboles. La courbe I montre le taux d'erreur binaire (TEB) observé en fonction du rapport signal-sur-bruit Eb/N0 en mettant en oeuvre l'invention. La courbe II montre la même quantité obtenue dans le cas o les vraisemblances Am ne sont pas utilisées, le décodeur de canal 76 étant à entrées rigides. On note le gain appréciable procuré par

l'invention, de l'ordre de 3 dB de rapport signal-sur-

bruit pour un taux d'erreur binaire de 10-2, qui montre que les performances du procédé sont très proches de

celles du MAP.

Claims (16)

R E V E N D I C A T I ON S

1. Procédé de détection d'une séquence de symboles discrets à partir d'un signal d'observation (R) dont la production peut être décrite à l'aide d'un treillis de NE états Ee (0<e<NE) et NB branches Bb (0<b<NB), chaque branche ayant un état de départ et un état d'arrivée parmi les NE états et étant associée à un unique Q-uplet de symboles discrets, Q étant un entier au moins égal à 1, le treillis comportant des chemins formés chacun par une succession de branches, chaque chemin ayant une métrique définie par une somme de métriques élémentaires relatives aux branches successives qui le forment, et étant associé à une unique séquence possible de symboles discrets formée par la succession des Q-uplets auxquels sont respectivement associées les branches successives formant ledit chemin, dans lequel le signal d'observation est traité par segments temporels successifs, le traitement effectué pour un segment n du signal d'observation comprenant: - pour chacune des NB branches Bb (0 b<NB), l'obtention d'une métrique élémentaire correspondant à une combinaison entre le segment n du signal d'observation et un signal de référence associé à la branche Bb, et le calcul d'une métrique de branche accumulée MBAb(n) en ajoutant la métrique élémentaire obtenue à une métrique d'état accumulée MEAe(n-1) relative à l'état de départ Ee de la branche Bb; et pour chacun des NE états Ee (O<0e<NE), la mise à jour de la métrique d'état accumulée MEAe(n), prise égale à un optimum des métriques de branche accumulées MBAb(n) relatives à celles des branches Bb qui ont l'état Ee comme état d'arrivée, et la mémorisation d'une identification d'une branche survivante pour laquelle ledit optimum est atteint, dans lequel, après avoir traité des segments successifs du signal d'observation, on sélectionne l'un des NE états EeO et un chemin optimal aopt du treillis formé en remontant les branches survivantes depuis l'état sélectionné, et on estime au moins un symbole discret Dm de la séquence à détecter par la valeur d'un symbole correspondant de la séquence à laquelle est associé le chemin optimal sélectionné, et dans lequel on détermine une vraisemblance Am de l'estimation de chaque symbole Dm, caractérisé en ce que, pour chaque symbole Dm de la séquence à détecter, estimé après la sélection d'un état EeO et d'un chemin optimal uopt, on calcule une différence de métriques minimale entre le chemin optimal et un chemin concurrent associé à une séquence dont le symbole correspondant au symbole Dm a une valeur autre que l'estimation retenue pour le symbole Dm, et on détermine la vraisemblance Am de l'estimation du symbole Dm en

fonction de la différence de métriques minimale calculée.

2. Procédé selon la revendication 1, dans lequel la vraisemblance Am de l'estimation du symbole Dm est prise égale ou proportionnelle à la différence de métriques

minimale calculée pour le symbole Dm.

3. Procédé selon la revendication 1 ou 2, dans lequel, le symbole Dm ayant un nombre ND plus grand que deux de valeurs possibles d0,...,dND-1, on calcule ND-1 différences de métriques relatives aux ND-1 valeurs possibles autres que l'estimation di retenue pour le symbole DmI la différence de métriques AJ relative à une valeur di (0<j<ND, jÉi) étant égale à la différence entre la métrique (M(aopt)) du chemin optimal et la métrique (MD](n)) d'un chemin concurrent relatif à la valeur di, qui présente une métrique optimale parmi tous les chemins associés à des séquences dont le symbole correspondant au symbole Dm a la valeur di, et la différence de métriques minimale pour le symbole Dm est déterminée comme étant la plus petite des ND-1 différences de métriques relatives

aux valeurs dJ (0Sj<ND, jÉi).

4. Procédé selon la revendication 3, dans lequel la vraisemblance Am de l'estimation du symbole Dm est prise égale ou proportionnelle à la différence de métriques minimale moins un terme dépendant de la dispersion des ND-1 différences de métriques relatives aux valeurs di

(0Oj<ND, jÉi).

5. Procédé selon l'une quelconque des revendications

1 à 4, dans lequel, lors des traitements effectués pour LO+L1 segments temporels successifs n-r du signal d'observation jusqu'à un segment n (n-LO-Ll<n-rSn), LO étant un entier positif ou nul et L1 étant un entier strictement positif, on mémorise pour chaque branche b (0Sb<NB) l'écart Èb(n-r)=IMBAb(n-r)-MEAe(n-r)I entre la métrique de branche accumulée MBAb(n-r) et la métrique d'état accumulée MEAe(n-r) mise à jour pour l'état d'arrivée Ee de la branche Bb, et dans lequel, après le traitement de LI segments successifs du signal d'observation jusqu'à un segment n et la sélection d'un état Ee0, on procède à un calcul récursif sur la base des écarts de métriques mémorisés lors des traitements effectués pour les L0+L1 segments précédents n-r (n-LO-Ll<n-r<n), pour déterminer la différence de métriques minimale relativement à chaque symbole Dm estimé à l'aide de la séquence à laquelle est associé le chemin optimal déterminé en remontant les

branches survivantes depuis l'état sélectionné.

6. Procédé selon la revendication 5, dans lequel, après le traitement de L1 segments successifs du signal d'observation jusqu'à un segment n et la sélection d'un état, on estime QxL1 symboles Dm relatifs aux Li segments antérieurs n-r tels que n-L0-Ll<n-r<n-L0, et on détermine les vraisemblances respectives des estimations de ces QxL1 symboles Dm, les estimations de Q symboles relatifs à un segment antérieur n-r étant respectivement formées par les valeurs du Q-uplet de symboles auquel est associée la (r+l)-ième branche survivante du chemin optimal parcouru

en remontant depuis l'état sélectionné.

7. Procédé selon la revendication 6, dans lequel, une fois qu'on a sélectionné un état EeO après le traitement de Ll segments successifs du signal d'observation jusqu'à un segment n, on initialise des notes d'état Xe relatives aux NE états Ee (0<e<NE) selon Xe=IMEAe(n)-MEAe0(n)I, puis on exécute les opérations suivantes pour chaque valeur de l'entier r allant de 0 à L0+Ll-1: - la sélection de la branche survivante BbO mémorisée, pour l'état sélectionné EeO, lors du traitement effectué pour le segment n-r, suivie par la mise à jour de l'état sélectionné Ee0 pris comme étant l'état de départ de la branche survivante sélectionnée BbO; - pour chacune des NB branches Bb (0<b<NB), le calcul d'une note de branche Zb en ajoutant à la note d'état Xe relative à l'état d'arrivée Ee de la branche Bb l'écart de métriques âb(n-r) mémorisé pour la branche Bb - pour chacun des NE états Ee (0<e<NE), la mise à jour de la note d'état Xe, prise égale à la plus petite des notes de branche Zb calculées pour celles des branches Bb qui ont l'état Ee comme état de départ; - si r>L0, l'estimation de Q symboles de la séquence à détecter, par les valeurs du Q-uplet de symboles auquel est associée la branche survivante sélectionnée BbO; et - si r>L0, pour chaque estimation di retenue pour l'un des Q symboles Dmr la détermination de la différence de métriques minimale comme étant la plus petite des notes de branche Zb calculées pour celles des branches Bb qui sont associées à des Q-uplets dont le symbole correspondant au symbole Dm a une valeur di

différente de l'estimation di.

8. Procédé selon l'une quelconque des revendications

à 7, dans lequel les écarts de métriques 6b(n-r) sont stockés dans des moyens de mémorisation organisés en mode

dernier entré - premier sorti.

9. Processeur de Viterbi, pour détecter une séquence de symboles discrets à partir d'un signal d'observation (R) dont la production peut être décrite à l'aide d'un treillis de NE états Ee (O<0e<NE) et NB branches Bb (0<b<NB), chaque branche ayant un état de départ et un état d'arrivée parmi les NE états et étant associée à un unique Q-uplet de symboles discrets, Q étant un entier au moins égal à 1, le treillis comportant des chemins formés chacun par une succession de branches, chaque chemin ayant une métrique définie par une somme de métriques élémentaires relatives aux branches successives qui le forment, et étant associé à une unique séquence possible de symboles discrets formée par la succession des Q-uplets auxquels sont respectivement associées les branches successives formant ledit chemin, comprenant des moyens (71; 85) de calcul de métriques élémentaires, chaque métrique élémentaire MBb(n) correspondant à une combinaison entre un segment temporel n du signal d'observation et un signal de référence associé à l'une des NB branches Bb, et des moyens (72; 86) de traitement séquentiel du signal d'observation par segments temporels successifs, agencés pour effectuer, pour chaque segment n du signal d'observation un traitement incluant: - pour chacune des NB branches Bb (0<b<NB), le calcul d'une métrique de branche accumulée MBAb(n) en ajoutant la métrique élémentaire MBb(n), fournie par les moyens de calcul de métriques élémentaires, à une métrique d'état accumulée MEAe(n-1) relative à l'état e de départ Ee de la branche Bb; et - pour chacun des NE états Ee (0<e<NE), la mise à jour de la métrique d'état accumulée MEAe(n), prise égale à un optimum des métriques de branche accumulées MBAb(n) relatives à celles des branches Bb qui ont l'état Ee comme état d'arrivée, et la mémorisation d'une identification d'une branche survivante pour laquelle ledit optimum est atteint, les moyens de traitement séquentiel étant agencés pour sélectionner l'un des NE états Ee0 et un chemin optimal aopt du treillis après avoir traité des segments successifs du signal d'observation, le chemin optimal aopt étant formé en remontant les branches survivantes depuis l'état sélectionné, pour estimer au moins un symbole 3? discret Dm de la séquence à détecter par la valeur d'un symbole correspondant de la séquence à laquelle est associé le chemin optimal sélectionné, et pour déterminer une vraisemblance Am de l'estimation de chaque symbole Dm, caractérisé en ce que les moyens de traitement séquentiel sont agencés pour calculer, pour chaque symbole Dm de la séquence à détecter, estimé après la sélection d'un état EeO et d'un chemin optimal copt, une différence de métriques minimale entre le chemin optimal et un chemin concurrent associé à une séquence dont le symbole correspondant au symbole Dm a une valeur autre que l'estimation retenue pour le symbole Dm, et pour déterminer la vraisemblance Am de l'estimation du symbole Dm en fonction de la différence de métriques minimale

calculée.

10. Processeur de Viterbi selon la revendication 9, dans lequel les moyens de traitement séquentiel (72; 86) déterminent la vraisemblance Am de l'estimation du symbole Dm comme étant égale ou proportionnelle à la différence de

métriques minimale calculée pour le symbole Dm.

11. Processeur de Viterbi selon la revendication 9 ou , comprenant des moyens de mémorisation (73; 87) dans lesquels les moyens de traitement séquentiel (72; 86) enregistrent pour chacune des NB branches Bb (0Sb<NB), lors des traitements effectués pour LO+L1 segments temporels successifs n-r du signal d'observation jusqu'à

un segment n (n-LO-Ll<n-r n), l'écart 6b(n-r)=IMBAb(n-r)-

MEAe(n-r)I entre la métrique de branche accumulée MBAb(n-r) et la métrique d'état accumulée MEAe(n-r) mise à jour pour l'état d'arrivée Ee de la branche Bb, LO étant un entier positif ou nul et L1 étant un entier strictement positif, et dans lequel les moyens de traitement séquentiel sont agencés pour procéder, après le traitement de Ll segments successifs du signal d'observation jusqu'à un segment n et la sélection d'un état Ee0, à un calcul récursif sur la base des écarts de métriques enregistrés dans les moyens de mémorisation, afin de déterminer la différence de métriques minimale relativement à chaque symbole Dm estimé à l'aide de la séquence à laquelle est associé le chemin optimal déterminé en remontant les

branches survivantes depuis l'état sélectionné.

12. Processeur de Viterbi selon la revendication 11, dans lequel, après le traitement de L1 segments successifs du signal d'observation jusqu'à un segment n et la sélection d'un état, les moyens de traitement séquentiel estiment QxL1 symboles Dm relatifs aux Li segments antérieurs n-r tels que n-LO-Ll<n-rSn-LO, et déterminent les vraisemblances respectives des estimations de ces QxL1 symboles Dm, les estimations de Q symboles relatifs à un segment antérieur n-r étant respectivement formées par les valeurs du Q-uplet de symboles auquel est associée la (r+l)-ième branche survivante du chemin optimal parcouru

en remontant depuis l'état sélectionné.

13. Processeur de Viterbi selon la revendication 12, dans lequel, une fois qu'ils ont sélectionné un état EeO après le traitement de LI segments successifs du signal d'observation jusqu'à un segment n, les moyens de traitement séquentiel (72; 86) initialisent des notes d'état Xe relatives aux NE états Ee (0Oe<NE) selon Xe=IMEAe(n)-MEAeo(n)I, puis exécutent les opérations suivantes pour chaque valeur de l'entier r allant de O à LO+Ll-1: - la sélection de la branche survivante BbO mémorisée, pour l'état sélectionné EeO, lors du traitement effectué pour le segment n-r, suivie par la mise à jour de l'état sélectionné Ee0 pris comme étant l'état de départ de la branche survivante sélectionnée BbO; - pour chacune des NB branches Bb (O<0b<NB), le calcul d'une note de branche Zb en ajoutant à la note d'état Xe relative à l'état d'arrivée Ee de la branche Bb l'écart de métriques 8b(n-r) mémorisé pour la branche Bb; - pour chacun des NE états Ee (0Oe<NE), la mise à jour de la note d'état Xet prise égale à la plus petite des notes de branche Zb calculées pour celles des branches Bb qui ont l'état Ee comme état de départ; - si rÄL0, l'estimation de Q symboles de la séquence à détecter, par les valeurs du Q-uplet de symboles auquel est associée la branche survivante sélectionnée BbO; et - si r>L0, pour chaque estimation di retenue pour l'un des Q symboles Dm, la détermination de la différence de métriques minimale comme étant la plus petite des notes de branche Zb calculées pour celles des branches Bb qui sont associées à des Q-uplets dont le symbole correspondant au symbole Dm a une valeur di

différente de l'estimation di.

14. Processeur de Viterbi selon l'une quelconque des

revendications 11 à 13, dans lequel les moyens de

mémorisation (73; 87) sont organisés en mode dernier entré

- premier sorti.

15. Démodulateur de signal numérique, comprenant des moyens d'estimation de canal (69) pour déterminer, à partir d'un signal d'observation (R), des signaux de référence (sb) respectivement associés à NB branches (Bb) d'un treillis, et un processeur de Viterbi (70) selon

l'une quelconque des revendications 9 à 14, recevant les

signaux de référence et le signal d'observation distribué en segments successifs (rn), et produisant des estimations (Dm) de symboles discrets traités par un modulateur (62) et des vraisemblances (Am) respectivement associées à ces estimations.

16. Décodeur de signal numérique, comprenant un processeur de Viterbi (84) selon l'une quelconque des

revendications 9 à 14, recevant un signal d'observation

(R) distribué en segments successifs (rn), et produisant des estimations (Dm) de symboles discrets traités par un codeur (82) et des vraisemblances (Am) respectivement

associées à ces estimations.