FR 3032571 A1 20160812 FR 1551116 A 20150211 1 MÉTHODE DE DÉCODAGE ITÉRATIF DE SÉQUENCES LFSR À FAIBLE PROBABILITÉ DE FAUSSE ALARME DESCRIPTION DOMAINE TECHNIQUE La présente invention concerne de manière générale le domaine du décodage itératif par passage de messages, et plus particulièrement celui de séquences de longueur maximale. ÉTAT DE LA TECHNIQUE ANTÉRIEURE Les séquences de longueur maximale, encore dénommées M-séquences, sont des séquences binaires présentant de très bonnes propriétés de corrélation. Elles sont pour cette raison largement utilisées dans la synchronisation des récepteurs de systèmes de télécommunication sans fil ou de systèmes de positionnement. Une méthode classique de synchronisation d'un récepteur au moyen d'une M-séquence consiste à effectuer une corrélation du signal reçu avec une réplique de la M-séquence. Si un pic de corrélation est observé et si son amplitude est supérieure à un niveau de seuil prédéterminé, le récepteur est synchronisé sur le pic en question. On rappelle qu'une M-séquence est obtenue à partir d'un polynôme générateur primitif. Si ce polynôme est de degré r, la période de la séquence est maximale, soit de longueur 2T -1. En pratique, une M-séquence peut être générée à partir d'un registre à décalage rebouclé sur lui-même, encore dénommé LFSR (Linear Feedback Shift Register), les prises du registre correspondant aux coefficients du polynôme générateur. La Fig. 1 représente un exemple de générateur de M-séquence utilisant un registre LFSR, selon une structure dite de Fibonacci. Le polynôme générateur (primitif) servant à générer la M-séquence est ici : 3032571 g(X) =1g kXk k=0 Le générateur est initialisé par un mot de r bits qui est stocké dans le registre à décalage. Le code ainsi généré, dit code simplexe, est un code cyclique [N, ri où N = 2' -1 5 est la taille du mot de code et r le nombre de bits d'information. Le polynôme de vérification (check polynomial), encore dénommé polynôme de parité, associé au polynôme générateur g (x) est h(x) = (xN -1)1 g (x) . On peut montrer que pour le code simplexe h(x) = x" g (x-1) et que la matrice de parité associée à ce code est la matrice H de taille (N - r)x N donnée par : 10 gr - go O - 0 0 gr --- go 0 0 H= (2) 0 0 gr - - - go 0 0 --- 0 gr --- g0 Une méthode alternative de décodage consiste à considérer les éléments de la M- 15 séquence comme des noeuds de variables et les équations de parité auxquelles ceux-ci doivent satisfaire, comme des noeuds de contraintes. Il est alors possible d'effectuer un décodage itératif à passage de messages dans un graphe bipartite formé par les noeuds de variables et les noeuds de contraintes, les arêtes entre noeuds de variables et noeuds de contraintes étant donnés par les éléments de la matrice de parité. On trouvera par 20 exemple un décodage itératif de M-séquence par passage de messages dans l'article de O.W. Yeung et al. intitulé « An iterative algorithm and low complexity hardware architecture for fast acquisition of long PN codes in UWB systems » publié dans Journal of VLSI Signal Processing 43, pp. 25-42, 2006. 2 (1) 25 En pratique, un décodage itératif de M-séquence à passage de messages converge 3032571 3 lentement si l'on utilise un graphe bipartite basé sur la matrice de parité donnée par expression (2). Pour remédier à cette difficulté, il a été proposé dans l'article précité de combiner une pluralité de sous-graphes élémentaires, chaque sous-graphe élémentaire correspondant à un ensemble de nouvelles équations de parité. Plus précisément, les 5 noeuds de variables restent identiques et l'on introduit des noeuds de contraintes redondants. En effet, la somme d'une pluralité d'équations de parité (par exemple celles correspondant aux lignes de la matrice H) est encore une équation de parité. On aboutit alors à un graphe constitué de plusieurs sous-graphes élémentaires bipartites, ces différents sous-graphes élémentaires partageant l'ensemble des noeuds de 10 variables et chaque sous-graphe élémentaire comprenant ses noeuds de contraintes spécifiques. En d'autres termes, cela revient à utiliser une matrice de parité étendue, Hex, obtenue par concaténation de K matrices de parité élémentaires : Ho He,, = H1 (3) H K-1 Les matrices de parité élémentaires Ha étant des matrices de Toeplitz circulantes, de taille (N -ra)xN définies par : C a ,0 0 0 0 0 0 0 0 15 (4) H, 0 ca,0 0 0 - - - Ca, â-1 Ca ,1 0 0 C am 20 3032571 4 Chaque matrice élémentaire 11, représente la convolution de la séquence d'échantillons reçus avec un polynôme de parité ha(x) =1+x`° +...+ xra de degré ra et chaque ligne de cette matrice correspond à une équation de parité basée sur ce polynôme. 5 La synchronisation du récepteur consiste à déterminer si une suite de M échantillons reçus, y = (y0...y m_1) correspond à une portion de séquence LFSR, autrement de déterminer si cette suite d'échantillons peut être décodée par le décodeur à passage de messages. Si c'est bien le cas, le récepteur peut en déduire le début de la séquence (le mot initial dans le registre LFSR) et l'endroit où se trouve la suite d'échantillons dans la 10 séquence. Le récepteur doit par conséquent faire le choix entre deux hypothèses : AO Yk = Wk (5-1) 15 Al : yk = sk + wk (5-2) où sk sont les éléments de la séquence LFSR et wk sont des échantillons de bruit. Si le récepteur détermine qu'il a détecté une séquence LFSR (hypothèse A1) alors que les échantillons reçus sont en réalité du bruit (hypothèse Ao valide), on a une situation 20 de fausse alarme. On suppose ici pour simplifier que le récepteur observe une suite de M =N échantillons consécutifs, autrement dit un nombre d'échantillons correspondant à la longueur d'une séquence LFSR. Pour faire le choix entre les hypothèses Ao et Ai, le décodeur effectue un décodage 25 itératif à passage de messages de la suite d'échantillons, les noeuds de variables étant initialisés au moyen de ces échantillons. Le décodage à passage de messages peut être effectué de manière connue au moyen d'un algorithme de type Sum-product tel que décrit dans l'article de Kschichang et 3032571 5 al. intitulé « Factor graph and the sum-product algorithm » publié dans IEEE Trans. on Information Theory, vol. 47, no. 2, Feb. 2001 ou bien d'un algorithme de type Min-Sum tel que décrit dans la thèse de N. Wiberg intitulée « Codes and decoding on general graphs », University of Linkôping, Sweden, 1996. 5 Le récepteur détermine que l'hypothèse Al est satisfaite si : IlextyT =0 (6) 10 où Hext est définie par les expressions (3) et (4). Autrement dit, le récepteur vérifie que toutes les équations de parité sont satisfaites. On a pu constater que le choix des polynômes ha(x) pouvait fortement influencer la probabilité de fausse alarme ( PFA ) du récepteur. 15 La Fig. 2 montre par exemple la probabilité de fausse alarme pour un récepteur décodant une séquence LFSR générée à partir d'un polynôme générateur dont les coefficients sont définis en numérotation octale par le mot 2415. Pour le décodage, on a choisi une matrice de parité étendue, Ilex' constituée par la concaténation de K =5 matrices de parité élémentaires Ha, chaque matrice 11, 20 correspondant à un polynôme ha(x) de poids 3. On rappelle que le poids d'un polynôme est le nombre de ses monômes non nuls. On a représenté sur la figure la probabilité de fausse alarme ( PFA ) en fonction du rapport signal sur bruit en réception ( SNR ), ce pour différentes combinaisons de K =5 matrices Ha . Les différentes combinaisons, et donc les différentes matrices Hext sont 25 désignées par a,b,c,d,e . On remarque que le taux de fausse alarme varie de trois ordres de grandeurs selon la combinaison de polynômes sélectionnée. 3032571 6 Le but de la présente invention est de proposer une méthode de décodage de séquence LFSR (ou M-séquence) présentant un très faible taux de fausse alarme (PFA ) sans sacrifier la vitesse de convergence. EXPOSÉ DE L'INVENTION 5 La présente invention est définie par une méthode de décodage itératif à passage de messages d'une séquence LFSR de longueur N générée au moyen d'un polynôme générateur, ladite séquence LFSR étant associée, comme code simplexe, à une matrice de parité, H, ladite méthode de décodage comprenant les étapes suivantes : (a) détermination d'un ensemble de polynômes de parité, de poids égal à 3 et de 10 constante égale à 1, correspondant à une combinaison d'équations de parité de la matrice H ; (b) génération d'une matrice de parité étendue Hext par concaténation d'un nombre prédéterminé K de matrices de parité élémentaires, respectivement associées à K polynômes de parité sélectionnés dans ledit ensemble ; 15 (c) vérification que le graphe de Tanner associé à la matrice Hext ne comporte pas de cycle de longueur 4 et, en absence de tel cycle, (d) calcul du nombre de cycles de longueur 6 au sein du graphe de Tanner et, dans le cas où ce nombre est égal à NK, stockage dans une table de la combinaison des polynômes de parité sélectionnés à l'étape (b) ; 20 les étapes (b), (c), (d) étant répétées pour toutes les combinaisons de K polynômes de parité dudit ensemble ; et (e) calcul pour chaque combinaison de polynômes de parité stockée dans ladite table du nombre de cycles de longueur 8 dans le graphe de Tanner associé à la matrice Hext ; 25 (f) sélection d'une combinaison de K polynômes de parité correspondant au plus faible nombre de cycles de longueur 8 calculé à l'étape (e) pour effectuer un décodage itératif à passage de messages de ladite séquence dans le graphe de Tanner associé à la matrice Hext générée à partir de la combinaison ainsi sélectionnée. 3032571 7 La vérification à l'étape (c) consiste avantageusement à déterminer si l'une des conditions suivantes rb -ib = ia , rb -ib = â, rb - ib =-ia ; =ib est satisfaite pour au moins un couple quelconque de polynômes de parité g a(x) =1+ xia +x° et g b(x) =1+ xib + xrb , parmi les K polynômes de parité sélectionnés à l'étape (b), l'absence 5 d'un cycle de longueur 4 dans le graphe de Tanner étant établie si aucune des conditions précédentes n'est satisfaite. Le nombre de cycles de longueur 6 dans le graphe de Tanner associé à la matrice Hext peut être obtenu à partir de N6 = -1 (tr(A3)-3KN ((K2 +3K +1)-9(K +1)+2)) où A = Ilil et tr(.) est la fonction trace. exteTxt 10 Le calcul du nombre de cycles de longueur 8 dans le graphe de Tanner associé à la matrice Hext comprend le calcul de tr(A4)-4(3K+1)tr(Al où A =H''1-1T, et tr(.) est la fonction trace. K-1 K -1 K -1 La trace tr(A3) peut être obtenue par tr(A3)=IIITy.k i=0 1=0 k=0 où Tiik = Ak , y)Aki (0,16)4ii (0,a), 4 (,u,v) étant l'élément à la ligne ,u et la cre Ç j fle 524 15 colonne v de la matrice A o = H HT où Hi et 111 sont les matrices de parité j élémentaires associées à deux polynômes de parité parmi les K polynômes de parité sélectionnés à l'étape (b), a ço(s ; /3= ço(h - É) ; y= ço(s - h) où : u si 0 N -1 N+u si -N REVENDICATIONS1. Méthode de décodage itératif à passage de messages d'une séquence LFSR de longueur N générée au moyen d'un polynôme générateur, ladite séquence LFSR étant associée, comme code simplexe, à une matrice de parité, H, ladite méthode de décodage comprenant les étapes suivantes : (a) détermination (410) d'un ensemble de polynômes de parité, de poids égal à 3 et de constante égale à 1, correspondant à une combinaison d'équations de parité de la matrice H ; (b) génération(440) d'une matrice de parité étendue Hext par concaténation d'un nombre prédéterminé K de matrices de parité élémentaires, respectivement associées à K polynômes de parité sélectionnés dans ledit ensemble ; (c) vérification (450) que le graphe de Tanner associé à la matrice Hext ne comporte pas de cycle de longueur 4 et, en absence de tel cycle, (d) calcul (460) du nombre de cycles de longueur 6 au sein du graphe de Tanner et, dans le cas où ce nombre est égal à NK , stockage dans une table (475) de la combinaison des polynômes de parité sélectionnés à l'étape (b) ; les étapes (b), (c), (d) étant répétées pour toutes les combinaisons de K polynômes de parité dudit ensemble ; et (e) calcul (480) pour chaque combinaison de polynômes de parité stockée dans ladite table du nombre de cycles de longueur 8 dans le graphe de Tanner associé à la matrice Hext; (f) sélection (490) d'une combinaison de K polynômes de parité correspondant au plus faible nombre de cycles de longueur 8 calculé à l'étape (e) pour effectuer un décodage itératif à passage de messages de ladite séquence dans le graphe de Tanner associé à la matrice Hext générée à partir de la combinaison ainsi sélectionnée. 2. Méthode de décodage itératif selon la revendication 1, caractérisée en ce que la 3032571 20 vérification à l'étape (c) consiste à déterminer si l'une des conditions suivantes rb -ib =ia , rb -ib = ra,rb- ib =-ia; = ib est satisfaite pour au moins un couple quelconque de polynômes de parité g b(x) =1+ +x° et g b(x) =1+ xib + xrb , parmi les K polynômes de parité sélectionnés à l'étape (b), l'absence d'un cycle de longueur 4 dans le graphe de 5 Tanner étant établie si aucune des conditions précédentes n'est satisfaite. 3. Méthode de décodage itératif selon l'une des revendications précédentes, caractérisée en ce que le nombre de cycles de longueur 6 dans le graphe de Tanner associé à la matriceHext est obtenu à partir de 10 N6 = - (tr(A3 ) - 3KN ( ( K 2 +3K +1)-9(K +1)+ 2)) oùA=Ilextil eTxt et tr(.) est la fonction trace. 4. Méthode de décodage itératif selon l'une des revendications précédentes, caractérisée en ce que le calcul du nombre de cycles de longueur 8 dans le graphe de 15 Tanner associé à la matrice Hext comprend le calcul de tr(A4)-4(3K+1)tr(Al où A = HHT et tr(.) est la fonction trace. 5. Méthode de décodage itératif selon la revendication 3 ou 4, caractérisée en ce K-1 K-1 K-1 que la trace tr (A' ) est obtenue en calculant tr (A' ) =111Tk où - " i=0 j=0 k=0 20 Tijk = kt ( ,y)Ak ( ,16)A ( , a) aEçàji fle çà ki (4u,v) étant l'élément à la ligne ,u et la colonne v de la matrice Ai,1 = HiHTi , où Hi et H1 sont les matrices de parité élémentaires associées à deux polynômes de parité parmi les K polynômes de parité sélectionnés à l'étape (b), a = v(s-,e); = v(h-,e); y= ço(s - h) où : 25 3032571 21 u siOttAT -1 N+u si -N 6. Méthode de décodage itératif selon la revendication 4, caractérisée en ce que la K-1 K-1 K-1 K-1 trace tr(A4) est obtenue en calculant tr(A4) = 1111T.k où : yk i=0 1=0 k=0 k=0 5 = ki (0, (a+ 16+ rmodN))Ak,i ( 41) ( (0, y) Leen,, flenk, re 10 4,, (,u,v) étant l'élément à la ligne ,u et la colonne v de la matrice A = .HT. "1 où Hi et H1 sont les matrices de parité élémentaires associées à deux polynômes de parité parmi les K polynômes de parité sélectionnés à l'étape (b), a = ço(s - ,e) ; fi = ço(h - ,e) ; y= v(s-h) où : u siOttAT -1 15 eu) N+u si -N 7. Méthode de décodage itératif selon l'une des revendications précédentes, caractérisé en ce qu'elle utilise un algorithme de type Min-Sum sur le graphe de Tanner associé à la matrice Hext générée à partir de la combinaison sélectionnée à l'étape (e). 8. Méthode de décodage itératif selon l'une des revendications 1-6, caractérisée en 3032571 22 ce qu'elle utilise un algorithme de type Sum-Product sur le graphe de Tanner associé à la matrice 1-1,,,, générée à partir de la combinaison sélectionnée à l'étape (e). 9. Méthode de décodage itératif selon l'une des revendications précédentes, 5 caractérisée en ce que l'on applique un critère de convergence aux valeurs des noeuds de variables du graphe de Tanner après un nombre prédéterminée d'itérations et si ce critère n'est pas satisfait, on conclut à une absence de la séquence LFSR.