FR2858141A1 - Codage d'informations par codes de reed-solomon raccourcis - Google Patents

Abstract

La présente invention concerne un procédé de codage dans lequel on code tout mot d'information a de longueur k sous la forme d'un mot v' appartenant à un code de Reed-Solomon C' de dimension k' et de longueur n' (avec n'-k'=n-k) de telle manière que les composantes de v' situées en (n'-n) positions prédéterminées quelconques soient systématiquement égales à des constantes respectives prédéterminées (par exemple, toutes nulles). On peut alors éventuellement supprimer ces composantes à valeur fixe pour obtenir un mot v de longueur n appartenant à un code C, qui constitue donc un code raccourci par rapport au code C'. L'invention concerne également des dispositifs et appareils destinés à mettre en oeuvre ce procédé de codage.Application notamment au codage par code de géométrie algébrique, dans le cas où ce codage peut être ramené au codage par une pluralité de codes de Reed-Solomon raccourcis.

Description

La présente invention concerne les systèmes de communication

dans lesquels, afin d'améliorer la fidélité de la transmission, les données à transmettre sont soumises à un codage de canal. Elle concerne plus particulièrement des procédés de codage ainsi que les dispositifs et appareils destinés à mettre en oeuvre ces procédés.

On rappelle que le codage dit de canal consiste, quand on forme les mots de code envoyés au récepteur, à introduire une certaine redondance dans les données à transmettre. Plus précisément, on transmet, au moyen de chaque mot de code, l'information initialement contenue dans un 10 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 (v0,vl, ...,vnl) (le symbole signifie par définition ).

L'ensemble des mots de code obtenus quand chaque symbole d'information 15 prend une valeur quelconque dans l'alphabet, constitue une sorte de dictionnaire appelé code de dimension k et de longueur n.

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, 20 ê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 T = 0 (où l'exposant T indique la transposition); on dit alors que le code est < orthogonal à cette matrice H. Parmi ces codes linéaires, certains ont la propriété d'être 25 cycliques : pour tout mot de code (v0,v,...,Vnl) donné, le mot (v-,Vl,v0l, ...,vn-2) obtenu par permutation circulaire est un mot du même code. On peut, de façon commode, représenter les mots appartenant à un code linéaire cyclique au moyen de polynômes: si l'on fait correspondre à un mot n-i quelconque v=(v0,vl,...,vn_1) le polynôme v(x)- Yvixi, un mot v donné i=o appartient à un code linéaire cyclique donné si, et seulement si, le polynôme v(x) correspondant est multiple d'un certain polynôme g(x), de degré (n-k) et diviseur de (xn -1), appelé polynôme générateur du code linéaire cyclique qui le caractérise. On peut d'ailleurs associer à tout polynôme générateur g(x) donné une matrice de parité H. Au niveau du récepteur, le procédé de décodage corrélatif à un procédé de codage donné exploite judicieusement la redondance incorporée dans les mots de code 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. 10 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é . Classiquement, le décodeur calcule d'abord le vecteur de syndromes d'erreurs H rT = H -eT. Si les syndromes sont tous nuls, on supposera qu'il n'y a pas eu d'erreur de transmission, et le mot de code 15 associé sera alors simplement pris égal au mot reçu. Si ce n'est pas le cas, on en déduit que certains symboles dans le mot reçu sont erronés, et l'on met alors en oeuvre un algorithme de correction destiné à estimer la valeur de l'erreur e; I'algorithme va ainsi fournir une valeur estimée ê de manière à ce que (r-ê) soit un mot de code, qui constituera alors le mot de code 20 associé .

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.

Un algorithme de correction d'erreurs a pour tâche d'associer au mot 25 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 dd'un code la plus petite distance de Hamming entre deux mots différents de ce code. C'est un paramètre 30 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, 5 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.

La présente invention concerne notamment les codes dits de Reed-Solomon , qui sont réputés pour leur efficacité. Ce sont des codes 10 linéaires cycliques, dont la distance minimale d est égale à (n-k+l). De manière générale, les codes de dimension k et de longueur n possédant une distance minimale d=n-k+l sont dits MDS (initiales des mots anglais Maximum Distance Separable ), car il s'agit de codes dont la Distance minimale permet une Séparation Maximale entre les mots du code, compte 15 tenu des paramètres k et n).

Lorsque la taille q de I'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 à yi-1 pour une valeur correspondante de i, 20 où i = 1,...,q -1, et où y est une racine (q - 1) eme primitive de l'unité dans Fq.

La matrice de parité H du code de Reed-Solomon de dimension k et de longueur n (où n est nécessairement égal à (q-l) ou un diviseur de (q - 1) ) est une matrice à m n - k lignes et à n colonnes, qui peut être définie par exemple en prenant Hj = o1(i+l)j (O < i < m- 1, 0 < j < n -1), où cx est une 25 racine n ème de l'unité dans Fq. Le polynôme générateur de ce code est m g(x) =f(X- c' i=! Parmi les algorithmes connus pour coder, au moyen d'un code de Reed-Solomon, une séquence _=(a0,a1, ...,ak-1) de symboles d'information appartenant à Fq, certains utilisent cette matrice de parité H. Dans ces algorithmes, on choisit une certaine relation entre les symboles d'information et ceux du mot de code correspondant v (par exemple vi = ai pour O < i < k- 1; dans ce cas, on dit que le codage est systématique ). Puis on calcule les composantes de v restant à déterminer d'après l'équation

T

matricielle H v = 0 o il faut donc résoudre (n-k) équations linéaires sur Fq, ce qui constitue un calcul relativement complexe. D'autres procédés de codage utilisent la divisibilité du polynôme v(x) par le polynôme générateur g(x); c'est notamment le cas de l'algorithme dit euclidien , dont le fonctionnement sera décrit en détail ci-dessous, et qui requiert des calculs nettement moins 10 complexes que les algorithmes, que l'on vient de mentionner, utilisant la matrice de parité H. Pour le décodage des codes de Reed-Solomon, on utilise habituellement un algorithme dit de Berlekamp-Massey pour la détection des positions erronées dans un mot reçu, et un algorithme dit de Forney 15 pour la correction des symboles erronés correspondants. Pour plus de détails sur les codes de Reed-Solomon, on pourra se référer par exemple à l'ouvrage de R.E. Blahut intitulé < Theory and practice of error-control codes , AddisonWesley, Reading, Mass.,1983.

Comme tous les codes, les codes de Reed-Solomon peuvent être 20 raccourcis . On dit qu'un code C, de longueur n, est une version raccourcie d'un code C', de longueur n', s'il ne comprend que les mots v 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 25 n = n'-R. Lorsque C' est un code MDS tel que défini ci-dessus, cela revient à coder, au moyen de ce code raccourci C, des séquences d'information de longueur k = k'-R = k'-n'+n (où k' désigne la dimension du code C') réduite, mais en conservant la même redondance m n'-k'= n - k.

On notera que les codes de Reed-Solomon raccourcis ont pris 30 récemment de l'importance du fait que le codage au moyen d'un nouveau type de code, très efficace, appelé code de géométrie algébrique , peut, dans certains cas, être commodément ramené au codage au moyen d'une pluralité de codes de Reed-Solomon raccourcis (pour une introduction aux codes de géométrie algébrique, on pourra par exemple se référer à l'article de par J.H.

van Lint intitulé Algebraic Geometric Codes , dans Coding Theory and 5 Design Theory , 1ère partie, IMA Volumes Math. Appl., volume 21, SpringerVerlag, Berlin, 1990). Un procédé de codage de ce type a été divulgué dans la demande FR-0301546 au nom de CANON.

