FR2866998A1

FR2866998A1 - Decodage et correction d'erreurs pour codes de geometrie algebrique

Info

Publication number: FR2866998A1
Application number: FR0402033A
Authority: FR
Inventors: Philippe Piret; Frederic Lehobey; Bars Philippe Le
Original assignee: Canon Inc
Current assignee: Canon Inc
Priority date: 2004-02-27
Filing date: 2004-02-27
Publication date: 2005-09-02
Anticipated expiration: 2024-02-27
Also published as: US20050204268A1; FR2866998B1; US7502988B2

Abstract

La présente invention concerne un procédé de décodage d'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 de degré b en X et de degré a en Y, ledit procédé comprenant, pour tout mot reçu, une étape de localisation des erreurs de transmission affectant ce mot reçu. L'invention ramène ensuite la correction d'erreurs dans ce mot, qui appartient à un code de géométrie algébrique, à la correction d'erreurs dans un certain nombre, au plus égal à a, de mots appartenant à un code de Reed-Solomon.L'invention concerne également les dispositifs et appareils destinés à mettre en oeuvre ce procédé.

Description

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 décodage, 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, quand on forme les mots de code envoyés à un récepteur ou enregistrés sur un support de données, à introduire une certaine redondance dans les données.

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 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 = (vl,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.

Lorsque la taille q de l'alphabet est une puissance d'un nombre premier, on peut donner à cet alphabet une structure de corps, dit corps de Galois , noté Fg, dont les éléments non-nuls peuvent être commodément identifiés comme étant chacun égal à y pour une valeur correspondante de i, où i = 1,..., q -1, et où y est une racine (q -1)ème primitive de l'unité dans Fq.

En particulier, 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, ê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. Au niveau du récepteur, le procédé de décodage associé exploite alors judicieusement cette redondance pour détecter d'éventuelles erreurs de transmission et si possible les corriger. 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.

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é . 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 -ê) soit un mot de code, qui constituera alors le mot de code associé . 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. Dans la situation idéale où toutes les erreurs de transmission ont été corrigées, on retrouve ainsi les symboles d'information initiaux.

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, la distance de Hamming étant, par définition, le nombre d'emplacements où deux mots de même longueur possèdent un symbole différent. On appelle distance minimale d d'un code la plus petite distance de Hamming entre deux mots différents de ce code. C'est un paramètre important du code. Plus précisément, il est en principe possible de trouver 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). Dans tous les cas toutefois, il ne s'agit que d'une possibilité de principe, car il est souvent difficile 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 + l). La matrice de parité H du code de Reed-Solomon de dimension k et de longueur n (où n est nécessairement égal à (q -1) ou à un diviseur de (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 HJ = a '-') (1 i 5 n - k, 1 j 5 n), où a est une racine n ème de l'unité dans Fq; on peut alors étiqueter la composante vi, où 1 <- , de tout mot de code v = (v1,v2, ...,vn) au moyen de l'élément a('-') de Fq; c'est pourquoi un ensemble tel que (1,a,a2,...,an-') est appelé ensemble de localisation ( locating set en anglais) du code de Reed-Solomon. On peut également, pour certains besoins particuliers, définir des codes de Reed-Solomon étendus ou raccourcis de longueur différente des longueurs normales que l'on vient de mentionner. Enfin, on peut modifier les codes de Reed-Solomon de la façon suivante: on choisit une matrice diagonale P de type n x n, dont tous les éléments diagonaux sont non-nuls, et on définit la matrice H p = H É P, où H est la matrice de parité pour code de Reed-Solomon standard définie ci-dessus; un mot appartient à ce code modifié Si, et seulement si, il est orthogonal à Hp; les propriétés d'un tel code modifié sont essentiellement les mêmes que celles du code standard d'origine.

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 en deux sous-étapes: la première sous-étape est une étape de localisation d'erreurs servant à identifier dans le mot reçu les composantes dont la valeur est erronée; 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, on utilise habituellement, en ce qui concerne la localisation d'erreurs, l'algorithme dit de Berlekamp-Massey que l'on va décrire sommairement: 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 =HeT; on cherche ensuite un vecteur A tel que A. S =0, puis l'on forme un polynôme 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 la correction d'erreurs, on utilise habituellement 20 l'algorithme dit de Forney , que l'on va décrire sommairement. On construit le polynôme de calcul d'erreurs S(Z) = A(Z)S(Z) modulo Zn-k, où n-k-I S(Z) _ Es,Z' et les s; sont les composantes du vecteur de syndromes d'erreurs s; les erreurs sont alors données, pour i =1,...,n, par: 0 si A(wl1) 0 Q(coi-l) si A(col) =0 p.A'(wT') où A'(Z) désigne la dérivée de A(Z), et p, est égal à 1 pour un code de Reed-Solomon standard et à l'élément diagonal en position (i,i) de la matrice P pour un code modifié (voir ci-dessus).

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 error-5 control 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 15 mots de code de grande longueur, on doit envisager de grandes valeurs de q, ce qui conduit à des mises en uvre 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 , 1 ère partie, IMA Volumes Math. Appl., volume 21, Springer-Verlag, Berlin, 1990). Ces codes sont construits à partir d'un ensemble de n couples (x, y) 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 Pj (où j =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+2g-M, qui peut être très élevée; par exemple, avec une taille d'alphabet égale à 256 et un genre égal à 120, on obtient des mots de code de longueur 4096.

Dans le cadre de la présente invention, on s'intéresse à une classe très générale de codes de géométrie algébrique: ces codes, dont on trouvera un exemple décrit en détail ci-dessous, sont définis sur une courbe algébrique représentée par une équation f(X,Y) = 0 avec f (X, Y) = X b + cYa + E cuX'Y' où c 0 et les cil 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 < ab. Cette forme d'équation est dite C(a,b) . Pour un tel code, on définit classiquement une matrice de parité de la manière suivante. A tout monôme Y'X u, où t et u sont des entiers positifs ou nuls, on associe un poids (voir détails plus bas). Si, pour un entier p 0, il existe au moins un monôme dont le poids est p, on dit que p est un poids réalisable . Soient Pl <P2 < < Pn-k les (n - k) plus petits poids qui sont réalisables, et soit hi (où i =1,..., n - k) un monôme de poids pi. L'élément en ligne i et colonne j de la matrice de parité est égal au monôme hi évalué au point Pi (où, rappelons-le, j =1,...,n) de la courbe algébrique. Chaque point Pj sert alors à identifier la j è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 Pi) des fonctions (les monômes hi) qui n'ont de pôles qu'en un seul point, à savoir le point à l'infini.

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 Hoholdt et Ruud Pellikaan intitulé On the Decoding of Algebraic-Geometric Codes , IEEE Trans. Inform. 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. Inform. 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 S1, 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 SIS au-delà de la frontière restant indéterminés; b) on considère le système d'équations linéaires Z S1 = 0, pour j =1,2,..., w(/3) , i_I où les inconnues ll appartiennent au même alphabet de symboles que les éléments des mots de code, et où /3 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ù 30 les coefficients li ne sont pas tous nuls), et l'on détermine les valeurs de ces coefficients l; correspondant à la plus petite valeur possible de,B, que l'on notera 2; et c) on calcule les zéros du polynôme de localisation d'erreurs A(x,y) = lt h1(x,y) , i=1 ces zéros comprenant tous les couples (x, y) correspondant à des positions du mot reçu pour lesquelles la composante en cette position a 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 10 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 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. Inform. 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 a été divulgué par M. O'Sullivan dans l'article A Generalization of the Berlekamp-MasseySakata Algorithm (preprint 2001).

