Brevet FR2883435A1 — publié le 20060922

- 1 " Procédé de décodage de codes matriciels, module de décodage associé, et applications mettant en oeuvre un tel procédé." La présente invention se rapporte à un procédé et un module pour décoder des codes matriciels reçus notamment dans un système de transmission utilisant de la diversité spatiale et/ou temporelle et/ou fréquentielle. L'invention concerne également des applications pour la mise en oeuvre du procédé selon l'invention. Toutefois, l'invention est d'un cadre plus large puisqu'elle peut s'appliquer à tout système de décodage dans lequel les éléments traités obéissent à l'équation suivante: Y=HX+B, où X représente le message à estimer, H une matrice réelle, et B le signal représentant le bruit. D'une façon générale, l'invention trouve son origine dans la résolution d'une façon quasi-optimale du problème ILS ("Integer Least squares", en anglais) suivant: Min j IY-Hxj 12 et X E C (C ensemble discrète entière). Une application particulièrement avantageuse de l'invention se trouve en effet dans le domaine des réseaux de communication sans fil dans lequel on désire recomposer un message transmis X. Après avoir subi de nombreuses contraintes dues au canal de transmission, ce signal transmis X est noyé dans un signal reçu Y. Ces contraintes sont essentiellement liées à la propagation multi-chemins. Cette propagation multiple est due au fait qu'un signal radio atteint une antenne par plusieurs chemins via des réflexions sur l'ionosphère et sur des objets terrestres tels que des montagnes et des bâtiments par exemple. Les effets de cette propagation multiple sont des interférences constructives et destructives ainsi que des décalages de phases du signal émis. De même le message X peut être émis sur une série de sous porteuses adjacentes et orthogonaux. Chaque sous- porteuse pourra être affectée d'une atténuation et d'une phase différente. Pour élaborer un système de communication fiable et robuste, on utilise des techniques de codage à l'émission et des techniques de décodage correspondantes à la réception. En particulier, aujourd'hui, les canaux de transmission de type MIMO 35 par exemple ("Multiple Input and Multiple Output" en langue anglaise) - 2comportant plusieurs antennes à l'émission et plusieurs antennes à la réception offrent une grande efficacité spectrale par rapport aux canaux de transmission de type SISO ("Single Input and Single Output" en langue anglaise). La capacité du canal de transmission de type MIMO augmente linéairement avec le nombre d'antennes de transmission dans la mesure où le nombre d'antennes à la réception reste supérieur ou égal au nombre d'antennes à la transmission. Il est nécessaire de concevoir des modules de codage et de décodage aptes à traite des signaux de très haut débit avec une fiabilité suffisante. io On connaît de nombreuses techniques de décodage permettant d'estimer le signal émis X à partir du signal reçu Y. Une première catégorie de ces algorithmes concerne les algorithmes à annulation d'interférences tel BLAST ("Bell Laboratories Layered Space-Time") qui ont de mauvaises performances en terme de taux d'erreurs fonction du rapport signal à bruit. Une seconde catégorie concerne notamment les algorithmes à maximum de vraisemblance qui sont optimum en terme de performances, mais d'une grande complexité d'implantation tel que le décodeur par sphères. On connaît le document "Efficient Detection Algorithms for MIMO Channels: A Geometrical Approach to Approximate ML Detection"; H. Artes et al, IEEE Transactions on Signal Processing, Vol. 51 (2003), 11; 2808-2820; dans lequel l'auteur présente un décodage à base d'une décomposition du type SVD dans le domaine complexe. Cette méthode de l'art antérieur décrite par Artes présente une grande complexité en terme d'implémentation matérielle. La présente invention a pour but la conception d'un nouveau décodeur quasi-optimum en terme de performances avec une faible complexité de calcul. Un autre but de l'invention est la conception d'un décodeur présentant une implémentation matérielle simple et déterministe. On atteint au moins l'un des objectifs précités avec un procédé pour décoder un signal vecteur Y de dimension (m,1), tel que Y=HX+B, où X est un vecteur de dimension (n,1) dont les éléments appartiennent à un sous ensemble fini appelé constellation C, H est une matrice réelle de dimension (m, n), et B est un vecteur de type bruit blanc gaussien de dimension (m,l). Le décodage a pour but d'obtenir une estimation du vecteur X. Selon l'invention, le procédé comprend les étapes suivantes dans un espace 93" : 3 a) calcul d'un point de référence Xr qui est une première estimation de X, obtenue par une méthode d'optimisation convexe non contrainte X E gin; b) détermination d'au moins un vecteur V1 correspondant à un vecteur singulier droit de la matrice H; c) détermination d'une droiteMl passant par Xr et ayant V1 comme vecteur directeur; d) détermination du point d'intersection I entre la droite Al et au moins un hyperplan de l'espace 9i e) projection du point I sur la constellation C de façon à générer au lo moins un point candidat Ip de la constellation C; et f) détermination d'un point Xe qui est une estimation finale de X, à partir du point candidat Ip. La constellation C étant un ensemble discret par définition, le point Xr E Idéalement, le point Xe est égale à X émis. Avec le procédé selon l'invention, on utilise une approche géométrique faisant intervenir les vecteurs singuliers droits de la matrice H. En particulier, on part d'un point d'origine Xr par une méthode notamment conventionnelle, et on recherche au moins un autre point I appartenant à la droite passant par Xr et de direction un vecteur singulier droit de la matrice H. On sait que si le vecteur directeur de la droite est associé à la plus faible valeur singulière de H, la fonction coût f(x) = IY-H.Xl 1 reste faible. Ce point I est ensuite projeté dans la constellation C de façon à retrouver une estimation valide de X. La complexité des calculs est faible dans la mesure où les calculs ne sont pas de type itératifs mais plutôt linéaires. En outre, contrairement à l'art antérieur, notamment le document Artes où les calculs sont réalisés dans l'espace complexe, dans la présente invention, les calculs sont réalisés dans l'espace réel Quand bien même le problème se présenterait dans l'espace complexe, il suffirait de se ramener à l'espace réel en faisant une transformation connue de l'homme du métier, puis en appliquant le procédé selon l'invention. En particulier, ledit au moins un vecteur V1 correspond à un axe dominant du bruit de la matrice H. Lorsqu'on utilise plusieurs vecteurs singuliers droits, chacun correspond à un axe dominant du bruit de la matrice H. - 4Par ailleurs, à l'étape b), on réalise une décomposition de type SVD (pour "Singular Value Decomposition" en langue anglaise) de façon à en déduire ledit au moins un vecteur singulier droit correspondant à la valeur singulière la plus faible de la matrice H. Une décomposition SVD peut être définie de la manière suivante: soit une matrice H, m x n. On rappelle que la décomposition de H en valeurs singulières est un triplet de matrices, U, let V telles que: - X est une matrice n x n diagonale dont les termes diagonaux (les valeurs singulières) sont positifs ou nuls et rangés par ordre décroissant. Le nombre de valeurs singulières non nulles est égal au rang de la matrice. - U et V sont des matrices orthonormées UtU=VtV=I,,. Les colonnes de U et V sont connues sous les nom de vecteurs singuliers respectivement gauches et droits de H. - H=U E Vt Le vecteur V1 correspond à la dernière colonne de la matrice V. Les valeurs singulières d'une matrice H sont les racines carrées des valeurs propres de HtxH. Alors que les valeurs propres sont liées aux directions invariantes par la transformation H, les valeurs singulières contiennent l'information "métrique" sur cette transformation. En dimension 2 l'image du cercle unité par H est un ellipsoïde dont la longueur des demi-axes principaux correspondent aux valeurs singulières maximale et minimale. En particulier, la matrice H est rectangulaire de dimension, m x n, elle est donc au plus de rang n. Supposons par la suite que H est de rang p: HtH=V12Vt HtH est une matrice de dimension n x n dont les valeurs propres sont telles que: f122 2P>0 2k =0 p La méthode d'optimisation convexe peut consister en une résolution de la minimisation de la distance IIY - H.XII, correspondant à la méthode dite lo de "zéro forcing" dans fit". D'autres méthodes conventionnelles peuvent être utilisées telles que par exemple MMSE (pour "minimum mean squared error" en langue anglaise), ou d'autres méthodes sous-optimales (PIC, SIC). Selon une caractéristique avantageuse de l'invention, ledit au moins hyperplan est obtenu par une équation du type x(i) = s, avec x(i) représentant la i1ème coordonnée d'un point x de l'espace 3t" et s un réel. Dans ce cas, l'hyperplan est parallèle à une face de l'hypercube ayant pour sommets la constellation C dans l'espace e. La valeur de s peut avantageusement être égale à une valeur de la constellation C. Dans ce cas, l'hyperplan comprend une des faces de l'hypercube ayant comme sommets la constellation C dans l'espace 9l La valeur de s peut aussi être égale à zéro; la hème coordonnée du point d'intersection I étant alors nulle, la projection de cette i'ème coordonnée sur la constellation C est alors égale à l'opposée du signe de la i1ème coordonnée Xr. Autrement, l'hyperplan peut être obtenu à partir dudit au moins un vecteur V1. Par exemple, on peut définir l'hyperplan de telle sorte que le vecteur normal à cet hyperplan est donné par la projection du vecteur V1 sur la constellation C. Selon une première variante de l'invention, à l'étape f), Xe est le point 30 candidat Ip. Cette variante constitue une solution simple et rapide en temps de calcul. Selon une seconde variante avantageuse de l'invention: - on détermine à l'étape b), D vecteurs V1, V2,...,VD correspondant chacun à un vecteur singulier droit de la matrice H; - 6- on détermine à l'étape c) , D droites Al, A2,..., AD passant par Xr et ayant respectivement V1, V2,. .., VD comme vecteur direction; - on détermine à l'étape d), au plus anD points d'intersection Ik entre les droites Al, A2,..., AD et au plus an hyperplans, chaque hyperplan comprenant une des faces de l'hypercube ayant comme sommets la constellation C dans l'espace 9i" , avec k allant de 1 à anD et a étant le nombre des points d'intersections par dimension; par exemple si C={-1, 1}, alors on peut prendre a=2; - on en déduit à l'étape e), au plus anD points candidats Ipk, avec k = 1...anD; - on calcule à l'étape f), au plus les anD distances 11Y - H.Ipkl I; et on considère le point candidat de distance minimale comme étant le point décodé Xe. En d'autres termes, on multiplie le nombre de points candidats en prenant plusieurs vecteurs singuliers droits correspondant notamment à plusieurs axes dominants du bruit de la matrice H; on multiplie également le nombre d'hyperplans; Xe étant le point qui présente une distance minimale parmi l'ensemble des points candidats. Selon encore une troisième variante avantageuse de l'invention, on reprend l'ensemble des étapes de la seconde variante et on change l'étape f) de la manière suivante: on calcule à l'étape f), au plus les anD distances I IY - H.Ipkl 1; et on détermine D sous ensembles chacun contenant M points candidats dont les distances I IY - H.Ipkl 1 sont les plus faibles, puis on utilise ces D sous ensembles pour initier un algorithme de recherche d'optimum local, le point candidat obtenu à l'issue de cette recherche ayant la plus faible valeur de la fonction coût est considéré comme étant le point décodé Xe. Plus précisément, les D sous ensembles correspondent aux D droites Al, 02, ..., AD. Avantageusement, on utilise l'algorithme conventionnelle glouton ("Greedy" en langue anglaise) pour la recherche de l'optimum local, qui est une recherche de l'optimum dans les voisins ayant une distance de Hamming égale à 1 par rapport au point initial X (Ipk). Cette recherche fait notamment intervenir le calcul de distance du typeI IY - H.XI 1 dans le calcul des distances des points voisins. La Distance de Hamming est le nombre de coordonnées différentes entre deux vecteurs. La fonction glouton peut être décrite comme une fonction de recherche local permettant de minimiser la fonction coût f(X)= I IY - H.XI I dans un voisinage du point initial. Le voisinage est défini de tel sorte que les points visités ont une distance de Hamming égale à 1 par rapport au point initial. D'une façon générale, chaque distance du type I IY - H.XI I calculée dans les différentes étapes et au sein de la fonction "glouton" peut être réalisée selon la norme euclidienne ou norme 2, dans ce cas il s'agit d'une distance quadratique, ou selon la norme 1, dans ce cas il s'agit d'une distance de Manhattan. De préférence, pour limiter le temps de calcul, à l'étape e), on supprime des points candidats Ipk redondants. Les points candidats redondants sont des points identiques mais provenant de points d'intersection différents. Avec le procédé selon l'invention, lorsqu'on a plusieurs vecteurs singuliers droits, on peut réaliser les processus (étapes b) à e) notamment) de façon parallèle, sans itérations. On peut alors réaliser une implémentation matérielle simple, efficace et rapide lors de la conception. A titre d'exemples non limitatifs, la constellation est égale à c = {-1,1} 20 ou à C = {-3,-1,1,3}. Avantageusement, lorsque la constellation C est égale à {-1,1}, à l'étape e), il n'est pas nécessaire de calculer le ou les points d'intersection, il suffit d'en déterminer le signe. L'explication est la suivante: on suppose que n = 2. Etant donnée une droite Al de vecteur directeur V1 et passant par Xr, et un hyperplan P représentant une des faces de l'hypercube ayant comme sommets la constellation C en dimension n, on est amené à chercher et projeter sur la constellation C" le point d'intersection I= Ain P. A1= {zER"/ z=Xr + V1 avec RER} P = {zER" / z(i)= s} Soit i = 1 et s = 1 I= A1n P. equivalent à s=Xr(1)+ f3 V1(1) a R = sXr(1)/V1(1) Ip = projection de I sur {-1,1}" Ip(1) = I(1) = s E {-1,1} I(2) = Xr(2)+[s-Xr(1)/V1(1)]*V1(2) -8 Ip(2)=Sign(I(2)) = sign(Xr(2)+[sXr(1)/V1(1)]*V1(2)) = xorsign(Xr(2)*V1(1) -Xr(1)*V1(2) +s*V1(2) ,V1(1)) ; = xorsign(Xr(2)*V1(1) -Xr(1)*V1(2) +V1(2) ,V1(1)) ; Si V1(1)=0 on prend Ip=sign(Xr). Ci-après un exemple de réalisation de la fonction xorsign: fonction a =xorsign(opl,op2) si (sign(opl) = =sign(op2)) 10 a=+1; sinon a=-1; fin; fin fonction Ainsi, on ne calcule pas explicitement les coordonnées du point I, mais on détermine seulement sonsigne. Suivant un mode de mise en oeuvre avantageux de l'invention, on détermine en outre une estimation de la fiabilité de Xe. Pour ce faire, lors des calculs de distance I IY - H.Ipj 1, on mémorise dans une table les distances minimales trouvées pour chaque valeur c de la constellation C et pour chaque coordonnée de Ip; puis on estime la fiabilité de Xe à partir de ladite table. En d'autres termes, pour C = {-1,1} par exemple, la table comprend deux colonnes, une première colonne (-1) et une seconde colonne (+1). Les lignes de cette table correspondent à la i1ème coordonnée de Ip avec i allant de 1 à n (dimension de X). Pour chaque distance I IY - H.IpI I calculé, on conserve dans le tableau, pour chaque coordonnée et pour la valeur c concernée, la valeur de distance minimale. Déterminer la fiabilité à partir de ce tableau est largement à la portée de l'homme du métier. Ensuite, on peut transmettre le point décodé Xe et l'estimation de la fiabilité associée vers un code correcteur d'erreur à décision souple en entrée. Suivant un autre aspect de l'invention, il est proposé un module de décodage mettant en oeuvre un procédé tel que décrit précédemment, pour décoder un signal vecteur Y de dimension (m,1), tel que Y=HX+B, où X est un vecteur de dimension (n,l) dont les éléments appartiennent à un sous ensemble fini appelé constellation C, H est une matrice réelle de dimension - 9- (m, n), et B est un vecteur de type bruit blanc gaussien de dimension (m,1), en vue d'obtenir une estimation du vecteur X. Selon l'invention, ce module comprend: - des moyens pour calculer dans l'espace e un point de référence Xr, 5 qui est une première estimation de X, par une méthode d'optimisation convexe non contrainte; - des moyens pour déterminer au moins un vecteur V1 correspondant à un vecteur singulier droit de la matrice H; - des moyens pour déterminer une droite Al passant par Xr et ayant V1 io comme vecteur directeur; - des moyens pour déterminer un point d'intersection I entre la droite Al et au moins un hyperplan de l'espace - des moyens pour projeter le point I sur la constellation C de façon à générer au moins un point candidat Ip de la constellation C; et - des moyens pour déterminer un point Xe qui est une estimation finale de X, à partir du point candidat Ip. Ces moyens peuvent être implémentés sous forme de blocs fonctionnels dans des circuits de type FPGA (Field-Programmable Gate Arrays), ASIC (Application Specific Integrated Circuit) ou DSP (Digital Signal Processor). Avantageusement, le module comprend une architecture parallèle apte à déterminer Xe par traitements parallèles à partir d'une pluralité de vecteurs Vi passant par Xr et correspondant à des vecteurs singuliers droits de la matrice H. Suivant encore un autre aspect de l'invention, il est proposé une application du procédé précédemment décrit, pour le décodage d'un signal numérique dans un système de communication sans fil. L'invention propose également une application du procédé précédemment décrit, pour le décodage d'un signal numérique Y, le signal d'émission X ayant subit une modulation du type compris dans la liste suivante: MIMO; CDMA; MC-CDMA, BLAST. L'invention propose encore une application du procédé précédemment décrit, pour le décodage d'une image dans un système de traitement d'image. En effet, on peut vouloir restituer une image précédemment déformée à la suite d'un zoom ou de toute autre déformation linéaire, -10 l'invention s'applique lorsque l'image Y peut être modélisée sous la forme: Y= HX + B, X étant l'image d'origine à restituer. D'autres avantages et caractéristiques de l'invention apparaîtront à l'examen de la description détaillée d'un mode de mise en oeuvre nullement 5 limitatif, et des dessins annexés, sur lesquels: la figure 1 est un schéma simplifié d'une partie d'une chaîne de transmission dans un système multi-antennes; - la figure 2 est un organigramme illustrant différentes étapes du procédé selon l'invention; la figure 3 est un schéma blocs d'une partie d'un circuit intégré mettant en oeuvre le procédé selon l'invention; - la figure 4 est un graphe illustrant le taux d'erreurs bit (BER) par rapport au rapport-signal-à-bruit (SNR) pour un décodeur selon l'invention en comparaison avec des décodeurs classiques, dans un système utilisant cinq antennes à l'émission et cinq antennes à la réception; et la figure 5 est un graphe illustrant le même rapport que sur la figure 4 mais dans un système utilisant vingt-cinq antennes à l'émission et vingt-cinq antennes à la réception. Bien que l'invention n'y soit pas limitée, on va maintenant décrire le procédé selon la présente invention au décodage d'un signal transmis via un système de communication sans fil multi-antennes. Sur la figure 1, la chaîne de transmission fait intervenir à l'émission, un module de code correcteur d'erreur 1 permettant d'introduire une redondance dans l'information à transmettre. Le modulateur 2a permet de moduler le signal à émettre selon différentes techniques telles que le CDMA, MC-CDMA, MIMO ou autres... Les modules de transmission 3 envoient les signaux ainsi modulés vers plusieurs antennes 4. A la réception, chaque antenne 5 capte les signaux provenant des différentes antennes d'émission 4 ensemble avec des perturbations et bruits dus à la propagation des ondes. Les modules de réception 6 relaient les signaux reçus vers un démodulateur 2b de façon à démoduler le signal reçu en fonction de la technique utilisée dans le modulateur 2a lors de l'émission. Le décodeur 7 selon la présente invention reçoit le signal généré par le démodulateur 2b et a pour rôle - 11- d'estimer le signal initialement transmis par les antennes à l'émission et de le fournir à un décodeur canal ou turbo code ou LDPC 10 sous forme d'un signal série 9. Le décodeur 7 selon l'invention permet également de fournir une fiabilité 8 associée au signal estimé. Pour des applications de décodage itératif, on peut re-injecter la sortie du décodeur canal 10 dans l'entrée du décodeur HISD 7. Ainsi, on réalise le procédé selon l'invention en considérant Xr(nouvelle itération) = Xe(obtenu à l'itération précédente). A la réception, pour estimer le signal émis, le système peut être modélisé sous la forme de l'équation suivante: Y=HX+B, où Y est le vecteur représentatif du signal reçu par les antennes 6, de dimension (m, 1); X est un vecteur représentatif du signal émis devant être estimé, de dimension (n,1) dont les éléments appartiennent à un sous ensemble fini appelé constellation C; H est une matrice réelle de dimension (m, n) représentative du canal de transmission; et B est un vecteur de type bruit blanc gaussien de dimension (m,1). On cherche notamment à résoudre d'une façon quasi-optimale le problème ILS ("integer Least squares", en anglais) suivant: Min 11Y-Hxl12 X E C (C ensemble discret entier) Les principales étapes du procédé selon l'invention sont illustrées sur la figure 2. A l'étape a), on calcule une première estimation Xr de X à partir du signal vecteur Y et du pseudo-inverse de la matrice H calculé au cours d'une étape préliminaire al. A l'étape b), on effectue une décomposition de type SVD d'où on extrait un vecteur singulier V1 correspondant à la valeur singulière la plus faible de la matrice H. A l'étape c) (non représentée), on détermine la droite M passant par Xr et ayant V1 comme vecteur directeur. A l'étape d), on recherche 2n points d'intersection entre la droiteMl et les 2n hyperplans x(i)=s, avec x(i) représentant la iième coordonnée d'un point x de l'espace e et s un réel. On projette ensuite les 2n points d'intersection sur la constellation C={- 1,+1} à l'étape e) de façon à obtenir 2n points candidats Ipk, k allant de 1 à 2n, puis on supprime les points candidats redondants. En effet, deux points d'intersection différents peuvent donner deux points candidats identiques. A l'étape f), on calcule les distances I IY-H.Ipkl I pour les points candidats restants, et on extrait M points candidats ayant la plus faible valeur en distance IIY-H.Ipkl I. A l'étape f1, on initie ensuite une fonction de - 12- recherche local par les M points candidats. Puis on extrait le point candidat estimé Xe minimisant la distanceI IY-HXI I. On reprend ci-après un exemple de mise en oeuvre du procédé pour D=1 (un seul vecteur V1), M=3 et n=4. 5 Soit: 0.2340 -0. 3510 0.9921 -0.7420'0.1184 0.6232 0.2120 1.0823 H= 0.3148 0.7990 0. 2379 -0.1315 1.4435 0.9409 -1.0078 0.3899 X=[1 -1 1 1]T Io Y=[0.2347 -0. 7542 0.6164 -0.7011]T B=[0.3678 0.6208 0.7313 0.1939]T Etape a) : calcul de Xr: Xr =H-1 x Y = [ 0.2628 0.5685 0.4322 -1.0802]T Etape b) : La décomposition SVD de H est H = U x E x V avec: -0.1805 -0.7347 -0.1770 -0. 6296 0.3711 0.5273 -0.4948 -0.5826 U= 0.2627 0.1151 0.8469 -0.4477 0. 8722 -0.4111 -0.0812 0.2525 2.1942 0 0 0 0 1.6486 0 0 0 0 0.7534 0 0 0 0 0. 4238 0.4238 est la valeur singulière la plus faible. - 13- 0.6507 -0.1958 0.1755 0.7123- 0.6039 0.1769 0.4700 -0.6189 V= -0. 2546 0. 7778 0.4699 0.3307 0.3833 0.5704 -0.7263 -0.0144 concentration de bruit est donnée par la dernière colonne de cette matrice. Extraction d'une direction de concentration de bruit (D=1) : V1 = 0.7123 0.6189 0.3307 -0.0144]T Etape c) : l'équation paramétrique de la droite Al, est Al: 61(k)= k.V1 + Xr kE9i Etapes d) et e) : Création de huit points candidats contenus dans l'ensemble LI1 = p (Al n 3) , c'est à dire la projection g sur la constellation C={-1, 1} des points d'intersection entre la droite Al et huit hyperplans s de l'espace Cependant dans les huit points candidats obtenus, on en supprime quatre qui sont redondants. On conserve donc quatre points candidats dans le sous ensemble LI1. Les coordonnes de ces points correspondent aux vecteurs colonnes de LI1. Etape f) : Calcul de la distance euclidienne Dist pour chaque point candidat de LI1.: 1 -1 -1 -1 -1 1 1 1 LI1 = 1 1 -1 -1 -1 -1 -1 1 Dist = 1. 0931 2.0074 2.6359 7.3445] Le premier, respectivement deuxième, troisième et quatrième, élément de Dist correspond à la première, respectivement deuxième, troisième et quatrième, colonne de LI1. la première direction de - 14 Création d'un ensemble nommé LC1, pour M=3, comprenant les trois premiers points candidats ou sommets ayant une distance euclidienne la plus faible: 1 -1 -1 -1 1 1 LC1 = 1 1 -1 -1 -1 -1 Application de la fonction glouton ou "greedy" sur: Xl=[1 -1 1 -1]T X2=[1 1 1 -1]T X3=[-1 1 1 _ 1T Extraction de la solution optimale: Xe = [1 -1 Le procédé selon la présente invention peut être implémenté dans un circuit intégré programmable tel qu'un circuit FPGA. La figure 3 illustre un tel circuit sous forme de blocs fonctionnels pour D=1, c'est à dire un seul vecteur directeur V1. La matrice H du canal est connue, et son vecteur directeur V1 est prédéterminé. L'unité d'intersection permet d'établir la droit de direction Vi et passant par Xr, de réaliser l'intersection entre cette droite et plusieurs hyperplans, puis de réaliser la projection sur la constellation C. Les données issues de l'unité d'intersection 11 sont une liste des points candidats. L'unité 12 permet de supprimer des points redondants. L'unité 13 calcule les distances euclidienne ou de Manhattan des points candidats restants. L'unité 14 est destinée à classer les distances par ordre ascendant et à extraire les M plus faibles points candidats. On applique ensuite l'algorithme glouton de recherche d'optimum dans les voisins sur chaque candidat via les unités glouton 15, 16. Enfin, l'unité 17 permet de classer les points candidats issus des unités glouton et d'en extraire l'estimation Xe. L'invention est notamment remarquable par le fait que si l'on utilise plusieurs vecteurs directeurs V1, V2,..., VD, les opérations sont effectuées en parallèle, ce qui est un avantage en terme d'implémentation. - 15 Sur la figure 4, on voit les résultats de simulation de l'algorithme nommé HISD pour "Hyperplane Intersection Selection Detection" en langue anglaise, basé sur le procédé selon la présente invention. L'axe des ordonnées correspond au taux d'erreurs bit (BER) et l'axe des abscisses au rapport-signal-à-bruit (SNR). Les courbes représentent respectivement lesperformances selon la présente invention ainsi que les performances selon les algorithmes de type ZF, MMSE, PIC et SDP. Ces résultats sont basés sur un système de transmission numérique de type MIMO avec cinq antennes à l'émission et cinq antennes à la réception, et en utilisant une modulation 4-Q AM non-codé. L'algorithme HISD présente d'excellentes performances notamment pour D=2 et M=4. En fait, pour un taux d'erreur bit de 10-5, l'algorithme HISD présente un rapport signal à bruit inférieur de -1dB par rapport à un détecteur optimum, le détecteur à maximum de vraisemblance (détecteur ML), alors que par exemple l'algorithme de type SDP est à -3dB du détecteur ML. La figure 5 illustre les mêmes performances pour vingt-cinq antennes à l'émission et vingt- cinq antennes à la réception. Bien sûr, l'invention n'est pas limitée aux exemples qui viennent d'être décrits et de nombreux aménagements peuvent être apportés à ces 20 exemples sans sortir du cadre de l'invention. - 16-REVENDICATIONS 1. Procédé pour décoder un signal vecteur Y de dimension (m,1), tel que Y=HX+B, où X est un vecteur de dimension (n,1) dont les éléments appartiennent à un sous ensemble fini appelé constellation C, H est une matrice réelle de dimension (m, n), et B est un vecteur de type bruit blanc gaussien de dimension (m,1), en vue d'obtenir une estimation du vecteur X, caractérisé en ce qu'il comprend les étapes suivantes dans un espace 91: a) calcul d'un point de référence Xr qui est une première estimation de io X, obtenue par une méthode d'optimisation convexe non contrainte; b) détermination d'au moins un vecteur V1 correspondant à un vecteur singulier droit de la matrice H; c) détermination d'une droite Al passant par Xr et ayant V1 comme vecteur directeur; d) détermination du point d'intersection I entre la droite Al et au moins un hyperplan de l'espace 91e) projection du point I sur la constellation C de façon à générer au moins un point candidat Ip de la constellation C; et f) détermination d'un point Xe qui est une estimation finale de X, à 20 partir du point candidat Ip. 2. Procédé selon la revendication 1, caractérisé en ce que ledit au moins un vecteur V1 correspond à un axe dominant du bruit de la matrice H. 3. Procédé selon la revendication 1 ou 2, caractérisé en ce que la méthode d'optimisation convexe consiste en une résolution de la minimisation de la distance I IY - H.XI I selon la méthode dite "zéro forcing" dans 31n ou la méthode dite MMSE. 4. Procédé selon l'une quelconque des revendications 1 à 3, caractérisé en ce que ledit au moins un hyperplan est obtenu par une équation du type x(i) = s, avec x(i) représentant la i1ème coordonnée d'un point x de l'espace 9t" et s un réel. - 17- 5. Procédé selon la revendication 4, caractérisé en ce que la valeur de s est égale à une valeur de la constellation C. 6. Procédé selon la revendication 4, caractérisé en ce que la valeur de s est égale à zéro; la iième coordonnée du point d'intersection I étant alors nulle, la projection de cette iième coordonnée sur la constellation C est alors égale à l'opposée du signe de la iième coordonnée Xr. 7. Procédé selon l'une quelconque des revendications 1 à 3, caractérisé io en ce que ledit au moins un hyperplan est défini de telle sorte que le vecteur normal à l'hyperplan est donné par la projection du vecteur V1 sur la constellation C. 8. Procédé selon l'une quelconque des revendications précédentes, 15 caractérisé en ce qu'à l'étape f), Xe est le point candidat Ip. 9. Procédé selon l'une quelconque des revendications 1 à 6, caractérisé en ce que: on détermine à l'étape b), D vecteurs V1, V2,..., VD 20 correspondant chacun à un vecteur singulier droit de la matrice H; on détermine à l'étape c), D droites M, L2,..., AD passant par Xr et ayant respectivement V1, V2,...,VD comme vecteur direction; - on détermine à l'étape d), au plus anD points d'intersection Ik entre les droites M, L2,. .., AD et au plus an hyperplans, chaque hyperplan comprenant une des faces de l'hypercube ayant comme sommets la constellation C dans l'espace 9i" , avec k allant de 1 à anD et a étant le nombre des points d'intersections par dimension; - on en déduit à l'étape e), au plus anD points candidats Ipk, avec k = 1...anD; - on calcule à l'étape f), au plus les anD distances 11Y - H.IpkI 1; et on considère le point candidat de distance minimale comme étant le point décodé Xe. 10. Procédé selon l'une quelconque des revendications 1 à 6, 35 caractérisé en ce que: - 18 - on détermine à l'étape b), D vecteurs V1, V2,...,VD correspondant chacun à un vecteur singulier droit de la matrice H; - on détermine à l'étape c), D droites M, D2,..., AD passant par Xr et ayant respectivement V1, V2,...,VD comme vecteur direction; - on détermine à l'étape d), au plus anD points d'intersection Ik entre les droites Al, 2,..., AD et au plus an hyperplans, chaque hyperplan comprenant une des faces de l'hypercube ayant comme sommets la constellation C dans l'espace 9%" , avec k allant de 1 à anD et a étant le nombre des points d'intersections par dimension.; io - on en déduit à l'étape e), au plus anD points candidats Ipk, avec k = 1...anD; - on calcule à l'étape f), ), au plus les anD distances 11Y - H.Ipkl I; et on détermine D sous ensembles chacun contenant M points candidats dont les distances 11Y - H.IpkII sont les plus faibles, puis on utilise ces D sous ensembles pour initier un algorithme de recherche d'optimum local, le point candidat obtenu à l'issue de cette recherche ayant la plus faible valeur de la fonction coût est considéré comme étant le point décodé Xe. 11. Procédé selon la revendication 10, caractérisé en ce qu'on utilise 20 l'algorithme glouton pour la recherche de l'optimum local. 12. Procédé selon l'une quelconque des revendications 9 à 11, caractérisé en ce qu'à l'étape e), on supprime des points candidats Ipk redondants. 13. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que la constellation est égale à C = {-1,1}. 14. Procédé selon l'une quelconque des revendications 1 à 12, 30 caractérisé en ce que la constellation est égale à c = {-3,-1,1,3}. 15. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'on détermine en outre une estimation de la fiabilité de Xe. - 19- 16. Procédé selon la revendication 15, caractérisé en ce que lors des calculs de distance IIY - H.Ipll, on mémorise dans une table les distances minimales trouvées pour chaque valeur c de la constellation C et pour chaque coordonnée de Ip; puis on estime la fiabilité de Xe à partir de ladite table. 17. Procédé selon la revendication 15 ou 16, caractérisé en ce qu'on transmet le point décodé Xe et l'estimation de la fiabilité associée vers un code correcteur d'erreur à décision souple en entrée. io 18. Procédé selon l'une quelconque des revendications 1 à 17, caractérisé en ce qu'à l'étape b), on réalise une décomposition de type SVD de façon à en déduire ledit au moins un vecteur singulier droit de la matrice H correspond à la valeur singulière la plus faible de la matrice H. 19. Procédé selon l'une quelconque des revendications 1 à 17, caractérisé en ce qu'à l'étape b), on utilise la méthode de Lanczos pour déterminer ledit au moins un vecteur singulier droit de la matrice H correspond à la valeur singulière la plus faible de la matrice H. 20. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'à l'étape e), on réalise la projection par minimisation de la distance quadratique IIY - H.Xl 21. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que des distances du type 11Y - H.XI l sont calculées selon la norme euclidienne ou norme 2 telle que IIY - H.XI12= sum((Y-H.X)t(YH.X)). 22. Procédé selon l'une quelconque des revendications précédentes, 30 caractérisé en ce que des distances du type IIY - H.XI I sont calculées selon la norme 1 telle que IIY - H.XI 11= sum(abs(Y-H.X)). 23. Module de décodage mettant en oeuvre un procédé selon l'une quelconque des revendications précédentes, pour décoder un signal vecteur Y 35 de dimension (m,1), tel que Y=HX+B, où X est un vecteur de dimension (n,1) dont les éléments appartiennent à un sous ensemble fini appelé constellation C, H est une matrice réelle de dimension (m, n), et B est un vecteur de type bruit blanc gaussien de dimension (m,l), en vue d'obtenir une estimation du vecteur X, caractérisé en ce qu'il comprend: - des moyens pour calculer dans l'espace 9t" un point de référence Xr, qui est une première estimation de X, par une méthode d'optimisation convexe non contrainte; - des moyens pour déterminer au moins un vecteur V1 correspondant à un vecteur singulier droit de la matrice H; - des moyens pour déterminer une droitél passant par Xr et ayant V1 comme vecteur directeur; - des moyens pour déterminer un point d'intersection I entre la droite M et au moins un hyperplan de l'espace 9i- des moyens pour projeter le point I sur la constellation C de façon à générer au moins un point candidat Ip de la constellation C; et - des moyens pour déterminer un point Xe qui est une estimation finale de X, à partir du point candidat Ip. 24. Module selon la revendication 23, caractérisé en ce qu'il comprend une architecture parallèle apte à déterminer Xe par traitements parallèles à partir d'une pluralité de vecteurs Vi passant par Xr et correspondant à des vecteurs singuliers droits de la matrice H. 25. Application du procédé selon l'une quelconque des revendications 1 25 à 22, pour le décodage d'un signal numérique dans un système de communication sans fil. 26. Application selon l'une quelconque des revendications 1 à 22, pour le décodage d'un signal numérique Y, le signal d'émission X ayant subit une modulation du type compris dans la liste suivante: MIMO; CDMA; MC-CDMA, BLAST. 27. Application du procédé selon l'une quelconque des revendications 1 à 22, pour le décodage d'une image dans un système de traitement d'image.