On remarquera au passage que, lorsque l'on entend supprimer certaines composantes des mots de code, il importe peu que les valeurs fixes 10 de ces composantes soient toutes nulles; éventuellement, elles peuvent chacune avoir une valeur prédéterminée quelconque.

Manifestement, un code de Reed-Solomon raccourci est encore un code linéaire, mais ce n'est plus un code cyclique. Pour former, à partir d'une séquence d'information, un mot de code appartenant à un code de Reed15 Solomon raccourci, on peut naturellement mettre en oeuvre un algorithme utilisant la matrice de parité H' du code C': il suffit d'assigner, dans les équations représentées par H'-v'T = 0, la valeur zéro (ou une constante respective prédéterminée) auxdites composantes prédéterminées de v'. Mais, comme on l'a dit, cet algorithme utilisant la matrice de parité nécessite des 20 calculs complexes.

Il serait donc souhaitable de pouvoir effectuer ce codage en utilisant un algorithme moins complexe, par exemple l'algorithme euclidien.

Malheureusement, cet algorithme ne permet pas, de façon naturelle, d'imposer une valeur prédéterminée (même nulle) à certaines composantes 25 prédéterminées du mot de code à calculer. Sans entrer dans les détails, on notera simplement ici que l'on connaît certaines manipulations de polynômes permettant d'adapter l'algorithme euclidien à cette exigence, mais uniquement dans le cas où lesdites positions prédéterminées du mot v sont consécutives; or cela est insuffisant par exemple dans le cas des applications aux codes de 30 géométrie algébrique visées par la demande FR-0301546 mentionnée cidessus, dans lesquelles les composantes supprimées en vertu du raccourcissement d'un code de Reed-Solomon ne sont pas nécessairement consécutives.

