Brevet FR2869482A1 — publié le 20051028

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 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 = (v1,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é Fq, 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)xn, 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é . Différentes méthodes ont déjà été proposées pour réaliser pratiquement cette première étape. Selon une première méthode possible, le décodeur calcule d'abord le vecteur de syndromes d'erreurs s = H É rT = H É eT de longueur (n - k) , puis détermine une valeur estimée ê de l'erreur e de telle sorte que (r.--ê_) soit un 10 mode de code. Le vecteur (r - ê) constitue alors le mot de code associé. Une méthode alternative pour réaliser la première étape consiste à rechercher tous les mots de code v qui sont situés à une distance de Hamming prédéterminée du mot reçu r. (On rappelle que la distance de Hamming est par définition le nombre de composantes où deux mots de même longueur possèdent un symbole différent.) Cette méthode est généralement dénommée décodage par liste ( //st decoding en anglais), puisque l'on obtient en général une liste de mots de code v qui répondent à cette définition. Selon les différents modes de mise en oeuvre envisageables, on pourra alors choisir le mot de code associé au mot reçu r parmi les mots de code de la liste au moyen d'un critère supplémentaire, ou bien considérer tous les mots de code ainsi obtenus dans la suite du traitement. La seconde étape consiste simplement à inverser le procédé de codage, ce qui permet d'obtenir la suite des k symboles initiaux (avant codage) si les erreurs de transmission ont été correctement corrigées. Lorsqu'on utilise une méthode de décodage par liste et qu'aucun choix parmi les différents mots de code de la liste n'a été effectué au préalable, on inverse le procédé de codage pour tous les mots de code de la liste et on obtient ainsi une pluralité de suites de k symboles possibles, parmi lesquelles on peut choisir celle qui vérifie un critère prédéterminé. 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. Un paramètre important dans la caractérisation d'un code est sa distance minimale d, qui peut être définie comme la plus petite distance de Hamming entre deux mots différents de ce 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) lorsqu'ils ne sont pas étendus. 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 H1 = a'1-1) (1 Il est par ailleurs connu qu'un tel code de Reed-Solomon peut être défini de manière équivalente comme suit: l'ensemble des mots du code de ReedSolomon est l'ensemble des mots (p(1), p(a), p(a2) ..., p(a -' )) lorsque p parcourt l'ensemble des polynômes de degré au plus (k -1) sur Fq. Pour le décodage des codes de Reed-Solomon, on utilise couramment l'algorithme dit de Berlekamp-Massey pour la localisation des erreurs et l'algorithme dit de Forney pour la correction des erreurs. Une alternative à ces méthodes, qui applique le décodage par liste aux codes de Reed-Solomon, a été proposée par M. Sudan dans son article Decoding of Reed Solomon Codes beyond the Error-Correction Bound , (Academic Press, 1997). Selon cet article, le problème du décodage par liste d'un mot reçu r = (r1, r2, ..., r ) revient à la recherche de l'ensemble des polynômes f de degré au plus (k -1) sur Fq qui génèrent un mot de code (f (1), f (a), f (a2) ..., f (a ^ )) situé dans un rayon ô du mot reçu r au sens de la distance de Hamming. Le problème du décodage par liste se ramène donc au problème 15 suivant: rechercher l'ensemble des polynômes f de degré au plus (k -1) sur Fq, pour lesquels le nombre de composantes i telles que f(a'-') = r, est au moins égal à (n-5). Il s'agit donc d'un problème d'interpolation puisque l'on recherche des polynômes f qui vérifient f (x) = y pour au moins (n-8) couples (x, y) . Pour résoudre ce problème d'interpolation de manière pratique, l'article de M. Sudan propose de rechercher un polynôme Q(X,Y) (où X et Y sont des éléments de Fq) qui s'annule en tout point (a'-',r;), pour i entre 1 et n, puis de factoriser le polynôme Q(X,Y) en facteurs irréductibles, afin de trouver des facteurs de la forme (y - f (x)) . Les fonctions f ainsi obtenues sont candidates à la solution du problème d'interpolation puisqu'elles vérifient r; - f(a'-') = 0 pour certaines valeurs de i au moins. Naturellement, la connaissance d'au moins un polynôme f solution du problème d'interpolation permet d'obtenir aisément le mot de code correspondant ( f (1), f (a), f (a2) ..., f (a -' )), qui peut donc être utilisé comme mot de code associé au mot reçu r. 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 10 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 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). 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. En général, 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 2869482 6 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 J), 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 contenant les codes de géométrie algébrique: ces codes, dont on trouvera un exemple décrit en détail ci-dessous, sont définis par une matrice de parité de la manière suivante. A tout monôme Y'X, où i et j sont des entiers positifs ou nuls, on associe un poids . 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 pi 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 est courant 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 + l - 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 T. Hoholdt et R. Pellikaan cité ci-dessus). 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. Comme pour les codes de Reed-Solomon, des méthodes de décodage d'un mot reçu r = (rl,r2, ...,rn) ont déjà été proposées qui utilisent un algorithme de localisation d'erreurs puis un algorithme de correction d'erreurs. Ce type de méthodes est par exemple décrit dans l'article de A. N. Skorobogatov et S.G. Vlàdut intitulé On the Decoding of AlgebraicGeometric Codes (IEEE Trans. Inform. Theory, vol. 36 n 5, pages 1051 à 1060, novembre 1990) pour la localisation d'erreurs et l'article A Generalized Forney Formula for Algebraic Geometric Codes , de Douglas A. Leonard (IEEE Trans. Inform. Theory, vol. 42, n 4, pages 1263 à 1268, juillet 1996) pour la correction d'erreurs. Ces algorithmes sont en général complexes à mettre en oeuvre, notamment du fait qu'ils comprennent la multiplication de polynômes à deux variables, en plus de multiplications formelles dans Fq. Pour essayer de bénéficier des avantages propres au décodage de liste, il a été proposé d'appliquer la méthode de décodage par liste aux codes de géométrie algébrique. Les principes de cette méthode de décodage sont décrits dans l'article Improved Decoding of Reed-Solomon and AlgebraicGeometry Codes de V. Guruswami et M. Sudan (IEEE Trans. Inform. Theory, vol. 45, n 6, septembre 1999). Une méthode de décodage par liste qui reprend ces principes et précise les techniques d'interpolation utilisées est par ailleurs décrite dans l'article Decoding Hermitian codes with Sudan's algorithm de T. Hoholdt et R. Refslund Nielsen (Applied Algebra, Algebraic Algorithm and Error Correcting Codes Lecture notes in computer science, Springer Verlag 1999). Par analogie avec la méthode d'interpolation utilisée pour les codes 5 de Reed-Solomon, les techniques proposées dans ces articles incluent la recherche d'un polynôme Q(X,Y,Z), où X, Y et Z sont des éléments de Fq, qui s'annule en tout point (PQ,re.) pour,6=1,...,n, puis la factorisation du polynôme Q(X,Y,Z). (On rappelle que les r, sont les composantes du mot reçu r et que les points P)g de Fq2 forment l'ensemble de localisation du code.) Ces techniques s'avèrent toutefois lourdes à mettre en oeuvre, notamment du fait que le polynôme Q(X,Y,Z) à factoriser est un polynôme à trois variables prenant leurs valeurs dans un corps de Galois. Les méthodes de décodage par liste ne semblaient donc pas apporter de solution au problème du décodage des codes de géométrie algébrique qui soit réaliste sur le plan pratique. Dans ces conditions, l'invention propose un procédé de décodage pour code de longueur n et de dimension k sur un corps de Galois Fq, le code étant défini au moyen d'un ensemble de localisation de cardinal n sur Fq x Fq, caractérisé en ce que, l'ensemble de localisation comprenant au moins p sous-ensembles dits agrégats, où ,u 2, chaque agrégat regroupant les éléments (x, y p (x)) de l'ensemble de localisation ayant une valeur commune de x, pour p= 0, (x) -1, où ,,(x) est le cardinal de l'agrégat, il comprend les étapes suivantes: - calcul, à partir d'un mot reçu r, de mots reçus agrégés rf selon lesdits p agrégats; - pour chaque mot reçu agrégé ri, obtention d'au moins un mot agrégé associé r; dans un code de Reed-Solomon par une méthode de décodage par liste; - calcul d'au moins un mot associé dans le code de longueur n et de dimension k, dont les mots agrégés correspondants selon lesdits,u agrégats sont les mots agrégés associés Ej Afin de résoudre notamment les problèmes évoqués ci-dessus, l'invention propose donc d'utiliser un code dont l'ensemble de localisation peut être divisé 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 (on aurait pu tout aussi bien définir les agrégats par une valeur commune de y 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). Lorsque l'on souhaite faire apparaître cette structure en agrégats, les couples de l'ensemble de localisation (qui n'est d'ailleurs pas nécessairement un ensemble de solutions d'une équation algébrique de type C(a,b)) seront notés (x, yp (x)) , où p = 0,...,2(x) -1 et 2(x) est le cardinal de l'agrégat considéré, et les composantes de tout mot c de longueur n seront notées c(x, yp(x)) ; on dira que les composantes de c qui, étiquetées de la sorte, possèdent la même valeur de x forment un agrégat de composantes du mot c L'invention propose ainsi un procédé et un dispositif de décodage dont la complexité est réduite. Par complexité, on entend ici le nombre d'opérations nécessaires à la réalisation du décodage, ou, dans le cas d'une réalisation dans un circuit de décodage, le nombre de portes logiques nécessaires à sa réalisation. Selon une solution pratique à mettre en oeuvre, le code est défini par une matrice de parité H dont les éléments Haa pour 1 Le problème du décodage d'un tel code est ramené à une pluralité de décodages pour codes de Reed-Solomon. On peut ainsi bénéficier des avantages offerts par la technique de décodage par liste dont la mise en oeuvre pour des codes de Reed-Solomon est nettement moins complexe que pour les codes de géométrie algébrique. On notera également que le système d'équations, qui permet d'obtenir le mot de code associé au mot reçu à partir des mots agrégés associés, est un système de Vandermonde; comme il est bien connu de l'homme du métier, la résolution d'un tel système d'équations linéaires est particulièrement simple. Un cas particulier de cette solution est le cas d'un code de géométrie algébrique. Ainsi, grâce à l'invention et contrairement à ce que l'on pouvait penser, on peut bénéficier des avantages offerts par la méthode de décodage par liste, sans toutefois souffrir de la lourdeur impliquée par l'utilisation de polynômes à trois variables prenant des valeurs dans un corps Galois. La méthode de décodage par liste comprend en général, pour chaque mot reçu agrégé r1, les étapes suivantes: - recherche d'au moins un polynôme f1 sur Fq de degré au plus k1 tel que le nombre de composantes r1(x) du mot reçu agrégé rj pour lesquelles r1 (x) = f1 (x) est au moins égal à un nombre r/l, où k1 est un nombre entier prédéterminé et où rit,u et; - calcul du mot agrégé associé r tel que i-1(x;)= f1(x,) pour tout i entre 1 et,u. Le nombre rit est peut être prédéterminé ou correspondre au nombre maximum de composantes pour lesquelles r1(x) = g1 (x) lorsque g1 parcourt l'ensemble des polynômes sur Fq de degré au plus k1. Enfin, lorsque l'étape de recherche d'au moins un polynôme fi génère au mois deux polynômes solutions, une mise en oeuvre possible de l'invention consiste à procéder aux étapes suivantes: - pour chaque polynôme solution, calcul d'un mot agrégé associé ; - pour chaque polynôme solution, calcul d'au moins un mot associé 30 en fonction dudit mot agrégé associé calculé pour le polynôme solution; 2869482 11 - comparaison des mots associés calculés pour chaque polynôme solution avec le mot reçu r - sélection du mot associé Y' parmi les mots associés calculés pour chaque polynôme solution. L'invention propose dans le même ordre d'idée un procédé de décodage pour code de longueur n et de dimension k sur un corps de Galois Fq, le code étant défini au moyen d'un ensemble de localisation de cardinal n sur Fq x Fq, caractérisé en ce que, l'ensemble de localisation comprenant au moins,u sous-ensembles dits agrégats, où ,u 2, chaque agrégat regroupant les éléments (x, yp (x)) de l'ensemble de localisation ayant une valeur commune de x, pour p = 0, (x) -1, où .1,(x) est le cardinal de l'agrégat, il comprend les étapes suivantes: - calcul, à partir d'un mot reçu r, de mots reçus agrégés = [ ri(xj), ri (x2),..., ri(xp) j pour j= 0,..., Jmax ' où J,nax 1, selon une formule du type ri (x) = A (x)[r(x, yo (x)),..., r(x, y,I(X,_l (x))] , où A. (x) est une fonction sur FgA(X), - pour chaque mot reçu agrégé ri, recherche d'au moins un polynôme fi sur Fq de degré au plus ki tel que le nombre de composantes ri(x) du mot reçu agrégé ri pour lesquelles ri(x) = fi (x) est au moins égal à un nombre i, où i u - pour chaque mot reçu agrégé ri, calcul d'au moins un mot agrégé associé tel que fi(x;) pour tout i entre 1 et,u - calcul d'au moins un mot de code associé ï^ dont les composantes i '(x, y) sont telles que A; (x,)[N(x;, yo (x y2(x,)_1 (x; ))] = i^i (x;) pour tout i entre 1 et,u et pour tout j entre 0 et jmax Dans le mode de réalisation déjà évoqué ci-dessus et proposé dans la suite, dans lequel la matrice de parité est formée des valeurs prises par les monômes Y'X' sur l'ensemble de localisation, on réunit avantageusement les monômes ayant une même puissance de la variable Y dans des ensembles M; : Mi ={Y'X1 I O Notons par x1,x2,...,xp les différentes valeurs de x dans l'ensemble de localisation, et par v = [v(xl, Yo (x1)), ..., v(x1, .ya11 1(x1)),..., v(x, YÂ, 1(xv)) l, un mot de code quelconque. On peut alors construire, pour chaque agrégat attaché à l'une des valeurs x1,x2,...,xp de x, (jmax + 1) symboles agrégés .1.(X)-1 v j (x) {y p (x)] i v(x, y p (x)) P=0 pour j = 0,..., jmax. Ces symboles agrégés servent à former (jm +1) mots agrégés v j = [ v j (xt), v j (x2),..., vi(xp) l de longueur g. On vérifie facilement que la condition d'appartenance au code de géométrie algébrique (à savoir H É vT =o) est équivalente à l'ensemble de ( jmax +1) équations: Ht(.i) . v.T =o, où la fonction t(j) est donnée ci- dessus et, par définition, 1 1 1 x1 X2 t-1 t-1 t-1 x1 x2 x1i - L'intérêt de cette formulation est que cette matrice lit 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 vi, 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. Dans le mode de réalisation proposé, pour j = 0,...,jmax, les mots reçus agrégés rl = [ri(xI),ri(x2),...,ri(xii) ] s'expriment donc en fonction du mot reçu r par la formule ri (x) _ E [y p (x)]' r(x, y p (x)) (1) p=o La mise en oeuvre de ce procédé de décodage est particulièrement avantageuse pour un certain type de canaux: il s'agit des canaux dans lesquels les données à transmettre sont groupées en blocs de longueur prédéterminée, et dans lesquels le taux d'erreurs par donnée transmise est essentiellement constant au sein d'un même bloc. Autrement dit, de tels canaux sont physiquement caractérisés en ce que, le plus souvent, les bruits de transmission affectent les données par bloc, et peuvent affecter différemment des blocs différents; ainsi, pour certains blocs, la probabilité d'erreur pourra être très faible ou même nulle, cependant que pour certains autres blocs la probabilité d'erreur pourra être élevée et même proche de (q -1)/ q. Cela se traduit par une rafale d'erreurs ( burst of errors en anglais) en termes de symboles du corps de Galois. Un exemple, important dans la pratique industrielle, de canaux de ce 20 type est constitué par l'enregistrement/lecture sur disque dur. En effet, les bits composant les symboles des mots de code sont habituellement enregistrés au moyen d'un code de modulation destiné à assurer certaines propriétés spectrales souhaitables, par exemple la propriété selon laquelle le nombre de 1 est, en moyenne, approximativement égal au nombre de 0 . Pour obtenir ce résultat, les bits entrant dans le modulateur sont groupés par blocs a de N bits; en fonction du bilan entre le nombre total de 1 et le nombre total de 0 précédemment enregistrés, un bloc a sera enregistré sur le disque, soit tel quel, soit sous forme de son complément a' (où l'on a changé chaque 1 en un 0 et inversement), de manière à ce que le nouveau bilan soit aussi proche que possible de l'égalité. Lorsqu'une erreur d'enregistrementllecture se produit sur un bit particulier, l'ambiguïté résultant du codage de modulation fait que l'on ne peut corriger individuellement ce bit, et que l'on doit par conséquent, en pratique, se résoudre à considérer le bloc entier de N bits comme erroné. Comme l'on considère par ailleurs que les bits enregistrés et lus forment des multiplets représentant des symboles d'un corps de Galois, un bloc erroné de N bits sera généralement à cheval sur plusieurs symboles; par exemple, si N=48 et q = 210, un bloc erroné pourra être à cheval sur 6 multiplets de 10 bits successifs, ce qui se traduit par une rafale d'erreurs affectant 6 symboles du corps de Galois. On voit donc que le procédé de décodage proposé qui corrige en premier lieu des agrégats erronés associés au mot reçu et non des composantes individuelles erronées de ce mot, est bien adapté à tirer parti d'une telle répartition du bruit sur un canal de transmission: il suffit pour cela d'insérer en position adjacente dans le flux de données à transmettre les composantes d'un mot de code (de canal) appartenant à un même agrégat. En revanche, et pour la même raison, le nombre d'erreurs individuelles 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 distanceminimale du code de géométrie algébrique considéré). Cela étant, la question se pose de savoir si les codes pouvant bénéficier de ce procédé de décodage souffrent tous de cet inconvénient dans la même mesure. Naturellement, l'invention concerne également les dispositifs de décodage mettant en oeuvre l'invention. Les avantages de ces dispositifs de décodage sont essentiellement les mêmes que ceux des procédés corrélatifs décrits ci-dessus. L'invention vise également: - un appareil de lecture de signaux numériques codés comprenant un lecteur de données modulées, des moyens pour démoduler lesdites données modulées en signaux numériques codés, et un dispositif de décodage tel que décrit ci-dessus, - un appareil de réception de signaux numériques codés comprenant un récepteur de données modulées, des moyens pour démoduler lesdites données 5 modulées en signaux numériques codés et un dispositif de décodage tel que décrit ci-dessus, - un système de stockage de données comprenant au moins un appareil d'enregistrement de signaux numériques codés, au moins un support d'enregistrement et au moins un appareil de lecture de signaux numériques codés tel que décrit ci-dessus, - un système de télécommunication de données sous forme de blocs de longueur prédéterminée, comprenant au moins un appareil d'émission de signaux numériques et au moins un appareil de réception de signaux numériques codés tel que décrit ci-dessus, - 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 et/ou de communication 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 et/ou de communication 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 et/ou de communication exposés ci-dessus. Les avantages offerts par ces appareils de lecture ou de réception, ces systèmes de stockage de données ou de télécommunication, 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 décodage 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 dans le contexte de l'invention, - la figure 2 représente un appareil d'enregistrement de signaux numériques incorporant un exemple de codeur, - la figure 3 représente un appareil de lecture de signaux numériques incorporant un dispositif de décodage selon l'invention, - la figure 4 présente le schéma général de la technique de décodage proposée par l'invention, - la figure 5 illustre un mode de réalisation de la phase d'interpolation proposée par l'invention, - la figure 6 illustre un mode de réalisation de la phase de factorisation proposée par l'invention, - la figure 7 décrit une solution possible lorsque les phases précédentes donnent plusieurs solutions. La figure 1 est un schéma synoptique d'un système de transmission d'informations utilisant un 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 série de bits conformément à un code de modulation, comme expliqué ci-dessus). 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 nonfilaire comme c'est le cas d'un lien radio. Le message transmis parvient à un lecteur (ou un récepteur) 105, 5 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 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. Le schéma synoptique de la figure 2 représente, de façon très 20 schématique, un appareil d'enregistrement de données d'information 48 incorporant le codeur 102. Cet appareil 48 comprend un clavier 911, un écran 909, une source d'informations externe 100, un modulateur 103 et un enregistreur de données modulées 104, conjointement reliés à des ports d'entrée/sortie 903 d'un dispositif de codage 102 qui est réalisé ici sous la forme d'une unité logique. Le dispositif de codage 102 comporte, reliés entre eux par un bus d'adresses et de données 902: - une unité centrale de traitement 900, une mémoire vive RAM 904, - une mémoire morte 905, et - lesdits ports d'entrée/sortie 903. 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 transmission 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: - la source d'informations 100 pourrait être, par exemple, un périphérique d'interface, un capteur, un démodulateur, une mémoire externe ou un autre système de traitement de l'information (non représenté), et pourrait par exemple fournir 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, et - l'enregistreur 104 est adapté à enregistrer des données modulées sur un support tel qu'un disque magnétique. La mémoire vive 904 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. On observera, au passage, que le mot registre désigne, à travers la présente description, aussi bien une zone mémoire de faible capacité (quelques données binaires) qu'une zone mémoire de grande capacité (permettant de stocker un programme entier) au sein d'une mémoire vive ou d'une mémoire morte. La mémoire vive 904 comporte notamment les registres suivants: - un registre symboles information dans lequel sont conservés les symboles d'information appartenant à Fq, et - un registre mots code , dans lequel sont conservés les mots de code v avant qu'ils ne soient soumis au modulateur 103. La mémoire morte 905 est adaptée à conserver, dans des registres 25 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 900, 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 - la matrice de parité du code, dans un registre H . Naturellement, la description qui vient d'être faite ne représente qu'un exemple illustratif et non limitatif de réalisation d'un codeur. Le schéma synoptique de la figure 3 représente un appareil de lecture de signaux numériques codés 70 incorporant le décodeur 10. Cet appareil 70 comprend un clavier 711, un écran 709, un destinataire d'informations externe 109, un lecteur de données 105 et un démodulateur 106, conjointement reliés à des ports d'entrée/sortie 703 du décodeur 10 qui est réalisé ici sous la forme d'une unité logique. Le décodeur 10 comporte, reliés entre eux par un bus d'adresses et de données 702: - une unité centrale de traitement 700, - une mémoire vive (RAM) 704, - une mémoire morte (ROM) 705, et - lesdits ports d'entrée/sortie 703. On observe que: - le destinataire d'informations 109 pourrait être, par exemple, un périphérique d'interface, un afficheur, un modulateur, une mémoire externe ou un autre système de traitement de l'information (non représenté), et pourrait être adapté à recevoir des séquences de signaux représentatifs de parole, de messages de service ou de données multimédia notamment de type IP ou ATM, sous forme de séquences de données binaires, - le lecteur 105 est adapté à lire des données enregistrées sur un support tel qu'un disque magnétique ou magnéto-optique. La mémoire vive 704 conserve des données, des variables et des résultats intermédiaires de traitement, dans des registres de mémoire portant, dans la description, les mêmes noms que les données dont ils conservent les valeurs. La mémoire vive 704 comporte notamment les registres suivants: des registres mots reçus , dans lesquels sont conservés les mots reçus, - des registres mots agrégés , dans lesquels sont conservés les mots reçus agrégés, - 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 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 , et - le nombre de symboles d'information servant à construire un mot de code, dans un registre k . On remarque que, dans les modes de réalisation où seule une méthode de décodage par liste est utilisée, il n'est pas nécessaire de mémoriser les matrices de parité des codes de Reed-Solomon. En effet, la méthode de décodage par liste utilise les valeurs de l'ensemble de localisation et non la matrice de parité du code, comme nous le verrons dans la suite. La mémorisation de la matrice de parité peut toutefois s'avérer utile, par exemple si l'on souhaite utiliser une méthode combinant le décodage par liste proposé par l'invention et un décodage d'un autre type. On notera que, dans certaines applications, il sera commode d'utiliser le même dispositif informatique (fonctionnant en mode multi-tâches) pour l'échange, c'est-à-dire à la fois l'émission et la réception, de signaux selon l'invention; dans ce cas, les unités 10 et 102 seront physiquement identiques. 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 uvre au sein d'un réseau de télécommunications, auquel cas l'unité 105 par exemple pourrait être un 2869482 21 récepteur adapté à mettre en oeuvre un protocole de transmission de données par paquets sur un canal hertzien. On va à présent décrire à titre d'illustration un exemple de réalisation de l'invention dans le cas d'un code de géométrie algébrique particulier. On considère ici un code de géométrie algébrique sur F16 basé sur la courbe algébrique C(2,5) dans F16xF16 représentée par l'équation f(X,Y) = 0 avec f(X,Y) =Y2 +Y +X5 Les points de la courbe C(2,5) (c'est-à-dire les couples (x, y) solutions de l'équation f(X,Y) = 0) constituent donc l'ensemble de localisation du code. Dans le cas présent, l'équation Y2+Y+X5 =0 a trente solutions non triviales dans F16xF16 qui sont les suivantes: (1,a), (1,a10), (a,a), (a,a4), (a2,a), (a2,a), (a3,a5), (a3,a1), (a4,a1), (a4,(y.4), (a5,a) , (a5,(2), (a6,a), (a6,a10), (a7,a), (a7,a4), (a8,(12), (12, a,'), (a9,a5), (a9,a1), (a1o,a), (a10 a4) (a11 a)(a11 a)(a12 a), (a12,a1), (a13,a), (a13 a4) (a14,a2), (a14,a8), où a est l'élément générateur de F16 tel que a4+a+1=0. L'ensemble de localisation peut donc ici être divisé en,u =15 agrégats qui regroupent chacun les points (x, y) ayant une valeur commune de x. Dans le cas présenté ici, le cardinal de chaque agrégat est égal à 2. En reprenant une formulation plus générale, si xi,...,x sont les valeurs de x associées respectivement à chaque agrégat (ici x, = a'd), le ieme agrégat se compose de 2(x,) éléments (ici /1,(x1) = 2) : (x, , yo (x, )),. , (x, , y2(X, )_1 (x, ))...DTD: On peut donc définir un code de géométrie algébrique de longueur n = 30 et de dimension k = 20 par une matrice de parité H de dimensions n = 30,n- k =10 dont les éléments sont définis comme suit: 25),J(I,P) = pour i =1, u, p = 0,..., /1.(x,) -1, j = 0,..., Jmax et z = 0,...,t( j)-1 i-1 où 1(-z-, j) = z+Et(l) pour j>1 etI(z,0) = , f=o et J (i, p) = i + ,u. p. La fonction t utilisée est celle définie plus haut: elle définie le nombre de monômes de la forme Y'XT à j fixé. Par ailleurs, on a supposé pour simplifier les notations que tous les agrégats ont le même cardinal /t(x,) = comme c'est le cas dans l'exemple étudié ici. La matrice de parité H est donc formée par l'évaluation d'un monôme Y'XT associé à chaque ligne sur chaque point de l'ensemble de localisation, chaque point étant associé à une colonne. Dans la matrice de parité H obtenue précisément selon la formule cidessus, les lignes associées aux monômes Y'XT d'une même puissance j sont avantageusement regroupées et classées suivant l'ordre des puissances z. De même, les colonnes sont regroupées en sous-ensemble de colonnes, de telle manière que chaque sous-ensemble contient une et une seule colonne associée à chaque agrégat; par ailleurs, dans chaque sous-ensemble de colonnes, les colonnes sont classées dans l'ordre des agrégats (x,,...,xp) . En utilisant des matrices H de la forme 1 1 1 Ht XI X2.. Xp, la matrice de parité H peut donc s'écrire t-1 t-1 t-1 x1 x2 x - _ H 0) - Ht(0) Ht(0) Ht(1).Y Ht(').y 1 Ht (Jmax) Y0 max t(lmax) y Jmax Ht(Jmax) ylmax où chaque Yp est une matrice diagonale d'éléments diagonaux (.vp (x1),..., y p (x,) ). Dans l'exemple étudié ici, la matrice de parité H peut donc s'écrire H6 H6 avec pour H6 la matrice suivante H4Y0 H4Y H= H1(').Yo H= 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 a a2 a3 a4 as a6 a7 as a9 a' a" a'2 a'3 a'4 1 a2 a4 a6 a8 a' a'2 a'4 a a3 as a7 a9 a'1 a13 1 a3 a6 a9 a12 1 a3 a6 a9 a12 1 a3 a6 a9 a12 1 a4 a8 a12 a as a9 a'3 a2 ab a' a14 a3 a7 al] 1 a5 a10 1 a5 a10 1 a a5 1 a5 as 1 a5 a5 1 1 H4 la matrice suivante 1 1 1 1 1 1 1 1 1 1 1 1 1 1 a a2 a3 a4 a5 a6 a7 a8 a9 a' a" a'2 a'3 a'4 1 a2 a4 a6 a8 a' a'2 a14 a a3 a5 a7 a9 al' a'3 1 a3 a6 a9 a12 1 a3 a6 a9 a12 1 a3 a6 a9 a12 et les diagonales respectives de Y et y étant (a5, a, a2, a5,a, a2, a5, a a2 5,a, a2 a5 a a2) et (a1 a4 a8 a10 a4 as a10 a4 as a10 a4 a8 a10 a4 as). On va à présent décrire les différentes étapes du décodage tel que proposé par l'invention, lorsque l'on souhaite décoder un mot reçu r, et par conséquent retrouver tout d'abord au moins un mot ï" du code de géométrie algébrique associé au mot reçu r. Cette description sera notamment faite en référence à la figure 4 qui décrit schématiquement les différentes étapes du décodage. Le schéma de la figure 4 peut en outre représenter une architecture envisageable pour un dispositif électronique apte à mettre en oeuvre l'invention. L'invention n'est toutefois pas limitée aux dispositifs de ce type. Le mot reçu r correspond donc à un mot de code c après transmission dans le canal, et intègre donc éventuellement des erreurs de transmission. On peut supposer à titre d'exemple que le mot de code c = (a9 a12 a13 a5 a12, a9, 0, 0, 0, 0, 0, 0, 0, a7, a6, a14, a2, 0, 0, 0, 0, 0, 0, 0, 0, 0) ait été transmis dans le canal et que le mot reçu r correspondant comporte trois erreurs indiquées en gras ci-dessous: r = (a9 a12 a13, a8, a12, a9, aO, 0, 0, 0, 0, 0, 0, 0, 0, a7, (16, a14, a 0,0,0,0,0, a12, 0, 0, 0). Comme on l'a vu, le décodage du mot reçu r consiste principalement à rechercher le (ou les) mot(s) de code associé(s) les plus 5 proche du mot reçu r au sens de la distance de Hamming. Vu le code utilisé, et notamment la forme particulière de la matrice de parité, on remarque toutefois que la condition d'appartenance du mot de code associé î au code (H. FT = 0) peut s'écrire sous la forme Ht(o) HI(0) Hrro) Ht(1).Y Ht(1) Ht(1).Y-1 (r (xl, y0 (x1)),..., i'-(x p, .y0 (xr))T =0, Hr(imax) yimax Ht(imax) yimax 0 1... Ht(imax) yimax /1 1 (r-(x, ,ya,-1(x1)),..., r (xM, Y 1 (xp))T c'est-à-dire - t 1 Ht (0) .E (r (x1, y (xl)),..., r (xi, , .y p (xa))T P=0 2 1 T 2 1 j.%t(imax) ypmax,Yp)) (x1,...,?(x,, yp(x))T t p=0 Comme on l'a vu, en définissant pour j = 0,... ,jmax des mots agrégés A 1 associés r i = [ i (x1), i'i (x2),..., ri (xi,) ] = E Yp.(r(xl, y p (xl)),..., (xp, y p (xp))T la p=0 condition d'appartenance au code de géométrie algébrique est ramenée à 15 j,n +1 équations de la forme Ht(i)& =0, qui signifient chacune que le mot agrégé associé ri est un mot du code de Reed-Solomon ayant pour matrice de parité Ht(i) . On ramène ainsi le décodage du mot reçu r au décodage de furax +1 mots agrégés ri définis par la formule 2 1 ri (x) = E [Yp (x)]i r(x,yp (x)) p=0 H .E yp É(r (xl, y p (xl)),..., (xp, Y p (x,)) p=0 =0 Le décodage du mot reçu r pourra être réalisé de manière séparée pour chaque mot agrégé, éventuellement en parallèle, comme représenté symboliquement par la présence de plusieurs (précisément jmax +1) zones de traitement 310,...,320 en figure 4. La première étape du traitement relatif à chaque mot agrégé rj consiste naturellement à calculer le mot agrégé (c'est-à-dire ses composantes), ce qui revient en pratique à effectuer des sommes de symboles du mot reçu r avec différentes pondérations, comme indiqué sur les blocs 315a,...,315b. Chaque bloc 315a,...,315b génère ainsi un mot agrégé ri. Dans le cas présenté ici à titre d'exemple, les mots reçus agrégés sont donc: 13 8 r1= (a', a12,a,a,a12,a9, O,O,O,O,O,O,O,O)+(a,7,a.6,a,14,a 0,0,0,0,0, a12, 0, 0, 0) = (a , a4, a2, a", a12, a9, a , 0, 0,0, a12, 0,0, 0,0) et r2= Yp (a9, a12 al3 a8 al2 a9 a0 O, o, O O O, o, O 0)+ y (a7 a6 a14, a,0,0,0,0,0, a12, 0, o, 0) = (a13, a9, a9, 0(.4 al3, a11, a5, 0, 0, 0, a, 0, 0, 0, 0) Au sein de chaque zone 310,...,320, le traitement de chaque mot agrégé ri se poursuit par son décodage selon une méthode de décodage par liste, qui comprend une phase d'interpolation et une phase de factorisation. La phase d'interpolation, qui va à présent être décrite en détail en référence à la figure 5, consiste à rechercher un polynôme Q sur FqxFq (ici sur F16xF16) qui passe par les points (x,,r](x;)) , pour i =1, u, avec un ordre de multiplicité m. On rappelle qu'un polynôme P(X,Y) passe par un point (x,y) avec un ordre de multiplicité m si toutes ses dérivées de Hasse d'ordre (m-1) 25 s'annulent en ce point. Si les a. sont les coefficients de chaque monôme X'Y' 00 0o i j ' j-!' au sein du polynôme P, cette condition s'exprime E E i-k x y a -u, k' l' 1=k' J=l' pour tous k' et l' entiers positifs tels que k'+ l' Dans le cas particulier où m=1 pris à titre illustratif, l'interpolation se ramène à la recherche un polynôme Q(X,Y) qui passe par les points (x,, rj(x; )) , pour i =1, u, c'est-à-dire qui s'annule en ces points. L'algorithme d'interpolation utilisé dans l'invention s'inspire des algorithmes proposés par les documents VLSI Architecture for softdecision decoding of Reed-Solomon Codes de Arshad Amesh, Ralf Koetter et Naresh R. Shanbag, Preprint, in IEEE transaction on VLSI systems, février 2003, et Decoding Hermitian codes with Sudan's algorithm , T. HoHoldt et R. Refsund Nielsen, in Applied Algebra, Algebraic Algorithm and Error Correcting Codes, Lecture notes in computer science, Springer Verlag 1999 Dans la description de l'algorithme qui suit, on utilisera le paramètre T défini par la formule T = Int(1 + 1,\il+8*C)-1 où C = pm2 et Int la fonction 2 n k 1 partie entière. Comme nous le verrons, ce paramètre T représente le nombre de 15 polynômes candidats obtenus par l'algorithme d'interpolation. On utilisera de plus un indice L qui permettra de désigner l'un des polynômes parmi ces T polynômes candidats. L'algorithme d'interpolation débute à l'étape E510 où l'on initialise l'indice L (L=0). On passe alors à l'étape E511 où l'on vérifie si l'indice L est inférieur ou égal au nombre de polynômes candidats T. Si l'indice L est inférieur au nombre de candidats T, on passe à l'étape E501 où l'on définit le polynôme ZL par ZL=YL. On passe alors à l'étape E512 où l'on incrémente la valeur de L. Une fois la valeur L incrémentée, on retourne à l'étape E511 à laquelle on compare l'indice L au nombre total T de polynômes candidats. Lorsqu'à l'étape E511, on ne vérifie plus que L est inférieur ou égal à T, on passe à l'étape E513 à laquelle on initialise la valeur d'un paramètre i à zéro. On peut remarquer que les étapes E510, E511, E501 et E512, qui définissent une boucle sur la valeur de l'indice L, permettent de construire une base de polynômes ZL qui est initialisée par la base de polynômes YL. 2869482 27 A l'étape E513, on procède à l'initialisation de l'indice i qui désigne les différents points où l'on souhaite que le polynôme Q(X,Y) s'annule. Après l'étape E513, l'indice i désigne donc un point particulier. On vérifie à l'étape E514 que le dernier point n'a pas été atteint, en comparant l'indice i au nombre p.. Si l'indice i a atteint une valeur supérieure à , c'est-à-dire que tous les points ont été précédemment traités, on passe à l'étape E505 qui sera décrite plus loin. Si au contraire l'indice i est inférieur ou égal à , le point courant désigné par cet indice i est traité en passant tout d'abord à l'étape E515. A l'étape E515, on initialise à zéro la valeur A qui correspond dans la suite à la puissance selon la variable X du monôme considéré. On passe alors à l'étape E516 où l'on compare la valeur courante A à la multiplicité m(i) pour le point d'indice i considéré. Si la puissance A de la variable X dans le monôme considéré est strictement inférieure à la multiplicité m(i), on poursuit le processus pour le point i à l'étape E518. Si au contraire l'exposant A est égal à la multiplicité m(i), on passe à l'étape E517 où l'on incrémente la valeur de i, ce qui revient à passer au traitement du point suivant. A l'étape E518, on initialise à zéro la variable B qui correspond à l'exposant en Y du monôme considéré. Comme précédemment pour la valeur A, on vérifie à l'étape E519 que la valeur B n'est pas strictement inférieure à la multiplicité m(i) pour le point d'indice i diminuée de la valeur courante A de l'exposant du monôme considéré en X. Si l'exposant B est bien inférieur à [m(i)-A], on poursuit le traitement pour le point d'indice i à l'étape E521. Dans le cas contraire, le traitement de tous les exposants B selon la variable Y envisageable pour la valeur A ayant été réalisée, on passe à la valeur A suivante à l'étape E520 (par incrémentation de la valeur A). Une fois la valeur A incrémentée, on retourne à l'étape E516 précédemment décrite. Le traitement se poursuit à l'étape E521 par l'initialisation à 0 de l'indice L qui, comme on l'a vu précédemment, désigne successivement chaque polynôme candidat, et l'initialisation à +oo d'une variable minWd utilisée dans la suite (en pratique, il s'agit naturellement d'une initialisation avec une valeur très importante, par exemple la plus grande valeur entière que peut prendre le registre correspondant). On va à présent décrire une boucle sur l'ensemble des polynômes candidats. En effet, l'étape E521 est suivie par une étape E522 à laquelle on vérifie si l'indice L a atteint le nombre de polynômes candidats T. Si tous les polynômes candidats ZL ont été traités, on sort de la boucle à l'étape E526 décrite plus loin. Si au contraire l'indice L désigne encore un polynôme à traiter, on passe à l'étape E502. A l'étape E502, on détermine le coefficient D du monôme d'exposant A en X et B en Y dans le polynôme translaté ZL(X+x;, Y+y;). On passe alors à l'étape E523 où l'on vérifie si le coefficient D est nul. Si c'est le cas, on passe à l'étape E525 où l'on incrémente l'indice L afin de considérer le polynôme candidat suivant, puis à l'étape E522 où l'on vérifie si le précédent polynôme candidat n'était pas le dernier à considérer. L'étape E522 a été décrite ci-dessus. Si l'étape E523 on détermine que le coefficient D n'est pas nul, on passe l'étape E524 où l'on compare le degré pondéré du polynôme candidat ZL courant au minimum minWd des degrés pondérés obtenus jusqu'alors. Si le degré pondéré du polynôme courant ZL est supérieur ou égal au minimum déjà obtenu minWd, on passe au polynôme candidat suivant en procédant à l'étape d'incrémentation de l'indice L E525 précédemment décrite. Si au contraire le poids pondéré du polynôme courant ZL est strictement inférieur au minimum déjà obtenu minWd, le polynôme courant ZL est donc le nouveau polynôme de degré pondéré le plus faible. On passe donc dans ce cas à l'étape E503 de mémorisation de valeurs relative au polynôme courant ZL. En effet, on mémorise à l'étape E503 le polynôme courant ZL comme le polynôme Zm;n. On met également à jour le degré pondéré minimum minWd à la valeur du poids pondéré du polynôme courant ZL. On mémorise également le coefficient D comme coefficient relatif au poids pondéré minimum, noté minD. Enfin, on mémorise l'indice L du polynôme candidat courant ZL sous la valeur minL. Les données du polynôme courant ZL ayant été mémorisées comme celles dupolynôme de poids pondéré minimum Zmin, on peut passer au polynôme candidat suivant en procédant à l'étape E525 d'incrémentation de l'indice L précédemment décrite. Comme on l'a vu précédemment, lorsque l'ensemble des polynômes candidats ZL a été traité à l'étape E502, on sort de la boucle de traitement à l'étape E522 pour procéder à l'étape E526. A l'étape E526, on initialise à nouveau l'indice L qui désigne le polynôme candidat courant. On va à présent réaliser une nouvelle boucle sur l'ensemble des polynômes candidats. Pour ce faire, on procède à l'étape E527 à la vérification que le polynôme courant L doit être traité, c'est-à-dire que l'indice L est bien inférieur au nombre total de polynômes candidats T. Si ce n'est pas le cas, on sort de la boucle pour passer à l'étape E530 décrite plus loin. Au contraire, si l'indice L représente un polynôme qui doit être traité, on passe à l'étape E528 où l'on détermine si l'indice courant L est égal à l'indice minL du polynôme de degré minimum, tel qu'il a été déterminé par le passage successif à l'étape E503 précédemment décrite. Si l'indice L correspond à l'indice minL du polynôme de degré minimum, on procède à l'étape E504b où l'on multiplie le polynôme Zmin correspondant par le polynôme X+xi. On passe ensuite au polynôme candidat suivant par incrémentation de l'indice L à l'étape E529. Si l'étape E528 il a été déterminé que l'indice L du polynôme courant 25 était différent de l'indice minL du polynôme de degré pondéré minimal, on procède à l'étape E504 à laquelle on modifie le polynôme courant ZL en le remplaçant par le polynôme suivant: ZL.minD+D.Zmin. On passe alors également à l'étape E529 d'incrémentation de l'indice L, suivie de l'étape E527 précédemment décrite. Lorsque le traitement des étapes E504a ou 504b a été réalisé pour 30 l'ensemble des polynômes candidats ZL, l'étape E527 conduit à l'étape E530 à laquelle on incrémente l'exposant B selon la variable Y. Une fois l'exposant B incrémenté à l'étape E530, on retourne à l'étape E519 précédemment décrite où l'on détermine si tous les exposants B qui devaient être traités l'on été. Lorsque tous les points on été traités par le passage de l'indice i de la valeur 1 à la valeur , et que pour chaque point, l'ensemble des exposants A, B envisageables pour les variables X et Y ont été traités, l'étape E514 conduit comme déjà mentionnée à l'étape E505. A l'étape E505, on choisit le polynôme Q(X, Y) qui résulte de l'ensemble de l'algorithme décrit comme étant le polynôme candidat ZL(X,Y) de degré pondéré minimum, et ce notamment pour simplifier les calculs qui suivront. Si plusieurs polynômes candidats ZL ont le même degré pondéré, on considère dans la suite la pluralité de polynômes candidats ZL de même degré. L'étape E505 met donc fin à l'algorithme d'interpolation. La phase d'interpolation génère ainsi au moins un polynôme Q qui 15 s'annule en tous points (x;,ri(x,)) , pour i = l, u. Dans le cas présenté en tant qu'exemple ici, on obtient dans le traitement de r1 le polynôme Q1(X,Y) = a12X +aX4 +a9X5 +aX6 +a6X7 +a3X8 + a4X10,+a5X11 +a13Y +aX2Y +a10X3 +a12XY, et dans le traitement de r2 le polynôme Q2(X,Y) = a12Y +a11XY1-a3X2Y +1 +a11X +a5X2 +a6X4 +0(,2X5 +a5X6 +a10X7 +a5X8 +a8X3 +a3X9 +a2X10 +a14X11 +a14X12 Le traitement du mot agrégé ri se poursuit alors par une phase de factorisation du (ou des) polynôme(s) Q obtenu(s) précédemment en vue 25 d'obtenir au moins un facteur de la forme [Y-f(X)]. La phase de factorisation est par exemple réalisée conformément à un algorithme du type Roth-Ruckenstein, tel que décrit à la figure 6. Pour plus de détails sur cet algorithme, on peut se référer à l'article Efficient Decoding of Reed Solomon Codes Beyond Half the Minimum Distance , R. Roth and G. Ruckenstein, IEEE Trans. Inform. Theory, vol. 46, n 1, janvier 2000. L'algorithme de factorisation débute par une étape E601 à laquelle le polynôme Q(X,Y) est mémorisé pour son traitement sous forme d'un polynôme M(X,Y). L'algorithme de factorisation est un algorithme récursif. Un indice i indique le nombre de boucles effectuées au sein de cet algorithme. On notera par ailleurs v; le nombre de racines trouvé lors de la boucle d'indice i de l'algorithme. On initialise ainsi à l'étape E610 l'indice i à zéro, ainsi que le nombre vo de racines trouvé lors de la boucle d'indice O. L'algorithme peut alors débuter au sens propre à l'étape E611 à laquelle on initialise à zéro la valeur d'un indice r. On passe ensuite à l'étape E612 à laquelle on détermine si le polynôme Xr divise le polynôme M(X,Y) courant. Si c'est le cas, on va rechercher si une puissance supérieure de X divise également le polynôme M(X,Y). Pour ce faire, on passe à l'étape E613 où l'on incrémente la variable r, puis on retourne à l'étape E612 qui vient d'être décrite. Si on détermine à l'étape E612 que le polynôme Xr ne divise pas le polynôme M(X,Y) courant, on passe à l'étape E602 où l'on divise le polynôme courant M(X,Y) par le polynôme X. Cette division est bien sûr possible vu la détermination effectuée lors de l'avant-dernier passage à l'étape E612. On passe alors à l'étape E615 à laquelle on initialise à zéro une variable t qui permettra de désigner successivement l'ensemble des éléments du corps de Galois Fq considéré. En effet, à l'étape E616 qui suit l'étape E615, on détermine si la valeur du polynôme M(X,Y) pour X=at et Y=0 est nulle. Si ce n'est pas le cas, on passe à l'étape E603 décrite plus loin. Si en revanche c'est le cas, on passe à l'étape E621 d'incrémentation de la variable t, puis à l'étape E622 où l'on vérifie si t atteint le nombre d'éléments du corps de Galois Fq. Dans la négative, on revient à l'étape E616 décrite plus haut; dans l'affirmative, le polynôme M(X,Y) s'annulant sur toutes les valeurs de X du corps de Galois pour Y=O, l'algorithme est terminé et on passe donc à l'étape E606a qui le conclut. En effet, l'étape E606a consiste à définir le polynôme f(X) en fonction des résultats de l'algorithme: f(X)=go+g1X+... +gk_iXk-1. De retour à l'étape E603 précédemment évoquée, on effectue une recherche exhaustive parmi les éléments du corps de Galois Fq des Nr racines du polynôme M(0,Y), qui seront dénommées g,,;. On passe alors à l'étape E617 à laquelle on détermine si l'indice v; des racines trouvées lors de la boucle d'indice i atteint le nombre de racines Nr. Si c'est le cas, on peut passer à l'étape E618 d'incrémentation de l'indice de boucle i, c'est-à-dire à la boucle suivante au sens de l'algorithme récursif. On remarque que l'on initialise également à l'étape E618 le nombre de racines v; de la nouvelle boucle à zéro. Après l'étape E618, on débute l'exécution de la nouvelle boucle à l'étape E611 précédemment décrite. Si à l'étape E617 on détermine que l'indice de la racine v; est inférieur ou égal au nombre de racines Nr, on passe à l'étape E619 à laquelle on détermine si l'indice de boucle i a atteint la dimension k du code, lié au degré k-1 du polynôme f(X) recherché. Si c'est le cas, c'est-à-dire si i=k, on passe à l'étape E606b à laquelle il est déterminé que l'algorithme n'a pas permis de trouver un polynôme f(X) solution. Cette étape conduit naturellement à l'échec du décodage pour le polynôme Q(X,Y) auquel on a appliqué l'algorithme de factorisation. Si on détermine à l'étape E619 que l'indice de boucle i n'a pas atteint la dimension du code k, on passe à l'étape E604 où l'on transpose le polynôme courant M(X,Y) par la définition suivante du nouveau polynôme courant: M(X,Y)=M(X,Y+g;). L'étape E604 est suivie de l'étape E605 à laquelle on décale le polynôme M(X,Y) : comme précédemment le polynôme courant est remplacé par 25 le nouveau polynôme courant selon la formule: M(X,Y)=M(X,XY). Après l'étape E605, on procède à l'étape E620 à laquelle on incrémente l'indice v; qui désigne une racine particulière trouvée lors de la boucle i. L'étape E620 est suivie de l'étape E611 précédemment décrite qui permet la poursuite de l'algorithme. L'algorithme qui vient d'être décrit a ainsi permis de déterminer un polynôme f(X), défini à l'étape E606a, de telle sorte que [Y-f(X)] est un facteur du polynôme Q(X,Y). 2869482 33 Le polynôme [Y-f(X)] étant un facteur de Q, il s'annule en au moins une partie des points (x,,r](x,)), pour i=1, u. Aux points (x,,rj (xi)) où [Y- f(X)] s'annule, on peut donc écrire r.)(x;) = f(x,) et le mot agrégé rj a donc autant de composantes communes avec le mot constitué des composantes f(x,) pour i =1, u. Le mot agrégé r tel que ij(x,) = f(x,) pour i = l, u, qui est un mode de code dans le code de Reed-Solomon considéré, est donc un bon candidat pour être un mot agrégé associé au mot reçu agrégé r. L'application de l'algorithme de factorisation qui vient d'être décrit au 10 polynôme Q1(X,Y) obtenu ci-dessus en relation avec le mot reçu agrégé r1 donne comme facteur du polynôme Q1(X,Y) le polynôme suivant: (Y+a5X9+a 10X8+a4X7+a 12X6+aX5+a3X4+aX3+a13X2+a 14X) L'application du même algorithme au polynôme Q2(X,Y) obtenu à partir du mot reçu agrégé r2 donne comme facteur le polynôme: (Y+a11X10+a13X9+a4X8+a8X7+a7X6+a11 X5+068X4+a13X3+a13X+(13) . Ces polynômes étant effectivement de la forme [Y-f(X)], on obtient le mot de code agrégé associé à chacun en calculant pour chacun, comme indiqué ci- dessus, la valeur prise par le polynôme f sur les points de l'ensemble de localisation (x,,...,x,). On peut de ce fait considérer que cette étape consiste à procéder au ré-encodage du mot. On obtient ainsi les mots de code agrégés associés: = (a , 064, 062, al, CL12, a9, a0, 0, 0,0, o, 0,0,0,0) et r2 = (a13, 2, a9 2a13, a11, a5, 0 0, 0, 0, 0 0, 0 0,0), où les chiffres en gras mettent en évidence les composantes qui ont été modifiées, c'est-à-dire corrigées, par rapport aux mots reçus agrégés r1 et [2. Chaque zone 310,...,320 permet ainsi d'obtenir selon une méthode de décodage par liste un mot de code agrégé associé r i à partir du mot agrégé r. Les mots agrégés v; correspondant aux mots v du code de géométrie algébrique par la relation générale: Â.(x)-1 v j (x) E [y p (x)]3 v(x,.yp (x)) , p=o on va pouvoir déterminer les composantes du mot de code associé r au mot reçu r en résolvant le système composé des équations suivantes: (x;) = E [y, (x,)}' (xi,Yp (x; )) (pour i =1, u et j = 0,..., max), p=0 puisque les mots agrégés associés r sont à présent connus. La résolution du système d'équations, représenté schématiquement par le bloc référencé 350 qui reçoit l'ensemble des mots agrégés associés rj des différentes zones 310,...,320, permet ainsi d'obtenir le mot de code r associé au mot reçu r. Dans l'exemple présenté en détail ici, la résolution du système donne pour résultat le mode de code associé suivant: (a9, a12 a13 a5 a127 a9, a , 0, 0, 0, 0, 0, 0, 0, a7, a6, a14, a2, 0, 0, 0, 0, 0, 0, 0, 0, 0), égal au mot de code initialement envoyé. La correction d'erreur au moyen du décodage par liste de chacun des mots reçus agrégés a donc été efficace. On peut remarquer qu'il est possible en variante de ne résoudre dans le système d'équations que les lignes qui correspondent à des mots reçus agrégés erronés, c'est-à-dire pour lesquelles ij (x;) r; (xi). Le coût calculatoire sera ainsi limité puisque le nombre de composantes erronées est en général faible. On a représenté schématiquement à la figure 7 une solution possible dans le cas où le décodage par liste des mots reçus agrégés ri donne plusieurs solutions, par exemple deux polynômes f1 et f2 qui correspondent à deux solutions &,o et il.;, , pour chaque mot reçu agrégé r; Dans le traitement de chaque mot reçu agrégé r; (c'est-à-dire dans chaque zone 310, ..., 320), un multiplexeur 720a, ..., 720b permet de ne transmettre au dispositif de ré-encodage 730a, ..., 730b qu'un seul des polynômes f1, f2 obtenus par l'algorithme de factorisation et stockés en mémoire (comme symboliquement représenté avec les références 710a, ..., 710b). Les polynômes sélectionnés par les multiplexeurs 720a, ..., 720b génèrent donc des mots agrégés associés qui sont utilisés dans la résolution du système représenté comme précédemment par la référence 350, afin d'obtenir un mot de code associé . Pour chaque sélection possible entre différents polynômes f2 réalisée par les multiplexeurs 720a, ..., 720b, on obtient ainsi un mot associé r qui peut être comparé au mot reçu r (référencé 760 sur la figure 7) au sein d'un dispositif comparateur 360. En commandant toutes les combinaisons possibles quant aux sélections des différents multiplexeurs, le comparateur 360 peut ainsi déterminer quelle combinaison permet d'obtenir un mot associé F le plus proche du mot reçu r au sens de la distance de Hamming, et de choisir ce mot associé comme résultat du décodage. On pourra utiliser sans sortir du cadre de l'invention d'autres méthodes de choix du résultat du décodage lorsque la méthode de décodage par liste donne une pluralité de solutions. REVENDICATIONS 1. Procédé de décodage pour code de longueur n et de dimension k sur un corps de Galois Fq, le code étant défini au moyen d'un ensemble de localisation de cardinal n sur Fq x Fq, caractérisé en ce que, l'ensemble de localisation comprenant au moins fu sous-ensembles dits agrégats, où , u 2, chaque agrégat regroupant les éléments (x, y p(x)) de l'ensemble de localisation ayant une valeur commune de x, pour p = 0,...,2(x) l, où ,. (x) est le cardinal de l'agrégat, il comprend les étapes suivantes: calcul (315a,315b), à partir d'un mot reçu r, de mots reçus agrégés r, selon lesdits,u agrégats; - pour chaque mot reçu agrégé r1, obtention (100) d'au moins un 15 mot agrégé associé iL-j dans un code de Reed-Solomon par une méthode de décodage par liste; - calcul (350) d'au moins un mot associé i, dans le code de longueur n et de dimension k, dont les mots agrégés correspondants selon lesdits,u agrégats sont les mots agrégés associés i^ J. 2. Procédé de décodage selon la revendication 1, caractérisé en ce que le code est défini par une matrice de parité H dont les éléments Ha,p pour 1 3. Procédé de décodage selon la revendication 1 ou 2, caractérisé en ce que le code est un code de géométrie algébrique. 2869482 37 4. Procédé de décodage selon l'une des revendications 1 à 3, caractérisé en ce que le calcul d'un mot reçu agrégé ri = [5 (xl), r1(x2), ., r1(xi,) ] est réalisé selon une formule du type ri (x) = A (x)[r(x, y0 (x)),..., r(x, y?(x)_, (x))] , où Ai (x) est une fonction sur Fei pour tout j entre 0 et jmax, où jmax 1...CLMF: 5. Procédé de décodage selon la revendication 4, caractérisé en ce que, pour tout i entre 1 et,u et pour tout j entre 0 et Lm, la fonction A (x,) 2(x,)-1 est définie par AJ(x,)[zo,...,z2(x,)_,1= E [Yp(x,)fzp. p=0 6. Procédé de décodage selon la revendication 4 ou 5, caractérisé en ce que les composantes i(x, y) du mot de code associé sont telles que (x, )[ (x ya (x, )),...,i--(x, , yz(x,)_, (x, ))] = (x,) pour tout i entre 1 et,u et pour tout j entre 0 et jmax 7. Procédé de décodage selon l'une des revendications 1 à 6, caractérisé en ce que le mot associé est calculé par la résolution d'un système d'équations. 8. Procédé de décodage selon la revendication 7, caractérisé en ce que la résolution du système d'équations est limitée aux lignes qui contiennent des composantes erronées des mots reçus agrégés r, pour lesquelles rf(x;) #ri (x,) . 9. Procédé de décodage selon l'une des revendications 1 à 8, caractérisé en ce qu'il comprend une étape de sélection d'un mot associé parmi une pluralité de mots associés calculés. 10. Procédé de décodage selon l'une des revendications 1 à 8, caractérisé en ce que la méthode de décodage par liste comprend, pour chaque mot reçu agrégé ri, les étapes suivantes: - recherche d'au moins un polynôme fi sur Fq de degré au plus ki 5 tel que le nombre de composantes ri (x) du mot reçu agrégé ri pour lesquelles ri(x) = f1 (x) est au moins égal à un nombre où ki est un nombre entier prédéterminé et où ris 12. Procédé de décodage selon la revendication 10, caractérisé en 15 ce que le nombre est le nombre maximum de composantes pour lesquelles r (x) = gJ (x) lorsque g parcourt l'ensemble des polynômes sur Fq de degré au plus ki. 13. Procédé de décodage selon l'une des revendications 10 à 12, 20 caractérisé en ce que, l'étape de recherche d'au moins un polynôme f générant au mois deux polynômes solutions, il comprend les étapes suivantes: - pour chaque polynôme solution, calcul d'un mot agrégé associé ; - pour chaque polynôme solution, calcul d'au moins un mot associé en fonction dudit mot agrégé associé calculé pour le polynôme solution; comparaison des mots associés calculés pour chaque polynôme solution avec le mot reçu r; - sélection du mot associé parmi les mots associés calculés pour chaque polynôme solution. 14. Procédé de décodage selon la revendication 13, caractérisé en ce que le mot associé sélectionné est le mot associé calculé le plus proche du mot reçu r au sens de la distance de Hamming. 15. Procédé de décodage pour code de longueur n et de dimension k sur un corps de Galois Fq, le code étant défini au moyen d'un ensemble de localisation de cardinal n sur Fq x Fq, caractérisé en ce que, l'ensemble de localisation comprenant au moins,u sous-ensembles dits agrégats, où u 2, chaque agrégat regroupant les éléments (x, y p (x)) de l'ensemble de localisation ayant une valeur commune de x, pour p = 0,...,2(x) -1, où /t(x) est le cardinal de l'agrégat, il comprend les étapes suivantes: calcul, à partir d'un mot reçu r, de mots reçus agrégés ri =[ri(xl), ri(x2),...,ri(xp)] pour j = 0,...,jmax, où ,%max ?1, selon la formule Â(x) -I ri (x) = E [y p (x)]' r (x, y p (x)) , p=o - pour chaque mot reçu agrégé ri, recherche d'au moins un polynôme fi sur Fq de degré au plus k. tel que le nombre de composantes r (x) du mot reçu agrégé r pour lesquelles r (x) = f (x) est au moins égal à un nombre ris, où i,u; - pour chaque mot reçu agrégé ri, calcul d'au moins un mot agrégé associé r tel que if(x,) = fj(x,) pour tout i entre 1 et,u; - calcul d'au moins un mot de code associé r dont les composantes 1(x)-I i,(x,y) sont telles que i,(x1)= E [yp(x1)]'ï"(x,,yp(x,)) pour tout i entre 1 et p=0 u et pour tout j entre 0 et Lm. 16. Dispositif de décodage pour code de longueur n et de dimension k sur un corps de Galois Fq, le code étant défini au moyen d'un ensemble de localisation de cardinal n sur Fq x Fq, caractérisé en ce que, l'ensemble de localisation comprenant au 5 moins,u sous-ensembles dits agrégats, où , u 2, chaque agrégat regroupant les éléments (x, y p (x)) de l'ensemble de localisation ayant une valeur commune de x, pour p = 0,...,2(x) l, où Z(x) est le cardinal de l'agrégat, il comprend: - des moyens de calcul, à partir d'un mot reçu r, de mots reçus agrégés r selon lesdits,u agrégats; - des moyens d'obtention, pour chaque mot reçu agrégé r, d'au moins un mot agrégé associé rJ dans un code de Reed-Solomon par une méthode de décodage par liste; - des moyens de calcul d'au moins un mot associé II", dans le code de longueur n et de dimension k, dont les mots agrégés correspondants selon lesdits,u agrégats sont les mots agrégés associés r. 17. Dispositif de décodage selon la revendication 16, caractérisé en 20 ce que le code est défini par une matrice de parité H dont les éléments Ha,a pour 1 18. Dispositif de décodage selon la revendication 16 ou 17, caractérisé en ce que le code est un code de géométrie algébrique. 19. Dispositif de décodage selon l'une des revendications 16 à 18, caractérisé en ce que les moyens de calcul d'un mot reçu agrégé 30 r1 =[ri(xl),ri(x2),...,r](xp)] incorporent des moyens de calcul du type r (x) = Ai (x)[r(x, yo (x)),..., r(x, y,(x)_1 (x))] , où A; (x) est une fonction sur Fe) pour tout j entre 0 et jmax, où Imax 2_1. 20. Dispositif de décodage selon la revendication 19, caractérisé en ce que, pour tout i entre 1 et p et pour tout j entre 0 et j,nax, la fonction %(x; ) 1 Aj(xi) est définie par A1(xi)[z0,...,za,(x)_1]= E [yp(x1)]'zp p=0 21. Dispositif de décodage selon la revendication 19 ou 20, caractérisé en ce que les moyens de calcul du mot de code associé ï^ déterminent les composantes i,-.(x, y) du mot de code associé i de telle sorte que Aj(x;) [r(x;, yo (x; )),..., r(x,, yÂ(x)_I (x; ))] = i'j (x;) pour tout i entre 1 et p et pour tout j entre 0 et jmax 22. Dispositif de décodage selon l'une des revendications 16 à 21, 15 caractérisé en ce que les moyens de calcul du mot de code associé comprennent des moyens de résolution d'un système d'équations. 23. Dispositif de décodage selon la revendication 22, caractérisé en ce que les moyens de résolution du système d'équations sont limités au traitement des lignes qui contiennent des composantes erronées des mots reçus agrégés r, pour lesquelles (x;) ri (x;) . 24. Dispositif de décodage selon l'une des revendications 16 à 23, caractérisé en ce qu'il comprend des moyens de sélection d'un mot associé parmi une pluralité de mots associés calculés. 25. Dispositif de décodage selon l'une des revendications 16 à 23, caractérisé en ce que les moyens d'obtention du mot agrégé associé L i par une méthode de décodage par liste comprennent: 2869482 42 - des moyens de recherche d'au moins un polynôme fi sur Fq de degré au plus kf tel que le nombre de composantes rf(x) du mot reçu agrégé r f pour lesquelles rf (x) = fi (x) est au moins égal à un nombre il; , où kf est un nombre entier prédéterminé et où 77 f _ 26. Dispositif de décodage selon la revendication 25, caractérisé en ce que, les moyens de recherche d'au moins un polynôme fi générant au mois deux polynômes solutions, il comprend: - des moyens de calcul d'un mot agrégé associé pour chaque polynôme solution, ; - des moyens de calcul, pour chaque polynôme solution, d'au moins un mot associé en fonction dudit mot agrégé associé calculé pour le polynôme solution; - des moyens de comparaison des mots associés calculés pour chaque polynôme solution avec le mot reçu r; - des moyens de sélection du mot associé r parmi les mots associés calculés pour chaque polynôme solution. 27. Dispositif de décodage pour code de longueur n et de dimension k sur un corps de Galois Fq, le code étant défini au moyen d'un ensemble de localisation de cardinal n sur Fq x Fq, caractérisé en ce que, l'ensemble de localisation comprenant au moins,u sous-ensembles dits agrégats, où ,u 2, chaque agrégat regroupant les éléments (x, y p (x)) de l'ensemble de localisation ayant une valeur commune de x, pour p = 0, (x) -1, où 2(x) est le cardinal de l'agrégat, il comprend: - des moyens de calcul, à partir d'un mot reçu r, de mots reçus agrégés r =[r(x1),ri (x2),...,ri(x,)] pour j=0,...,jmax, où .max ?1, selon la 2(x)- 1 formule r i (x) _ E [y p (x)}' r(x, y p (x)) , p=o - des moyens de recherche, pour chaque mot reçu agrégé rj, d'au moins un polynôme fj sur Fq de degré au plus ki tel que le nombre de composantes ri(x) du mot reçu agrégé r pour lesquelles rj(x) = fj(x) est au moins égal à un nombre 77; , où s u; - des moyens de calcul, pour chaque mot reçu agrégé rj, d'au moins un mot agrégé associé r tel que (x,) = fj(x1) pour tout i entre 1 et,u 10 - des moyens de calcul d'au moins un mot de code associé dont 2(x) 1 les composantes i, (x, y) sont telles que t"j(x1) = [yp (x, )] r(x1, y p (x1)) pour p=o tout i entre 1 et,u et pour tout j entre 0 et jm. 28. Appareil de lecture de signaux numériques codés comprenant un lecteur de données modulées, des moyens pour démoduler lesdites données modulées en signaux numériques codés, et un dispositif de décodage selon l'une des revendication 16 à 27 pour décoder desdits signaux numériques codés. 29. Appareil de réception de signaux numériques codés comprenant un récepteur de données modulées, des moyens pour démoduler lesdites données modulées en signaux numériques codés et un dispositif de décodage selon l'une des revendication 16 à 27 pour décoder desdits signaux numériques codés. 30. Système de stockage de données comprenant au moins un appareil d'enregistrement de signaux numériques codés, au moins un support d'enregistrement et au moins un appareil de lecture de signaux numériques codés selon la revendication 28. 31. Système de télécommunication de données sous forme de blocs de longueur prédéterminée, comprenant au moins un appareil d'émission de signaux numériques et au moins un appareil de réception de signaux numériques codés selon la revendication 29. 32. Moyen de stockage de données inamovible comportant des 10 instructions de code de programme informatique pour l'exécution des étapes d'un procédé de décodage selon l'une des revendications 1 à 15. 33. Moyen de stockage de données partiellement ou totalement amovible, comportant des instructions de code de programme informatique pour l'exécution des étapes d'un procédé de décodage selon l'une des revendications 1 à 15. 34. Programme d'ordinateur, contenant des instructions telles que, lorsque ledit programme commande un dispositif de traitement de données programmable, lesdites instructions font que ledit dispositif de traitement de données met en oeuvre un procédé de décodage selon l'une des revendications 1 à 15.