Pour tout mot reçu r, on appelle idéal de Grôbner associé aux erreurs de transmission affectant ce mot, l'ensemble des polynômes de localisation d'erreurs définis plus haut. On peut engendrer cet idéal de Grôbner au moyen d'un ensemble fini de polynômes qui constitue ce que l'on appelle une base de Grôbner de l'idéal. L'algorithme de O'Sullivan que l'on vient de citer produit une telle base de Grôbner à partir d'une matrice S*, de dimension 2866998 9 n x n, obtenue en étendant la matrice S (autrement dit, les éléments de S et ceux de S* sont identiques pour j < w(i) avec i s n - k). Cette extension est possible à chaque fois que le nombre d'erreurs dans le mot reçu est inférieur ou égal à (n-k-g)12.

En effet, lorsque le nombre d'erreurs dans le mot reçu est inférieur ou égal à (n - k - g)l2, 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. Inform. 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 20 une base de Grôbner à partir de la matrice S* ainsi obtenue.

A ce stade, il est également possible de calculer des éléments inconnus supplémentaires de la matrice 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 Sakata et al. cité ci-dessus.

Dans le cadre de la présente invention, on dira que les éléments de la matrice des syndromes S* ( connus ou inconnus ) sont des 30 syndromes d'erreurs étendus .

L'invention concerne plus particulièrement la sous-étape consistant à calculer la valeur corrigée des composantes erronées du mot reçu; elle concerne donc les algorithmes aptes à fournir une valeur 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 localisation d'erreurs (noté ci-dessus A(Z) ), 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 donc des dérivées partielles par rapport à ces deux variables, de sorte que la formule de Forney donnée ci-dessus, qui fait intervenir une dérivée unique, n'est plus applicable.

On connaît divers algorithmes de calcul des erreurs pour codes de géométrie algébrique.

L'article Algebraic Geometry Codes , de Tom Hrholdt, 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. II 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), et 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) calculent les valeurs des erreurs en évaluant un polynôme à deux variables en les zéros communs des polynômes de localisation d'erreurs.

Ces trois algorithmes sont complexes à mettre en oeuvre, notamment du fait qu'ils comprennent la multiplication de polynômes à deux variables, en plus de multiplications formelles dans Fq.

On connaît un algorithme plus simple d'après l'article A Forney type formula for the determination of error values for Hermitian codes de Ralf Kôtter (Algebraic Decoding of Algebraic Geometry and Cyclic Codes, dissertation n 419, Linkoping Studies in Science and Technology,1996). Mais cet algorithme s'applique uniquement au cas des codes construits sur une courbe hermitienne (c'est-à-dire une courbe représentée par l'équation Y +Y = Xdéfinie sur Fq, où q est un carré parfait).

La demande de brevet européen n 03293336.8 au nom de CANON divulgue un procédé de décodage adapté notamment aux codes de géométrie algébrique à un point définis sur une courbe algébrique de type C(a,b) (voir cidessus), et qui effectue à la fois la localisation et la correction d'erreurs.

Ce procédé 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 ayant une valeur commune de x; ces couples seront notés (x,yp(x)), où p = 0, 1(x) - 1 et 2(x) est le cardinal de l'agrégat considéré (naturellement, on pourrait tout aussi bien définir les agrégats et décrire le procédé de décodage selon l'invention, en échangeant les rôles des inconnues X et Y de l'équation représentant la courbe algébrique sur laquelle est définie le code). Les composantes de tout mot c de longueur n seront alors notées c(x, y p (x)) lorsque l'on souhaite faire apparaître cette structure en agrégats, et on dira que 25 les composantes de c, indexées de la sorte, qui possèdent la même valeur de x forment un agrégat de composantes du mot c.

