Brevet FR2723455A1 — publié le 19960209

CIRCUIT D'INVERSION D'ELEMENTS D'UN CORPS DE GALOIS La présente invention concerne les circuits permettant d'effectuer des calculs sur des éléments d'un corps de Galois, et en particulier un circuit permettant de calculer les inverses de ces éléments. Un corps de Galois est en ensemble fini de nombres binaires servant, par exemple, à la correction d'erreurs dans les transmissions de données grâce à un codage et décodage Reed-Solomon. L'ensemble des nombres binaires de n bits forme un corps de Galois de 2n=N+l éléments, sur lequel on définit une addition et une multiplication internes, c'est-à-dire telles que la somme ou le produit de deux nombres du corps est également un nombre du corps. L'addition de deux nombres consiste à effectuer un OU exclusif bit par bit entre ces deux nombres. D'o il résulte que, si x est un élément quelconque du corps, on a x+x = 2x = 0. La multiplication est une multiplication classique de deux nombres binaires de n bits tant qu'elle ne génère pas une retenue, c'est-à-dire tant que le résultat ne comporte pas de bits à 1 de poids supérieur à n-1. Dès qu'une retenue est géné- rée, celle-ci est combinée par OU exclusif à des bits prédéter- minés des bits de poids 0 à n-l, définis par un polynôme dit polynôme générateur du corps de Galois. Tout élément non nul du corps de Galois est une puis- sance d'un autre élément non nul et non unitaire de ce corps. Dans un corps de Galois de N+1 éléments, ces puissances sont définies modulo-N, c'est-à-dire que xi=xi+N, o x est un élément non nul et non unitaire du corps de Galois et i un entier positif ou négatif. Les éléments d'un corps de Galois de N+1 éléments sont notés 0, o0, a1,... aN-1. Les éléments sO à "n-1 sont les nombres 20, 21... 2n-1 constituant la base des nombres binaires de n bits. Pour calculer des coefficients de correction dans un décodeur Reed-Solomon, il est nécessaire de calculer des rap- ports y/x, o y et x sont des nombres calculés par le décodeur et pouvant avoir des valeurs quelconques. Pour cela, on multi- plie généralement y par l'inverse de x. Pour calculer un inverse, on peut avoir recours à une table d'inverses stockés dans une mémoire ROM. Toutefois, l'uti- lisation d'une mémoire ROM se prête mal à une intégration parmi les autres circuits de traitement avec les techniques actuelles de conception de circuit intégré. Avec ces techniques, la mé- moire ROM doit être placée en dehors d'une zone o sont intégrés les autres éléments du circuit de traitement. Ceci entraîne une perte de surface notable malgré qu'une mémoire ROM occupe une surface relativement faible. Une autre solution consiste à obtenir les inverses de manière câblée, à l'aide de portes logiques. Toutefois, le ncmbre de connexions entre les portes logiques pour effectuer la fonction d'inversion est si important que les métallisations correspondantes occupent une surface équivalente à la surface perdue entraînée par utilisation d'une mémoire ROM, malgré le fait que 1' inverseur câblé puisse être intégré dans la même zone que les circuits de traitement. Un objet de la présente invention est de prévoir un inverseur d'éléments d'un corps de Galois occupant une surface particulièrement faible. Cet objet est atteint par une décomposition d'une inversion en une suite d'opérations particulières qui sont faisables à l'aide de circuits occupant une faible surface. Une décomposition selon l 'invention fournit un circuit d'inversion d'un nombre de n bits d'un corps de Galois de 2n = N+l éléments, comprenant un élévateur à la puissance t = 2n/2 recevant le nombre à inverser. Un premier multiplieur complet reçoit le nombre à inverser et la sortie de l'élévateur à la puissance t. Un circuit fournit le produit de la sortie de l'élévateur à la puissance t et de l'inverse de la sortie du premier multiplieur complet. Selon un mode de réalisation de la présente invention, le circuit qui fournit le produit comprend un inverseur pour fournir l'inverse de la sortie du premier multiplieur complet parmi t-l valeurs possibles, et un deuxième multiplieur complet recevant la sortie de l'inverseur et la sortie de l'élévateur à la puissance t. Selon une variante, le circuit qui fournit le produit comprend n/2 multiplieurs par une constante dont le i-ème (i=l, 2... n/2) a pour constante 2i, o p est une racine (t-l)ème de l'unité; n/2 multiplexeurs dont le i-ème reçoit la sortie du i-ème multiplieur par une constante sur une première entrée et la sortie du (i-l)ème multiplexeur sur une deuxième entrée, et fournit sa sortie au (i+l)ème multiplieur par une constante, les deuxièmes entrées du premier multiplieur par une constante et du premier multiplexeur recevant la sortie de l'élévateur à la puissance t; et un décodeur recevant la sortie du premier multiplieur complet et agissant sur les multiplexeurs pour mettre en série les multiplieurs dont le produit des constantes est l'inverse de la sortie du premier multiplieur complet. Selon un mode de réalisation de la présente invention, l'élévateur à la puissance t comprend n groupes de portes dont le i-ème (i = 0, 1... n-l), fournit ou non le i-éme élément non nul du corps de Galois selon l'état 1 ou 0 du i-ème bit du nombre à élever à la puissance t; et n-l additionneurs dont le j-ème (j=l, 2... n-l) reçoit la sortie du j-ème groupe de portes et la sortie du (j-l)ème additionneur, le premier additionneur recevant les sorties des deux premiers groupes de portes. Selon un mode de réalisation de la présente invention, le circuit qui fournit le produit comprend t-l multiplieurs par une constante, dont les constantes sont des racines (t-l)èmes distinctes entre elles et de l'unité, recevant chacun la sortie de l'élévateur à la puissance t. Un multiplexeur est commandé par un décodeur pour sélectionner la sortie de l'un des multi- plieurs par une constante en fonction de la sortie du premier multiplieur complet. Un additionneur reçoit la sortie du multi- plexeur et, selon la sortie du premier multiplieur complet, la valeur 0 ou le nombre à inverser. 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 représente un mode de réalisation de cir- cuit d'inversion selon la présente invention; la figure 2 représente un mode de réalisation de cir- cuit élévateur à la puissance d'une puissance de deux utilisé dans le circuit d'inversion de la figure 1; la figure 3 représente un deuxième mode de réalisation de certains des éléments du circuit de la figure 1; et la figure 4 représente un troisième mode de réalisa- tion de certains des éléments du circuit de la figure 1. Selon la présente invention, l'inverse x-l d'un nombre x de n bits est exprimé sous la forme: x-l = xt/xt+l, (1) avec t = 2n/2 Le nombre xt est particulièrement facile à calculer, conmme on le verra ultérieurement, grâce au fait qu'il s'agit d'un nombre élevé à une puissance d'une puissance de 2 (t = 2n/2). Le nombre xt+l est une racine (t-l)ème de l'unité car (xt+l)t-1 = xt2-1 = x2n-1 = xN = 1 Par conséquent, xt+l, quelle que soit la valeur de x, ne prend que l'une des t-l valeurs at+l, a2(t+l)... (t-1)(t+l). Ces t-l valeurs sont notées ci-après respectivement p, p2,... pt-1 Ainsi, on est amené à calculer l'inverse du nombre xt+l qui n'a que t-1 = 2n/2-1 valeurs possibles p, p2... pt-l, au lieu des 2n-1 valeurs possibles de l'inverse d'un nombre quelconque. Par exemple, si n=8, le nombre xt+l a 15 valeurs possibles au lieu de 255. Ainsi, un inverseur du nombre xt+l occupe notablement moins de surface qu'un inverseur d'un nombre quelconque, qu'il soit réalisé à l'aide d'une table en mémoire RCM, ou à l'aide de circuits logiques. En outre, il suffit de ne fournir à cet inverseur que des bits du nombre xt+l qui permettent de distinguer les t-1 valeurs possibles du nombre xt+l. La figure 1 représente un mode de réalisation de circuit inverseur obtenu directement à l'aide de la décompo- sition (1) ci-dessus. Le nombre x, de n bits, est fourni à un élévateur à la puissance t 10. Un multiplieur 12 reçoit la sortie de l'élévateur 10 sur une première entrée et le nombre x sur une deuxième entrée. Un inverseur 14 reçoit la sortie, xt+l, du multiplieur 12 et fournit l'inverse correspondant, x-(t+l), à une première entrée d'un multiplieur 16. Comme on l'a précédemment indiqué, l'inverseur 14 ne doit fournir que t-1 valeurs. Le multiplieur 16 reçoit sur une deuxième entrée la sortie de l'élévateur 10 et fournit l'inverse x-l recherché. Le circuit 10 élévateur à la puissance t, t étant une puissance de 2, est particulièrement simple à réaliser pour les raisons expliquées ci-dessous. Le nombre x s'exprime par x = x0-O0 + Xl-c1 + x2.-2 +... Xnlc n-l, o xo, x l... xn_1 sont les valeurs des bits de poids croissant du nombre x. 5 En élevant le nombre x à la puissance t, t étant une puissance de 2, on élève le deuxième membre à la puissance t, ce qui fournit la somme de termes xi-.it et de termes sup- plémentaires qui se répètent un nombre pair de fois. Du fait que la somme sur le corps de Galois est un OU exclusif bit à bit,10 tous ces termes supplémentaires s'annulent. Ainsi, on a: xt = xo.O + xl-.at + x2.c2t +... xn_.l (n-l)t. La figure 2 représente un circuit élévateur à la puis- sance t directement établi à partir de cette équation. A chaque bit xi (i=0, 1... n-1) est associé un groupe de portes ET 18 qui reçoivent sur des premières entrées le bit xi et sur des deuxièmes entrées les bits respectifs du nombre ait. Ainsi, chaque nombre ait est transmis sur la sortie du groupe 18 correspondant si xi=l. Un premier additionneur 20 reçoit sur une première entrée la sortie du groupe 18 associé au bit xo et sur une deuxième entrée la sortie du groupe 18 associé au bit xl. Des additionneurs 20 supplémentaires sont associés respec- tivement aux groupes 18 restants et chacun reçoit sur une première entrée la sortie du groupe 18 associé et sur une deuxième entrée la sortie de l'additionneur 20 précédent. Le dernier additionneur 20 fournit le nombre xt. Bien entendu, dans chaque groupe de portes ET 18 associé à un bit xi, on prévoit des portes ET pour les seuls bits non nuls du nombre ait. De même, les additionneurs 20 (des groupes de portes OU exclusif) peuvent aussi être simpli- fiés en tenant compte du fait que certaines de leurs lignes d'entrée sont toujours à un état constant. La figure 3 représente un mode de réalisation de circuit destiné à remplacer avantageusement l'inverseur 14 et le multiplieur 16 de la figure 1. Ce circuit comprend n/2 multi- plieurs 22 par une constante. Les constantes de multiplication sont respectivement les nombres p2i, o i varie de 0 à n/2-1. Chaque multiplieur 22 est associé à un multiplexeur 24 qui reçoit sur un premier canal la sortie du multiplieur et sur un deuxième canal la sortie du multiplexeur précédent, qui est aussi fournie à l'entrée du multiplieur. A l'aide de cette disposition, en sélectionnant convenablement les multiplexeurs 24, on obtient une multiplication par n'importe quelle valeur pi, o i varie de 1 à t-1. Le premier multiplieur 22 et premier multiplexeur 24 reçoivent le nombre xt délivré par l'élévateur 10. Le dernier multiplexeur 24 fournit l'inverse x-1 recherché. Un décodeur 26, recevant le nombre xt+l fourni par le multiplieur 12, commande les multiplexeurs 24 de manière que soient mis en série les multiplieurs 22 dont le produit des constantes est égal à l'inverse de xt+l. Le circuit de la figure 3 est particulièrement simple car il utilise des multiplieurs par une constante; le fait d'en prévoir n/2 avec des multiplexeurs associés reste plus simple que de prévoir un multiplieur complet 16. En outre, le décodeur 26 n'a que n/2 sorties au lieu des n sorties requises dans le cas de la figure 1. Comme dans le cas de la figure 1, pour commander le décodeur 26, on ne lui fournit que des bits du nombre xt+l qui permettent de distinguer les t-1 valeurs possibles du nombre xt+l. Dans certaines applications, la structure de la figure 3 pourrait ne pas être assez rapide car le nombre xt doit parfois traverser un grand nombre de multiplieurs 22 qui intro- duisent chacun un retard. La figure 4 représente une alternative particuliè- rement rapide de la structure de la figure 3. Le nombre xt est fourni en parallèle à t/2 multiplieurs 40 par une constante. Les constantes sont respectivement p1 à pt-l1 Les constantes p1 à pt-l sont t-1 racines (t-l)èmes de l'unité distinctes entre elles et de l'unité, et telles que les t-1 racines restantes soient I+p1 à l+p-t_1. En effet, sur un corps de Galois, si un nombre r est racine p-ième de l'unité, le nombre r+l l'est aussi (p étant un entier quelconque inférieur à N+1). Un multiplexeur 42 reçoit les sorties des multiplieurs et sélectionne l'une d'entre elles en fonction d'un signal de commande fourni par un décodeur 44. La sortie du multiplexeur 42 est fournie à une première entrée d'un additionneur 46 recevant sur une deuxième entrée la sortie d'un groupe de portes ET 48. Une première entrée des portes 48 reçoit une sortie du décodeur 44, qui prend un état dépendant de la parité de l'inverse du nombre xt+l. Les deuxièmes entrées des portes 48 reçoivent respec- tivement les bits du nombre x. Ainsi, le nombre x est sommé ou non à la sortie du multiplexeur 42 selon les valeurs du nombre xt+l. Avec cette configuration, on multiplie xt par pi ou l+pi (i=l, 2... ft-1), c'est-àdire par l'une ou l'autre de deux racines (t-l)èmes distinctes de l'unité. Le décodeur 44, en fonction des n-1 bits de poids fort du nombre xt+l sélectionne le multiplieur 40 adéquat pour que le nombre pi ou l+pi par lequel le nombre xt est finalement multiplié soit l'inverse du nombre xt+l. En outre, le décodeur reçoit seulement des bits du nombre xt+l qui permettent de distinguer les t-l racines P1 à Pt-1l Bien entendu, parmi les racines (t-l)èmes de l'unité, il y a l'unité. Si le nombre xt+l est égal à 1, le nombre x est aussi égal à 1, alors, par exemple, le multiplexeur 42 est sélectionné pour fournir le nombre 0 à l'additionneur 46 qui fournit alors la valeur 1 (x) par l'intermédiaire du groupe de portes 48. REVEND ICAT IONS 1. Circuit d'inversion d'un nombre (x) de n bits d'un corps de Galois de 2n = N+l éléments, caractérisé en ce qu'il comprend: - un élévateur (10) à la puissance t = 2n/2 recevant le nombre à inverser (x); - un premier multiplieur complet (12) recevant le nom- bre à inverser et la sortie de l'élévateur à la puissance t; et - un circuit (14, 16) pour fournir le produit de la sortie de l'élévateur à la puissance t et de l'inverse de la sortie du premier multiplieur complet. 2. Circuit d'inversion selon la revendication 1, caractérisé en ce que ledit circuit pour fournir le produit comprend un inverseur (14) pour fournir l'inverse de la sortie (xt+l) du premier multiplieur complet (12) parmi t-1 valeurs possibles, et un deuxième multiplieur complet (16) recevant la sortie de l'inverseur (14) et la sortie de l'élévateur (10) à la puissance t. 3. Circuit d'inversion selon la revendication 1, caractérisé en ce que ledit circuit pour fournir le produit comprend: - n/2 multiplieurs par une constante (22) dont le i-ème (i=l, 2... n/2) a pour constante p2i, o p est une racine (t-l)ème de l'unité; - n/2 multiplexeurs (24) dont le i-ème reçoit la sor- tie du i-ème multiplieur par une constante sur une première entrée et la sortie du (i-1)ème multiplexeur sur une deuxième entrée, et fournit sa sortie au (i+l)ème multiplieur par une constante, les deuxièmes entrées du premier multiplieur par une constante et du premier multiplexeur recevant la sortie (xt) de l'élévateur (10) à la puissance t; et - un décodeur (26) recevant la sortie (xt+l) du premier multiplieur complet (12) et agissant sur les multi- plexeurs (24) pour mettre en série les multiplieurs (22) dont le produit des constantes est l'inverse de la sortie du premier multiplieur complet. 4. Circuit inverseur selon la revendication 1, carac- térisé en ce que l'élévateur (10) à la puissance t comprend: - n groupes de portes (18) dont le i-ème (i = 0, 1... n-l), fournit ou non le i- ème élément non nul du corps de Galois selon l'état 1 ou 0 du i-ème bit du nombre à élever à la puis- sance t; et10 - n-l additionneurs (20) dont le j-ème (j=l, 2... n-l) reçoit la sortie du j- ème groupe de portes et la sortie du (j-l) me additionneur, le premier additionneur recevant les sorties des deux premiers groupes de portes. 5. Circuit inverseur selon la revendication 1, carac- térisé en ce que ledit circuit pour fournir le produit comprend: - t-l multiplieurs (40) par une constante, dont les constantes sont des racines (t-l)èmes distinctes entre elles et de l'unité, recevant chacune la sortie de l'élévateur (10) à la puissance t; - un multiplexeur (42) commandé par un décodeur (44) pour sélectionner la sortie de l'un des multiplieurs par une constante en fonction de la sortie du premier multiplieur complet (12); et - un additionneur recevant la sortie du multiplexeur et, selon la sortie du premier multiplieur complet, la valeur 0 ou le nombre à inverser (x).