Brevet FR2878096A1 — publié le 20060519

A(X)=11(X-x,,) , v=1 La présente invention concerne les systèmes de communication ou d'enregistrement de données dans lesquels, afin d'améliorer la fidélité de la transmission ou du stockage, on soumet les données à un codage de canal. Elle concerne plus particulièrement un procédé de localisation d'erreurs ainsi que les dispositifs et appareils destinés à mettre en oeuvre ce procédé. On rappelle que le codage de canal dit en blocs consiste à transmettre à un récepteur (ou à enregistrer sur un support de données) des mots de code qui sont formés en introduisant une certaine redondance dans les données à transmettre. Plus précisément, on transmet au moyen de chaque mot de code l'information initialement contenue dans un nombre prédéterminé k de symboles, dits symboles d'information , prélevés dans un alphabet de taille finie q; on calcule à partir de ces k symboles d'information un nombre n > k de symboles appartenant à cet alphabet, qui constituent les composantes des mots de code: v=(vi,v2, .,vn). L'ensemble des mots de code obtenus quand chaque symbole d'information prend une valeur quelconque dans l'alphabet, constitue une sorte de dictionnaire appelé code de dimension k et de longueur n...DTD: Notamment, lorsque la taille q de l'alphabet est prise égale à une puissance d'un nombre premier, on peut donner à cet alphabet une structure de 20 corps ( field en anglais), dit corps de Galois ( Galois field en anglais), noté Fq. Par exemple, pour q = 2, Fq est un alphabet binaire, et pour q = 28 = 256, Fq est un alphabet d'octets ( bytes en anglais). On appelle distance de Hamming entre deux mots de même longueur le nombre d'indices pour lesquels la composante du premier mot est différente de la composante du deuxième mot. Pour un code donné, on appelle distance minimale d la plus petite distance de Hamming entre deux mots différents quelconques appartenant au code; c'est un paramètre important du code. Certains codes, appelés codes linéaires , sont tels que toute combinaison linéaire de mots de code (avec les coefficients pris dans l'alphabet) est encore un mot de code. Ces codes peuvent, de façon commode, 2878096 2 être associés à une matrice H de dimension (n - k)x n, dite matrice de parité : un mot v de longueur n donné est un mot de code si, et seulement si, il vérifie la relation: H É vT = 0 (où l'exposant T indique la transposition) ; on dit alors que le code est orthogonal à cette matrice H. Il y a erreur de transmission si la différence e entre un mot reçu r et le mot de code v correspondant envoyé par l'émetteur, est non- nulle. On dit que les erreurs de transmission sont causées par le bruit du canal . Pour détecter d'éventuelles erreurs de transmission et si possible les corriger, on met en oeuvre au niveau du récepteur un procédé de décodage qui exploite judicieusement la redondance mentionnée ci- dessus. Plus précisément, le décodage se fait en deux étapes principales. La première étape consiste à associer au mot reçu un mot de code associé v. Pour ce faire, le décodeur calcule d'abord le vecteur de syndromes d'erreurs s = H É rT = H É eT de longueur (n - k) (dans le cadre de la présente invention, on ne fait pas de différence entre le terme mot et le terme vecteur ). Si les syndromes sont tous nuls, on supposera qu'il n'y a pas eu d'erreur de transmission, et le mot de code associé sera alors simplement pris égal au mot reçu. Si ce n'est pas le cas, on en déduit que le mot reçu est erroné, et l'on procède alors à des calculs destinés à estimer la valeur de l'erreur e; autrement dit, ces calculs fournissent une valeur estimée ê de l'erreur telle que le mot (r e) soit un mot de code, qui constituera alors le mot de code associé V. Habituellement, cette première étape du décodage est décomposée en deux sous-étapes distinctes: une première sous-étape, dite de localisation d'erreurs , au cours de laquelle on détermine quelles sont les composantes du mot reçu dont la valeur est erronée, et une seconde sous-étape, dite de correction d'erreurs , au cours de laquelle on calcule une estimation de l'erreur de transmission affectant ces composantes. La seconde étape consiste simplement à inverser le procédé de codage. Si le mot reçu était correct ou si l'on est parvenu, lors de la première étape, à y corriger toutes les erreurs de transmission, cette seconde étape permet évidemment de retrouver les k symboles d'information initiaux (avant codage) correspondant à ce mot reçu. On notera que dans le cadre de la présente invention, on parlera souvent, pour faire court, de décodage pour désigner uniquement la première de ces étapes, étant entendu que l'homme du métier est capable sans difficulté de mettre en oeuvre la seconde étape. On assigne habituellement comme but au décodage d'associer au mot reçu le mot de code situé à la distance de Hamming la plus courte de ce mot reçu. Raisonnablement, on va essayer d'identifier la position des erreurs éventuelles dans un mot reçu, et de fournir le symbole de remplacement correct (c'est-à-dire, identique à celui envoyé par l'émetteur) pour chacune de ces positions, chaque fois que le nombre de positions erronées est au plus égal à INT [(d -1) /2] (où INT désigne la partie entière) pour un code de distance minimale d. Pour certaines configurations d'erreurs, on peut même parfois faire mieux. Toutefois, il n'est pas toujours aisé de mettre au point un algorithme de décodage atteignant cette performance. On notera également que, lorsque l'algorithme choisi parvient à proposer une correction pour le mot reçu, cette correction est d'autant plus fiable (du moins, pour la plupart des canaux de transmission) qu'elle concerne un plus petit nombre de positions. Parmi les codes connus, on peut citer les codes dits de Reed-Solomon , qui sont réputés pour leur efficacité. Ce sont des codes linéaires dont la distance minimale d est égale à (n k + 1). La matrice de parité H du code de Reed-Solomon de dimension k et de longueur n (où n est inférieur ou égal à (q -1)) est une matrice à (n k) lignes et à n colonnes, qui a la structure d'une matrice de Vandermonde. Cette matrice de parité H peut être définie par exemple en prenant H = a(1-1) (1 2878096 4 Comme mentionné ci-dessus, l'étape d'un procédé de décodage au cours de laquelle on calcule un mot de code associé au mot reçu se décompose habituellement en deux sous-étapes: la première sous-étape, dite de localisation d'erreurs , consiste à identifier dans le mot reçu les éventuelles composantes dont la valeur est erronée, et la seconde sousétape consiste à calculer ensuite la valeur corrigée de ces composantes erronées. Pour le décodage des codes de Reed-Solomon, en ce qui concerne, d'une part, la localisation d'erreurs, on utilise habituellement l'algorithme dit de Berlekamp-Massey : on construit d'abord une matrice S, appelée matrice des syndromes , dont chaque élément est une certaine composante du vecteur de syndromes d'erreurs s = H É rT = H É eT; on cherche ensuite un vecteur A tel que A É S = 0, puis l'on forme un polynôme de localisation d'erreurs A(Z) dont les coefficients sont des composantes du vecteur A; les inverses des racines de ce polynôme A(Z) sont alors, parmi les. éléments w, (où i =1,...,n) de l'ensemble de localisation, ceux qui étiquettent les composantes erronées du mot reçu r. En ce qui concerne, d'autre part, la correction d'erreurs, on utilise habituellement l'algorithme dit de Forney . Pour plus de détails sur les codes de Reed-Solomon, et en particulier les algorithmes de Berlekamp-Massey et de Forney, on pourra se référer par exemple à l'ouvrage de R.E. Blahut intitulé Theory and practice of errorcontrol codes , Addison-Wesley, Reading, Mass.,1983. Dans les supports d'information modernes, par exemple dans les disques durs d'ordinateurs, les CD ( compact discs ) ou encore les DVD ( digital video discs ), on cherche à accroître la densité d'information. Quand un tel support est affecté par un défaut physique tel qu'une éraflure, un nombre important de symboles d'information peuvent être rendus illisibles. On peut toutefois remédier à ce problème en utilisant un code de très grande longueur. Or, comme indiqué ci-dessus, la longueur n des mots dans les codes de Reed- Solomon est inférieure à la taille q de l'alphabet des symboles. Par conséquent, si l'on souhaite disposer d'un code de Reed-Solomon ayant des mots de code de grande longueur, on doit envisager de grandes valeurs de q, ce qui conduit à des mises en oeuvre coûteuses au niveau des calculs et de la mémorisation. De plus, de grandes valeurs de q sont parfois inadaptées à l'application technique envisagée. C'est pourquoi l'on a cherché à construire des codes offrant de manière naturelle une plus grande longueur de mots que les codes de Reed-Solomon sans nécessiter pour autant un alphabet de plus grande taille. On a notamment proposé récemment des codes dits codes de géométrie algébrique ou codes de Goppa géométriques (voir par exemple Algebraic Geometric Codes , par J.H. van Lint, dans Coding Theory and Design Theory , IMA Volumes Math. Appl., vol. 21, pages 137 à 162, Springer-Verlag, Berlin, 1990). Ces codes sont construits à partir d'un ensemble de n couples (x,y) distincts de symboles appartenant à un corps de Galois Fq choisi; cet ensemble de couples constitue l'ensemble de localisation du code de géométrie algébrique. De manière générale, il existe une équation algébrique à deux inconnues X et Y telle que les couples (x,y) de cet ensemble de localisation soient tous des solutions de cette équation algébrique. Les valeurs de x et de y de ces couples peuvent être considérées comme les coordonnées de points Pfl (où /3 =1,...,n) formant une courbe algébrique . Un paramètre important d'une telle courbe est son genre g. Dans le cas particulier où la courbe est une simple droite (le genre g est alors nul), le code de géométrie algébrique se réduit à un code de Reed-Solomon. Pour q et g donnés, certaines courbes algébriques, dites maximales , permettent d'atteindre une longueur égale à (q+2gJ), qui peut être très élevée; par exemple, avec une taille d'alphàbet égale à 256 et un genre égal à 120, on obtient des mots de code de longueur 4096. Parmi tous les codes de géométrie algébrique, on considère habituellement ceux qui sont définis sur une courbe algébrique représentée par une équation F(X,Y) = 0, avec: F(X,Y) =Xb + cya +1cUY'X, 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 A tout monôme de la forme Y'X1, où i et j sont des entiers positifs 10 ou nuls, on associe classiquement un poids , qui est égal par définition à (ai + bj). On peut montrer que les monômes ha = YiX 1 de poids pa m, où a = 1,..., n k, et j est un entier compris entre 0 et (a -1) , constituent une base de l'espace vectoriel L(m P.) des polynômes en X et Y à coefficients dans Fq dont les seuls pôles sont situés à l'infini et sont d'ordre inférieur ou égal à m, où 0 2g 2). Pour tout code de type C(a,b) , on définit classiquement une matrice de parité de la manière suivante: l'élément en ligne a et colonne fi de la matrice de parité est égal au monôme ha évalué au point Pfl (où, rappelons-le, 20 f3=1,...,n) de la courbe algébrique. Chaque point Pfl sert alors à identifier la ème 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 P,g) des fonctions (les monômes ha) qui n'ont de pôles qu'en un seul point, à savoir le point à l'infini. Dans le cadre de la présente invention, on s'intéressera particulièrement à des codes de type C(a,b) particuliers: il s'agit des codes dits hyperelliptiques , qui sont définis sur une courbe algébrique représentée par l'équation F(X,Y) = 0, avec: F(X,Y)=Y2+Yu1(X)+uo(X) , (1) où uo (X) est un polynôme sur Fq de degré exactement égal à (2g + 1) , et u1(X) est un polynôme non-nul sur Fq de degré inférieur ou égal à g. On peut montrer qu'une telle courbe algébrique a effectivement un genre égal à g. 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 à v É A 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. Les codes de géométrie algébrique sont avantageux quant à leur distance minimale d, qui est au moins égale à (n - k + 1- g), et, comme on l'a dit, quant à la longueur des mots de code, mais ils présentent l'inconvénient de requérir des algorithmes de décodage assez complexes, et donc assez coûteux en termes d'équipements (logiciel et/ou matériel) et de temps de traitement. Cette complexité est en fait plus ou moins grande selon l'algorithme considéré, une plus grande complexité étant en principe le prix à payer pour accroître la capacité de correction d'erreurs du décodeur (voir par exemple l'article de Tom Hraholdt et Ruud Pellikaan intitulé On the Decoding of Algebraic-Geometric Codes , IEEE Trans. lnform. Theory, vol. 41 n 6, pages 1589 à 1614, novembre 1995). De manière générale, plus la courbe algébrique utilisée est de genre g élevé et plus les mots de code sont de grande longueur, mais aussi plus le décodage est complexe. On connaît divers algorithmes de localisation d'erreurs pour codes de géométrie algébrique (définis sur une courbe de genre non-nul). Un tel algorithme, appelé algorithme de base , a été proposé par A.N. Skorobogatov et S.G. Vlâdut dans l'article intitulé On the Decoding of Algebraic-Geometric Codes , IEEE Trans. lnform. Theory, vol. 36 n 5, pages 1051 à 1060, novembre 1990). On va décrire sommairement cet algorithme: a) on construit une matrice des syndromes S, de dimension (n k)x(n k), dont chaque coefficient Sv., où j est inférieur ou égal à une valeur frontière w(i) , est égal à une combinaison linéaire judicieusement choisie des éléments s, (v =1,2,...,n-k) du syndrome s, les coefficients Sv au-delà de la frontière restant indéterminés; b) on considère le système d'équations linéaires E lt Su =0, pour j =1,2,..., w() , i=1 où les inconnues li appartiennent au même alphabet de symboles que les éléments des mots de code, et où est un entier compris entre 1 et (n k) tel que le système admette une solution non-triviale (c'est-à-dire une solution où les coefficients li ne sont pas tous nuls), et l'on détermine les valeurs de ces coefficients li correspondant à la plus petite valeur possible de e, que l'on notera 2, et c) on calcule les zéros du polynôme de localisation d'erreurs 2 A(X,Y) = Eli hi(X,Y) i=I (où les monômes ht (X,Y) ont été définis ci-dessus) ; ces zéros comprennent tous les couples (x,y) étiquetant les composantes du mot reçu ayant souffert d'une erreur de transmission. Skorobogatov et Vlâdut ont également proposé, dans le même article cité ci-dessus, une version modifiée de l'algorithme de base , qui permet généralement de corriger un plus grand nombre d'erreurs que l'algorithme de base . On connaît également des algorithmes qui fonctionnent suivant un principe itératif: chaque nouvelle itération d'un tel algorithme fait appel à une composante supplémentaire du vecteur de syndromes d'erreurs s = H É rT. Un exemple d'un tel algorithme de décodage itératif est divulgué dans 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. lnform. Theory, vol. 41, pages 1762 à 1768, novembre 1995). Cet algorithme peut être vu comme une généralisation de l'algorithme de Berlekamp-Massey aux codes de géométrie algébrique définis sur une courbe de genre non-nul. Un autre exemple d'algorithme de décodage itératif pour codes de géométrie algébrique est divulgué dans l'article de M.E. O'Sullivan intitulé Decoding of Codes Defined by a Single Point on a Curve (IEEE Trans. lnform. Theory, vol. 41, pages 1709 à 1719). Pour tout mot reçu r donné, on peut déterminer des polynômes de localisation d'erreurs dont les zéros comprennent tous les 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 engendrer l'idéal de Grôbner au moyen d'un ensemble fini de f polynômes, où f Cette extension est possible à chaque fois que le nombre d'erreurs dans le mot reçu est inférieur ou égal à (n-k-g)/2. En effet, 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 localiser ces erreurs, connaître plus d'éléments de la matrice des syndromes que les éléments que nous qualifierons de connus du fait qu'ils sont égaux à des composantes du vecteur de syndromes d'erreurs s = H É rT ou à de simples combinaisons linéaires de ces composantes (voir l'exemple numérique décrit ci-dessous). 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. lnform. Theory, vol. 39, n 1, janvier 1993). Cet algorithme a essentiellement pour but d'étendre la matrice S au moyen d'étapes de calcul jouant le rôle d'itérations successives. Il faut un nombre d'itérations égal à un certain nombre g', où g' est au plus égal à 2g, pour parvenir au stade où, comme expliqué ci-dessus, il devient possible de calculer une base de Grôbner à partir de la matrice des syndromes étendue S* ainsi obtenue. Comme les couples (x,y) étiquetant les composantes erronées d'un mot reçu vérifient évidemment tous l'équation F(X,Y) = 0 de la courbe 15 algébrique, le polynôme F(X,Y) fait partie de l'idéal de Grôbner, et l'on peut par conséquent réduire modulo F(X,Y) les f polynômes G,(X,Y) de toute base de Grôbner donnée. Il en résulte qu'il existe toujours une base de Grôbner dont tous les éléments ont un degré en Y inférieur à a. Dans le cas particulier des codes hyperelliptiques, où a =2, cela signifie que l'on peut constituer une base de Grôbner dont les f éléments, où f On connaît par ailleurs divers algorithmes pour codes de géométrie algébrique permettant de calculer la valeur corrigée des composantes erronées du mot reçu; autrement dit, ces algorithmes sont aptes à fournir une valeur 25 estimée ê de l'erreur de transmission e subie par le mot de code transmis. Le calcul des erreurs pour les codes de géométrie algébrique est a priori plus compliqué que pour les codes de Reed-Solomon. En effet: - la sous-étape de localisation d'erreurs ne produit pas seulement un polynôme de focalisation d'erreurs (tel que A(Z) ci-dessus), mais plusieurs polynômes, qui forment une base de Grôbner de l'idéal des polynômes de localisation d'erreurs; - ces polynômes de localisation d'erreurs sont des polynômes à deux variables au lieu d'une; et - ces polynômes de localisation d'erreurs ont des dérivées partielles par rapport à ces deux variables, de sorte que les algorithmes de correction classiques (tels que l'algorithme de Forney mentionné ci-dessus), qui font intervenir une dérivée unique, ne sont plus applicables. On connaît divers algorithmes de calcul des erreurs pour codes de géométrie algébrique. L'article Algebraic Geometry Codes , de Tom Hoholdt, Jacobus Van Lint et Ruud Pelikaan (Chapitre 10 de Handbook of Coding Theory , North Holland, 1998) construit le produit de certaines puissances des polynômes de la base de Grôbner. Il effectue ensuite une combinaison linéaire de ces produits, affectés de coefficients adéquats. Il démontre enfin que la valeur du polynôme ainsi obtenu, prise au point (x, y) de l'ensemble de localisation est, au signe près, la valeur de l'erreur pour la composante du mot reçu étiquetée par ce point (x, y). L'article A Generalized Forney Formula for Algebraic Geometric Codes , de Douglas A. Leonard (IEEE Trans. lnform. Theory, vol. 42, n 4, pages 1263 à 1268, juillet 1996) calcule les valeurs des erreurs en évaluant un polynôme à deux variables en les points dont lés coordonnées sont les zéros communs des polynômes de localisation d'erreurs. L'article A Key Equation and the Computation of Error Values for Codes from Order Domains de John B. Little (publié sur Internet le 7 avril 2003) calcule les valeurs des erreurs en évaluant deux polynômes à une variable en les mêmes points que précédemment. Ces trois algorithmes sont complexes à mettre en oeuvre. La demande de brevet EP-1 434 132 au nom de CANON décrit un procédé de décodage applicable notamment aux codes, décrits ci-dessus, de géométrie algébrique à un point définis sur une courbe algébrique de type C(a,b). Ce procédé de décodage effectue à la fois la localisation et ta correction d'erreurs. Nous allons à présent le décrire de manière assez détaillée. Ce procédé de décodage repose sur la subdivision de l'ensemble de localisation du code en sous-ensembles appelés agrégats . Par définition, un agrégat regroupe les couples (x,y) de l'ensemble de localisation partageant la même valeur de x, lorsque l'on prend: a Soit m le poids maximal des monômes définissant les lignes de la matrice de parité (voir ci-dessus). Selon la demande EP-1 434 132, on classe ces monômes dans des ensembles de monômes M. ={YJX1I05iS(m-bj)/a} pour 0 ,v(x/,y2(x,)(x,))l un mot de code quelconque. On construit, pour chaque agrégat attaché à l'une des valeurs xl,x2,...,x, de x, (jmax +1) symboles agrégés 2(x) (( J v.(x) = E [yp (x)J v(x, yp (x)) p=1 pour j = 0,..., jmax. Ces symboles agrégés servent à former (jmax +1) mots agrégés V j =[vj(x1),...,Vi(x,u)] , de longueur t...DTD: On vérifie facilement que la condition d'appartenance au code de géométrie algébrique (à savoir H É vT =0) est équivalente à l'ensemble de (Jmax +1) équations: T Hi(J) .vJ =0, où la fonction t(j) est donnée ci-dessus et, par définition, 1 1 1 Ht = xl X2.. xu t 1 t I t 1 XI x2 xu Or cette matrice Ht est une matrice de Vandermonde définie sur Fq; par conséquent, si l'on considère, pour chaque valeur de j, que Htu) est une matrice de parité définissant un ensemble de mots de code vi, cet ensemble constitue un code de ReedSolomon. On dit alors que l'on a 15 décomposé le code de géométrie algébrique considéré en un certain nombre de codes de Reed-Solomon composants . L'intérêt de cette formulation est que l'on dispose, pour les codes de Reed-Solomon, d'algorithmes de décodage très simples, et très performants au moins pour certains types de canaux. Par exemple, un mot r ayant été reçu, on calcule d'abord, pour j = 0,...,jmax, les mots reçus agrégés r _[rj(xl),...,ri(x/i)] , dans lesquels, pour x = x1,...,x, les symboles reçus agrégés rj(x) sont donnés par 2(x) rj(x)= E [Yp(x)]r(x, yp(x)) p=1 Puis on utilise l'algorithme de Berlekamp-Massey pour la localisation des (2) symboles erronés de chaque mot ri, suivi de l'algorithme de Forney pour la correction de ces symboles erronés, d'après le vecteur de syndromes d'erreurs s = Htu) É rT. Enfin, on calcule les symboles v(x, y p (x)) du mot de code associé à partir des symboles corrigés P1(x) en utilisant le système d'équations 2(x) @1(x) = E, [.Yp (x)]J v(x, yp (x)) p=1 où j prend un nombre de valeurs différentes (le nombre d'équations) au moins égal à 2(x) (le nombre d'inconnues). Ce procédé de décodage requiert donc que (jmax +1) soit au moins égal à 2max, où 21max est le plus grand parmi les cardinaux d'agrégat 2(x) . Par rapport aux algorithmes de correction d'erreurs connus applicables de manière générale aux codes de géométrie algébrique considérés, le gain en complexité résultant de la mise en oeuvre du procédé selon la demande EP- 1 434 132 est significatif, et ce, malgré la nécessité de mettre en oeuvre un algorithme de correction d'erreurs pour code de Reed- Solomon (par exemple l'algorithme de Forney) 2, ax fois, et de résoudre pour chaque agrégat erroné étiqueté par une valeur x de X un système d'équations (3) ; on notera à cet égard que le nombre d'équations dans chacun de ces systèmes est au plus égal à a (l'exposant de Y dans l'équation représentant la courbe algébrique),puisque la taille de tout agrégat (c'est à dire le nombre de solutions, pour x fixé, de l'équation représentant la courbe algébrique) est au plus égale à a. On notera par ailleurs que le système d'équations (3) est un système de Vandermonde: il possède donc toujours une, et une seule, solution; de plus, comme il est bien connu de l'homme du métier, la résolution de ce type de système d'équations linéaires est, avantageusement, particulièrement simple. La demande française n 0402033 au nom de CANON décrit un procédé, applicable aux codes de géométrie algébrique à un point définis sur une courbe algébrique de type C(a,b), qui effectue la correction d'erreurs dans un mot reçu r après que les agrégats erronés de ce mot reçu aient été (3) localisés d'une manière ou d'une autre. Plus précisément, ce procédé permet de calculer l'estimation de l'erreur Ei(x) = ri(x) P1(x) sur le symbole reçu (x) 1 agrégé rj(x) = [yp (x)}'r(x, yp (x)) (voir équations (2) et (3) ci-dessus). p=0 Selon la demande française n 0402033, le calcul des valeurs 5 (estimées) des erreurs comprend notamment les étapes suivantes (où la notation (C1 ç2) représente le produit scalaire de deux mots c1 et c2 de longueur n) : - on compte le nombre l de valeurs différentes de x apparaissant dans ces points associés à des composantes erronées de L7 chacune de ces valeurs de x définissant un agrégat erroné dont les éléments sont tous les 2(x) points (x, yp(x)), où p = 0,...,2(x) 1, de l'ensemble de localisation correspondant à cette valeur de x, - on calcule, pour 1=0,...,21 1 et '= É'2m ax -1, où 2max est la valeur maximale des cardinaux 2(x) des agrégats erronés, les syndromes d'erreurs étendus 6 (0= (Y'X I, où e est l'erreur de transmission affectant r et Y' X' représente le mot dont les composantes sont égales à la valeur prise par le monôme Y'X' aux points de l'ensemble de localisation, - on met en oeuvre, pour j= 0,..., lmax -1, au moyen du polynôme de syndromes d'erreurs 21 1 SJ(Z)= Euj(i)Z, 1=0 un algorithme de correction d'erreurs adapté aux codes de Reed-Solomon, de manière à calculer les erreurs Ej(x) sur celles des composantes d'un mot de code de Reed-Solomon défini sur le même corps de Galois que ledit code de géométrie algébrique qui sont étiquetées par les l valeurs de x associées à un 25 agrégat erroné, et - on calcule, pour chaque valeur de x telle qu'il existe au moins une valeur de j pour laquelle Ej(x) est non-nulle, les estimations ê(x, y p (x)) des 2878096 16 erreurs respectives sur les composantes r(x, y p (x)) de r en résolvant le système d'équations 2(x) t Ej(x) E [yp(x)]J ê(x,yp(x) ) , p=o où l'on choisit des équations (associées chacune à une valeur distincte de j) en nombre au moins égal au nombre de composantes erronées de l'agrégat considéré. Dans la demande française n 0408345 au nom de CANON, il est fait observer que, pour pouvoir mettre en oeuvre le procédé selon la demande n 0402033, décrit succinctement ci-dessus, il n'est pas nécessaire de connaître les couples (x, y p (x)) étiquetant les composantes erronées du mot reçu, mais seulement toutes les valeurs de x dans ces couples (autrement dit les valeurs qui étiquettent les agrégats erronés). Cette remarque s'applique notamment aux systèmes d'équations (4) : il suffit en effet de considérer que les symboles ê(x, yp(x)) représentent une erreur nulle Si la composante correspondante r(x, yp (x)) est correcte, et d'utiliser un nombre d'équations égal à la taille de l'agrégat, pour obtenir toutes les valeurs des estimations d'erreurs ê(x, y p (x)) , que celles-ci soient nulles ou non. La demande française n 0408345 enseigne donc un procédé de localisation d'agrégats erronés de composantes d'un mot reçu r pour un code de géométrie algébrique à un point défini sur une courbe algébrique de type C(a,b) représentée par une équation F(X,Y) = 0, procédé dans lequel on associe à ce mot reçu r un ensemble E de polynômes de localisation d'erreurs à deux variables X et Y (cet ensemble E est donc un sousensemble fini de l'idéal de Grôbner associé au mot reçu r, et peut en particulier être une base de cet idéal). Selon ce procédé, si l'idéal de Grôbner contient un polynôme qui ne dépend que de la variable X, il suffit de calculer les racines de ce polynôme pour obtenir les valeurs étiquetant les agrégats erronés; sinon: - on détermine un polynôme de localisation d'erreurs en X à partir d'au moins deux polynômes appartenant à l'ensemble cp = EU {F(X,Y)} ; et (4) 2878096 17 - on détermine, à partir dudit polynôme de localisation d'erreurs en X, un ensemble de valeurs de X comprenant les valeurs de X étiquetant lesdits agrégats erronés. On peut ainsi remplacer avantageusement la localisation complète des erreurs par un algorithme moins complexe, dans lequel on détermine un ensemble de valeurs de x comprenant toutes celles pour lesquelles qu'il existe au moins un point (x, y) de l'ensemble de localisation du code tel que la composante du mot reçu r étiquetée par ce point soit erronée (c'est-à-dire tel que ce couple (x, y) soit un zéro commun des polynômes de la base de Grôbner ç), mais sans avoir à calculer pour autant les valeurs correspondantes de y. Comme expliqué ci-dessus au sujet du procédé selon la demande française n 0402033, l'identification des agrégats erronés sert de préalable au calcul des valeurs d'erreurs au sein de mots appartenant à des codes de ReedSolomon. Or les algorithmes de correction d'erreurs classiques (tels que l'algorithme de Forney) utilisent un polynôme de localisation d'erreurs de la forme: (5) A(X)=fl(X x,,) v =1 (à une constante multiplicative près), où les symboles x, (où v =1,...,1) désignent les valeurs de X étiquetant un agrégat erroné (on peut aussi, en variante, utiliser le polynôme de localisation d'erreurs A(X) _ [T (1 Xx ), dont les racines sont égales aux quantités 1/x,,). En revanche, le polynôme de localisation d'erreurs en X obtenu dans une étape intermédiaire du procédé selon la demande française n 0408345 (voir ci- dessus) admet, en général, d'une part, un facteur (X x ) porté à une certaine puissance, qui peut être supérieure à 1, pour chaque valeur x, de X étiquetant un agrégat erroné, et d'autre part des facteurs supplémentaires correspondant à des racines excédentaires . C'est pourquoi la dernière étape de ce procédé consiste à calculer les racines xw de ce polynôme de localisation d'erreurs en X obtenu dans une étape intermédiaire, de manière à pouvoir ensuite construire un polynôme de localisation d'erreurs par produit des facteurs (X xw) . Manifestement, il serait bien plus commode de pouvoir disposer, dès l'abord, d'un polynôme de localisation d'erreurs en X dont, à coup sûr, d'une part, l'ensemble des racines est identique à l'ensemble des x , et dont, d'autre part, ces racines sont simples (par opposition à multiples ). Les auteurs de la présente invention se sont donc demandés s'il ne serait pas possible, au moins pour certains types de codes de géométrie algébrique, de trouver un algorithme fournissant directement un polynôme de localisation d'agrégats erronés ayant ces propriétés. L'invention concerne donc un procédé de localisation d'agrégats erronés de composantes d'un mot reçu r pour un code défini sur une courbe hyperelliptique représentée par une équation du type Y2 +Yu1(X)+uo(X) = 0, définie sur un corps de Galois dont le cardinal q est égal à une puissance de 2 et est supérieur à 2, procédé dans lequel on calcule une base de Grôbner g associée au mot reçu L, ledit procédé étant remarquable en ce que, lorsque l'idéal de Grôbner associé à r ne comprend pas de polynôme ne dépendant que de la variable X, il comprend les étapes suivantes: - on obtient un polynôme z(X) qui est égal à z(X)=uo(X)[a1(X)]2 u1(X) ai(X)ao(X)+[ao(X)]2 si ladite base de Grôbner ç ne contient qu'un élément Gl (X, Y) = ao(X)+Yal (X) , et qui est égal à z(X) = ao (X)bi (X) at (X) b0 (X) si ladite base de Grôbner g contient deux éléments GI (X,Y) = ao (X) + Yal (X) et G2 (X, Y) = bo (X) + Yb' (X) , - on calcule la dérivée z'(X) de z(X), - on calcule le plus grand commun diviseur D(X) de z(X) et z'(X) , qui est de la forme D(X) = E, di x2', et 19 - on calcule le polynôme A(X) = z(X) D*(X) ' où D*(X)=E.diq/2Xi En effet, comme expliqué en détail ci-dessous, le polynôme A(X) ainsi obtenu possède bien les propriétés souhaitées. En particulier, ce polynôme A(X) ne possède que des racines simples, alors que, dans le cas dudit polynôme de localisation d'erreurs en X obtenu dans une étape intermédiaire du procédé selon la demande française n 0408345, cette propriété n'est pas garantie. Selon des caractéristiques particulières, on obtient l'ensemble des valeurs de X étiquetant les agrégats erronés dudit mot reçu r en calculant les racines dudit polynôme A(X) . En effet, la correction du mot reçu conformément au procédé selon la demande française n 0402033 requiert la connaissance des valeurs de X étiquetant les agrégats erronés. Selon d'autres caractéristiques particulières, on obtient l'ensemble des valeurs de X étiquetant les agrégats contenant exactement deux composantes erronées dudit mot reçu r en calculant les racines dudit polynôme D * (X) ou dudit polynôme D(X) . Grâce à ces dispositions, on détermine quels sont les agrégats du mot reçu r contenant exactement deux composantes erronées, et donc, après calcul de toutes les racines de A(X), quels sont (par complémentation) les agrégats du mot reçu r contenant une seule composante erronée. Cette information peut par exemple servir de moyen de vérification du bon déroulement du décodage après obtention du mot de code associé v, par comparaison entre r et pour identifier précisément quelles composantes de r ont été corrigées. Selon un second aspect, l'invention concerne un dispositif de localisation d'agrégats erronés de composantes d'un mot reçu r pour un code défini sur une courbe hyperelliptique représentée par une équation du type Y2 +Yut (X) +uo(X) = 0, définie sur un corps de Galois dont le cardinal q est égal à une puissance de 2 et est supérieur à 2, comprenant des moyens pour calculer une base de Grôbner g associée au mot reçu r, ledit dispositif étant remarquable en ce qu'il comprend également des moyens pour, lorsque l'idéal de Grôbner associé à r ne comprend pas de polynôme ne dépendant que de la variable X: - obtenir un polynôme z(X) qui est égal à z(X) = uo(X)[at(X)]2 -ut (X) at(X)ao(X)+[ao(X)]2 si ladite base de Grôbner g ne contient qu'un élément Gt (X, Y) = ao(X) +Yat (X) , et qui est égal à z(X) = ao (X)bt (X) - al (X)bo (X) si ladite base de Grôbner g contient deux éléments Gt (X,Y).= ao (X) + Yat (X) et G2 (X, Y) = bo (X) + Ybt (X) , calculer la dérivée z'(X) de z(X), - calculer le plus grand commun diviseur D(X) de z(X) et z'(X), qui est de la forme D(X) = E.d1 X2, et calculer le polynôme A(X) = z(X) D*(X) où D*(X)=E1d1g12Xi. Selon des caractéristiques particulières, ledit dispositif comprend également des moyens pour obtenir l'ensemble des valeurs de X étiquetant les agrégats erronés dudit mot reçu r en calculant les racines dudit polynôme A(X) . Selon d'autres caractéristiques particulières, ledit dispositif comprend également des moyens pour obtenir l'ensemble des valeurs de X étiquetant les agrégats contenant exactement deux composantes erronées dudit mot reçu r en calculant les racines dudit polynôme D*(X) ou dudit polynôme D(X). 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 10 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 décodage 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 décodage 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 oeuvre un procédé selon l'invention, et - la figure 2 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 oeuvre 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 oeuvre 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. La présente invention concerne le décodage des codes hyperelliptiques, définis ci-dessus. Elle concerne entre autres le décodage des codes hyperelliptiques maximaux , également définis ci-dessus. Voici à titre d'exemple trois courbes hyperelliptiques maximales sur Fq: - celle représentée par l'équation F(X, Y) = Y2 + y+ x9, avec q =26 et g = 4, comprend 128 points (à distance finie) ; - celle représentée par l'équation F(X,Y) =Y2 +Y+X17, avec q = 28 et g =8, comprend 512 points (à distance finie) ; et - celle représentée par l'équation F(X,Y) = Y2 +Y +X33, avec q= 210 et g =16, comprend 2048 points (à distance finie). On va à présent illustrer le procédé de codage selon l'invention à 20 l'aide d'un exemple numérique. On notera que cet exemple ne constitue pas nécessairement un choix de paramètres préférentiel pour le codage ou le décodage. Il n'est fourni ici que pour permettre à l'homme du métier de comprendre plus facilement le fonctionnement du procédé selon l'invention. On désignera par Q le code de géométrie algébrique à un point , de dimension 12 et de longueur 30, défini de la manière suivante. L'alphabet des symboles est constitué par le corps de Galois F16. Comme le cardinal de ce corps est une puissance de 2 (16 = 24), le signe + est équivalent au signe devant tout coefficient d'un polynôme à coefficients sur ce corps. On considère la courbe algébrique de genre g = 2 constituée par l'ensemble des solutions (X = x,Y = y) de l'équation à deux inconnues F(X, Y) = Y2 +Y+X5 =0 (6) sur F16; ainsi: uo (X) = X5 et ul (X) =1. On constate qu'en donnant à X une valeur x quelconque dans F16, il existe à chaque fois 2 valeurs y(x) (p =1,2) dans F16 telles que le couple (x, y p (x)) soit solution de l'équation (6) ; ces solutions de l'équation (6) sont les coordonnées des points finis de la courbe (la courbe contient également un point à l'infini noté P.). On choisit de constituer l'ensemble de localisation au moyen de toutes ces solutions sauf celles où x = 0; l'ensemble de localisation a donc un cardinal égal à 30, et il peut être subdivisé en agrégats qui ont chacun un cardinal 2(x) égal à 2. On rappelle que chaque point Pfl de l'ensemble de localisation sert à identifier le,8ème élément de tout mot de code; le nombre de tels points étant ici égal à 30, la longueur n du code est donc elle aussi égale à 30. Ensuite, on considère l'espace vectoriel L( m P.) de polynômes en X et Y à coefficients dans F16 dont les seuls pôles sont situés en P.., et sont d'ordre inférieur ou égal à m, où m est un entier strictement positif. Cet espace vectoriel possède une base constituée par les monômes ha = Y' X, où j est un entier égal à 0 ou à 1, i est un entier positif ou nul, 2i + 5 j 5 m, et a =1,...,n - k. Cette 20 quantité p(ha) = 2i +5 j est le poids du monôme ha. Prenons par exemple: m =19; on obtient alors un ensemble de monômes ha où a =1,...,18, puisque: m-g+1=19-2+1=18. Les monômes ha peuvent être classés dans des sous-ensembles 25 ordonnés de monômes M._ {Y1X 0Si5(19-5j)/2}, pour j égal à 0 ou 1 (ici, jmax =1). Ces sous-ensembles ordonnés de monômes sont explicitement: Mo = {1,X,X2, X3,X4,X5,X6,X7,X8,X9} , et Ml = {Y,YX,YX2,YX3,YX4,YX5,YX6,YX7} . On vérifie que le nombre total de monômes ha est bien égal à : 10+8 = 18. On peut par exemple prendre pour matrice de parité H de ce code Q la matrice dont l'élément en ligne a et colonne /3 est égal à la valeur prise par le monôme ha au point P1 de la courbe algébrique. La redondance (n - k) du code Q étant égale à 18, sa dimension vaut k = 30-18=12. La distance minimale d de ce code est au moins égale à n - k + 1-g= 17. On peut donc corriger (au moins) INT [(17 -1)/2] = 8 symboles ayant subi une erreur de transmission si les erreurs sont localisées. Comme expliqué ci-dessus, parmi les algorithmes connus offrant une telle capacité, l'un des moins complexes est celui divulgué dans la demande française n 0402033. Selon ce procédé, un mot r ayant été reçu, on commence par localiser les erreurs de transmission affectant ce mot. Comme expliqué ci-dessus, un moyen classique pour effectuer cette localisation est: 1) de construire une base de Grôbner g à partir de la matrice des syndromes étendue S * , puis 2) de chercher les zéros communs aux polynômes GÇ,(X,Y) (où ç' =1,...f) constituant cette base G. La seconde sous-étape de localisation que l'on vient de mentionner est assez complexe. Il est nécessaire en effet, pour chaque point PQ = (x13, y13) de l'ensemble de localisation, de vérifier si Gq,(x13, y13) est nul pour chaque valeur de ço =1,... f. Naturellement, dès que l'on constate que G4, (x1, yQ) est non-nul pour une certaine valeur de ç' , on peut passer au point PP suivant. Selon les cas donc, cette vérification exige, pour chaque point P13, le calcul d'un nombre imprévisible de valeurs G,(.9,y1) ; tout ce que l'on sait a priori, c'est que ce nombre est compris entre 1 et f inclus. Pour couvrir l'ensemble de localisation, on devra effectuer au minimum n telles évaluations polynomiales, mais évidemment un nombre bien plus grand en moyenne. On va décrire à présent les étapes principales du procédé selon l'invention. Considérons donc un code défini sur une courbe algébrique représentée par l'équation F(X,Y)=Y2+Yu1(X)+uo(X) , (1) où uo (X) est un polynôme sur Fq de degré exactement égal à (2g +1) , et ul (X) est un polynôme non-nul sur Fq de degré inférieur ou égal à g. Si l'idéal de Grôbner associé à r comprend un polynôme ne dépendant que de la variable X, les racines de ce polynôme fournissent directement les valeurs étiquetant les agrégats erronés. Si en revanche l'idéal de Grôbner ne contient que des polynômes dépendant au moins de la variable Y, on considère une base de Grôbner G de cet idéal. Deux cas peuvent alors se présenter: - dans le premier cas, la base de Grôbner ne contient qu'un seul élément, noté Gl(X,Y)=ao(X)+Ya1(X) ; on forme alors un polynôme z(X) qui est égal à z(X) = uo (X)[al (x)]2 ul (X)al (X)a0 (X) + [ao (X)]2; - dans le second cas, la base de Grôbner contient deux éléments, notés G1(X,Y)=ao(X)+Ya1(X) et G2 (X, Y)=bo(X)+Yb1(X) ; on forme alors un polynôme z(X) qui est égal à z(X) = ao (X)b1(X) al (X)bo (X) . En effet, on peut montrer que, quel que soit le cas, z(X) = fj(X xv)E(Xv) v=1 où s(x,,) désigne le nombre de composantes erronées dans l'agrégat erroné 25 étiqueté par x ; les agrégats étant de cardinal 1 ou 2 pour une équation hyperelliptique, il est clair que s(x ) ne peut être égal qu'à 1 ou à 2. 2878096 27 Selon l'invention, on calcule ensuite la dérivée z'(X) de z(X). Or on peut vérifier aisément que (compte tenu du fait que le double de n'importe quelle quantité sur Fq est identiquement nul lorsque q est une puissance de 2) : - pour les agrégats tels que s(x ) =1, la quantité (X xv) , bien qu'étant un 5 facteur de z(X), n'est pas un facteur de z'(X), cependant que - pour les agrégats tels que s(x ) = 2, la quantité (X xv)2, qui est un facteur de z(X), est aussi un facteur de z'(X). Par conséquent, le PGCD D(X) de z(X) et z'(X) s'écrit D(X)= fJ (X x,,)2. s(x )=2 On note ensuite que le développement de D(X) est de la forme D(X) = Eidi X 2t et que le polynôme D * (X) _ Eidigt 2 X: vérifie manifestement: [D * (X)]2 = D(X) (compte tenu de ce que (di)q = di quelle que soit la valeur de di dans Fq). Mais D*(X)= fl (X xv) e(xv)=2 de sorte que le polynôme A(X) défini par A(X) = D *(X) vérifie bien A(X)=fl(X x ) (5) v=1 comme souhaité. Par conséquent, si l'on souhaite (selon un mode de réalisation de l'invention), trouver les valeurs x, étiquetant les agrégats erronés, il suffit de déterminer les racines de A(X), par exemple au moyen de l'algorithme de Chien (voir l'article de R.T. Chien intitulé Cyclic Decoding Procedures for Bose-Chaudhury-Hocquenghem Codes , IEEE Trans. Inform. Theory, pages 357 à 363, vol. 10, n 5, octobre 1964). On notera que, de manière très avantageuse, les racines (doubles) du polynôme D(X), ou les racines (simples) du polynôme D * (X) , ne sont autres que les valeurs x, de X étiquetant les agrégats contenant exactement deux composantes erronées (les autres valeurs x,, de X étiquetant les agrégats contenant une, et une seule, composante erronée). Le calcul de ces racines peut par exemple servir de moyen de vérification en fin de correction du mot reçu. Pour terminer la description du procédé de localisation en X selon l'invention, on va maintenant présenter un exemple numérique, dans lequel on 10 considérera le code Q, décrit ci-dessus, de dimension 12 et de longueur 30, et défini sur la courbe algébrique représentée par l'équation (6). Les éléments de F16 seront identifiés comme puissances respectives d'un élément primitif a de F16 qui est racine de l'équation z4+z+1=0. Supposons que l'on reçoive un mot r dont les composantes non-nulles sont les suivantes: r(a2,a2) = a13, r(a2,a8) = a11, r(a4,a) = a12, r(a8,a8) = a13, r(a9,a5)=a6, r(a9,a10)=a13, r(a10,a)=a, r(a13,a)=a2. Pour ce mot reçu, le vecteur de syndromes d'erreurs (à n k = 18 composantes) 20 s = H É rT est le suivant: s = H T= [a8a11 a14a a5a7 a a4 a2a41 a a a50 0 0 1]T (7) Dans ce cas, un algorithme de localisation d'erreurs (par exemple, l'algorithme de O'Sullivan cité ci-dessus) produit (au moyen, au passage, du calcul de quatre syndromes de la matrice étendue S*) une base de Grôbner constituée de deux éléments, à savoir GI(X,Y)=ao(X)+Yal(X) et G2 (X, Y)=b0(X)+Yb](X), où ao(X) =a'+ax+ X3+a10X4+X5, al(X)=a10+a10X4+a14X2, b0(X) =a3 +a12X +2) (2 +X3 +a14X4 + a4X5, et b1(X) = a9 +a2X +a4X2 +X3 Conformément à l'invention, on calcule alors: z(X) = ao (X)b1(X) al (X)bo (X) =a12 +a7X +X2 +a5X3 +a4X4 +a6X5 +a3X6 +a6X7 +X8. 5 La dérivée de z(X) est: z'(X) = a7 +a5X2 +a6X4 +a6X6. Le PGCD de z(X) et z'(X) est: D(X) = a4X4 +a11X2 +all et la racine carrée de D(X) est: D*(X)=a2X2+a13X+a13 On obtient enfin le polynôme de localisation en X: A(X)=D(X)* )=a-2(X6+aX5 +a14X4+a2X3+a14X2+a6X+a), dont les racines x = a2,a4,a8,a9,a10,a13 étiquettent donc les agrégats erronés de ce mot reçu. Ceci achève la mise en oeuvre du procédé selon l'invention, mais on va à présent, en outre, montrer comment on peut achever la correction du mot reçu en mettant en oeuvre le procédé, décrit succinctement ci-dessus, selon la demande française n 0402033. L'algorithme de correction d'erreurs pour j= 0 donne: Eo(a2)=a4, Eo(a4) =a12, Eo(a8)=a13, Eo(a9)=1, Eo(alo)=1, et Eo(a13)=a2, et l'algorithme de correction d'erreurs pour j= 1 donne: E1(a2)=a, E1(a4)=a13, E1(a8)=a6, E1(a9)=a', E1(alo)=a, et El(a13)=a3. Pour terminer, on regroupe les résultats ci-dessus agrégat par agrégat, et on résout le système d'équations (4) (de dimension 2) pour chaque agrégat: - pour x1 = a2, sachant que Yl(a2)=a2, Y2(a2)=a8, on trouve: ê(a2,Y1(a2))=a13,ê(a2,Y2(a2))=a11; - pour x2 = a4, sachant que Yl(a4)=a, Y2(a4)=a4, on trouve: e(a4,Y1(a4)) =a12, e(a4,Y2( 4)) = 0 - pour x3 = a8, sachant que Yi(a8)=a2, Y2(a8)=ag, on trouve: ê(a8,Y1(a8)) _ 0, ê(a8,Y2(a8)) = a13 - pour x4 = a9, sachant que Yl(a9)=a5, Y2(a9)=a1 , on trouve: ê(a9,Y1(a9)) = a6, e(a9,Y2(a9)) = a13 - pour x4 = a10, sachant que Yi(a10)=a, Y2(a10)=a4, on trouve: ê(a10,Y1(al ) =1, ê(a'',Y2(ai ) = ; pour x5 = a13, sachant que Y](a13)=a, Y2(a13)=a4, on trouve: e(a13, Y1(a13)) = a2, ê(a13, y2(a13)) = 0 On peut vérifier la justesse de ces résultats de diverses manières. 25 et Par exemple, on constate que les agrégats étiquetés par x1 = a2 et x4 = a9comprennent deux composantes erronées, cependant que les autres agrégats erronés ne comprennent qu'une seule composante erronée; autrement dit, dans la notation introduite ci-dessus, d'une part s(xl) = E(x4) = 2, et d'autre part S(X2)=E(X3)=e(X5)=l. Or, comme expliqué ci- dessus, les valeurs x, de X qui étiquettent les agrégats tels que c(x ) = 2 coïncident avec les racines du polynôme D * (X) . En effet, on vérifie facilement que les racines de D*(X)=a2X2+a13X+a13 sont bien a2 et a9. On peut également vérifier, en utilisant les coordonnées (indiquées cidessus) des points de la courbe algébrique appartenant à des agrégats erronés, que le mot ê dont certaines composantes sont données ci-dessus et les autres sont nulles, est, comme souhaité, tel que s; _ h1 ê) pour toutes les composantes s; du vecteur de syndromes d'erreurs données en (7) . On trouve donc finalement: 7'=r ê= 0; autrement dit, selon l'estimation, le mot de code envoyé se trouve être, en l'occurrence, le mot nul. Le schéma synoptique de la figure 2 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 2 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 10 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, - un registre mots associés , dans lequel sont conservés les 20 symboles des mots de code associés , 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 25 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 - les coefficients des polynômes uo(X) et u1(X) figurant dans l'équation (1) représentant la courbe hyperelliptique, dans des registres uo et ul . 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 oeuvre 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 5 mot reçu r appliqué au décodage pour un code défini sur une courbe hyperelliptique représentée par une équation du type Y2 +Yul (X) +uo(X) =0, définie sur un corps de Galois dont le cardinal q est égal à une puissance de 2 et est supérieur à 2, procédé dans lequel on calcule une base de Grôbner ç associée au mot reçu r, ledit procédé étant caractérisé en ce que, lorsque l'idéal de Grôbner associé à r ne comprend pas de polynôme ne dépendant que de la variable X, il comprend les étapes suivantes: - on obtient un polynôme z(X) qui est égal à z(X) =uo(X)[ai(X)] 2 ut(X)at(X)ao(X)+[ao(X)]2 si ladite base de Grôbner ç ne contient qu'un élément Gl (X, Y) = ao (X) + Yal (X) , 15 et qui est égal à z(X) = ao (X) bl (X) al (X)bo (X) si ladite base de Grôbner ç contient deux éléments Gl (X, Y) = ao (X) + Val (X) et G2(X,Y) =bo(X)+Ybl(X), - on calcule la dérivée z'(X) de z(X), - on calcule le plus grand commun diviseur D(X) de z(X) et z'(X), qui est de la forme D(X) = di X 2, et - on calcule le polynôme A(X) _ z(X) D*(X) ' où D *(X) = E.dlq/2 XI 2. Procédé de localisation d'agrégats erronés selon la revendication 1, caractérisé en ce que l'on obtient l'ensemble des valeurs de X étiquetant les agrégats erronés dudit mot reçu r en calculant les racines dudit polynôme A(X). 3. Procédé de localisation d'agrégats erronés selon la revendication 1 ou la revendication 2, caractérisé en ce que l'on obtient l'ensemble des valeurs de X étiquetant les agrégats contenant exactement deux composantes erronées dudit mot reçu r en calculant les racines dudit polynôme D * (X) ou dudit polynôme D(X). 4. Dispositif (107) de localisation d'agrégats erronés de composantes d'un mot reçu r appliqué au décodage pour un code défini sur une courbe hyperelliptique représentée par une équation du type Y2 +Yu,(X)+uo(X) = 0, définie sur un corps de Galois dont le cardinal q est égal à une puissance de 2 et est supérieur à 2, comprenant des moyens pour calculer une base de Grôbner g associée au mot reçu r, ledit dispositif étant caractérisé en ce qu'il comprend également des moyens pour, lorsque l'idéal de Grôbner associé à r ne comprend pas de polynôme ne dépendant que de la variable X: - obtenir un polynôme z(X) qui est égal à z(X) =uo(X){ai(X)]2 u1(X)a1(X)ao(X)+{ao(X)]2 si ladite base de Grôbner g ne contient qu'un élément Gl (X, Y) = ao (X) + Yal (X) , et qui est égal à z(X) = ao (X)b1 (X) al (X)bo (X) si ladite base de Grôbner g contient deux éléments Gl (X, Y) = ao (X) +Ya (X) et 20 G2 (X, Y) = bo (X) + Ybl (X) , - calculer la dérivée z'(X) de z(X) , - calculer le plus grand commun diviseur D(X) de z(X) et z'(X), qui est de la forme D(X) = Ei di x 2i, et - calculer le polynôme A(X) = z(X) D*(X) ' où D*(X)= idigl2Xi 5. Dispositif de localisation d'agrégats erronés selon la revendication 4, caractérisé en ce qu'il comprend également des moyens pour obtenir l'ensemble des valeurs de X étiquetant les agrégats erronés dudit mot reçu r en calculant les racines dudit polynôme A(X). 6. Dispositif de localisation d'agrégats erronés selon la revendication 4 ou la revendication 5, caractérisé en ce qu'il comprend également des moyens pour obtenir l'ensemble des valeurs de X étiquetant les agrégats contenant exactement deux composantes erronées dudit mot reçu r en calculant les racines dudit polynôme D * (X) ou dudit polynôme D(X). 7. Décodeur (10), caractérisé en ce qu'il comprend: - au moins un dispositif de localisation d'agrégats erronés selon l'une 10 quelconque des revendications 4 à 6, et - au moins une unité de suppression de la redondance (108). 10. Appareil de réception de signaux numériques codés (70), caractérisé en ce qu'il comprend un décodeur selon la revendication 7, et en ce qu'il comprend des moyens (106) pour démoduler lesdits signaux numériques codés. 11. Système informatique (70), caractérisé en ce qu'il comprend un décodeur selon la revendication 7, et en ce qu'il comprend en outre: - au moins un disque dur, et - au moins un moyen de lecture (105) de ce disque dur. 10. Moyen de stockage de données inamovible, caractérisé en ce qu'il comporte des instructions de code de programme informatique pour l'exécution des étapes d'un procédé de localisation d'agrégats erronés selon l'une quelconque des revendications 1 à 3. 11. Moyen de stockage de données partiellement ou totalement amovible, caractérisé en ce qu'il comporte des instructions de code de programme informatique pour l'exécution des étapes d'un procédé de localisation d'agrégats erronés selon l'une quelconque des revendications 1 à 3. 12. Programme d'ordinateur, caractérisé en ce qu'il contient 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 un procédé de localisation d'agrégats erronés selon l'une quelconque des revendications 1 à 3.