Soit m le poids maximal des monômes définissant les lignes de la matrice de parité (voir ci-dessus). Selon la demande n 03293336.8, on classe ces monômes dans des ensembles de monômes T(j)={Y'X(0<_i<_(m bj)/a} 2866998 12 pour j 0, j < a, et j (m/b) . L'ensemble T(j) a donc pour cardinal: t(j) =1 + INT [(m bj) / aJ, et la valeur maximale de j, notée jmax, vérifie: Jmax n k= t( j) . j=0 Notons par xl,x2,...,x les différentes valeurs de x dans l'ensemble de localisation, et par y = [ v(xl, .vo (xl)) , ..., v(x1, y, 1(x1)),..., v(x, y, (xv)) l un mot de code quelconque. On construit, pour chaque agrégat attaché à l'une des valeurs xi de x, (jmax +1) symboles agrégés 2(x) 1 r v1(x) [yp (x)] v(x, yp (x)) p=o pour j = 0,..., jmax. Ces symboles agrégés servent à former (Jmax +1) mots agrégés VJ -[V.] (xl),VJ(x2),...,VJ(xp)} , de longueur t.

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 Umm +1) équations: H'(J) .v T =0 où la fonction t(j) est donnée ci-dessus et, par définition, Ht = t-1 t-1 t-1 xl X2 xu L'intérêt de cette formulation est que cette matrice Ht de l'équation est une matrice de Vandermonde définie sur Fq; par conséquent, si on considère H J) comme une matrice de parité définissant des mots de code v, , il s'agit, pour chaque valeur de j, d'un code de Reed-Solomon, pour lequel on connaît des algorithmes de décodage aussi simples que performants. Par exemple, un mot r ayant été reçu, on calcule d'abord, pour j = 0,..., j,nax, les mots reçus agrégés r _j = [ r j (x1), rj (x2),..., r. (xp) ] dans lesquels, pour x = xl, x2,..., x , les symboles reçus agrégés rj (x) sont donnés par (x)-1 ri (x) E [Y p (x)]' r(x,.y p (x)) ; p=0 puis on utilise l'algorithme de Berlekamp-Massèy pour la localisation des 10 symboles erronés de chaque mot rj, suivi de l'algorithme de Forney pour la correction de ces symboles erronés, d'après le vecteur de syndromes d'erreurs sj = Ht(j)r T Ainsi, au cours des étapes de localisation d'erreurs dans le procédé selon la demande n 03293336.8, on localise des agrégats erronés associés au mot reçu, et non des composantes individuelles erronées du mot reçu. De ce fait, le nombre d'erreurs que l'on peut corriger avec ce procédé peut être inférieur à la capacité de correction d'erreurs théorique du code (comme expliqué ci-dessus, cette capacité théorique est égale à INT[(d -1)/2], où d est la distance minimale du code de géométrie algébrique considéré).

Le besoin se fait donc sentir d'un algorithme de correction d'erreurs qui soit à la fois relativement simple à mettre en oeuvre, applicable à tous les codes de géométrie algébrique (du moins, à tous ceux appartenant à la classe très générale des codes à un point définis sur une courbe algébrique de type C(a,b) ), et capable de corriger tout mot reçu comprenant un nombre d'erreurs inférieur ou égal à la capacité théorique du code.