Selon un autre point de vue, il est connu de < poinçonner les mots de code à la transmission: le poinçonnage consiste à se dispenser de 5 transmettre certaines composantes prédéterminées, quelle que soit la valeur (non prédéterminée dans ce cas) de ces composantes. L'inconvénient du poinçonnage par rapport au raccourcissement est que les composantes supprimées par poinçonnage renferment une partie de la redondance apportée par le codage de canal; il s'ensuit une perte irrémédiable de cette redondance. 10 L'invention concerne donc, selon un premier aspect, un procédé de codage sur un corps de Galois Fq, Oë q est un entier supérieur à 2 et égal à une puissance d'un nombre premier, dans lequel on calcule un mot v'= (V,'l, ...,v'n,_l), où n'>3, appartenant à un code linéaire cyclique MDS C' de dimension (n'-m), où i <m<n'-2, à partir d'un mot 15 a =(ao,al,...,anml) de symboles d'information, où m<n<n'. Un ensemble s=(s0,s1, ...,sn,_l) d'entiers strictement croissants, avec s0 > 0 et sn_<n'-l, ayant été prédéterminé, ledit procédé comprend les étapes suivantes n-l a) on forme le polynôme a(x)- ai-mxsi, i=m b) on calcule le reste r(x) de la division euclidienne de a(x) par le m polynôme g(x)- ,gpxp engendrant ledit code C', p=o n'-I c) on calcule le polynôme v* (x) = a(x) - r(x) =v *i xi, correspondant i=0 au mot v* = (v*O,v*lv...,v*_'-1), et d) on prend v=v* si Sml =m-1; sinon, on obtient ledit mot V' en prenant: S-m m-1 v'=v*+ Y f_ (1) j=o où les mots Ej de longueur n' sont définis par: rJi = gi-j pour j < i < j + m et F/i = 0 sinon, et où les éléments fj de Fq sont calculés au moyen des équations (1) dans lesquelles, pour les (Sm -m) valeurs de i<sm n'appartenant pas à l'ensemble s, chaque composante V'i est prise égale à une constante prédéterminée.

Ainsi, selon l'invention, on code tout mot d'information a de longueur k sous la forme d'un mot v appartenant à un code de Reed-Solomon C' de dimension k' et de longueur n' (avec n'-k'=n-k) de telle manière que les composantes de v situées en (n'-n) positions prédéterminées quelconques 10 soient systématiquement égales à des constantes respectives prédéterminées (par exemple, toutes nulles).

On notera que le procédé selon l'invention est avantageusement simple à mettre en oeuvre. En effet, ce procédé utilise, d'une part, l'algorithme euclidien qui est, comme on l'a dit, de faible complexité par comparaison avec 15 un codage sur C' faisant explicitement appel à une matrice de parité H'.

D'autre part, le procédé selon l'invention comprend la résolution d'un système d'équations linéaires ayant les coefficients fi comme inconnues; or, comme on le verra ci-dessous sur la base d'exemples de réalisation, la dimension de ce système d'équations n'est généralement que de quelques unités.

On pourra naturellement, suite aux étapes succinctement mentionnées cidessus, supprimer ces composantes à valeur fixe pour obtenir un mot v de longueur n appartenant à un code C, qui constitue donc un code raccourci par rapport au code C'. Grâce à l'invention, comme ces composantes de positions prédéterminées prennent, après codage dans C', une valeur fixée 25 à l'avance, leur suppression pour former les mots du code raccourci C n'entraîne aucune perte de redondance.

Pour certaines applications, il peut être intéressant de modifier le code C. Un code CB est une version modifiée d'un code C de longueur n s'il existe une matrice n x n diagonale carrée non-singulière B telle que chaque mot 30 vB de CB est égal à vB avec v dans C. Dans le cas, donc, où l'on souhaite coder des symboles d'information au moyen de mots appartenant au code CB plutôt qu'au code C, on procèdera comme suit.

Dénotons par Pi l'élément de B en position (i,). Alors - on construit, à partir des symboles d'information, le polynôme n-1 5,-1 si a =aB(x) i i=M - on met en oeuvre les étapes b), c) et d) du procédé selon l'invention, en remplaçant a(x) par aB(x), ce qui donne un mot v'B, - on supprime les composantes de valeur prédéterminée de v'B, ce qui donne un mot vB = (vBo,vB1, ...,vnl), et - on calcule le mot v= (vO,vl, .... ,vn) défini par: vi =vBip3i pour tout i de 0 à (n-1).

Selon des caractéristiques particulières de l'invention, n' est égal à m (q-1) ou est un diviseur de (q-1), et g(x)=--(x-oci), où oc est un élément i=1 de Fq vérifiant con =1. Dans ce cas, le code C' est donc un code de Reed15 Solomon, et C est un code de Reed-Solomon raccourci. Ce cas particulier de code linéaire cyclique MDS peut notamment être utile pour le codage au moyen d'un code complexe dont au moins le codage ou le décodage peut être ramené, d'une certaine façon, au codage ou au décodage d'au moins un code de Reed-Solomon raccourci. La présente invention pourra donc, par exemple, 20 s'appliquer au procédé divulgué dans la demande FR-0301546, mentionnée cidessus, dans laquelle ledit code complexe est un code de géométrie algébrique.

Plus généralement, toujours selon le même premier aspect, l'invention concerne un procédé de codage pour codes de géométrie 25 algébrique, comprenant au moins une étape dans laquelle on calcule des mots de code appartenant à un code linéaire cyclique MDS raccourci, ledit procédé étant remarquable en ce que ledit calcul est effectué au moyen de l'un quelconque des procédés de codage décrits succinctement ci-dessus.

Selon un deuxième aspect, I'invention concerne un dispositif de codage sur un corps de Galois Fq, où q est un entier supérieur à 2 et égal à une puissance d'un nombre premier, dans lequel on calcule un mot V'=(V'o0,V'1,

