Brevet FR2886078A1 — publié le 20061124

L'invention concerne un procédé de localisation d'agrégats erroné pour décodage, qui utilise un polynôme localisateur d'agrégats, et un dispositif associé, ainsi qu'un procédé de décodage avec calcul des valeurs des erreurs à partir d'un polynôme localisateur d'agrégats de degré minimal. Afin de se prémunir contre les erreurs pouvant survenir lors du stockage (ou de la transmission) de données, il est classique de stocker (ou de transmettre) ces données sous forme codée afin d'y introduire une certaine redondance qui rend possible, sauf dans des cas très défavorables, la détection des erreurs de stockage (ou de transmission) et leur correction. Un tel codage consiste à associer à une suite de k symboles d'information dans le message original (mot d'information) un mot de code formé de n symboles (avec k Lors du décodage, on cherchera ainsi à retrouver la suite de k symboles d'information du message initial à partir du mot reçu, éventuellement affecté par des erreurs. En pratique, on procède en général en premier lieu à la recherche du mot de code le plus proche du mot reçu (par exemple par une localisation des erreurs affectant le mot reçu et une correction des erreurs localisées), puis en second lieu au calcul du mot d'information associé au mot de code ainsi déterminé (selon un procédé inverse de celui utilisé pour le codage). Lorsque les symboles d'information (qui constituent l'élément de base du message initial) sont choisis dans un ensemble (ou alphabet) dont le cardinal est égal à la puissance d'un nombre premier (comme c'est fréquemment le cas dans les traitements informatiques où ce cardinal vaut une puissance de 2), on peut représenter les symboles comme des éléments d'un corps de Galois, ce qui permet de réaliser le codage notamment au moyen d'opérations dans ce corps. Ainsi, on a pu définir les codes de Reed-Solomon qui sont largement utilisés, par exemple pour le stockage des données sur les disques compacts. Ce type de code est toutefois limité en ce sens que, du fait de leur définition, la longueur des mots de code est au maximum égale au cardinal de l'alphabet avec lequel on travaille. Cette limitation peut s'avérer gênante, par exemple dans le cadre du stockage d'information où la densité de données stockées augmente continuellement : ceci implique en effet qu'une éraflure touche un nombre de symboles de plus en plus important et on cherche à augmenter la longueur des mots de code afin qu'une proportion suffisante de ceux-ci soit laissée intacte en cas d'éraflure.L'augmentation du nombre de symboles dans l'alphabet, qui nécessiterait de modifier la mise en u̇vre matérielle des systèmes de traitement d'informations, a déjà été envisagée mais elle est par nature provisoire puisqu'elle nécessite de changer d'alphabet dès que l'on souhaite augmenter la longueur des mots utilisés. C'est pourquoi on a proposé plus récemment d'utiliser des codes dits "de géométrie algébrique" (ou "de Goppa géométrique") construits à partir d'un ensemble dit "de localisation" formé de n couples (x,y) de symboles appartenant au corps de Galois, ce qui permet d'obtenir une longueur n bien supérieure à celle envisageable dans le cas des codes de Reed-Solomon pour un même corps de Galois. Le décodage de tels codes de géométrie algébrique est toutefois sensiblement plus complexe que celui des codes de Reed-Solomon du fait de l'utilisation de couples d'éléments du corps de Galois, c'est-à-dire en pratique de deux variables. Ainsi, si des algorithmes de localisation d'erreurs particulièrement efficaces ont été développés dans le cadre des codes de géométrie algébrique dans la lignée de ceux utilisés pour les codes de Reed-Solomon (voir par exemple l'article "Generalized Berlekamp-Massey Decoding of Algebraic-Geometric Codes Up To Half the Feng-Rao Bound", de S. Sakata, H.E. Jensen et T. Hoeholdt, in IEEE Transactions on Information Theory, vol. 41, No. 6, novembre 1995 sur la détermination de syndromes étendus et l'article "A generalized Forney Formula for Algebraic-Geometric Codes", de D. A.Leonard, in IEEE Transactions on Information Theory, Vol. 42, No. 4, juillet 1996 sur les bases de Grôbner), ces techniques ont recours à des polynômes à plusieurs variables, ce qui rend délicate leur mise en u̇vre pratique, par exemple lorsqu'il s'agit de rechercher les valeurs pour lesquelles ils s'annulent. Il a de ce fait été proposé dans la demande de brevet EP 1 434 132 une solution qui permet de ramener le décodage d'un code de géométrie algébrique au décodage d'une pluralité de codes de Reed-Solomon en regroupant par agrégats les couples, ou points, (x,y) de l'ensemble de localisation ayant une même valeur de x. Cette solution permet une mise en u̇vre plus aisée du décodage des codes de géométrie algébrique, mais rend nécessaire des calculs complémentaires pour générer à partir du mot reçu plusieurs mots de codes de Reed-Solomon en vue de leur traitement par des algorithmes applicables à ce type de code ainsi que l'application de ces algorithmes à plusieurs reprises. Il paraît donc souhaitable de proposer une solution pour le décodage d'un mot reçu dans le cadre des codes de géométrie algébrique qui allie l'efficacité des algorithmes de localisation d'erreurs tels que ceux mentionnés ci-dessus et une possibilité de mise en u̇vre pratique du calcul des valeurs d'erreur par l'utilisation du traitement par agrégats tel qu'il est proposé dans ses principes dans la demande EP 1 434 132. Pour répondre à cette attente, l'invention propose d'utiliser un polynôme à une variable dont les zéros (c'est-à-dire les valeurs de x pour lesquelles le polynôme s'annule) indiquent les agrégats qui contiennent au moins un couple (x, y) associé à une composante erronée du mot reçu. Un tel polynôme peut ainsi être dénommé "polynôme localisateur d'agrégats erronés". En particulier, l'invention propose un procédé de localisation d'agrégats erronés de composantes d'un mot reçu, appliqué au décodage pour code de géométrie algébrique défini sur une courbe algébrique d'équation polynomiale à deux variables de puissance a en la seconde variable, les composantes du mot reçu étant étiquetées par des points (x,y) de la courbe regroupés en agrégats de points ayant une première coordonnée commune, caractérisé en ce qu'il comprend les étapes suivantes : - détermination d'une base de Grôbner associée au mot reçu et comportant a' polynômes ; - détermination de a-a' polynômes Ys.Fi (X,Y) chacun produit d'un polynôme de la base de Grôbner Fi(X,Y) et d'une puissance Y de la seconde variable, afin d'obtenir, par adjonction à la base de Grôbner, un ensemble étendu de a polynômes ;- détermination, sur la base des a polynômes de l'ensemble étendu, de polynômes i̇,j(X) en la première variable facteurs de monômes en la seconde variable qui forment une matrice de polynômes dont le déterminant z*(X) est un polynôme qui s'annule sur la première coordonnée x des points erronés (x,y) du mot reçu ; - détermination d'au moins une valeur de la première variable qui annule ledit déterminant. Le déterminant utilisé, qui est un polynôme de la première variable construit à partir des polynômes de la base de Grôbner, permet d'obtenir directement les valeurs de la première variable étiquetant les agrégats erronés et constitue donc un polynôme localisateur d'agrégats erronés. En outre, l'utilisation dans la construction de la matrice de polynômes de l'ensemble étendu (produits de polynômes de la base de Grôbner et d'une puissance de la seconde variable, et donc également éléments de l'idéal de Grôbner) permet de pouvoir aboutir à une matrice carrée, pour laquelle le déterminant est défini. On rappelle qu'étant donné un mot reçu, l'ensemble des polynômes F(X,Y) qui s'annulent pour toutes les paires de valeurs (x,y) qui étiquètent une position erronée de ce mot reçu sera appelé l'idéal de Grôbner du mot reçu, et qu'un tel idéal admet un ensemble générateur d'un type particulier appelé base de Grôbner, définie par exemple au point 3.1 dans le chapitre I du livre "Using Algebraic Geometry" par D. Cox, J. Little et D. O'Shea. On note également que la notion de base de Grôbner réduite, également définie dans ce document, ne sera pas considérée ici et que toute base de Grôbner telle que définie ci-dessus peut donc être utilisée dans la présente invention. L'étape de détermination de a-a' polynômes est naturellement mise en u̇vre en cas de vérification positive de la condition a' Lorsque l'équation polynomiale définissant la courbe est de degré b en la première variable et de degré a en la seconde variable et que le poids d'un polynôme est défini comme la valeur maximale prise par la formule ai+bj sur variable utilisées pour la détermination de chacun des a-a' polynômes sont telles deux. Un tel résultat est obtenu selon le mode de réalisation de l'invention décrit ci-après par les étapes suivantes : - ordonnancement des polynômes Fi(X,Y) de la base de Grôbner par ordre croissant de la puissance j(i) en la seconde variable du monôme qui détermine le poids du polynôme Fi(X,Y) concerné ; - pour chacune des valeurs entières k de 0 à a-1 pour laquelle j(i)=k n'est pas réalisé, détermination d'un polynôme construit comme suit : * s'il existe un plus grande') tel que j(i') * s'il n'existe pas de tel plus grand j(i') , construction du seconde variable, construites ci-dessus, - adjonction des polynômes ainsi construits à l'ensemble des polynômes de la base de Grôbner. Selon un mode de réalisation, le procédé peut comprendre une étape de réduction des polynômes de l'ensemble étendu modulo le polynôme Fo(X,Y) définissant l'équation polynomiale. On réduit ainsi le degré des polynômes de l'ensemble étendu, si bien qu'ils sont chacun au plus de degré (a-1) en la seconde variable. On peut donc prendre pour éléments de la matrice de polynômes les polynômes i̇,j (X) facteurs de monômes de la seconde variable dans les carrée de dimension a x a dont les éléments sont des polynômes.. En variante, la matrice de polynômes peut avoir notamment pour éléments les polynômes facteurs de monômes de la seconde variable dans les polynômes de l'ensemble étendu (sans étape de réduction). On peut dans ce cas utiliser également pour éléments de la matrice de polynômes notamment les polynômes facteurs de monômes de la seconde variable Fo(X,Y) définissant l'équation polynomiale, pris en nombre suffisant pour construire la matrice carrée désirée. L'utilisation de tels polynômes permet ainsi d'aboutir également dans cette variante à une matrice carrée. Le procédé peut également comprendre une étape d'élimination des facteurs multiples dans ledit déterminant, ce qui permet d'obtenir un polynôme localisateur d'agrégats erronés de degré minimal. Cette étape est par exemple mis en u̇vre par au moyen d'étapes de calcul du plus grand diviseur commun d'un polynôme et de sa dérivée. Autrement dit, l'invention propose un procédé de localisation d'agrégats erronés de composantes d'un mot reçu, appliqué au décodage pour code de géométrie algébrique défini sur une courbe algébrique d'équation polynomiale à deux variables, les composantes du mot reçu étant étiquetées par des points de la courbe regroupés en agrégats de points ayant une première coordonnée commune, avec les étapes suivantes : - détermination à partir du mot reçu d'au moins un premier polynôme à deux variables qui s'annule pour un point étiquetant une composante erronée du mot reçu ; - détermination d'au moins un second polynôme produit du premier polynôme et d'un polynôme de la seconde variable ;- détermination, en partie au moins sur la base des premier et second polynômes, de polynômes de la première variable facteurs de monômes de la seconde variable qui forment une matrice de polynômes dont le déterminant est un polynôme qui s'annule sur la première coordonnée dudit point ; - détermination d'au moins une valeur qui annule ledit déterminant. Lorsque l'équation polynomiale définissant la courbe est de degré b en la première variable et de degré a en la seconde variable et que le poids d'un polynôme est la valeur maximale prise par la formule ai+bj sur l'ensemble des monômes XY de ce polynôme, le polynôme de la seconde variable est choisi tel que le poids du second polynôme est différent de chacun des poids desdits premiers polynômes. L'ensemble des premiers et seconds polynômes forme ainsi un ensemble de polynômes dont les poids sont tous différents. Lorsque l'étape de détermination d'au moins un premier polynôme génère a' premiers polynômes, l'étape de détermination d'au moins un second polynôme peut générer par exemple (a-a) seconds polynômes produits d'un premier polynôme et d'un polynôme de la seconde variable. L'ensemble des premiers et seconds polynômes contient ainsi précisément a éléments. L'invention propose également un procédé de décodage d'un mot reçu pour code de géométrie algébrique défini sur une courbe algébrique d'équation polynomiale à deux variables, les composantes du mot reçu étant étiquetées par des points de la courbe regroupés en agrégats de points ayant une première coordonnée commune, avec les étapes suivantes : - localisation des agrégats erronés au moyen d'un procédé comme évoqué ci-dessus ; - correction d'erreur dans les agrégats localisés. L'invention propose ainsi un dispositif de localisation d'agrégats erronés de composantes d'un mot reçu, adaptée au décodage pour code de géométrie algébrique défini sur une courbe algébrique d'équation polynomiale à deux variables de puissance a en la seconde variable, les composantes du mot reçu étant étiquetées par des points (x, y ) de la courbe regroupés en agrégats de points ayant une première coordonnée commune, caractérisé en ce qu'il comprend : - des moyens de détermination d'une base de Grôbner associée au mot produit d'un polynôme de la base de Grôbner Fi (X, Y) et d'une puissance Y de la seconde variable, afin d'obtenir, par adjonction à la base de Grôbner, un ensemble étendu de a polynômes ;- des moyens de détermination, sur la base des a polynômes de l'ensemble étendu, de polynômes i̇,y(X) en la première variable facteurs de monômes en la seconde variable qui forment une matrice de polynômes dont le déterminant z*(X) est un polynôme qui s'annule sur la première coordonnée (x) des points erronés (x, y ) du mot reçu ; - des moyens de détermination d'au moins une valeur de la première variable qui annule ledit déterminant. L'invention propose aussi un dispositif de localisation d'agrégats erronés de composantes d'un mot reçu, adaptée au décodage pour code de géométrie algébrique défini sur une courbe algébrique d'équation polynomiale à deux variables, les composantes du mot reçu étant étiquetées par des points (x,y) de la courbe regroupés en agrégats de points ayant une première coordonnée commune, caractérisé en ce qu'il comprend : - des moyens de détermination à partir du mot reçu d'au moins un premier polynôme à deux variables Fi (X, Y) qui s'annule pour un point (x,y) étiquetant une composante erronée du mot reçu ; - des moyens de détermination d'au moins un second polynôme variable ;- des moyens de détermination, en partie au moins sur la base des premier et second polynômes, de polynômes i̇,j(X) de la première variable facteurs de monômes de la seconde variable qui forment une matrice de polynômes dont le déterminant z*(X) est un polynôme qui s'annule sur la première - des moyens de détermination d'au moins une valeur qui annule ledit déterminant. Les avantages de ces dispositifs de localisation d'erreurs sont essentiellement les mêmes que ceux des procédés corrélatifs décrits succinctement ci-dessus. L'invention vise également : - un décodeur comprenant au moins un dispositif de localisation d'erreurs tel que décrit succinctement ci-dessus, et au moins une unité de suppression de la redondance, - un appareil de réception de signaux numériques codés comprenant un décodeur tel que décrit succinctement ci-dessus, et comprenant des moyens pour démoduler lesdits signaux numériques codés, - un système informatique comprenant un décodeur tel que décrit succinctement ci-dessus, et comprenant en outre au moins un disque dur ainsi qu'au moins un moyen de lecture de ce disque dur, - un moyen de stockage de données inamovible comportant des instructions de code de programme informatique pour l'exécution des étapes de l'un quelconque des procédés de décodage succinctement exposés ci-dessus, - un moyen de stockage de données partiellement ou totalement amovible,comportant des instructions de code de programme informatique pour l'exécution des étapes de l'un quelconque des procédés de localisation d'agrégats succinctement exposés ci-dessus, et - un programme d'ordinateur, contenant des instructions telles que, lorsque ledit programme commande un dispositif de traitement de données programmable, lesdites instructions font que ledit dispositif de traitement de données met en oeuvre l'un des procédés de localisation d'agrégats succinctement exposés ci-dessus. Les avantages offerts par ce décodeur, cet appareil de réception, ce système informatique, ces moyens de stockage de données et ce programme d'ordinateur sont essentiellement les mêmes que ceux offerts par les procédés de localisation d'erreurs selon l'invention. D'autres aspects et avantages de l'invention apparaîtront à la lecture de la description détaillée ci-dessous de modes de réalisation particuliers, donnés à titre d'exemples non limitatifs. La description se réfère aux dessins qui l'accompagnent, dans lesquels : - la figure 1 est un schéma synoptique d'un système de transmission d'informations mettant en u̇vre un procédé selon l'invention ; - la figure 2 illustre les étapes essentielles d'un procédé de décodage selon l'invention ; et - la figure 3 représente un appareil de réception de signaux numériques incorporant un décodeur selon l'invention. La figure 1 est un schéma synoptique d'un système de transmission d'informations mettant en u̇vre un procédé selon l'invention. Ce système a pour fonction de transmettre des informations de nature quelconque à partir d'une source 100 vers un destinataire ou utilisateur 109. En premier lieu, la source 100 traduit ces informations en une suite de symboles appartenant à un certain corps de Galois Fq (par exemple des octets de bits pour q = 28 ), et transmet ces symboles à une unité de stockage 101, qui accumule les symboles de façon à former des ensembles contenant chacun k symboles. Ensuite, chacun de ces ensembles est transmis par l'unité de stockage 101 à un codeur 102 qui y incorpore de la redondance, de manière à construire un mot de longueur n appartenant au code choisi. Les mots de code ainsi formés sont ensuite transmis à un modulateur 103, qui associe à chaque symbole du mot de code un symbole de modulation. Ensuite, ces symboles de modulation sont transmis à un enregistreur (ou un émetteur) 104, qui insère les symboles dans un canal de transmission. Ce canal peut être par exemple un stockage sur un support adapté tel qu'un DVD ou un disque magnétique ou encore une bande magnétique. Il peut correspondre également à une émission filaire ou non-filaire comme c'est le cas d'un lien radio. Le message transmis parvient à un lecteur (ou un récepteur) 105, après avoir été affecté par un "bruit de transmission" dont l'effet est de modifier ou d'effacer certains des symboles de modulation. Le lecteur (ou récepteur) 105 transmet alors ces symboles au démodulateur 106, qui les transforme en symboles de Fq. Les n symboles résultant de la transmission d'un même mot de code sont ensuite groupés en un "mot reçu" dans une unité de correction d'erreurs 107, qui met en u̇vre un procédé de décodage selon l'invention, de manière à fournir un "mot de code associé". Puis ce mot de code associé est transmis à une unité de suppression de redondance 108, qui en extrait k symboles d'information en mettant en oeuvre un algorithme de décodage inverse de celui mis en oeuvre par le codeur 102. Enfin, ces symboles d'information sont fournis à leur destinataire 109. On peut considérer que les unités 107 et 108 forment conjointement un "décodeur" 10. On considère ici les codes de géométrie algébrique définis sur une courbe algébrique représentée par une équation F0(X,Y) = 0, avec : où c 0 et les ci} sont des éléments de Fq, a et b sont des entiers strictement positifs et premiers entre eux, et où la somme ne porte que sur les entiers i et j qui satisfont ai +bj Pour un tel code, on définit classiquement une matrice de parité H de la manière suivante. A tout monôme Y j Xi , où i et j sont des entiers positifs ou nuls, on associe un "poids" égal par définition à (ai + bj ). Si, pour un entier 0 , il existe au moins un monôme dont le poids est , on dit que p est un poids "réalisable ". Soient 1 la matrice de parité est égal au monôme ha évalué au point Pbeta (où, rappelons-le, composante de tout mot de code. Un code ayant une telle matrice de parité est appelé "code à un point' car sa matrice de parité est obtenue en évaluant (en les n points Pbeta ) des fonctions (les monômes ha ) qui n'ont de pôles qu'en un seul point, à savoir le point à l'infini. Comme tous les codes, les codes de géométrie algébrique peuvent être "modifiés" et/ou "raccourcis". On dit qu'un code donné Cmod est une version "modifiée" du code C s'il existe une matrice diagonale carrée non-singulière A telle que chaque mot de Cmod est égal à Ȧ avec v dans C. On dit qu'un code donné est une version "raccourcie" du code C s'il ne comprend que les mots de C dont, pour un nombre R de positions prédéterminées, les composantes sont toutes nulles : ces positions étant connues du récepteur, on peut se dispenser de les transmettre, de sorte que le code raccourci est de longueur (n-R). En particulier, il peut être utile en vue de la facilité de décodage de raccourcir un code de géométrie algébrique en supprimant de l'ensemble de localisation, le cas échéant, un point, ou plusieurs points, dont la coordonnée x est nulle. Un procédé de décodage (et précisément sa partie relative à la correction d'erreur, la partie suppression de la redondance étant classique) va à présent être décrite en référence à la figure 2. L'algorithme commence naturellement avec la réception d'un r formé de n symboles (étape E200). (On considère le mot r après l'étape de démodulation.) On détermine ensuite à l'étape E202 des polynômes de localisation d'erreurs associés au mot reçu r dont les zéros sont des couples (x, y) étiquetant les composantes erronées de ce mot reçu. L'ensemble des polynômes de localisation d'erreurs possède la structure d'un idéal appelé "idéal de Gröbner (associé aux erreurs de transmission affectant ce mot). On peut obtenir récurrent qui à chaque étape de récurrence utilise une nouvelle composante du vecteur des syndromes s .L'obtention de cette base de Grôbner est possible au moins chaque fois que le nombre d'erreurs dans le mot reçu est inférieur ou égal Toutefois, même lorsque le nombre d'erreurs dans le mot reçu est inférieur ou égal à (n - k - g )/2, il faut en général, pour pouvoir construire la base de l'idéal de Grôbner, connaître plus de composantes du syndrome que ceux que nous qualifierons de "connus" du fait qu'ils sont égaux à une des composantes composantes. Il est heureusement possible de calculer ces éléments de valeur "inconnue" par un procédé comprenant un certain nombre de "décisions majoritaires", par exemple l'algorithme dit "de Feng-Rao" (voir l'article de G.-L. Feng et T.R.N. Rao intitulé "Decoding Algebraic-Geometric Codes up to the Designed Minimum Distance", IEEE Trans. Inform. Theory, vol. 39, n[deg] 1, janvier 1993).Cet algorithme permet d'étendre le vecteur des syndromes s = H.rT au moyen au moyen d'étapes de calcul que l'on peut décrire comme étant g' itérations supplémentaires après les (n - k) premières itérations utilisant les (n -k) composantes du vecteur s = H.rT . Ce nombre g' d'itérations supplémentaires est au plus égal à 2g . Ainsi, on parvient au stade où, comme expliqué ci-dessus, il devient possible de calculer une base de Grôbner à partir du syndromes*, prolongement du vecteurs, ainsi obtenu. A ce stade, il est également possible de calculer des éléments "inconnus" supplémentaires du syndrome s * à partir des éléments obtenus précédemment, soit au moyen de nouvelles itérations d'un algorithme à "décisions majoritaires", soit plus commodément au moyen d'un certain nombre de relations, dites "de récurrence", utilisant des "polynômes de rétroaction" choisis dans la base de Grôbner. On pourra se référer à ce propos à l'article de M. Sakata et al. intitulé "Generalized Berlekamp-Massey Decoding of Algebraic-Geometric Codes up to Half the Feng-Rao Bound " (IEEE Trans. Inform. Theory, vol. 41, pages 1762 à 1768, novembre 1995). On peut considérer les éléments du syndrome s * comme étant des "syndromes d'erreur étendus" ou "syndromes étendus". Ces syndromes étendus permettent de calculer une base de Grôbner a ) qui peuvent s'écrire comme suit : On peut ordonner ces polynômes par poids croissant comme décrit à présent : si on définit le poids d'un polynôme comme le poids du monôme de poids maximal dans ce polynôme (selon la définition du poids d'un monôme Les propriétés des bases de Grôbner impliquent que les a' entiers j(i) sont distincts et peuvent ainsi être ordonnés et définir un a'-uple J : Cette organisation des polynômes de la base de Grôbner permet d'étendre cette base par des polynômes de la forme YsFi(X,Y) (étape E204), lorsque la base ne contient pas déjà a polynômes (c'est-à-dire lorsque a' L'étape E204 vise ainsi à étendre si nécessaire la base de Gröbner G de façon à obtenir un ensemble G de a polynômes (c'est-à-dire tel que, après extension de l'ensemble G, card G=a). Pour ce faire, on identifie les valeurs de j comprises entre 0 et (a-1) qui n'apparaissent pas dans le a' - uple J défini ci-dessus. Pour chacune de ces réalise cette valeur manquante. En pratique, le calcul de ces (a-a ) polynômes à adjoindre à la base de Grôbner prend donc la forme qui suit : s'annulent chacun aux points de l'ensemble de localisation où le polynôme Fi s'annule ; par ailleurs, de par la construction décrite ci-dessus, les polynômes de l'ensemble étendu à a polynômes ont tous des poids différents. Ainsi, cet ensemble forme une base de l'idéal des polynômes localisateur d'erreurs comprenant a éléments. De plus, la valeur j(i) définie plus haut, et comprise entre 0 et (a-1), est différente pour chacun d'entre eux. On choisira donc d'indicer chacun des a polynômes de l'ensemble étendu par sa valeur de j(i) . Lors de l'étape E206, on procède ensuite à la réduction de chacun des polynômes de l'ensemble étendu G modulo le polynôme Fo (qui définit la courbe algébrique qui forme l'ensemble de localisation du code utilisé, comme indiqué cidessus) considéré comme étant un polynôme en Y . On obtient ainsi l'expression réduite de l'ensemble étendu G sous forme de a polynômes i̇, que l'on peut écrire en regroupant les monômes ayant une puissance de Y commune : Ainsi réduite modulo Fo , l'ensemble étendu à a polynômes permet de définir une matrice de polynômes dont l'élément en ligne i et colonne (j + 1) est le polynôme Oij(X), dont on calcule le déterminant z*(X) à l'étape E208 : (On pourrait également procéder ainsi sans passer par l'étape de réduction par Fo(X,Y), les polynômes i̇ étant alors les a polynômes obtenues après l'étape E204. Dans ce cas, il faut compléter la matrice dont on va calculer le déterminant - qui présente dans cette hypothèse plus de a colonnes - par le nombre convenable de lignes obtenues à partir de polynômes du type sera décrit dans la variante de réalisation proposée plus loin.) Sous l'hypothèse que le nombre d'erreurs contenues dans le mot reçu où n( ) est le nombre d'erreurs contenues dans l'agrégat d'indice . Ainsi, chercher les zéros du polynôme z*(X) permet de déterminer la première coordonnée des couples (x,y) annulant les polynômes de la base de Grôbner, c'est-à-dire la première coordonnée x des couples (x,y) étiquetant les erreurs du mot reçu r, ce qui revient (selon la terminologie de la demande EP 1 434 132) à identifier les agrégats erronés (c'est-à-dire contenant au moins une erreur). Ce polynôme z*(X) n'est pas optimal au sens où il a des racines multiples chaque fois qu'un au moins un des nombres n( ) est égal ou supérieur à 2. Dès lors, lorsque la détermination d'un polynôme à racines simples est nécessaire (comme c'est par exemple le cas pour certains algorithmes de calcul des valeurs d'erreur), il faut procéder au préalable à une étape E210 à laquelle on élimine les facteurs multiples dans le polynôme z*(X) afin d'obtenir un polynôme z(X) dont les zéros sont identiques à ceux de z*(X), mais sans facteur multiple. Lorsque le nombre d'éléments q du corps de Galois Fq est une puissance de deux (comme c'est couramment le cas en pratique), on peut procéder comme suit afin d'éliminer les facteurs multiples dans z*(X): on remarque que, dans ce cas, le plus grand commun diviseur (g.c.d.) de z*(X) et de sa dérivée est un carré. Son expression ne contient que des puissances paires de X et on peut donc procéder ainsi : On a ainsi déterminé un polynôme z(X) localisateur d'agrégats de degré minimum : un tel polynôme permet de localiser précisément tous les agrégats erronés ;de plus, il n'a pas de racines multiples, ce qui rend possible le calcul des valeurs d'erreur comme décrit dans l'exemple numérique donné plus bas. On peut ainsi procéder à l'étape E212 à l'identification des agrégats erronés, c'est-à-dire à la recherche des xe (indexant ces agrégats erronés) tels que z(xe) = 0. Cette recherche est par exemple effectuée en calculant la valeur du polynôme z pour chacune des valeurs x indexant les agrégats. On peut alors procéder à l'étape E214 à laquelle on effectue des corrections d'erreurs dans les agrégats erronés, c'est-à-dire pour toutes les composantes du mot reçu r de la forme r(xe, y(xe)). Cette correction d'erreurs est par exemple mise en u̇vre comme proposé dans le document EP 1 434 132, en limitant toutefois les calculs aux valeurs de x déterminées à l'étape E212, ce qui allège considérablement les calculs. On présente ci-dessous l'application du procédé qui vient d'être décrit à un cas particulier qui permettra d'illustrer sa mise en u̇vre pratique. On considère pour cet exemple un système utilisant un code de géométrie algébrique C défini sur une courbe r de F16 x F16 d'équation La courbe r définie ci-dessus contient 64 points, parmi lesquels 60 points n'ont aucune coordonnée nulle. On peut ainsi définir le code C avec une longueur 60 et une dimension 20 au moyen de sa matrice de parité construite en prenant en chacun des 60 points précités la valeur des 40 monômes suivants : On considère dans l'exemple traité ici que toutes les composantes du mot reçu sont nulles, à l'exception des composantes étiquetées par les points (x,y) dont les coordonnées sont données dans le tableau ci-dessous, pour lesquelles la composante vaut la valeur r(x,y) indiquée dans le tableau qui suit : La base de Grôbner associée à ce mot reçu, obtenue par exemple au moyen de l'algorithme décrit dans l'article de M. Sakata et al. déjà mentionné, contient deux polynômes F1(X,Y) et F2(X,Y) qui peuvent être décrits comme suit à 3 j=0 Le monôme du polynôme F1(X,Y) qui réalise le poids le plus fort est donc proposée plus haut. Le monôme du polynôme F2(X, Y) qui réalise le poids le plus fort employée il =2 et i2=1. L'application de l'étape E204 d'obtention d'un ensemble étendu de polynômes à partir de la base de Grôbner donne dans le cas présent l'ensemble étendu suivant : En réduisant les polynômes modulo Fo(X,Y) (étape E206) par rapport à la plus grande puissance en Y (quand nécessaire pour obtenir des polynômes de degré au plus a en Y, c'est-à-dire ici pour les deux derniers polynômes de g dans le cas présent), on obtient quatre polynômes référencés ci-dessus i̇ (X,7), sur la a-1 j=o une matrice carrée de polynômes en X, dont on calcule le déterminant (étape E208) qui vaut ici : On élimine alors les facteurs multiples au moyen de l'algorithme décrit cidessus à propos de l'étape E210, dans lequel on obtient donc ici à la première itération : puis ainsi dès la seconde itération D(X)=1 . Le polynôme z*(X)lD*(X) défini avec les valeurs ci-dessus lors de la première itération ne possède donc que des racines simples et pourra ainsi être utilisé en tant que polynôme localisateur d'agrégats erronés de degré minimal. Ce polynôme permet alors de localiser les 11 agrégats erronés On peut alors retrouver par décodage dans ces agrégats erronés (par exemple en tenant compte du fait que la valeur d'erreur est nulle pour les composantes correspondant à tous les autres agrégats et en utilisant une méthode du type décrit dans le document EP 1 434 132) que le mot reçu corrigé (après décodage, c'est-à-dire tel qu'il avait été envoyé) est le mot nul (c'est-à-dire le mot dont toutes les composantes sont nulles). On va à présent décrire une variante de réalisation du procédé décrit en référence à la figure 2. Selon cette variante, l'étape E206 de réduction des polynômes de l'ensemble étendu et l'étape E208 de calcul du déterminant z*(X) à partir des polynômes réduits i̇(X,Y) sont remplacées par les étapes suivantes (qui permettent d'aboutir au même déterminant z*(X)) : E204 (sans réduction modulo Fo ), où beta est le degré maximum en Y des polynômes de cet ensemble étendu ;beta élément en ligne i et colonne (j + 1) le polynôme i̇,j (X), En effet, le polynôme Fo(X,Y), et de même tous les polynômes du s'annulent notamment pour les points (x,y) étiquetant les composantes erronées du mot reçu et qu'ainsi leur présence dans la matrice ne remet pas en cause l'écriture de son déterminant sous la forme présentée ci-dessus, à savoir : Le schéma synoptique de la figure 3 représente un appareil de lecture de signaux numériques codés 70 incorporant le décodeur 10. Cet appareil 70 comprend un clavier 711, un écran 709, un destinataire d'informations externe 109, un lecteur de données 105 et un démodulateur 106, conjointement reliés à des ports d'entrée/sortie 703 du décodeur 10 qui est réalisé ici sous la forme d'une unité logique. Le décodeur 10 comporte, reliés entre eux par un bus d'adresses et de données 702 : - une unité centrale de traitement 700, - une mémoire vive (RAM) 704, - une mémoire morte (ROM) 705, et - lesdits ports d'entrée/sortie 703. Chacun des éléments illustrés en figure 3 est bien connu de l'homme du métier des micro-ordinateurs et des systèmes de stockage de masse et, plus généralement, des systèmes de traitement de l'information. Ces éléments connus ne sont donc pas décrits ici. On observe, cependant, que : - le destinataire d'informations 109 pourrait être, par exemple, un périphérique d'interface, un afficheur, un modulateur, une mémoire externe ou un autre système de traitement de l'information (non représenté), et pourrait être adapté à recevoir des séquences de signaux représentatifs de parole, de messages de service ou de données multimédia notamment de type IP ou ATM, sous forme de séquences de données binaires, - le lecteur 105 est adapté à lire des données enregistrées sur un support tel qu'un disque magnétique ou magnéto-optique. La mémoire vive 704 conserve des données, des variables et des résultats intermédiaires de traitement, dans des registres de mémoire portant, dans la description, les mêmes noms que les données dont ils conservent les valeurs. La mémoire vive 704 comporte notamment les registres suivants : - des registres "mots_reçus", dans lesquels sont conservés les mots reçus, - un registre "symboles_estimés", dans lequel sont conservés les symboles issus d'un mot reçu en cours de correction, et - un registre "symboles information", dans lequel sont conservés les symboles résultant de la suppression de la redondance.La mémoire morte 705 est adaptée à conserver, dans des registres qui, par commodité, possèdent les mêmes noms que les données qu'ils conservent : - le programme de fonctionnement de l'unité centrale de traitement 700, dans un registre "programme", - la longueur des mots de code dans un registre "n", - le cardinal du corps de Galois Fq servant d'alphabet pour le code utilisé, dans un registre "q", - le nombre de symboles d'information servant à construire un mot de code, dans un registre "k", et - une table mémorisant les éléments de la matrice de parité H, c'est-àdire les valeurs prises par les monômes YjXi aux points de l'ensemble de localisation. On a décrit ci-dessus à titre d'exemple une application de l'invention au stockage de masse des données, mais il est clair que les procédés selon l'invention peuvent tout aussi bien être mis en u̇vre au sein d'un réseau de télécommunications, auquel cas l'unité 105 par exemple pourrait être un récepteur adapté à mettre en oeuvre un protocole de transmission de données par paquets sur un canal hertzien. REVENDICATIONS 1. Procédé de localisation d'agrégats erronés de composantes d'un mot reçu, appliqué au décodage pour code de géométrie algébrique défini sur une puissance a en la seconde variable, les composantes du mot reçu étant étiquetées par des points (x,y) de la courbe regroupés en agrégats de points ayant une première coordonnée commune, caractérisé en ce qu'il comprend les étapes suivantes : - détermination d'une base de Grôbner associée au mot reçu et variable (Y), afin d'obtenir, par adjonction à la base de Grôbner, un ensemble étendu de a polynômes ;- détermination, sur la base des a polynômes de l'ensemble étendu, de seconde variable (Y) qui forment une matrice de polynômes dont le déterminant (z*(X) est un polynôme qui s'annule sur la première coordonnée (x) des points erronés (x, y ) du mot reçu ; - détermination d'au moins une valeur de la première variable qui annule ledit déterminant. 2. Procédé selon la revendication 1, caractérisé en ce que l'étape de détermination de a-a' polynômes est mise en u̇vre en cas de vérification positive de la condition a' 3. Procédé selon la revendication 1 ou 2, caractérisé en ce que, l'équation polynomiale définissant la courbe étant de degré b en la première variable (X) et de degré a en la seconde variable (Y) et le poids d'un polynôme étant la valeur maximale prise par la formule ai+bj sur l'ensemble des monômes XiYj de ce polynôme, les puissances (Ys) de la seconde variable utilisées pour la détermination de chacun des a-a' polynômes sont telles que les poids des 4. Procédé selon la revendication 3, caractérisé en ce que l'étape de détermination des a-a' polynômes comprend les étapes suivantes : ordre croissant de la puissance j(i) en la seconde variable (Y) du monôme qui - pour chacune des valeurs entières k de 0 à a-1 pour laquelle j(i)=k n'est pas réalisé, détermination d'un polynôme construit comme suit : * s'il existe un plus grande') tel que j(i') en la seconde variable. 5. Procédé selon l'une des revendications 1 à 4, caractérisé en ce qu'il comprend une étape de réduction des polynômes de l'ensemble étendu modulo le 6. Procédé selon la revendication 5, caractérisé en ce que la matrice de seconde variable (Y) dans les polynômes réduits ( i̇(X,Y)). 7. Procédé selon la revendication 5 ou 6, caractérisé en ce que la matrice de polynômes est carrée de dimension a. 8. Procédé selon l'une des revendications 1 à 4, caractérisé en ce que la matrice de polynômes a notamment pour éléments les polynômes facteurs de monômes de la seconde variable (Y) dans les polynômes de l'ensemble étendu. 9. Procédé selon la revendication 8, caractérisé en ce que la matrice de polynômes a notamment pour éléments les polynômes facteurs de monômes de la polynôme (Fo(X,Y) ) définissant l'équation polynomiale. 10. Procédé selon l'une des revendications 1 à 9, caractérisé en ce qu'il comprend une étape d'élimination des facteurs multiples dans ledit déterminant. 11. Procédé selon la revendication 10, caractérisé en ce que l'étape d'élimination des facteurs multiples comprend des étapes de calcul du plus grand diviseur commun d'un polynôme et de sa dérivée. 12. Procédé de localisation d'agrégats erronés de composantes d'un mot reçu, appliqué au décodage pour code de géométrie algébrique défini sur une composantes du mot reçu étant étiquetées par des points (x,y) de la courbe regroupés en agrégats de points ayant une première coordonnée commune, caractérisé en ce qu'il comprend les étapes suivantes : - détermination à partir du mot reçu d'au moins un premier polynôme à composante erronée du mot reçu ; - détermination, en partie au moins sur la base des premier et second monômes de la seconde variable (Y) qui forment une matrice de polynômes dont le déterminant (z*(X) est un polynôme qui s'annule sur la première coordonnée (x ) dudit point (x,y) ; - détermination d'au moins une valeur qui annule ledit déterminant. 13. Procédé selon la revendication 12, caractérisé en ce que, l'équation polynomiale définissant la courbe étant de degré b en la première variable (X) et de degré a en la seconde variable (Y) et le poids d'un polynôme étant la valeur maximale prise par la formule ai+bj sur l'ensemble des monômes XiYj de ce polynôme, le polynôme (Ys) de la seconde variable est tel que le poids du second 14. Procédé selon la revendication 12 ou 13, caractérisé en ce que, l'équation polynomiale étant de degré a en la seconde variable (Y) et l'étape de détermination d'au moins un premier polynôme générant a' premiers polynômes, l'étape de détermination d'au moins un second polynôme génère (alpha -alpha ') seconds seconde variable (Y). 15. Procédé de décodage d'un mot reçu pour code de géométrie algébrique défini sur une courbe algébrique d'équation polynomiale à deux points (x,y) de la courbe regroupés en agrégats de points ayant une première coordonnée commune, caractérisé par les étapes suivantes : - localisation des agrégats erronés au moyen d'un procédé selon l'une des revendications 1 à 14 ; - correction d'erreur dans les agrégats localisés. 16. Dispositif de localisation d'agrégats erronés de composantes d'un mot reçu, adaptée au décodage pour code de géométrie algébrique défini sur une puissance a en la seconde variable, les composantes du mot reçu étant étiquetées par des points (x,y) de la courbe regroupés en agrégats de points ayant une première coordonnée commune, caractérisé en ce qu'il comprend : - des moyens de détermination d'une base de Grôbner associée au mot reçu et comportant a' polynômes ( Fi (X, Y) ) ; - des moyens de détermination de a-a' polynômes (Ys.Fi(X, Y)) chacun la seconde variable (Y), afin d'obtenir, par adjonction à la base de Grôbner, un ensemble étendu de a polynômes ; - des moyens de détermination, sur la base des a polynômes de l'ensemble étendu, de polynômes ( i ,j ,(X)) en la première variable (X) facteurs de monômes en la seconde variable (Y) qui forment une matrice de polynômes dont le déterminant (z*(X) est un polynôme qui s'annule sur la première coordonnée (x ) des points erronés (x, y ) du mot reçu ; - des moyens de détermination d'au moins une valeur de la première variable qui annule ledit déterminant. 17. Dispositif selon la revendication 16, caractérisé en ce que les moyens de détermination de a-a' polynômes sont mis en oeuvre en cas de vérification positive de la condition a ' 18. Dispositif selon la revendication 16 ou 17, caractérisé en ce que, l'équation polynomiale définissant la courbe étant de degré b en la première variable (X) et de degré a en la seconde variable (Y) et le poids d'un polynôme étant la valeur maximale prise par la formule ai+bj sur l'ensemble des monômes XiYj de ce polynôme, les moyens de détermination de a-a' polynômes sont configurés de telle sorte que les poids des polynômes (Ys.Fi(X,Y)) de l'ensemble étendu sont différents deux à deux. 19. Dispositif selon la revendication 18, caractérisé en ce que les moyens de détermination des a-a' polynômes comprennent : - des moyens d'ordonnancement des polynômes (Fi(X,Y)) de la base de Grôbner par ordre croissant de la puissance j(i) en la seconde variable (Y) du monôme qui détermine le poids du polynôme concerné (Fi(X,Y) ) ; - des moyens de détermination d'un polynôme construit pour chacune des valeurs entières k de 0 à a-1 pour laquelle j(i)=k n'est pas réalisé, qui sont configurés pour : * s'il existe un plus grand j(i') tel que j(i') * s'il n'existe pas de tel plus grand j(i') , construire le polynôme seconde variable. 20. Dispositif selon l'une des revendications 16 à 19, caractérisé en ce qu'il comprend des moyens de réduction des polynômes de l'ensemble étendu modulo le polynôme (Fo(X,Y) ) définissant l'équation polynomiale. 21. Dispositif selon la revendication 20, caractérisé en ce que les moyens de détermination de polynômes en la première variable sont configurés de telle sorte que la matrice de polynômes a pour éléments les polynômes ( i̇,j (X)) facteurs de monômes de la seconde variable (Y) dans les polynômes réduits ( i̇(X,7)). 22. Dispositif selon la revendication 20 ou 21, caractérisé en ce que la matrice de polynômes est carrée de dimension a. 23. Dispositif selon l'une des revendications 16 à 19, caractérisé en ce que les moyens de détermination de polynômes en la première variable sont configurés de telle sorte que la matrice de polynômes a notamment pour éléments les polynômes facteurs de monômes de la seconde variable (Y) dans les polynômes de l'ensemble étendu. 24. Dispositif selon la revendication 23, caractérisé en ce que les moyens de détermination de polynômes en la première variable sont configurés de telle sorte que la matrice de polynômes a notamment pour éléments les polynômes facteurs de monômes de la seconde variable (Y) dans des polynômes polynomiale. 25. Dispositif selon l'une des revendications 16 à 24, caractérisé en ce qu'il comprend des moyens d'élimination des facteurs multiples dans ledit déterminant. 26. Dispositif selon la revendication 25, caractérisé en ce que les moyens d'élimination des facteurs multiples comprennent des moyens de calcul du plus grand diviseur commun d'un polynôme et de sa dérivée. 27. Dispositif de localisation d'agrégats erronés de composantes d'un mot reçu, adaptée au décodage pour code de géométrie algébrique défini sur une courbe algébrique d'équation polynomiale à deux variables (Fo (X,Y) = 0), les composantes du mot reçu étant étiquetées par des points (x,y) de la courbe regroupés en agrégats de points ayant une première coordonnée commune, caractérisé en ce qu'il comprend : - des moyens de détermination à partir du mot reçu d'au moins un premier polynôme à deux variables (Fi(X,Y)) qui s'annule pour un point (x,y) étiquetant une composante erronée du mot reçu ; - des moyens de détermination d'au moins un second polynôme seconde variable (Y) ; - des moyens de détermination, en partie au moins sur la base des premier et second polynômes, de polynômes ( i,j (X)) de la première variable (X) facteurs de monômes de la seconde variable (Y) qui forment une matrice de polynômes dont le déterminant (z*(X)) est un polynôme qui s'annule sur la première coordonnée (x ) dudit point (x, y ) ; - des moyens de détermination d'au moins une valeur qui annule ledit déterminant. 28. Dispositif de décodage d'un mot reçu pour code de géométrie algébrique défini sur une courbe algébrique d'équation polynomiale à deux variables (Fo (X,Y) = 0), les composantes du mot reçu étant étiquetées par des points (x,y) de la courbe regroupés en agrégats de points ayant une première coordonnée commune, caractérisé par : - un dispositif de localisation des agrégats erronés selon l'une des revendications 1 à 14 ; - des moyens de correction d'erreur dans les agrégats localisés. 29. Décodeur comprenant au moins un dispositif de localisation d'erreurs selon l'une des revendications 16 à 27, et au moins une unité de suppression de la redondance. 30. Appareil de réception de signaux numériques codés comprenant un décodeur selon la revendication 28 et des moyens pour démoduler lesdits signaux numériques codés. 31. Système informatique comprenant un décodeur selon la revendication 28, au moins un disque dur et au moins un moyen de lecture de ce disque dur. 32. Moyen de stockage de données inamovible comportant des instructions de code de programme informatique pour l'exécution des étapes d'un procédé selon l'une des revendications 1 à 15. 33. Moyen de stockage de données partiellement ou totalement amovible, comportant des instructions de code de programme informatique pour l'exécution des étapes d'un procédé selon l'une des revendications 1 à 15. 34. Programme d'ordinateur, contenant des instructions telles que, lorsque ledit programme commande un dispositif de traitement de données programmable, lesdites instructions font que ledit dispositif de traitement de données met en u̇vre un procédé selon l'une des revendications 1 à 15.