L'invention concerne donc, selon un premier aspect, un procédé de décodage d'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 de degré b en X et de degré a en Y, ledit procédé comprenant, pour tout mot reçu L, une étape dans laquelle on identifie chaque point (x, y) de l'ensemble de localisation du code tel que la composante dudit mot reçu r étiquetée par ce point soit erronée. Ce procédé est remarquable en ce qu'il comprend ensuite les étapes suivantes (où la notation (c1 Ic2) représente le produit scalaire de deux mots çi et ç2 de longueur n) : - on compte le nombre 1 de valeurs différentes de x apparaissant dans ces points associés à des composantes erronées der, chacune de ces valeurs de x définissant un agrégat erroné dont les éléments sont tous les 2(x) points (x, y p (x)) , où p = 0,..., 2(x) -1, de l'ensemble de localisation correspondant à cette valeur de x, - on calcule, pour i -0,...,21-1 et j = 0,..., 2,a, -1, où 2max est la valeur maximale des cardinaux 2(x) des agrégats erronés, les syndromes d'erreurs étendus 6j (i) = (Y'X, 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 15 monôme Y1X aux points de l'ensemble de localisation, - on met en oeuvre, pour j= 0,...,maX -1, au moyen du polynôme de syndromes d'erreurs 21-1 S (Z) = (i)Z' i=o un algorithme de correction d'erreurs adapté aux codes de Reed-Solomon, demanière à calculer les erreurs Ei(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 1 valeurs de x associées à un 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 erreurs respectives sur les composantes r(x, y p (x)) , où p = 0,

., 2(x) -1, de r en résolvant le système d'équations À(x) 1 Ei (x) = E [y p (x)P ê(x, y p (x)) , où j = 0,...,2(x) -1 p=o Ainsi, le procédé selon l'invention comprend le calcul de l'erreur Â(x) 1 Ei (x) sur le symbole reçu agrégé ri (x) _ E [y p (x)}'r(x, y p (x)) mentionné ci- p=o dessus. Grâce à ces dispositions, l'invention ramène essentiellement la correction d'erreurs dans un mot appartenant à un code de géométrie algébrique à la correction d'erreurs dans 2max mots appartenant à un code de Reed-Solomon; autrement dit, les inventeurs sont parvenus à remplacer un problème complexe, car faisant intervenir des polynômes à deux variables, par un problème plus simple faisant intervenir des polynômes à une seule variable...DTD: Mais contrairement au procédé selon la demande n 03293336.8, la présente invention ne cause aucune perte en termes de capacité de correction d'erreurs par rapport à la capacité théorique du code, car, d'une part, l'algorithme selon invention n'est mis en oeuvre qu'après que la localisation d'erreurs ait été effectuée de manière classique (c'est-à- dire après identification de chaque point (x,y) de l'ensemble de localisation du code tel que la composante dudit mot reçu r étiquetée par ce point soit erronée), et d'autre part l'algorithme selon invention utilise les syndromes d'erreurs étendus classiques, et non des syndromes d'erreurs obtenus à partir de mots agrégés.

Par rapport, maintenant, 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 de l'invention 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) 2max fois, et de résoudre pour chaque agrégat erroné étiqueté par une valeur x de X un système d'équations (1) de taille 2(x) ; on notera à cet égard que 2max est au plus égal à a, puisque a désigne, rappelons-le, l'exposant de Y dans l'équation représentant la courbe algébrique.

On notera par ailleurs que le système d'équations (1) est un système de Vandermonde: il possède donc toujours une, et une seule, solution; de (1) 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.

Ainsi, lorsque le nombre d'erreurs de transmission affectant le mot reçu est inférieur ou égal à (n k-g)12, l'estimation fournie par le procédé selon l'invention fournit de manière certaine la valeur des erreurs de transmission.

Selon des caractéristiques particulières, s'il existe au moins une valeur de x associée à un agrégat erroné telle que 2(x) <a, on compare ensuite les membres d'au moins une équation 2(x)-I Ei (x) = E [yp (x)]' ê(x, yp (x)) , ou 2(x) S j < a -1, p=0 associée à ladite valeur de x, au besoin après avoir calculé Ej(x) au moyen d'un algorithme de correction d'erreurs adapté aux codes de Reed-Solomon.

Grâce à ces dispositions, on pourra détecter une éventuelle correction erronée au cas où ladite au moins une équation s'avère ne pas être vérifiée avec les valeurs de e(x,yp(x)) obtenues précédemment.

Selon d'autres caractéristiques particulières, ledit calcul des syndromes d'erreurs étendus (i) = (YJxi e) pour i = 0,...,21 1 et j = 0,...,max -1 comprend les sous-étapes suivantes: - on calcule, pour chaque valeur de j =0,...,max -1, un nombre de 20 syndromes d'erreurs étendus o-j(i) au moins égal audit nombre Z d'agrégats erronés, et - on calcule (s'il y a lieu) ceux parmi les syndromes d'erreurs étendus o- j (i) pour i = 0,...,21 1 et j = 0,...,2ma, -1 qui n'ont pas encore été obtenus, au moyen de relations de récurrence utilisant le polynôme localisateur d'erreurs en x A(Z)=fl(1-Zxt) , t=1 où les xt sont lesdites valeurs de x associées à un agrégat erroné.

Grâce à ces dispositions, on obtient (s'il y a lieu) certains des syndromes d'erreurs étendus requis pour les étapes suivantes du procédé selon l'invention, au moyen de relations de récurrence utilisant ledit polynôme A(Z), au lieu de procédés classiques tels que de nouvelles itérations d'un algorithme à décisions majoritaires ou, plus commodément, de récurrences utilisant des polynômes de rétroaction choisis dans la base de Grôbner. Comme A(Z) est un polynôme à une variable alors que les polynômes de l'idéal de Grôbner sont à deux variables, le présent mode de réalisation de l'invention permet de réduire de manière significative la complexité des calculs pour l'obtention de ces syndromes d'erreurs étendus.

Selon un second aspect, l'invention concerne divers dispositifs.

Elle concerne ainsi, premièrement, un dispositif de correction d'erreurs pour le décodage d'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 de degré b en X et de degré a en Y, ledit dispositif comprenant, pour tout mot reçu L, des moyens pour identifier chaque point (x, y) de l'ensemble de localisation du code tel que la composante dudit mot reçu r étiquetée par ce point soit erronée. Ce dispositif est remarquable en ce qu'il comprend également des moyens pour: - compter le nombre 1 de valeurs différentes de x apparaissant dans ces points associés à des composantes erronées de r, chacune de ces valeurs de x définissant un agrégat erroné dont les éléments sont tous les a, (x) points (x, y p (x)) , où p =0,...,2(x) 1, de l'ensemble de localisation correspondant à cette valeur de x, - calculer, pour i = 0,...,21 1 et j = 0,...,iîm -1, où ,i.max est la valeur maximale des cardinaux 2(x) des agrégats erronés, les syndromes d'erreurs étendus a1(0 = (Y-1X' e) , 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, - mettre en oeuvre, pour j =0,...,2m < -1, au moyen du polynôme de syndromes d'erreurs 21 1 sj(Z)=E6j(i)Z, t=o 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 1 valeurs de x associées à un agrégat erroné, et - calculer, pour chaque valeur de x telle qu'il existe au moins une valeur de j pour laquelle E1(x) est non-nulle, les estimations ê(x, y p (x)) des erreurs respectives sur les composantes r(x, y p (x)) , où p =0,.

,2(x) 1, de r en résolvant le système d'équations t(x) 1 Ej(x) [yp(x)] 'ê(x,yp(x)) , où j =0,...,2(x) -1. (1) p=o Ledit algorithme de correction d'erreurs pour code de Reed-Solomon peut être, par exemple, l'algorithme de Forney...DTD: Selon des caractéristiques particulières, le dispositif de correction d'erreurs comprend des moyens pour, s'il existe au moins une valeur de x associée à un agrégat erroné de cardinal 2(x)<a, comparer ensuite les membres d'au moins une équation t(x)-1 E1 (x) E [y p (x)] J ê(x, y p (x)) , où 2(x) < j S a -1, p=o associée à ladite valeur de x, au besoin après avoir calculé E j (x) au moyen d'un algorithme de correction d'erreurs adapté aux codes de Reed-Solomon. Selon d'autres caractéristiques particulières, le dispositif de correction d'erreurs comprend, pour effectuer ledit calcul des syndromes d'erreurs étendus a- j (i) = (Y'X' l pour i = 0,...,21 1 et j = 0,..., 2max -1, des moyens pour: - calculer, pour chaque valeur de j= 0,...,2n,u -1, un nombre de syndromes d'erreurs étendus 6) (i) au moins égal audit nombre 1 d'agrégats erronés, et - calculer (s'il y a lieu) ceux parmi les syndromes d'erreurs étendus 0-J(i) pour 1=0,...,21 1 et j = 0,..., 2max -1 qui n'ont pas encore été obtenus, au moyen de relations de récurrence utilisant le polynôme localisateur d'erreurs en x A(Z)=H(1 Zxt) t=1 où les xt sont lesdites valeurs de x associées à un agrégat erroné.

Les avantages de ces dispositifs de correction d'erreurs sont essentiellement les mêmes que ceux des procédés corrélatifs décrits succinctement ci-dessus.

L'invention concerne aussi, deuxièmement, un décodeur comprenant: - au moins un dispositif de correction d'erreurs tel que décrit succinctement ci-dessus, et - au moins une unité de suppression de la redondance.

L'invention vise également: - un appareil de réception de signaux numériques codés comprenant un 20 décodeur tel que décrit succinctement ci-dessus, ainsi que 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, et 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 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 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 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 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 utilisant un décodeur 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 utilisant un codage et décodage de canal 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 met ces informations sous la forme de symboles appartenant à un certain alphabet (par exemple des octets de bits), 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 (par exemple, une amplitude complexe). Ensuite, ces symboles de modulation sont transmis à un émetteur ou à un enregistreur 104, qui insère les symboles dans un canal de transmission. Ce canal peut être constitué par exemple d'une émission filaire ou non-filaire telle qu'un signal radio, ou par un stockage sur un support adapté tel qu'un DVD ou une bande magnétique. Cette transmission parvient à un récepteur ou à un lecteur 105, après avoir été affectée par un bruit de transmission dont l'effet est de modifier ou d'effacer, aléatoirement, certains des symboles de modulation.

Le récepteur ou lecteur 105 transmet alors ces symboles au démodulateur 106, qui les transforme en symboles de l'alphabet mentionné précédemment. 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.

On va à présent illustrer le procédé de correction d'erreurs selon l'invention à 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. II n'est fourni ici que pour permettre à l'homme du métier de comprendre plus facilement le fonctionnement du procédé selon l'invention.

Considérons donc un code de géométrie algébrique de dimension 42 et de longueur 60 défini comme suit.

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 = 6 constituée par l'ensemble des solutions (X = x,Y = y) de l'équation à deux inconnues Y4+ Y+XS=O (2) sur F16 (il s'agit ici d'une équation hermitienne, mais, comme on s'en rendra compte aisément, l'application de l'invention n'est nullement limitée à ce type d'équations algébriques). On constate qu'en donnant à x une valeur x quelconque dans F16, il existe à chaque fois 4 valeurs y(x) (p =1,2,3,4) dans F16 telles que le couple (x, y p (x)) soit solution de l'équation (2) ; ces solutions de l'équation (2) 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 à 60, et il peut être subdivisé en 15 agrégats qui ont chacun un cardinal 2(x) égal à 4. On rappelle que chaque point P. de l'ensemble de localisation sert à identifier le j -ème élément de tout mot de code; le nombre de tels points étant ici égal à 60, la longueur n du code est donc elle aussi égale à 60.

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 (l'image de cet espace de polynômes sur les points finis de la courbe représentée par l'équation (2) est donc un code de géométrie algébrique dit à un point ). Cet espace vectoriel, qui est de dimension supérieure ou égale à (m - g +1) (égale si m > 2g - 2), possède une base constituée par les monômes h1 = YX u, où t est un entier compris entre 0 et 3, u est un entier positif ou nul, 4u + 5t m, et i = 1,..., n - k. Cette quantité p(h1) = 4u + 5t est habituellement appelée le poids du monôme h. . Prenons par exemple: m=23; on obtient alors un ensemble de monômes h1 où i =1,...,18, puisque: m-g+1=23-6+1=18.

Les monômes hi peuvent être classés dans des sous-ensembles ordonnés de monômes M, = {YtXu J 0 <u <(23-5t)/4} , où : 0 t s 3. Ces sous-ensembles ordonnés de monômes sont explicitement: Mo = {1,X,X2,X3,X4,X5} M, = {Y,YX, YX2,YX3,YX4} , M2 = {Y2,Y2X,Y2X2,Y2X3} , et M3 = {Y3,Y3X,Y3X2} . On vérifie que le nombre total de monômes hi est bien égal à : 6+5+4+3 = 18.

Enfin, la matrice de parité H du code est définie de la manière suivante: l'élément en ligne i et colonne j de cette matrice est égal à la valeur prise par le monôme hi au point Pi de la courbe algébrique. Ainsi, n - k = 18, et donc k = 42. La distance minimale d de ce code est au moins égale à 10 n - k + 1- g =13. On peut donc corriger au moins INT[(13-1)/2] = 6 symboles ayant subi une erreur de transmission.

On va résumer à présent la manière dont, un code de géométrie algébrique ayant été choisi et un mot de code ayant été transmis, on construit, de manière classique, la matrice des syndromes S * pour le mot reçu correspondant.

Considérons les poids p(YX u) = 4u + 5t inférieurs ou égaux à (n + g).

Pour chaque valeur de poids accessible, on choisit un monôme YXu particulier. Les lignes et les colonnes de la matrice S * sont alors indexées par la série de monômes choisis, par ordre de poids croissant.

L'élément, noté 6r+T (u + v) , de la matrice S* situé à la ligne indexée par YtX u et à la colonne indexée par YzX' est pris égal à 6r+z (u + v) = (yt+rXu+v et Autrement dit, pour obtenir un élément de cette matrice, il faut calculer le produit scalaire de l'erreur e affectant le mot reçu par le mot dont les composantes sont égales à la valeur prise aux points de l'ensemble de localisation par le monôme 25 correspondant à cet élément de matrice.

Si le poids de ce monôme est inférieur ou égal à m, l'élément de matrice cherché est, compte tenu de l'équation algébrique (2) et de la séquence de monômes hi choisie pour la matrice de parité H, soit une composante s, _ (h, e} (où i =1,..., n k) du vecteur de syndromes d'erreurs s = H É eT (ainsi, dans notre exemple, (YX3 e) = s,o), soit une combinaison linéaire de composantes du vecteur de syndromes d'erreurs (ainsi, dans notre exemple, (y4 e)=(Yle)+(X)=57 + s6).

Les éléments de matrice ainsi obtenus sont ceux possédés en commun par les matrices de syndromes S et S* . Pour calculer les éléments de matrice de S* dont le poids p vérifie m < p < m + g', où g' est un entier compris entre g et 2g, on utilise un procédé itératif comprenant un certain nombre de décisions majoritaires , tel que l'algorithme de Feng-Rao mentionné ci- dessus. On peut 10 ensuite obtenir des éléments de matrice de S* de poids p > m+ g' à 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 de récurrences utilisant des polynômes de rétroaction choisis dans la base de Grôbner.

On va maintenant illustrer le procédé de correction d'erreurs selon l'invention au moyen d'un exemple numérique appliqué au code, présenté cidessus, de longueur 60 et de dimension 42 défini sur une courbe algébrique de genre g = 6 sur F16. Pour cela, choisissons comme élément primitif de F16 une racine a de l'équation Z4+Z+1=0.

Supposons que l'on reçoive un mot r produisant le vecteur de syndromes d'erreurs (à n k = 18 composantes) suivant: s = H.rT= [a2a2a6a2a13a7 a60 a3a13a a9a10a10a5 a8a8 0]T (3) Au moyen d'un algorithme à décisions majoritaires , on obtient les 2g =12 syndromes d'erreurs inconnus suivants: e)=0, 60(7)=(X' e)=a6, o0(8)=(X8 e)=a14 e)=a14, 61(6)=(YX6le)=a8, (Ti 7)=(YX7e)=a12 62 (4) = (Y2X4 e=a14 62(5)=1Y2X5 e=a, 0-2(6)=(Y2X6 0-3(3) = Y3X3 =0, 0-3(4)=Y3X4 e)=a9, a3(5)=(Y3X5 Dans ce cas, sur la base de ces 18+12 = 30 syndromes étendus , un algorithme de localisation d'erreurs (par exemple, l'algorithme de O'Sullivan cité ci-dessus) est à même de produire les trois générateurs suivants de l'idéal 5 de Grêbner: G1(X,Y) =a14X2 +a5YX+a2X + Y2 +a3Y+a6, G2 (X,Y) = a3X3 +YX2 +a14X2 +a14YX +X +a8Y+a6, et G3(X,Y) =X4 +a12X3 +a6YX2 +a7X2 +a3YX+a2X +Y+a4. Ces trois générateurs possèdent 6 zéros en commun: (1,a8),(a,a9),(a5,a3),(a7,a9),(a7,a13), et (a14,a14) qui étiquettent les composantes erronées du mot reçu r.

Jusque là, les calculs ont été conduits de manière classique. A ce stade, selon l'invention, on identifie les agrégats erronés , c'est-à-dire les agrégats dont au moins un élément est erroné : par inspection des positions d'erreurs que l'on vient de calculer, on constate que les agrégats erronés sont étiquetés par les 1= 5 valeurs de x suivantes: Xi =1, x2 = a, x3 = a 5, x4 =a', et x5 = a 14.

Ces agrégats sont de cardinal 4 (comme d'ailleurs, en l'occurrence, tous les agrégats de l'ensemble de localisation), et par conséquent 2max = 4.

Selon l'invention, on met en oeuvre à présent, pour chaque valeur de j allant de 0 à a-1=3, un algorithme apte à fournir la valeur des erreurs, par rapport à un certain mot d'un code de Reed-Solomon, dont la position dans ce mot est étiquetée par les 5 valeurs de x que l'on vient de déterminer. Naturellement, ce code de Reed-Solomon est supposé être défini sur F16 comme le code de géométrie algébrique considéré.

Pour ce faire, il est nécessaire de connaître la valeur des syndromes d'erreurs étendus o-1(i) = (YJX' e) pour i allant de 0 à 21-1= 9.

De manière classique, ceux parmi ces syndromes d'erreurs étendus qui n'ont pas encore été obtenus (on vérifie aisément qu'ils sont au nombre de 10) peuvent être calculés à l'aide des générateurs G1(X,Y) , G2 (X,Y) , et G3(X,Y) utilisés en tant que polynômes de rétroaction . Ce calcul est toutefois assez fastidieux.

Dans le présent mode de réalisation de l'invention, on utilise une méthode plus rapide pour calculer ces 10 syndromes d'erreurs étendus.

On constate que dans le cas présent on connaît, pour chaque valeur de j allant de 0 à 2max -1.3, la valeur d'un nombre de syndromes d'erreurs étendus o-. (i) au moins égal au nombre 1 d'agrégats erronés, à savoir 5 dans l'exemple considéré. On peut alors calculer les 10 syndromes d'erreurs étendus encore requis, par récurrence à l'aide du polynôme localisateur d'erreurs en x A(Z)= (1-Z)(1-aZ)(1-a5Z)(1-a7Z)(l-a14Z) =1+a10Z+a11Z2 +a5Z3 +Z4 +a12Z5, du type des polynômes localisateurs d'erreurs fournis par les algorithmes classiques (par exemple, l'algorithme de Berlekamp-Massey) adaptés aux codes de Reed-Solomon. Il est clair que la récurrence utilisant le polynôme à une variable A(Z) est beaucoup plus simple que la récurrence utilisant les polynômes à deux variables G1(X,Y) , G2 (X,Y) , et G3 (X,Y) . On obtient ainsi: 60(9)_ (X9 61(8)=(YX8 =a, e=a9,a1(9)=(YX9 62 (7) = (y2X7 63(6)=(y3X6 0-3(8) _ (Y3X8 e)=a12, 62(8)=(y2X8 e}=0, 63(7)_(Y3X7 e}=0,63(9)=(y3x9 eI =as,62(9)=(Y2X9Ie)=a13, Ç_) a14 e)=a'.

Selon l'invention, on forme ensuite les polynômes de syndromes d'erreurs S1(Z)=a1(i)Z' (puisque 21 1= 9) . t=o Pour la correction des erreurs Ei(x) affectant un mot de code de Reed-Solomon, on peut par exemple faire appel à l'algorithme de Forney, qui utilise les polynômes de calcul d'erreurs S2i(Z) = A(Z)Si(Z) modulo Z10 (puisque 21 =10) pour j =0,1,2,3. Compte tenu des syndromes étendus obtenus ci-dessus, ces polynômes sont explicitement les suivants: S (Z)=a2 +a2Z+a6Z2 +a13Z4 +a'Z5 +a6Z' +a14Z8 + aZ9, no(Z)= a2 +a7Z+a11Z2 +a14Z4, Sl(Z)=a6 +a3Z2 +a13Z3 +aZ4 +a14Z5 +a8Z6 +a'2Z' +a11Z8, S21(Z)=a6 +aZ+a6Z2 +a"Z3 +aZ4, S2(Z)=a9 +a10Z+a11Z2 +a5Z3 + a14Z4 +aZ5 +aZ6 +a12Z7 +a8Z8 +a13Z9, û2(Z)= a9 +a2Z+a10Z2 +a8Z3 +a12Z4, S3(Z)= a8 +a8Z+a9Z4 +a14Z' +a'Z9, et Q3(Z)=a8 +a13Z+a7Z2 +a11Z3 +aZ4 Enfin, l'algorithme de correction d'erreurs pour j = 0 donne: E (1) = 1 x SZ (1)/ A'(1) = a', E (a) = aç2 (a-1)/ A'(a-1) = 1, E (a5) = a5Q0(a5)/A'(a-5) = a, E (a') = a'SZ (a-')/A'(a-') = a9 E04'4) = a14Q0(a-14) /A'(a-14) = a5; l'algorithme de correction d'erreurs pour j =1 donne: E1(1) = lx Q1(1)/ A'(1) = 1, El (a) = aS21(a-1)/Ar(a-1) = a9, El(a5) = a5Q1(a-5)/A'(a-5) = a4, El(a') = a'Q1(a-2)/A'(a-2) = a10, El(ala) a'4Q1 (a-14)/A'(a-14) a4 l'algorithme de correction d'erreurs pour j = 2 donne: algorithme de correction det erreurs pour j = 3 donne: E3 (1) = 1 x S23 (1)/ A'(1) = a, E3(a) = aS23(a-1)/A'(a-1) = a12, E3(a5) = a5S25(a-5) /A'(a-5) = a10, E3(a') = a'Q3(a-')/A'(a-') = a' E3 (a14) = a14S23(a-14) /A1(a-14) = a2 La dernière étape du procédé selon l'invention consiste à regrouper les résultats ci-dessus agrégat par agrégat, et à résoudre le système d'équations (1) (de dimension 4) pour chaque agrégat: - pour x1 =1, sachant que Yo(1)= a,Yt(1)= a2,y2(1)= a4,y3(1)= a8, on trouve: ê(l, Yo (1)) = 0, ê(l, y1(1)) = 0, ê(l, Y2 (1)) = 0, ê(l, Y3 (1)) = a ' - pour x2 = a, sachant que yo(a)= a6,Y1(a)= a7,y2(a)= a9,Y3 (a)= a13 on trouve: ê(a, yo (a)) = 0, ê(a, y1 (a)) = 0, ê(a, y2 (a)) =1, ê(a, y3 (a)) = 0; - pour x3 = a' , sachant que Yo(a5)=a3,Y1(a5)-a",y2(a5)=a12,Y3(a5)=a14, on trouve: e(a5,yo(a5)) = a, e(a5,y1(a5)) = 0, ê(a5,Y2(a5)) = 0, ê(a5,Y3 (as)) = 0; - pour x4 = a' , sachant que E2 (a) = aS22(a 1)/A'(a l E2(as) = a5S22(a-5) /A'(a-5) E2(a') = a7ç 2(a-')/A'(a-') E2 (a14) = at4S214(a-14)/A'(a-14) E2 (1) = 1 x ç22 (1)/ A'(1) a8 = a3, = a', = a2, = a3; Yo(a=a6Yl(a=aY2(a=a9, Y3(a =al3, on trouve: êta' ,Yo(a'))=0,êta' ,Yl(a'))=0,ê(a',Y2(a'))=a11,êta' ,Y3(a'))=a2 et - pour x; =a14, sachant que y (a14)= a3,Yl (a14)= a11,Y2(a14)= a12, Y3(a14)= a14, on trouve: J ê(a14,YO(a14)) = 0, ê'(a14,Yl (al4)) = ê(a14,Y2 (al4)) = O, ê(a14,Y3(al4)) = a3 En utilisant fes coordonnées, indiquées ci-dessus, des points de la courbe algébrique appartenant à des agrégats erronés, on peut vérifier facilement que le mot ê dont certaines composantes sont données ci-dessus et les autres sont nulles, est, comme souhaité, tel que s1 = Khi pour toutes les composantes s, du vecteur de syndromes d'erreurs données en (3) .

On notera que dans l'exemple numérique ci-dessus, après avoir 15 effectué 2g itérations de l'algorithme à décisions majoritaires , on connaît, pour tout j, la valeur des 1 syndromes d'erreurs étendus ff.(i) pour i allant de o à 1-1=4. On a donc pu, dans cet exemple, directement enchaîner cette étape du décodage avec fe calcul selon ce mode de réalisation de ['invention (c'est-à-dire par récurrence à l'aide du polynôme à une variable A(Z)) des autres syndromes d'erreurs étendus requis. Mais il n'en est pas toujours ainsi: en effet, il peut se produire, pour certains mots reçus, qu'après lesdites 2g itérations, on n'obtienne pas un nombre suffisant (à savoir, un nombre 1 pour chaque valeur de j) de syndromes d'erreurs étendus pour pouvoir directement mettre en oeuvre la récurrence à l'aide du polynôme à une variable A(Z) ; dans de tels. cas, il faudra calculer le(s) syndrome(s) d'erreur(s) étendu(s) manquant(s) pour atteindre ledit nombre suffisant, au moyen, par exemple, de l'algorithme à décisions majoritaires ou de récurrences utilisant les polynômes de rétroaction à deux variables.

Le schéma synoptique de la figure 2 représente un appareil de réception de signaux numériques 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: - ledestinataire 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, - un registre mots associés , dans lequel sont conservés les 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 conservent: le programme de fonctionnement de l'unité centrale de traitement 700, dans un registre programme , - la longueur de chaque mot de code dans un registre n , - le nombre de symboles d'information dans chaque mot de code, dans un registre k , et - une table contenant chaque mot Y'X' dont les composantes sont égales à la valeur prise par le monôme Y'X' aux points de l'ensemble de localisation, pour i =0,...,2L -1 et j = 0,...,Amax -1, où L est le nombre total d'agrégats et Amax est la taille d'agrégat maximale, dans un registre W .

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 pourrait par exemple être un récepteur adapté à mettre en oeuvre un protocole de transmission de données par paquets sur un canal hertzien.

Claims

32 REVENDICATIONS

1. Procédé de décodage d'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 de degré h en X et de degré a en Y, ledit procédé comprenant, pour tout mot reçu L, une étape d'identification de chaque point (x,y) de l'ensemble de localisation du code tel que la composante dudit mot reçu r étiquetée par ce point soit erronée, caractérisé en ce qu'il comprend ensuite les étapes suivantes: - on compte le nombre Z de valeurs différentes de x apparaissant dans ces points associés à des composantes erronées de L, chacune de ces valeurs de x définissant un agrégat erroné dont les éléments sont tous les 2(x) points (x, y y (x)) , où p = 0,..., 2(x) -1, de l'ensemble de localisation correspondant à cette valeur de x, - on calcule, pour i = 0,...,21 1 et j = 0,..., .m -1, où 2n,ax est la valeur m imale des cardinaux 2(x) des agrégats erronés, les syndromes d'erreurs étendus 61(i) _ (Y'X' I e) , où e est l'erreur de transmission affectant r et Y'X' iepré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= -1, au moyen du polynôme de syndromes d'erreurs 21-1 si g) = (i)z' 1=0 un algorithme de correction d'erreurs adapté aux codes de Reed-Solornon, de manière à calculer les erreurs E1(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 Z valeurs de x associées à un agrégat erroné, et - on calcule, pour chaque valeur de x telle qu'il existe au moins une valeur de.j pour laquelle E1(x) est non-nulle, les estimations ê(x, y1, (x)) des 2866998 33 erreurs respectives sur les composantes r(x, yl,(x)) , où p = 0,..., 2(x) -1, der en résolvant le système d'équations 2(x)-1ii Ej (x) _ E lyr (x)]J ê(x,yi,(x)) , où j = 0,...,2(x) -1.

2. Procédé de décodage selon la revendication 1, caractérisé en ce 5 que ledit algorithme de correction d'erreurs adapté aux codes de Reed-Solomon est l'algorithme dit de Forney .

3. Procédé de décodage selon la revendication 1 ou la revendication 2, caractérisé en ce que, s'il existe au moins une valeur de x associée à un agrégat erroné de cardinal 2(x)<a, on compare ensuite les membres d'au moins une équation 2(c)-1( E.(x) E Lyp (x)P (x, yP (x)) , où 2(x) S j 5 a -1, p=O associée à ladite valeur de x, au besoin après avoir calculé E1 (x) au moyen d'un algorithme de correction d'erreurs adapté aux codes de Reed-Solomon.

4. Procédé de décodage selon l'une quelconque des revendications 15 1 à 3, caractérisé en ce que ledit calcul des syndromes d'erreurs étendus 6J(i) = (YJX' e) pour i = 0,...,21-1 et j= 0,..., 2n,ax -1 comprend les sousétapes suivantes: - on calcule, pour chaque valeur de j = 0,...,2nm -1, un nombre de syndromes d'erreurs étendus oj(i) au moins égal audit nombre 1 d'agrégats erronés, et - on calcule (s'il y a lieu) ceux parmi les syndromes d'erreurs étendus c- 1(i) pour i= 0,...,21-1 et j = 0,...,21 -1 qui n'ont pas encore été obtenus, au moyen de relations de récurrence utilisant le polynôme localisateur d'erreurs en x A(Z)=JJ(1 Zx,) , !=1 où les x, sont lesdites valeurs de x associées à un agrégat erroné.
2866998 34 5. Dispositif (107) de correction d'erreurs pour le décodage d'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 de degré b en X et de degré a en Y, ledit dispositif comprenant, pour tout mot reçu r, des moyens pour identifier chaque point (x, y) de l'ensemble de localisation du code tel que la composante dudit mot reçu r étiquetée par ce point soit erronée, caractérisé en ce qu'il comprend également des moyens pour: compter le nombre 1 de valeurs différentes de x apparaissant dans ces points associés à des composantes erronées de r, chacune de ces valeurs de x définissant un agrégat erroné dont les éléments sont tous les 21. (x) points (x, y p (x)) , où p = 0,...,2(x) -1, de l'ensemble de localisation correspondant à cette valeur de x, - calculer, pour i -0,...,21 1 et j = 0,..., 2max -1, où 2max est la valeur maximale des cardinaux 2(x) des agrégats erronés, les syndromes d'erreurs 15 étendus o-; (i) = (Y'X1 le) , où e est l'erreur de transmission affectant r et représente le mot dont les composantes sont égales à la valeur prise par le monôme Y'X1 aux points de l'ensemble de localisation, - mettre en oeuvre, pour j= 0,..., 2max -1, au moyen du polynôme de syndromes d'erreurs 21-1 S(z) _ (i) Z, un algorithme de correction d'erreurs adapté aux codes de Reed-Solomon, de manière à calculer les erreurs E; (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 calculer, pour chaque valeur de x telle qu'il existe au moins une valeur de j pour laquelle E; (x) est non-nulle, les estimations ê(x, y p (x)) des erreurs respectives sur les composantes r(x, y p (x)) , où p = 0,

., 2(x) -1, de r en résolvant le système d'équations Ei(x) _ E [yn(x)] P'O ê(x, yp (x)) , où j = 0,...,2(x) -1...CLMF: 6. Dispositif de correction d'erreurs selon la revendication 5, caractérisé en ce que ledit algorithme de correction d'erreurs adapté aux codes 5 de Reed-Solomon est l'algorithme dit de Forney .

7. Dispositif de correction d'erreurs selon la revendication 5 ou la revendication 6, caractérisé en ce qu'il comprend des moyens pour, s'il existe au moins une valeur de x associée à un agrégat erroné de cardinal 2(x) <a, comparer ensuite les membres d'au moins une équation À.(x)-1 Ei (x) = E [yp (x)]i ê(x,yp (x)) , où .,(x) < j S a -1, p=o associée à ladite valeur de x, au besoin après avoir calculé Ei (x) au moyen d'un algorithme de correction d'erreurs adapté aux codes de Reed-Solomon.

8. Dispositif de correction d'erreurs selon l'une quelconque des revendications 5 à 7, caractérisé en ce que, pour effectuer ledit calcul des syndromes d'erreurs étendus 6i (i) _ (Y'X' l e pour i = 0,...,21-1 et j = 0,...,/L,a, -1, il comprend des moyens pour: - calculer, pour chaque valeur de j = 0,...,2n,at -1, un nombre de - sgrrdromes d'erreurs étendus o. ) au moins égal audit nombre l d'agrégats erronés, et - calculer (s'il y a lieu) ceux parmi les syndromes d'erreurs étendus 6i (i) pour i= 0,...,21-1 et j = -1 qui n'ont pas encore été obtenus, au moyen de relations de récurrence utilisant le polynôme localisateur d'erreurs en x A(Z)=fl(l Zx,) , r=1 où fes xt sont lesdites valeurs de x associées à un agrégat erroné.

9. Décodeur (10), caractérisé en ce qu'il comprend: - au moins un dispositif de correction d'erreurs selon l'une quelconque des revendications 5 à 8, 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 9, et en ce qu'il comporte 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 9, et en ce qu'il comprend en outre: 10 au moins un disque dur, et - au moins un moyen de lecture (105) de ce disque dur.

13. 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é selon l'une quelconque des revendications 1 à4.

14. 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é selon l'une quelconque des revendications 1 à 4.

14. 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é selon l'une quelconque des revendications 1 à 4.