.,V'nl), où n'>3, appartenant à un code linéaire cyclique 5 MDS C' de dimension (n'-m), où 1 < m <n'-2, à partir d'un mot a =(ao,a1, ..., anmrl) de symboles d'information, où m <n <n'. Un ensemble s = (s0,sl, ... ,snl) d'entiers strictement croissants, avec so > 0 et sn1 < n'-l, ayant été prédéterminé, ledit dispositif est apte n-i1 a) à former le polynôme a(x) - a.__xsi i=m b) à calculer le reste r(x) de la division euclidienne de a(x) par le m polynôme g(x)- ,-gpxP engendrant ledit code C', p=o n'-I c) à calculer le polynôme v * (x) = a(x) - r(x) - v *i xi correspondant i=0 au mot v* (v *0,v, * ...,v *n), et d) à prendre v'=_v* si sm-1 =ni-1; sinon, à obtenir ledit mot V' en 15 prenant: Sm -m-1 v'=v*+ f;, (1) j=0 où les mots Fi de longueur n' sont définis par: r FJi = gi-j pour j < i < j + m, et rji =0 sinon, et où les éléments fj de Fq sont calculés au moyen des équations (1) dans lesquelles, pour les (Sm-m) valeurs de i<sm 20 n'appartenant pas à l'ensemble s, chaque composante v'i est prise égale à une constante prédéterminée...DTD: Selon des caractéristiques particulières, n' est égal à (q-l 1) ou est m un diviseur de (q-l), et g(x) =I-(x-oc'), où ca est un élément de Fq vérifiant n i=! n =1.

Selon un troisième aspect, I'invention concerne également divers appareils.

L'invention concerne ainsi, premièrement, un appareil de traitement de données comprenant une source de symboles d'information, ledit appareil étant remarquable en ce qu'il comprend en outre: - une unité de stockage apte à accumuler lesdits symboles de façon à 10 former des mots a contenant chacun un nombre prédéterminé k de symboles, - un dispositif de codage tel que décrit succinctement ci-dessus, et - un transmetteur apte à transmettre les mots v' résultant du codage desdits symboles d'information.

Deuxièmement, l'invention concerne un appareil de traitement de 15 données comprenant une source de symboles d'information, ledit appareil étant remarquable en ce qu'il comprend en outre: - une unité de stockage apte à accumuler lesdits symboles de façon à former des mots a contenant chacun un nombre prédéterminé k de symboles, - un dispositif de codage tel que décrit succinctement ci-dessus, - une unité de raccourcissement apte à supprimer lesdites composantes de valeur prédéterminée de v, de manière à former un mot v de longueur n, et - un transmetteur apte à transmettre les mots v résultant du codage desdits symboles d'information.

L'invention vise également: - 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 codage décrits succinctement ci-dessus, - un moyen de stockage de données partiellement ou totalement 30 amovible, comportant des instructions de code de programme informatique pour l'exécution des étapes de l'un quelconque des procédés de codage décrits succinctement ci-dessus, et - un programme d'ordinateur, contenant des instructions telles que, lorsque ledit programme commande un dispositif de traitement de données 5 programmable, lesdites instructions font que ledit dispositif de traitement de données met en oeuvre l'un des procédés de codage décrits succinctement cidessus.

Les avantages de ce dispositif de codage, de ces appareils de traitement de données, de ces moyens de stockage de données et de ce 10 programme d'ordinateur sont essentiellement les mêmes que ceux des procédés de codage correspondants décrits succinctement ci-dessus.

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 15 l'accompagnent, dans lesquels: - la figure 1 est un schéma synoptique d'un système de codage de symboles d'information selon un mode de réalisation de l'invention, et - la figure 2 représente un appareil de traitement de données comprenant un codeur selon l'invention.

La figure 1 est un schéma synoptique d'un système de codage selon un mode de réalisation de l'invention.

Ce système a pour fonction de coder des informations de nature quelconque à partir d'une source 100. En premier lieu, la source 100 met ces informations sous la forme de symboles appartenant à un certain alphabet (par 25 exemple des octets de bits dans le cas où la taille q de l'alphabet vaut 256), 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 à une unité de codage 102 qui construit un mot précodé v' appartenant à un 30 certain code de Reed-Solomon (au sens strict) C'.

On va à présent rappeler comment fonctionne l'algorithme de codage dit euclidien pour un code linéaire cyclique de longueur n et de polynôme générateur g(x), de degré mni = n - k.

On forme d'abord, à partir de la séquence a=(a0,al,...,akl) de symboles d'information, le polynôme n-i a(x)- Zaimxi i=m On divise ensuite a(x) par g(x), ce qui s'écrit: a(x) = q(x)g(x) + r(x), où q(x) désigne le quotient, et où le degré du reste r(x) est strictement 10 inférieur à m. Si l'on prend alors v(x) a(x) - r(x) , on voit effectivement que v(x) est multiple de g(x), et représente donc bien un mot v appartenant au code. Explicitement, si l'on écrit m-1 r(x) E rix' i=o le mot de code obtenu par cet algorithme euclidien est v = (- ro,...,-rm-laoa,, ...,akl) . Parmi les composantes de v ainsi obtenues, k sont respectivement égales à des composantes de a: il s'agit donc d'un codage systématique .

Par exemple, prenons: q=24, k=10, et n=q-1=15 soit m=. 20 Considérons plus particulièrement le corps de Galois dans lequel un élément primitif Y vérifie: y4 + Y + 1 = 0. Le polynôme générateur est g(x) =-(x-Yi)=x5 + y7x4 +y2x3 +y5x2 +x+1, (2) i=1 qui divise (x15 -1).

