Brevet FR2549984A1 — publié le 19850201

SYSTEME DE CORRECTION D'ERREURS DE SIGNAUX NUMERIQUES CODES EN CODE DE REED-SOLOMON La présente invention concerne une méthode de codage et de décodage de données numériques par un code correcteur d'erreurs ainsi qu'un codeur et un décodeur mettant en oeuvre ladite méthode Plus précisément, l'invention concerne une méthode de codage et de décodage de données par le code de Reed Solomon et les codeurs et décodeurs qui appliquent cette méthode. Le code de Reed Solomon est décrit par exemple dans l'ouvrage "The Theory of Error-Correcting Codes" par F J Mac Williams et N J A Sloane, North Holland Publishing Company, 1981, Chapitre 10. On rappelle qu'un code de Reed-Solomon dans un corps o champ fini de Gallois CG (q) est un code de Bose, Chaudhuri, Hocquenghem (BCH) de longueur N = q-1. Les codes BCH sont des codes dont le polynôme générateur est par définition le suivant: G(x) = (x amo) (x amo+ 1) (x amo±2) o 6 est la distance désignée Avec 6 = 2 t + 1 si t désigne le nombre d'erreurs à corriger. Les racines de G(x) sont donc les puissances successives d'un élément primitif appartenant à CG ( 2 P) Cela veut dire que dans un mot de code: n-i n-i V(x) = Yn-1 xn + ''' Y n-i xn + ''' Yo Yn-i a deux valeurs possibles O ou 1; et xni détermine la position de Yn-i' Dans un code de Reed Solomon, la caractéristique du corps n'est plus 2 mais un entier premier quelconque b donnant lieu à un corps CG (b P) Chaque Yn-i n'a plus deux formes possibles mais q = bp formes Le coefficient Yn-i est un symbole du code. On définit ainsi des polyn 6 mes dont les coefficients sont non plus seulement les entiers O ou 1 (base 2) mais des éléments de CG (bp) qui seront exprimés par p éléments binaires. Par exemple, si m = O, q = 23 et si le polynôme qui génère les o éléments du corps est égal à x 3 + x 2 + 1, chaque coefficient va 10 s'exprimer sos forme d'un mot de 3 bits. a a 1 O O 1 1 O 1 0 a 3 2 1 0 0 a 2 1 O 1 a + a 1 = 1 a a + a + a + a 4 =a+a =i+a+a 2 2 2 O 1 a= a + a+ + 1 + =l+a 6 2 1 O a a + a 7 2 3 2 2 O O 1 a= a + a = a +a + 1 = 1 On définit alors, comme pour le cas binaire, les racines des polyn 6 mes et pour m = 0, le polyn 6 me générateur du code est: O G(x) = (x-l) (x-a) (x-a) -3 Comme on a pris q = 8, les mots du code ont une longueur de N = 7 symboles Un code C ( 7, 4) contient quatre symboles d'information et trois symboles de contrôle de chacun trois bits Le mot de code s'écrit par exemple 6 5 4 3 2 1 O ( 001) x 6 +( 101)x 5 +(OOO)x 4 +( 000)x+t(O 11)x + 10 x 1 + ( 010)x, V V 45 I(x) R(x) o I(x) désigne les symboles d'information et R(x) les symboles de contr 8 le constitués par le reste de la division de I(x) par G(x). Une erreur est caractérisée par sa valeur et sa position dans un mot de code donné Dans le cas d'un code binaire, il suffit de déterminer la 10 position de l'erreur, sa valeur étant obtenue en complémentant la valeur erronée à la position calculée Donc corriger deux erreurs à l'aide d'un code binaire revient à résoudre un système de deux équations à deux inconnues Par contre, dans le cas d'un code de Reed-Solomon, un symbole du code représente un paquet de p éléments binaires Dans ce cas, deux erreurs sont 15 caractérisées par quatre paramètres, respectivement leurs deux valeurs et positions. L'invention tant en ce qui concerne la méthode de codage que le codeur et le décodeur de code Reed Solomon, va être maintenant décrite en détail en relation avec les dessins annexés, dans lesquels: la Fig 1 représente sous la forme d'un diagramme de blocs le codeur pour code de Reed-Solomon conforme à l'invention; la Fig 2 représente le décodeur pour code de Reed-Solomon conforme à l'invention; et la Fig 3 représente l'algorithme de décodage. -4 1 CODAGE Ainsi qu'on l'a dit dans l'entrée en matière, les symboles du code sont des éléments du champ fini de 2 p éléments Chaque symbole du code comporte p éléments binaires Les symboles de contr 8 le sont obtenus en divisant le message informationnel I(x) par le polyname générateur G(x). Le code comporte m symboles d'information et k symboles de contr 6 le On désigne le code par C(m + k, m) Une méthode de codage bien connue consiste à k prémultiplier I(x) par x, k étant le degré le plus élevé du polyn 6 me générateur et à diviser le produit ainsi obtenu par G(x), soit k x I(x) G(x) o G(x) a la forme polynomiale précédemment indiquée avec k = m + S 1. Le code décrit est un code C ( 255, 247) avec 2 p = 28 d'o G(x) = x + Ax + Bx + Cx + Dx 3 + Ex 2 + Fx + G. Les coefficients A, B, C, D, E, F sont des mots de huit bits. Lorsque le premier symbole apparaît à l'entrée du système, les restes partiels précédents sont nuls Soit S,' ce premier symbole Le circuit 2 stocke temporairement 51 le temps que le circuit 3 fournisse le résultat de la multiplication 51 par chacun des termes du polytime générateur Ces 20 restes partiels sont stockés dans le circuit 1 dans un ordre qui est une caractéristique du système. Quand le deuxième symbole 52 se présente à l'entrée du système, on additionne modulo 2, 52 avec le reste partiel précédent de degrée le plus élevé Le résultat de cette opération est stocké dans 2 Ensuite, le circuit 25 3 effectue les multiplications avec les restes partiels précédents et le -5 processus continue, jusqu'à ce que le 247 ième symbole d'information soit rentré dans le système. Le circuit 1 est une mémoire vive de k mots de p bits. Les circuits 2 et 3 sont des unités de stockage de p bits. Le circuit 4 est un additionneur modulo 2 de p bits. Quant au circuit 5, il est constitué d'une table inaltérable qui, adressée par (Si + Rpi) fournit respectivement les produits de (Si + Rpi) par chacun des coefficients de G(x). Avec S désignant le symbole informationnel d'ordre i et R pi, le i pi reste partiel d'ordre i de même degré que Si. Lorsque tous les symboles d'information constituant I(x) sont entres dans le système, le circuit 1 contient les 8 symboles de contr 8 le rangés dans un certain ordre Symboles qu'il suffit d'appeler en ligne à la suite de k x I(x) pour finir de constituer le mot de code. 2 DECODAGE La méthode de décodage conforme à l'invention utilise un système unique pour calculer: les syndromes d'erreurs; les coefficients du polyn 8 me localisateur d'erreurs; 20 les racines du polynôme localisateur d'erreurs; les diagrammes d'erreurs correspondant aux positions d'erreurs calculées; les corrections. 2549984 ' CALCUL RELATIF A LA CORRECTION DE QUATRE EPREURS. CALCUL DES SYNDROMES V(x) étant un mot de code, s'il y a des erreurs, il s'écrit V'(x) = V(x) + E(x). E(x) étant la configuration d'erreurs apparue au cours de la transmission. Afin de déceler les erreurs à la réception, il faut soit vérifier que les mots reçus sont divisibles ou non par le polynôme générateur, soit vérifier que chaque mot de code admet pour racines les racines du polyn Sme générateur Cette deuxième solution est celle utilisée pour le décodage de la présente invention. Un mot de code t (x) s'écrit sous la forme d"'un polyn Sme de la manière suivante, ainsi qu'on l'a vu précédemment V (x) = y xn-l + y xn-2 + + y ni+ + x ( 1) V(x)-1 xn +Y-2 x + +yx+ + Yo Si V(x) admet aj pour racine cela s'écrit: V(aj) = Yn_l(a J)n-l + Yn-2 (a J)n 2 + + n_i(a J)n-i + * + Yo ai i=o À À V(a J) = L(aa) = Sj ( 2) i=n-1 S'il y a une erreur, on reçoit non plus le mot de code V (a J) 20 mais le mot de code V' (aj) = V (aj) + E (aj) = S. puisque V (ai) = O Sj est le syndrome d'erreur d'ordre j, il faut calculer les syndromes S avant de pouvoir déterminer la position et la valeur des erreurs. J -7 Si on reçoit un mot erroné, il y a donc une certaine configuration d'erreurs E(x) dont chacune peut être repérée par un couple xi, Yi (position et valeur). CALCUL DES COEFFICIENTS DU POLYNOME LOCALISATEUR D'ERREURS A PARTIR DES SYNDROMES Si on veut corriger t erreurs, le polyn Sme localisateur d'erreurs s'écrit: Xi +o x +a 2 xt 2 + Xi + ot O ( 3) Les coefficients Oc, 2 t sont obtenus en résolvant le système suivant: St + 01 St_ 1 + 02 St-2 + aj St_ + t SO = O St+l + 1 St + 02 St-1 + Si = O 52 t-1 + a 1 52 t-2 + + at St-i = O Soit A le déterminant principal du système, il est égal à 15 St_ 1 St_ 2 St_ 1 - -S = St St-1 St-i+l S . 52 t-i 52 t-2 ' i St En appliquant les règles sur la résolution des systèmes d'équations linéaires, il vient: a = A / A o i i St-l St_ 2 St S A= t St+l S. 52 t-1 52 t-2 52 t-1 t-1 Les coefficients de polynôme localisateur d'erreurs ont donc pour valeurs respectives les valeurs suivantes: ot = At / C i = Ai / A 4 = A 1 /à ( 4) CALCUL DES RACINES DU POLYNOME LOCALISATEUR D'ERREURS L'équation ( 3) n'étant résoluble que si elle est au plus du quatrième degré, le système peut corriger jusqu'à quatre erreurs. Les positions des quatre erreurs sont donc solutions de: X 4 + C 1 X 3 + a 2 X 2 + a 3 X + 4 = O ( 3 ') Cette équation peut aussi se mettre sous la forme bicarrée: (x + Xx + u) (x + XI X + P') = O ( 5) Avec a 1 = X + À' ( 2 = + P' + X Xit ( 6) 03 = tp' + À'P j 04 = p P' Pour localiser les erreurs, il suffit de déterminer les valeurs de À, X', M et p' puis les racines de chacune des équations du second degré Pour résoudre le système ( 6), deux cas se présentent suivant que a 1 est nul ou non nul, en effet Le système ( 6) devient pour a 1 = O x+x' = O a 2 = P + ' + 2 ( 7) D'o a 3 = x (P + P) a 4 = Pp' a _ 3 + X 2 x 3 + o 2 X + 3 ( 8) Cette équation est du troisième degré en X et fournit une 10 racine i 1 ' Les quantités p et p' est solution d'une équation du second degré, sachant que: P + P' = a 3/ À 1 pe = oa 4 p et p' sont racines de 2 + (a 3/X 1) + a 4 = O Pour o 1 4 Pour a( 1 0, on a en posant: a 1 = À + X p = x X' ( 9) ( 10) On aboutit à une équation du troisième degré en p, soit: P + ( 3 + 2) P ( Y 44 a 3 + 1 + 2 C 3 0 ( 11) On en tire une racine p 1 par exemple D'o X et À' sont solution d'une équation du second degré, soit: 2 + % 1 + P= O ( 12) Le système ( 6) permet alors de déduire les valeur de p et de '. RESOLUTION D'UNE EQUATION DU TROISIEME DEGRE DE TYPE ( 8) ou ( 11) Ces deux équations sont de la forme: y + Vy + T = O ( 13) Cette équation peut se mettre sous la forme canonique (coefficient de y égal à l'unité) en posant: z = y/v 1/2 et Q = T 3/2 ce qui donne: z 3 + z + Q = O z +z+Q= O ( 14) 2549984 ' Si p est pair, deux cas se présentent pour trouver une racine cubique dans le corps CG ( 2). 1) v = O L'équation ( 13) devient: y + T = O est donné par une table. 3 = T 1/3 y T Ensuite: Y 1 + Y 2 + Y 3 = O Yl Y 2 Y 3 = Y 1 et Y 2 sont alors solution de: y y+ 3 + T/y 3 = O ( 15) Equation qui se met sous la forme canonique suivante: Y + Y + R = O ( 16) avec Y = y/y 3 R =T/ y 3 = 1 2)Si v # 0, il faut alors résoudre l'équation ( 14) z 3 est obtenu par une table adressée par Q Les racines z 1 et z 2 sont obtenues par une méthode identique à celle qu'on vient de voir pour v = O et R # 1. La Fig 3 représente l'algorithme de décodage. Le nombre d'erreurs que l'on s'impose de corriger est de quatre, trois ou deux. La phase 101 représente le calcul des syndromes qui dans notre cas seront au nombre de 8, 57 à SO La phase 102 représente le calculde (A)4, (A)3, (A)2, déterminant principal dans le cas de 4, 3 ou 2 erreurs ainsi que celui de Ai, i variant de 1 à 4, soit: A = A 1 A 2, A 3 A 4. Si (A 4) est différent de zéro (phase 103), on en déduit qu'il y a 4 erreurs, et on va vers la phase 104 o l'on calcule l, 02, ( 3 Y 04, 10 définis par les équations ( 4). Si O 1 # O phase 105, on passe à la phase 106 de calcul des racines de l'équation en p (équation ( 11)), puis à la phase 107 de calcul des racines X, À' de l'équation ( 12), enfin à la phase 108 de calcul des p et I' par les équations ( 6). On pose ensuite à la résolution de l'équation ( 5) (phase 109), ce qui donne X 1, X 2, X 3, X 4 et on déduit l'adresse de l'erreur à l'aide de la formule ( 17) Enfin, phase 110, on calcule y 1 à y 4 par la formule ( 18). Si (phase 105) on a a O = 0, les phases ( 106-108) sont remplacées 20 par les phases ( 111-112) qui correspondent respectivement à la résolution de l'équation en À 3 (équation ( 8)) et à la résolution de l'équation en i 2 (équation ( 9)). L'algorithme de la Fig 3 représente également les phases de décodage dans le cas de la correction de trois erreurs et de deux 25 erreurs Dans ces deux cas, l'équation ( 3 ') devient: trois erreurs X 3 + + O 1 X + 2 X + 3 = O ( 3 ") deux erreurs X 2 + e 1 X + a 2 = ( 3 "') L'équation ( 3 ") peut être mise sous la forme canonique et une des racines est obtenue par la formule de Cardan (phase ( 206)). Les deux autres racines sont obtenues en résolvant une équation du second degré en X (phase 207). On voit sur la Fig 3 qu'il y a équivalence entre les phases ayant pour numéros de centaines 1, 2, 3, 4 et les mêmes numéros d'unités et de dizaines. Dans tous les cas de figures à la valeur des coefficients près, on est ramené à la résolution d'une équation du troisième degré 10 ou du deuxième degré mise sous forme canonique. La position effective des erreurs est déterminée de la façon suivante: Sachant que X est de forme X = aji (aji étant un élément 1 i CG ( 2 P), ii caractérise la position de l'erreur d'o: ji = Loga (Xi) ( 17) La détermination des Xi permet alors de calculer les diagrammes d'erreurs yi correspondants. SO = Y 1 + Y 2 + Y 3 + Y 4 51 Y 1 X + Y 2 X 2 + Y 3 X 3 + Y 4 X 4) 1 1 1 2 2 3 3 44) 2 2 2 2 18 52 = Y 1 X 1 + Y 2 X 2 + Y 3 X 3 + Y 4 X 4) 54 Y X 3 + Y 22 + Y 3 3 + Y 4 Y 4) 54 = 1 X 1 2 2 X 3 3) Ln 44 O x x ( (./3 X CD en Il (./' x r SX j x l - 1 F-. r-. (A 3 CA (A 3 w rla X x x l \ rli x x X x W x xe > j- W j- rl% x > &- w W W r w x X X> j-. I 1-. l M UI c_ o ul r IN cl l> f-. w,, (A -L I-à I-à X X 1 W # PID e) n c.> W -P r > r./3 r,3 XP X P x r.> c-o I-à :%, :,/ Xi I-à Ln CD À o * (./3 I- I Ln I MI vil %o, "o 1 coe I- 2549984 ' En se référant à la Fig 2, au fur et à mesure de l'arrivée des symboles, le décodeur calcule S conformément à l'équation ( 2) J pour une valeur de j donnée Cette opération est réalisée autant de fois que G(x) a de racines. Le circuit 11 calcule pour un symbole d'ordre Z y, (a J) pour une racine x = a. Ce résultat est alors stocké temporairement dans le circuit 12. Le décodeur appelle la somme des (n-k) termes précédents, stockée dans le circuit 10, le circuit 11 étant transparent Le circuit 10 13 effectue la somme: 9,-l Z yi (aj)i + Y (ai) i=n-l Le calcul de cette opération transite à travers l'unité de 15 stockage 14 et le circuit 15 qui est transparent pour être stocké dans le circuit 10 jusqu'à l'arrivée du symbole suivant et l'opération décrite se renouvelle jusqu'à l'arrivée du dernier symbole Les différents syndromes sont stockés dans le circuit 10. Le décodeur est formé de trois unités de stockage: le circuit 10 qui est une mémoire vive de u mots de p bits, u étant une caractéristique du système, les circuits 12 et 14 qui sont des unités de stockage de p bits. Un circuit 13 qui lors du calcul des syndrômes, fonctionne en additionneur modulo 2. Un circuit Il qui est une table dont une zone réservée multiplie le symbole présent à son entrée par les racines du polyn Sme générateur dans un ordre que le système définit à l'avance. Un circuit 15 qui est une table dont on utilise une zone transparente lors de cette opération. Les opérations nécessaires pour calculer les différents déter10 minants sont la multiplication et l'addition modulo 2. La multiplication de deux éléments du champ d'extension C G ( 2 P) est remplacée par l'addition modulo ( 2 P-1) des logarithmes à base a de ces deux nombres, a étant un élément primitif du champ C G ( 2 P). CAS DE LA MULTIPLICATION La valeur d'un syndrome stocké dans le circuit 10 transite dans le circuit 11 qui en donne le logarithme Ce résultat est stocké dans le circuit 12 En utilisant le même processus on calcule par exemple le logarithme d'un autre syndrome A ce moment les sorties des circuits il et 12 attaquent le circuit 13 fonctionnant dans ce cas 20 bien précis en additionneur modulo ( 2 P-1) Le résultat de l'addition des deux logarithmes est stocké dans le circuit 14 A cet instant le circuit 15 fournit l'antilogarithme du résultat issu de 14, résultat qui prend place dans une zone réservée du circuit 10. CAS DE L' ADDITION Dans ce cas les circuits 11 et 15 sont transparents et le circuit 13 fonctionne en additionneur modulo 2. Les coefficients O 1 a 2 " vi 'at calculés par la méthode ci-dessus sont stockés dans les zones bien définies du circuit 10. R e v e N d i c a t i o N s 1 Système de codage en code de Reed-Solomon permettant d'effectuei le calcul des symboles de contrôle à adjoindre aux symboles d'information, caractérisé en ce qu'il comporte une table ( 5), trois unités de stockage ( 1, 2, 3) et un additionneur modulo 2 ( 4) le tout permettant d'effectuer des multiplications d'une part et d'additionner modulo 2 des termes de degrés identiques, de les stocker dans une unité ( 1) telle qu'on puisse les reconnaître à chaque étape de la division d'autre part, ledit système du codage permettant de calculer des symboles de contrôle des codes de Reed-Solomon dont les symboles sont dans un champ fini 10 CG ( 2 P), p pouvant avoir une valeur quelconque 2 Système de calcul des symdr 8 mes d'erreurs dans un code de Reed-Solomon permettant de calculer k syndromes d'erreurs, caractérisé en ce qu'il comprend trois unités de stockage ( 10, 12, 14), le circuit ( 10) étant une mémoire vive de u mots de p bits, u étant une caracté15 ristique du système, les circuits ( 12) et ( 14) étant des unités de stockage de p éléments binaires, un circuit ( 13) qui lors du calcul des syndromes, fonctionne en additionneur modulo 2, un circuit ( 11) qui est une table dont une zone réservée multiplie le symbole présent à son entrée par les racines du polynôme générateur dans un ordre que le système définit à l'avance, et un circuit( 15)qui est une table dont on utilise une zone transparente lors de cette opération. 3 Système conforme à la revendication 2 permettant en outre de calculer les t coefficients de p bits du polynôme localisateur d'erreurs, caractérisé en ce qu'un circuit ( 16) testé successivement la valeur des' 25 déterminants (A)4 (A)3, (A)2 (A)1 jusqu'à l'instant o il trouve (A)i O et à ce moment et suivant la valeur de i, le circuit ( 16) délivre une information qui indique le nombre d'erreurs rencontrées d'une part et permet au système de calculer les coefficients Ci correspondant au nombre d'erreurs à corriger d'autre part. 4 Système conforme aux revendications 2 et 3, caractérisé en ce que le circuit ( 10) détecte le type d'opération à effectuer afin de l'indiquer au>circuit ( 13) qui, suivant le cas, se positionne en additionneur modulo 2 ou modulo ( 2 p-) et que les circu{ts'( 1 l) et ( 15) -19 sont des tables dont certaines zones fournissent respectivement Loga (ai) et Loga (a), ai étant un élément de CG ( 2 P), et qu'en outre, le système possède au travers du circuit ( 16) un détecteur de configurations d'opérations interdites telles que Loga ( 0), le système permet de réaliser le calcul de a 1 à a 4. Système conforme aux revendications 2, 3 et 4, caractérise en ce que le circuit ( 16) permet, à la suite de tests successifs, de déterminer'le nombre d'erreurs apparues, et que dans le cas o il y a quatre erreurs, le systnme en calcule les positions à partir d'équations 10 du troisième degré et du second degré mises sous forme canonique, et qu'en outre, le circuit ( 15) est constitué de manière telle qu'il détecte les cas o l'équation du troisième degré n'a pas de solutions afin d'ada Dter la procédure de poursuite des calculs. Système conforme à la revendication 2, caractérisé en ce que le circuit ( 15) est une table inaltérable dont certaines zones fournissent les racines d'une équation du troisième et du second degré mises sous forme canonique. 7 Système conforme aux revendications 2 et 3, caractérisé en ce que la conjonction des circuits ( 15) et ( 16) évite d'ajouter des erreurs 20 supplémentaires lorsqu'il apparaît plus de quatre erreurs.