Brevet FR2721774A1 — publié le 19951229

DECODEUR REED-SOLOMON La présente invention concerne un décodeur Reed-Solo- mon qui sert à corriger des erreurs subies par des données numé- riques lors d'une transmission (par voie électrique, hertzienne, ou autre), et plus particulièrement une partie de ce décodeur 5 servant à fournir, dans un ordre adéquat, des données à corriger et les valeurs de correction respectives. Un codage Reed-Solomon (RS) consiste à mettre sous forme de codes RS des paquets de données à transmettre, ces données pouvant ensuite être extraites des codes et corrigées au niveau d'un appareil récepteur. Un code RS est un ensemble de M données numériques que l'on associe à des coefficients d'un polynôme de degré M-1 qui est un multiple d'un polynôme généra- teur de degré 2t ayant 2t racines distinctes. Dans une transmis- sion d'un tel code, on peut localiser et corriger jusqu'à t coefficients erronés. Les coefficients d'un code RS sont en outre associés à des éléments d'un corps de Galois. Ainsi, si les coefficients à transmettre sont des nombres de n bits, on utilisera un corps de Galois de 2n éléments, noté GF(2n). Dans ce corps de Galois, un code RS peut comporter jusqu'à N=2n-1 coefficients. Dans un corps de Galois, on définit l'addition et la multiplication de manière particulière. La multiplication est telle que les éléments successifs du corps peuvent être notés 0, O,0l,. .1,... l *N-l et que xi=ai+N, o i est un entier5 positif ou négatif quelconque. Pour transmettre un ensemble de M-2t données aM-2t-1... al, a0 selon un codage Reed-Solomon (M le polynôme a(x) = aM_2tl-xM-2t-1 +... + al-x + ao. Ensuite, on transmet les coefficients du polynôme A(x) = x2t-a(x) + r(x), o r(x) est le reste de la division du polynôme x2t.a(x) par le polynôme générateur. Ainsi, les coefficients A du polynôme A(x) constituent un code RS, et ceux correspondant aux termes de degrés 2t à N-1 sont les coefficients a que l'on cherche à transmettre. Bien entendu, la transmission est susceptible d'erreurs et certains des coefficients A reçus peuvent être erronés. La figure 1 représente une architecture classique de décodeur Reed-Solomon, prévu pour corriger jusqu'à t coef- ficients erronés parmi les coefficients A. Les coefficients A sont fournis au décodeur dans l'ordre correspondant aux termes de degrés décroissants du polynôme A(x). Un circuit 10 fournit les coefficients d'un polynôme syndrome S(x) (ci-après appelé syndrome) de degré 2t-1. Le coef- ficient du terme de degré i (i=0, 1,... 2t-l) de ce syndrome, s'exprime par: Si = A("B+i), o "B+0, "B+l... "B+2t-1 sont les racines du polynôme générateur et B une constante. La figure 2 représente une structure classique du circuit 10 permettant de fournir les coefficients du syndrome. Cette structure comprend 2t compteurs polynômiaux associés respectivement aux coefficients SO à S2t-l du syndrome. Chaque compteur polynômial associé à un coefficient Si du syndrome comprend un registre 12 précédé d'un additionneur 13. Une première entrée de l'additionneur 13 reçoit successivement les coefficients AM_1 à Ao. La deuxième entrée de l'additionneur5 13 reçoit la sortie du registre 12 multipliée par aB+i par un multiplieur 14. A chaque arrivée d'un coefficient Aj, le contenu du registre 12 est remplacé par son contenu initial augmenté de Aj- xB+i. A l'arrivée du coefficient AM_1, le registre 1210 contient la valeur du polynôme A(x) pour x="B+i, c'est-à-dire le coefficient Si du syndrome. Les coefficients A doivent être fournis aux compteurs polynômiaux dans l'ordre correspondant aux termes de degrés décroissants du polynôme A(x). Un circuit 20 de la figure 1 fournit, à partir des coefficients du syndrome, les coefficients d'un polynôme X(x), dit polynôme de localisation d'erreur, de degré inférieur ou égal à t, et d'un polynôme R(x), dit polynôme de correction d'erreur, de degré inférieur à t, tels que x2t.y(x) + X(x).S(x) = R(x) o y(x) est un polynôme que l'on ne cherche pas à déterminer. Le polynôme X(x) a au plus t racines distinctes. Si Jr (r=0, 1,... M-1) est une racine du polynôme X(x), le coef- ficient ANr a été transmis avec une erreur. L'erreur sur ce coefficient s'exprime par er = R(xr)/xr.>'(r) (1) o X' est le polynôme dérivé du polynôme X. Pour trouver les coefficients des polynômes X(x) et R(x) le circuit 20 met en oeuvre l'algorithme d'Euclide. L'article de IEEE Transactions on Computers, Vol. C-34, N 5, Mai 1985, "A VLSI Design of a Pipeline Reed-Solomon Decoder" décrit un exemple d'application d'algorithme d'Euclide et un circuit pour mettre en oeuvre l'algorithme d'Euclide dans cet exemple. Un circuit 30 à la figure 1 sert, à partir des coef- ficients des polynômes A(x) et R(x), à trouver les racines du polynôme x(x) et à calculer les erreurs selon la relation (1). La figure 3 représente une structure classique de la partie du circuit 30 permettant de trouver les racines du poly- nôme x(x). Cette structure calcule successivement les valeurs du polynôme x(x) pour x valant successivement s0, "-1... =i-M. Plutôt que de prévoir M compteurs polynômiaux pour calculer la valeur du polynôme x(x) pour chacune des valeurs sO à al-M, ce10 qui occuperait une surface notable, on prévoit t+l cellules de calcul associés respectivement aux coefficients X0 à \t du polynôme À(x). Chaque cellule associée à un coefficient Xi comprend un registre 32 précédé d'un multiplieur 33 dont une première entrée reçcoit la sortie du registre 32 et une deuxième la valeur a-i=N-i Les sorties des registres 32 sont fournies à des entrées respectives d'un additionneur 34. Initialement, les coefficients XO à Xt sont écrits dans les registres 32 respectifs. L'additionneur 34 fournit alors la valeur du polynôme À(x) pour x=aO=l. Ensuite, les registres 32 sont validés en écriture à chacune de M-1 étapes successives. Ainsi, à la j-ièmne étape, le registre 32 associé au coefficient xi contient la valeur ÀXi. ij. L'additionneur 34 fournit alors la valeur du poly- nôme x(x) pour x="-J. Ainsi, la structure de la figure 3 fournit, en M étapes successives, les valeurs du polynôme x(x) pour x valant successivement s0 à ai-M. A chacune de ces étapes, l'erreur e correspondante est calculée. Si à une étape r, l'additionneur 34 fournit une valeur non nulle, l'erreur er est nulle. Dans le cas contraire, l'erreur er est calculée selon la relation (1). Il en résulte que les erreurs e sont calculées dans l'ordre correspondant aux coefficients des termes de degrés croissants du polynôme A(x). Comme le représente la figure 1, les erreurs e0 à eMl sont successivement fournies à une première entrée d'un additionneur 36. En même temps, l'additionneur reçoit sur une deuxième entrée les coefficients A correspondants, c'est-à-dire5 successivement Ao à AM-1. Les coefficients A sont fournis à l'additionneur 36 par un circuit 40 de retard et d'inversion d'ordre. Le retard introduit est destiné à compenser M cycles de calcul des coefficients du polynôme syndrome par le circuit 10 et 2t cycles nécessaires à fournir les coefficients des poly-10 nômes X(x) et R(x) par le circuit 20. L'ordre de transmission des coefficients A corrigés fournis par l'additionneur 36 est de nouveau inversé par un circuit d'inversion 42 pour rétablir l'ordre de transmission initial. En effet, les circuits permet- tant d'extraire les coefficients a recherchés des coefficients A15 ont également besoin de recevoir les coefficients A dans l'ordre correspondant aux degrés décroissants. Ainsi, un décodeur Reed-Solomon classique néoessite deux circuits d'inversion dont chacun contient au moins M bas- cules gérées par un circuit de commande complexe. Un objet de la présente invention est de prévoir un décodeur Reed- Solomon permettant de fournir les erreurs des coefficients à traiter dans l'ordre de transmission initial de ces coefficients. Pour atteindre cet objet, l'invention est basée sur l'inversion de l'ordre d'essai des racines du polynôme X(x), c'est-à-dire que, au lieu d'essayer les valeurs sO à 1I-M, on essaie les valeurs a1 à aM, ce que permet aussi la structure d'essais successifs de la figure 3. Toutefois, en procédant directement ainsi, les indices des coefficients à corriger correspondants seraient N-1 à N-M qui ne correspondent effecti- vement aux coefficients AM_1 à AO que dans le cas particulier o M=N. Pour que l'inversion des essais soit applicable dans le cas général, la présente invention prévoit en outre de consi- dérer les M coefficients AMl à Ao cornmme les coefficients des termes de plus haut degré d'un polynôme de degré N-1 dont les coefficients des N- M termes de plus bas degré sont nuls. Pour cela, il suffit, dans le circuit de calcul des coefficients du syndrome, d'utiliser le polynôme xN-M-A(x) au lieu du polynômne A(x). La présente invention prévoit plus particulièrement un décodeur Reed-Solomnon recevant des suites de M données de n bits correspondant à des coefficients de polynômes de degré M-1 multiples d'un polynôme générateur de racines successives "B à "B+2t-1, o B est une constante, les coefficients étant asso- ciés à des éléments d'un corps de Galois de N+l=2n éléments dont a est un élément non nul et non-unitaire. Le décodeur comprend 2t compteurs polynémiaux recevant successivement les M données de chaque suite et dont celui de rang i, i=0,1... 2t-l, fournit le coefficient du terme de degré i d'un polynâne syn- drome, égal à la valeur dudit polynôme de degré M-1 pour la racine "B+i. Un circuit fournit les coefficients d'un polynôme de localisation d'erreur de degré au plus égal à t à partir des coefficients du polynôme syndrome. Un autre circuit trouve les racines du polynôme de localisation d'erreur par essais succes- sifs de M valeurs du corps de Galois. Le compteur polynomial de rang i est précédé d'un multiplieur par a(B+i)(N-M) et le circuit pour trouver les racines du polynôme de localisation d'erreur est prévu pour essayer successivement les valeurs a1 à aM. Selon un mode de réalisation de la présente invention, si N=k(N-M), o k est un entier, le décodeur comprend k multiplieurs par respectivement XB (N-M), c(B+1)(N-M)... 0(B+k-l)(N-M), dont celui de rang i, i=0,1l,... k-l, précède les compteurs polynômiaux de rangs i+pk, o p varie entre 0 et la partie entière de (2t-i-l)/k. Selon un mode de réalisation de la présente invention, le circuit pour trouver les racines du polynôme de localisation d'erreur comprend, pour chaque coefficient de terme de degré i du polynôme de localisation d'erreur, un registre stockant ini- tialement ce coefficient et un multiplieur connecté pour succes- sivement remplacer le contenu du registre par son contenu pré- cédent multiplié par ai, la sortie de chaque multiplieur étant fournie à une entrée respective d'un additionneur. Ces objets, caractéristiques et avantages ainsi que d'autres de la présente invention seront exposés plus en détail dans la description suivante de modes de réalisation particu- liers faite à titre non-limitatif à l'aide des figures jointes parmi lesquelles: la figure 1, précédemment décrite, représente schéma- tiquement une architecture classique de décodeur Reed-Solomon; la figure 2, précédemment décrite, représente une structure classique de circuit de calcul des coefficients d'un syndrome; la figure 3, précédemment décrite, représente une structure classique d'un circuit d'essais successifs de racines d'un polynôme de localisation d'erreur; la figure 4 représente un mode de réalisation de circuit de calcul selon l'invention des coefficients d'un syn- drome;25 la figure 5 représente un mode de réalisation de circuit d'essais successifs de racines selon l'invention; et la figure 6 représente un mode de réalisation optimisé de circuit de calcul des coefficients d'un polynôme syndrome. Pour pouvoir corriger M coefficients AM_1 à AO d'un code Reed-Solomon sans modifier leur ordre d'arrivée, la pré- sente invention propose de traiter les M coefficients cornmme s'ils correspondaient aux termes de plus haut degré d'un poly- nôme de degré N-l, les coefficients des N-M termes de plus bas degré étant considérés nuls (N étant le nombre d'éléments rnon nuls du corps de Galois utilisé et M le nombre de coefficients de chaque code Reed-Solomon). Ceci revient à multiplier le poly- nôme initial A(x) par xN-M. Les coefficients du polynôme xN-M-A(x) ainsi obtenu, constituent aussi un code Reed-Solomon 5 puisque les racines du polynôme générateur du polynôme A(x) sont aussi des racines du polynôme xN-M-A(x). En procédant ainsi, le calcul des coefficients du syndrome est modifié puisque celui du terme de degré i s'exprime maintenant par10 S Si = a(B+i)(M-N).A(aB+i). La figure 4 représente un mode de réalisation de circuit de calcul des coefficients du syndrome selon l'inven- tion. On retrouve des mêmes éléments qu'à la figure 2, désignés par des mêmes références. Le circuit diffère de celui de la figure 2 par le fait que chaque compteur polynômial associé à un coefficient Si est précédé d'un multiplieur 44 par a (B+i)(N-M). La figure 5 représente un mode de réalisation de circuit de détermination des racines du polynôme de localisation d'erreur X(x), par essais successifs des valeurs "1 à "M. Les M valeurs successives essayées dans cet ordre correspondent aux coefficients de termes de degrés N-1 à N-M d'un polynôme de degré N-1. Grâce à la multiplication du polynôme A(x) par xN-M, ces coefficients correspondent justement aux coef-25 ficients AM_1 à AO. Les valeurs étant essayées dans l'ordre correspondant à l'ordre d'arrivée des coefficients A, il est inutile de prévoir le circuit d'inversion 42 de la figure 1 et la gestion de l'inversion dans le circuit de retard 40, ce qui constitue une simplification notable du décodeur. Dans ce circuit d'essais successifs, on retrouve des mêmes éléments qu'à la figure 3, désignés par des mêmes réfé- rences. Toutefois, la structure diffère de celle de la figure 3 par le fait que l'additionneur 34 revoit les sorties des multi- plieurs 33 au lieu des sorties des registres 32 et que chaque multiplieur 33 associé à un coefficient Xi reçoit la valeur ai au lieu de a-i. Initialement, les coefficients X0 à Xt sont écrits dans les registres 32 respectifs. Alors, l'additionneur 34 fournit la valeur du polynôme X(x) pour x=al. En M-1 étapes supplémentaires, les registres 32 sont validés en écriture et l'additionneur 34 fournit les valeurs du polynôme X(x) pour x variant de "2 à aM-1. La figure 6 représente un mode de réalisation simpli- fié du circuit de calcul des coefficients du syndrome de la figure 4 dans un cas particulier o N est un multiple de N-M (N=k(N-M)). En effet, dans ce cas, chaque multiplieur 44 associé à un coefficient Si effectue la même multiplication que celui associé au coefficient Sik. Par conséquent, le multiplieur 44 associé au coefficient Si peut être supprimé et le compteur polynômial correspondant sera alimenté par le multiplieur 44 associé au coefficient Si-k. La figure 6 illustre la simplification qui en résulte à l'aide d'un exemple o N=255, M=204, B=0, et t=8, correspon- dant à la norme européenne de transmission par câble ou satel- lite de codes Reed-Solomon dans le cadre de la télévision numé- rique. Dans ce cas, N=5(N-M) et N-M=51. Les compteurs poly- nômiaux associés aux coefficients SO, S5, S10 et SS15 sont direc- tement alimentés par les coefficients A203 à AO. Les compteurs polynômiaux associés aux coefficients S1, S6 et Sll sont pré- cédés d'un multiplieur par "51. Les compteurs polynômiaux associés aux coefficients S2, S7 et S12 sont précédés d'un multiplieur par 2- 51. Les compteurs polynômiaux associés aux coefficients S3, S8 et S13 sont précédés d'un multiplieur par 3- 51. Finalement, les compteurs polynômiaux associés aux coefficients S4, S9 et S14 sont précédés d'un multiplieur par 04-51 Dans cet exemple, on utilise que 4 multiplieurs aux entrées des compteurs polynômiaux à la place des 15 qu'il fau- drait normalement. REVENDICATIONS 1. Décodeur Reed-Solomon recevant des suites de M données de n bits correspondant à des coefficients de polynômes de degré M-1 multiples d'un polynôme générateur de racines suc- cessives cB à "B+2t-1, o B est une constante, les coef- 5 ficients étant associés à des éléments d'un corps de Galois de N+l=2n éléments dont a est un élément non nul et non-unitaire, le décodeur comprenant: - 2t compteurs polynômiaux (12-14) recevant succes- sivement les M données de chaque suite et dont celui de rang i, i=O,1.. . 2t-l, fournit le coefficient (Si) du terme de degré i d'un polynôme syndrcme, égal à la valeur dudit polynôme de degré M-1 pour la racine aB+ i; - un circuit (20) fournissant les coefficients d'un polynôme de localisation d'erreur (x) de degré au plus égal à t à partir des coefficients du polynôme syndrome; - un circuit (30) pour trouver les racines du polynôme de localisation d'erreur par essais successifs de M valeurs du corps de Galois; caractérisé en ce que: - le compteur polynômial (12-14) de rang i est précédé d'un multiplieur (44) par a(B+i)(N-M) et - ledit circuit (30) pour trouver les racines du poly- nôme de localisation d'erreur est prévu pour essayer successive- ment les valeurs "1 à aM. 2. Décodeur Reed-Solomon selon la revendication 1, caractérisé en ce que, si N=k(N-M), o k est un entier, le décodeur comprend k multiplieurs (44) par respectivement aB(N-M) À(B+1)(N-M)... ó(B+k-1)(N-M), dont celui de rang i, i=0,1,... k-l, précède les compteurs polynômiaux de rangs i+pk, o p varie entre O et la partie entière de (2t-i-1)/k. 3. Décodeur Reed-Solomon selon la revendication 1, caractérisé en ce que ledit circuit (30) pour trouver les racines du polynôme de localisation d'erreur (X) comprend, pour chaque coefficient de terme de degré i du polynôme de localisa- 5 tion d'erreur, un registre (32) stockant initialement ce coef- ficient et un multiplieur (33) connecté pour successivement remplacer le contenu du registre par son contenu précédent multiplié par "i, la sortie de chaque multiplieur étant fournie à une entrée respective d'un additionneur (34).10 4. Décodeur Reed- Solomon selon l'une quelconque des revendications précédentes, caractérisé en ce que N=255, M=204, B=0, et t=8.