Soit à coder par exemple la séquence d'information a = (y4,0,y7,1,0, 0,0, 0,0,0), correspondant au polynôme 8 7 7 4 5 a(x) = x + 7x7 +7 4x5 La division euclidienne de a(x) par g(x) donne alors respectivement un quotient et un reste égaux à 3 2 12 4 4 3 6 2 14 12 q(x) = x3 +Ty x+Y12, r(x) = yx +y 4x3 +T6y x2 + 14x+y12 Finalement (en se rappelant que sur F16, les signes + et - sont équivalents), on obtient 8 7 7 4 5 4 4 3 6 2 14 12 v(x) =- x8 + yx + y 4x + yx4 +y 4x3 + x62 + 14x + , soit v = (712 14,6 4,,4,0,7,1,0,0,0,0,00).

Si à la place, on avait voulu calculer v en résolvant H.vT =0, on aurait travaillé avec la matrice de parité -1 y 72 73 y4 75 76 77 78 79 710 711 712 713 714 1 2 y4 y6 y8 y10 12 y14 y y3 y5 y7 y9 11 y13 H= 73 76 79 y12 1, 3 y6 79 712 1 y3 76 79 712 4 y8 y12 y y5 79 y13,2 y6 y10 y14 y3 y7 1 1 1 5 10 1 75 710 1 75 710 1 75 y101 y5 y10 ce qui implique manifestement de lourds calculs. On voit donc bien grâce à cet exemple que l'algorithme euclidien fournit le mot de code cherché de manière 15 beaucoup moins complexe qu'en utilisant la matrice de parité du code.

La présente invention permet de tirer avantage de cette simplicité en adaptant judicieusement l'algorithme euclidien au cas des codes raccourcis, et ce, quelles que soient les positions des composantes des mots de code v' (de longueur n') destinées à être préservées dans les mots de code raccourcis v (de 20 longueur n). L'ensemble de ces positions sera noté _ = (SO,si, ...Sn-) où les entiers si (0< i<n-l) sont strictement croissants, et naturellement so > 0, sn_1 _ n'-l. Dans le cadre de l'invention, on désigne par C' un code linéaire cyclique MDS , tel que défini ci-dessus, et par C le code obtenu en 25 raccourcissant le code C'.

Plus précisément, le procédé selon l'invention effectue un codage systématique de toute séquence d'information a =(aoal, ...ak1 Il comprend les étapes principales suivantes. n-i

Dans une première étape, on forme le polynôme a(x) Eaimxs i=m (où m n'-k'= n - k) à partir de la séquence d'information a.

Dans une deuxième étape, on calcule le reste r(x) de la division euclidienne de a(x) par g(x), qui est le polynôme générateur de C'. Comme g(x) est de degré m, le degré de r(x) est au maximum égal à (m-1).

Dans une troisième étape, on calcule le polynôme n'-I v*(x)=a(x)-r(x) v *i i=0 correspondant au mot _*=(v*o,v*l, ...,v*n') appartenant à C'. Il importe de noter que, par construction, la contribution de a(x) à v * (x) ne contient que des puissances de x appartenant à s (la plus petite étant supérieure ou égale à Sm).

Deux cas principaux sont alors à envisager pour la quatrième étape du procédé selon l'invention.

Si les m premiers entiers de s comprennent tous les entiers successifs de 0 à (m-l), alors la contribution de r(x) à v*(x) ne contient que des puissances de x appartenant à s (la plus grande étant inférieure ou égale 20 à sm-1 = m -1). Dans ce cas, il suffit de prendre v'= v *.

En revanche, s'il existe au moins un trou dans la succession des m premiers entiers de s (et donc sm_1 > m - 1, Sm > m, et ainsi de suite), on va à présent calculer un mot v' vérifiant: e v'i = v *i pour sm < i < n'-I (contribution de a(x)), et v'i= ci, où les ci sont des constantes prédéterminées, pour tout i<sm n'appartenant pas à s, c'est à dire différent de s0, s1, ..., sm-_1; ces valeurs de i sont donc au nombre de (sm - m).

On notera que v *i =0 pour m < i < (s - 1); mais, dans le cas considéré où sn-1l >m-l, on n'aura pas nécessairement v'i= 0 pour ces indices, même lorsque ci = 0. En effet, selon l'invention, on obtient un mot v' appartenant à C' par combinaison linéaire de v* avec e, où e_ s -m, mots 171_ appartenant à C'judicieusement choisis: e-i v=v* +E jFj (1) j=o0 où les coefficients f1 appartiennent à Fq. Explicitement, cela signifie: É pour s < i < n'-i: v'i=v *i, (1 a) Sm -m-1 * pour mn < i < sm: v'i = E fjFJi, et (lb) j=o Sm -m-1 * pour 0 < i < m v'i = v*i + E fj'Ji. (lc) j=0 Les mots _FJ sont construits à partir des coefficients de m-1 g(x) gpxp. Plus précisément, les mots Fj sont définis comme suit: p=o - pour j < i < j + m: Fi =gij, et (3a) - rJi =0 sinon. (3b) Explicitement: F = (go, g, ..., gm,o,. ,o) F1 = (O, go, g, ..., gmo.... ) Fe-l= (0,...,O, gO,gl,...gm,O,...,0), où la dernière composante non-nulle a pour indice i=sm - 1.

Le polynôme correspondant au mot _F étant identique à g(x), il est évidemment divisible par g(x), et F appartient donc à C'. Les autres mots Fy n'étant que des permutations circulaires de _0 ils appartiennent eux aussi à C'.

Il ne reste plus alors qu'à trouver les e coefficients fj qui satisfont le système de e équations concernées (dans lesquelles on pose v'i = ci, comme 5 mentionné ci-dessus) parmi les n' équations linéaires représentées par l'équation (1). On peut montrer que, avec les définitions (3a-3b), le déterminant de ce système est non-nul quelles que soient lesdites équations concernées cette propriété est liée au caractère MDS du code C'.

