FR 3025322 A1 20160304 FR 1458115 A 20140829 1 SP55859EA-T MÉTHODE D'ACQUISITION D'UNE SÉQUENCE DE GOLD PAR DOUBLE DÉCODAGE ITÉRATIF DESCRIPTION DOMAINE TECHNIQUE La présente invention concerne de manière générale le domaine du décodage. Elle s'applique notamment à la phase d'acquisition d'un signal satellitaire par un récepteur GPS (Global Positioning System) ou par un récepteur du système Galileo. ÉTAT DE LA TECHNIQUE ANTÉRIEURE Un récepteur GPS détermine classiquement sa position en mesurant les temps de vol de signaux reçus d'une pluralité de satellites (en principe au moins quatre). Pour estimer le temps de vol d'un signal GPS émis par un satellite, le récepteur utilise un canal d'acquisition grossière dit canal C/A (Coarse Acquisition) sur lequel le satellite émet un message de navigation étalé spectralement au moyen d'une séquence pseudo-aléatoire (dite séquence d'étalement) possédant de bonnes propriétés d'auto-corrélation ainsi que d'inter-corrélation (avec les séquences PRN utilisées par les autres satellites). Les bonnes propriétés d'auto-corrélation des séquences d'étalement permettent d'optimiser la probabilité de détection d'un signal en présence de bruit alors que les bonnes propriétés d'inter-corrélation de ces séquences permettent aux différents satellites de partager une même bande de transmission au moyen d'un accès multiple par répartition de codes (CDMA). La première tâche d'un récepteur GPS est de détecter les satellites en visibilité. Pour ce faire, le récepteur cherche à détecter le code d'étalement du satellite dont il souhaite tester la présence et, le cas échéant, se synchronise par rapport à ce signal. Cette première tâche est dénommée étape d'acquisition du signal GPS. De nombreuses méthodes d'acquisition du signal GPS sont connues de l'état de la technique. Elles s'apparentent à la problématique de détection multi-utilisateur dans les 3025322 2 SP55859EA-T systèmes CDMA. Ces méthodes d'acquisition sont généralement basées sur une corrélation du signal reçu par le récepteur avec le code d'étalement du satellite à tester. Un exemple de méthode d'acquisition par corrélation avec le code d'étalement est décrit dans l'article de A. Polydoros et al. intitulé « A unified approach to serial search spread spectrum code 5 acquisition » Part I : A general theory & Part II : a matched filter receiver, publiés dans IEEE Trans. on. Comm., Vol. 32, No. 5, 1984. Une méthode d'acquisition plus récente a été proposée dans l'article de F. Principe et al. intitulé « Rapid acquisition of Gold codes and related sequences using iterative message passing on redundant graphical models » publié dans Proc. MILCOM '06, 10 2006. Cette méthode est basée sur un décodage itératif par passage de messages (IMPA) dans un graphe de Tanner représentant les contraintes de parité imposées au code. Toutefois, cette dernière méthode d'acquisition ne permet pas d'obtenir des niveaux de probabilité de détection ratée (missed detection probability) et de probabilité de fausse alarme suffisamment faible à bas rapport signal sur bruit (SNR). Par probabilité 15 de détection ratée, on entend la probabilité de ne pas se synchroniser avec une séquence d'étalement d'un satellite alors que celle-ci est effectivement reçue par le récepteur. Par probabilité de fausse alarme, on entend la probabilité de se synchroniser avec une séquence d'étalement alors que celle-ci n'est pas reçue par le récepteur. La demande de brevet FR 1351423 propose une méthode d'acquisition par 20 décodage IMPA permettant d'obtenir des niveaux de probabilité de détection ratée et de probabilité de fausse alarme sensiblement plus faibles. Toutefois, cette méthode est relativement complexe dans la mesure où elle effectue un décodage en série . Selon cette méthode, en effet, le décodeur suppose être synchronisé avec le code et tente un premier décodage. En cas d'échec le décodeur suppose être synchronisé avec l'instant suivant et 25 ainsi de suite. Chaque tentative de décodage doit être réalisée dans un laps de temps très court de manière à respecter les contraintes de temps d'acquisition. Le but de la présente invention est de proposer une méthode d'acquisition d'une séquence de Gold, en particulier d'une séquence de Gold émise par un satellite d'un système GPS ou Galiléo, qui permette d'obtenir des temps d'acquisition plus courts et avec une plus faible complexité que dans l'art antérieur. 3025322 3 SP55859EA-T EXPOSÉ DE L'INVENTION La présente invention est définie par une méthode d'acquisition d'une séquence de Gold étalant un signal à une fréquence bribe, ladite séquence de Gold étant obtenue 5 comme somme d'une première M-séquence et d'une seconde M-séquence , la première M-séquence étant générée par un premier polynôme générateur et la seconde M-séquence étant générée par un second polynôme générateur, les premier et second polynômes générateurs étant de même degré et le poids du second polynôme générateur étant supérieur au poids du premier polynôme générateur, la méthode comprenant : 10 (a) une étape de réception et d'échantillonage à la fréquence bribe dudit signal pour obtenir une pluralité d'échantillons représentatifs d'éléments successifs de ladite séquence de Gold ; (b) une première étape de décodage par passage de messages dans un premier graphe bipartite entre des premiers noeuds de variable représentant les éléments 15 successifs de la séquence de Gold et des premiers noeuds de contrôle , chaque noeud de contrôle étant associé de manière biunivoque à une variable représentative d'un élément de la seconde M-séquence, les arêtes du graphe bipartie étant déterminées par les coefficients du premier polynôme générateur ; (c) une étape de décimation des variables représentatives d'éléments successifs 20 de la seconde M-séquence à l'aide d'un facteur de décimation prédéterminé pour obtenir des secondes variables représentatives d'éléments d'une troisième M-séquence, la troisième séquence étant de même longueur que la seconde séquence et étant générée par un troisième polynôme générateur de poids minimal ; (d) une seconde étape de décodage par passage de messages dans un second 25 graphe bipartite entre lesdits seconds noeuds de variable et des seconds noeuds de contrôle, les arêtes du second graphe bipartite étant déterminées par les coefficients du troisième polynôme générateur. On pourra effectuer une pluralité de premières étapes de décodage par passage de messages avant d'effectuer ladite étape de décimation. 3025322 4 SP55859EA-T Avantageusement, après la seconde étape de décodage par passage de messages, on effectue une opération inverse de celle de l'étape de décimation pour mettre à jour lesdites variables représentatives des éléments successifs de la seconde séquence. 5 On pourra également effectuer une pluralité de secondes étapes de décodage par passage de messages avant d'effectuer une opération inverse de celle de l'étape de décimation. Les étapes (b) (c) (d) pourront être itérées jusqu'à ce qu'un critère d'arrêt prédéterminé soit satisfait. Lorsque ce critère d'arrêt est satisfait, on détermine à partir 10 des valeurs des premières variables représentatives des éléments de la séquence de Gold et des variables représentatives des elements successifs de la seconde séquence l'instant de génération de ladite séquence de Gold. BRÈVE DESCRIPTION DES DESSINS 15 D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture de modes de réalisation préférentiels de l'invention faite en référence aux figures jointes parmi lesquelles : La Fig. 1 représente de manière schématique un générateur de séquence maximale selon une représentation de Fibonacci ; 20 La Fig. 2 donne des paramètres de codes de Gold pour différents satellites ; La Fig. 3 représente de manière schématique un générateur de code de Gold dans un système GPS ; La Fig. 4 représente schématiquement une méthode d'acquisition d'une séquence de Gold à l'aide de deux décodeurs cascadés à passage de messages ; 25 La Fig. 5 représente schématiquement une méthode d'acquisition d'une séquence de Gold selon un mode de réalisation de l'invention ; La Fig. 6 illustre la probabilité d'une acquisition d'une séquence de Gold en fonction du rapport signal sur bruit, pour la méthode d'acquisition de la Fig. 5 et celle de la Fig. 4. 3025322 5 SP55859EA-T EXPOSÉ DÉTAILLÉ DE MODES DE RÉALISATION PARTICULIERS On rappelle qu'un signal émis par un satellite d'un système de positionnement tel que le système GPS ou le système Galileo est obtenu par étalement spectral d'un message de navigation, le code d'étalement étant propre au satellite en question. Chaque symbole 5 du message dure une pluralité de périodes de répétition du code d'étalement. Ainsi, pour le système GPS, chaque symbole dure 20 ms, soit 20 périodes de répétition du code d'étalement, la fréquence bribe (ou rythme chip) étant de 1,023 MHz. Les séquences d'étalement ci des différents satellites i =1,..., 1 sont des séquences de Gold, chaque séquence de Gold étant construite à partir d'une somme de deux 10 séquences de longueur maximale, encore dénommées M-séquences. On rappelle qu'une M-séquence est une suite périodique de valeurs produite par un registre à décalage à rétroaction linéaire (LFSR) qui explore toutes les valeurs pouvant être produites par le registre à décalage. Toute combinaison linéaire de deux M-séquences de même degré r (c'est-à-dire générées par des polynômes générateurs de même degré) ne donne pas 15 nécessairement une séquence de Gold : une paire de M-séquences dont la somme donne une séquence de Gold est appelée paire de séquences préférentielles. Les séquences d'étalement ci sont chacune construites à partir d'une paire de M- séquences préférentielles, x et y . Plus précisément : 20 ci(k)= x(k)+ y(k (1) où 21 est un retard, exprimé en nombre de périodes bribes, spécifique au satellite i . Dans le cas du système GPS, les M-séquences x et y sont respectivement générées à partir des polynômes générateurs : 25 g x(D) = +D3 +1 g y(D) = + D9 + D8 + D6 + + D2 +1 (2) 3025322 6 SP55859EA-T On rappelle qu'une séquence LFSR générée par un polynôme générateur g (D) =1g pDP de degré r, avec gr = g0 =1 est obtenue par un registre à décalage à p=0 r positions mémoire (dénommées ci-après plus simplement positions) et r prises, rebouclé sur lui-même, comme représenté en Fig. 1, selon la représentation dite de 5 Fibonacci. Les coefficients multiplicateurs sur les différentes prises sont les coefficients du polynôme générateur. Une M-séquence est définie de manière univoque par son polynôme générateur, le contenu du registre à décalage à l'instant initial donnant sa valeur à l'origine. Une M-séquence générée par un polynôme générateur (primitif) de degré r est périodique et de 10 longueur K = 2r -1. Les M-séquences x et y sont générées en initialisant les positions de leurs registres à décalage respectifs à 1, soit x(0) = x(1) = ...= x(9)=1 et y(0) = y(1)= ...= y(9)=1. On peut montrer que la séquence de Gold C, est également une M-séquence de longueur 22T -1 et de polynôme générateur g c(D) = g x(D)g y (D) . 15 La séquence retardée définie par y(k), y(k- r,) est avantageusement obtenue en utilisant la propriété « add and shift » des M-séquences. Plus précisément, les délais r, sont choisis de sorte à ce que la séquence y puisse être générée à partir de la somme des contenus en deux positions a, et /3, du registre à décalage générant la 20 séquence y soit : y(k)= aoe,(k)+ afi,(k) (3) où (9,, (k), afi (k) sont respectivement les contenus du registre à décalage aux positions 25 a, et ,6' à l'instant k, autrement dit aoe(k)= y(k+ ai) et afi, (k) = y(k+A). 3025322 7 SP55859EA-T On a représenté en Fig. 2 une table donnant les paramètres a' A et r, pour les différents satellites. Plus précisément, la colonne intitulée « code phase selection » donne les positions a',(3, et la colonne intitulée « code delay chips » donne le retard r,. Enfin, la dernière colonne fournit le mot d'initialisation, c'est-à-dire les 10 premières valeurs de la 5 séquence y en représentation octale. La Fig. 3 représente de manière schématique un générateur de code d'étalement (code C/A) dans un système GPS. On distingue dans la partie supérieure le générateur, 310, de la M-séquence X et 10 dans la partie inférieure le générateur, 320, de la M-séquence y. Les deux générateurs 310 et 320 utilisent des registres à décalage rebouclés sur eux-mêmes. Pour chaque générateur, les prises du registre à décalage correspondent aux monômes du polynôme générateur correspondant. Le sélecteur de phase, 330, vient sommer sélectivement certaines positions du registre à décalage de 320. Le choix de ces positions a, et /3, est effectué selon la table 15 de la Fig. 2, la somme des contenus du registre en ces deux positions fournissant la séquence retardée y. Cette implémentation est avantageuse dans la mesure où elle ne nécessite pas l'utilisation d'une importante ligne à retard, de longueur r,. La somme des M-séquences X et y en 350 donne la séquence de Gold autrement dit la séquence d'étalement relative au satellite i. 20 On considérera dans la suite la synchronisation d'un récepteur par rapport à un signal d'un satellite i , autrement dit l'acquisition du signal satellitaire émis par le satellite i. Le récepteur échantillonne à la fréquence bribe le signal satellitaire reçu, après 25 translation en bande de base. Le récepteur forme une séquence de N échantillons successifs du signal ainsi reçu, où N > 2r . Ces N échantillons successifs sont constitués de valeurs souples, par exemple des rapports des logarithmes de valeurs de vraisemblance ou LLRs (Log Likelihood Ratios), et sont notés dans la suite r(0),...,r(N -1). 3025322 8 SP55859EA-T Les échantillons r(k) , k = N -1, peuvent s'exprimer sous la forme : r(k)= "..(k)55(k - + (k) (4) où ".i(k) =1-2x(k) et ÿ(k) 5(k)=1-2y(k) sont les versions BPSK des bits x(k) et y(k) . Les séquences x et y vérifient respectivement les équations de parité : gx (r - j)x (k + j) = 0 (5-1) i=0 gy(r - j)yi(k + j)= (5-2) i=0 les sommes portant ici sur des bits et donc étant calculées modulo 2. De manière similaire, la séquence de Gold ci formée par des M-séquences x et 15 y , vérifie la relation de parité : 2r g ,(2r - k)ci(k)= 0 k=0 Compte tenu du fait que ci(k) = x(k)+ y i(k) , 20 x(r - j)ci(k + j) =1 g x(r - j)yi(k + j) i=o i=o Compte tenu de la propriété précitée « add-and-shift » des M-séquences, il existe un entier O tel que : 5 10 (6) (7) 25 3025322 9 SP55859EA-T y i(k + 0i) =1 g '(r - j)y + (8) i=0 Compte tenu de (7) et (8), on a l'équation de parité : ( 5 Igx(r- j)ci(j+k) + yi(k+0)=0 (9) On comprend des expressions (5-2) et (9) que l'on peut décoder conjointement les séquences ci(k) et y i(k) à l'aide de deux décodeurs à passage de messages en cascade, comme représenté en Fig. 4. 10 Le premier décodeur est basé sur un premier graphe bipartite comprenant N premiers noeuds de variable, 410, et N - r premiers noeuds de contrôle, 420. Les premiers noeuds de variable sont initialisés avec les valeurs des échantillons r (0), , r (N -1) et les premiers noeuds de contrôle correspondent aux équations de parité (9). Les arêtes du premier graphe bipartite sont déterminées par les coefficients du polynôme générateur gx 15 et, plus précisément par les éléments de la matrice de parité de taille (N - r)x N : ( g x(r) - - - g,(0) 0 - - 0 0 g ,(0) - - - g ,(0) 0 0 (10) 0 0 g ,(r) - - - g,(0) 0 0 - 0 g ,(r) - - - gx(0)) chaque premier noeud de contrôle correspondant à une ligne de la matrice de parité H. . 20 A chacun des premiers noeuds de contrôle, 420, est associé de manière biunivoque un second noeud de variable. Plus précisément, à chaque premier noeud de contrôle k = 0 , , N - r -1 correspondant à l'équation de parité (9-2), est associé un second noeud de variable y i(k + . 3025322 10 SP55859EA-T Le second décodeur est basé sur un second graphe bipartite comprenant N -r seconds noeuds de variable, 430, et N -2r seconds noeuds de contrôle, 440. Les seconds noeuds de variable sont initialisés à des valeurs nulles de LLR (absence d'information a priori) et les seconds noeuds de contrôle correspondent aux équations de parité (5-2). Les 5 arêtes du second graphe bipartite sont déterminées par les coefficients du polynôme générateur gy et plus précisément par les éléments de la matrice de parité de taille (N-2r)x(N-r) : ( g y(r) - - - g y(0) 0 - - - 0 0 gy (0) - - - gy (0) 0 0 H Y (11) 0 0 g y(r) - - - g y(0) 0 0 . 0 gy(r) ... gy(0)) 10 chaque second noeud de contrôle correspondant à une ligne de la matrice de parité H. . Le premier décodeur à passage de messages permet d'obtenir une première estimation des variables c (k) , k = 0 N -1 et y (k + , k = 0 N - r -1. Le second décodeur à passage de messages permet ensuite d'affiner la première estimation des 15 variables y i(k + , k = 0 , N - r -1 à l'aide des contraintes imposées par les noeuds de contrôle 540. Cette seconde estimation affinée est ensuite utilsée dans le premier décodeur pour affiner la première estimation des variables ci(k) , k = 0,...,N -1 et y i(k + , k = 0,...,N - r -1. Le processus de décodage se poursuit ainsi jusqu'à ce qu'un critère d'arrêt soit satisfait, par exemple au bout d'un nombre prédéterminé d'itérations 20 ou bien lorsque les valeurs absolues de LLR des variables ci(k) , k = 0,...,N -1 sont supérieures à un seuil prédéterminé. D'autres critères d'arrêt pourront être envisagés par l'homme du métier sans sortir du cadre de la présente invention. Le passage du premier au second décodeur peut être effectué toutes les Li 1 itérations du premier décodeur. De manière similaire, le passage du second au premier 25 décodeur peut être effectué toutes les L2 1 itérations du second décodeur. On rappelle 3025322 11 SP55859EA-T qu'une itération d'un décodeur à passage de messages comprend un premier transfert de messages des noeuds de variables aux noeuds de contrôle via le graphe bipartite et un second transfert de messages en sens inverse. 5 La Fig. 5 représente schématiquement une méthode d'acquisition d'une séquence de Gold selon un mode de réalisation de l'invention. On suppose comme précédemment que la séquence de Gold ci à acquérir est la somme d'un première M-séquence x de polynôme générateur g., et d'une seconde M-séquence y, de polynôme générateur gy . On supposera que les deux polynômes 10 générateurs g., et gy sont de même degré et que le poids du polynôme gy est supérieur au poids du polynôme gx . On rappelle que le poids d'un polynôme est la somme des coefficients des monômes figurant dans ce polynôme. Ainsi les poids respectifs des polynômes g., et gy définis en (2) sont respectivement de 3 et 7. On sait que deux M-séquences de même taille, c'est-à-dire dont les polynômes 15 générateurs ont le même degré, sont reliées par une relation de décimation. Autrement dit, pour deux M-séquences z1 et z2 de polynômes générateurs respectifs gd et gz2 , de même degré r, il existe un facteur de décimation /721 et un offset 1/21 REVENDICATIONS1. Méthode d'acquisition d'une séquence de Gold (c1) étalant un signal à une fréquence bribe, ladite séquence de Gold étant obtenue comme somme d'une première M-séquence (x ) et d'une seconde M-séquence (yi) , la première M-séquence étant générée par un premier polynôme générateur ( gx ) et la seconde M-séquence étant générée par un second polynôme générateur (gy ), les premier et second polynômes générateurs étant de même degré et le poids du second polynôme générateur étant supérieur au poids du premier polynôme générateur, la méthode comprenant : (a) une étape de réception et d'échantillonage à la fréquence bribe dudit signal pour obtenir une pluralité d'échantillons représentatifs d'éléments successifs de ladite séquence de Gold ; (b) une première étape de décodage par passage de messages dans un premier graphe bipartite entre des premiers noeuds de variable (510) représentant les éléments successifs de la séquence de Gold et des premiers noeuds de contrôle (520), chaque noeud de contrôle étant associé de manière biunivoque à une variable (530) représentative d'un élément de la seconde M-séquence, les arêtes du graphe bipartie étant déterminées par les coefficients du premier polynôme générateur ; (c) une étape de décimation (533) des variables représentatives d'éléments successifs de la seconde M-séquence à l'aide d'un facteur de décimation prédéterminé pour obtenir des secondes variables représentatives d'éléments d'une troisième M-séquence, la troisième séquence (u ) étant de même longueur que la seconde séquence et étant générée par un troisième polynôme générateur de poids minimal ( ) ; (d) une seconde étape de décodage par passage de messages dans un second graphe bipartite entre lesdits seconds noeuds de variable (535) et des seconds noeuds de contrôle (540), les arêtes du second graphe bipartite étant déterminées par les coefficients du troisième polynôme générateur. 3025322 16 SP55859EA-T 2. Méthode d'acquisition d'une séquence de Gold selon la revendication 1, caractérisée en ce que l'on effectue une pluralité ( Li ) de premières étapes de décodage par passage de messages avant d'effectuer ladite étape de décimation (533). 5 3. Méthode d'acquisition d'une séquence de Gold selon la revendication 1 ou 2, caractérisée en ce qu'après la seconde étape de décodage par passage de messages, on effectue une opération inverse de celle de l'étape de décimation (533) pour mettre à jour lesdites variables (530) représentatives des éléments successifs de la seconde séquence. 10 4. Méthode d'acquisition d'une séquence de Gold selon la revendication 3, caractérisée en ce que l'on effectue une pluralité (L2) de secondes étapes de décodage par passage de messages avant d'effectuer une opération inverse de celle de l'étape de décimation. 15 5. Méthode d'acquisition d'une séquence de Gold selon la revendication 1 caractérisée en ce que les étapes (b) (c) (d) sont itérées jusqu'à ce qu'un critère d'arrêt prédéterminé soit satisfait. 6. Méthode d'acquisition d'une séquence de Gold selon la revendication 5, 20 caractérisé en ce que, lorsque le critère d'arrêt est satisfait on détermine à partir des valeurs des premières variables représentatives des éléments de la séquence de Gold et des variables représentatives des elements successifs de la seconde séquence l'instant de génération de ladite séquence de Gold. 25