Illustrons le procédé décrit ci-dessus au moyen d'un exemple 10 numérique.

Prenons par exemple, pour code C', celui qui a servi ci-dessus d'exemple pour illustrer l'algorithme euclidien (q=24, k'=10, n'=q-l=15, m = 5, etg(x) donné par l'équation (2)). On souhaite le raccourcir pour construire un code C de dimension k = 5 et de longueur n = 10; plus 15 précisément, supposons que l'on veuille obtenir v'i = 0 pour i n'appartenant pas à s = (1, 2,4,5,7,8,10,11,13,14).

Ainsi, Sm =8, et e = 8 - 5 =3, et les trois indices en question (c'est à dire n'appartenant pas à s, et inférieurs à sm = 8) sont: 0, 3 et 6. On obtient alors 20 F =(1,?,y5,72,y7,1,0,...,0), FI =(0,1,yy5,y22,i7,,0,..., 0), F2 =(0,0,1, 7,y5,Y2,y7,1,0,...,0), et donc, en particulier: F0O 0, r03 = 2, F0o6 =0, 25 Flo =0, 13 =Y5, rF16 =1, et F20 = 0, F23 =y, F26 =Y77.

Soit à coder par exemple la séquence d'information a = (y9,0, yll,,o0) . On lui fait alors correspondre le polynôme a(x) = 9] ixTM + 79x8, et la division euclidienne par g(x) donne q(x) =l lx6 +73x5 + 9x4 + 6x3 +1 4x2 + 713 +8, et r(x) =x4 +x3 +13x2 +10+ 8 r(x)=yx +YX +vy X +y x+'Y Par conséquent, v*(x)= xlxi + 9x8 +x4 + x 13 x2 +10X+ 8 et donc: v*0 y8 v *3=y (naturellement, V *6=0).

La résolution des 3 équations (1) donne alors fo= 8, fi =2, f2 = l Finalement, on obtient: v= v*+ 8r0 +211 +7102 =,(14,12,0,1OO010,9,0,O1 1OOO) Dans ce mode de réalisation, une fois le codage terminé, I'unité de codage 102 transmet les mots précodés v' à une unité de raccourcissement 15 20, qui supprime les composantes de v dont l'indice n'appartient pas à l'ensemble s. On obtient ainsi des mots v appartenant au code raccourci C. Ainsi, dans l'exemple numérique que l'on vient de considérer, on obtient: v = (Y14,l12,1,0, y10,y9,0,yil,0, 0) Il est clair, au vu de l'exposé ci-dessus, que les calculs impliqués par le procédé selon l'invention seront d'autant moindres que e est faible. Or on va montrer à présent comment, pour s donné, il est possible, selon un raffinement de l'invention, de minimiser la valeur de e.

Comme on l'a montré ci-dessus, la valeur de e est liée à l'existence de 25 trous dans une succession de m éléments consécutifs de s. Le raffinement en question consiste donc à chercher dans s la séquence de m éléments consécutifs présentant le moins de trous , et d'amener cette séquence au début des mots du code C', en tirant parti du caractère cyclique de ce code.

Cette stratégie sera mieux comprise à l'aide d'un exemple numérique.

Reprenons l'exemple dans lequel le polynôme générateur est donné par l'équation (2), mais considérons cette fois un ensemble de positions prédéterminées donné par: s = (1, 4,6,7,8,9,11,12,13,14) . Ici, sm= s5 =9, et donc l'application stricte du procédé décrit cidessus conduit à former, à partir d'une séquence d'information a de longueur 5, le polynôme 9 Il1 12 13 14 a(x) = aOx9 lx +a2x2 +a3x3 + a4x4.

La division euclidienne permet de construire le mot v* = (-ro,-rl,-r2,-r3, -r4,0,0,0,0,a0,0,al,a2,a3,a4) , dans lequel on se propose, par exemple, de transformer les e = 4 composantes v *0, v *2, v *3, et v *5 en constantes toutes nulles de la manière enseignée par l'invention.

On va monter à présent qu'il existe une autre façon de conduire les calculs, qui est nettement moins complexe car elle conduit à une valeur inférieure de e, à savoir e* = 1.

En effet, on remarque que, dans s, la séquence de 5 positions consécutives 8,9,11,12,13 ne présente qu'un seul trou , à savoir la position n 10. Si donc l'on effectue, sur tous les mots du code C', une permutation circulaire de 8 positions vers la gauche, on amène la position initiale de cette séquence, à savoir la position n 8, en position initiale n 0. Globalement, on transforme ainsi s en 25 s* = (0,1,3,4,5,6,8,11,13,14), en se rappelant que les positions de composantes sont définies modulo n'= 15.

Ainsi, dans s * la seule position manquante en dessous de S*m = *5 = 6 est la position n 2, ce qui correspond en effet à e* = 1.

Dans le langage des polynômes, cette permutation circulaire de 8 positions vers la gauche correspond à une multiplication par x-8 modulo (xl5 -1).

Faisons donc correspondre à la séquence d'information a le polynôme 4 6 7 14 a(x) = aox+alx +a2x + a3x +a4x4, et définissons a*(x) = x-Sa(x) = a4x6 + aOx8 + al 1 + a2x13 + a3x14 La division euclidienne de a * (x) par g(x) donne alors un reste r*(x)=r*4 x4 +r*3 x3 +r **2x2 +r*l x+r*O.

On en tire v * (x) - a * (x) - r * (x), d'où v* = (- r *o,- r *1,-r *2,-r *3,-r *4,0, a4,0, a,0,0, a,O, a2, a3) . Dans ce mot v*, seule la composante v*2 = -r *2 est à la fois nonnulle (en général) et absente de s*. On met alors en oeuvre la technique enseignée selon l'invention, avec donc e*= 1, pour déduire de v* un mot de code v' ayant v'2 = 0.

Il reste toutefois à appliquer aux composantes de ce mot v' une permutation circulaire de 8 positions, cette fois vers la droite, pour retrouver les positions prescrites par s. On obtient ainsi un mot de C' qui est le résultat final du codage selon l'invention de la séquence d'information a.

Les mots v issus de l'unité de raccourcissement 20 sont enfin 20 transmis par l'unité de transmission 103 à un destinataire prédéterminé. Ce destinataire peut par exemple faire partie d'un système de codage complexe (faisant par exemple appel à une multiplicité de codes de Reed- Solomon raccourcis). Ce destinataire peut, selon un autre exemple, être une chaîne de transmission comprenant un modulateur, qui associe un symbole de modulation 25 à chaque nombre prédéterminé de symboles binaires ( bits ), suivi d'un enregistreur ou bien (respectivement) d'un émetteur insérant les symboles dans un canal de transmission, ce canal pouvant être par exemple un stockage sur un support adapté (tel qu'un DVD, ou un disque magnétique ou magnéto- optique, ou encore une bande magnétique), ou bien (respectivement) une émission filaire ou non-filaire (telle qu'une liaison radio).

Le schéma synoptique de la figure 2 représente, de façon très schématique, un appareil de traitement de données 48 incorporant le codeur 102.

Cet appareil 48 comprend un clavier 911, un écran 909, une source d'informations externe 100, et un transmetteur 103, 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 25 ATM, sous forme de séquences de données binaires, et - le transmetteur 103 est adapté à transmettre les mots appartenant au code C, par exemple à une unité appartenant à un système de codage complexe, ou à un dispositif d'émission sur un canal hertzien ou d'enregistrement sur un support pour stockage de masse.

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, - un registre mots _précodés , dans lequel sont conservés les mots 10 v appartenant au code non raccourci, et - un registre mots_code , dans lequel sont conservés les mots v appartenant au code raccourci, avant qu'ils ne soient soumis au transmetteur 103.

La mémoire morte 905 est adaptée à conserver, dans des registres 15 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 n' des mots appartenant au code non raccourci, dans un 20 registre n' , - la longueur n des mots appartenant au code raccourci, dans un registre n , - I'ensemble s des positions des composantes à conserver après raccourcissement, dans un registre s , - le cardinal du corps de Galois Fq servant d'alphabet pour le code utilisé, dans un registre q , - le nombre k = n - m de symboles d'information servant à construire un mot de code, dans un registre k , et - les coefficients du polynôme générateur g(x) du code non raccourci, 30 dans un registre g .

Claims (12)

REVENDICATIONS

1. Procédé de codage sur un corps de Galois Fq, où q est un entier 5 supérieur à 2 et égal à une puissance d'un nombre premier, dans lequel on calcule un mot v'=(v'0,v'1,...,v'n'l), où n'> 3, appartenant à un code linéaire cyclique MDS C' de dimension (n'-m), où 1 < m < n'-2, à partir d'un mot _ = (a, a, ..., an_,-_) de symboles d'information, où m < n < n', caractérisé en ce que, un ensemble _ =( (sO,Sl, ...,S-1) d'entiers strictement croissants, avec 10 so >0 et s-1 <n'-l, ayant été prédéterminé, il comprend les étapes suivantes: n-I a) on forme le polynôme a(x) - aimxsi i =in b) on calcule le reste r(x) de la division euclidienne de a(x) par le m polynôme g(x)- lgpxP engendrant ledit code C, p=O n'-I c) on calcule le polynôme v*(x) = a(x)-r(x) - v * xcorrespondant i=0 au mot v* = (v *0,v *1, ... v*,' ), et d) on prend v'=v* si si-_ =m- ; sinon, on obtient ledit mot v' en prenant: Sm -m-I v=_V*+ fjJ, (1) j=0 où les mots Fi de longueur n' sont définis par: rJi =gi j pour j<i< j+m, et Fi =0 sinon, et où les éléments fj de Fq sont calculés au moyen des équations (1) dans lesquelles, pour les (Sm -m) valeurs de i <Sm n'appartenant pas à l'ensemble s, chaque composante v'i est prise égale à une constante prédéterminée.

2. Procédé de codage selon la revendication 1, caractérisé en ce qu'il comprend une étape supplémentaire consistant à supprimer lesdites composantes de valeur prédéterminée de v', de manière à former un mot v de longueur n.

3. Procédé de codage sur un corps de Galois Fq, où q est un entier supérieur à 2 et égal à une puissance d'un nombre premier, dans lequel on calcule un mot v'=(v'0,v'1, ..., v'n-), où n'> 3, appartenant à un code linéaire cyclique MDS C' de dimension (n'-m), Oë 1 < m < n'-2, à partir d'un mot a = (ao, al, ...,anmrl) de symboles d'information, où m <n <n', caractérisé en 10 ce que, un ensemble s =(sO,sl,..., s,1_l) d'entiers strictement croissants, avec so > 0 et sn_l < n'-l, et une matrice diagonale non-singulière B de dimension n ayant été prédéterminés, il comprend les étapes suivantes: - on construit, à partir des symboles d'information, le polynôme n-1 a (x) aimp xi, i=m où f3i est l'élément de B en position (i,), - on met en oeuvre les étapes b), c) et d) du procédé selon la revendication 1, en remplaçant a(x) par aB(x), ce qui donne un mot v'B, - on supprime les composantes de valeur prédéterminée de v'B, ce qui donne un mot vB = (vB0,vB1, ...,vB-1), et - on calcule le mot v = (v0,v1, ... ,Vnl) défini par: vi = vBi3i pour tout i de0à (n-1).

4. Procédé de codage selon l'une quelconque des revendications précédentes, caractérisé en ce que n' est égal à (q-l) ou est un diviseur de (q-l), et en ce que g(x)=l-(x-ci), où a. est un élément de Fq vérifiant i=l a' =1.

5. Procédé de codage pour codes de géométrie algébrique, comprenant au moins une étape dans laquelle on calcule des mots de code appartenant à un code linéaire cyclique MDS raccourci, caractérisé en ce que ledit calcul est effectué au moyen d'un procédé de codage selon l'une

quelconque des revendications précédentes.

6. Dispositif de codage (102) sur un corps de Galois Fq, où q est un entier supérieur à 2 et égal à une puissance d'un nombre premier, dans lequel on calcule un mot '=v'(V',v'1, ...,'), où n'o3, appartenant à un code linéaire cyclique MDS C' de dimension (n'-m), où 1 < m < n'-2, à partir d'un 10 mot a = (aû,al, ...,anml) de symboles d'information, où m < n < n', caractérisé en ce que, un ensemble s=(s0,sl, ...,sn-l) d'entiers strictement croissants, avec so > 0 et sn-1 < n'-l, ayant été prédéterminé, il est apte n-] a) à former le polynôme a(x) - aimxsi i=m b) à calculer le reste r(x) de la division euclidienne de a(x) par le m polynôme g(x) = gpxP engendrant ledit code C', p=o n'-I c) à calculer le polynôme v * (x) = a(x) - r(x) _ v *i xi, correspondant i=0 au mot v*= (v*0,v*1,....v*nl), et d) à prendre v'=v* si Sm_ =m-1; sinon, à obtenir ledit mot v' en prenant: Sm -m-I v'=v*+ fjFj, (1) j=o où les mots _Fj de longueur n' sont définis par: rJi = gi-j pour j < i < j + m, et FJi = 0 sinon, et où les éléments fi de Fq sont calculés au moyen des équations (1) dans lesquelles, pour les (Sm -m) valeurs de i < Sm n'appartenant pas à l'ensemble s, chaque composante v'i est prise égale à une constante prédéterminée.

7. Dispositif de codage selon la revendication 6, caractérisé en ce que n' est égal à (q-1) ou est un diviseur de (q-1), et en ce que m g(x) = (x-ai), où oc est un élément de Fq vérifiant cn = 1. i=l

8. Appareil (48) de traitement de données comprenant une source de symboles d'information (100), caractérisé en ce qu'il comprend en outre: une unité de stockage (101) apte à accumuler lesdits symboles de façon à former des mots a contenant chacun un nombre prédéterminé k de 10 symboles, - un dispositif de codage selon la revendication 6 ou la revendication 7, et - un transmetteur (103) apte à transmettre les mots v résultant du codage desdits symboles d'information.

9. Appareil (48) de traitement de données comprenant une source de symboles d'information (100), caractérisé en ce qu'il comprend en outre: une unité de stockage (101) apte à accumuler lesdits symboles de façon à former des mots a contenant chacun un nombre prédéterminé k de symboles, un dispositif de codage selon la revendication 6 ou la revendication 7, une unité de raccourcissement (20) apte à supprimer lesdites composantes de valeur prédéterminée de v, de manière à former un mot v de longueur n, et - un transmetteur (103) apte à transmettre les mots v résultant du 25 codage desdits symboles d'information.

10. Moyen de stockage de données inamovible, caractérisé en ce qu'il comporte des instructions de code de programme informatique pour l'exécution des étapes d'un procédé de codage selon l'une quelconque des

revendications 1 à 5.

11. Moyen de stockage de données partiellement ou totalement amovible, caractérisé en ce qu'il comporte des instructions de code de programme informatique pour l'exécution des étapes d'un procédé de codage

selon l'une quelconque des revendications 1 à 5.

12. Programme d'ordinateur, caractérisé en ce qu'il contient des instructions telles que, lorsque ledit programme commande un dispositif de traitement de données programmable, lesdites instructions font que ledit dispositif de traitement de données met en oeuvre un procédé de codage selon

l'une quelconque des revendications 1 à 5. 10